// Copyright 2013 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.

// This file implements type-checking of identifiers and type expressions.

package types

import (
	
	
	
	
	
)

// ident type-checks identifier e and initializes x with the value or type of e.
// If an error occurred, x.mode is set to invalid.
// For the meaning of def, see Checker.definedType, below.
// If wantType is set, the identifier e is expected to denote a type.
//
func ( *Checker) ( *operand,  *ast.Ident,  *Named,  bool) {
	.mode = invalid
	.expr = 

	// Note that we cannot use check.lookup here because the returned scope
	// may be different from obj.Parent(). See also Scope.LookupParent doc.
	,  := .scope.LookupParent(.Name, .pos)
	if  == nil {
		if .Name == "_" {
			.errorf(, _InvalidBlank, "cannot use _ as value or type")
		} else {
			.errorf(, _UndeclaredName, "undeclared name: %s", .Name)
		}
		return
	}
	.recordUse(, )

	// Type-check the object.
	// Only call Checker.objDecl if the object doesn't have a type yet
	// (in which case we must actually determine it) or the object is a
	// TypeName and we also want a type (in which case we might detect
	// a cycle which needs to be reported). Otherwise we can skip the
	// call and avoid a possible cycle error in favor of the more
	// informative "not a type/value" error that this function's caller
	// will issue (see issue #25790).
	 := .Type()
	if ,  := .(*TypeName);  == nil ||  &&  {
		.objDecl(, )
		 = .Type() // type must have been assigned by Checker.objDecl
	}
	assert( != nil)

	// The object may be dot-imported: If so, remove its package from
	// the map of unused dot imports for the respective file scope.
	// (This code is only needed for dot-imports. Without them,
	// we only have to mark variables, see *Var case below).
	if  := .Pkg();  != .pkg &&  != nil {
		delete(.unusedDotImports[], )
	}

	switch obj := .(type) {
	case *PkgName:
		.errorf(, _InvalidPkgUse, "use of package %s not in selector", .name)
		return

	case *Const:
		.addDeclDep()
		if  == Typ[Invalid] {
			return
		}
		if  == universeIota {
			if .iota == nil {
				.errorf(, _InvalidIota, "cannot use iota outside constant declaration")
				return
			}
			.val = .iota
		} else {
			.val = .val
		}
		assert(.val != nil)
		.mode = constant_

	case *TypeName:
		.mode = typexpr

	case *Var:
		// It's ok to mark non-local variables, but ignore variables
		// from other packages to avoid potential race conditions with
		// dot-imported variables.
		if .pkg == .pkg {
			.used = true
		}
		.addDeclDep()
		if  == Typ[Invalid] {
			return
		}
		.mode = variable

	case *Func:
		.addDeclDep()
		.mode = value

	case *Builtin:
		.id = .id
		.mode = builtin

	case *Nil:
		.mode = value

	default:
		unreachable()
	}

	.typ = 
}

// typ type-checks the type expression e and returns its type, or Typ[Invalid].
func ( *Checker) ( ast.Expr) Type {
	return .definedType(, nil)
}

// definedType is like typ but also accepts a type name def.
// If def != nil, e is the type specification for the defined type def, declared
// in a type declaration, and def.underlying will be set to the type of e before
// any components of e are type-checked.
//
func ( *Checker) ( ast.Expr,  *Named) ( Type) {
	if trace {
		.trace(.Pos(), "%s", )
		.indent++
		defer func() {
			.indent--
			.trace(.Pos(), "=> %s", )
		}()
	}

	 = .typInternal(, )
	assert(isTyped())
	.recordTypeAndValue(, typexpr, , nil)

	return
}

// funcType type-checks a function or method type.
func ( *Checker) ( *Signature,  *ast.FieldList,  *ast.FuncType) {
	 := NewScope(.scope, token.NoPos, token.NoPos, "function")
	.isFunc = true
	.recordScope(, )

	,  := .collectParams(, , false)
	,  := .collectParams(, .Params, true)
	,  := .collectParams(, .Results, false)

	if  != nil {
		// recv parameter list present (may be empty)
		// spec: "The receiver is specified via an extra parameter section preceding the
		// method name. That parameter section must declare a single parameter, the receiver."
		var  *Var
		switch len() {
		case 0:
			.error(, _BadRecv, "method is missing receiver")
			 = NewParam(0, nil, "", Typ[Invalid]) // ignore recv below
		default:
			// more than one receiver
			.error([len()-1], _BadRecv, "method must have exactly one receiver")
			fallthrough // continue with first receiver
		case 1:
			 = [0]
		}
		// spec: "The receiver type must be of the form T or *T where T is a type name."
		// (ignore invalid types - error was reported before)
		if ,  := deref(.typ);  != Typ[Invalid] {
			var  string
			if ,  := .(*Named);  != nil {
				// spec: "The type denoted by T is called the receiver base type; it must not
				// be a pointer or interface type and it must be declared in the same package
				// as the method."
				if .obj.pkg != .pkg {
					 = "type not defined in this package"
				} else {
					// TODO(gri) This is not correct if the underlying type is unknown yet.
					switch u := .underlying.(type) {
					case *Basic:
						// unsafe.Pointer is treated like a regular pointer
						if .kind == UnsafePointer {
							 = "unsafe.Pointer"
						}
					case *Pointer, *Interface:
						 = "pointer or interface type"
					}
				}
			} else {
				 = "basic or unnamed type"
			}
			if  != "" {
				.errorf(, _InvalidRecv, "invalid receiver %s (%s)", .typ, )
				// ok to continue
			}
		}
		.recv = 
	}

	.scope = 
	.params = NewTuple(...)
	.results = NewTuple(...)
	.variadic = 
}

