I'd like to use goreduce to reduce a test case, but the reproduction of the test case (golang/go#20272) involves some machinery--running the compiler multiple times and checking for identical output. Instead of adding mechanism to goreduce to do that, it'd be nice to have a mode a bit like git bisect run.

Here's a rough sketch. I provide an executable to goreduce; it accepts a path argument (file? dir? not sure). goreduce generates a reduction, writes it to disk, and calls my executable with its path. My executable indicates whether it reproduces, or doesn't, or is somehow invalid, with a return code. When minimization is complete, goreduce writes the minimal reduction to disk somewhere, prints the path to it, and exits.

Right now we do this with basic literals only. For example, we try to replace "foo" with "" and 123 with 0.

But we could do this with basically all expressions, being more aggressive:

• getInt() could be replaced with 0
• someStruct could be replaced with Struct{}
• 1.0 * 10.0 - 2 could be replaced with 0.0

I need to think about this, however. It might not always be a good idea. And sometimes the result might be awkward, since we might need parentheses or type conversions to make it compile properly.

Also worth noting that we could instead go for doing these step-by-step. The third example should be doable by replacing each literal and removing BinaryExpr sides. The second should be done by inlining a variable and zeroing the composite literal.

The first one will also be done, once we're able to inline somewhat complex func calls.

So need to also think whether or not this would make the tool able to reduce more programs. If not, we have to be careful if this is for performance because it may well actually make the tool slower.

Like we do with unused imports, which cause soft errors.

So this:

goreduce -match 'crash string' . "go build"

Would become:

goreduce . "go build |& grep 'crash string'"

And we would want a zero exit code. (the |& is just to match stderr too)

Advantages:

• Simpler tool (one less flag)
• The logic is no longer tied/restricted to a regex

Disadvantages:

• Basic shell commands become more complex
• Most usages can be expressed in terms of a regex (I think?)

Leaning towards doing this, just thinking outloud.

Right now we walk the entire file containing the func to reduce. This has several disadvantages:

• Code that isn't executed when running the func might be reduced, losing everyone's time
• Code in separate files isn't reduced

We should instead start the walk on the func. To also walk nodes referenced by our func, we should walk any nodes referenced by name. It's important to keep a set of what we've already traversed to avoid infinite loops.

Another advantage of this is that this method would give priority to the actual execution flow of the program. We would try deleting the highest statements first, etc.

As suggested by @rogpeppe, if we know we're after a run-time crash, we can take many assumptions safely that we can't if we're after compiler bugs. Some examples:

• Code that isn't being run can be removed (via code coverage)
• Statements after a panic/return can be removed (likely covered by the item above)
• Packace members (vars, consts, types) that aren't used can be removed (perhaps exclude exported ones)

Anything else?

Also note that none of these should make the tool better at reducing a program (I think?). They should only make it faster since it can get rid of many things at once instead of one by one.

This is one of those 'obvious in hindsight' things.

goreduce deleted my testcase. I don't know what I expected, but I wasn't expecting it to be destructive to my input. It seems that this is coupled with another issue (or PEBKAC), because goreduce didn't respect my -match string as I expected either, so it managed to delete just almost the entire input.

Luckily, I had a copy of it around. But I think if you're going to modify the input in place there should be a bright red warning somewhere - at least it should be mentioned in the README - or a flag where the user can signal that they understand what is going to happen (--inplace).

I also note that the text of the README might leave one to believe the input would be preserved, because it says that the runs should be reproducible for same input (implying to me that you should be able to repeatedly run it from the same input).

