// isPackageLevel reports whether obj is a package-level object.
func isPackageLevel(obj types.Object) bool {
	// TODO(adonovan): fix go/types bug:
	//   obj.Parent().Parent() == obj.Pkg().Scope()
	// doesn't work because obj.Parent() gets mutated during
	// dot-imports.
	return obj.Pkg().Scope().Lookup(obj.Name()) == obj
}

// lookup returns the address of the named variable identified by obj
// that is local to function f or one of its enclosing functions.
// If escaping, the reference comes from a potentially escaping pointer
// expression and the referent must be heap-allocated.
//
func (f *Function) lookup(obj types.Object, escaping bool) Value {
	if v, ok := f.objects[obj]; ok {
		if alloc, ok := v.(*Alloc); ok && escaping {
			alloc.Heap = true
		}
		return v // function-local var (address)
	}

	// Definition must be in an enclosing function;
	// plumb it through intervening closures.
	if f.Enclosing == nil {
		panic("no Value for type.Object " + obj.Name())
	}
	outer := f.Enclosing.lookup(obj, true) // escaping
	v := &Capture{
		name:   obj.Name(),
		typ:    outer.Type(),
		pos:    outer.Pos(),
		outer:  outer,
		parent: f,
	}
	f.objects[obj] = v
	f.FreeVars = append(f.FreeVars, v)
	return v
}

// checkSelection checks that all uses and selections that resolve to
// the specified object would continue to do so after the renaming.
func (r *renamer) checkSelections(from types.Object) {
	for pkg, info := range r.packages {
		if id := someUse(info, from); id != nil {
			if !r.checkExport(id, pkg, from) {
				return
			}
		}

		for syntax, sel := range info.Selections {
			// There may be extant selections of only the old
			// name or only the new name, so we must check both.
			// (If neither, the renaming is sound.)
			//
			// In both cases, we wish to compare the lengths
			// of the implicit field path (Selection.Index)
			// to see if the renaming would change it.
			//
			// If a selection that resolves to 'from', when renamed,
			// would yield a path of the same or shorter length,
			// this indicates ambiguity or a changed referent,
			// analogous to same- or sub-block lexical conflict.
			//
			// If a selection using the name 'to' would
			// yield a path of the same or shorter length,
			// this indicates ambiguity or shadowing,
			// analogous to same- or super-block lexical conflict.

			// TODO(adonovan): fix: derive from Types[syntax.X].Mode
			// TODO(adonovan): test with pointer, value, addressable value.
			isAddressable := true

			if sel.Obj() == from {
				if obj, indices, _ := types.LookupFieldOrMethod(sel.Recv(), isAddressable, from.Pkg(), r.to); obj != nil {
					// Renaming this existing selection of
					// 'from' may block access to an existing
					// type member named 'to'.
					delta := len(indices) - len(sel.Index())
					if delta > 0 {
						continue // no ambiguity
					}
					r.selectionConflict(from, delta, syntax, obj)
					return
				}

			} else if sel.Obj().Name() == r.to {
				if obj, indices, _ := types.LookupFieldOrMethod(sel.Recv(), isAddressable, from.Pkg(), from.Name()); obj == from {
					// Renaming 'from' may cause this existing
					// selection of the name 'to' to change
					// its meaning.
					delta := len(indices) - len(sel.Index())
					if delta > 0 {
						continue //  no ambiguity
					}
					r.selectionConflict(from, -delta, syntax, sel.Obj())
					return
				}
			}
		}
	}
}

// isLocal reports whether obj is local to some function.
// Precondition: not a struct field or interface method.
func isLocal(obj types.Object) bool {
	// [... 5=stmt 4=func 3=file 2=pkg 1=universe]
	var depth int
	for scope := obj.Parent(); scope != nil; scope = scope.Parent() {
		depth++
	}
	return depth >= 4
}

// same reports whether x and y are identical, or both are PkgNames
// referring to the same Package.
//
func sameObj(x, y types.Object) bool {
	if x == y {
		return true
	}
	if _, ok := x.(*types.PkgName); ok {
		if _, ok := y.(*types.PkgName); ok {
			return x.Pkg() == y.Pkg()
		}
	}
	return false
}

