func init() {
	scope = ast.NewScope(nil)
	Universe = scope

	Bool = defType("bool")
	defType("byte") // TODO(gri) should be an alias for uint8
	defType("complex64")
	Complex128 = defType("complex128")
	defType("float32")
	Float64 = defType("float64")
	defType("int8")
	defType("int16")
	defType("int32")
	defType("int64")
	String = defType("string")
	defType("uint8")
	defType("uint16")
	defType("uint32")
	defType("uint64")
	Int = defType("int")
	defType("uint")
	defType("uintptr")

	defConst("true")
	defConst("false")
	defConst("iota")
	defConst("nil")

	defFun("append")
	defFun("cap")
	defFun("close")
	defFun("complex")
	defFun("copy")
	defFun("delete")
	defFun("imag")
	defFun("len")
	defFun("make")
	defFun("new")
	defFun("panic")
	defFun("print")
	defFun("println")
	defFun("real")
	defFun("recover")

	scope = ast.NewScope(nil)
	Unsafe = ast.NewObj(ast.Pkg, "unsafe")
	Unsafe.Data = scope

	defType("Pointer")

	defFun("Alignof")
	defFun("New")
	defFun("NewArray")
	defFun("Offsetof")
	defFun("Reflect")
	defFun("Sizeof")
	defFun("Typeof")
	defFun("Unreflect")
}

// FuncType = "func" Signature .
//
func (p *gcParser) parseFuncType() Type {
	// "func" already consumed
	scope := ast.NewScope(nil)
	isVariadic := false
	p.parseSignature(scope, &isVariadic)
	return &Func{IsVariadic: isVariadic}
}

// ParseFile parses the source code of a single Go source file and returns
// the corresponding ast.File node. The source code may be provided via
// the filename of the source file, or via the src parameter.
//
// If src != nil, ParseFile parses the source from src and the filename is
// only used when recording position information. The type of the argument
// for the src parameter must be string, []byte, or io.Reader.
// If src == nil, ParseFile parses the file specified by filename.
//
// The mode parameter controls the amount of source text parsed and other
// optional parser functionality. Position information is recorded in the
// file set fset.
//
// If the source couldn't be read, the returned AST is nil and the error
// indicates the specific failure. If the source was read but syntax
// errors were found, the result is a partial AST (with ast.Bad* nodes
// representing the fragments of erroneous source code). Multiple errors
// are returned via a scanner.ErrorList which is sorted by file position.
//
func ParseFile(fset *token.FileSet, filename string, src interface{}, mode Mode) (f *ast.File, err error) {
	// get source
	text, err := readSource(filename, src)
	if err != nil {
		return nil, err
	}

	var p parser
	defer func() {
		if e := recover(); e != nil {
			_ = e.(bailout) // re-panics if it's not a bailout
		}

		// set result values
		if f == nil {
			// source is not a valid Go source file - satisfy
			// ParseFile API and return a valid (but) empty
			// *ast.File
			f = &ast.File{
				Name:  new(ast.Ident),
				Scope: ast.NewScope(nil),
			}
		}

		p.errors.Sort()
		err = p.errors.Err()
	}()

	// parse source
	p.init(fset, filename, text, mode)
	f = p.parseFile()

	return
}

// ImportPath = string_lit .
//
func (p *gcParser) parsePkgId() *ast.Object {
	id, err := strconv.Unquote(p.expect(scanner.String))
	if err != nil {
		p.error(err)
	}

	switch id {
	case "":
		// id == "" stands for the imported package id
		// (only known at time of package installation)
		id = p.id
	case "unsafe":
		// package unsafe is not in the imports map - handle explicitly
		return Unsafe
	}

	pkg := p.imports[id]
	if pkg == nil {
		scope = ast.NewScope(nil)
		pkg = ast.NewObj(ast.Pkg, "")
		pkg.Data = scope
		p.imports[id] = pkg
	}

	return pkg
}

