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

package types

import (
	
	
	
	
	
	. 
	
	
	
	
)

// A declInfo describes a package-level const, type, var, or func declaration.
type declInfo struct {
	file      *Scope        // scope of file containing this declaration
	lhs       []*Var        // lhs of n:1 variable declarations, or nil
	vtyp      ast.Expr      // type, or nil (for const and var declarations only)
	init      ast.Expr      // init/orig expression, or nil (for const and var declarations only)
	inherited bool          // if set, the init expression is inherited from a previous constant declaration
	tdecl     *ast.TypeSpec // type declaration, or nil
	fdecl     *ast.FuncDecl // func declaration, or nil

	// The deps field tracks initialization expression dependencies.
	deps map[Object]bool // lazily initialized
}

// hasInitializer reports whether the declared object has an initialization
// expression or function body.
func ( *declInfo) () bool {
	return .init != nil || .fdecl != nil && .fdecl.Body != nil
}

// addDep adds obj to the set of objects d's init expression depends on.
func ( *declInfo) ( Object) {
	 := .deps
	if  == nil {
		 = make(map[Object]bool)
		.deps = 
	}
	[] = true
}

// arityMatch checks that the lhs and rhs of a const or var decl
// have the appropriate number of names and init exprs. For const
// decls, init is the value spec providing the init exprs; for
// var decls, init is nil (the init exprs are in s in this case).
func ( *Checker) (,  *ast.ValueSpec) {
	 := len(.Names)
	 := len(.Values)
	if  != nil {
		 = len(.Values)
	}

	const  = WrongAssignCount
	switch {
	case  == nil &&  == 0:
		// var decl w/o init expr
		if .Type == nil {
			.error(, , "missing type or init expr")
		}
	case  < :
		if  < len(.Values) {
			// init exprs from s
			 := .Values[]
			.errorf(, , "extra init expr %s", )
			// TODO(gri) avoid declared and not used error here
		} else {
			// init exprs "inherited"
			.errorf(, , "extra init expr at %s", .fset.Position(.Pos()))
			// TODO(gri) avoid declared and not used error here
		}
	case  >  && ( != nil ||  != 1):
		 := .Names[]
		.errorf(, , "missing init expr for %s", )
	}
}

func validatedImportPath( string) (string, error) {
	,  := strconv.Unquote()
	if  != nil {
		return "", 
	}
	if  == "" {
		return "", fmt.Errorf("empty string")
	}
	const  = `!"#$%&'()*,:;<=>?[\]^{|}` + "`\uFFFD"
	for ,  := range  {
		if !unicode.IsGraphic() || unicode.IsSpace() || strings.ContainsRune(, ) {
			return , fmt.Errorf("invalid character %#U", )
		}
	}
	return , nil
}

// declarePkgObj declares obj in the package scope, records its ident -> obj mapping,
// and updates check.objMap. The object must not be a function or method.
func ( *Checker) ( *ast.Ident,  Object,  *declInfo) {
	assert(.Name == .Name())

	// spec: "A package-scope or file-scope identifier with name init
	// may only be declared to be a function with this (func()) signature."
	if .Name == "init" {
		.error(, InvalidInitDecl, "cannot declare init - must be func")
		return
	}

	// spec: "The main package must have package name main and declare
	// a function main that takes no arguments and returns no value."
	if .Name == "main" && .pkg.name == "main" {
		.error(, InvalidMainDecl, "cannot declare main - must be func")
		return
	}

	.declare(.pkg.scope, , , nopos)
	.objMap[] = 
	.setOrder(uint32(len(.objMap)))
}

// filename returns a filename suitable for debugging output.
func ( *Checker) ( int) string {
	 := .files[]
	if  := .Pos(); .IsValid() {
		return .fset.File().Name()
	}
	return fmt.Sprintf("file[%d]", )
}