func (r *resolver) defineObject(b *Block, name string, obj types.Object) {
	if obj.Name() == "_" {
		return
	}
	i := len(b.bindings)
	b.bindings = append(b.bindings, obj)
	b.index[name] = i
	if trace {
		logf("def %s = %s in %s\n", name, types.ObjectString(r.pkg, obj), b)
	}
	r.result.Defs[obj] = b
}

func (r *renamer) checkInLocalScope(from types.Object) {
	info := r.packages[from.Pkg()]

	// Is this object an implicit local var for a type switch?
	// Each case has its own var, whose position is the decl of y,
	// but Ident in that decl does not appear in the Uses map.
	//
	//   switch y := x.(type) {	 // Defs[Ident(y)] is undefined
	//   case int:    print(y)       // Implicits[CaseClause(int)]    = Var(y_int)
	//   case string: print(y)       // Implicits[CaseClause(string)] = Var(y_string)
	//   }
	//
	var isCaseVar bool
	for syntax, obj := range info.Implicits {
		if _, ok := syntax.(*ast.CaseClause); ok && obj.Pos() == from.Pos() {
			isCaseVar = true
			r.check(obj)
		}
	}

	r.checkInLexicalScope(from, info)

	// Finally, if this was a type switch, change the variable y.
	if isCaseVar {
		_, path, _ := r.iprog.PathEnclosingInterval(from.Pos(), from.Pos())
		path[0].(*ast.Ident).Name = r.to // path is [Ident AssignStmt TypeSwitchStmt...]
	}
}

func (c *compiler) newStackVarEx(argument int, stackf *LLVMValue, v types.Object, value llvm.Value, name string) (stackvalue llvm.Value, stackvar *LLVMValue) {
	typ := v.Type()

	// We need to put alloca instructions in the top block or the values
	// displayed when inspecting these variables in a debugger will be
	// completely messed up.
	curBlock := c.builder.GetInsertBlock()
	if p := curBlock.Parent(); !p.IsNil() {
		fb := p.FirstBasicBlock()
		fi := fb.FirstInstruction()
		if !fb.IsNil() && !fi.IsNil() {
			c.builder.SetInsertPointBefore(fi)
		}
	}
	old := c.builder.CurrentDebugLocation()
	c.builder.SetCurrentDebugLocation(llvm.Value{})
	stackvalue = c.builder.CreateAlloca(c.types.ToLLVM(typ), name)

	// For arguments we want to insert the store instruction
	// without debug information to ensure that they are executed
	// (and hence have proper values) before the debugger hits the
	// first line in a function.
	if argument == 0 {
		c.builder.SetCurrentDebugLocation(old)
		c.builder.SetInsertPointAtEnd(curBlock)
	}

	if !value.IsNil() {
		c.builder.CreateStore(value, stackvalue)
	}
	c.builder.SetCurrentDebugLocation(old)
	c.builder.SetInsertPointAtEnd(curBlock)

	ptrvalue := c.NewValue(stackvalue, types.NewPointer(typ))
	stackvar = ptrvalue.makePointee()
	stackvar.stack = stackf
	c.objectdata[v].Value = stackvar

	// Generate debug metadata (will return nil
	// if debug-data generation is disabled).
	if descriptor := c.createLocalVariableMetadata(v, argument); descriptor != nil {
		c.builder.InsertDeclare(
			c.module.Module,
			llvm.MDNode([]llvm.Value{stackvalue}),
			c.debug_info.MDNode(descriptor),
		)
	}
	return stackvalue, stackvar
}

// ssaValueForIdent returns the ssa.Value for the ast.Ident whose path
// to the root of the AST is path.  isAddr reports whether the
// ssa.Value is the address denoted by the ast.Ident, not its value.
//
func ssaValueForIdent(prog *ssa.Program, qinfo *importer.PackageInfo, obj types.Object, path []ast.Node) (value ssa.Value, isAddr bool, err error) {
	switch obj := obj.(type) {
	case *types.Var:
		pkg := prog.Package(qinfo.Pkg)
		pkg.Build()
		if v, addr := prog.VarValue(obj, pkg, path); v != nil {
			return v, addr, nil
		}
		return nil, false, fmt.Errorf("can't locate SSA Value for var %s", obj.Name())

	case *types.Func:
		return prog.FuncValue(obj), false, nil
	}
	panic(obj)
}

