1 // Code generated by "go test -run=Generate -write=all"; DO NOT EDIT.
2 // Source: ../../cmd/compile/internal/types2/termlist.go
3 4 // Copyright 2021 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 "strings"
11 12 // A termlist represents the type set represented by the union
13 // t1 ∪ y2 ∪ ... tn of the type sets of the terms t1 to tn.
14 // A termlist is in normal form if all terms are disjoint.
15 // termlist operations don't require the operands to be in
16 // normal form.
17 type termlist []*term
18 19 // allTermlist represents the set of all types.
20 // It is in normal form.
21 var allTermlist = termlist{new(term)}
22 23 // termSep is the separator used between individual terms.
24 const termSep = " | "
25 26 // String prints the termlist exactly (without normalization).
27 func (xl termlist) String() string {
28 if len(xl) == 0 {
29 return "∅"
30 }
31 var buf strings.Builder
32 for i, x := range xl {
33 if i > 0 {
34 buf.WriteString(termSep)
35 }
36 buf.WriteString(x.String())
37 }
38 return buf.String()
39 }
40 41 // isEmpty reports whether the termlist xl represents the empty set of types.
42 func (xl termlist) isEmpty() bool {
43 // If there's a non-nil term, the entire list is not empty.
44 // If the termlist is in normal form, this requires at most
45 // one iteration.
46 for _, x := range xl {
47 if x != nil {
48 return false
49 }
50 }
51 return true
52 }
53 54 // isAll reports whether the termlist xl represents the set of all types.
55 func (xl termlist) isAll() bool {
56 // If there's a 𝓤 term, the entire list is 𝓤.
57 // If the termlist is in normal form, this requires at most
58 // one iteration.
59 for _, x := range xl {
60 if x != nil && x.typ == nil {
61 return true
62 }
63 }
64 return false
65 }
66 67 // norm returns the normal form of xl.
68 func (xl termlist) norm() termlist {
69 // Quadratic algorithm, but good enough for now.
70 // TODO(gri) fix asymptotic performance
71 used := make([]bool, len(xl))
72 var rl termlist
73 for i, xi := range xl {
74 if xi == nil || used[i] {
75 continue
76 }
77 for j := i + 1; j < len(xl); j++ {
78 xj := xl[j]
79 if xj == nil || used[j] {
80 continue
81 }
82 if u1, u2 := xi.union(xj); u2 == nil {
83 // If we encounter a 𝓤 term, the entire list is 𝓤.
84 // Exit early.
85 // (Note that this is not just an optimization;
86 // if we continue, we may end up with a 𝓤 term
87 // and other terms and the result would not be
88 // in normal form.)
89 if u1.typ == nil {
90 return allTermlist
91 }
92 xi = u1
93 used[j] = true // xj is now unioned into xi - ignore it in future iterations
94 }
95 }
96 rl = append(rl, xi)
97 }
98 return rl
99 }
100 101 // union returns the union xl ∪ yl.
102 func (xl termlist) union(yl termlist) termlist {
103 return append(xl, yl...).norm()
104 }
105 106 // intersect returns the intersection xl ∩ yl.
107 func (xl termlist) intersect(yl termlist) termlist {
108 if xl.isEmpty() || yl.isEmpty() {
109 return nil
110 }
111 112 // Quadratic algorithm, but good enough for now.
113 // TODO(gri) fix asymptotic performance
114 var rl termlist
115 for _, x := range xl {
116 for _, y := range yl {
117 if r := x.intersect(y); r != nil {
118 rl = append(rl, r)
119 }
120 }
121 }
122 return rl.norm()
123 }
124 125 // equal reports whether xl and yl represent the same type set.
126 func (xl termlist) equal(yl termlist) bool {
127 // TODO(gri) this should be more efficient
128 return xl.subsetOf(yl) && yl.subsetOf(xl)
129 }
130 131 // includes reports whether t ∈ xl.
132 func (xl termlist) includes(t Type) bool {
133 for _, x := range xl {
134 if x.includes(t) {
135 return true
136 }
137 }
138 return false
139 }
140 141 // supersetOf reports whether y ⊆ xl.
142 func (xl termlist) supersetOf(y *term) bool {
143 for _, x := range xl {
144 if y.subsetOf(x) {
145 return true
146 }
147 }
148 return false
149 }
150 151 // subsetOf reports whether xl ⊆ yl.
152 func (xl termlist) subsetOf(yl termlist) bool {
153 if yl.isEmpty() {
154 return xl.isEmpty()
155 }
156 157 // each term x of xl must be a subset of yl
158 for _, x := range xl {
159 if !yl.supersetOf(x) {
160 return false // x is not a subset yl
161 }
162 }
163 return true
164 }
165