1 // Code generated by "go test -run=Generate -write=all"; DO NOT EDIT.
2 // Source: ../../cmd/compile/internal/types2/typeset.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 (
11 "go/token"
12 . "internal/types/errors"
13 "slices"
14 "strings"
15 )
16 17 // ----------------------------------------------------------------------------
18 // API
19 20 // A _TypeSet represents the type set of an interface.
21 // Because of existing language restrictions, methods can be "factored out"
22 // from the terms. The actual type set is the intersection of the type set
23 // implied by the methods and the type set described by the terms and the
24 // comparable bit. To test whether a type is included in a type set
25 // ("implements" relation), the type must implement all methods _and_ be
26 // an element of the type set described by the terms and the comparable bit.
27 // If the term list describes the set of all types and comparable is true,
28 // only comparable types are meant; in all other cases comparable is false.
29 type _TypeSet struct {
30 methods []*Func // all methods of the interface; sorted by unique ID
31 terms termlist // type terms of the type set
32 comparable bool // invariant: !comparable || terms.isAll()
33 }
34 35 // IsEmpty reports whether s is the empty set.
36 func (s *_TypeSet) IsEmpty() bool { return s.terms.isEmpty() }
37 38 // IsAll reports whether s is the set of all types (corresponding to the empty interface).
39 func (s *_TypeSet) IsAll() bool { return s.IsMethodSet() && len(s.methods) == 0 }
40 41 // IsMethodSet reports whether the interface t is fully described by its method set.
42 func (s *_TypeSet) IsMethodSet() bool { return !s.comparable && s.terms.isAll() }
43 44 // IsComparable reports whether each type in the set is comparable.
45 func (s *_TypeSet) IsComparable(seen map[Type]bool) bool {
46 if s.terms.isAll() {
47 return s.comparable
48 }
49 return s.is(func(t *term) bool {
50 return t != nil && comparableType(t.typ, false, seen) == nil
51 })
52 }
53 54 // NumMethods returns the number of methods available.
55 func (s *_TypeSet) NumMethods() int { return len(s.methods) }
56 57 // Method returns the i'th method of s for 0 <= i < s.NumMethods().
58 // The methods are ordered by their unique ID.
59 func (s *_TypeSet) Method(i int) *Func { return s.methods[i] }
60 61 // LookupMethod returns the index of and method with matching package and name, or (-1, nil).
62 func (s *_TypeSet) LookupMethod(pkg *Package, name string, foldCase bool) (int, *Func) {
63 return methodIndex(s.methods, pkg, name, foldCase)
64 }
65 66 func (s *_TypeSet) String() string {
67 switch {
68 case s.IsEmpty():
69 return "∅"
70 case s.IsAll():
71 return "𝓤"
72 }
73 74 hasMethods := len(s.methods) > 0
75 hasTerms := s.hasTerms()
76 77 var buf strings.Builder
78 buf.WriteByte('{')
79 if s.comparable {
80 buf.WriteString("comparable")
81 if hasMethods || hasTerms {
82 buf.WriteString("; ")
83 }
84 }
85 for i, m := range s.methods {
86 if i > 0 {
87 buf.WriteString("; ")
88 }
89 buf.WriteString(m.String())
90 }
91 if hasMethods && hasTerms {
92 buf.WriteString("; ")
93 }
94 if hasTerms {
95 buf.WriteString(s.terms.String())
96 }
97 buf.WriteString("}")
98 return buf.String()
99 }
100 101 // ----------------------------------------------------------------------------
102 // Implementation
103 104 // hasTerms reports whether s has specific type terms.
105 func (s *_TypeSet) hasTerms() bool { return !s.terms.isEmpty() && !s.terms.isAll() }
106 107 // subsetOf reports whether s1 ⊆ s2.
108 func (s1 *_TypeSet) subsetOf(s2 *_TypeSet) bool { return s1.terms.subsetOf(s2.terms) }
109 110 // typeset is an iterator over the (type/underlying type) pairs in s.
111 // If s has no specific terms, typeset calls yield with (nil, nil).
112 // In any case, typeset is guaranteed to call yield at least once.
113 func (s *_TypeSet) typeset(yield func(t, u Type) bool) {
114 if !s.hasTerms() {
115 yield(nil, nil)
116 return
117 }
118 119 for _, t := range s.terms {
120 assert(t.typ != nil)
121 // Unalias(x) == under(x) for ~x terms
122 u := Unalias(t.typ)
123 if !t.tilde {
124 u = under(u)
125 }
126 if debug {
127 assert(Identical(u, under(u)))
128 }
129 if !yield(t.typ, u) {
130 break
131 }
132 }
133 }
134 135 // is calls f with the specific type terms of s and reports whether
136 // all calls to f returned true. If there are no specific terms, is
137 // returns the result of f(nil).
138 func (s *_TypeSet) is(f func(*term) bool) bool {
139 if !s.hasTerms() {
140 return f(nil)
141 }
142 for _, t := range s.terms {
143 assert(t.typ != nil)
144 if !f(t) {
145 return false
146 }
147 }
148 return true
149 }
150 151 // topTypeSet may be used as type set for the empty interface.
152 var topTypeSet = _TypeSet{terms: allTermlist}
153 154 // computeInterfaceTypeSet may be called with check == nil.
155 func computeInterfaceTypeSet(check *Checker, pos token.Pos, ityp *Interface) *_TypeSet {
156 if ityp.tset != nil {
157 return ityp.tset
158 }
159 160 // If the interface is not fully set up yet, the type set will
161 // not be complete, which may lead to errors when using the
162 // type set (e.g. missing method). Don't compute a partial type
163 // set (and don't store it!), so that we still compute the full
164 // type set eventually. Instead, return the top type set and
165 // let any follow-on errors play out.
166 //
167 // TODO(gri) Consider recording when this happens and reporting
168 // it as an error (but only if there were no other errors so
169 // to not have unnecessary follow-on errors).
170 if !ityp.complete {
171 return &topTypeSet
172 }
173 174 if check != nil && check.conf._Trace {
175 // Types don't generally have position information.
176 // If we don't have a valid pos provided, try to use
177 // one close enough.
178 if !pos.IsValid() && len(ityp.methods) > 0 {
179 pos = ityp.methods[0].pos
180 }
181 182 check.trace(pos, "-- type set for %s", ityp)
183 check.indent++
184 defer func() {
185 check.indent--
186 check.trace(pos, "=> %s ", ityp.typeSet())
187 }()
188 }
189 190 // An infinitely expanding interface (due to a cycle) is detected
191 // elsewhere (Checker.validType), so here we simply assume we only
192 // have valid interfaces. Mark the interface as complete to avoid
193 // infinite recursion if the validType check occurs later for some
194 // reason.
195 ityp.tset = &_TypeSet{terms: allTermlist} // TODO(gri) is this sufficient?
196 197 var unionSets map[*Union]*_TypeSet
198 if check != nil {
199 if check.unionTypeSets == nil {
200 check.unionTypeSets = make(map[*Union]*_TypeSet)
201 }
202 unionSets = check.unionTypeSets
203 } else {
204 unionSets = make(map[*Union]*_TypeSet)
205 }
206 207 // Methods of embedded interfaces are collected unchanged; i.e., the identity
208 // of a method I.m's Func Object of an interface I is the same as that of
209 // the method m in an interface that embeds interface I. On the other hand,
210 // if a method is embedded via multiple overlapping embedded interfaces, we
211 // don't provide a guarantee which "original m" got chosen for the embedding
212 // interface. See also go.dev/issue/34421.
213 //
214 // If we don't care to provide this identity guarantee anymore, instead of
215 // reusing the original method in embeddings, we can clone the method's Func
216 // Object and give it the position of a corresponding embedded interface. Then
217 // we can get rid of the mpos map below and simply use the cloned method's
218 // position.
219 220 var seen objset
221 var allMethods []*Func
222 mpos := make(map[*Func]token.Pos) // method specification or method embedding position, for good error messages
223 addMethod := func(pos token.Pos, m *Func, explicit bool) {
224 switch other := seen.insert(m); {
225 case other == nil:
226 allMethods = append(allMethods, m)
227 mpos[m] = pos
228 case explicit:
229 if check != nil {
230 err := check.newError(DuplicateDecl)
231 err.addf(atPos(pos), "duplicate method %s", m.name)
232 err.addf(atPos(mpos[other.(*Func)]), "other declaration of method %s", m.name)
233 err.report()
234 }
235 default:
236 // We have a duplicate method name in an embedded (not explicitly declared) method.
237 // Check method signatures after all types are computed (go.dev/issue/33656).
238 // If we're pre-go1.14 (overlapping embeddings are not permitted), report that
239 // error here as well (even though we could do it eagerly) because it's the same
240 // error message.
241 if check != nil {
242 check.later(func() {
243 if pos.IsValid() && !check.allowVersion(go1_14) || !Identical(m.typ, other.Type()) {
244 err := check.newError(DuplicateDecl)
245 err.addf(atPos(pos), "duplicate method %s", m.name)
246 err.addf(atPos(mpos[other.(*Func)]), "other declaration of method %s", m.name)
247 err.report()
248 }
249 }).describef(atPos(pos), "duplicate method check for %s", m.name)
250 }
251 }
252 }
253 254 for _, m := range ityp.methods {
255 addMethod(m.pos, m, true)
256 }
257 258 // collect embedded elements
259 allTerms := allTermlist
260 allComparable := false
261 for i, typ := range ityp.embeddeds {
262 // The embedding position is nil for imported interfaces.
263 // We don't need to do version checks in those cases.
264 var pos token.Pos // embedding position
265 if ityp.embedPos != nil {
266 pos = (*ityp.embedPos)[i]
267 }
268 var comparable bool
269 var terms termlist
270 switch u := under(typ).(type) {
271 case *Interface:
272 // For now we don't permit type parameters as constraints.
273 assert(!isTypeParam(typ))
274 tset := computeInterfaceTypeSet(check, pos, u)
275 // If typ is local, an error was already reported where typ is specified/defined.
276 if pos.IsValid() && check != nil && check.isImportedConstraint(typ) && !check.verifyVersionf(atPos(pos), go1_18, "embedding constraint interface %s", typ) {
277 continue
278 }
279 comparable = tset.comparable
280 for _, m := range tset.methods {
281 addMethod(pos, m, false) // use embedding position pos rather than m.pos
282 }
283 terms = tset.terms
284 case *Union:
285 if pos.IsValid() && check != nil && !check.verifyVersionf(atPos(pos), go1_18, "embedding interface element %s", u) {
286 continue
287 }
288 tset := computeUnionTypeSet(check, unionSets, pos, u)
289 if tset == &invalidTypeSet {
290 continue // ignore invalid unions
291 }
292 assert(!tset.comparable)
293 assert(len(tset.methods) == 0)
294 terms = tset.terms
295 default:
296 if !isValid(u) {
297 continue
298 }
299 if pos.IsValid() && check != nil && !check.verifyVersionf(atPos(pos), go1_18, "embedding non-interface type %s", typ) {
300 continue
301 }
302 terms = termlist{{false, typ}}
303 }
304 305 // The type set of an interface is the intersection of the type sets of all its elements.
306 // Due to language restrictions, only embedded interfaces can add methods, they are handled
307 // separately. Here we only need to intersect the term lists and comparable bits.
308 allTerms, allComparable = intersectTermLists(allTerms, allComparable, terms, comparable)
309 }
310 311 ityp.tset.comparable = allComparable
312 if len(allMethods) != 0 {
313 sortMethods(allMethods)
314 ityp.tset.methods = allMethods
315 }
316 ityp.tset.terms = allTerms
317 318 return ityp.tset
319 }
320 321 // TODO(gri) The intersectTermLists function belongs to the termlist implementation.
322 // The comparable type set may also be best represented as a term (using
323 // a special type).
324 325 // intersectTermLists computes the intersection of two term lists and respective comparable bits.
326 // xcomp, ycomp are valid only if xterms.isAll() and yterms.isAll() respectively.
327 func intersectTermLists(xterms termlist, xcomp bool, yterms termlist, ycomp bool) (termlist, bool) {
328 terms := xterms.intersect(yterms)
329 // If one of xterms or yterms is marked as comparable,
330 // the result must only include comparable types.
331 comp := xcomp || ycomp
332 if comp && !terms.isAll() {
333 // only keep comparable terms
334 i := 0
335 for _, t := range terms {
336 assert(t.typ != nil)
337 if comparableType(t.typ, false /* strictly comparable */, nil) == nil {
338 terms[i] = t
339 i++
340 }
341 }
342 terms = terms[:i]
343 if !terms.isAll() {
344 comp = false
345 }
346 }
347 assert(!comp || terms.isAll()) // comparable invariant
348 return terms, comp
349 }
350 351 func compareFunc(a, b *Func) int {
352 return a.cmp(&b.object)
353 }
354 355 func sortMethods(list []*Func) {
356 slices.SortFunc(list, compareFunc)
357 }
358 359 func assertSortedMethods(list []*Func) {
360 if !debug {
361 panic("assertSortedMethods called outside debug mode")
362 }
363 if !slices.IsSortedFunc(list, compareFunc) {
364 panic("methods not sorted")
365 }
366 }
367 368 // invalidTypeSet is a singleton type set to signal an invalid type set
369 // due to an error. It's also a valid empty type set, so consumers of
370 // type sets may choose to ignore it.
371 var invalidTypeSet _TypeSet
372 373 // computeUnionTypeSet may be called with check == nil.
374 // The result is &invalidTypeSet if the union overflows.
375 func computeUnionTypeSet(check *Checker, unionSets map[*Union]*_TypeSet, pos token.Pos, utyp *Union) *_TypeSet {
376 if tset, _ := unionSets[utyp]; tset != nil {
377 return tset
378 }
379 380 // avoid infinite recursion (see also computeInterfaceTypeSet)
381 unionSets[utyp] = new(_TypeSet)
382 383 var allTerms termlist
384 for _, t := range utyp.terms {
385 var terms termlist
386 u := under(t.typ)
387 if ui, _ := u.(*Interface); ui != nil {
388 // For now we don't permit type parameters as constraints.
389 assert(!isTypeParam(t.typ))
390 terms = computeInterfaceTypeSet(check, pos, ui).terms
391 } else if !isValid(u) {
392 continue
393 } else {
394 if t.tilde && !Identical(t.typ, u) {
395 // There is no underlying type which is t.typ.
396 // The corresponding type set is empty.
397 t = nil // ∅ term
398 }
399 terms = termlist{(*term)(t)}
400 }
401 // The type set of a union expression is the union
402 // of the type sets of each term.
403 allTerms = allTerms.union(terms)
404 if len(allTerms) > maxTermCount {
405 if check != nil {
406 check.errorf(atPos(pos), InvalidUnion, "cannot handle more than %d union terms (implementation limitation)", maxTermCount)
407 }
408 unionSets[utyp] = &invalidTypeSet
409 return unionSets[utyp]
410 }
411 }
412 unionSets[utyp].terms = allTerms
413 414 return unionSets[utyp]
415 }
416