// ssaValueForIdent returns the ssa.Value for the ast.Ident whose path
// to the root of the AST is path.  It may return a nil Value without
// an error to indicate the pointer analysis is not appropriate.
//
func ssaValueForIdent(prog *ssa.Program, qinfo *importer.PackageInfo, obj types.Object, path []ast.Node) (ssa.Value, error) {
	if obj, ok := obj.(*types.Var); ok {
		pkg := prog.Package(qinfo.Pkg)
		pkg.Build()
		if v := prog.VarValue(obj, pkg, path); v != nil {
			// Don't run pointer analysis on a ref to a const expression.
			if _, ok := v.(*ssa.Const); ok {
				v = nil
			}
			return v, nil
		}
		return nil, fmt.Errorf("can't locate SSA Value for var %s", obj.Name())
	}

	// Don't run pointer analysis on const/func objects.
	return nil, nil
}

func (c *funcContext) initType(o types.Object) {
	if _, isInterface := o.Type().Underlying().(*types.Interface); !isInterface {
		writeMethodSet := func(t types.Type) {
			methodSet := types.NewMethodSet(t)
			if methodSet.Len() == 0 {
				return
			}
			methods := make([]string, methodSet.Len())
			for i := range methods {
				method := methodSet.At(i)
				pkgPath := ""
				if !method.Obj().Exported() {
					pkgPath = method.Obj().Pkg().Path()
				}
				t := method.Type().(*types.Signature)
				embeddedIndex := -1
				if len(method.Index()) > 1 {
					embeddedIndex = method.Index()[0]
				}
				methods[i] = fmt.Sprintf(`["%s", "%s", %s, %s, %t, %d]`, method.Obj().Name(), pkgPath, c.typeArray(t.Params()), c.typeArray(t.Results()), t.Variadic(), embeddedIndex)
			}
			c.Printf("%s.methods = [%s];", c.typeName(t), strings.Join(methods, ", "))
		}
		writeMethodSet(o.Type())
		writeMethodSet(types.NewPointer(o.Type()))
	}
	switch t := o.Type().Underlying().(type) {
	case *types.Array, *types.Chan, *types.Interface, *types.Map, *types.Pointer, *types.Slice, *types.Signature, *types.Struct:
		c.Printf("%s.init(%s);", c.objectName(o), c.initArgs(t))
	}
}

func (w *Walker) emitObj(obj types.Object) {
	switch obj := obj.(type) {
	case *types.Const:
		w.emitf("const %s %s", obj.Name(), w.typeString(obj.Type()))

	case *types.Var:
		w.emitf("var %s %s", obj.Name(), w.typeString(obj.Type()))

	case *types.TypeName:
		w.emitType(obj)

	case *types.Func:
		w.emitFunc(obj)

	default:
		panic("unknown object: " + obj.String())
	}
}

func objectKind(obj types.Object) string {
	switch obj := obj.(type) {
	case *types.PkgName:
		return "imported package name"
	case *types.TypeName:
		return "type"
	case *types.Var:
		if obj.IsField() {
			return "field"
		}
	case *types.Func:
		if obj.Type().(*types.Signature).Recv() != nil {
			return "method"
		}
	}
	// label, func, var, const
	return strings.ToLower(strings.TrimPrefix(reflect.TypeOf(obj).String(), "*types."))
}

// addSpilledParam declares a parameter that is pre-spilled to the
// stack; the function body will load/store the spilled location.
// Subsequent lifting will eliminate spills where possible.
//
func (f *Function) addSpilledParam(obj types.Object) {
	name := obj.Name()
	param := f.addParam(name, obj.Type())
	spill := &Alloc{
		Name_: name + "~", // "~" means "spilled"
		Type_: pointer(obj.Type()),
		pos:   obj.Pos(),
	}
	f.objects[obj] = spill
	f.Locals = append(f.Locals, spill)
	f.emit(spill)
	f.emit(&Store{Addr: spill, Val: param})
}

