src/cmd/gofix/typecheck.go - go - Git at Google

 // Copyright 2011 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 main

 import (
 	"fmt"
 	"go/ast"
 	"go/token"
 	"os"
 	"reflect"
 	"strings"
 )

 // Partial type checker.
 //
 // The fact that it is partial is very important: the input is
 // an AST and a description of some type information to
 // assume about one or more packages, but not all the
 // packages that the program imports.  The checker is
 // expected to do as much as it can with what it has been
 // given.  There is not enough information supplied to do
 // a full type check, but the type checker is expected to
 // apply information that can be derived from variable
 // declarations, function and method returns, and type switches
 // as far as it can, so that the caller can still tell the types
 // of expression relevant to a particular fix.
 //
 // TODO(rsc,gri): Replace with go/typechecker.
 // Doing that could be an interesting test case for go/typechecker:
 // the constraints about working with partial information will
 // likely exercise it in interesting ways.  The ideal interface would
 // be to pass typecheck a map from importpath to package API text
 // (Go source code), but for now we use data structures (TypeConfig, Type).
 //
 // The strings mostly use gofmt form.
 //
 // A Field or FieldList has as its type a comma-separated list
 // of the types of the fields.  For example, the field list
 //	x, y, z int
 // has type "int, int, int".

 // The prefix "type " is the type of a type.
 // For example, given
 //	var x int
 //	type T int
 // x's type is "int" but T's type is "type int".
 // mkType inserts the "type " prefix.
 // getType removes it.
 // isType tests for it.

 func mkType(t string) string {
 	return "type " + t
 }

 func getType(t string) string {
 	if !isType(t) {
 		return ""
 	}
 	return t[len("type "):]
 }

 func isType(t string) bool {
 	return strings.HasPrefix(t, "type ")
 }

 // TypeConfig describes the universe of relevant types.
 // For ease of creation, the types are all referred to by string
 // name (e.g., "reflect.Value").  TypeByName is the only place
 // where the strings are resolved.

 type TypeConfig struct {
 	Type map[string]*Type
 	Var  map[string]string
 	Func map[string]string
 }

 // typeof returns the type of the given name, which may be of
 // the form "x" or "p.X".
 func (cfg *TypeConfig) typeof(name string) string {
 	if cfg.Var != nil {
 		if t := cfg.Var[name]; t != "" {
 			return t
 		}
 	}
 	if cfg.Func != nil {
 		if t := cfg.Func[name]; t != "" {
 			return "func()" + t
 		}
 	}
 	return ""
 }

 // Type describes the Fields and Methods of a type.
 // If the field or method cannot be found there, it is next
 // looked for in the Embed list.
 type Type struct {
 	Field  map[string]string // map field name to type
 	Method map[string]string // map method name to comma-separated return types
 	Embed  []string          // list of types this type embeds (for extra methods)
 }

 // dot returns the type of "typ.name", making its decision
 // using the type information in cfg.
 func (typ *Type) dot(cfg *TypeConfig, name string) string {
 	if typ.Field != nil {
 		if t := typ.Field[name]; t != "" {
 			return t
 		}
 	}
 	if typ.Method != nil {
 		if t := typ.Method[name]; t != "" {
 			return t
 		}
 	}

 	for _, e := range typ.Embed {
 		etyp := cfg.Type[e]
 		if etyp != nil {
 			if t := etyp.dot(cfg, name); t != "" {
 				return t
 			}
 		}
 	}

 	return ""
 }

 // typecheck type checks the AST f assuming the information in cfg.
 // It returns a map from AST nodes to type information in gofmt string form.
 func typecheck(cfg *TypeConfig, f *ast.File) map[interface{}]string {
 	typeof := make(map[interface{}]string)

 	// gather function declarations
 	for _, decl := range f.Decls {
 		fn, ok := decl.(*ast.FuncDecl)
 		if !ok {
 			continue
 		}
 		typecheck1(cfg, fn.Type, typeof)
 		t := typeof[fn.Type]
 		if fn.Recv != nil {
 			// The receiver must be a type.
 			rcvr := typeof[fn.Recv]
 			if !isType(rcvr) {
 				if len(fn.Recv.List) != 1 {
 					continue
 				}
 				rcvr = mkType(gofmt(fn.Recv.List[0].Type))
 				typeof[fn.Recv.List[0].Type] = rcvr
 			}
 			rcvr = getType(rcvr)
 			if rcvr != "" && rcvr[0] == '*' {
 				rcvr = rcvr[1:]
 			}
 			typeof[rcvr+"."+fn.Name.Name] = t
 		} else {
 			if isType(t) {
 				t = getType(t)
 			} else {
 				t = gofmt(fn.Type)
 			}
 			typeof[fn.Name] = t

 			// Record typeof[fn.Name.Obj] for future references to fn.Name.
 			typeof[fn.Name.Obj] = t
 		}
 	}

 	typecheck1(cfg, f, typeof)
 	return typeof
 }

 func makeExprList(a []*ast.Ident) []ast.Expr {
 	var b []ast.Expr
 	for _, x := range a {
 		b = append(b, x)
 	}
 	return b
 }

 // Typecheck1 is the recursive form of typecheck.
 // It is like typecheck but adds to the information in typeof
 // instead of allocating a new map.
 func typecheck1(cfg *TypeConfig, f interface{}, typeof map[interface{}]string) {
 	// set sets the type of n to typ.
 	// If isDecl is true, n is being declared.
 	set := func(n ast.Expr, typ string, isDecl bool) {
 		if typeof[n] != "" || typ == "" {
 			return
 		}
 		typeof[n] = typ

 		// If we obtained typ from the declaration of x
 		// propagate the type to all the uses.
 		// The !isDecl case is a cheat here, but it makes
 		// up in some cases for not paying attention to
 		// struct fields.  The real type checker will be
 		// more accurate so we won't need the cheat.
 		if id, ok := n.(*ast.Ident); ok && id.Obj != nil && (isDecl || typeof[id.Obj] == "") {
 			typeof[id.Obj] = typ
 		}
 	}

 	// Type-check an assignment lhs = rhs.
 	// If isDecl is true, this is := so we can update
 	// the types of the objects that lhs refers to.
 	typecheckAssign := func(lhs, rhs []ast.Expr, isDecl bool) {
 		if len(lhs) > 1 && len(rhs) == 1 {
 			if _, ok := rhs[0].(*ast.CallExpr); ok {
 				t := split(typeof[rhs[0]])
 				// Lists should have same length but may not; pair what can be paired.
 				for i := 0; i < len(lhs) && i < len(t); i++ {
 					set(lhs[i], t[i], isDecl)
 				}
 				return
 			}
 		}
 		if len(lhs) == 1 && len(rhs) == 2 {
 			// x = y, ok
 			rhs = rhs[:1]
 		} else if len(lhs) == 2 && len(rhs) == 1 {
 			// x, ok = y
 			lhs = lhs[:1]
 		}

 		// Match as much as we can.
 		for i := 0; i < len(lhs) && i < len(rhs); i++ {
 			x, y := lhs[i], rhs[i]
 			if typeof[y] != "" {
 				set(x, typeof[y], isDecl)
 			} else {
 				set(y, typeof[x], false)
 			}
 		}
 	}

 	// The main type check is a recursive algorithm implemented
 	// by walkBeforeAfter(n, before, after).
 	// Most of it is bottom-up, but in a few places we need
 	// to know the type of the function we are checking.
 	// The before function records that information on
 	// the curfn stack.
 	var curfn []*ast.FuncType

 	before := func(n interface{}) {
 		// push function type on stack
 		switch n := n.(type) {
 		case *ast.FuncDecl:
 			curfn = append(curfn, n.Type)
 		case *ast.FuncLit:
 			curfn = append(curfn, n.Type)
 		}
 	}

 	// After is the real type checker.
 	after := func(n interface{}) {
 		if n == nil {
 			return
 		}
 		if false && reflect.TypeOf(n).Kind() == reflect.Ptr { // debugging trace
 			defer func() {
 				if t := typeof[n]; t != "" {
 					pos := fset.Position(n.(ast.Node).Pos())
 					fmt.Fprintf(os.Stderr, "%s: typeof[%s] = %s\n", pos.String(), gofmt(n), t)
 				}
 			}()
 		}

 		switch n := n.(type) {
 		case *ast.FuncDecl, *ast.FuncLit:
 			// pop function type off stack
 			curfn = curfn[:len(curfn)-1]

 		case *ast.FuncType:
 			typeof[n] = mkType(joinFunc(split(typeof[n.Params]), split(typeof[n.Results])))

 		case *ast.FieldList:
 			// Field list is concatenation of sub-lists.
 			t := ""
 			for _, field := range n.List {
 				if t != "" {
 					t += ", "
 				}
 				t += typeof[field]
 			}
 			typeof[n] = t

 		case *ast.Field:
 			// Field is one instance of the type per name.
 			all := ""
 			t := typeof[n.Type]
 			if !isType(t) {
 				// Create a type, because it is typically *T or *p.T
 				// and we might care about that type.
 				t = mkType(gofmt(n.Type))
 				typeof[n.Type] = t
 			}
 			t = getType(t)
 			if len(n.Names) == 0 {
 				all = t
 			} else {
 				for _, id := range n.Names {
 					if all != "" {
 						all += ", "
 					}
 					all += t
 					typeof[id.Obj] = t
 					typeof[id] = t
 				}
 			}
 			typeof[n] = all

 		case *ast.ValueSpec:
 			// var declaration.  Use type if present.
 			if n.Type != nil {
 				t := typeof[n.Type]
 				if !isType(t) {
 					t = mkType(gofmt(n.Type))
 					typeof[n.Type] = t
 				}
 				t = getType(t)
 				for _, id := range n.Names {
 					set(id, t, true)
 				}
 			}
 			// Now treat same as assignment.
 			typecheckAssign(makeExprList(n.Names), n.Values, true)

 		case *ast.AssignStmt:
 			typecheckAssign(n.Lhs, n.Rhs, n.Tok == token.DEFINE)

 		case *ast.Ident:
 			// Identifier can take its type from underlying object.
 			if t := typeof[n.Obj]; t != "" {
 				typeof[n] = t
 			}

 		case *ast.SelectorExpr:
 			// Field or method.
 			name := n.Sel.Name
 			if t := typeof[n.X]; t != "" {
 				if strings.HasPrefix(t, "*") {
 					t = t[1:] // implicit *
 				}
 				if typ := cfg.Type[t]; typ != nil {
 					if t := typ.dot(cfg, name); t != "" {
 						typeof[n] = t
 						return
 					}
 				}
 				tt := typeof[t+"."+name]
 				if isType(tt) {
 					typeof[n] = getType(tt)
 					return
 				}
 			}
 			// Package selector.
 			if x, ok := n.X.(*ast.Ident); ok && x.Obj == nil {
 				str := x.Name + "." + name
 				if cfg.Type[str] != nil {
 					typeof[n] = mkType(str)
 					return
 				}
 				if t := cfg.typeof(x.Name + "." + name); t != "" {
 					typeof[n] = t
 					return
 				}
 			}

 		case *ast.CallExpr:
 			// make(T) has type T.
 			if isTopName(n.Fun, "make") && len(n.Args) >= 1 {
 				typeof[n] = gofmt(n.Args[0])
 				return
 			}
 			// new(T) has type *T
 			if isTopName(n.Fun, "new") && len(n.Args) == 1 {
 				typeof[n] = "*" + gofmt(n.Args[0])
 				return
 			}
 			// Otherwise, use type of function to determine arguments.
 			t := typeof[n.Fun]
 			in, out := splitFunc(t)
 			if in == nil && out == nil {
 				return
 			}
 			typeof[n] = join(out)
 			for i, arg := range n.Args {
 				if i >= len(in) {
 					break
 				}
 				if typeof[arg] == "" {
 					typeof[arg] = in[i]
 				}
 			}

 		case *ast.TypeAssertExpr:
 			// x.(type) has type of x.
 			if n.Type == nil {
 				typeof[n] = typeof[n.X]
 				return
 			}
 			// x.(T) has type T.
 			if t := typeof[n.Type]; isType(t) {
 				typeof[n] = getType(t)
 			}

 		case *ast.SliceExpr:
 			// x[i:j] has type of x.
 			typeof[n] = typeof[n.X]

 		case *ast.IndexExpr:
 			// x[i] has key type of x's type.
 			t := typeof[n.X]
 			if strings.HasPrefix(t, "[") || strings.HasPrefix(t, "map[") {
 				// Lazy: assume there are no nested [] in the array
 				// length or map key type.
 				if i := strings.Index(t, "]"); i >= 0 {
 					typeof[n] = t[i+1:]
 				}
 			}

 		case *ast.StarExpr:
 			// *x for x of type *T has type T when x is an expr.
 			// We don't use the result when *x is a type, but
 			// compute it anyway.
 			t := typeof[n.X]
 			if isType(t) {
 				typeof[n] = "type *" + getType(t)
 			} else if strings.HasPrefix(t, "*") {
 				typeof[n] = t[len("*"):]
 			}

 		case *ast.UnaryExpr:
 			// &x for x of type T has type *T.
 			t := typeof[n.X]
 			if t != "" && n.Op == token.AND {
 				typeof[n] = "&" + t
 			}

 		case *ast.CompositeLit:
 			// T{...} has type T.
 			typeof[n] = gofmt(n.Type)

 		case *ast.ParenExpr:
 			// (x) has type of x.
 			typeof[n] = typeof[n.X]

 		case *ast.TypeSwitchStmt:
 			// Type of variable changes for each case in type switch,
 			// but go/parser generates just one variable.
 			// Repeat type check for each case with more precise
 			// type information.
 			as, ok := n.Assign.(*ast.AssignStmt)
 			if !ok {
 				return
 			}
 			varx, ok := as.Lhs[0].(*ast.Ident)
 			if !ok {
 				return
 			}
 			t := typeof[varx]
 			for _, cas := range n.Body.List {
 				cas := cas.(*ast.CaseClause)
 				if len(cas.List) == 1 {
 					// Variable has specific type only when there is
 					// exactly one type in the case list.
 					if tt := typeof[cas.List[0]]; isType(tt) {
 						tt = getType(tt)
 						typeof[varx] = tt
 						typeof[varx.Obj] = tt
 						typecheck1(cfg, cas.Body, typeof)
 					}
 				}
 			}
 			// Restore t.
 			typeof[varx] = t
 			typeof[varx.Obj] = t

 		case *ast.ReturnStmt:
 			if len(curfn) == 0 {
 				// Probably can't happen.
 				return
 			}
 			f := curfn[len(curfn)-1]
 			res := n.Results
 			if f.Results != nil {
 				t := split(typeof[f.Results])
 				for i := 0; i < len(res) && i < len(t); i++ {
 					set(res[i], t[i], false)
 				}
 			}
 		}
 	}
 	walkBeforeAfter(f, before, after)
 }

 // Convert between function type strings and lists of types.
 // Using strings makes this a little harder, but it makes
 // a lot of the rest of the code easier.  This will all go away
 // when we can use go/typechecker directly.

 // splitFunc splits "func(x,y,z) (a,b,c)" into ["x", "y", "z"] and ["a", "b", "c"].
 func splitFunc(s string) (in, out []string) {
 	if !strings.HasPrefix(s, "func(") {
 		return nil, nil
 	}

 	i := len("func(") // index of beginning of 'in' arguments
 	nparen := 0
 	for j := i; j < len(s); j++ {
 		switch s[j] {
 		case '(':
 			nparen++
 		case ')':
 			nparen--
 			if nparen < 0 {
 				// found end of parameter list
 				out := strings.TrimSpace(s[j+1:])
 				if len(out) >= 2 && out[0] == '(' && out[len(out)-1] == ')' {
 					out = out[1 : len(out)-1]
 				}
 				return split(s[i:j]), split(out)
 			}
 		}
 	}
 	return nil, nil
 }

 // joinFunc is the inverse of splitFunc.
 func joinFunc(in, out []string) string {
 	outs := ""
 	if len(out) == 1 {
 		outs = " " + out[0]
 	} else if len(out) > 1 {
 		outs = " (" + join(out) + ")"
 	}
 	return "func(" + join(in) + ")" + outs
 }

 // split splits "int, float" into ["int", "float"] and splits "" into [].
 func split(s string) []string {
 	out := []string{}
 	i := 0 // current type being scanned is s[i:j].
 	nparen := 0
 	for j := 0; j < len(s); j++ {
 		switch s[j] {
 		case ' ':
 			if i == j {
 				i++
 			}
 		case '(':
 			nparen++
 		case ')':
 			nparen--
 			if nparen < 0 {
 				// probably can't happen
 				return nil
 			}
 		case ',':
 			if nparen == 0 {
 				if i < j {
 					out = append(out, s[i:j])
 				}
 				i = j + 1
 			}
 		}
 	}
 	if nparen != 0 {
 		// probably can't happen
 		return nil
 	}
 	if i < len(s) {
 		out = append(out, s[i:])
 	}
 	return out
 }

 // join is the inverse of split.
 func join(x []string) string {
 	return strings.Join(x, ", ")
 }
	// Copyright 2011 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 main

	import (
	"fmt"
	"go/ast"
	"go/token"
	"os"
	"reflect"
	"strings"
	)

	// Partial type checker.
	//
	// The fact that it is partial is very important: the input is
	// an AST and a description of some type information to
	// assume about one or more packages, but not all the
	// packages that the program imports. The checker is
	// expected to do as much as it can with what it has been
	// given. There is not enough information supplied to do
	// a full type check, but the type checker is expected to
	// apply information that can be derived from variable
	// declarations, function and method returns, and type switches
	// as far as it can, so that the caller can still tell the types
	// of expression relevant to a particular fix.
	//
	// TODO(rsc,gri): Replace with go/typechecker.
	// Doing that could be an interesting test case for go/typechecker:
	// the constraints about working with partial information will
	// likely exercise it in interesting ways. The ideal interface would
	// be to pass typecheck a map from importpath to package API text
	// (Go source code), but for now we use data structures (TypeConfig, Type).
	//
	// The strings mostly use gofmt form.
	//
	// A Field or FieldList has as its type a comma-separated list
	// of the types of the fields. For example, the field list
	// x, y, z int
	// has type "int, int, int".

	// The prefix "type " is the type of a type.
	// For example, given
	// var x int
	// type T int
	// x's type is "int" but T's type is "type int".
	// mkType inserts the "type " prefix.
	// getType removes it.
	// isType tests for it.

	func mkType(t string) string {
	return "type " + t
	}

	func getType(t string) string {
	if !isType(t) {
	return ""
	}
	return t[len("type "):]
	}

	func isType(t string) bool {
	return strings.HasPrefix(t, "type ")
	}

	// TypeConfig describes the universe of relevant types.
	// For ease of creation, the types are all referred to by string
	// name (e.g., "reflect.Value"). TypeByName is the only place
	// where the strings are resolved.

	type TypeConfig struct {
	Type map[string]*Type
	Var map[string]string
	Func map[string]string
	}

	// typeof returns the type of the given name, which may be of
	// the form "x" or "p.X".
	func (cfg *TypeConfig) typeof(name string) string {
	if cfg.Var != nil {
	if t := cfg.Var[name]; t != "" {
	return t
	}
	}
	if cfg.Func != nil {
	if t := cfg.Func[name]; t != "" {
	return "func()" + t
	}
	}
	return ""
	}

	// Type describes the Fields and Methods of a type.
	// If the field or method cannot be found there, it is next
	// looked for in the Embed list.
	type Type struct {
	Field map[string]string // map field name to type
	Method map[string]string // map method name to comma-separated return types
	Embed []string // list of types this type embeds (for extra methods)
	}

	// dot returns the type of "typ.name", making its decision
	// using the type information in cfg.
	func (typ Type) dot(cfg TypeConfig, name string) string {
	if typ.Field != nil {
	if t := typ.Field[name]; t != "" {
	return t
	}
	}
	if typ.Method != nil {
	if t := typ.Method[name]; t != "" {
	return t
	}
	}

	for _, e := range typ.Embed {
	etyp := cfg.Type[e]
	if etyp != nil {
	if t := etyp.dot(cfg, name); t != "" {
	return t
	}
	}
	}

	return ""
	}

	// typecheck type checks the AST f assuming the information in cfg.
	// It returns a map from AST nodes to type information in gofmt string form.
	func typecheck(cfg TypeConfig, f ast.File) map[interface{}]string {
	typeof := make(map[interface{}]string)

	// gather function declarations
	for _, decl := range f.Decls {
	fn, ok := decl.(*ast.FuncDecl)
	if !ok {
	continue
	}
	typecheck1(cfg, fn.Type, typeof)
	t := typeof[fn.Type]
	if fn.Recv != nil {
	// The receiver must be a type.
	rcvr := typeof[fn.Recv]
	if !isType(rcvr) {
	if len(fn.Recv.List) != 1 {
	continue
	}
	rcvr = mkType(gofmt(fn.Recv.List[0].Type))
	typeof[fn.Recv.List[0].Type] = rcvr
	}
	rcvr = getType(rcvr)
	if rcvr != "" && rcvr[0] == '*' {
	rcvr = rcvr[1:]
	}
	typeof[rcvr+"."+fn.Name.Name] = t
	} else {
	if isType(t) {
	t = getType(t)
	} else {
	t = gofmt(fn.Type)
	}
	typeof[fn.Name] = t

	// Record typeof[fn.Name.Obj] for future references to fn.Name.
	typeof[fn.Name.Obj] = t
	}
	}

	typecheck1(cfg, f, typeof)
	return typeof
	}

	func makeExprList(a []*ast.Ident) []ast.Expr {
	var b []ast.Expr
	for _, x := range a {
	b = append(b, x)
	}
	return b
	}

	// Typecheck1 is the recursive form of typecheck.
	// It is like typecheck but adds to the information in typeof
	// instead of allocating a new map.
	func typecheck1(cfg *TypeConfig, f interface{}, typeof map[interface{}]string) {
	// set sets the type of n to typ.
	// If isDecl is true, n is being declared.
	set := func(n ast.Expr, typ string, isDecl bool) {
	if typeof[n] != "" \|\| typ == "" {
	return
	}
	typeof[n] = typ

	// If we obtained typ from the declaration of x
	// propagate the type to all the uses.
	// The !isDecl case is a cheat here, but it makes
	// up in some cases for not paying attention to
	// struct fields. The real type checker will be
	// more accurate so we won't need the cheat.
	if id, ok := n.(*ast.Ident); ok && id.Obj != nil && (isDecl \|\| typeof[id.Obj] == "") {
	typeof[id.Obj] = typ
	}
	}

	// Type-check an assignment lhs = rhs.
	// If isDecl is true, this is := so we can update
	// the types of the objects that lhs refers to.
	typecheckAssign := func(lhs, rhs []ast.Expr, isDecl bool) {
	if len(lhs) > 1 && len(rhs) == 1 {
	if _, ok := rhs[0].(*ast.CallExpr); ok {
	t := split(typeof[rhs[0]])
	// Lists should have same length but may not; pair what can be paired.
	for i := 0; i < len(lhs) && i < len(t); i++ {
	set(lhs[i], t[i], isDecl)
	}
	return
	}
	}
	if len(lhs) == 1 && len(rhs) == 2 {
	// x = y, ok
	rhs = rhs[:1]
	} else if len(lhs) == 2 && len(rhs) == 1 {
	// x, ok = y
	lhs = lhs[:1]
	}

	// Match as much as we can.
	for i := 0; i < len(lhs) && i < len(rhs); i++ {
	x, y := lhs[i], rhs[i]
	if typeof[y] != "" {
	set(x, typeof[y], isDecl)
	} else {
	set(y, typeof[x], false)
	}
	}
	}

	// The main type check is a recursive algorithm implemented
	// by walkBeforeAfter(n, before, after).
	// Most of it is bottom-up, but in a few places we need
	// to know the type of the function we are checking.
	// The before function records that information on
	// the curfn stack.
	var curfn []*ast.FuncType

	before := func(n interface{}) {
	// push function type on stack
	switch n := n.(type) {
	case *ast.FuncDecl:
	curfn = append(curfn, n.Type)
	case *ast.FuncLit:
	curfn = append(curfn, n.Type)
	}
	}

	// After is the real type checker.
	after := func(n interface{}) {
	if n == nil {
	return
	}
	if false && reflect.TypeOf(n).Kind() == reflect.Ptr { // debugging trace
	defer func() {
	if t := typeof[n]; t != "" {
	pos := fset.Position(n.(ast.Node).Pos())
	fmt.Fprintf(os.Stderr, "%s: typeof[%s] = %s\n", pos.String(), gofmt(n), t)
	}
	}()
	}

	switch n := n.(type) {
	case ast.FuncDecl, ast.FuncLit:
	// pop function type off stack
	curfn = curfn[:len(curfn)-1]

	case *ast.FuncType:
	typeof[n] = mkType(joinFunc(split(typeof[n.Params]), split(typeof[n.Results])))

	case *ast.FieldList:
	// Field list is concatenation of sub-lists.
	t := ""
	for _, field := range n.List {
	if t != "" {
	t += ", "
	}
	t += typeof[field]
	}
	typeof[n] = t

	case *ast.Field:
	// Field is one instance of the type per name.
	all := ""
	t := typeof[n.Type]
	if !isType(t) {
	// Create a type, because it is typically T or p.T
	// and we might care about that type.
	t = mkType(gofmt(n.Type))
	typeof[n.Type] = t
	}
	t = getType(t)
	if len(n.Names) == 0 {
	all = t
	} else {
	for _, id := range n.Names {
	if all != "" {
	all += ", "
	}
	all += t
	typeof[id.Obj] = t
	typeof[id] = t
	}
	}
	typeof[n] = all

	case *ast.ValueSpec:
	// var declaration. Use type if present.
	if n.Type != nil {
	t := typeof[n.Type]
	if !isType(t) {
	t = mkType(gofmt(n.Type))
	typeof[n.Type] = t
	}
	t = getType(t)
	for _, id := range n.Names {
	set(id, t, true)
	}
	}
	// Now treat same as assignment.
	typecheckAssign(makeExprList(n.Names), n.Values, true)

	case *ast.AssignStmt:
	typecheckAssign(n.Lhs, n.Rhs, n.Tok == token.DEFINE)

	case *ast.Ident:
	// Identifier can take its type from underlying object.
	if t := typeof[n.Obj]; t != "" {
	typeof[n] = t
	}

	case *ast.SelectorExpr:
	// Field or method.
	name := n.Sel.Name
	if t := typeof[n.X]; t != "" {
	if strings.HasPrefix(t, "*") {
	t = t[1:] // implicit *
	}
	if typ := cfg.Type[t]; typ != nil {
	if t := typ.dot(cfg, name); t != "" {
	typeof[n] = t
	return
	}
	}
	tt := typeof[t+"."+name]
	if isType(tt) {
	typeof[n] = getType(tt)
	return
	}
	}
	// Package selector.
	if x, ok := n.X.(*ast.Ident); ok && x.Obj == nil {
	str := x.Name + "." + name
	if cfg.Type[str] != nil {
	typeof[n] = mkType(str)
	return
	}
	if t := cfg.typeof(x.Name + "." + name); t != "" {
	typeof[n] = t
	return
	}
	}

	case *ast.CallExpr:
	// make(T) has type T.
	if isTopName(n.Fun, "make") && len(n.Args) >= 1 {
	typeof[n] = gofmt(n.Args[0])
	return
	}
	// new(T) has type *T
	if isTopName(n.Fun, "new") && len(n.Args) == 1 {
	typeof[n] = "*" + gofmt(n.Args[0])
	return
	}
	// Otherwise, use type of function to determine arguments.
	t := typeof[n.Fun]
	in, out := splitFunc(t)
	if in == nil && out == nil {
	return
	}
	typeof[n] = join(out)
	for i, arg := range n.Args {
	if i >= len(in) {
	break
	}
	if typeof[arg] == "" {
	typeof[arg] = in[i]
	}
	}

	case *ast.TypeAssertExpr:
	// x.(type) has type of x.
	if n.Type == nil {
	typeof[n] = typeof[n.X]
	return
	}
	// x.(T) has type T.
	if t := typeof[n.Type]; isType(t) {
	typeof[n] = getType(t)
	}

	case *ast.SliceExpr:
	// x[i:j] has type of x.
	typeof[n] = typeof[n.X]

	case *ast.IndexExpr:
	// x[i] has key type of x's type.
	t := typeof[n.X]
	if strings.HasPrefix(t, "[") \|\| strings.HasPrefix(t, "map[") {
	// Lazy: assume there are no nested [] in the array
	// length or map key type.
	if i := strings.Index(t, "]"); i >= 0 {
	typeof[n] = t[i+1:]
	}
	}

	case *ast.StarExpr:
	// x for x of type T has type T when x is an expr.
	// We don't use the result when *x is a type, but
	// compute it anyway.
	t := typeof[n.X]
	if isType(t) {
	typeof[n] = "type *" + getType(t)
	} else if strings.HasPrefix(t, "*") {
	typeof[n] = t[len("*"):]
	}

	case *ast.UnaryExpr:
	// &x for x of type T has type *T.
	t := typeof[n.X]
	if t != "" && n.Op == token.AND {
	typeof[n] = "&" + t
	}

	case *ast.CompositeLit:
	// T{...} has type T.
	typeof[n] = gofmt(n.Type)

	case *ast.ParenExpr:
	// (x) has type of x.
	typeof[n] = typeof[n.X]

	case *ast.TypeSwitchStmt:
	// Type of variable changes for each case in type switch,
	// but go/parser generates just one variable.
	// Repeat type check for each case with more precise
	// type information.
	as, ok := n.Assign.(*ast.AssignStmt)
	if !ok {
	return
	}
	varx, ok := as.Lhs[0].(*ast.Ident)
	if !ok {
	return
	}
	t := typeof[varx]
	for _, cas := range n.Body.List {
	cas := cas.(*ast.CaseClause)
	if len(cas.List) == 1 {
	// Variable has specific type only when there is
	// exactly one type in the case list.
	if tt := typeof[cas.List[0]]; isType(tt) {
	tt = getType(tt)
	typeof[varx] = tt
	typeof[varx.Obj] = tt
	typecheck1(cfg, cas.Body, typeof)
	}
	}
	}
	// Restore t.
	typeof[varx] = t
	typeof[varx.Obj] = t

	case *ast.ReturnStmt:
	if len(curfn) == 0 {
	// Probably can't happen.
	return
	}
	f := curfn[len(curfn)-1]
	res := n.Results
	if f.Results != nil {
	t := split(typeof[f.Results])
	for i := 0; i < len(res) && i < len(t); i++ {
	set(res[i], t[i], false)
	}
	}
	}
	}
	walkBeforeAfter(f, before, after)
	}

	// Convert between function type strings and lists of types.
	// Using strings makes this a little harder, but it makes
	// a lot of the rest of the code easier. This will all go away
	// when we can use go/typechecker directly.

	// splitFunc splits "func(x,y,z) (a,b,c)" into ["x", "y", "z"] and ["a", "b", "c"].
	func splitFunc(s string) (in, out []string) {
	if !strings.HasPrefix(s, "func(") {
	return nil, nil
	}

	i := len("func(") // index of beginning of 'in' arguments
	nparen := 0
	for j := i; j < len(s); j++ {
	switch s[j] {
	case '(':
	nparen++
	case ')':
	nparen--
	if nparen < 0 {
	// found end of parameter list
	out := strings.TrimSpace(s[j+1:])
	if len(out) >= 2 && out[0] == '(' && out[len(out)-1] == ')' {
	out = out[1 : len(out)-1]
	}
	return split(s[i:j]), split(out)
	}
	}
	}
	return nil, nil
	}

	// joinFunc is the inverse of splitFunc.
	func joinFunc(in, out []string) string {
	outs := ""
	if len(out) == 1 {
	outs = " " + out[0]
	} else if len(out) > 1 {
	outs = " (" + join(out) + ")"
	}
	return "func(" + join(in) + ")" + outs
	}

	// split splits "int, float" into ["int", "float"] and splits "" into [].
	func split(s string) []string {
	out := []string{}
	i := 0 // current type being scanned is s[i:j].
	nparen := 0
	for j := 0; j < len(s); j++ {
	switch s[j] {
	case ' ':
	if i == j {
	i++
	}
	case '(':
	nparen++
	case ')':
	nparen--
	if nparen < 0 {
	// probably can't happen
	return nil
	}
	case ',':
	if nparen == 0 {
	if i < j {
	out = append(out, s[i:j])
	}
	i = j + 1
	}
	}
	}
	if nparen != 0 {
	// probably can't happen
	return nil
	}
	if i < len(s) {
	out = append(out, s[i:])
	}
	return out
	}

	// join is the inverse of split.
	func join(x []string) string {
	return strings.Join(x, ", ")
	}