trie.go

     1  // Code generated by "go test -run=Generate -write=all"; DO NOT EDIT.
     2  // Source: ../../cmd/compile/internal/types2/trie.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 "sort"
    11  
    12  // A trie[V] maps keys to values V, similar to a map.
    13  // A key is a list of integers; two keys collide if one of them is a prefix of the other.
    14  // For instance, [1, 2] and [1, 2, 3] collide, but [1, 2, 3] and [1, 2, 4] do not.
    15  // If all keys have length 1, a trie degenerates into an ordinary map[int]V.
    16  type trie[V any] map[int]any // map value is either trie[V] (non-leaf node), or V (leaf node)
    17  
    18  // insert inserts a value with a key into the trie; key must not be empty.
    19  // If key doesn't collide with any other key in the trie, insert succeeds
    20  // and returns (val, 0). Otherwise, insert fails and returns (alt, n) where
    21  // alt is an unspecified but deterministically chosen value with a colliding
    22  // key and n is the length > 0 of the common key prefix. The trie is not
    23  // changed in this case.
    24  func (tr trie[V]) insert(key []int, val V) (V, int) {
    25  	// A key serves as the path from the trie root to its corresponding value.
    26  	for l, index := range key {
    27  		if v, exists := tr[index]; exists {
    28  			// An entry already exists for this index; check its type to determine collision.
    29  			switch v := v.(type) {
    30  			case trie[V]:
    31  				// Path continues.
    32  				// Must check this case first in case V is any which would act as catch-all.
    33  				tr = v
    34  			case V:
    35  				// Collision: An existing key ends here.
    36  				// This means the existing key is a prefix of (or exactly equal to) key.
    37  				return v, l + 1
    38  			case nil:
    39  				// Handle esoteric case where V is any and val is nil.
    40  				var zero V
    41  				return zero, l + 1
    42  			default:
    43  				panic("trie.insert: invalid entry")
    44  			}
    45  		} else {
    46  			// Path doesn't exist yet, we need to build it.
    47  			if l == len(key)-1 {
    48  				// No prefix collision detected; insert val as a new leaf node.
    49  				tr[index] = val
    50  				return val, 0
    51  			}
    52  			node := make(trie[V])
    53  			tr[index] = node
    54  			tr = node
    55  		}
    56  	}
    57  
    58  	if len(key) == 0 {
    59  		panic("trie.insert: key must not be empty")
    60  	}
    61  
    62  	// Collision: path ends here, but the trie continues.
    63  	// This means key is a prefix of an existing key.
    64  	// Return a value from the subtrie.
    65  	for len(tr) != 0 {
    66  		// see switch above
    67  		switch v := tr.pickValue().(type) {
    68  		case trie[V]:
    69  			tr = v
    70  		case V:
    71  			return v, len(key)
    72  		case nil:
    73  			var zero V
    74  			return zero, len(key)
    75  		default:
    76  			panic("trie.insert: invalid entry")
    77  		}
    78  	}
    79  
    80  	panic("trie.insert: unreachable")
    81  }
    82  
    83  // pickValue deterministically picks a value of the trie and returns it.
    84  // Only called in case of a collision.
    85  // The trie must not be empty.
    86  func (tr trie[V]) pickValue() any {
    87  	var keys []int
    88  	for k := range tr {
    89  		keys = append(keys, k)
    90  	}
    91  	sort.Ints(keys) // guarantee deterministic element pick
    92  	return tr[keys[0]]
    93  }
    94
View as plain text