index_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  //go:build amd64 || arm64 || loong64 || s390x || ppc64le || ppc64
     6  
     7  package bytealg_test
     8  
     9  import (
    10  	"fmt"
    11  	"internal/bytealg"
    12  	"math/rand"
    13  	"strings"
    14  	"testing"
    15  )
    16  
    17  // indexRef is a reference implementation of Index, used as the
    18  // correctness oracle for the assembly implementations.
    19  func indexRef(hay, needle string) int {
    20  	for i := 0; i+len(needle) <= len(hay); i++ {
    21  		if hay[i:i+len(needle)] == needle {
    22  			return i
    23  		}
    24  	}
    25  	return -1
    26  }
    27  
    28  // check compares both Index and IndexString against the reference
    29  // implementation for one input pair.
    30  func check(t *testing.T, hay, needle string) {
    31  	t.Helper()
    32  	want := indexRef(hay, needle)
    33  	if got := bytealg.IndexString(hay, needle); got != want {
    34  		t.Errorf("IndexString(%q, %q) = %d, want %d", hay, needle, got, want)
    35  	}
    36  	if got := bytealg.Index([]byte(hay), []byte(needle)); got != want {
    37  		t.Errorf("Index(%q, %q) = %d, want %d", hay, needle, got, want)
    38  	}
    39  }
    40  
    41  // TestIndexExhaustive sweeps all needle lengths and all match positions
    42  // over a range of haystack lengths chosen to cover both the scalar and
    43  // SIMD paths and the boundary between them, including haystack lengths
    44  // that are not a multiple of the vector width and matches inside the
    45  // final (overlapping) block.
    46  func TestIndexExhaustive(t *testing.T) {
    47  	if bytealg.MaxLen < 2 {
    48  		t.Skip("Index not enabled")
    49  	}
    50  	maxNeedle := bytealg.MaxLen
    51  	if maxNeedle > 64 {
    52  		maxNeedle = 64 // keep the sweep bounded
    53  	}
    54  	// Distinct-ish byte content so partial overlaps of the needle
    55  	// never accidentally match: position i holds byte 'A'+i%23.
    56  	content := func(n int) string {
    57  		s := make([]byte, n)
    58  		for i := range s {
    59  			s[i] = byte('A' + i%23)
    60  		}
    61  		return string(s)
    62  	}
    63  	for n := 2; n <= maxNeedle; n++ {
    64  		for _, extra := range []int{0, 1, 7, 13, 14, 15, 16, 17, 30, 31, 32, 33, 47, 48, 63, 64, 100} {
    65  			h := n + extra
    66  			hay := content(h)
    67  			// A needle taken from every position must be found there:
    68  			// earlier positions cannot match because every window of
    69  			// content is unique.
    70  			for pos := 0; pos+n <= h; pos++ {
    71  				check(t, hay, hay[pos:pos+n])
    72  			}
    73  			// Absent needles: right length, wrong content.
    74  			check(t, hay, strings.Repeat("z", n))
    75  			// Wrong middle byte: anchors (first/last byte) match at
    76  			// one position but the needle differs inside.
    77  			corrupt := []byte(hay[h-n : h])
    78  			corrupt[n/2] ^= 0x80
    79  			check(t, hay, string(corrupt))
    80  		}
    81  	}
    82  }
    83  
    84  // TestIndexPathological exercises inputs that generate many anchor
    85  // false positives per 16-byte block, stressing the candidate
    86  // verification and mask-clearing paths.
    87  func TestIndexPathological(t *testing.T) {
    88  	if bytealg.MaxLen < 2 {
    89  		t.Skip("Index not enabled")
    90  	}
    91  	tests := []struct {
    92  		name string
    93  		a, b string
    94  	}{
    95  		// Both anchors match at every even offset; middles never match.
    96  		{"anchor false positives", strings.Repeat("ab", 100), "a" + strings.Repeat("c", 10) + "b"},
    97  		// Every byte matches both anchors; verification fails everywhere.
    98  		{"all candidates no match", strings.Repeat("a", 200), "a" + strings.Repeat("a", 10) + "b"},
    99  		{"all candidates match at 0", strings.Repeat("a", 200), strings.Repeat("a", 12)},
   100  		{"all candidates match late", strings.Repeat("a", 100) + "b" + strings.Repeat("a", 20), strings.Repeat("a", 8) + "b"},
   101  		// Overlapping self-similar needle.
   102  		{"overlapping periodic", strings.Repeat("abcab", 40), "abcabcab"},
   103  		// Needle lengths 4..8 with the needle's own first/last byte
   104  		// recurring throughout the haystack: forces many anchor
   105  		// collisions per 16-byte block for every length in the {4-8}
   106  		// class, exercising both the post-refine single-check verify
   107  		// (multiple candidates) and its max(n-6,0) offset boundary at
   108  		// each length, and the lone-candidate two-chunk verify.
   109  		{"anchor collisions n=4 no match", strings.Repeat("a", 200), "aqqa"},
   110  		{"anchor collisions n=5 no match", strings.Repeat("a", 200), "aqqqa"},
   111  		{"anchor collisions n=6 no match", strings.Repeat("a", 200), "aqqqqa"},
   112  		{"anchor collisions n=7 no match", strings.Repeat("a", 200), "aqqqqqa"},
   113  		{"anchor collisions n=8 no match", strings.Repeat("a", 200), "aqqqqqqa"},
   114  		{"anchor collisions n=4 match late", strings.Repeat("a", 150) + "aqqa" + strings.Repeat("a", 46), "aqqa"},
   115  		{"anchor collisions n=5 match late", strings.Repeat("a", 150) + "aqqqa" + strings.Repeat("a", 45), "aqqqa"},
   116  		{"anchor collisions n=6 match late", strings.Repeat("a", 150) + "aqqqqa" + strings.Repeat("a", 44), "aqqqqa"},
   117  		{"anchor collisions n=7 match late", strings.Repeat("a", 150) + "aqqqqqa" + strings.Repeat("a", 43), "aqqqqqa"},
   118  		{"anchor collisions n=8 match late", strings.Repeat("a", 150) + "aqqqqqqa" + strings.Repeat("a", 42), "aqqqqqqa"},
   119  		// Match only at the very last valid offset.
   120  		{"match at end", strings.Repeat("x", 50) + "needle", "needle"},
   121  		{"match at start", "needle" + strings.Repeat("x", 50), "needle"},
   122  		// Needle almost at the end, misaligned with the final block.
   123  		{"near end miss", strings.Repeat("x", 53) + "needl!", "needle"},
   124  		// Second anchor differs only at the last byte of the haystack.
   125  		{"last byte differs", strings.Repeat("x", 60) + "ne", "nz"},
   126  		{"last byte matches", strings.Repeat("x", 60) + "ne", "ne"},
   127  	}
   128  	// Needles whose first two and last two bytes all match at every
   129  	// offset, so candidates pass both the anchor and refine checks and
   130  	// only full verification can reject them: the one differing byte
   131  	// sits at each end of the region the verify chunks must cover.
   132  	for n := 5; n <= 32; n++ {
   133  		for _, mid := range []int{2, n / 2, n - 3} {
   134  			needle := []byte(strings.Repeat("a", n))
   135  			needle[mid] = 'b'
   136  			tests = append(tests,
   137  				struct{ name, a, b string }{
   138  					fmt.Sprintf("refine passes n=%d b[%d] no match", n, mid),
   139  					strings.Repeat("a", 200), string(needle),
   140  				},
   141  				struct{ name, a, b string }{
   142  					fmt.Sprintf("refine passes n=%d b[%d] match late", n, mid),
   143  					strings.Repeat("a", 150) + string(needle) + strings.Repeat("a", 30), string(needle),
   144  				})
   145  		}
   146  	}
   147  	for _, tt := range tests {
   148  		t.Run(tt.name, func(t *testing.T) {
   149  			if len(tt.b) > bytealg.MaxLen {
   150  				t.Skip("needle longer than MaxLen")
   151  			}
   152  			check(t, tt.a, tt.b)
   153  		})
   154  	}
   155  }
   156  
   157  // TestIndexRandom cross-checks the assembly implementations against the
   158  // reference on random inputs over a small alphabet (to generate plenty
   159  // of partial matches and anchor collisions).
   160  func TestIndexRandom(t *testing.T) {
   161  	if bytealg.MaxLen < 2 {
   162  		t.Skip("Index not enabled")
   163  	}
   164  	r := rand.New(rand.NewSource(1))
   165  	for _, alphabet := range []string{"a", "ab", "abc", "abcdefgh"} {
   166  		for i := 0; i < 5000; i++ {
   167  			n := 2 + r.Intn(bytealg.MaxLen-1)
   168  			h := n + r.Intn(300)
   169  			hay := make([]byte, h)
   170  			for j := range hay {
   171  				hay[j] = alphabet[r.Intn(len(alphabet))]
   172  			}
   173  			var needle string
   174  			if r.Intn(2) == 0 && h > n {
   175  				// Slice of the haystack: guaranteed to occur.
   176  				pos := r.Intn(h - n)
   177  				needle = string(hay[pos : pos+n])
   178  			} else {
   179  				nb := make([]byte, n)
   180  				for j := range nb {
   181  					nb[j] = alphabet[r.Intn(len(alphabet))]
   182  				}
   183  				needle = string(nb)
   184  			}
   185  			check(t, string(hay), needle)
   186  		}
   187  	}
   188  }
   189  
   190  // BenchmarkIndexString measures IndexString directly (bypassing the
   191  // strings/bytes dispatch layers) across needle lengths and haystack
   192  // sizes, so implementation thresholds can be recalibrated on future
   193  // hardware.
   194  //
   195  // "text" searches random lowercase text for an uppercase needle placed
   196  // at the very end: a full scan with a realistic (low) rate of anchor
   197  // false positives. "hard" searches an alternating haystack for an
   198  // absent needle whose first and last bytes match at every other
   199  // offset: maximum verification pressure.
   200  func BenchmarkIndexString(b *testing.B) {
   201  	r := rand.New(rand.NewSource(1))
   202  	base := make([]byte, 4096)
   203  	for i := range base {
   204  		base[i] = 'a' + byte(r.Intn(26))
   205  	}
   206  	sizes := []int{16, 24, 32, 64, 512, 4096}
   207  	for _, n := range []int{2, 4, 8, 16, 32} {
   208  		if n > bytealg.MaxLen {
   209  			continue
   210  		}
   211  		for _, h := range sizes {
   212  			if h < n {
   213  				continue
   214  			}
   215  			hay := make([]byte, h)
   216  			copy(hay, base)
   217  			needle := make([]byte, n)
   218  			for i := range needle {
   219  				needle[i] = 'A' + byte(r.Intn(26))
   220  			}
   221  			copy(hay[h-n:], needle)
   222  			s, sep := string(hay), string(needle)
   223  			b.Run(fmt.Sprintf("text/n=%d/h=%d", n, h), func(b *testing.B) {
   224  				b.SetBytes(int64(h))
   225  				for i := 0; i < b.N; i++ {
   226  					if bytealg.IndexString(s, sep) != h-n {
   227  						b.Fatal("wrong result")
   228  					}
   229  				}
   230  			})
   231  		}
   232  	}
   233  	for _, n := range []int{4, 8, 16, 32} {
   234  		if n > bytealg.MaxLen {
   235  			continue
   236  		}
   237  		for _, h := range sizes {
   238  			if h < n {
   239  				continue
   240  			}
   241  			s := strings.Repeat("ab", h/2)
   242  			sep := "a" + strings.Repeat("c", n-2) + "b"
   243  			b.Run(fmt.Sprintf("hard/n=%d/h=%d", n, h), func(b *testing.B) {
   244  				b.SetBytes(int64(h))
   245  				for i := 0; i < b.N; i++ {
   246  					if bytealg.IndexString(s, sep) != -1 {
   247  						b.Fatal("wrong result")
   248  					}
   249  				}
   250  			})
   251  		}
   252  	}
   253  }
   254
View as plain text