// MethodDecl = "func" Receiver Name Func .
// Receiver   = "(" ( identifier | "?" ) [ "*" ] ExportedName ")" .
//
func (p *gcParser) parseMethodDecl() {
	// "func" already consumed
	p.expect('(')
	recv, _ := p.parseParameter() // receiver
	p.expect(')')

	// determine receiver base type object
	typ := recv.Type.(Type)
	if ptr, ok := typ.(*Pointer); ok {
		typ = ptr.Base
	}
	obj := typ.(*NamedType).Obj

	// determine base type scope
	var scope *ast.Scope
	if obj.Data != nil {
		scope = obj.Data.(*ast.Scope)
	} else {
		scope = ast.NewScope(nil)
		obj.Data = scope
	}

	// declare method in base type scope
	name := p.parseName() // unexported method names in imports are qualified with their package.
	p.parseFunc(scope, name)
}

// ParseFile parses the source code of a single Go source file and returns
// the corresponding ast.File node. The source code may be provided via
// the filename of the source file, or via the src parameter.
//
// If src != nil, ParseFile parses the source from src and the filename is
// only used when recording position information. The type of the argument
// for the src parameter must be string, []byte, or io.Reader.
// If src == nil, ParseFile parses the file specified by filename.
//
// The mode parameter controls the amount of source text parsed and other
// optional parser functionality. Position information is recorded in the
// file set fset.
//
// If the source couldn't be read, the returned AST is nil and the error
// indicates the specific failure. If the source was read but syntax
// errors were found, the result is a partial AST (with ast.Bad* nodes
// representing the fragments of erroneous source code). Multiple errors
// are returned via a scanner.ErrorList which is sorted by file position.
//
func ParseFile(fset *token.FileSet, filename string, src interface{}, mode Mode) (*ast.File, error) {
	// get source
	text, err := readSource(filename, src)
	if err != nil {
		return nil, err
	}

	// parse source
	var p parser
	p.init(fset, filename, text, mode)
	f := p.parseFile()
	if f == nil {
		// source is not a valid Go source file - satisfy
		// ParseFile API and return a valid (but) empty
		// *ast.File
		f = &ast.File{
			Name:  new(ast.Ident),
			Scope: ast.NewScope(nil),
		}
	}

	// sort errors
	if p.mode&SpuriousErrors == 0 {
		p.errors.RemoveMultiples()
	} else {
		p.errors.Sort()
	}

	return f, p.errors.Err()
}

func (p *parser) parseFuncDecl() *ast.FuncDecl {
	if p.trace {
		defer un(trace(p, "FunctionDecl"))
	}

	doc := p.leadComment
	pos := p.expect(token.FUNC)
	scope := ast.NewScope(p.funcScope)

	var recv *ast.FieldList
	if p.tok == token.LPAREN {
		recv = p.parseReceiver(scope)
	}

	ident := p.parseIdent(ast.Fun)
	p.declIdent(p.pkgScope, ident) // there are no local function declarations
	params, results := p.parseSignature(scope)

	var body *ast.BlockStmt
	if p.tok == token.LBRACE {
		body = p.parseBody(scope)
	}
	p.expectSemi()

	return &ast.FuncDecl{doc, recv, ident, &ast.FuncType{pos, params, results}, body}
}

func simpleImporter(imports map[string]*ast.Object, path string) (*ast.Object, error) {
	pkg := imports[path]
	if pkg == nil {
		// Guess the package name without importing it. Start with the last
		// element of the path.
		name := path[strings.LastIndex(path, "/")+1:]

		// Trim commonly used prefixes and suffixes containing illegal name
		// runes.
		name = strings.TrimSuffix(name, ".go")
		name = strings.TrimSuffix(name, "-go")
		name = strings.TrimPrefix(name, "go.")
		name = strings.TrimPrefix(name, "go-")
		name = strings.TrimPrefix(name, "biogo.")

		// It's also common for the last element of the path to contain an
		// extra "go" prefix, but not always. TODO: examine unresolved ids to
		// detect when trimming the "go" prefix is appropriate.

		pkg = ast.NewObj(ast.Pkg, name)
		pkg.Data = ast.NewScope(nil)
		imports[path] = pkg
	}
	return pkg, nil
}