// typInternal drives type checking of types.
// Must only be called by definedType.
//
func ( *Checker) ( ast.Expr,  *Named) Type {
	switch e := .(type) {
	case *ast.BadExpr:
		// ignore - error reported before

	case *ast.Ident:
		var  operand
		.ident(&, , , true)

		switch .mode {
		case typexpr:
			 := .typ
			.setUnderlying()
			return 
		case invalid:
			// ignore - error reported before
		case novalue:
			.errorf(&, _NotAType, "%s used as type", &)
		default:
			.errorf(&, _NotAType, "%s is not a type", &)
		}

	case *ast.SelectorExpr:
		var  operand
		.selector(&, )

		switch .mode {
		case typexpr:
			 := .typ
			.setUnderlying()
			return 
		case invalid:
			// ignore - error reported before
		case novalue:
			.errorf(&, _NotAType, "%s used as type", &)
		default:
			.errorf(&, _NotAType, "%s is not a type", &)
		}

	case *ast.ParenExpr:
		return .definedType(.X, )

	case *ast.ArrayType:
		if .Len != nil {
			 := new(Array)
			.setUnderlying()
			.len = .arrayLength(.Len)
			.elem = .typ(.Elt)
			return 

		} else {
			 := new(Slice)
			.setUnderlying()
			.elem = .typ(.Elt)
			return 
		}

	case *ast.StructType:
		 := new(Struct)
		.setUnderlying()
		.structType(, )
		return 

	case *ast.StarExpr:
		 := new(Pointer)
		.setUnderlying()
		.base = .typ(.X)
		return 

	case *ast.FuncType:
		 := new(Signature)
		.setUnderlying()
		.funcType(, nil, )
		return 

	case *ast.InterfaceType:
		 := new(Interface)
		.setUnderlying()
		.interfaceType(, , )
		return 

	case *ast.MapType:
		 := new(Map)
		.setUnderlying()

		.key = .typ(.Key)
		.elem = .typ(.Value)

		// spec: "The comparison operators == and != must be fully defined
		// for operands of the key type; thus the key type must not be a
		// function, map, or slice."
		//
		// Delay this check because it requires fully setup types;
		// it is safe to continue in any case (was issue 6667).
		.atEnd(func() {
			if !Comparable(.key) {
				.errorf(.Key, _IncomparableMapKey, "incomparable map key type %s", .key)
			}
		})

		return 

	case *ast.ChanType:
		 := new(Chan)
		.setUnderlying()

		 := SendRecv
		switch .Dir {
		case ast.SEND | ast.RECV:
			// nothing to do
		case ast.SEND:
			 = SendOnly
		case ast.RECV:
			 = RecvOnly
		default:
			.invalidAST(, "unknown channel direction %d", .Dir)
			// ok to continue
		}

		.dir = 
		.elem = .typ(.Value)
		return 

	default:
		.errorf(, _NotAType, "%s is not a type", )
	}

	 := Typ[Invalid]
	.setUnderlying()
	return 
}

// typeOrNil type-checks the type expression (or nil value) e
// and returns the typ of e, or nil.
// If e is neither a type nor nil, typOrNil returns Typ[Invalid].
//
func ( *Checker) ( ast.Expr) Type {
	var  operand
	.rawExpr(&, , nil)
	switch .mode {
	case invalid:
		// ignore - error reported before
	case novalue:
		.errorf(&, _NotAType, "%s used as type", &)
	case typexpr:
		return .typ
	case value:
		if .isNil() {
			return nil
		}
		fallthrough
	default:
		.errorf(&, _NotAType, "%s is not a type", &)
	}
	return Typ[Invalid]
}

