path: root/src/cmd/compile/internal/types2/typeset.go

// Copyright 2021 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package types2

import (
	"bytes"
	"cmd/compile/internal/syntax"
	"fmt"
	"sort"
)

// ----------------------------------------------------------------------------
// API

// A _TypeSet represents the type set of an interface.
type _TypeSet struct {
	comparable bool // if set, the interface is or embeds comparable
	// TODO(gri) consider using a set for the methods for faster lookup
	methods []*Func  // all methods of the interface; sorted by unique ID
	terms   termlist // type terms of the type set
}

// IsEmpty reports whether type set s is the empty set.
func (s *_TypeSet) IsEmpty() bool { return s.terms.isEmpty() }

// IsAll reports whether type set s is the set of all types (corresponding to the empty interface).
func (s *_TypeSet) IsAll() bool {
	return !s.comparable && len(s.methods) == 0 && s.terms.isAll()
}

// TODO(gri) IsMethodSet is not a great name for this predicate. Find a better one.

// IsMethodSet reports whether the type set s is described by a single set of methods.
func (s *_TypeSet) IsMethodSet() bool { return !s.comparable && s.terms.isAll() }

// IsComparable reports whether each type in the set is comparable.
func (s *_TypeSet) IsComparable() bool {
	if s.terms.isAll() {
		return s.comparable
	}
	return s.is(func(t *term) bool {
		return Comparable(t.typ)
	})
}

// TODO(gri) IsTypeSet is not a great name for this predicate. Find a better one.

// IsTypeSet reports whether the type set s is represented by a finite set of underlying types.
func (s *_TypeSet) IsTypeSet() bool {
	return !s.comparable && len(s.methods) == 0
}

// NumMethods returns the number of methods available.
func (s *_TypeSet) NumMethods() int { return len(s.methods) }

// Method returns the i'th method of type set s for 0 <= i < s.NumMethods().
// The methods are ordered by their unique ID.
func (s *_TypeSet) Method(i int) *Func { return s.methods[i] }

// LookupMethod returns the index of and method with matching package and name, or (-1, nil).
func (s *_TypeSet) LookupMethod(pkg *Package, name string) (int, *Func) {
	// TODO(gri) s.methods is sorted - consider binary search
	return lookupMethod(s.methods, pkg, name)
}

func (s *_TypeSet) String() string {
	switch {
	case s.IsEmpty():
		return "∅"
	case s.IsAll():
		return "𝓤"
	}

	hasMethods := len(s.methods) > 0
	hasTerms := s.hasTerms()

	var buf bytes.Buffer
	buf.WriteByte('{')
	if s.comparable {
		buf.WriteString(" comparable")
		if hasMethods || hasTerms {
			buf.WriteByte(';')
		}
	}
	for i, m := range s.methods {
		if i > 0 {
			buf.WriteByte(';')
		}
		buf.WriteByte(' ')
		buf.WriteString(m.String())
	}
	if hasMethods && hasTerms {
		buf.WriteByte(';')
	}
	if hasTerms {
		buf.WriteString(s.terms.String())
	}
	buf.WriteString(" }") // there was at least one method or term

	return buf.String()
}

// ----------------------------------------------------------------------------
// Implementation

func (s *_TypeSet) hasTerms() bool              { return !s.terms.isAll() }
func (s *_TypeSet) structuralType() Type        { return s.terms.structuralType() }
func (s *_TypeSet) includes(t Type) bool        { return s.terms.includes(t) }
func (s1 *_TypeSet) subsetOf(s2 *_TypeSet) bool { return s1.terms.subsetOf(s2.terms) }

// TODO(gri) TypeSet.is and TypeSet.underIs should probably also go into termlist.go

var topTerm = term{false, theTop}

func (s *_TypeSet) is(f func(*term) bool) bool {
	if len(s.terms) == 0 {
		return false
	}
	for _, t := range s.terms {
		// Terms represent the top term with a nil type.
		// The rest of the type checker uses the top type
		// instead. Convert.
		// TODO(gri) investigate if we can do without this
		if t.typ == nil {
			t = &topTerm
		}
		if !f(t) {
			return false
		}
	}
	return true
}

