lattice.go (4023B)
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 dfa 6 7 import ( 8 "fmt" 9 "maps" 10 "slices" 11 ) 12 13 // A Semilattice describes a bounded semilattice over Elem. 14 // That is, a partial order over values of type Elem, with a binary 15 // Merge operator and an identity element. 16 // 17 // This is typically implemented by a stateless type, and acts as a factory for 18 // lattice elements. 19 type Semilattice[Elem any] interface { 20 // Ident returns the identity element of this lattice, that is the unit of 21 // the Merge operation. 22 Ident() Elem 23 24 // Equals returns whether a and b are the same element. 25 Equals(a, b Elem) bool 26 27 // Merge combines two lattice values, such as the two possible values of a 28 // variable at the end of an if/else statement. 29 // 30 // Merge must satisfy the following identities, where we use ∧ for Merge, = 31 // for Equals, and 𝟏 for Ident: 32 // 33 // - Associativity: x ∧ (y ∧ z) = (x ∧ y) ∧ z 34 // - Commutativity: x ∧ y = y ∧ x 35 // - Idempotency: x ∧ x = x 36 // - Identity: x ∧ 𝟏 = x 37 Merge(a, b Elem) Elem 38 } 39 40 // A MapLattice implements [Semilattice][map[Key]Elem]. The values in the map 41 // are themselves defined by [Semilattice] L. 42 // 43 // Any elements missing from the map are implicitly L's identity element, and 44 // L's identity element never appears as a value in the map. 45 // 46 // For densely numbered keys, consider using [DenseMapLattice] instead. 47 type MapLattice[Key comparable, Elem any, L Semilattice[Elem]] struct { 48 l L 49 } 50 51 func (m MapLattice[Key, Elem, L]) Ident() map[Key]Elem { 52 return nil 53 } 54 55 func (m MapLattice[Key, Elem, L]) Equals(a, b map[Key]Elem) bool { 56 return maps.EqualFunc(a, b, m.l.Equals) 57 } 58 59 func (m MapLattice[Key, Elem, L]) Merge(a, b map[Key]Elem) map[Key]Elem { 60 if len(a) == 0 { 61 return b 62 } else if len(b) == 0 { 63 return a 64 } 65 66 // We need to consider the union of keys in a and b. 67 out := make(map[Key]Elem) 68 id := m.l.Ident() 69 for k, av := range a { 70 bv, ok := b[k] 71 if !ok { 72 // Because Merge(x, Ident()) == x, we can skip calling L.Merge. 73 out[k] = av 74 continue 75 } 76 77 w := m.l.Merge(av, bv) 78 if m.l.Equals(w, id) { 79 // In a semilattice, Merge(x, y) = Ident is only possible when x == 80 // Ident and y == Ident. 81 panic(fmt.Sprintf( 82 "%T is not a semilattice: Merge(%v, %v) returned Ident for non-Ident arguments", 83 m.l, av, bv)) 84 } 85 out[k] = w 86 } 87 // We considered keys that are only in a, and in both a and b. Now we just 88 // need to handle keys that are only in b. 89 for k, v2 := range b { 90 if _, ok := a[k]; !ok { 91 out[k] = v2 92 } 93 } 94 95 return out 96 } 97 98 // A DenseMapLattice implements [Semilattice][[]Elem]. It is like a [MapLattice] 99 // that is indexed by integers. The values in the map are themselves defined by 100 // [Semilattice] L. 101 // 102 // Unlike [MapLattice], L's identity element may appear as a value in the map, 103 // to allow for gaps in the numbering of keys when the identity element is 104 // Elem's zero value. 105 type DenseMapLattice[Elem any, L Semilattice[Elem]] struct { 106 l L 107 } 108 109 func (s DenseMapLattice[Elem, L]) Ident() []Elem { 110 return nil 111 } 112 113 func (s DenseMapLattice[Elem, L]) Equals(a, b []Elem) bool { 114 nmin := min(len(a), len(b)) 115 ident := s.l.Ident() 116 117 // Check that up to nmin, all elements in a and b match. If one of a or b 118 // is longer, then its tail nmin:nmax must only contain identity elements. 119 return slices.EqualFunc(a[:nmin], b[:nmin], s.l.Equals) && 120 !slices.ContainsFunc(a[nmin:], func(e Elem) bool { 121 return !s.l.Equals(e, ident) 122 }) && 123 !slices.ContainsFunc(b[nmin:], func(e Elem) bool { 124 return !s.l.Equals(e, ident) 125 }) 126 } 127 128 func (s DenseMapLattice[Elem, L]) Merge(a, b []Elem) []Elem { 129 if len(a) == 0 { 130 return b 131 } else if len(b) == 0 { 132 return a 133 } 134 out := make([]Elem, max(len(a), len(b))) 135 for k := range max(len(a), len(b)) { 136 av := s.l.Ident() 137 bv := s.l.Ident() 138 if k < len(a) { 139 av = a[k] 140 } 141 if k < len(b) { 142 bv = b[k] 143 } 144 out[k] = s.l.Merge(av, bv) 145 } 146 return out 147 }