func (e *exporter) addImport(pkg *types.Package) {
	if _, found := e.imports[pkg]; found {
		return
	}
	fmt.Fprintf(e.out, "import %s \"%s\"\n", pkg.Name(), pkg.Path())
	e.imports[pkg] = true
}

func (w *PkgWalker) LookupStructFromField(info *types.Info, cursorPkg *types.Package, cursorObj types.Object, cursorPos token.Pos) types.Object {
	if info == nil {
		conf := &PkgConfig{
			IgnoreFuncBodies: true,
			AllowBinary:      true,
			Info: &types.Info{
				Defs: make(map[*ast.Ident]types.Object),
			},
		}
		w.imported[cursorPkg.Path()] = nil
		pkg, _ := w.Import("", cursorPkg.Path(), conf)
		if pkg != nil {
			info = conf.Info
		}
	}
	for _, obj := range info.Defs {
		if obj == nil {
			continue
		}
		if _, ok := obj.(*types.TypeName); ok {
			if t, ok := obj.Type().Underlying().(*types.Struct); ok {
				for i := 0; i < t.NumFields(); i++ {
					if t.Field(i).Pos() == cursorPos {
						return obj
					}
				}
			}
		}
	}
	return nil
}

func (x *exporter) export(pkg *types.Package) error {
	x.pkg = pkg
	x.writeFunc = true
	exportsFile := packageExportsFile(x.context, pkg.Path())
	err := os.MkdirAll(filepath.Dir(exportsFile), 0755)
	if err != nil && !os.IsExist(err) {
		return err
	}
	f2, err := os.Create(exportsFile)
	if err != nil {
		return err
	}
	defer f2.Close()
	x.writer = f2
	x.write("package %s\n", pkg.Name())
	for _, imp := range pkg.Imports() {
		x.write("\timport %s \"%s\"\n", imp.Name(), imp.Path())
	}
	for _, n := range pkg.Scope().Names() {
		if obj := pkg.Scope().Lookup(n); obj != nil {
			x.exportObject(obj)
		}
	}
	x.write("$$")
	return nil
}

// Export generates a file containing package export data
// suitable for importing with Importer.Import.
func Export(ctx *build.Context, pkg *types.Package) error {
	exportsPath := packageExportsFile(ctx, pkg.Path())
	err := os.MkdirAll(filepath.Dir(exportsPath), 0755)
	if err != nil && !os.IsExist(err) {
		return err
	}
	tracef("Writing import data to %q", exportsPath)
	return ioutil.WriteFile(exportsPath, importer.ExportData(pkg), 0644)
}

func WriteArchive(code []byte, pkg *types.Package, w io.Writer) {
	w.Write(code)
	w.Write([]byte("$$\n"))
	for _, impPkg := range pkg.Imports() {
		w.Write([]byte(impPkg.Path()))
		w.Write([]byte{'\n'})
	}
	w.Write([]byte("$$\n"))
	gcexporter.Write(pkg, w, sizes32)
}

func typePackageToJson(p *types.Package) interface{} {
	if p == nil {
		return nil
	} else {
		return struct {
			Isa, Name, ImportPath string
		}{
			"Package", p.Name(), p.Path(),
		}
	}
}

// pkgString returns a string representation of a package's exported interface.
func pkgString(pkg *types.Package) string {
	var buf bytes.Buffer

	fmt.Fprintf(&buf, "package %s\n", pkg.Name())

	scope := pkg.Scope()
	for _, name := range scope.Names() {
		if exported(name) {
			obj := scope.Lookup(name)
			buf.WriteString(obj.String())

			switch obj := obj.(type) {
			case *types.Const:
				// For now only print constant values if they are not float
				// or complex. This permits comparing go/types results with
				// gc-generated gcimported package interfaces.
				info := obj.Type().Underlying().(*types.Basic).Info()
				if info&types.IsFloat == 0 && info&types.IsComplex == 0 {
					fmt.Fprintf(&buf, " = %s", obj.Val())
				}

			case *types.TypeName:
				// Print associated methods.
				// Basic types (e.g., unsafe.Pointer) have *types.Basic
				// type rather than *types.Named; so we need to check.
				if typ, _ := obj.Type().(*types.Named); typ != nil {
					if n := typ.NumMethods(); n > 0 {
						// Sort methods by name so that we get the
						// same order independent of whether the
						// methods got imported or coming directly
						// for the source.
						// TODO(gri) This should probably be done
						// in go/types.
						list := make([]*types.Func, n)
						for i := 0; i < n; i++ {
							list[i] = typ.Method(i)
						}
						sort.Sort(byName(list))

						buf.WriteString("\nmethods (\n")
						for _, m := range list {
							fmt.Fprintf(&buf, "\t%s\n", m)
						}
						buf.WriteString(")")
					}
				}
			}
			buf.WriteByte('\n')
		}
	}

	return buf.String()
}