func ( *Checker) ( positioner, ,  string) *Package {
	// If we already have a package for the given (path, dir)
	// pair, use it instead of doing a full import.
	// Checker.impMap only caches packages that are marked Complete
	// or fake (dummy packages for failed imports). Incomplete but
	// non-fake packages do require an import to complete them.
	 := importKey{, }
	 := .impMap[]
	if  != nil {
		return 
	}

	// no package yet => import it
	if  == "C" && (.conf.FakeImportC || .conf.go115UsesCgo) {
		 = NewPackage("C", "C")
		.fake = true // package scope is not populated
		.cgo = .conf.go115UsesCgo
	} else {
		// ordinary import
		var  error
		if  := .conf.Importer;  == nil {
			 = fmt.Errorf("Config.Importer not installed")
		} else if ,  := .(ImporterFrom);  {
			,  = .ImportFrom(, , 0)
			if  == nil &&  == nil {
				 = fmt.Errorf("Config.Importer.ImportFrom(%s, %s, 0) returned nil but no error", , )
			}
		} else {
			,  = .Import()
			if  == nil &&  == nil {
				 = fmt.Errorf("Config.Importer.Import(%s) returned nil but no error", )
			}
		}
		// make sure we have a valid package name
		// (errors here can only happen through manipulation of packages after creation)
		if  == nil &&  != nil && (.name == "_" || .name == "") {
			 = fmt.Errorf("invalid package name: %q", .name)
			 = nil // create fake package below
		}
		if  != nil {
			.errorf(, BrokenImport, "could not import %s (%s)", , )
			if  == nil {
				// create a new fake package
				// come up with a sensible package name (heuristic)
				 := 
				if  := len();  > 0 && [-1] == '/' {
					 = [:-1]
				}
				if  := strings.LastIndex(, "/");  >= 0 {
					 = [+1:]
				}
				 = NewPackage(, )
			}
			// continue to use the package as best as we can
			.fake = true // avoid follow-up lookup failures
		}
	}

	// package should be complete or marked fake, but be cautious
	if .complete || .fake {
		.impMap[] = 
		// Once we've formatted an error message, keep the pkgPathMap
		// up-to-date on subsequent imports. It is used for package
		// qualification in error messages.
		if .pkgPathMap != nil {
			.markImports()
		}
		return 
	}

	// something went wrong (importer may have returned incomplete package without error)
	return nil
}

