diff options
Diffstat (limited to 'vendor/google.golang.org/appengine/cmd/aefix/typecheck.go')
-rw-r--r-- | vendor/google.golang.org/appengine/cmd/aefix/typecheck.go | 673 |
1 files changed, 0 insertions, 673 deletions
diff --git a/vendor/google.golang.org/appengine/cmd/aefix/typecheck.go b/vendor/google.golang.org/appengine/cmd/aefix/typecheck.go deleted file mode 100644 index d54d37547..000000000 --- a/vendor/google.golang.org/appengine/cmd/aefix/typecheck.go +++ /dev/null @@ -1,673 +0,0 @@ -// 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 (should start with "func ") - Embed []string // list of types this type embeds (for extra methods) - Def string // definition of named type -} - -// 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 two maps with type information: -// typeof maps AST nodes to type information in gofmt string form. -// assign maps type strings to lists of expressions that were assigned -// to values of another type that were assigned to that type. -func typecheck(cfg *TypeConfig, f *ast.File) (typeof map[interface{}]string, assign map[string][]interface{}) { - typeof = make(map[interface{}]string) - assign = make(map[string][]interface{}) - cfg1 := &TypeConfig{} - *cfg1 = *cfg // make copy so we can add locally - copied := false - - // gather function declarations - for _, decl := range f.Decls { - fn, ok := decl.(*ast.FuncDecl) - if !ok { - continue - } - typecheck1(cfg, fn.Type, typeof, assign) - 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 - } - } - - // gather struct declarations - for _, decl := range f.Decls { - d, ok := decl.(*ast.GenDecl) - if ok { - for _, s := range d.Specs { - switch s := s.(type) { - case *ast.TypeSpec: - if cfg1.Type[s.Name.Name] != nil { - break - } - if !copied { - copied = true - // Copy map lazily: it's time. - cfg1.Type = make(map[string]*Type) - for k, v := range cfg.Type { - cfg1.Type[k] = v - } - } - t := &Type{Field: map[string]string{}} - cfg1.Type[s.Name.Name] = t - switch st := s.Type.(type) { - case *ast.StructType: - for _, f := range st.Fields.List { - for _, n := range f.Names { - t.Field[n.Name] = gofmt(f.Type) - } - } - case *ast.ArrayType, *ast.StarExpr, *ast.MapType: - t.Def = gofmt(st) - } - } - } - } - } - - typecheck1(cfg1, f, typeof, assign) - return typeof, assign -} - -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, assign map[string][]interface{}) { - // 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 == "" { - if typeof[n] != typ { - assign[typ] = append(assign[typ], n) - } - 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) - } - } - } - - expand := func(s string) string { - typ := cfg.Type[s] - if typ != nil && typ.Def != "" { - return typ.Def - } - return s - } - - // 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, 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) - } else { - typeof[n] = gofmt(n.Type) - } - - 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 := expand(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 := expand(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.RangeStmt: - t := expand(typeof[n.X]) - if t == "" { - return - } - var key, value string - if t == "string" { - key, value = "int", "rune" - } else if strings.HasPrefix(t, "[") { - key = "int" - if i := strings.Index(t, "]"); i >= 0 { - value = t[i+1:] - } - } else if strings.HasPrefix(t, "map[") { - if i := strings.Index(t, "]"); i >= 0 { - key, value = t[4:i], t[i+1:] - } - } - changed := false - if n.Key != nil && key != "" { - changed = true - set(n.Key, key, n.Tok == token.DEFINE) - } - if n.Value != nil && value != "" { - changed = true - set(n.Value, value, n.Tok == token.DEFINE) - } - // Ugly failure of vision: already type-checked body. - // Do it again now that we have that type info. - if changed { - typecheck1(cfg, n.Body, typeof, assign) - } - - 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, assign) - } - } - } - // 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, ", ") -} |