// arrayLength type-checks the array length expression e
// and returns the constant length >= 0, or a value < 0
// to indicate an error (and thus an unknown length).
func ( *Checker) ( ast.Expr) int64 {
	var  operand
	.expr(&, )
	if .mode != constant_ {
		if .mode != invalid {
			.errorf(&, _InvalidArrayLen, "array length %s must be constant", &)
		}
		return -1
	}
	if isUntyped(.typ) || isInteger(.typ) {
		if  := constant.ToInt(.val); .Kind() == constant.Int {
			if representableConst(, , Typ[Int], nil) {
				if ,  := constant.Int64Val();  &&  >= 0 {
					return 
				}
				.errorf(&, _InvalidArrayLen, "invalid array length %s", &)
				return -1
			}
		}
	}
	.errorf(&, _InvalidArrayLen, "array length %s must be integer", &)
	return -1
}

func ( *Checker) ( *Scope,  *ast.FieldList,  bool) ( []*Var,  bool) {
	if  == nil {
		return
	}

	var ,  bool
	for ,  := range .List {
		 := .Type
		if ,  := .(*ast.Ellipsis);  != nil {
			 = .Elt
			if  &&  == len(.List)-1 && len(.Names) <= 1 {
				 = true
			} else {
				.softErrorf(, _MisplacedDotDotDot, "can only use ... with final parameter in list")
				// ignore ... and continue
			}
		}
		 := .typ()
		// The parser ensures that f.Tag is nil and we don't
		// care if a constructed AST contains a non-nil tag.
		if len(.Names) > 0 {
			// named parameter
			for ,  := range .Names {
				if .Name == "" {
					.invalidAST(, "anonymous parameter")
					// ok to continue
				}
				 := NewParam(.Pos(), .pkg, .Name, )
				.declare(, , , .pos)
				 = append(, )
			}
			 = true
		} else {
			// anonymous parameter
			 := NewParam(.Pos(), .pkg, "", )
			.recordImplicit(, )
			 = append(, )
			 = true
		}
	}

	if  &&  {
		.invalidAST(, "list contains both named and anonymous parameters")
		// ok to continue
	}

	// For a variadic function, change the last parameter's type from T to []T.
	// Since we type-checked T rather than ...T, we also need to retro-actively
	// record the type for ...T.
	if  {
		 := [len()-1]
		.typ = &Slice{elem: .typ}
		.recordTypeAndValue(.List[len(.List)-1].Type, typexpr, .typ, nil)
	}

	return
}

func ( *Checker) ( *objset,  token.Pos,  Object) bool {
	if  := .insert();  != nil {
		.errorf(atPos(), _DuplicateDecl, "%s redeclared", .Name())
		.reportAltDecl()
		return false
	}
	return true
}

func ( *Checker) ( *Interface,  *ast.InterfaceType,  *Named) {
	for ,  := range .Methods.List {
		if len(.Names) > 0 {
			// We have a method with name f.Names[0].
			// (The parser ensures that there's only one method
			// and we don't care if a constructed AST has more.)
			 := .Names[0]
			if .Name == "_" {
				.errorf(, _BlankIfaceMethod, "invalid method name _")
				continue // ignore
			}

			 := .typ(.Type)
			,  := .(*Signature)
			if  == nil {
				if  != Typ[Invalid] {
					.invalidAST(.Type, "%s is not a method signature", )
				}
				continue // ignore
			}

			// use named receiver type if available (for better error messages)
			var  Type = 
			if  != nil {
				 = 
			}
			.recv = NewVar(.Pos(), .pkg, "", )

			 := NewFunc(.Pos(), .pkg, .Name, )
			.recordDef(, )
			.methods = append(.methods, )
		} else {
			// We have an embedded interface and f.Type is its
			// (possibly qualified) embedded type name. Collect
			// it if it's a valid interface.
			 := .typ(.Type)

			 := .underlying()
			if ,  := .(*Interface); ! {
				if  != Typ[Invalid] {
					.errorf(.Type, _InvalidIfaceEmbed, "%s is not an interface", )
				}
				continue
			}

			.embeddeds = append(.embeddeds, )
			.posMap[] = append(.posMap[], .Type.Pos())
		}
	}

	if len(.methods) == 0 && len(.embeddeds) == 0 {
		// empty interface
		.allMethods = markComplete
		return
	}

	// sort for API stability
	sort.Sort(byUniqueMethodName(.methods))
	sort.Stable(byUniqueTypeName(.embeddeds))

	.later(func() { .completeInterface() })
}

