typeset.go

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