func declTypeName(pkg *types.Package, name string) *types.TypeName {
	scope := pkg.Scope()
	if obj := scope.Lookup(name); obj != nil {
		return obj.(*types.TypeName)
	}
	obj := types.NewTypeName(token.NoPos, pkg, name, nil)
	// a named type may be referred to before the underlying type
	// is known - set it up
	types.NewNamed(obj, nil, nil)
	scope.Insert(obj)
	return obj
}

func assocObjectPackages(pkg *types.Package, objectdata map[types.Object]*ObjectData) {
	for _, obj := range pkg.Scope().Entries {
		if data, ok := objectdata[obj]; ok {
			data.Package = pkg
		} else {
			objectdata[obj] = &ObjectData{Package: pkg}
		}
	}
	for _, pkg := range pkg.Imports() {
		assocObjectPackages(pkg, objectdata)
	}
}

func (ctx *Context) getObjects(paths []string) ([]types.Object, []error) {
	var errors []error
	var objects []types.Object

pathLoop:
	for _, path := range paths {
		buildPkg, err := build.Import(path, ".", 0)
		if err != nil {
			errors = append(errors, fmt.Errorf("Couldn't import %s: %s", path, err))
			continue
		}
		fset := token.NewFileSet()
		var astFiles []*ast.File
		var pkg *types.Package
		if buildPkg.Goroot {
			// TODO what if the compiled package in GoRoot is
			// outdated?
			pkg, err = types.GcImport(ctx.allImports, path)
			if err != nil {
				errors = append(errors, fmt.Errorf("Couldn't import %s: %s", path, err))
				continue
			}
		} else {
			if len(buildPkg.GoFiles) == 0 {
				errors = append(errors, fmt.Errorf("Couldn't parse %s: No (non cgo) Go files", path))
				continue pathLoop
			}
			for _, file := range buildPkg.GoFiles {
				astFile, err := parseFile(fset, filepath.Join(buildPkg.Dir, file))
				if err != nil {
					errors = append(errors, fmt.Errorf("Couldn't parse %s: %s", err))
					continue pathLoop
				}
				astFiles = append(astFiles, astFile)
			}
			pkg, err = check(ctx, path, fset, astFiles)
			if err != nil {
				errors = append(errors, fmt.Errorf("Couldn't parse %s: %s\n", path, err))
				continue pathLoop
			}
		}

		scope := pkg.Scope()
		for i := 0; i < scope.NumEntries(); i++ {
			obj := scope.At(i)
			objects = append(objects, obj)
		}
	}

	return objects, errors
}

func assocObjectPackages(pkg *types.Package, objectdata map[types.Object]*ObjectData) {
	scope := pkg.Scope()
	for _, name := range scope.Names() {
		obj := scope.Lookup(name)
		if data, ok := objectdata[obj]; ok {
			data.Package = pkg
		} else {
			objectdata[obj] = &ObjectData{Package: pkg}
		}
	}
	for _, pkg := range pkg.Imports() {
		assocObjectPackages(pkg, objectdata)
	}
}

func (r *renamer) checkExport(id *ast.Ident, pkg *types.Package, from types.Object) bool {
	// Reject cross-package references if r.to is unexported.
	// (Such references may be qualified identifiers or field/method
	// selections.)
	if !ast.IsExported(r.to) && pkg != from.Pkg() {
		r.errorf(from.Pos(),
			"renaming this %s %q to %q would make it unexported",
			objectKind(from), from.Name(), r.to)
		r.errorf(id.Pos(), "\tbreaking references from packages such as %q",
			pkg.Path())
		return false
	}
	return true
}

