// isHTTPFuncOrMethodOnClient checks whether the given call expression is on
// either a function of the net/http package or a method of http.Client that
// returns (*http.Response, error).
func isHTTPFuncOrMethodOnClient(f *File, expr *ast.CallExpr) bool {
	fun, _ := expr.Fun.(*ast.SelectorExpr)
	sig, _ := f.pkg.types[fun].Type.(*types.Signature)
	if sig == nil {
		return false // the call is not on of the form x.f()
	}

	res := sig.Results()
	if res.Len() != 2 {
		return false // the function called does not return two values.
	}
	if ptr, ok := res.At(0).Type().(*types.Pointer); !ok || !types.Identical(ptr.Elem(), httpResponseType) {
		return false // the first return type is not *http.Response.
	}
	if !types.Identical(res.At(1).Type().Underlying(), errorType) {
		return false // the second return type is not error
	}

	typ := f.pkg.types[fun.X].Type
	if typ == nil {
		id, ok := fun.X.(*ast.Ident)
		return ok && id.Name == "http" // function in net/http package.
	}

	if types.Identical(typ, httpClientType) {
		return true // method on http.Client.
	}
	ptr, ok := typ.(*types.Pointer)
	return ok && types.Identical(ptr.Elem(), httpClientType) // method on *http.Client.
}

// containsAllIdsOf reports whether the method identifiers of T are a
// superset of those in U.  If U belongs to an interface type, the
// result is equal to types.Assignable(T, U), but is cheaper to compute.
//
// TODO(gri): make this a method of *types.MethodSet.
//
func containsAllIdsOf(T, U *types.MethodSet) bool {
	t, tlen := 0, T.Len()
	u, ulen := 0, U.Len()
	for t < tlen && u < ulen {
		tMeth := T.At(t).Obj()
		uMeth := U.At(u).Obj()
		tId := tMeth.Id()
		uId := uMeth.Id()
		if tId > uId {
			// U has a method T lacks: fail.
			return false
		}
		if tId < uId {
			// T has a method U lacks: ignore it.
			t++
			continue
		}
		// U and T both have a method of this Id.  Check types.
		if !types.Identical(tMeth.Type(), uMeth.Type()) {
			return false // type mismatch
		}
		u++
		t++
	}
	return u == ulen
}

func visitTypeAssert(inst *ssa.TypeAssert, fr *frame) {
	if iface, ok := inst.AssertedType.(*types.Interface); ok {
		if meth, _ := types.MissingMethod(inst.X.Type(), iface, true); meth == nil { // No missing methods
			switch vd, kind := fr.get(inst.X); kind {
			case Struct, LocalStruct, Array, LocalArray, Chan:
				fr.tuples[inst] = make(Tuples, 2)
				fr.tuples[inst][0] = vd
				fmt.Fprintf(os.Stderr, "   %s = %s.(type assert %s) iface\n", reg(inst), reg(inst.X), inst.AssertedType.String())
				fmt.Fprintf(os.Stderr, "    ^ defined as %s\n", vd.String())

			default:
				fmt.Fprintf(os.Stderr, "   %s = %s.(type assert %s)\n", red(reg(inst)), reg(inst.X), inst.AssertedType.String())
				fmt.Fprintf(os.Stderr, "    ^ untracked/unknown\n")
			}
			return
		}
	} else { // Concrete type
		if types.Identical(inst.AssertedType.Underlying(), inst.X.Type().Underlying()) {
			switch vd, kind := fr.get(inst.X); kind {
			case Struct, LocalStruct, Array, LocalArray, Chan:
				fr.tuples[inst] = make(Tuples, 2)
				fr.tuples[inst][0] = vd
				fmt.Fprintf(os.Stderr, "   %s = %s.(type assert %s) concrete\n", reg(inst), reg(inst.X), inst.AssertedType.String())
				fmt.Fprintf(os.Stderr, "    ^ defined as %s\n", vd.String())

			default:
				fmt.Fprintf(os.Stderr, "   %s = %s.(type assert %s)\n", red(reg(inst)), reg(inst.X), inst.AssertedType.String())
				fmt.Fprintf(os.Stderr, "    ^ untracked/unknown\n")
			}
			return
		}
	}
	fmt.Fprintf(os.Stderr, "   # %s = %s.(%s) impossible type assertion\n", red(reg(inst)), reg(inst.X), inst.AssertedType.String())
}

