go/ast: implemented NewPackage

NewPackage creates an ast.Package node from
a set of package files and resolves unresolved
identifiers.

Also:
- Changed semantics of Scope.Insert: If an
  object is inserted w/o errors, the result
  is nil (before it was obj).
- Fixed an identifier resolution bug in the
  parser: map keys must not be resolved.

gotype runs through several go/* packages
and successfully resolves all (non-field/method)
identifiers.

R=rog, rsc
CC=golang-dev
https://golang.org/cl/4298044

12 files changed, 321 insertions, 44 deletions

diff --git a/src/cmd/gotype/gotype.go b/src/cmd/gotype/gotype.go
index 0d57c18a65..5fa9e28592 100644
--- a/src/cmd/gotype/gotype.go
+++ b/src/cmd/gotype/gotype.go
@@ -165,22 +165,24 @@ func processFiles(filenames []string, allFiles bool) {
 			}
 		}
 	}
-	processPackage(parseFiles(token.NewFileSet(), filenames[0:i]))
+	fset := token.NewFileSet()
+	processPackage(fset, parseFiles(fset, filenames[0:i]))
 }
 
 
-func processPackage(files map[string]*ast.File) {
-	// TODO(gri) Enable this code once we have ast.NewPackage.
-	/*
-		// make a package (resolve all identifiers)
-		pkg, err := ast.NewPackage(files)
-		if err != nil {
-			report(err)
-			return
-		}
-		// TODO(gri): typecheck package
-		_ = pkg
-	*/
+// TODO(gri) Replace this with a fully functioning importer.
+//           For now a dummy importer is set up by gotype_test.go.
+var importer ast.Importer
+
+func processPackage(fset *token.FileSet, files map[string]*ast.File) {
+	// make a package (resolve all identifiers)
+	pkg, err := ast.NewPackage(fset, files, importer, universe)
+	if err != nil {
+		report(err)
+		return
+	}
+	// TODO(gri): typecheck package
+	_ = pkg
 }
 
 
@@ -189,10 +191,74 @@ func main() {
 	flag.Parse()
 
 	if flag.NArg() == 0 {
-		processPackage(parseStdin(token.NewFileSet()))
+		fset := token.NewFileSet()
+		processPackage(fset, parseStdin(fset))
 	} else {
 		processFiles(flag.Args(), true)
 	}
 
 	os.Exit(exitCode)
 }
+
+
+// TODO(gri) Move universe and its initialization in to the right package.
+var universe *ast.Scope
+
+func define(kind ast.ObjKind, names ...string) {
+	for _, name := range names {
+		obj := ast.NewObj(kind, name)
+		if universe.Insert(obj) != nil {
+			panic("gotype internal error: incorrect universe scope")
+		}
+	}
+}
+
+
+func init() {
+	universe = ast.NewScope(nil)
+
+	define(ast.Typ,
+		"bool",
+		"byte",
+		"complex64",
+		"complex128",
+		"float32",
+		"float64",
+		"int8",
+		"int16",
+		"int32",
+		"int64",
+		"string",
+		"uint8",
+		"uint16",
+		"uint32",
+		"uint64",
+		"int",
+		"uint",
+		"uintptr",
+	)
+
+	define(ast.Con,
+		"true",
+		"false",
+		"iota",
+		"nil",
+	)
+
+	define(ast.Fun,
+		"append",
+		"cap",
+		"close",
+		"complex",
+		"copy",
+		"imag",
+		"len",
+		"make",
+		"new",
+		"panic",
+		"print",
+		"println",
+		"real",
+		"recover",
+	)
+}
diff --git a/src/cmd/gotype/gotype_test.go b/src/cmd/gotype/gotype_test.go
index ddd958c9aa..96f54ea419 100644
--- a/src/cmd/gotype/gotype_test.go
+++ b/src/cmd/gotype/gotype_test.go
@@ -5,25 +5,36 @@
 package main
 
 import (
+	"go/ast"
+	"os"
 	"path/filepath"
 	"runtime"
+	"path"
 	"testing"
 )
 
 