// export emits the exported package features.
func (w *Walker) export(pkg *types.Package) {
	if *verbose {
		log.Println(pkg)
	}
	pop := w.pushScope("pkg " + pkg.Path())
	w.current = pkg
	scope := pkg.Scope()
	for _, name := range scope.Names() {
		if ast.IsExported(name) {
			w.emitObj(scope.Lookup(name))
		}
	}
	pop()
}

func describePackage(o *Oracle, qpos *QueryPos, path []ast.Node) (*describePackageResult, error) {
	var description string
	var pkg *types.Package
	switch n := path[0].(type) {
	case *ast.ImportSpec:
		var pkgname *types.PkgName
		if n.Name != nil {
			pkgname = qpos.info.Defs[n.Name].(*types.PkgName)
		} else if p := qpos.info.Implicits[n]; p != nil {
			pkgname = p.(*types.PkgName)
		}
		description = fmt.Sprintf("import of package %q", pkgname.Pkg().Path())
		pkg = pkgname.Pkg()

	case *ast.Ident:
		if _, isDef := path[1].(*ast.File); isDef {
			// e.g. package id
			pkg = qpos.info.Pkg
			description = fmt.Sprintf("definition of package %q", pkg.Path())
		} else {
			// e.g. import id "..."
			//  or  id.F()
			pkg = qpos.info.ObjectOf(n).Pkg()
			description = fmt.Sprintf("reference to package %q", pkg.Path())
		}

	default:
		// Unreachable?
		return nil, fmt.Errorf("unexpected AST for package: %T", n)
	}

	var members []*describeMember
	// NB: "unsafe" has no types.Package
	if pkg != nil {
		// Enumerate the accessible package members
		// in lexicographic order.
		for _, name := range pkg.Scope().Names() {
			if pkg == qpos.info.Pkg || ast.IsExported(name) {
				mem := pkg.Scope().Lookup(name)
				var methods []*types.Selection
				if mem, ok := mem.(*types.TypeName); ok {
					methods = accessibleMethods(mem.Type(), qpos.info.Pkg)
				}
				members = append(members, &describeMember{
					mem,
					methods,
				})

			}
		}
	}

	return &describePackageResult{o.fset, path[0], description, pkg, members}, nil
}

func describePackage(o *Oracle, qpos *QueryPos, path []ast.Node) (*describePackageResult, error) {
	var description string
	var pkg *types.Package
	switch n := path[0].(type) {
	case *ast.ImportSpec:
		// Most ImportSpecs have no .Name Ident so we can't
		// use ObjectOf.
		// We could use the types.Info.Implicits mechanism,
		// but it's easier just to look it up by name.
		description = "import of package " + n.Path.Value
		importPath, _ := strconv.Unquote(n.Path.Value)
		pkg = o.prog.ImportedPackage(importPath).Object

	case *ast.Ident:
		if _, isDef := path[1].(*ast.File); isDef {
			// e.g. package id
			pkg = qpos.info.Pkg
			description = fmt.Sprintf("definition of package %q", pkg.Path())
		} else {
			// e.g. import id
			//  or  id.F()
			pkg = qpos.info.ObjectOf(n).Pkg()
			description = fmt.Sprintf("reference to package %q", pkg.Path())
		}

	default:
		// Unreachable?
		return nil, fmt.Errorf("unexpected AST for package: %T", n)
	}

	var members []*describeMember
	// NB: "unsafe" has no types.Package
	if pkg != nil {
		// Enumerate the accessible package members
		// in lexicographic order.
		for _, name := range pkg.Scope().Names() {
			if pkg == qpos.info.Pkg || ast.IsExported(name) {
				mem := pkg.Scope().Lookup(name)
				var methods []*types.Selection
				if mem, ok := mem.(*types.TypeName); ok {
					methods = accessibleMethods(mem.Type(), qpos.info.Pkg)
				}
				members = append(members, &describeMember{
					mem,
					methods,
				})

			}
		}
	}

	return &describePackageResult{o.prog.Fset, path[0], description, pkg, members}, nil
}