// typeAssert checks whether dynamic type of itf is instr.AssertedType.
// It returns the extracted value on success, and panics on failure,
// unless instr.CommaOk, in which case it always returns a "value,ok" tuple.
//
func typeAssert(i *interpreter, instr *ssa.TypeAssert, itf iface) value {
	var v value
	err := ""
	if itf.t == nil {
		err = fmt.Sprintf("interface conversion: interface is nil, not %s", instr.AssertedType)

	} else if idst, ok := instr.AssertedType.Underlying().(*types.Interface); ok {
		v = itf
		err = checkInterface(i, idst, itf)

	} else if types.Identical(itf.t, instr.AssertedType) {
		v = itf.v // extract value

	} else {
		err = fmt.Sprintf("interface conversion: interface is %s, not %s", itf.t, instr.AssertedType)
	}

	if err != "" {
		if !instr.CommaOk {
			panic(err)
		}
		return tuple{zero(instr.AssertedType), false}
	}
	if instr.CommaOk {
		return tuple{v, true}
	}
	return v
}

func (c *funcContext) translateImplicitConversion(expr ast.Expr, desiredType types.Type) *expression {
	if desiredType == nil {
		return c.translateExpr(expr)
	}

	exprType := c.p.TypeOf(expr)
	if types.Identical(exprType, desiredType) {
		return c.translateExpr(expr)
	}

	basicExprType, isBasicExpr := exprType.Underlying().(*types.Basic)
	if isBasicExpr && basicExprType.Kind() == types.UntypedNil {
		return c.formatExpr("%e", c.zeroValue(desiredType))
	}

	switch desiredType.Underlying().(type) {
	case *types.Slice:
		return c.formatExpr("$subslice(new %1s(%2e.$array), %2e.$offset, %2e.$offset + %2e.$length)", c.typeName(desiredType), expr)

	case *types.Interface:
		if typesutil.IsJsObject(exprType) {
			// wrap JS object into js.Object struct when converting to interface
			return c.formatExpr("new $jsObjectPtr(%e)", expr)
		}
		if isWrapped(exprType) {
			return c.formatExpr("new %s(%e)", c.typeName(exprType), expr)
		}
		if _, isStruct := exprType.Underlying().(*types.Struct); isStruct {
			return c.formatExpr("new %1e.constructor.elem(%1e)", expr)
		}
	}

	return c.translateExpr(expr)
}

// Set sets the map entry for key to val,
// and returns the previous entry, if any.
func (m *Map) Set(key types.Type, value interface{}) (prev interface{}) {
	if m.table != nil {
		hash := m.hasher.Hash(key)
		bucket := m.table[hash]
		var hole *entry
		for i, e := range bucket {
			if e.key == nil {
				hole = &bucket[i]
			} else if types.Identical(key, e.key) {
				prev = e.value
				bucket[i].value = value
				return
			}
		}

		if hole != nil {
			*hole = entry{key, value} // overwrite deleted entry
		} else {
			m.table[hash] = append(bucket, entry{key, value})
		}
	} else {
		if m.hasher.memo == nil {
			m.hasher = MakeHasher()
		}
		hash := m.hasher.Hash(key)
		m.table = map[uint32][]entry{hash: {entry{key, value}}}
	}

	m.length++
	return
}

// computeTrackBits sets a.track to the necessary 'track' bits for the pointer queries.
func (a *analysis) computeTrackBits() {
	var queryTypes []types.Type
	for v := range a.config.Queries {
		queryTypes = append(queryTypes, v.Type())
	}
	for v := range a.config.IndirectQueries {
		queryTypes = append(queryTypes, mustDeref(v.Type()))
	}
	for _, t := range queryTypes {
		switch t.Underlying().(type) {
		case *types.Chan:
			a.track |= trackChan
		case *types.Map:
			a.track |= trackMap
		case *types.Pointer:
			a.track |= trackPtr
		case *types.Slice:
			a.track |= trackSlice
		case *types.Interface:
			a.track = trackAll
			return
		}
		if rVObj := a.reflectValueObj; rVObj != nil && types.Identical(t, rVObj.Type()) {
			a.track = trackAll
			return
		}
	}
}