// collectObjects collects all file and package objects and inserts them
// into their respective scopes. It also performs imports and associates
// methods with receiver base type names.
func ( *Checker) () {
	 := .pkg

	// pkgImports is the set of packages already imported by any package file seen
	// so far. Used to avoid duplicate entries in pkg.imports. Allocate and populate
	// it (pkg.imports may not be empty if we are checking test files incrementally).
	// Note that pkgImports is keyed by package (and thus package path), not by an
	// importKey value. Two different importKey values may map to the same package
	// which is why we cannot use the check.impMap here.
	var  = make(map[*Package]bool)
	for ,  := range .imports {
		[] = true
	}

	type  struct {
		  *Func      // method
		  bool       // true if pointer receiver
		 *ast.Ident // receiver type name
	}
	var  [] // collected methods with valid receivers and non-blank _ names
	var  []*Scope
	for ,  := range .files {
		// The package identifier denotes the current package,
		// but there is no corresponding package object.
		.recordDef(.Name, nil)

		// Use the actual source file extent rather than *ast.File extent since the
		// latter doesn't include comments which appear at the start or end of the file.
		// Be conservative and use the *ast.File extent if we don't have a *token.File.
		,  := .Pos(), .End()
		if  := .fset.File(.Pos());  != nil {
			,  = token.Pos(.Base()), token.Pos(.Base()+.Size())
		}
		 := NewScope(.scope, , , .filename())
		 = append(, )
		.recordScope(, )

		// determine file directory, necessary to resolve imports
		// FileName may be "" (typically for tests) in which case
		// we get "." as the directory which is what we would want.
		 := dir(.fset.Position(.Name.Pos()).Filename)

		.walkDecls(.Decls, func( decl) {
			switch d := .(type) {
			case importDecl:
				// import package
				if .spec.Path.Value == "" {
					return // error reported by parser
				}
				,  := validatedImportPath(.spec.Path.Value)
				if  != nil {
					.errorf(.spec.Path, BadImportPath, "invalid import path (%s)", )
					return
				}

				 := .importPackage(.spec.Path, , )
				if  == nil {
					return
				}

				// local name overrides imported package name
				 := .name
				if .spec.Name != nil {
					 = .spec.Name.Name
					if  == "C" {
						// match 1.17 cmd/compile (not prescribed by spec)
						.error(.spec.Name, ImportCRenamed, `cannot rename import "C"`)
						return
					}
				}

				if  == "init" {
					.error(.spec, InvalidInitDecl, "cannot import package as init - init must be a func")
					return
				}

				// add package to list of explicit imports
				// (this functionality is provided as a convenience
				// for clients; it is not needed for type-checking)
				if ![] {
					[] = true
					.imports = append(.imports, )
				}

				 := NewPkgName(.spec.Pos(), , , )
				if .spec.Name != nil {
					// in a dot-import, the dot represents the package
					.recordDef(.spec.Name, )
				} else {
					.recordImplicit(.spec, )
				}

				if .fake {
					// match 1.17 cmd/compile (not prescribed by spec)
					.used = true
				}

				// add import to file scope
				.imports = append(.imports, )
				if  == "." {
					// dot-import
					if .dotImportMap == nil {
						.dotImportMap = make(map[dotImportKey]*PkgName)
					}
					// merge imported scope with file scope
					for ,  := range .scope.elems {
						// Note: Avoid eager resolve(name, obj) here, so we only
						// resolve dot-imported objects as needed.

						// A package scope may contain non-exported objects,
						// do not import them!
						if token.IsExported() {
							// declare dot-imported object
							// (Do not use check.declare because it modifies the object
							// via Object.setScopePos, which leads to a race condition;
							// the object may be imported into more than one file scope
							// concurrently. See go.dev/issue/32154.)
							if  := .Lookup();  != nil {
								.errorf(.spec.Name, DuplicateDecl, "%s redeclared in this block", .Name())
								.reportAltDecl()
							} else {
								.insert(, )
								.dotImportMap[dotImportKey{, }] = 
							}
						}
					}
				} else {
					// declare imported package object in file scope
					// (no need to provide s.Name since we called check.recordDef earlier)
					.declare(, nil, , nopos)
				}
			case constDecl:
				// declare all constants
				for ,  := range .spec.Names {
					 := NewConst(.Pos(), , .Name, nil, constant.MakeInt64(int64(.iota)))

					var  ast.Expr
					if  < len(.init) {
						 = .init[]
					}

					 := &declInfo{file: , vtyp: .typ, init: , inherited: .inherited}
					.declarePkgObj(, , )
				}

			case varDecl:
				 := make([]*Var, len(.spec.Names))
				// If there's exactly one rhs initializer, use
				// the same declInfo d1 for all lhs variables
				// so that each lhs variable depends on the same
				// rhs initializer (n:1 var declaration).
				var  *declInfo
				if len(.spec.Values) == 1 {
					// The lhs elements are only set up after the for loop below,
					// but that's ok because declareVar only collects the declInfo
					// for a later phase.
					 = &declInfo{file: , lhs: , vtyp: .spec.Type, init: .spec.Values[0]}
				}

				// declare all variables
				for ,  := range .spec.Names {
					 := NewVar(.Pos(), , .Name, nil)
					[] = 

					 := 
					if  == nil {
						// individual assignments
						var  ast.Expr
						if  < len(.spec.Values) {
							 = .spec.Values[]
						}
						 = &declInfo{file: , vtyp: .spec.Type, init: }
					}

					.declarePkgObj(, , )
				}
			case typeDecl:
				_ = .spec.TypeParams.NumFields() != 0 && .verifyVersionf(.spec.TypeParams.List[0], go1_18, "type parameter")
				 := NewTypeName(.spec.Name.Pos(), , .spec.Name.Name, nil)
				.declarePkgObj(.spec.Name, , &declInfo{file: , tdecl: .spec})
			case funcDecl:
				 := .decl.Name.Name
				 := NewFunc(.decl.Name.Pos(), , , nil)
				 := false // avoid duplicate type parameter errors
				if .decl.Recv.NumFields() == 0 {
					// regular function
					if .decl.Recv != nil {
						.error(.decl.Recv, BadRecv, "method has no receiver")
						// treat as function
					}
					if  == "init" || ( == "main" && .pkg.name == "main") {
						 := InvalidInitDecl
						if  == "main" {
							 = InvalidMainDecl
						}
						if .decl.Type.TypeParams.NumFields() != 0 {
							.softErrorf(.decl.Type.TypeParams.List[0], , "func %s must have no type parameters", )
							 = true
						}
						if  := .decl.Type; .Params.NumFields() != 0 || .Results != nil {
							// TODO(rFindley) Should this be a hard error?
							.softErrorf(.decl.Name, , "func %s must have no arguments and no return values", )
						}
					}
					if  == "init" {
						// don't declare init functions in the package scope - they are invisible
						.parent = .scope
						.recordDef(.decl.Name, )
						// init functions must have a body
						if .decl.Body == nil {
							// TODO(gri) make this error message consistent with the others above
							.softErrorf(, MissingInitBody, "missing function body")
						}
					} else {
						.declare(.scope, .decl.Name, , nopos)
					}
				} else {
					// method

					// TODO(rFindley) earlier versions of this code checked that methods
					//                have no type parameters, but this is checked later
					//                when type checking the function type. Confirm that
					//                we don't need to check tparams here.

					, ,  := .unpackRecv(.decl.Recv.List[0].Type, false)
					// (Methods with invalid receiver cannot be associated to a type, and
					// methods with blank _ names are never found; no need to collect any
					// of them. They will still be type-checked with all the other functions.)
					if  != nil &&  != "_" {
						 = append(, {, , })
					}
					.recordDef(.decl.Name, )
				}
				_ = .decl.Type.TypeParams.NumFields() != 0 && ! && .verifyVersionf(.decl.Type.TypeParams.List[0], go1_18, "type parameter")
				 := &declInfo{file: , fdecl: .decl}
				// Methods are not package-level objects but we still track them in the
				// object map so that we can handle them like regular functions (if the
				// receiver is invalid); also we need their fdecl info when associating
				// them with their receiver base type, below.
				.objMap[] = 
				.setOrder(uint32(len(.objMap)))
			}
		})
	}

	// verify that objects in package and file scopes have different names
	for ,  := range  {
		for ,  := range .elems {
			if  := .scope.Lookup();  != nil {
				 = resolve(, )
				if ,  := .(*PkgName);  {
					.errorf(, DuplicateDecl, "%s already declared through import of %s", .Name(), .Imported())
					.reportAltDecl()
				} else {
					.errorf(, DuplicateDecl, "%s already declared through dot-import of %s", .Name(), .Pkg())
					// TODO(gri) dot-imported objects don't have a position; reportAltDecl won't print anything
					.reportAltDecl()
				}
			}
		}
	}

	// Now that we have all package scope objects and all methods,
	// associate methods with receiver base type name where possible.
	// Ignore methods that have an invalid receiver. They will be
	// type-checked later, with regular functions.
	if  == nil {
		return // nothing to do
	}
	.methods = make(map[*TypeName][]*Func)
	for  := range  {
		 := &[]
		// Determine the receiver base type and associate m with it.
		,  := .resolveBaseTypeName(., ., )
		if  != nil {
			..hasPtrRecv_ = 
			.methods[] = append(.methods[], .)
		}
	}
}