+func testImporter(importPath string) (string, *ast.Scope, os.Error) {
+	_, pkgName := path.Split(importPath) // filename is package name for std library
+	return pkgName, ast.NewScope(nil), nil
+}
+
+
 func testDir(t *testing.T, dir, pkg string) {
+	exitCode = 0
 	*pkgName = pkg
 	*recursive = false
+	importer = testImporter
 	processDirectory(dir)
 	if exitCode != 0 {
-		t.Errorf("processing %d failed: exitCode = %d", dir, exitCode)
+		t.Errorf("processing %s failed: exitCode = %d", dir, exitCode)
 	}
 }
 
 
 func Test(t *testing.T) {
-	testDir(t, ".", "main")
 	testDir(t, filepath.Join(runtime.GOROOT(), "src/pkg/go/ast"), "ast")
+	testDir(t, filepath.Join(runtime.GOROOT(), "src/pkg/go/token"), "scanner")
 	testDir(t, filepath.Join(runtime.GOROOT(), "src/pkg/go/scanner"), "scanner")
 	testDir(t, filepath.Join(runtime.GOROOT(), "src/pkg/go/parser"), "parser")
 }
diff --git a/src/pkg/go/ast/Makefile b/src/pkg/go/ast/Makefile
index e9b885c705..40be10208b 100644
--- a/src/pkg/go/ast/Makefile
+++ b/src/pkg/go/ast/Makefile
@@ -9,6 +9,7 @@ GOFILES=\
 	ast.go\
 	filter.go\
 	print.go\
+	resolve.go\
 	scope.go\
 	walk.go\
 
