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