// unpackRecv unpacks a receiver type and returns its components: ptr indicates whether
// rtyp is a pointer receiver, rname is the receiver type name, and tparams are its
// type parameters, if any. The type parameters are only unpacked if unpackParams is
// set. If rname is nil, the receiver is unusable (i.e., the source has a bug which we
// cannot easily work around).
func ( *Checker) ( ast.Expr,  bool) ( bool,  *ast.Ident,  []*ast.Ident) {
: // unpack receiver type
	// This accepts invalid receivers such as ***T and does not
	// work for other invalid receivers, but we don't care. The
	// validity of receiver expressions is checked elsewhere.
	for {
		switch t := .(type) {
		case *ast.ParenExpr:
			 = .X
		case *ast.StarExpr:
			 = true
			 = .X
		default:
			break 
		}
	}

	// unpack type parameters, if any
	switch .(type) {
	case *ast.IndexExpr, *ast.IndexListExpr:
		 := typeparams.UnpackIndexExpr()
		 = .X
		if  {
			for ,  := range .Indices {
				var  *ast.Ident
				switch arg := .(type) {
				case *ast.Ident:
					 = 
				case *ast.BadExpr:
					// ignore - error already reported by parser
				case nil:
					.error(.Orig, InvalidSyntaxTree, "parameterized receiver contains nil parameters")
				default:
					.errorf(, BadDecl, "receiver type parameter %s must be an identifier", )
				}
				if  == nil {
					 = &ast.Ident{NamePos: .Pos(), Name: "_"}
				}
				 = append(, )
			}
		}
	}

	// unpack receiver name
	if ,  := .(*ast.Ident);  != nil {
		 = 
	}

	return
}

