proposal: debug/bisect: publish x/tools/internal/bisect

[rsc]

golang.org/x/tools/cmd/bisect is incredibly useful for binary-searching over potential bug locations when a compiler or library change causes a problem. There is a small package that handles the protocol of speaking to the bisect tool, and we have two copies of it: std's internal/bisect (for the compiler and runtime) and also golang.org/x/tools/internal/bisect (for x/tools/cmd/bisect).

We have been using bisect successfully long enough that I feel pretty confident in the API. I propose we publish the package as the standard library package debug/bisect. This will let the compiler and runtime both use it, it will let us drop down to having just one copy of the code, and it will also make the logic available to other programs that want to be bisect-debuggable. In particular, packages beyond the standard library could use it to provide bisectable implementation changes when they make compatible-but-possibly-breaking changes.

The full API is:

package bisect

func AppendMarker(dst []byte, id uint64) []byte
func CutMarker(line string) (short string, id uint64, ok bool)
func Hash(data ...any) uint64
func Marker(id uint64) string
func PrintMarker(w Writer, h uint64) error

type Matcher struct { ... }
func New(pattern string) (*Matcher, error)
func (*Matcher) FileLine(w Writer, file string, line int) bool
func (*Matcher) MarkerOnly() bool
func (*Matcher) ShouldEnable(id uint64) bool
func (*Matcher) ShouldPrint(id uint64) bool
func (*Matcher) Stack(w io.Writer) bool

For doc comments, see https://pkg.go.dev/golang.org/x/tools/internal/bisect.
For more background, see https://research.swtch.com/bisect.

[aclements]

Because of its very low-level uses by the runtime, package bisect has no imports, so it defines its own copy of io.Writer.

Alternatively, we keep most of the implementation in internal/bisect, and the public package is just a thin wrapper around this. In general, we're having to move more toward this model anyway for things that are used from runtime.

[rsc]

Thanks for pointing that out. Changed the API for the public package to use io.

[rsc]

This proposal has been added to the active column of the proposals project
and will now be reviewed at the weekly proposal review meetings.
— rsc for the proposal review group

[hherman1]

I’m having a hard time understanding what this does, or how the api methods are meant to be used. Comments on the api methods would be helpful for me.

[rsc]

Apologies for not linking to it at the start, but the docs for these functions are at https://pkg.go.dev/golang.org/x/tools/internal/bisect.

[rsc]

I added to the top comment:

For doc comments, see https://pkg.go.dev/golang.org/x/tools/internal/bisect.
For more background, see https://research.swtch.com/bisect.

[hherman1]

Thanks, I loved the blog post! Looking for ways to use this at work…

[rsc]

Have all remaining concerns about this proposal been addressed?

The proposal details are in #67140 (comment).

[rsc]

I need to write the full package docs and post them here, along with some examples. Some things are still not clear.

[aclements]

The Matcher API makes sense to me, but I find the Marker part of the API pretty confusing. Partly this is a documentation issue (the Marker doc comment as written assumes a lot of context). Partly though I think this requires the user of this API to hook up the parts just right, and things can go wrong if they don't. Specifically:

1. If you call ShouldReport, it seems like you also always need to call Marker to get the marker string and always need to print it, but these are three steps the user has to wire together right now.
2. It seems like you always need to do both ShouldEnable and ShouldReport. Is there ever a situation where you need to to one without the other?

To me, this suggests that there could be a single method of Matcher that reports that we're making a decision based on this marker and returns what the decision was. That would reduce this example:

for each change {
	h := bisect.Hash(file, line)
	if m.ShouldEnable(h) {
		enableChange()
	}
	if m.ShouldReport(h) {
		log.Printf("%v %s:%d", bisect.Marker(h), file, line)
	}
}

to something like

for each change {
	h := bisect.Hash(file, line)
	if m.Test(h, "%s:%d", file, line) {
		enableChange()
	}
}

I'm not sure how much flexibility is needed in the reporting. The existence of AppendMarker suggests that there were use cases where you wanted to do something other than print it right away. Could this be abstracted out into some setting on Matcher such as an io.Writer or a callback?

Minor API comments

Some of these might be obviated if we switch to an API like I suggest above, but I wanted to get them on the record in case they remain relevant.

• You mentioned that Marker is a separate function because it needs to allocate, but it seems like it could just be a type wrapping the uint64 with a String() method so it only allocates at the point of formatting. (It's perhaps unfortunate that with both 1) don't have a common interface for appending your string representing to a []byte and 2) can't automatically optimize the away string allocation by String() )

• uint64 IDs appear in several places in the API, but the type doesn't tie them together, and they're called both "IDs" and "markers". Consider introducing a named type for these that's just a uint64, but makes it clear what you can do with one of these. It might make sense to replace the current Marker function with a String method on this type.