// 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
	typ       ast.Expr      // type, or nil
	init      ast.Expr      // init/orig expression, or nil
	inherited bool          // if set, the init expression is inherited from a previous constant declaration
	fdecl     *ast.FuncDecl // func declaration, or nil
	alias     bool          // type alias declaration

	// 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 {
			.errorf(, , "missing type or init expr")
		}
	case  < :
		if  < len(.Values) {
			// init exprs from s
			 := .Values[]
			.errorf(, , "extra init expr %s", )
			// TODO(gri) avoid declared but not used error here
		} else {
			// init exprs "inherited"
			.errorf(, , "extra init expr at %s", .fset.Position(.Pos()))
			// TODO(gri) avoid declared but 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" {
		.errorf(, _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" {
		.errorf(, _InvalidMainDecl, "cannot declare main - must be func")
		return
	}

	.declare(.pkg.scope, , , token.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) ( token.Pos, ,  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(atPos(), _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[] = 
		.pkgCnt[.name]++
		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
	}

	var  []*Func // list of methods with non-blank _ names
	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(.pkg.scope, , , .filename())
		.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
				,  := validatedImportPath(.spec.Path.Value)
				if  != nil {
					.errorf(.spec.Path, _BadImportPath, "invalid import path (%s)", )
					return
				}

				 := .importPackage(.spec.Path.Pos(), , )
				if  == nil {
					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, )
				}

				// local name overrides imported package name
				 := .name
				if .spec.Name != nil {
					 = .spec.Name.Name
					if  == "C" {
						// match cmd/compile (not prescribed by spec)
						.errorf(.spec.Name, _ImportCRenamed, `cannot rename import "C"`)
						return
					}
					if  == "init" {
						.errorf(.spec.Name, _InvalidInitDecl, "cannot declare init - must be func")
						return
					}
				}

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

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

				// add import to file scope
				if  == "." {
					// merge imported scope with file scope
					for ,  := range .scope.elems {
						// A package scope may contain non-exported objects,
						// do not import them!
						if .Exported() {
							// 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 issue #32154.)
							if  := .Insert();  != nil {
								.errorf(.spec.Name, _DuplicateDecl, "%s redeclared in this block", .Name())
								.reportAltDecl()
							}
						}
					}
					// add position to set of dot-import positions for this file
					// (this is only needed for "imported but not used" errors)
					.addUnusedDotImport(, , .spec)
				} else {
					// declare imported package object in file scope
					// (no need to provide s.Name since we called check.recordDef earlier)
					.declare(, nil, , token.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: , typ: .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: , typ: .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: , typ: .spec.Type, init: }
					}

					.declarePkgObj(, , )
				}
			case typeDecl:
				 := NewTypeName(.spec.Name.Pos(), , .spec.Name.Name, nil)
				.declarePkgObj(.spec.Name, , &declInfo{file: , typ: .spec.Type, alias: .spec.Assign.IsValid()})
			case funcDecl:
				 := &declInfo{file: , fdecl: .decl}
				 := .decl.Name.Name
				 := NewFunc(.decl.Name.Pos(), , , nil)
				if .decl.Recv == nil {
					// regular function
					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 {
							.softErrorf(, _MissingInitBody, "missing function body")
						}
					} else {
						.declare(.scope, .decl.Name, , token.NoPos)
					}
				} else {
					// method
					// (Methods with blank _ names are never found; no need to collect
					// them for later type association. They will still be type-checked
					// with all the other functions.)
					if  != "_" {
						 = append(, )
					}
					.recordDef(.decl.Name, )
				}
				// 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 .pkg.scope.children /* file scopes */ {
		for ,  := range .elems {
			if  := .scope.Lookup(.Name());  != nil {
				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  {
		 := .objMap[].fdecl
		if  := .Recv.List; len() > 0 {
			// f is a method.
			// Determine the receiver base type and associate f with it.
			,  := .resolveBaseTypeName([0].Type)
			if  != nil {
				.hasPtrRecv = 
				.methods[] = append(.methods[], )
			}
		}
	}
}

// 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) ( ast.Expr) ( 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 {
		 = 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
		,  := .(*ast.Ident)
		if  == nil {
			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(.Name)
		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[] // must exist for objects in package scope
		if !.alias {
			return , 
		}

		// otherwise, continue resolving
		 = .typ
		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 {
			.addMethodDecls()
		}
	}

	// We process non-alias declarations first, in order to avoid situations where
	// the type of an alias declaration is needed before it is available. In general
	// this is still not enough, as it is possible to create sufficiently convoluted
	// recursive type definitions that will cause a type alias to be needed before it
	// is available (see issue #25838 for examples).
	// As an aside, the cmd/compiler suffers from the same problem (#25838).
	var  []*TypeName
	// phase 1
	for ,  := range  {
		// If we have a type alias, collect it for the 2nd phase.
		if ,  := .(*TypeName);  != nil && .objMap[].alias {
			 = append(, )
			continue
		}

		.objDecl(, nil)
	}
	// phase 2
	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."

	// check use of regular imported packages
	for ,  := range .pkg.scope.children /* file scopes */ {
		for ,  := range .elems {
			if ,  := .(*PkgName);  {
				// Unused "blank imports" are automatically ignored
				// since _ identifiers are not entered into scopes.
				if !.used {
					 := .imported.path
					 := pkgName()
					if .name ==  {
						.softErrorf(, _UnusedImport, "%q imported but not used", )
					} else {
						.softErrorf(, _UnusedImport, "%q imported but not used as %s", , .name)
					}
				}
			}
		}
	}

	// check use of dot-imported packages
	for ,  := range .unusedDotImports {
		for ,  := range  {
			.softErrorf(, _UnusedImport, "%q imported but not used", .path)
		}
	}
}

// pkgName returns the package name (last element) of an import path.
func pkgName( string) string {
	if  := strings.LastIndex(, "/");  >= 0 {
		 = [+1:]
	}
	return 
}

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