// resolveBaseTypeName returns the non-alias base type name for typ, and whether
// there was a pointer indirection to get to it. The base type name must be declared
// in package scope, and there can be at most one pointer indirection. If no such type
// name exists, the returned base is nil.
func ( *Checker) ( bool,  ast.Expr,  []*Scope) ( bool,  *TypeName) {
	// Algorithm: Starting from a type expression, which may be a name,
	// we follow that type through alias declarations until we reach a
	// non-alias type name. If we encounter anything but pointer types or
	// parentheses we're done. If we encounter more than one pointer type
	// we're done.
	 = 
	var  map[*TypeName]bool
	for {
		// Note: this differs from types2, but is necessary. The syntax parser
		// strips unnecessary parens.
		 = unparen()

		// check if we have a pointer type
		if ,  := .(*ast.StarExpr);  != nil {
			// if we've already seen a pointer, we're done
			if  {
				return false, nil
			}
			 = true
			 = unparen(.X) // continue with pointer base type
		}

		// typ must be a name, or a C.name cgo selector.
		var  string
		switch typ := .(type) {
		case *ast.Ident:
			 = .Name
		case *ast.SelectorExpr:
			// C.struct_foo is a valid type name for packages using cgo.
			//
			// Detect this case, and adjust name so that the correct TypeName is
			// resolved below.
			if ,  := .X.(*ast.Ident);  != nil && .Name == "C" {
				// Check whether "C" actually resolves to an import of "C", by looking
				// in the appropriate file scope.
				var  Object
				for ,  := range  {
					if .Contains(.Pos()) {
						 = .Lookup(.Name)
					}
				}
				// If Config.go115UsesCgo is set, the typechecker will resolve Cgo
				// selectors to their cgo name. We must do the same here.
				if ,  := .(*PkgName);  != nil {
					if .imported.cgo { // only set if Config.go115UsesCgo is set
						 = "_Ctype_" + .Sel.Name
					}
				}
			}
			if  == "" {
				return false, nil
			}
		default:
			return false, nil
		}

		// name must denote an object found in the current package scope
		// (note that dot-imported objects are not in the package scope!)
		 := .pkg.scope.Lookup()
		if  == nil {
			return false, nil
		}

		// the object must be a type name...
		,  := .(*TypeName)
		if  == nil {
			return false, nil
		}

		// ... which we have not seen before
		if [] {
			return false, nil
		}

		// we're done if tdecl defined tname as a new type
		// (rather than an alias)
		 := .objMap[].tdecl // must exist for objects in package scope
		if !.Assign.IsValid() {
			return , 
		}

		// otherwise, continue resolving
		 = .Type
		if  == nil {
			 = make(map[*TypeName]bool)
		}
		[] = true
	}
}