func checkEqualButNotIdentical(t *testing.T, x, y types.Type, comment string) {
	if !types.Identical(x, y) {
		t.Errorf("%s: not equal: %s, %s", comment, x, y)
	}
	if x == y {
		t.Errorf("%s: identical: %v, %v", comment, x, y)
	}
}

// At returns the map entry for the given key.
// The result is nil if the entry is not present.
//
func (m *Map) At(key types.Type) interface{} {
	if m != nil && m.table != nil {
		for _, e := range m.table[m.hasher.Hash(key)] {
			if e.key != nil && types.Identical(key, e.key) {
				return e.value
			}
		}
	}
	return nil
}

// purgeChanOps removes channels that are of different type as queryOp, i.e.
// channel we are looking for.
func purgeChanOps(ops []ChanOp, ch ssa.Value) []ChanOp {
	i := 0
	for _, op := range ops {
		if types.Identical(op.Value.Type().Underlying().(*types.Chan).Elem(), ch.Type().Underlying().(*types.Chan).Elem()) {
			ops[i] = op
			i++
		}
	}
	ops = ops[:i]
	return ops
}

// FindTests returns the Test, Benchmark, and Example functions
// (as defined by "go test") defined in the specified package,
// and its TestMain function, if any.
func FindTests(pkg *Package) (tests, benchmarks, examples []*Function, main *Function) {
	prog := pkg.Prog

	// The first two of these may be nil: if the program doesn't import "testing",
	// it can't contain any tests, but it may yet contain Examples.
	var testSig *types.Signature                              // func(*testing.T)
	var benchmarkSig *types.Signature                         // func(*testing.B)
	var exampleSig = types.NewSignature(nil, nil, nil, false) // func()

	// Obtain the types from the parameters of testing.MainStart.
	if testingPkg := prog.ImportedPackage("testing"); testingPkg != nil {
		mainStart := testingPkg.Func("MainStart")
		params := mainStart.Signature.Params()
		testSig = funcField(params.At(1).Type())
		benchmarkSig = funcField(params.At(2).Type())

		// Does the package define this function?
		//   func TestMain(*testing.M)
		if f := pkg.Func("TestMain"); f != nil {
			sig := f.Type().(*types.Signature)
			starM := mainStart.Signature.Results().At(0).Type() // *testing.M
			if sig.Results().Len() == 0 &&
				sig.Params().Len() == 1 &&
				types.Identical(sig.Params().At(0).Type(), starM) {
				main = f
			}
		}
	}

	// TODO(adonovan): use a stable order, e.g. lexical.
	for _, mem := range pkg.Members {
		if f, ok := mem.(*Function); ok &&
			ast.IsExported(f.Name()) &&
			strings.HasSuffix(prog.Fset.Position(f.Pos()).Filename, "_test.go") {

			switch {
			case testSig != nil && isTestSig(f, "Test", testSig):
				tests = append(tests, f)
			case benchmarkSig != nil && isTestSig(f, "Benchmark", benchmarkSig):
				benchmarks = append(benchmarks, f)
			case isTestSig(f, "Example", exampleSig):
				examples = append(examples, f)
			default:
				continue
			}
		}
	}
	return
}

