forked from golang/tools
/
main.go
733 lines (663 loc) · 23.9 KB
/
main.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
// Copyright 2023 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
// Bisect finds changes responsible for causing a failure.
// A typical use is to identify the source locations in a program
// that are miscompiled by a given compiler optimization.
//
// Usage:
//
// bisect [flags] [var=value...] command [arguments...]
//
// Bisect operates on a target command line – the target – that can be
// run with various changes individually enabled or disabled. With none
// of the changes enabled, the target is known to succeed (exit with exit
// code zero). With all the changes enabled, the target is known to fail
// (exit any other way). Bisect repeats the target with different sets of
// changes enabled, using binary search to find (non-overlapping) minimal
// change sets that provoke the failure.
//
// The target must cooperate with bisect by accepting a change pattern
// and then enabling and reporting the changes that match that pattern.
// The change pattern is passed to the target by substituting it anywhere
// the string PATTERN appears in the environment values or the command
// arguments. For each change that matches the pattern, the target must
// enable that change and also print one or more “match lines”
// (to standard output or standard error) describing the change.
// The [github.com/goki/go-tools/internal/bisect] package provides functions to help
// targets implement this protocol. We plan to publish that package
// in a non-internal location after finalizing its API.
//
// Bisect starts by running the target with no changes enabled and then
// with all changes enabled. It expects the former to succeed and the latter to fail,
// and then it will search for the minimal set of changes that must be enabled
// to provoke the failure. If the situation is reversed – the target fails with no
// changes enabled and succeeds with all changes enabled – then bisect
// automatically runs in reverse as well, searching for the minimal set of changes
// that must be disabled to provoke the failure.
//
// Bisect prints tracing logs to standard error and the minimal change sets
// to standard output.
//
// # Command Line Flags
//
// Bisect supports the following command-line flags:
//
// -max=M
//
// Stop after finding M minimal change sets. The default is no maximum, meaning to run until
// all changes that provoke a failure have been identified.
//
// -maxset=S
//
// Disallow change sets larger than S elements. The default is no maximum.
//
// -timeout=D
//
// If the target runs for longer than duration D, stop the target and interpret that as a failure.
// The default is no timeout.
//
// -count=N
//
// Run each trial N times (default 2), checking for consistency.
//
// -v
//
// Print verbose output, showing each run and its match lines.
//
// In addition to these general flags,
// bisect supports a few “shortcut” flags that make it more convenient
// to use with specific targets.
//
// -compile=<rewrite>
//
// This flag is equivalent to adding an environment variable
// “GOCOMPILEDEBUG=<rewrite>hash=PATTERN”,
// which, as discussed in more detail in the example below,
// allows bisect to identify the specific source locations where the
// compiler rewrite causes the target to fail.
//
// -godebug=<name>=<value>
//
// This flag is equivalent to adding an environment variable
// “GODEBUG=<name>=<value>#PATTERN”,
// which allows bisect to identify the specific call stacks where
// the changed [GODEBUG setting] value causes the target to fail.
//
// # Example
//
// The Go compiler provides support for enabling or disabling certain rewrites
// and optimizations to allow bisect to identify specific source locations where
// the rewrite causes the program to fail. For example, to bisect a failure caused
// by the new loop variable semantics:
//
// bisect go test -gcflags=all=-d=loopvarhash=PATTERN
//
// The -gcflags=all= instructs the go command to pass the -d=... to the Go compiler
// when compiling all packages. Bisect varies PATTERN to determine the minimal set of changes
// needed to reproduce the failure.
//
// The go command also checks the GOCOMPILEDEBUG environment variable for flags
// to pass to the compiler, so the above command is equivalent to:
//
// bisect GOCOMPILEDEBUG=loopvarhash=PATTERN go test
//
// Finally, as mentioned earlier, the -compile flag allows shortening this command further:
//
// bisect -compile=loopvar go test
//
// # Defeating Build Caches
//
// Build systems cache build results, to avoid repeating the same compilations
// over and over. When using a cached build result, the go command (correctly)
// reprints the cached standard output and standard error associated with that
// command invocation. (This makes commands like 'go build -gcflags=-S' for
// printing an assembly listing work reliably.)
//
// Unfortunately, most build systems, including Bazel, are not as careful
// as the go command about reprinting compiler output. If the compiler is
// what prints match lines, a build system that suppresses compiler
// output when using cached compiler results will confuse bisect.
// To defeat such build caches, bisect replaces the literal text “RANDOM”
// in environment values and command arguments with a random 64-bit value
// during each invocation. The Go compiler conveniently accepts a
// -d=ignore=... debug flag that ignores its argument, so to run the
// previous example using Bazel, the invocation is:
//
// bazel test --define=gc_goopts=-d=loopvarhash=PATTERN,unused=RANDOM //path/to:test
//
// [GODEBUG setting]: https://tip.golang.org/doc/godebug
package main
import (
"context"
"flag"
"fmt"
"io"
"log"
"math/bits"
"math/rand"
"os"
"os/exec"
"sort"
"strconv"
"strings"
"time"
"github.com/goki/go-tools/internal/bisect"
)
// Preserve import of bisect, to allow [bisect.Match] in the doc comment.
var _ bisect.Matcher
func usage() {
fmt.Fprintf(os.Stderr, "usage: bisect [flags] [var=value...] command [arguments...]\n")
flag.PrintDefaults()
os.Exit(2)
}
func main() {
log.SetFlags(0)
log.SetPrefix("bisect: ")
var b Bisect
b.Stdout = os.Stdout
b.Stderr = os.Stderr
flag.IntVar(&b.Max, "max", 0, "stop after finding `m` failing change sets")
flag.IntVar(&b.MaxSet, "maxset", 0, "do not search for change sets larger than `s` elements")
flag.DurationVar(&b.Timeout, "timeout", 0, "stop target and consider failed after duration `d`")
flag.IntVar(&b.Count, "count", 2, "run target `n` times for each trial")
flag.BoolVar(&b.Verbose, "v", false, "enable verbose output")
env := ""
envFlag := ""
flag.Func("compile", "bisect source locations affected by Go compiler `rewrite` (fma, loopvar, ...)", func(value string) error {
if envFlag != "" {
return fmt.Errorf("cannot use -%s and -compile", envFlag)
}
envFlag = "compile"
env = "GOCOMPILEDEBUG=" + value + "hash=PATTERN"
return nil
})
flag.Func("godebug", "bisect call stacks affected by GODEBUG setting `name=value`", func(value string) error {
if envFlag != "" {
return fmt.Errorf("cannot use -%s and -godebug", envFlag)
}
envFlag = "godebug"
env = "GODEBUG=" + value + "#PATTERN"
return nil
})
flag.Usage = usage
flag.Parse()
args := flag.Args()
// Split command line into env settings, command name, args.
i := 0
for i < len(args) && strings.Contains(args[i], "=") {
i++
}
if i == len(args) {
usage()
}
b.Env, b.Cmd, b.Args = args[:i], args[i], args[i+1:]
if env != "" {
b.Env = append([]string{env}, b.Env...)
}
// Check that PATTERN is available for us to vary.
found := false
for _, e := range b.Env {
if _, v, _ := strings.Cut(e, "="); strings.Contains(v, "PATTERN") {
found = true
}
}
for _, a := range b.Args {
if strings.Contains(a, "PATTERN") {
found = true
}
}
if !found {
log.Fatalf("no PATTERN in target environment or args")
}
if !b.Search() {
os.Exit(1)
}
}
// A Bisect holds the state for a bisect invocation.
type Bisect struct {
// Env is the additional environment variables for the command.
// PATTERN and RANDOM are substituted in the values, but not the names.
Env []string
// Cmd is the command (program name) to run.
// PATTERN and RANDOM are not substituted.
Cmd string
// Args is the command arguments.
// PATTERN and RANDOM are substituted anywhere they appear.
Args []string
// Command-line flags controlling bisect behavior.
Max int // maximum number of sets to report (0 = unlimited)
MaxSet int // maximum number of elements in a set (0 = unlimited)
Timeout time.Duration // kill target and assume failed after this duration (0 = unlimited)
Count int // run target this many times for each trial and give up if flaky (min 1 assumed; default 2 on command line set in main)
Verbose bool // print long output about each trial (only useful for debugging bisect itself)
// State for running bisect, replaced during testing.
// Failing change sets are printed to Stdout; all other output goes to Stderr.
Stdout io.Writer // where to write standard output (usually os.Stdout)
Stderr io.Writer // where to write standard error (usually os.Stderr)
TestRun func(env []string, cmd string, args []string) (out []byte, err error) // if non-nil, used instead of exec.Command
// State maintained by Search.
// By default, Search looks for a minimal set of changes that cause a failure when enabled.
// If Disable is true, the search is inverted and seeks a minimal set of changes that
// cause a failure when disabled. In this case, the search proceeds as normal except that
// each pattern starts with a !.
Disable bool
// SkipDigits is the number of hex digits to use in skip messages.
// If the set of available changes is the same in each run, as it should be,
// then this doesn't matter: we'll only exclude suffixes that uniquely identify
// a given change. But for some programs, especially bisecting runtime
// behaviors, sometimes enabling one change unlocks questions about other
// changes. Strictly speaking this is a misuse of bisect, but just to make
// bisect more robust, we use the y and n runs to create an estimate of the
// number of bits needed for a unique suffix, and then we round it up to
// a number of hex digits, with one extra digit for good measure, and then
// we always use that many hex digits for skips.
SkipHexDigits int
// Add is a list of suffixes to add to every trial, because they
// contain changes that are necessary for a group we are assembling.
Add []string
// Skip is a list of suffixes that uniquely identify changes to exclude from every trial,
// because they have already been used in failing change sets.
// Suffixes later in the list may only be unique after removing
// the ones earlier in the list.
// Skip applies after Add.
Skip []string
}
// A Result holds the result of a single target trial.
type Result struct {
Success bool // whether the target succeeded (exited with zero status)
Cmd string // full target command line
Out string // full target output (stdout and stderr combined)
Suffix string // the suffix used for collecting MatchIDs, MatchText, and MatchFull
MatchIDs []uint64 // match IDs enabled during this trial
MatchText []string // match reports for the IDs, with match markers removed
MatchFull []string // full match lines for the IDs, with match markers kept
}
// &searchFatal is a special panic value to signal that Search failed.
// This lets us unwind the search recursion on a fatal error
// but have Search return normally.
var searchFatal int
// Search runs a bisect search according to the configuration in b.
// It reports whether any failing change sets were found.
func (b *Bisect) Search() bool {
defer func() {
// Recover from panic(&searchFatal), implicitly returning false from Search.
// Re-panic on any other panic.
if e := recover(); e != nil && e != &searchFatal {
panic(e)
}
}()
// Run with no changes and all changes, to figure out which direction we're searching.
// The goal is to find the minimal set of changes to toggle
// starting with the state where everything works.
// If "no changes" succeeds and "all changes" fails,
// we're looking for a minimal set of changes to enable to provoke the failure
// (broken = runY, b.Negate = false)
// If "no changes" fails and "all changes" succeeds,
// we're looking for a minimal set of changes to disable to provoke the failure
// (broken = runN, b.Negate = true).
b.Logf("checking target with all changes disabled")
runN := b.Run("n")
b.Logf("checking target with all changes enabled")
runY := b.Run("y")
var broken *Result
switch {
case runN.Success && !runY.Success:
b.Logf("target succeeds with no changes, fails with all changes")
b.Logf("searching for minimal set of enabled changes causing failure")
broken = runY
b.Disable = false
case !runN.Success && runY.Success:
b.Logf("target fails with no changes, succeeds with all changes")
b.Logf("searching for minimal set of disabled changes causing failure")
broken = runN
b.Disable = true
case runN.Success && runY.Success:
b.Fatalf("target succeeds with no changes and all changes")
case !runN.Success && !runY.Success:
b.Fatalf("target fails with no changes and all changes")
}
// Compute minimum number of bits needed to distinguish
// all the changes we saw during N and all the changes we saw during Y.
b.SkipHexDigits = skipHexDigits(runN.MatchIDs, runY.MatchIDs)
// Loop finding and printing change sets, until none remain.
found := 0
for {
// Find set.
bad := b.search(broken)
if bad == nil {
if found == 0 {
b.Fatalf("cannot find any failing change sets of size ≤ %d", b.MaxSet)
}
break
}
// Confirm that set really does fail, to avoid false accusations.
// Also asking for user-visible output; earlier runs did not.
b.Logf("confirming failing change set")
b.Add = append(b.Add[:0], bad...)
broken = b.Run("v")
if broken.Success {
b.Logf("confirmation run succeeded unexpectedly")
}
b.Add = b.Add[:0]
// Print confirmed change set.
found++
b.Logf("FOUND failing change set")
desc := "(enabling changes causes failure)"
if b.Disable {
desc = "(disabling changes causes failure)"
}
fmt.Fprintf(b.Stdout, "--- change set #%d %s\n%s\n---\n", found, desc, strings.Join(broken.MatchText, "\n"))
// Stop if we've found enough change sets.
if b.Max > 0 && found >= b.Max {
break
}
// If running bisect target | tee bad.txt, prints to stdout and stderr
// both appear on the terminal, but the ones to stdout go through tee
// and can take a little bit of extra time. Sleep 1 millisecond to give
// tee time to catch up, so that its stdout print does not get interlaced
// with the stderr print from the next b.Log message.
time.Sleep(1 * time.Millisecond)
// Disable the now-known-bad changes and see if any failures remain.
b.Logf("checking for more failures")
b.Skip = append(bad, b.Skip...)
broken = b.Run("")
if broken.Success {
what := "enabled"
if b.Disable {
what = "disabled"
}
b.Logf("target succeeds with all remaining changes %s", what)
break
}
b.Logf("target still fails; searching for more bad changes")
}
return true
}
// Fatalf prints a message to standard error and then panics,
// causing Search to return false.
func (b *Bisect) Fatalf(format string, args ...any) {
s := fmt.Sprintf("bisect: fatal error: "+format, args...)
if !strings.HasSuffix(s, "\n") {
s += "\n"
}
b.Stderr.Write([]byte(s))
panic(&searchFatal)
}
// Logf prints a message to standard error.
func (b *Bisect) Logf(format string, args ...any) {
s := fmt.Sprintf("bisect: "+format, args...)
if !strings.HasSuffix(s, "\n") {
s += "\n"
}
b.Stderr.Write([]byte(s))
}
func skipHexDigits(idY, idN []uint64) int {
var all []uint64
seen := make(map[uint64]bool)
for _, x := range idY {
seen[x] = true
all = append(all, x)
}
for _, x := range idN {
if !seen[x] {
seen[x] = true
all = append(all, x)
}
}
sort.Slice(all, func(i, j int) bool { return bits.Reverse64(all[i]) < bits.Reverse64(all[j]) })
digits := sort.Search(64/4, func(digits int) bool {
mask := uint64(1)<<(4*digits) - 1
for i := 0; i+1 < len(all); i++ {
if all[i]&mask == all[i+1]&mask {
return false
}
}
return true
})
if digits < 64/4 {
digits++
}
return digits
}
// search searches for a single locally minimal change set.
//
// Invariant: r describes the result of r.Suffix + b.Add, which failed.
// (There's an implicit -b.Skip everywhere here. b.Skip does not change.)
// We want to extend r.Suffix to preserve the failure, working toward
// a suffix that identifies a single change.
func (b *Bisect) search(r *Result) []string {
// The caller should be passing in a failure result that we diagnose.
if r.Success {
b.Fatalf("internal error: unexpected success") // mistake by caller
}
// If the failure reported no changes, the target is misbehaving.
if len(r.MatchIDs) == 0 {
b.Fatalf("failure with no reported changes:\n\n$ %s\n%s\n", r.Cmd, r.Out)
}
// If there's one matching change, that's the one we're looking for.
if len(r.MatchIDs) == 1 {
return []string{fmt.Sprintf("x%0*x", b.SkipHexDigits, r.MatchIDs[0]&(1<<(4*b.SkipHexDigits)-1))}
}
// If the suffix we were tracking in the trial is already 64 bits,
// either the target is bad or bisect itself is buggy.
if len(r.Suffix) >= 64 {
b.Fatalf("failed to isolate a single change with very long suffix")
}
// We want to split the current matchIDs by left-extending the suffix with 0 and 1.
// If all the matches have the same next bit, that won't cause a split, which doesn't
// break the algorithm but does waste time. Avoid wasting time by left-extending
// the suffix to the longest suffix shared by all the current match IDs
// before adding 0 or 1.
suffix := commonSuffix(r.MatchIDs)
if !strings.HasSuffix(suffix, r.Suffix) {
b.Fatalf("internal error: invalid common suffix") // bug in commonSuffix
}
// Run 0suffix and 1suffix. If one fails, chase down the failure in that half.
r0 := b.Run("0" + suffix)
if !r0.Success {
return b.search(r0)
}
r1 := b.Run("1" + suffix)
if !r1.Success {
return b.search(r1)
}
// suffix failed, but 0suffix and 1suffix succeeded.
// Assuming the target isn't flaky, this means we need
// at least one change from 0suffix AND at least one from 1suffix.
// We are already tracking N = len(b.Add) other changes and are
// allowed to build sets of size at least 1+N (or we shouldn't be here at all).
// If we aren't allowed to build sets of size 2+N, give up this branch.
if b.MaxSet > 0 && 2+len(b.Add) > b.MaxSet {
return nil
}
// Adding all matches for 1suffix, recurse to narrow down 0suffix.
old := len(b.Add)
b.Add = append(b.Add, "1"+suffix)
r0 = b.Run("0" + suffix)
if r0.Success {
// 0suffix + b.Add + 1suffix = suffix + b.Add is what r describes, and it failed.
b.Fatalf("target fails inconsistently")
}
bad0 := b.search(r0)
if bad0 == nil {
// Search failed due to MaxSet limit.
return nil
}
b.Add = b.Add[:old]
// Adding the specific match we found in 0suffix, recurse to narrow down 1suffix.
b.Add = append(b.Add[:old], bad0...)
r1 = b.Run("1" + suffix)
if r1.Success {
// 1suffix + b.Add + bad0 = bad0 + b.Add + 1suffix is what b.search(r0) reported as a failure.
b.Fatalf("target fails inconsistently")
}
bad1 := b.search(r1)
if bad1 == nil {
// Search failed due to MaxSet limit.
return nil
}
b.Add = b.Add[:old]
// bad0 and bad1 together provoke the failure.
return append(bad0, bad1...)
}
// Run runs a set of trials selecting changes with the given suffix,
// plus the ones in b.Add and not the ones in b.Skip.
// The returned result's MatchIDs, MatchText, and MatchFull
// only list the changes that match suffix.
// When b.Count > 1, Run runs b.Count trials and requires
// that they all succeed or they all fail. If not, it calls b.Fatalf.
func (b *Bisect) Run(suffix string) *Result {
out := b.run(suffix)
for i := 1; i < b.Count; i++ {
r := b.run(suffix)
if r.Success != out.Success {
b.Fatalf("target fails inconsistently")
}
}
return out
}
// run runs a single trial for Run.
func (b *Bisect) run(suffix string) *Result {
random := fmt.Sprint(rand.Uint64())
// Accept suffix == "v" to mean we need user-visible output.
visible := ""
if suffix == "v" {
visible = "v"
suffix = ""
}
// Construct change ID pattern.
var pattern string
if suffix == "y" || suffix == "n" {
pattern = suffix
suffix = ""
} else {
var elem []string
if suffix != "" {
elem = append(elem, "+", suffix)
}
for _, x := range b.Add {
elem = append(elem, "+", x)
}
for _, x := range b.Skip {
elem = append(elem, "-", x)
}
pattern = strings.Join(elem, "")
if pattern == "" {
pattern = "y"
}
}
if b.Disable {
pattern = "!" + pattern
}
pattern = visible + pattern
// Construct substituted env and args.
env := make([]string, len(b.Env))
for i, x := range b.Env {
k, v, _ := strings.Cut(x, "=")
env[i] = k + "=" + replace(v, pattern, random)
}
args := make([]string, len(b.Args))
for i, x := range b.Args {
args[i] = replace(x, pattern, random)
}
// Construct and log command line.
// There is no newline in the log print.
// The line will be completed when the command finishes.
cmdText := strings.Join(append(append(env, b.Cmd), args...), " ")
fmt.Fprintf(b.Stderr, "bisect: run: %s...", cmdText)
// Run command with args and env.
var out []byte
var err error
if b.TestRun != nil {
out, err = b.TestRun(env, b.Cmd, args)
} else {
ctx := context.Background()
if b.Timeout != 0 {
var cancel context.CancelFunc
ctx, cancel = context.WithTimeout(ctx, b.Timeout)
defer cancel()
}
cmd := exec.CommandContext(ctx, b.Cmd, args...)
cmd.Env = append(os.Environ(), env...)
// Set up cmd.Cancel, cmd.WaitDelay on Go 1.20 and later
// TODO(rsc): Inline go120.go's cmdInterrupt once we stop supporting Go 1.19.
cmdInterrupt(cmd)
out, err = cmd.CombinedOutput()
}
// Parse output to construct result.
r := &Result{
Suffix: suffix,
Success: err == nil,
Cmd: cmdText,
Out: string(out),
}
// Calculate bits, mask to identify suffix matches.
var bits, mask uint64
if suffix != "" && suffix != "y" && suffix != "n" && suffix != "v" {
var err error
bits, err = strconv.ParseUint(suffix, 2, 64)
if err != nil {
b.Fatalf("internal error: bad suffix")
}
mask = uint64(1<<len(suffix)) - 1
}
// Process output, collecting match reports for suffix.
have := make(map[uint64]bool)
all := r.Out
for all != "" {
var line string
line, all, _ = strings.Cut(all, "\n")
short, id, ok := bisect.CutMarker(line)
if !ok || (id&mask) != bits {
continue
}
if !have[id] {
have[id] = true
r.MatchIDs = append(r.MatchIDs, id)
}
r.MatchText = append(r.MatchText, short)
r.MatchFull = append(r.MatchFull, line)
}
// Finish log print from above, describing the command's completion.
if err == nil {
fmt.Fprintf(b.Stderr, " ok (%d matches)\n", len(r.MatchIDs))
} else {
fmt.Fprintf(b.Stderr, " FAIL (%d matches)\n", len(r.MatchIDs))
}
if err != nil && len(r.MatchIDs) == 0 {
b.Fatalf("target failed without printing any matches\n%s", r.Out)
}
// In verbose mode, print extra debugging: all the lines with match markers.
if b.Verbose {
b.Logf("matches:\n%s", strings.Join(r.MatchFull, "\n\t"))
}
return r
}
// replace returns x with literal text PATTERN and RANDOM replaced by pattern and random.
func replace(x, pattern, random string) string {
x = strings.ReplaceAll(x, "PATTERN", pattern)
x = strings.ReplaceAll(x, "RANDOM", random)
return x
}
// commonSuffix returns the longest common binary suffix shared by all uint64s in list.
// If list is empty, commonSuffix returns an empty string.
func commonSuffix(list []uint64) string {
if len(list) == 0 {
return ""
}
b := list[0]
n := 64
for _, x := range list {
for x&((1<<n)-1) != b {
n--
b &= (1 << n) - 1
}
}
s := make([]byte, n)
for i := n - 1; i >= 0; i-- {
s[i] = '0' + byte(b&1)
b >>= 1
}
return string(s[:])
}