// packageObjects typechecks all package objects, but not function bodies.
func ( *Checker) () {
	// process package objects in source order for reproducible results
	 := make([]Object, len(.objMap))
	 := 0
	for  := range .objMap {
		[] = 
		++
	}
	sort.Sort(inSourceOrder())

	// add new methods to already type-checked types (from a prior Checker.Files call)
	for ,  := range  {
		if ,  := .(*TypeName);  != nil && .typ != nil {
			.collectMethods()
		}
	}

	if .enableAlias {
		// With Alias nodes we can process declarations in any order.
		for ,  := range  {
			.objDecl(, nil)
		}
	} else {
		// Without Alias nodes, we process non-alias type declarations first, followed by
		// alias declarations, and then everything else. This appears to avoid most situations
		// where the type of an alias is needed before it is available.
		// There may still be cases where this is not good enough (see also go.dev/issue/25838).
		// In those cases Checker.ident will report an error ("invalid use of type alias").
		var  []*TypeName
		var  []Object // everything that's not a type
		// phase 1: non-alias type declarations
		for ,  := range  {
			if ,  := .(*TypeName);  != nil {
				if .objMap[].tdecl.Assign.IsValid() {
					 = append(, )
				} else {
					.objDecl(, nil)
				}
			} else {
				 = append(, )
			}
		}
		// phase 2: alias type declarations
		for ,  := range  {
			.objDecl(, nil)
		}
		// phase 3: all other declarations
		for ,  := range  {
			.objDecl(, nil)
		}
	}

	// At this point we may have a non-empty check.methods map; this means that not all
	// entries were deleted at the end of typeDecl because the respective receiver base
	// types were not found. In that case, an error was reported when declaring those
	// methods. We can now safely discard this map.
	.methods = nil
}

// inSourceOrder implements the sort.Sort interface.
type inSourceOrder []Object

func ( inSourceOrder) () int           { return len() }
func ( inSourceOrder) (,  int) bool { return [].order() < [].order() }
func ( inSourceOrder) (,  int)      { [], [] = [], [] }

// unusedImports checks for unused imports.
func ( *Checker) () {
	// If function bodies are not checked, packages' uses are likely missing - don't check.
	if .conf.IgnoreFuncBodies {
		return
	}

	// spec: "It is illegal (...) to directly import a package without referring to
	// any of its exported identifiers. To import a package solely for its side-effects
	// (initialization), use the blank identifier as explicit package name."

	for ,  := range .imports {
		if !.used && .name != "_" {
			.errorUnusedPkg()
		}
	}
}

func ( *Checker) ( *PkgName) {
	// If the package was imported with a name other than the final
	// import path element, show it explicitly in the error message.
	// Note that this handles both renamed imports and imports of
	// packages containing unconventional package declarations.
	// Note that this uses / always, even on Windows, because Go import
	// paths always use forward slashes.
	 := .imported.path
	 := 
	if  := strings.LastIndex(, "/");  >= 0 {
		 = [+1:]
	}
	if .name == "" || .name == "." || .name ==  {
		.softErrorf(, UnusedImport, "%q imported and not used", )
	} else {
		.softErrorf(, UnusedImport, "%q imported as %s and not used", , .name)
	}
}

// dir makes a good-faith attempt to return the directory
// portion of path. If path is empty, the result is ".".
// (Per the go/build package dependency tests, we cannot import
// path/filepath and simply use filepath.Dir.)
func dir( string) string {
	if  := strings.LastIndexAny(, `/\`);  > 0 {
		return [:]
	}
	// i <= 0
	return "."
}