func ( *Checker) ( *Interface) {
	if .allMethods != nil {
		return
	}

	// completeInterface may be called via the LookupFieldOrMethod,
	// MissingMethod, Identical, or IdenticalIgnoreTags external API
	// in which case check will be nil. In this case, type-checking
	// must be finished and all interfaces should have been completed.
	if  == nil {
		panic("internal error: incomplete interface")
	}

	if trace {
		.trace(token.NoPos, "complete %s", )
		.indent++
		defer func() {
			.indent--
			.trace(token.NoPos, "=> %s", )
		}()
	}

	// 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.
	.allMethods = markComplete

	// 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  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 :
			.errorf(atPos(), _DuplicateDecl, "duplicate method %s", .name)
			.errorf(atPos([.(*Func)]), _DuplicateDecl, "\tother declaration of %s", .name) // secondary error, \t indented
		default:
			// check method signatures after all types are computed (issue #33656)
			.atEnd(func() {
				if !.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)
	}

	 := .posMap[]
	for ,  := range .embeddeds {
		 := [] // embedding position
		,  := .underlying().(*Interface)
		if ! {
			// An error was reported when collecting the embedded types.
			// Ignore it.
			continue
		}
		.()
		for ,  := range .allMethods {
			(, , false) // use embedding position pos rather than m.pos
		}
	}

	if  != nil {
		sort.Sort(byUniqueMethodName())
		.allMethods = 
	}
}

// byUniqueTypeName named type lists can be sorted by their unique type names.
type byUniqueTypeName []Type

func ( byUniqueTypeName) () int           { return len() }
func ( byUniqueTypeName) (,  int) bool { return sortName([]) < sortName([]) }
func ( byUniqueTypeName) (,  int)      { [], [] = [], [] }

func sortName( Type) string {
	if ,  := .(*Named);  != nil {
		return .obj.Id()
	}
	return ""
}

// 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)      { [], [] = [], [] }

func ( *Checker) ( *ast.BasicLit) string {
	if  != nil {
		if .Kind == token.STRING {
			if ,  := strconv.Unquote(.Value);  == nil {
				return 
			}
		}
		.invalidAST(, "incorrect tag syntax: %q", .Value)
	}
	return ""
}

func ( *Checker) ( *Struct,  *ast.StructType) {
	 := .Fields
	if  == nil {
		return
	}

	// struct fields and tags
	var  []*Var
	var  []string

	// for double-declaration checks
	var  objset

	// current field typ and tag
	var  Type
	var  string
	 := func( *ast.Ident,  bool,  token.Pos) {
		if  != "" &&  == nil {
			 = make([]string, len())
		}
		if  != nil {
			 = append(, )
		}

		 := .Name
		 := NewField(, .pkg, , , )
		// spec: "Within a struct, non-blank field names must be unique."
		if  == "_" || .declareInSet(&, , ) {
			 = append(, )
			.recordDef(, )
		}
	}

	// addInvalid adds an embedded field of invalid type to the struct for
	// fields with errors; this keeps the number of struct fields in sync
	// with the source as long as the fields are _ or have different names
	// (issue #25627).
	 := func( *ast.Ident,  token.Pos) {
		 = Typ[Invalid]
		 = ""
		(, true, )
	}

	for ,  := range .List {
		 = .typ(.Type)
		 = .tag(.Tag)
		if len(.Names) > 0 {
			// named fields
			for ,  := range .Names {
				(, false, .Pos())
			}
		} else {
			// embedded field
			// spec: "An embedded type must be specified as a type name T or as a pointer
			// to a non-interface type name *T, and T itself may not be a pointer type."
			 := .Type.Pos()
			 := embeddedFieldIdent(.Type)
			if  == nil {
				.invalidAST(.Type, "embedded field type %s has no name", .Type)
				 = ast.NewIdent("_")
				.NamePos = 
				(, )
				continue
			}
			,  := deref()
			// Because we have a name, typ must be of the form T or *T, where T is the name
			// of a (named or alias) type, and t (= deref(typ)) must be the type of T.
			switch t := .Underlying().(type) {
			case *Basic:
				if  == Typ[Invalid] {
					// error was reported before
					(, )
					continue
				}

				// unsafe.Pointer is treated like a regular pointer
				if .kind == UnsafePointer {
					.errorf(.Type, _InvalidPtrEmbed, "embedded field type cannot be unsafe.Pointer")
					(, )
					continue
				}

			case *Pointer:
				.errorf(.Type, _InvalidPtrEmbed, "embedded field type cannot be a pointer")
				(, )
				continue

			case *Interface:
				if  {
					.errorf(.Type, _InvalidPtrEmbed, "embedded field type cannot be a pointer to an interface")
					(, )
					continue
				}
			}
			(, true, )
		}
	}

	.fields = 
	.tags = 
}

func embeddedFieldIdent( ast.Expr) *ast.Ident {
	switch e := .(type) {
	case *ast.Ident:
		return 
	case *ast.StarExpr:
		// *T is valid, but **T is not
		if ,  := .X.(*ast.StarExpr); ! {
			return (.X)
		}
	case *ast.SelectorExpr:
		return .Sel
	}
	return nil // invalid embedded field
}