diff --git a/src/pkg/go/ast/ast.go b/src/pkg/go/ast/ast.go
index 4a4c12b7c0..2023002e2d 100644
--- a/src/pkg/go/ast/ast.go
+++ b/src/pkg/go/ast/ast.go
@@ -781,7 +781,7 @@ type (
 	ImportSpec struct {
 		Doc     *CommentGroup // associated documentation; or nil
 		Name    *Ident        // local package name (including "."); or nil
-		Path    *BasicLit     // package path
+		Path    *BasicLit     // import path
 		Comment *CommentGroup // line comments; or nil
 	}
 
@@ -925,8 +925,9 @@ type File struct {
 	Package    token.Pos       // position of "package" keyword
 	Name       *Ident          // package name
 	Decls      []Decl          // top-level declarations; or nil
-	Scope      *Scope          // package scope
-	Unresolved []*Ident        // unresolved global identifiers
+	Scope      *Scope          // package scope (this file only)
+	Imports    []*ImportSpec   // imports in this file
+	Unresolved []*Ident        // unresolved identifiers in this file
 	Comments   []*CommentGroup // list of all comments in the source file
 }
 
@@ -944,9 +945,10 @@ func (f *File) End() token.Pos {
 // collectively building a Go package.
 //
 type Package struct {
-	Name  string           // package name
-	Scope *Scope           // package scope
-	Files map[string]*File // Go source files by filename
+	Name    string            // package name
+	Scope   *Scope            // package scope
+	Imports map[string]*Scope // map of import path -> package scope across all files
+	Files   map[string]*File  // Go source files by filename
 }
 
 
diff --git a/src/pkg/go/ast/filter.go b/src/pkg/go/ast/filter.go
index 4da487ce02..f010bb9359 100644
--- a/src/pkg/go/ast/filter.go
+++ b/src/pkg/go/ast/filter.go
@@ -426,5 +426,6 @@ func MergePackageFiles(pkg *Package, mode MergeMode) *File {
 	}
 
 	// TODO(gri) need to compute pkgScope and unresolved identifiers!
-	return &File{doc, pos, NewIdent(pkg.Name), decls, nil, nil, comments}
+	// TODO(gri) need to compute imports!
+	return &File{doc, pos, NewIdent(pkg.Name), decls, nil, nil, nil, comments}
 }
diff --git a/src/pkg/go/ast/resolve.go b/src/pkg/go/ast/resolve.go
new file mode 100644
index 0000000000..fddc3baab8
--- /dev/null
+++ b/src/pkg/go/ast/resolve.go
@@ -0,0 +1,188 @@
+// 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.
+
+// This file implements NewPackage.
+
+package ast
+
+import (
+	"fmt"
+	"go/scanner"
+	"go/token"
+	"os"
+)
+
+
+type pkgBuilder struct {
+	scanner.ErrorVector
+	fset *token.FileSet
+}
+
+
+func (p *pkgBuilder) error(pos token.Pos, msg string) {
+	p.Error(p.fset.Position(pos), msg)
+}
+
+
+func (p *pkgBuilder) errorf(pos token.Pos, format string, args ...interface{}) {
+	p.error(pos, fmt.Sprintf(format, args...))
+}
+
+
+func (p *pkgBuilder) declare(scope, altScope *Scope, obj *Object) {
+	alt := scope.Insert(obj)
+	if alt == nil && altScope != nil {
+		// see if there is a conflicting declaration in altScope
+		alt = altScope.Lookup(obj.Name)
+	}
+	if alt != nil {
+		prevDecl := ""
+		if pos := alt.Pos(); pos.IsValid() {
+			prevDecl = fmt.Sprintf("\n\tprevious declaration at %s", p.fset.Position(pos))
+		}
+		p.error(obj.Pos(), fmt.Sprintf("%s redeclared in this block%s", obj.Name, prevDecl))
+	}
+}
+
+
+func resolve(scope *Scope, ident *Ident) bool {
+	for ; scope != nil; scope = scope.Outer {
+		if obj := scope.Lookup(ident.Name); obj != nil {
+			ident.Obj = obj
+			return true
+		}
+	}
+	return false
+}
+
+
+// NewPackage uses an Importer to resolve imports. Given an importPath,
+// an importer returns the imported package's name, its scope of exported
+// objects, and an error, if any.
+//
+type Importer func(path string) (name string, scope *Scope, err os.Error)
+
+
+// NewPackage creates a new Package node from a set of File nodes. It resolves
+// unresolved identifiers across files and updates each file's Unresolved list
+// accordingly. If a non-nil importer and universe scope are provided, they are
+// used to resolve identifiers not declared in any of the package files. Any
+// remaining unresolved identifiers are reported as undeclared. If the files
+// belong to different packages, one package name is selected and files with
+// different package name are reported and then ignored.
+// The result is a package node and a scanner.ErrorList if there were errors.
+//
+func NewPackage(fset *token.FileSet, files map[string]*File, importer Importer, universe *Scope) (*Package, os.Error) {
+	var p pkgBuilder
+	p.fset = fset
+
+	// complete package scope
+	pkgName := ""
+	pkgScope := NewScope(universe)
+	for _, file := range files {
+		// package names must match
+		switch name := file.Name.Name; {
+		case pkgName == "":
+			pkgName = name
+		case name != pkgName:
+			p.errorf(file.Package, "package %s; expected %s", name, pkgName)
+			continue // ignore this file
+		}
+
+		// collect top-level file objects in package scope
+		for _, obj := range file.Scope.Objects {
+			p.declare(pkgScope, nil, obj)
+		}
+	}
+
+	// imports maps import paths to package names and scopes
+	// TODO(gri): Eventually we like to get to the import scope from
+	//            a package object. Then we can have a map path -> Obj.
+	type importedPkg struct {
+		name  string
+		scope *Scope
+	}
+	imports := make(map[string]*importedPkg)
+
+	// complete file scopes with imports and resolve identifiers
+	for _, file := range files {
+		// ignore file if it belongs to a different package
+		// (error has already been reported)
+		if file.Name.Name != pkgName {
+			continue
+		}
+
+		// build file scope by processing all imports
+		importErrors := false
+		fileScope := NewScope(pkgScope)
+		for _, spec := range file.Imports {
+			// add import to global map of imports
+			path := string(spec.Path.Value)
+			path = path[1 : len(path)-1] // strip ""'s
+			pkg := imports[path]
+			if pkg == nil {
+				if importer == nil {
+					importErrors = true
+					continue
+				}
+				name, scope, err := importer(path)
+				if err != nil {
+					p.errorf(spec.Path.Pos(), "could not import %s (%s)", path, err)
+					importErrors = true
+					continue
+				}
+				pkg = &importedPkg{name, scope}
+				imports[path] = pkg
+				// TODO(gri) If a local package name != "." is provided,
+				// global identifier resolution could proceed even if the
+				// import failed. Consider adjusting the logic here a bit.
+			}
+			// local name overrides imported package name
+			name := pkg.name
+			if spec.Name != nil {
+				name = spec.Name.Name
+			}
+			// add import to file scope
+			if name == "." {
+				// merge imported scope with file scope
+				for _, obj := range pkg.scope.Objects {
+					p.declare(fileScope, pkgScope, obj)
+				}
+			} else {
+				// declare imported package object in file scope
+				obj := NewObj(Pkg, name)
+				obj.Decl = spec
+				p.declare(fileScope, pkgScope, obj)
+			}
+		}
+
+		// resolve identifiers
+		if importErrors {
+			// don't use the universe scope without correct imports
+			// (objects in the universe may be shadowed by imports;
+			// with missing imports identifiers might get resolved
+			// wrongly)
+			pkgScope.Outer = nil
+		}
+		i := 0
+		for _, ident := range file.Unresolved {
+			if !resolve(fileScope, ident) {
+				p.errorf(ident.Pos(), "undeclared name: %s", ident.Name)
+				file.Unresolved[i] = ident
+				i++
+			}
+
+		}
+		file.Unresolved = file.Unresolved[0:i]
+		pkgScope.Outer = universe // reset universe scope
+	}
+
+	// collect all import paths and respective package scopes
+	importedScopes := make(map[string]*Scope)
+	for path, pkg := range imports {
+		importedScopes[path] = pkg.scope
+	}
+
+	return &Package{pkgName, pkgScope, importedScopes, files}, p.GetError(scanner.Sorted)
+}
diff --git a/src/pkg/go/ast/scope.go b/src/pkg/go/ast/scope.go
index 91866dcf57..830d88aef4 100644
--- a/src/pkg/go/ast/scope.go
+++ b/src/pkg/go/ast/scope.go
@@ -39,16 +39,14 @@ func (s *Scope) Lookup(name string) *Object {
 }
 
 
-// Insert attempts to insert a named object into the scope s.
-// If the scope does not contain an object with that name yet,
-// Insert inserts the object and returns it. Otherwise, Insert
-// leaves the scope unchanged and returns the object found in
-// the scope instead.
+// Insert attempts to insert a named object obj into the scope s.
+// If the scope already contains an object alt with the same name,
+// Insert leaves the scope unchanged and returns alt. Otherwise
+// it inserts obj and returns nil."
 //
 func (s *Scope) Insert(obj *Object) (alt *Object) {
 	if alt = s.Objects[obj.Name]; alt == nil {
 		s.Objects[obj.Name] = obj
-		alt = obj
 	}
 	return
 }
@@ -101,6 +99,11 @@ func (obj *Object) Pos() token.Pos {
 				return n.Pos()
 			}
 		}