func (s *_TypeSet) underIs(f func(Type) bool) bool {
	if len(s.terms) == 0 {
		return false
	}
	for _, t := range s.terms {
		// see corresponding comment in TypeSet.is
		u := t.typ
		if u == nil {
			u = theTop
		}
		// t == under(t) for ~t terms
		if !t.tilde {
			u = under(u)
		}
		if debug {
			assert(Identical(u, under(u)))
		}
		if !f(u) {
			return false
		}
	}
	return true
}

// topTypeSet may be used as type set for the empty interface.
var topTypeSet = _TypeSet{terms: allTermlist}

// computeInterfaceTypeSet may be called with check == nil.
func computeInterfaceTypeSet(check *Checker, pos syntax.Pos, ityp *Interface) *_TypeSet {
	if ityp.tset != nil {
		return ityp.tset
	}

	// If the interface is not fully set up yet, the type set will
	// not be complete, which may lead to errors when using the the
	// type set (e.g. missing method). Don't compute a partial type
	// set (and don't store it!), so that we still compute the full
	// type set eventually. Instead, return the top type set and
	// let any follow-on errors play out.
	if !ityp.complete {
		return &topTypeSet
	}

	if check != nil && check.conf.Trace {
		// Types don't generally have position information.
		// If we don't have a valid pos provided, try to use
		// one close enough.
		if !pos.IsKnown() && len(ityp.methods) > 0 {
			pos = ityp.methods[0].pos
		}

		check.trace(pos, "type set for %s", ityp)
		check.indent++
		defer func() {
			check.indent--
			check.trace(pos, "=> %s ", ityp.typeSet())
		}()
	}

	// An infinitely expanding interface (due to a cycle) is detected
	// elsewhere (Checker.validType), so here we simply assume we only
	// have valid interfaces. Mark the interface as complete to avoid
	// infinite recursion if the validType check occurs later for some
	// reason.
	ityp.tset = &_TypeSet{terms: allTermlist} // TODO(gri) is this sufficient?

	// Methods of embedded interfaces are collected unchanged; i.e., the identity
	// of a method I.m's Func Object of an interface I is the same as that of
	// the method m in an interface that embeds interface I. On the other hand,
	// if a method is embedded via multiple overlapping embedded interfaces, we
	// don't provide a guarantee which "original m" got chosen for the embedding
	// interface. See also issue #34421.
	//
	// If we don't care to provide this identity guarantee anymore, instead of
	// reusing the original method in embeddings, we can clone the method's Func
	// Object and give it the position of a corresponding embedded interface. Then
	// we can get rid of the mpos map below and simply use the cloned method's
	// position.

	var todo []*Func
	var seen objset
	var methods []*Func
	mpos := make(map[*Func]syntax.Pos) // method specification or method embedding position, for good error messages
	addMethod := func(pos syntax.Pos, m *Func, explicit bool) {
		switch other := seen.insert(m); {
		case other == nil:
			methods = append(methods, m)
			mpos[m] = pos
		case explicit:
			if check == nil {
				panic(fmt.Sprintf("%s: duplicate method %s", m.pos, m.name))
			}
			// check != nil
			var err error_
			err.errorf(pos, "duplicate method %s", m.name)
			err.errorf(mpos[other.(*Func)], "other declaration of %s", m.name)
			check.report(&err)
		default:
			// We have a duplicate method name in an embedded (not explicitly declared) method.
			// Check method signatures after all types are computed (issue #33656).
			// If we're pre-go1.14 (overlapping embeddings are not permitted), report that
			// error here as well (even though we could do it eagerly) because it's the same
			// error message.
			if check == nil {
				// check method signatures after all locally embedded interfaces are computed
				todo = append(todo, m, other.(*Func))
				break
			}
			// check != nil
			check.later(func() {
				if !check.allowVersion(m.pkg, 1, 14) || !Identical(m.typ, other.Type()) {
					var err error_
					err.errorf(pos, "duplicate method %s", m.name)
					err.errorf(mpos[other.(*Func)], "other declaration of %s", m.name)
					check.report(&err)
				}
			})
		}
	}

	for _, m := range ityp.methods {
		addMethod(m.pos, m, true)
	}

	// collect embedded elements
	var allTerms = allTermlist
	for i, typ := range ityp.embeddeds {
		// The embedding position is nil for imported interfaces
		// and also for interface copies after substitution (but
		// in that case we don't need to report errors again).
		var pos syntax.Pos // embedding position
		if ityp.embedPos != nil {
			pos = (*ityp.embedPos)[i]
		}
		var terms termlist
		switch u := under(typ).(type) {
		case *Interface:
			tset := computeInterfaceTypeSet(check, pos, u)
			if tset.comparable {
				ityp.tset.comparable = true
			}
			for _, m := range tset.methods {
				addMethod(pos, m, false) // use embedding position pos rather than m.pos
			}
			terms = tset.terms
		case *Union:
			tset := computeUnionTypeSet(check, pos, u)
			if tset == &invalidTypeSet {
				continue // ignore invalid unions
			}
			terms = tset.terms
		case *TypeParam:
			// Embedding stand-alone type parameters is not permitted.
			// This case is handled during union parsing.
			unreachable()
		default:
			if typ == Typ[Invalid] {
				continue
			}
			if check != nil && !check.allowVersion(check.pkg, 1, 18) {
				check.errorf(pos, "%s is not an interface", typ)
				continue
			}
			terms = termlist{{false, typ}}
		}
		// The type set of an interface is the intersection
		// of the type sets of all its elements.
		// Intersection cannot produce longer termlists and
		// thus cannot overflow.
		allTerms = allTerms.intersect(terms)
	}
	ityp.embedPos = nil // not needed anymore (errors have been reported)

	// process todo's (this only happens if check == nil)
	for i := 0; i < len(todo); i += 2 {
		m := todo[i]
		other := todo[i+1]
		if !Identical(m.typ, other.typ) {
			panic(fmt.Sprintf("%s: duplicate method %s", m.pos, m.name))
		}
	}

	if methods != nil {
		sortMethods(methods)
		ityp.tset.methods = methods
	}
	ityp.tset.terms = allTerms

	return ityp.tset
}