func (c *funcContext) translateResults(results []ast.Expr) string {
	tuple := c.sig.Results()
	switch tuple.Len() {
	case 0:
		return ""
	case 1:
		result := c.zeroValue(tuple.At(0).Type())
		if results != nil {
			result = results[0]
		}
		v := c.translateImplicitConversion(result, tuple.At(0).Type())
		c.delayedOutput = nil
		return " " + v.String()
	default:
		if len(results) == 1 {
			resultTuple := c.p.TypeOf(results[0]).(*types.Tuple)

			if resultTuple.Len() != tuple.Len() {
				panic("invalid tuple return assignment")
			}

			resultExpr := c.translateExpr(results[0]).String()

			if types.Identical(resultTuple, tuple) {
				return " " + resultExpr
			}

			tmpVar := c.newVariable("_returncast")
			c.Printf("%s = %s;", tmpVar, resultExpr)

			// Not all the return types matched, map everything out for implicit casting
			results = make([]ast.Expr, resultTuple.Len())
			for i := range results {
				results[i] = c.newIdent(fmt.Sprintf("%s[%d]", tmpVar, i), resultTuple.At(i).Type())
			}
		}
		values := make([]string, tuple.Len())
		for i := range values {
			result := c.zeroValue(tuple.At(i).Type())
			if results != nil {
				result = results[i]
			}
			values[i] = c.translateImplicitConversion(result, tuple.At(i).Type()).String()
		}
		c.delayedOutput = nil
		return " [" + strings.Join(values, ", ") + "]"
	}
}

// Delete removes the entry with the given key, if any.
// It returns true if the entry was found.
//
func (m *Map) Delete(key types.Type) bool {
	if m != nil && m.table != nil {
		hash := m.hasher.Hash(key)
		bucket := m.table[hash]
		for i, e := range bucket {
			if e.key != nil && types.Identical(key, e.key) {
				// We can't compact the bucket as it
				// would disturb iterators.
				bucket[i] = entry{}
				m.length--
				return true
			}
		}
	}
	return false
}

// isErrorMethodCall reports whether the call is of a method with signature
//	func Error() string
// where "string" is the universe's string type. We know the method is called "Error".
func (f *File) isErrorMethodCall(call *ast.CallExpr) bool {
	typ := f.pkg.types[call].Type
	if typ != nil {
		// We know it's called "Error", so just check the function signature
		// (stringerType has exactly one method, String).
		if stringerType != nil && stringerType.NumMethods() == 1 {
			return types.Identical(f.pkg.types[call.Fun].Type, stringerType.Method(0).Type())
		}
	}
	// Without types, we can still check by hand.
	// Is it a selector expression? Otherwise it's a function call, not a method call.
	sel, ok := call.Fun.(*ast.SelectorExpr)
	if !ok {
		return false
	}
	// The package is type-checked, so if there are no arguments, we're done.
	if len(call.Args) > 0 {
		return false
	}
	// Check the type of the method declaration
	typ = f.pkg.types[sel].Type
	if typ == nil {
		return false
	}
	// The type must be a signature, but be sure for safety.
	sig, ok := typ.(*types.Signature)
	if !ok {
		return false
	}
	// There must be a receiver for it to be a method call. Otherwise it is
	// a function, not something that satisfies the error interface.
	if sig.Recv() == nil {
		return false
	}
	// There must be no arguments. Already verified by type checking, but be thorough.
	if sig.Params().Len() > 0 {
		return false
	}
	// Finally the real questions.
	// There must be one result.
	if sig.Results().Len() != 1 {
		return false
	}
	// It must have return type "string" from the universe.
	return sig.Results().At(0).Type() == types.Typ[types.String]
}

// assign records pairs of distinct types that are related by
// assignability, where the left-hand side is an interface and both
// sides have methods.
//
// It should be called for all assignability checks, type assertions,
// explicit conversions and comparisons between two types, unless the
// types are uninteresting (e.g. lhs is a concrete type, or the empty
// interface; rhs has no methods).
//
func (f *Finder) assign(lhs, rhs types.Type) {
	if types.Identical(lhs, rhs) {
		return
	}
	if !isInterface(lhs) {
		return
	}

	if f.msetcache.MethodSet(lhs).Len() == 0 {
		return
	}
	if f.msetcache.MethodSet(rhs).Len() == 0 {
		return
	}
	// record the pair
	f.Result[Constraint{lhs, rhs}] = true
}