func testExportImport(t *testing.T, pkg0 *types.Package, path string) (size, gcsize int) {
	data := ExportData(pkg0)
	size = len(data)

	imports := make(map[string]*types.Package)
	n, pkg1, err := ImportData(imports, data)
	if err != nil {
		t.Errorf("package %s: import failed: %s", pkg0.Name(), err)
		return
	}
	if n != size {
		t.Errorf("package %s: not all input data consumed", pkg0.Name())
		return
	}

	s0 := pkgString(pkg0)
	s1 := pkgString(pkg1)
	if s1 != s0 {
		t.Errorf("package %s: \nimport got:\n%s\nwant:\n%s\n", pkg0.Name(), s1, s0)
	}

	// If we have a standard library, compare also against the gcimported package.
	if path == "" {
		return // not std library
	}

	gcdata, err := gcExportData(path)
	gcsize = len(gcdata)

	imports = make(map[string]*types.Package)
	pkg2, err := gcImportData(imports, gcdata, path)
	if err != nil {
		t.Errorf("package %s: gcimport failed: %s", pkg0.Name(), err)
		return
	}

	s2 := pkgString(pkg2)
	if s2 != s0 {
		t.Errorf("package %s: \ngcimport got:\n%s\nwant:\n%s\n", pkg0.Name(), s2, s0)
	}

	return
}

func FindImplentations(i *types.Interface, pkg *types.Package) []string {
	var names []string

	scope := pkg.Scope()
	allNames := scope.Names()

	for _, name := range allNames {
		obj := scope.Lookup(name)
		if typeName, ok := obj.(*types.TypeName); ok {
			if types.Implements(typeName.Type(), i) {
				names = append(names, typeName.Name())
			} else {
				println(typeName.Name(), "cannot be an ensurer")
				println(types.NewMethodSet(typeName.Type()).String())
			}
		}
	}

	return names
}

func (p *importer) obj(pkg *types.Package) {
	var obj types.Object
	switch tag := p.int(); tag {
	case constTag:
		obj = types.NewConst(token.NoPos, pkg, p.string(), p.typ(), p.value())
	case typeTag:
		// type object is added to scope via respective named type
		_ = p.typ().(*types.Named)
		return
	case varTag:
		obj = types.NewVar(token.NoPos, pkg, p.string(), p.typ())
	case funcTag:
		obj = types.NewFunc(token.NoPos, pkg, p.string(), p.typ().(*types.Signature))
	default:
		panic(fmt.Sprintf("unexpected object tag %d", tag))
	}

	if alt := pkg.Scope().Insert(obj); alt != nil {
		panic(fmt.Sprintf("%s already declared", alt.Name()))
	}
}

func (p *exporter) pkg(pkg *types.Package) {
	if trace {
		p.tracef("package { ")
		defer p.tracef("} ")
	}

	if pkg == nil {
		panic("unexpected nil pkg")
	}

	// if the package was seen before, write its index (>= 0)
	if i, ok := p.pkgIndex[pkg]; ok {
		p.int(i)
		return
	}
	p.pkgIndex[pkg] = len(p.pkgIndex)

	// otherwise, write the package tag (< 0) and package data
	p.int(packageTag)
	p.string(pkg.Name())
	p.string(pkg.Path())
}

// ExportData serializes the interface (exported package objects)
// of package pkg and returns the corresponding data. The export
// format is described elsewhere (TODO).
func ExportData(pkg *types.Package) []byte {
	p := exporter{
		data:     []byte(magic),
		pkgIndex: make(map[*types.Package]int),
		typIndex: make(map[types.Type]int),
	}

	// populate typIndex with predeclared types
	for _, t := range types.Typ[1:] {
		p.typIndex[t] = len(p.typIndex)
	}
	p.typIndex[types.Universe.Lookup("error").Type()] = len(p.typIndex)

	if trace {
		p.tracef("export %s\n", pkg.Name())
		defer p.tracef("\n")
	}

	p.string(version)

	p.pkg(pkg)

	// collect exported objects from package scope
	var list []types.Object
	scope := pkg.Scope()
	for _, name := range scope.Names() {
		if exported(name) {
			list = append(list, scope.Lookup(name))
		}
	}

	// write objects
	p.int(len(list))
	for _, obj := range list {
		p.obj(obj)
	}

	return p.data
}