func sortMethods(list []*Func) {
	sort.Sort(byUniqueMethodName(list))
}

func assertSortedMethods(list []*Func) {
	if !debug {
		panic("assertSortedMethods called outside debug mode")
	}
	if !sort.IsSorted(byUniqueMethodName(list)) {
		panic("methods not sorted")
	}
}

// byUniqueMethodName method lists can be sorted by their unique method names.
type byUniqueMethodName []*Func

func (a byUniqueMethodName) Len() int           { return len(a) }
func (a byUniqueMethodName) Less(i, j int) bool { return a[i].less(&a[j].object) }
func (a byUniqueMethodName) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }

// invalidTypeSet is a singleton type set to signal an invalid type set
// due to an error. It's also a valid empty type set, so consumers of
// type sets may choose to ignore it.
var invalidTypeSet _TypeSet

// computeUnionTypeSet may be called with check == nil.
// The result is &invalidTypeSet if the union overflows.
func computeUnionTypeSet(check *Checker, pos syntax.Pos, utyp *Union) *_TypeSet {
	if utyp.tset != nil {
		return utyp.tset
	}

	// avoid infinite recursion (see also computeInterfaceTypeSet)
	utyp.tset = new(_TypeSet)

	var allTerms termlist
	for _, t := range utyp.terms {
		var terms termlist
		switch u := under(t.typ).(type) {
		case *Interface:
			terms = computeInterfaceTypeSet(check, pos, u).terms
		case *TypeParam:
			// A stand-alone type parameters is not permitted as union term.
			// This case is handled during union parsing.
			unreachable()
		default:
			if t.typ == Typ[Invalid] {
				continue
			}
			terms = termlist{(*term)(t)}
		}
		// The type set of a union expression is the union
		// of the type sets of each term.
		allTerms = allTerms.union(terms)
		if len(allTerms) > maxTermCount {
			if check != nil {
				check.errorf(pos, "cannot handle more than %d union terms (implementation limitation)", maxTermCount)
			}
			utyp.tset = &invalidTypeSet
			return utyp.tset
		}
	}
	utyp.tset.terms = allTerms

	return utyp.tset
}