known_bits_test.go

     1  // Copyright 2026 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  package ssa
     6  
     7  import (
     8  	"fmt"
     9  	"iter"
    10  	"math/bits"
    11  	"testing"
    12  )
    13  
    14  // allPossibleValuesRejection has identical behavior to allPossibleValues
    15  // but it is implemented with an obviously correct rejection based algorithm.
    16  // We use it to test that allPossibleValues.
    17  func allPossibleValuesRejection(value, known, max int64) func(yield func(v int64) bool) {
    18  	return func(yield func(v int64) bool) {
    19  		for i := int64(0); i <= max; {
    20  			if i&known == value {
    21  				if !yield(i) {
    22  					return
    23  				}
    24  			}
    25  
    26  			next, overflow := bits.Add64(uint64(i), 1, 0)
    27  			if overflow != 0 {
    28  				// exit condition in case the 64th bit is unknown.
    29  				break
    30  			}
    31  			i = int64(next)
    32  		}
    33  	}
    34  }
    35  
    36  func TestAllPossibleValues(t *testing.T) {
    37  	// We can't test too much since it scales exponentially with the number of unknown bits.
    38  	const tryMask = int64(0b0111_1111)
    39  	for i := int64(0); uint64(i) <= uint64(tryMask); i++ {
    40  		unknown := ^i
    41  		known := i | ^tryMask
    42  
    43  		for value := range allPossibleValuesRejection(0, unknown, tryMask) { // don't use allPossibleValues since it's what we are about to test.
    44  			t.Run(fmt.Sprintf("%v", knownBitsEntry{known: known, value: value}), func(t *testing.T) {
    45  				truth, truthStop := iter.Pull(allPossibleValuesRejection(value, known, tryMask))
    46  				defer truthStop()
    47  				dut, dutStop := iter.Pull(allPossibleValues(value, known))
    48  				defer dutStop()
    49  				for i := int64(0); ; i++ {
    50  					want, wantOk := truth()
    51  					got, gotOk := dut()
    52  					if wantOk != gotOk {
    53  						t.Fatalf("unexpected ok at iteration %d: got %v, want %v", i, gotOk, wantOk)
    54  					}
    55  					if !gotOk {
    56  						break
    57  					}
    58  
    59  					if got != want {
    60  						t.Errorf("unexpected value at iteration %d: got %b, want %b", i, uint64(got), uint64(want))
    61  					}
    62  				}
    63  			})
    64  		}
    65  	}
    66  }
    67
View as plain text