// ssaValueForIdent returns the ssa.Value for the ast.Ident whose path
// to the root of the AST is path.  isAddr reports whether the
// ssa.Value is the address denoted by the ast.Ident, not its value.
//
func ssaValueForIdent(prog *ssa.Program, qinfo *loader.PackageInfo, obj types.Object, path []ast.Node) (value ssa.Value, isAddr bool, err error) {
	switch obj := obj.(type) {
	case *types.Var:
		pkg := prog.Package(qinfo.Pkg)
		pkg.Build()
		if v, addr := prog.VarValue(obj, pkg, path); v != nil {
			return v, addr, nil
		}
		return nil, false, fmt.Errorf("can't locate SSA Value for var %s", obj.Name())

	case *types.Func:
		fn := prog.FuncValue(obj)
		if fn == nil {
			return nil, false, fmt.Errorf("%s is an interface method", obj)
		}
		// TODO(adonovan): there's no point running PTA on a *Func ident.
		// Eliminate this feature.
		return fn, false, nil
	}
	panic(obj)
}

func (f *File) checkNilFuncComparison(e *ast.BinaryExpr) {
	if !vet("nilfunc") {
		return
	}

	// Only want == or != comparisons.
	if e.Op != token.EQL && e.Op != token.NEQ {
		return
	}

	// Only want comparisons with a nil identifier on one side.
	var e2 ast.Expr
	switch {
	case f.isNil(e.X):
		e2 = e.Y
	case f.isNil(e.Y):
		e2 = e.X
	default:
		return
	}

	// Only want identifiers or selector expressions.
	var obj types.Object
	switch v := e2.(type) {
	case *ast.Ident:
		obj = f.pkg.idents[v]
	case *ast.SelectorExpr:
		obj = f.pkg.idents[v.Sel]
	default:
		return
	}

	// Only want functions.
	if _, ok := obj.(*types.Func); !ok {
		return
	}

	f.Badf(e.Pos(), "comparison of function %v %v nil is always %v", obj.Name(), e.Op, e.Op == token.NEQ)
}

func (r *renamer) selectionConflict(from types.Object, delta int, syntax *ast.SelectorExpr, obj types.Object) {
	r.errorf(from.Pos(), "renaming this %s %q to %q",
		objectKind(from), from.Name(), r.to)

	switch {
	case delta < 0:
		// analogous to sub-block conflict
		r.errorf(syntax.Sel.Pos(),
			"\twould change the referent of this selection")
		r.errorf(obj.Pos(), "\tto this %s", objectKind(obj))
	case delta == 0:
		// analogous to same-block conflict
		r.errorf(syntax.Sel.Pos(),
			"\twould make this reference ambiguous")
		r.errorf(obj.Pos(), "\twith this %s", objectKind(obj))
	case delta > 0:
		// analogous to super-block conflict
		r.errorf(syntax.Sel.Pos(),
			"\twould shadow this selection")
		r.errorf(obj.Pos(), "\tto the %s declared here",
			objectKind(obj))
	}
}

func (f *Function) addParamObj(obj types.Object) *Parameter {
	name := obj.Name()
	if name == "" {
		name = fmt.Sprintf("arg%d", len(f.Params))
	}
	param := f.addParam(name, obj.Type(), obj.Pos())
	param.object = obj
	return param
}

func (p *printer) printObj(obj types.Object) {
	p.print(obj.Name())

	typ, basic := obj.Type().Underlying().(*types.Basic)
	if basic && typ.Info()&types.IsUntyped != 0 {
		// don't write untyped types
	} else {
		p.print(" ")
		p.writeType(p.pkg, obj.Type())
	}

	if obj, ok := obj.(*types.Const); ok {
		floatFmt := basic && typ.Info()&(types.IsFloat|types.IsComplex) != 0
		p.print(" = ")
		p.print(valString(obj.Val(), floatFmt))
	}
}

// check performs safety checks of the renaming of the 'from' object to r.to.
func (r *renamer) check(from types.Object) {
	if r.objsToUpdate[from] {
		return
	}
	r.objsToUpdate[from] = true

	// NB: order of conditions is important.
	if from_, ok := from.(*types.PkgName); ok {
		r.checkInFileBlock(from_)
	} else if from_, ok := from.(*types.Label); ok {
		r.checkLabel(from_)
	} else if isPackageLevel(from) {
		r.checkInPackageBlock(from)
	} else if v, ok := from.(*types.Var); ok && v.IsField() {
		r.checkStructField(v)
	} else if f, ok := from.(*types.Func); ok && f.Type().(*types.Signature).Recv() != nil {
		r.checkMethod(f)
	} else if isLocal(from) {
		r.checkInLocalScope(from)
	} else {
		r.errorf(from.Pos(), "unexpected %s object %q (please report a bug)\n",
			objectKind(from), from)
	}
}