We have rudimentary support for inlining blocks. Once that gets better (i.e. clashing names) and we have better support for inlining vars (#11), we could look into inlining func calls.

This will likely be tricky though, so not looking into it yet.

This is step 1 towards inlining func/method calls.

The tricky bit is scopes - if a block's scope and its parent have any colliding names, they need rewriting.

I'm on go version devel +5e954047bc Fri Mar 24 20:07:15 2017 +0000 linux/amd64.

The following code:

package b

func Func2107() {
	if false {
		Var2528 := (**[1]*int)(nil)
		(func() map[interface{}]uint {
			return map[interface{}]uint{}
		})()[interface{}(nil)]--
	}
}

crashes goreduce when run as goreduce -match="cannot inline" . Func2107 with:

panic: types.Check should not error here

goroutine 1 [running]:
main.(*reducer).reduceLoop(0xc4200ac8c0, 0x0)
	/home/alberto/gocode/src/github.com/mvdan/goreduce/reduce.go:230 +0x2b8
main.reduce(0x7ffceafc94ad, 0x1, 0x7ffceafc94af, 0x8, 0x7ffceafc949f, 0xd, 0x7ff880, 0xc42000c020, 0xc42000e220, 0x0, ...)
	/home/alberto/gocode/src/github.com/mvdan/goreduce/reduce.go:150 +0x1213
main.main()
	/home/alberto/gocode/src/github.com/mvdan/goreduce/main.go:44 +0x10e

This one is easy. We can start with untyped ones, which are the easiest.

We could have a rule for this too, but this would be a good shortcut.

Like #10, but slightly trickier. In particular, a lot more things can be vars than consts (slices, structs...). Can be restricted as a start.

Getting:

# github.com/mvdan/goreduce
./reduce.go:292:7: unknown field 'Node' in struct literal of type interp.Runner
./reduce.go:297:12: not enough arguments in call to runner.Run
	have ()
	want ("github.com/mvdan/sh/syntax".Node)

Right now, the tests suck for two reasons:

• They're slow. go test takes almost 4s on my machine even when they are parallel.
• We are merging different tests in single files to speed them up, reducing maintainability.
• They will only get slower as we add more rules to add tests for.
• We can't test against compiler crashes, as we can't depend on real ones.

This can be fixed if the Go toolchain in the tests is replaced by an interface. By default it would be a mock like a regex match, but with a flag like -gotool we would actually use the Go toolchain like we do now.

This would allow adding a regression test for programs like the one in #13.

I was checking out your project and ran across this panic.

Built with go version go1.8.3 darwin/amd64, latest goreduce commit 126d2e99d.

Possibly related to #13?

Source:

package main

import "fmt"

var b []int

func main() {
	fmt.Println(a())
}

func a() string {
	_ = b[0]
	return "hello"
}

Command:
goreduce -match 'index out of range' -call main .

Output:

panic: types.Check should not error here: main.go:8:2: undeclared name: fmt [recovered]
	panic: types.Check should not error here: main.go:8:2: undeclared name: fmt

goroutine 1 [running]:
go/types.(*Checker).handleBailout(0xc420236000, 0xc420109a68)
	/Users/kale/goroots/go1.8/src/go/types/check.go:213 +0xa4
panic(0x127ade0, 0xc4200e3280)
	/Users/kale/goroots/go1.8/src/runtime/panic.go:489 +0x2cf
main.reduce.func1(0x13fdca0, 0xc4200e5770)
	/Users/kale/go/src/github.com/mvdan/goreduce/reduce.go:159 +0x1cd
go/types.(*Checker).err(0xc420236000, 0x39, 0xc420071a80, 0x14, 0x0)
	/Users/kale/goroots/go1.8/src/go/types/errors.go:78 +0x11c
go/types.(*Checker).errorf(0xc420236000, 0x39, 0x12dc9ba, 0x13, 0xc4201079e8, 0x1, 0x1)
	/Users/kale/goroots/go1.8/src/go/types/errors.go:86 +0x95
go/types.(*Checker).ident(0xc420236000, 0xc4200e6e80, 0xc420070240, 0x0, 0x0, 0x0, 0x0)
	/Users/kale/goroots/go1.8/src/go/types/typexpr.go:30 +0xfff
go/types.(*Checker).exprInternal(0xc420236000, 0xc4200e6e80, 0x13ffe60, 0xc420070240, 0x0, 0x0, 0x0)
	/Users/kale/goroots/go1.8/src/go/types/expr.go:989 +0x1aa5
go/types.(*Checker).rawExpr(0xc420236000, 0xc4200e6e80, 0x13ffe60, 0xc420070240, 0x0, 0x0, 0x0)
	/Users/kale/goroots/go1.8/src/go/types/expr.go:945 +0x8d
go/types.(*Checker).exprOrType(0xc420236000, 0xc4200e6e80, 0x13ffe60, 0xc420070240)
	/Users/kale/goroots/go1.8/src/go/types/expr.go:1524 +0x5f
go/types.(*Checker).selector(0xc420236000, 0xc4200e6e80, 0xc420070280)
	/Users/kale/goroots/go1.8/src/go/types/call.go:336 +0xb0
go/types.(*Checker).exprInternal(0xc420236000, 0xc4200e6e80, 0x14001a0, 0xc420070280, 0x0, 0x0, 0x0)
	/Users/kale/goroots/go1.8/src/go/types/expr.go:1180 +0x1fdd
go/types.(*Checker).rawExpr(0xc420236000, 0xc4200e6e80, 0x14001a0, 0xc420070280, 0x0, 0x0, 0x0)
	/Users/kale/goroots/go1.8/src/go/types/expr.go:945 +0x8d
go/types.(*Checker).exprOrType(0xc420236000, 0xc4200e6e80, 0x14001a0, 0xc420070280)
	/Users/kale/goroots/go1.8/src/go/types/expr.go:1524 +0x5f
go/types.(*Checker).call(0xc420236000, 0xc4200e6e80, 0xc4200e61c0, 0xc4200e2e82)
	/Users/kale/goroots/go1.8/src/go/types/call.go:15 +0x66
go/types.(*Checker).exprInternal(0xc420236000, 0xc4200e6e80, 0x13ffa60, 0xc4200e61c0, 0x0, 0x0, 0x106c3c1)
	/Users/kale/goroots/go1.8/src/go/types/expr.go:1375 +0x1e5d
go/types.(*Checker).rawExpr(0xc420236000, 0xc4200e6e80, 0x13ffa60, 0xc4200e61c0, 0x0, 0x0, 0x0)
	/Users/kale/goroots/go1.8/src/go/types/expr.go:945 +0x8d
go/types.(*Checker).stmt(0xc420236000, 0x0, 0x13ffca0, 0xc4200e2260)
	/Users/kale/goroots/go1.8/src/go/types/stmt.go:318 +0x4a32
go/types.(*Checker).stmtList(0xc420236000, 0x0, 0xc4200e2270, 0x1, 0x1)
	/Users/kale/goroots/go1.8/src/go/types/stmt.go:110 +0xb8
go/types.(*Checker).funcBody(0xc420236000, 0xc420072fa0, 0xc4200e2200, 0x4, 0xc4200e56b0, 0xc4200e42a0)
	/Users/kale/goroots/go1.8/src/go/types/stmt.go:42 +0x196
go/types.(*Checker).functionBodies(0xc420236000)
	/Users/kale/goroots/go1.8/src/go/types/resolver.go:443 +0xdf
go/types.(*Checker).checkFiles(0xc420236000, 0xc4200f0078, 0x1, 0x1, 0x0, 0x0)
	/Users/kale/goroots/go1.8/src/go/types/check.go:229 +0xf2
go/types.(*Checker).Files(0xc420236000, 0xc4200f0078, 0x1, 0x1, 0xc4200e5170, 0xc420070380)
	/Users/kale/goroots/go1.8/src/go/types/check.go:218 +0x49
go/types.(*Config).Check(0xc4200ec060, 0x7fff5fbff81e, 0x1, 0xc4200e6080, 0xc4200f0078, 0x1, 0x1, 0xc4200a36d0, 0xc4200a3770, 0x0, ...)
	/Users/kale/goroots/go1.8/src/go/types/api.go:349 +0x180
main.(*reducer).reduceLoop(0xc4200ec000, 0x0)
	/Users/kale/go/src/github.com/mvdan/goreduce/reduce.go:248 +0x165
main.reduce(0x7fff5fbff81e, 0x1, 0x7fff5fbff819, 0x4, 0x7fff5fbff800, 0x12, 0x13fd860, 0xc420088010, 0xc4200740b0, 0x0, ...)
	/Users/kale/go/src/github.com/mvdan/goreduce/reduce.go:170 +0x1434
main.main()
	/Users/kale/go/src/github.com/mvdan/goreduce/main.go:48 +0x113

See #25.

Given this testcase:

https://gist.github.com/pwaller/a99e3836293e23677ad08052263b293a

If you run goreduce -match=StructOf ., goreduce deletes the x decl and exits.

The resulting file when run does not output the string StructOf anywhere, contrary to my expectation.

For simplicity, the tool assumes . is the package to use right now. Once tests are in place, we should investigate whether supporting arbitrary import paths makes sense.

Ideally, we would modify the program in memory and run it without having to modify any files on disk nor linking a binary. As far as I can tell, this is impossible since we only have go/parser and go/types, but not an actual compiler.

The closest thing is the ssa interpreter: https://godoc.org/golang.org/x/tools/go/ssa/interp

Unfortunately, that's incomplete by design. Discarding it for now.

Since we have to link a program, we're going with a test file in the very same package. Another option would be multiple main programs in temporary directories, all importing the current package.

Advantages of a test:

• In the same package, thus will work with unexported funcs
• Will work on main packages, which are not importable
• Built-in extra features via test, like cpu/mem profiles and cover reports

Advantages of multiple, separate main programs:

• Concurrent steps are possible
• Slightly faster to run go build and ./foo than go test -run ...? (would have to verify)

We can delete lots of code by simply seeing what code wasn't run to reproduce the issue. For example, produce a coverage file and parse it with https://godoc.org/golang.org/x/tools/cover.

This will likely be useful at the start, perhaps even after every change.

We use go build right now. We should test if using the compiler and linker directly noticeably speeds up the compiler roundtrip.

In the README, we show the result:

func Crasher() {
        a := []int{1, 2, 3}
        println(a[10])
}

We actually produce:

func Crasher() {
        a := []int{1, 2, 3}

        println(a[10])
}

Figure out a way to remove stuff from the AST without introducing these extra empty lines.

If we're after a compiler or linker crash, we don't care about the resulting binary or how to run it. Thus the func name or entry point is not at all useful.

We can't just remove it now because we depend on it to find what ast.File to walk. We should instead just walk the ast.Package.

Split off #15.

If we import package foo and we remove a node containing the only use of that imported package, like foo.Bar, we will remove the import.

This is not a safe assumption - for example, perhaps foo's init() is what we're after. We should instead rewrite the import into a blank import (import _ "foo").

Perhaps it's worth using go/types to check whether the imported package has an init() at all. If it doesn't, is it safe to skip this step?

In any case, removing imports won't happen often and the tool is more useful when it's safe (useful) than when it's fast.

I have a directory full of go that builds fine with regular go:

$ go build

but fails to build with goreduce:

$ goreduce -match=xxxxnomatchxxx .
error does not match:
cmdexe.go:8:2: no required module provides package github.com/gobwas/glob; to add it:
	go get github.com/gobwas/glob

Now, uh, do I use goreduce to find the minimal source that causes the goreduce panic? :-)

