typeset.go

     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
View as plain text