+	case *ImportSpec:
+		if d.Name != nil && d.Name.Name == name {
+			return d.Name.Pos()
+		}
+		return d.Path.Pos()
 	case *ValueSpec:
 		for _, n := range d.Names {
 			if n.Name == name {
diff --git a/src/pkg/go/parser/interface.go b/src/pkg/go/parser/interface.go
index cca251b81f..fc4ae09439 100644
--- a/src/pkg/go/parser/interface.go
+++ b/src/pkg/go/parser/interface.go
@@ -159,7 +159,8 @@ func ParseFiles(fset *token.FileSet, filenames []string, mode uint) (pkgs map[st
 			name := src.Name.Name
 			pkg, found := pkgs[name]
 			if !found {
-				pkg = &ast.Package{name, nil, make(map[string]*ast.File)}
+				// TODO(gri) Use NewPackage here; reconsider ParseFiles API.
+				pkg = &ast.Package{name, nil, nil, make(map[string]*ast.File)}
 				pkgs[name] = pkg
 			}
 			pkg.Files[filename] = src
diff --git a/src/pkg/go/parser/parser.go b/src/pkg/go/parser/parser.go
index d2916d93a2..e5eec6f98c 100644
--- a/src/pkg/go/parser/parser.go
+++ b/src/pkg/go/parser/parser.go
@@ -148,8 +148,7 @@ func (p *parser) declare(decl interface{}, scope *ast.Scope, kind ast.ObjKind, i
 			// remember the corresponding declaration for redeclaration
 			// errors and global variable resolution/typechecking phase
 			obj.Decl = decl
-			alt := scope.Insert(obj)
-			if alt != obj && p.mode&DeclarationErrors != 0 {
+			if alt := scope.Insert(obj); alt != nil && p.mode&DeclarationErrors != 0 {
 				prevDecl := ""
 				if pos := alt.Pos(); pos.IsValid() {
 					prevDecl = fmt.Sprintf("\n\tprevious declaration at %s", p.file.Position(pos))
@@ -175,8 +174,9 @@ func (p *parser) shortVarDecl(idents []*ast.Ident) {
 			// and are not global => no need to remember the respective
 			// declaration
 			alt := p.topScope.Insert(obj)
-			if alt == obj {
+			if alt == nil {
 				n++ // new declaration
+				alt = obj
 			}
 			ident.Obj = alt
 		}
@@ -1151,12 +1151,16 @@ func (p *parser) parseElement(keyOk bool) ast.Expr {
 		return p.parseLiteralValue(nil)
 	}
 
-	x := p.parseRhs()
-	if keyOk && p.tok == token.COLON {
-		colon := p.pos
-		p.next()
-		x = &ast.KeyValueExpr{x, colon, p.parseElement(false)}
+	x := p.parseExpr(keyOk) // don't resolve if map key
+	if keyOk {
+		if p.tok == token.COLON {
+			colon := p.pos
+			p.next()
+			return &ast.KeyValueExpr{x, colon, p.parseElement(false)}
+		}
+		p.resolve(x) // not a map key
 	}
+
 	return x
 }
 
@@ -2247,5 +2251,5 @@ func (p *parser) parseFile() *ast.File {
 	}
 
 	// TODO(gri): store p.imports in AST
-	return &ast.File{doc, pos, ident, decls, p.pkgScope, p.unresolved[0:i], p.comments}
+	return &ast.File{doc, pos, ident, decls, p.pkgScope, p.imports, p.unresolved[0:i], p.comments}
 }
diff --git a/src/pkg/go/typechecker/scope.go b/src/pkg/go/typechecker/scope.go
index bd24f4ca42..a4bee6e696 100644
--- a/src/pkg/go/typechecker/scope.go
+++ b/src/pkg/go/typechecker/scope.go
@@ -33,7 +33,7 @@ func (tc *typechecker) declInScope(scope *ast.Scope, kind ast.ObjKind, name *ast
 	//obj.N = n
 	name.Obj = obj
 	if name.Name != "_" {
-		if alt := scope.Insert(obj); alt != obj {
+		if alt := scope.Insert(obj); alt != nil {
 			tc.Errorf(name.Pos(), "%s already declared at %s", name.Name, tc.fset.Position(alt.Pos()).String())
 		}
 	}
diff --git a/src/pkg/go/typechecker/typechecker.go b/src/pkg/go/typechecker/typechecker.go
index 4fc5647f0d..b5e695d973 100644
--- a/src/pkg/go/typechecker/typechecker.go
+++ b/src/pkg/go/typechecker/typechecker.go
@@ -53,7 +53,7 @@ func CheckPackage(fset *token.FileSet, pkg *ast.Package, importer Importer) os.E
 //
 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}}
+	pkg := &ast.Package{file.Name.Name, nil, nil, map[string]*ast.File{fset.Position(file.Name.NamePos).Filename: file}}
 	return CheckPackage(fset, pkg, importer)
 }
 
@@ -327,8 +327,8 @@ func (tc *typechecker) checkBlock(body []ast.Stmt, ftype *Type) {
 	if ftype != nil {
 		for _, par := range ftype.Params.Objects {
 			if par.Name != "_" {
-				obj := tc.topScope.Insert(par)
-				assert(obj == par) // ftype has no double declarations
+				alt := tc.topScope.Insert(par)
+				assert(alt == nil) // ftype has no double declarations
 			}
 		}
 	}
diff --git a/src/pkg/go/typechecker/universe.go b/src/pkg/go/typechecker/universe.go
index cf4434993e..abc8bbbd49 100644
--- a/src/pkg/go/typechecker/universe.go
+++ b/src/pkg/go/typechecker/universe.go
@@ -14,7 +14,7 @@ var Universe *ast.Scope
 
 func def(obj *ast.Object) {
 	alt := Universe.Insert(obj)
-	if alt != obj {
+	if alt != nil {
 		panic("object declared twice")
 	}
 }