trie_test.go

     1  // Code generated by "go test -run=Generate -write=all"; DO NOT EDIT.
     2  // Source: ../../cmd/compile/internal/types2/trie_test.go
     3  
     4  // Copyright 2026 The Go Authors. All rights reserved.
     5  // Use of this source code is governed by a BSD-style
     6  // license that can be found in the LICENSE file.
     7  
     8  package types
     9  
    10  import (
    11  	"fmt"
    12  	"testing"
    13  )
    14  
    15  func TestTrie(t *testing.T) {
    16  	strie := make(trie[string])
    17  
    18  	okay := func(index ...int) {
    19  		s := fmt.Sprintf("%x", index)
    20  		if p, n := strie.insert(index, s); n != 0 {
    21  			t.Errorf("%s collided with %s (n = %d)", s, p, n)
    22  		}
    23  	}
    24  
    25  	fail := func(collision string, index ...int) {
    26  		s := fmt.Sprintf("%x", index)
    27  		if p, n := strie.insert(index, s); n == 0 {
    28  			t.Errorf("%s did not collide", s)
    29  		} else if p != collision {
    30  			t.Errorf("%s collided with %s (n == %d), want %s", s, p, n, collision)
    31  		}
    32  	}
    33  
    34  	clear(strie)
    35  	okay(0)
    36  	fail("[0]", 0)
    37  
    38  	clear(strie)
    39  	okay(0)
    40  	fail("[0]", 0, 1, 2, 3, 4, 5)
    41  
    42  	clear(strie)
    43  	okay(1, 2)
    44  	okay(1, 3)
    45  	okay(1, 4, 5)
    46  	okay(1, 4, 2)
    47  	fail("[1 4 2]", 1, 4)
    48  	fail("[1 4 5]", 1, 4, 5)
    49  	okay(1, 4, 3)
    50  	okay(2, 1)
    51  	okay(2, 2)
    52  	fail("[2 2]", 2, 2, 3)
    53  
    54  	clear(strie)
    55  	okay(0, 1, 2, 3, 4, 5)
    56  	okay(0, 1, 2, 3, 4, 6)
    57  	okay(0, 1, 2, 3, 4, 7)
    58  	okay(0, 1, 2, 3, 4, 8, 1)
    59  	okay(0, 1, 2, 3, 4, 4)
    60  	fail("[0 1 2 3 4 4]", 0, 1, 2, 3)
    61  }
    62  
    63  func TestAnyValue(t *testing.T) {
    64  	atrie := make(trie[any]) // allow values of any type
    65  
    66  	val := new(42)
    67  	alt, n := atrie.insert([]int{0}, val)
    68  	if n != 0 {
    69  		t.Errorf("unexpected collision (n = %d)", n)
    70  	}
    71  	if alt != val {
    72  		t.Errorf("unexpected result (alt = %#x, val = %#x)", alt, val)
    73  	}
    74  
    75  	alt, n = atrie.insert([]int{0}, val) // nil is a valid value
    76  	if n == 0 {
    77  		t.Errorf("expected collision")
    78  	}
    79  	if alt != val {
    80  		t.Errorf("unexpected result (alt = %#x, val = %#x)", alt, val)
    81  	}
    82  }
    83
View as plain text