func checkFuncValue(t *testing.T, prog *ssa.Program, obj *types.Func) {
	fn := prog.FuncValue(obj)
	// fmt.Printf("FuncValue(%s) = %s\n", obj, fn) // debugging
	if fn == nil {
		if obj.Name() != "interfaceMethod" {
			t.Errorf("FuncValue(%s) == nil", obj)
		}
		return
	}
	if fnobj := fn.Object(); fnobj != obj {
		t.Errorf("FuncValue(%s).Object() == %s; value was %s",
			obj, fnobj, fn.Name())
		return
	}
	if !types.Identical(fn.Type(), obj.Type()) {
		t.Errorf("FuncValue(%s).Type() == %s", obj, fn.Type())
		return
	}
}

func checkConstValue(t *testing.T, prog *ssa.Program, obj *types.Const) {
	c := prog.ConstValue(obj)
	// fmt.Printf("ConstValue(%s) = %s\n", obj, c) // debugging
	if c == nil {
		t.Errorf("ConstValue(%s) == nil", obj)
		return
	}
	if !types.Identical(c.Type(), obj.Type()) {
		t.Errorf("ConstValue(%s).Type() == %s", obj, c.Type())
		return
	}
	if obj.Name() != "nil" {
		if !exact.Compare(c.Value, token.EQL, obj.Val()) {
			t.Errorf("ConstValue(%s).Value (%s) != %s",
				obj, c.Value, obj.Val())
			return
		}
	}
}

// isValuePreserving returns true if a conversion from ut_src to
// ut_dst is value-preserving, i.e. just a change of type.
// Precondition: neither argument is a named type.
//
func isValuePreserving(ut_src, ut_dst types.Type) bool {
	// Identical underlying types?
	if types.Identical(ut_dst, ut_src) {
		return true
	}

	switch ut_dst.(type) {
	case *types.Chan:
		// Conversion between channel types?
		_, ok := ut_src.(*types.Chan)
		return ok

	case *types.Pointer:
		// Conversion between pointers with identical base types?
		_, ok := ut_src.(*types.Pointer)
		return ok
	}
	return false
}

// checkShadowing checks whether the identifier shadows an identifier in an outer scope.
func checkShadowing(f *File, ident *ast.Ident) {
	if ident.Name == "_" {
		// Can't shadow the blank identifier.
		return
	}
	obj := f.pkg.defs[ident]
	if obj == nil {
		return
	}
	// obj.Parent.Parent is the surrounding scope. If we can find another declaration
	// starting from there, we have a shadowed identifier.
	_, shadowed := obj.Parent().Parent().LookupParent(obj.Name(), obj.Pos())
	if shadowed == nil {
		return
	}
	// Don't complain if it's shadowing a universe-declared identifier; that's fine.
	if shadowed.Parent() == types.Universe {
		return
	}
	if *strictShadowing {
		// The shadowed identifier must appear before this one to be an instance of shadowing.
		if shadowed.Pos() > ident.Pos() {
			return
		}
	} else {
		// Don't complain if the span of validity of the shadowed identifier doesn't include
		// the shadowing identifier.
		span, ok := f.pkg.spans[shadowed]
		if !ok {
			f.Badf(ident.Pos(), "internal error: no range for %q", ident.Name)
			return
		}
		if !span.contains(ident.Pos()) {
			return
		}
	}
	// Don't complain if the types differ: that implies the programmer really wants two different things.
	if types.Identical(obj.Type(), shadowed.Type()) {
		f.Badf(ident.Pos(), "declaration of %q shadows declaration at %s", obj.Name(), f.loc(shadowed.Pos()))
	}
}

// findVisibleErrs returns a mapping from each package-level variable of type "error" to nil.
func findVisibleErrs(prog *ssa.Program, qpos *queryPos) map[*ssa.Global]ssa.Value {
	globals := make(map[*ssa.Global]ssa.Value)
	for _, pkg := range prog.AllPackages() {
		for _, mem := range pkg.Members {
			gbl, ok := mem.(*ssa.Global)
			if !ok {
				continue
			}
			gbltype := gbl.Type()
			// globals are always pointers
			if !types.Identical(deref(gbltype), builtinErrorType) {
				continue
			}
			if !isAccessibleFrom(gbl.Object(), qpos.info.Pkg) {
				continue
			}
			globals[gbl] = nil
		}
	}
	return globals
}