panic: could not remove name declaration

goroutine 1 [running]:
main.(*reducer).removeDecl(0xc00012c7e0, 0xc0000681a0, 0xc001121500)
	/Users/dkegel/go/pkg/mod/mvdan.cc/[email protected]/rules.go:509 +0x645
main.(*reducer).afterDelete(0xc00012c7e0, 0xc0011215e8, 0x1, 0x1)
	/Users/dkegel/go/pkg/mod/mvdan.cc/[email protected]/rules.go:755 +0x2d0
main.(*reducer).removeStmt(0xc00012c7e0, 0xc00007f058)
	/Users/dkegel/go/pkg/mod/mvdan.cc/[email protected]/rules.go:598 +0x2b7
main.(*reducer).reduceNode(0xc00012c7e0, 0x1272320, 0xc00007f058, 0xc000197301)
	/Users/dkegel/go/pkg/mod/mvdan.cc/[email protected]/rules.go:78 +0xc9c
main.(*walker).walkSingle(0xc00012c8d8, 0x1272320, 0xc00007f058)
	/Users/dkegel/go/pkg/mod/mvdan.cc/[email protected]/walk.go:60 +0x5b
main.(*walker).walk(0xc00012c8d8, 0x128c200, 0xc00007f830, 0xc0005b9a40)
	/Users/dkegel/go/pkg/mod/mvdan.cc/[email protected]/walk.go:27 +0xaa