// Export        = "PackageClause { Decl } "$$" .
// PackageClause = "package" identifier [ "safe" ] "\n" .
//
func (p *gcParser) parseExport() *ast.Object {
	p.expectKeyword("package")
	name := p.expect(scanner.Ident)
	if p.tok != '\n' {
		// A package is safe if it was compiled with the -u flag,
		// which disables the unsafe package.
		// TODO(gri) remember "safe" package
		p.expectKeyword("safe")
	}
	p.expect('\n')

	assert(p.imports[p.id] == nil)
	pkg := ast.NewObj(ast.Pkg, name)
	pkg.Data = ast.NewScope(nil)
	p.imports[p.id] = pkg

	for p.tok != '$' && p.tok != scanner.EOF {
		p.parseDecl()
	}

	if ch := p.scanner.Peek(); p.tok != '$' || ch != '$' {
		// don't call next()/expect() since reading past the
		// export data may cause scanner errors (e.g. NUL chars)
		p.errorf("expected '$$', got %s %c", scanner.TokenString(p.tok), ch)
	}

	if n := p.scanner.ErrorCount; n != 0 {
		p.errorf("expected no scanner errors, got %d", n)
	}

	return pkg
}

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.(*Type)
			assert(typ.Form == 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) declSignature(typ *Type, recv, params, results *ast.FieldList) {
	assert((typ.Form == 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 TestParse3(t *testing.T) {
	for _, filename := range validFiles {
		_, err := ParseFile(filename, nil, ast.NewScope(nil), 0)
		if err != nil {
			t.Errorf("ParseFile(%s): %v", filename, err)
		}
	}
}

func TestParseValidPrograms(t *testing.T) {
	for _, src := range validPrograms {
		_, err := ParseFile("", src, ast.NewScope(nil), 0)
		if err != nil {
			t.Errorf("ParseFile(%q): %v", src, err)
		}
	}
}

// assocMethod associates a method declaration with the respective
// receiver base type. meth.Recv must exist.
//
func (check *checker) assocMethod(meth *ast.FuncDecl) {
	// The receiver type is one of the following (enforced by parser):
	// - *ast.Ident
	// - *ast.StarExpr{*ast.Ident}
	// - *ast.BadExpr (parser error)
	typ := meth.Recv.List[0].Type
	if ptr, ok := typ.(*ast.StarExpr); ok {
		typ = ptr.X
	}
	// determine receiver base type object (or nil if error)
	var obj *ast.Object
	if ident, ok := typ.(*ast.Ident); ok && ident.Obj != nil {
		obj = ident.Obj
		if obj.Kind != ast.Typ {
			check.errorf(ident.Pos(), "%s is not a type", ident.Name)
			obj = nil
		}
		// TODO(gri) determine if obj was defined in this package
		/*
			if check.notLocal(obj) {
				check.errorf(ident.Pos(), "cannot define methods on non-local type %s", ident.Name)
				obj = nil
			}
		*/
	} else {
		// If it's not an identifier or the identifier wasn't declared/resolved,
		// the parser/resolver already reported an error. Nothing to do here.
	}
	// determine base type scope (or nil if error)
	var scope *ast.Scope
	if obj != nil {
		if obj.Data != nil {
			scope = obj.Data.(*ast.Scope)
		} else {
			scope = ast.NewScope(nil)
			obj.Data = scope
		}
	} else {
		// use a dummy scope so that meth can be declared in
		// presence of an error and get an associated object
		// (always use a new scope so that we don't get double
		// declaration errors)
		scope = ast.NewScope(nil)
	}
	check.declare(scope, ast.Fun, meth.Name, meth)
}

// poorMansImporter returns a (dummy) package object named
// by the last path component of the provided package path
// (as is the convention for packages). This is sufficient
// to resolve package identifiers without doing an actual
// import. It never returns an error.
//
func poorMansImporter(imports map[string]*ast.Object, path string) (*ast.Object, error) {
	pkg := imports[path]
	if pkg == nil {
		// note that strings.LastIndex returns -1 if there is no "/"
		pkg = ast.NewObj(ast.Pkg, path[strings.LastIndex(path, "/")+1:])
		pkg.Data = ast.NewScope(nil) // required by ast.NewPackage for dot-import
		imports[path] = pkg
	}
	return pkg, nil
}

func importer(imports map[string]*ast.Object, path string) (*ast.Object, error) {
	pkg := imports[path]
	if pkg == nil {
		name := path[strings.LastIndex(path, "/")+1:]
		pkg = ast.NewObj(ast.Pkg, name)
		pkg.Data = ast.NewScope(nil) // required by ast.NewPackage for dot-import
		imports[path] = pkg
	}
	return pkg, nil
}

func (p *gcParser) init(filename, id string, src io.Reader) {
	p.scanner.Init(src)
	p.scanner.Error = func(_ *scanner.Scanner, msg string) { p.error(msg) }
	p.scanner.Mode = scanner.ScanIdents | scanner.ScanInts | scanner.ScanStrings | scanner.ScanComments | scanner.SkipComments
	p.scanner.Whitespace = 1<<'\t' | 1<<' '
	p.scanner.Filename = filename // for good error messages
	p.next()
	p.id = id
	p.scope = ast.NewScope(nil)
	p.deps = map[string]*ast.Scope{"unsafe": Unsafe, id: p.scope}
}

func (p *parser) parseFuncType() (*ast.Scope, *ast.FuncType) {
	if p.trace {
		defer un(trace(p, "FuncType"))
	}

	pos := p.expect(token.FUNC)
	scope := ast.NewScope(p.funcScope)
	params, results := p.parseSignature(scope)

	return scope, &ast.FuncType{pos, params, results}
}

// MethodDecl = "func" Receiver identifier Signature .
// Receiver   = "(" ( identifier | "?" ) [ "*" ] ExportedName ")" .
//
func (p *gcParser) parseMethodDecl() {
	// "func" already consumed
	scope := ast.NewScope(nil) // method scope
	p.expect('(')
	p.parseParameter(scope, nil) // receiver
	p.expect(')')
	p.expect(scanner.Ident)
	isVariadic := false
	p.parseSignature(scope, &isVariadic)

}

func init() {
	// Universe scope
	Universe = ast.NewScope(nil)

	// unsafe package and its scope
	unsafe = ast.NewScope(nil)
	Unsafe = ast.NewObj(ast.Pkg, "unsafe")
	Unsafe.Data = unsafe

	// predeclared types
	for _, t := range Typ {
		def(ast.Typ, t.Name).Type = t
	}
	for _, t := range aliases {
		def(ast.Typ, t.Name).Type = t
	}

	// error type
	{
		res := ast.NewObj(ast.Var, "")
		res.Type = Typ[String]
		err := ast.NewObj(ast.Fun, "Error")
		err.Type = &Signature{Results: ObjList{res}}
		obj := def(ast.Typ, "error")
		obj.Type = &NamedType{Underlying: &Interface{Methods: ObjList{err}}, Obj: obj}
	}

	// predeclared constants
	for _, t := range predeclaredConstants {
		obj := def(ast.Con, t.name)
		obj.Type = Typ[t.kind]
		obj.Data = t.val
	}

	// predeclared functions
	for _, f := range predeclaredFunctions {
		def(ast.Fun, f.name).Type = f
	}

	universeIota = Universe.Lookup("iota")
}