diff options
Diffstat (limited to 'libgo/go/go/typechecker/typechecker.go')
-rw-r--r-- | libgo/go/go/typechecker/typechecker.go | 484 |
1 files changed, 484 insertions, 0 deletions
diff --git a/libgo/go/go/typechecker/typechecker.go b/libgo/go/go/typechecker/typechecker.go new file mode 100644 index 000000000..e9aefa240 --- /dev/null +++ b/libgo/go/go/typechecker/typechecker.go @@ -0,0 +1,484 @@ +// Copyright 2010 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. + +// INCOMPLETE PACKAGE. +// This package implements typechecking of a Go AST. +// The result of the typecheck is an augmented AST +// with object and type information for each identifier. +// +package typechecker + +import ( + "fmt" + "go/ast" + "go/token" + "go/scanner" + "os" +) + + +// TODO(gri) don't report errors for objects/types that are marked as bad. + + +const debug = true // set for debugging output + + +// An importer takes an import path and returns the data describing the +// respective package's exported interface. The data format is TBD. +// +type Importer func(path string) ([]byte, os.Error) + + +// CheckPackage typechecks a package and augments the AST by setting +// *ast.Object, *ast.Type, and *ast.Scope fields accordingly. If an +// importer is provided, it is used to handle imports, otherwise they +// are ignored (likely leading to typechecking errors). +// +// If errors are reported, the AST may be incompletely augmented (fields +// may be nil) or contain incomplete object, type, or scope information. +// +func CheckPackage(fset *token.FileSet, pkg *ast.Package, importer Importer) os.Error { + var tc typechecker + tc.fset = fset + tc.importer = importer + tc.checkPackage(pkg) + return tc.GetError(scanner.Sorted) +} + + +// CheckFile typechecks a single file, but otherwise behaves like +// CheckPackage. If the complete package consists of more than just +// one file, the file may not typecheck without errors. +// +func CheckFile(fset *token.FileSet, file *ast.File, importer Importer) os.Error { + // create a single-file dummy package + pkg := &ast.Package{file.Name.Name, nil, map[string]*ast.File{fset.Position(file.Name.NamePos).Filename: file}} + return CheckPackage(fset, pkg, importer) +} + + +// ---------------------------------------------------------------------------- +// Typechecker state + +type typechecker struct { + fset *token.FileSet + scanner.ErrorVector + importer Importer + topScope *ast.Scope // current top-most scope + cyclemap map[*ast.Object]bool // for cycle detection + iota int // current value of iota +} + + +func (tc *typechecker) Errorf(pos token.Pos, format string, args ...interface{}) { + tc.Error(tc.fset.Position(pos), fmt.Sprintf(format, args...)) +} + + +func assert(pred bool) { + if !pred { + panic("internal error") + } +} + + +/* +Typechecking is done in several phases: + +phase 1: declare all global objects; also collect all function and method declarations + - all objects have kind, name, decl fields; the decl field permits + quick lookup of an object's declaration + - constant objects have an iota value + - type objects have unresolved types with empty scopes, all others have nil types + - report global double declarations + +phase 2: bind methods to their receiver base types + - received base types must be declared in the package, thus for + each method a corresponding (unresolved) type must exist + - report method double declarations and errors with base types + +phase 3: resolve all global objects + - sequentially iterate through all objects in the global scope + - resolve types for all unresolved types and assign types to + all attached methods + - assign types to all other objects, possibly by evaluating + constant and initializer expressions + - resolution may recurse; a cyclemap is used to detect cycles + - report global typing errors + +phase 4: sequentially typecheck function and method bodies + - all global objects are declared and have types and values; + all methods have types + - sequentially process statements in each body; any object + referred to must be fully defined at this point + - report local typing errors +*/ + +func (tc *typechecker) checkPackage(pkg *ast.Package) { + // setup package scope + tc.topScope = Universe + tc.openScope() + defer tc.closeScope() + + // TODO(gri) there's no file scope at the moment since we ignore imports + + // phase 1: declare all global objects; also collect all function and method declarations + var funcs []*ast.FuncDecl + for _, file := range pkg.Files { + for _, decl := range file.Decls { + tc.declGlobal(decl) + if f, isFunc := decl.(*ast.FuncDecl); isFunc { + funcs = append(funcs, f) + } + } + } + + // phase 2: bind methods to their receiver base types + for _, m := range funcs { + if m.Recv != nil { + tc.bindMethod(m) + } + } + + // phase 3: resolve all global objects + // (note that objects with _ name are also in the scope) + tc.cyclemap = make(map[*ast.Object]bool) + for _, obj := range tc.topScope.Objects { + tc.resolve(obj) + } + assert(len(tc.cyclemap) == 0) + + // 4: sequentially typecheck function and method bodies + for _, f := range funcs { + tc.checkBlock(f.Body.List, f.Name.Obj.Type) + } + + pkg.Scope = tc.topScope +} + + +func (tc *typechecker) declGlobal(global ast.Decl) { + switch d := global.(type) { + case *ast.BadDecl: + // ignore + + case *ast.GenDecl: + iota := 0 + var prev *ast.ValueSpec + for _, spec := range d.Specs { + switch s := spec.(type) { + case *ast.ImportSpec: + // TODO(gri) imports go into file scope + case *ast.ValueSpec: + switch d.Tok { + case token.CONST: + if s.Values == nil { + // create a new spec with type and values from the previous one + if prev != nil { + s = &ast.ValueSpec{s.Doc, s.Names, prev.Type, prev.Values, s.Comment} + } else { + // TODO(gri) this should probably go into the const decl code + tc.Errorf(s.Pos(), "missing initializer for const %s", s.Names[0].Name) + } + } + for _, name := range s.Names { + tc.decl(ast.Con, name, s, iota) + } + case token.VAR: + for _, name := range s.Names { + tc.decl(ast.Var, name, s, 0) + } + default: + panic("unreachable") + } + prev = s + iota++ + case *ast.TypeSpec: + obj := tc.decl(ast.Typ, s.Name, s, 0) + // give all type objects an unresolved type so + // that we can collect methods in the type scope + typ := ast.NewType(ast.Unresolved) + obj.Type = typ + typ.Obj = obj + default: + panic("unreachable") + } + } + + case *ast.FuncDecl: + if d.Recv == nil { + tc.decl(ast.Fun, d.Name, d, 0) + } + + default: + panic("unreachable") + } +} + + +// If x is of the form *T, deref returns T, otherwise it returns x. +func deref(x ast.Expr) ast.Expr { + if p, isPtr := x.(*ast.StarExpr); isPtr { + x = p.X + } + return x +} + + +func (tc *typechecker) bindMethod(method *ast.FuncDecl) { + // a method is declared in the receiver base type's scope + var scope *ast.Scope + base := deref(method.Recv.List[0].Type) + if name, isIdent := base.(*ast.Ident); isIdent { + // if base is not an *ast.Ident, we had a syntax + // error and the parser reported an error already + obj := tc.topScope.Lookup(name.Name) + if obj == nil { + tc.Errorf(name.Pos(), "invalid receiver: %s is not declared in this package", name.Name) + } else if obj.Kind != ast.Typ { + tc.Errorf(name.Pos(), "invalid receiver: %s is not a type", name.Name) + } else { + typ := obj.Type + assert(typ.Form == ast.Unresolved) + scope = typ.Scope + } + } + if scope == nil { + // no receiver type found; use a dummy scope + // (we still want to type-check the method + // body, so make sure there is a name object + // and type) + // TODO(gri) should we record the scope so + // that we don't lose the receiver for type- + // checking of the method body? + scope = ast.NewScope(nil) + } + tc.declInScope(scope, ast.Fun, method.Name, method, 0) +} + + +func (tc *typechecker) resolve(obj *ast.Object) { + // check for declaration cycles + if tc.cyclemap[obj] { + tc.Errorf(objPos(obj), "illegal cycle in declaration of %s", obj.Name) + obj.Kind = ast.Bad + return + } + tc.cyclemap[obj] = true + defer func() { + tc.cyclemap[obj] = false, false + }() + + // resolve non-type objects + typ := obj.Type + if typ == nil { + switch obj.Kind { + case ast.Bad: + // ignore + + case ast.Con: + tc.declConst(obj) + + case ast.Var: + tc.declVar(obj) + //obj.Type = tc.typeFor(nil, obj.Decl.(*ast.ValueSpec).Type, false) + + case ast.Fun: + obj.Type = ast.NewType(ast.Function) + t := obj.Decl.(*ast.FuncDecl).Type + tc.declSignature(obj.Type, nil, t.Params, t.Results) + + default: + // type objects have non-nil types when resolve is called + if debug { + fmt.Printf("kind = %s\n", obj.Kind) + } + panic("unreachable") + } + return + } + + // resolve type objects + if typ.Form == ast.Unresolved { + tc.typeFor(typ, typ.Obj.Decl.(*ast.TypeSpec).Type, false) + + // provide types for all methods + for _, obj := range typ.Scope.Objects { + if obj.Kind == ast.Fun { + assert(obj.Type == nil) + obj.Type = ast.NewType(ast.Method) + f := obj.Decl.(*ast.FuncDecl) + t := f.Type + tc.declSignature(obj.Type, f.Recv, t.Params, t.Results) + } + } + } +} + + +func (tc *typechecker) checkBlock(body []ast.Stmt, ftype *ast.Type) { + tc.openScope() + defer tc.closeScope() + + // inject function/method parameters into block scope, if any + if ftype != nil { + for _, par := range ftype.Params.Objects { + obj := tc.topScope.Insert(par) + assert(obj == par) // ftype has no double declarations + } + } + + for _, stmt := range body { + tc.checkStmt(stmt) + } +} + + +// ---------------------------------------------------------------------------- +// Types + +// unparen removes parentheses around x, if any. +func unparen(x ast.Expr) ast.Expr { + if ux, hasParens := x.(*ast.ParenExpr); hasParens { + return unparen(ux.X) + } + return x +} + + +func (tc *typechecker) declFields(scope *ast.Scope, fields *ast.FieldList, ref bool) (n uint) { + if fields != nil { + for _, f := range fields.List { + typ := tc.typeFor(nil, f.Type, ref) + for _, name := range f.Names { + fld := tc.declInScope(scope, ast.Var, name, f, 0) + fld.Type = typ + n++ + } + } + } + return n +} + + +func (tc *typechecker) declSignature(typ *ast.Type, recv, params, results *ast.FieldList) { + assert((typ.Form == ast.Method) == (recv != nil)) + typ.Params = ast.NewScope(nil) + tc.declFields(typ.Params, recv, true) + tc.declFields(typ.Params, params, true) + typ.N = tc.declFields(typ.Params, results, true) +} + + +func (tc *typechecker) typeFor(def *ast.Type, x ast.Expr, ref bool) (typ *ast.Type) { + x = unparen(x) + + // type name + if t, isIdent := x.(*ast.Ident); isIdent { + obj := tc.find(t) + + if obj.Kind != ast.Typ { + tc.Errorf(t.Pos(), "%s is not a type", t.Name) + if def == nil { + typ = ast.NewType(ast.BadType) + } else { + typ = def + typ.Form = ast.BadType + } + typ.Expr = x + return + } + + if !ref { + tc.resolve(obj) // check for cycles even if type resolved + } + typ = obj.Type + + if def != nil { + // new type declaration: copy type structure + def.Form = typ.Form + def.N = typ.N + def.Key, def.Elt = typ.Key, typ.Elt + def.Params = typ.Params + def.Expr = x + typ = def + } + return + } + + // type literal + typ = def + if typ == nil { + typ = ast.NewType(ast.BadType) + } + typ.Expr = x + + switch t := x.(type) { + case *ast.SelectorExpr: + if debug { + fmt.Println("qualified identifier unimplemented") + } + typ.Form = ast.BadType + + case *ast.StarExpr: + typ.Form = ast.Pointer + typ.Elt = tc.typeFor(nil, t.X, true) + + case *ast.ArrayType: + if t.Len != nil { + typ.Form = ast.Array + // TODO(gri) compute the real length + // (this may call resolve recursively) + (*typ).N = 42 + } else { + typ.Form = ast.Slice + } + typ.Elt = tc.typeFor(nil, t.Elt, t.Len == nil) + + case *ast.StructType: + typ.Form = ast.Struct + tc.declFields(typ.Scope, t.Fields, false) + + case *ast.FuncType: + typ.Form = ast.Function + tc.declSignature(typ, nil, t.Params, t.Results) + + case *ast.InterfaceType: + typ.Form = ast.Interface + tc.declFields(typ.Scope, t.Methods, true) + + case *ast.MapType: + typ.Form = ast.Map + typ.Key = tc.typeFor(nil, t.Key, true) + typ.Elt = tc.typeFor(nil, t.Value, true) + + case *ast.ChanType: + typ.Form = ast.Channel + typ.N = uint(t.Dir) + typ.Elt = tc.typeFor(nil, t.Value, true) + + default: + if debug { + fmt.Printf("x is %T\n", x) + } + panic("unreachable") + } + + return +} + + +// ---------------------------------------------------------------------------- +// TODO(gri) implement these place holders + +func (tc *typechecker) declConst(*ast.Object) { +} + + +func (tc *typechecker) declVar(*ast.Object) { +} + + +func (tc *typechecker) checkStmt(ast.Stmt) { +} |