main.(*reducer).reduceLoop(0xc00012c7e0, 0x0)
	/Users/dkegel/go/pkg/mod/mvdan.cc/[email protected]/reduce.go:254 +0x185
main.reduce(0x7ffeefbffb9e, 0x1, 0x7ffeefbffb28, 0xf, 0x13228b0, 0xc000010020, 0x7ffeefbffb3d, 0x60, 0x0, 0x0)
	/Users/dkegel/go/pkg/mod/mvdan.cc/[email protected]/reduce.go:146 +0xa28
main.main()
	/Users/dkegel/go/pkg/mod/mvdan.cc/[email protected]/main.go:58 +0x135

There's another thing I don't understand (but maybe this is just a documentation issue).

Take this (it crashes the compiler on tip, it's already reported):

package p

func f1() {
	f2()
}

func f2() {
	if false {
		_ = func() {}
	}
}

I ran goreduce -v -match="cannot inline" . f2 and -v says: crash-goreduce.go:4: ExprStmt removed, which is true: it removed the call at line 4:

package p

func f1() {
}

func f2() {
	if false {
		_ = func() {}
	}
}

I see two problems:

• why did it touch f1 at all? I run it with f2 as argument and docs says "Reduce a function" so I assumed it wouldn't touch f1 (especially so if you consider that f1 is not called by f2).
• the new snippet does not crash the compiler (the f2() call in f1 is needed to reproduce the crash) but goreduce seems convinced to have successfully reduced the code.