// 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 types

import (
	
	
	
	
)

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

// A _TypeSet represents the type set of an interface.
// Because of existing language restrictions, methods can be "factored out"
// from the terms. The actual type set is the intersection of the type set
// implied by the methods and the type set described by the terms and the
// comparable bit. To test whether a type is included in a type set
// ("implements" relation), the type must implement all methods _and_ be
// an element of the type set described by the terms and the comparable bit.
// If the term list describes the set of all types and comparable is true,
// only comparable types are meant; in all other cases comparable is false.
type _TypeSet struct {
	methods    []*Func  // all methods of the interface; sorted by unique ID
	terms      termlist // type terms of the type set
	comparable bool     // invariant: !comparable || terms.isAll()
}

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

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

// IsMethodSet reports whether the interface t is fully described by its method set.
func ( *_TypeSet) () bool { return !.comparable && .terms.isAll() }

// IsComparable reports whether each type in the set is comparable.
func ( *_TypeSet) ( map[Type]bool) bool {
	if .terms.isAll() {
		return .comparable
	}
	return .is(func( *term) bool {
		return  != nil && comparable(.typ, false, , nil)
	})
}

// NumMethods returns the number of methods available.
func ( *_TypeSet) () int { return len(.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 ( *_TypeSet) ( int) *Func { return .methods[] }

// LookupMethod returns the index of and method with matching package and name, or (-1, nil).
func ( *_TypeSet) ( *Package,  string,  bool) (int, *Func) {
	return lookupMethod(.methods, , , )
}

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

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

	var  bytes.Buffer
	.WriteByte('{')
	if .comparable {
		.WriteString("comparable")
		if  ||  {
			.WriteString("; ")
		}
	}
	for ,  := range .methods {
		if  > 0 {
			.WriteString("; ")
		}
		.WriteString(.String())
	}
	if  &&  {
		.WriteString("; ")
	}
	if  {
		.WriteString(.terms.String())
	}
	.WriteString("}")
	return .String()
}

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

// hasTerms reports whether the type set has specific type terms.
func ( *_TypeSet) () bool { return !.terms.isEmpty() && !.terms.isAll() }

// subsetOf reports whether s1 ⊆ s2.
func ( *_TypeSet) ( *_TypeSet) bool { return .terms.subsetOf(.terms) }

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

// is calls f with the specific type terms of s and reports whether
// all calls to f returned true. If there are no specific terms, is
// returns the result of f(nil).
func ( *_TypeSet) ( func(*term) bool) bool {
	if !.hasTerms() {
		return (nil)
	}
	for ,  := range .terms {
		assert(.typ != nil)
		if !() {
			return false
		}
	}
	return true
}

// underIs calls f with the underlying types of the specific type terms
// of s and reports whether all calls to f returned true. If there are
// no specific terms, underIs returns the result of f(nil).
func ( *_TypeSet) ( func(Type) bool) bool {
	if !.hasTerms() {
		return (nil)
	}
	for ,  := range .terms {
		assert(.typ != nil)
		// x == under(x) for ~x terms
		 := .typ
		if !.tilde {
			 = under()
		}
		if debug {
			assert(Identical(, under()))
		}
		if !() {
			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( *Checker,  token.Pos,  *Interface) *_TypeSet {
	if .tset != nil {
		return .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
	// 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.
	//
	// TODO(gri) Consider recording when this happens and reporting
	// it as an error (but only if there were no other errors so to
	// to not have unnecessary follow-on errors).
	if !.complete {
		return &topTypeSet
	}

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

		.trace(, "type set for %s", )
		.indent++
		defer func() {
			.indent--
			.trace(, "=> %s ", .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.
	.tset = &_TypeSet{terms: allTermlist} // TODO(gri) is this sufficient?

	var  map[*Union]*_TypeSet
	if  != nil {
		if .unionTypeSets == nil {
			.unionTypeSets = make(map[*Union]*_TypeSet)
		}
		 = .unionTypeSets
	} else {
		 = make(map[*Union]*_TypeSet)
	}

	// 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  []*Func
	var  objset
	var  []*Func
	 := make(map[*Func]token.Pos) // method specification or method embedding position, for good error messages
	 := func( token.Pos,  *Func,  bool) {
		switch  := .insert(); {
		case  == nil:
			 = append(, )
			[] = 
		case :
			if  == nil {
				panic(fmt.Sprintf("%v: duplicate method %s", .pos, .name))
			}
			// check != nil
			.errorf(atPos(), _DuplicateDecl, "duplicate method %s", .name)
			.errorf(atPos([.(*Func)]), _DuplicateDecl, "\tother declaration of %s", .name) // secondary error, \t indented
		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  == nil {
				// check method signatures after all locally embedded interfaces are computed
				 = append(, , .(*Func))
				break
			}
			// check != nil
			.later(func() {
				if !.allowVersion(.pkg, 1, 14) || !Identical(.typ, .Type()) {
					.errorf(atPos(), _DuplicateDecl, "duplicate method %s", .name)
					.errorf(atPos([.(*Func)]), _DuplicateDecl, "\tother declaration of %s", .name) // secondary error, \t indented
				}
			})
		}
	}

	for ,  := range .methods {
		(.pos, , true)
	}

	// collect embedded elements
	 := allTermlist
	 := false
	for ,  := range .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  token.Pos // embedding position
		if .embedPos != nil {
			 = (*.embedPos)[]
		}
		var  bool
		var  termlist
		switch u := under().(type) {
		case *Interface:
			// For now we don't permit type parameters as constraints.
			assert(!isTypeParam())
			 := (, , )
			// If typ is local, an error was already reported where typ is specified/defined.
			if  != nil && .isImportedConstraint() && !.allowVersion(.pkg, 1, 18) {
				.errorf(atPos(), _UnsupportedFeature, "embedding constraint interface %s requires go1.18 or later", )
				continue
			}
			 = .comparable
			for ,  := range .methods {
				(, , false) // use embedding position pos rather than m.pos
			}
			 = .terms
		case *Union:
			if  != nil && !.allowVersion(.pkg, 1, 18) {
				.errorf(atPos(), _InvalidIfaceEmbed, "embedding interface element %s requires go1.18 or later", )
				continue
			}
			 := computeUnionTypeSet(, , , )
			if  == &invalidTypeSet {
				continue // ignore invalid unions
			}
			assert(!.comparable)
			assert(len(.methods) == 0)
			 = .terms
		default:
			if  == Typ[Invalid] {
				continue
			}
			if  != nil && !.allowVersion(.pkg, 1, 18) {
				.errorf(atPos(), _InvalidIfaceEmbed, "embedding non-interface type %s requires go1.18 or later", )
				continue
			}
			 = termlist{{false, }}
		}

		// The type set of an interface is the intersection of the type sets of all its elements.
		// Due to language restrictions, only embedded interfaces can add methods, they are handled
		// separately. Here we only need to intersect the term lists and comparable bits.
		,  = intersectTermLists(, , , )
	}
	.embedPos = nil // not needed anymore (errors have been reported)

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

	.tset.comparable = 
	if len() != 0 {
		sortMethods()
		.tset.methods = 
	}
	.tset.terms = 

	return .tset
}

// TODO(gri) The intersectTermLists function belongs to the termlist implementation.
//           The comparable type set may also be best represented as a term (using
//           a special type).

// intersectTermLists computes the intersection of two term lists and respective comparable bits.
// xcomp, ycomp are valid only if xterms.isAll() and yterms.isAll() respectively.
func intersectTermLists( termlist,  bool,  termlist,  bool) (termlist, bool) {
	 := .intersect()
	// If one of xterms or yterms is marked as comparable,
	// the result must only include comparable types.
	 :=  || 
	if  && !.isAll() {
		// only keep comparable terms
		 := 0
		for ,  := range  {
			assert(.typ != nil)
			if Comparable(.typ) {
				[] = 
				++
			}
		}
		 = [:]
		if !.isAll() {
			 = false
		}
	}
	assert(! || .isAll()) // comparable invariant
	return , 
}

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

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

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

func ( byUniqueMethodName) () int           { return len() }
func ( byUniqueMethodName) (,  int) bool { return [].Id() < [].Id() }
func ( byUniqueMethodName) (,  int)      { [], [] = [], [] }

// 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( *Checker,  map[*Union]*_TypeSet,  token.Pos,  *Union) *_TypeSet {
	if ,  := [];  != nil {
		return 
	}

	// avoid infinite recursion (see also computeInterfaceTypeSet)
	[] = new(_TypeSet)

	var  termlist
	for ,  := range .terms {
		var  termlist
		 := under(.typ)
		if ,  := .(*Interface);  != nil {
			// For now we don't permit type parameters as constraints.
			assert(!isTypeParam(.typ))
			 = computeInterfaceTypeSet(, , ).terms
		} else if .typ == Typ[Invalid] {
			continue
		} else {
			if .tilde && !Identical(.typ, ) {
				// There is no underlying type which is t.typ.
				// The corresponding type set is empty.
				 = nil // ∅ term
			}
			 = termlist{(*term)()}
		}
		// The type set of a union expression is the union
		// of the type sets of each term.
		 = .union()
		if len() > maxTermCount {
			if  != nil {
				.errorf(atPos(), _InvalidUnion, "cannot handle more than %d union terms (implementation limitation)", maxTermCount)
			}
			[] = &invalidTypeSet
			return []
		}
	}
	[].terms = 

	return []
}