// 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 Union represents a union of terms embedded in an interface.
type Union struct {
	terms []*Term // list of syntactical terms (not a canonicalized termlist)
}

// NewUnion returns a new [Union] type with the given terms.
// It is an error to create an empty union; they are syntactically not possible.
func ( []*Term) *Union {
	if len() == 0 {
		panic("empty union")
	}
	return &Union{}
}

func ( *Union) () int         { return len(.terms) }
func ( *Union) ( int) *Term { return .terms[] }

func ( *Union) () Type { return  }
func ( *Union) () string   { return TypeString(, nil) }

// A Term represents a term in a [Union].
type Term term

// NewTerm returns a new union term.
func ( bool,  Type) *Term { return &Term{, } }

func ( *Term) () bool    { return .tilde }
func ( *Term) () Type     { return .typ }
func ( *Term) () string { return (*term)().String() }

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

// Avoid excessive type-checking times due to quadratic termlist operations.
const maxTermCount = 100

// parseUnion parses uexpr as a union of expressions.
// The result is a Union type, or Typ[Invalid] for some errors.
func parseUnion( *Checker,  ast.Expr) Type {
	,  := flattenUnion(nil, )
	assert(len() == len()-1)

	var  []*Term

	var  Type
	for ,  := range  {
		 := parseTilde(, )
		if len() == 1 && !.tilde {
			// Single type. Ok to return early because all relevant
			// checks have been performed in parseTilde (no need to
			// run through term validity check below).
			return .typ // typ already recorded through check.typ in parseTilde
		}
		if len() >= maxTermCount {
			if isValid() {
				.errorf(, InvalidUnion, "cannot handle more than %d union terms (implementation limitation)", maxTermCount)
				 = Typ[Invalid]
			}
		} else {
			 = append(, )
			 = &Union{}
		}

		if  > 0 {
			.recordTypeAndValue([-1], typexpr, , nil)
		}
	}

	if !isValid() {
		return 
	}

	// Check validity of terms.
	// Do this check later because it requires types to be set up.
	// Note: This is a quadratic algorithm, but unions tend to be short.
	.later(func() {
		for ,  := range  {
			if !isValid(.typ) {
				continue
			}

			 := under(.typ)
			,  := .(*Interface)
			if .tilde {
				if  != nil {
					.errorf([], InvalidUnion, "invalid use of ~ (%s is an interface)", .typ)
					continue // don't report another error for t
				}

				if !Identical(, .typ) {
					.errorf([], InvalidUnion, "invalid use of ~ (underlying type of %s is %s)", .typ, )
					continue
				}
			}

			// Stand-alone embedded interfaces are ok and are handled by the single-type case
			// in the beginning. Embedded interfaces with tilde are excluded above. If we reach
			// here, we must have at least two terms in the syntactic term list (but not necessarily
			// in the term list of the union's type set).
			if  != nil {
				 := .typeSet()
				switch {
				case .NumMethods() != 0:
					.errorf([], InvalidUnion, "cannot use %s in union (%s contains methods)", , )
				case .typ == universeComparable.Type():
					.error([], InvalidUnion, "cannot use comparable in union")
				case .comparable:
					.errorf([], InvalidUnion, "cannot use %s in union (%s embeds comparable)", , )
				}
				continue // terms with interface types are not subject to the no-overlap rule
			}

			// Report overlapping (non-disjoint) terms such as
			// a|a, a|~a, ~a|~a, and ~a|A (where under(A) == a).
			if  := overlappingTerm([:], );  >= 0 {
				.softErrorf([], InvalidUnion, "overlapping terms %s and %s", , [])
			}
		}
	}).describef(, "check term validity %s", )

	return 
}

func parseTilde( *Checker,  ast.Expr) *Term {
	 := 
	var  bool
	if ,  := .(*ast.UnaryExpr);  != nil && .Op == token.TILDE {
		 = .X
		 = true
	}
	 := .typ()
	// Embedding stand-alone type parameters is not permitted (go.dev/issue/47127).
	// We don't need this restriction anymore if we make the underlying type of a type
	// parameter its constraint interface: if we embed a lone type parameter, we will
	// simply use its underlying type (like we do for other named, embedded interfaces),
	// and since the underlying type is an interface the embedding is well defined.
	if isTypeParam() {
		if  {
			.errorf(, MisplacedTypeParam, "type in term %s cannot be a type parameter", )
		} else {
			.error(, MisplacedTypeParam, "term cannot be a type parameter")
		}
		 = Typ[Invalid]
	}
	 := NewTerm(, )
	if  {
		.recordTypeAndValue(, typexpr, &Union{[]*Term{}}, nil)
	}
	return 
}

// overlappingTerm reports the index of the term x in terms which is
// overlapping (not disjoint) from y. The result is < 0 if there is no
// such term. The type of term y must not be an interface, and terms
// with an interface type are ignored in the terms list.
func overlappingTerm( []*Term,  *Term) int {
	assert(!IsInterface(.typ))
	for ,  := range  {
		if IsInterface(.typ) {
			continue
		}
		// disjoint requires non-nil, non-top arguments,
		// and non-interface types as term types.
		if debug {
			if  == nil || .typ == nil ||  == nil || .typ == nil {
				panic("empty or top union term")
			}
		}
		if !(*term)().disjoint((*term)()) {
			return 
		}
	}
	return -1
}

// flattenUnion walks a union type expression of the form A | B | C | ...,
// extracting both the binary exprs (blist) and leaf types (tlist).
func flattenUnion( []ast.Expr,  ast.Expr) (,  []ast.Expr) {
	if ,  := .(*ast.BinaryExpr);  != nil && .Op == token.OR {
		,  = (, .X)
		 = append(, )
		 = .Y
	}
	return , append(, )
}