func generate_target(srcdir string, pkgdir string, prefix string, ctx build.Context) string {
	pkg, _ := ctx.ImportDir(srcdir+pkgdir, 0)
	name := pkg.Name
	var deps []string
	for _, imp := range pkg.Imports {
		if strings.HasPrefix(imp, prefix) {
			imp = strings.TrimPrefix(imp, prefix)
			if packages[imp] == "" {
				packages[imp] = generate_target(srcdir, imp, prefix, ctx)
			}
			deps = append(deps, "$(LIBS_"+packages[imp]+")")
		}
	}
	if pkgdir != "" {
		fmt.Printf("SRCDIR_%s := $(SRCDIR)%s/\n", name, pkgdir)
	} else {
		fmt.Printf("SRCDIR_%s := $(SRCDIR)\n", name)
	}
	fmt.Printf("SRC_%s := $(addprefix $(SRCDIR_%s), %s)\n", name, name, strings.Join(pkg.GoFiles, " "))
	fmt.Printf("DEPS_%s := %s\n", name, strings.Join(deps, " "))
	if pkgdir != "" {
		fmt.Printf("OBJ_%s := $(LIBDIR)/%s.o\n", name, pkgdir)
		fmt.Printf("LIB_%s := $(LIBDIR)/%s.a\n", name, pkgdir)
		fmt.Printf("LIBS_%s := $(LIB_%s) $(DEPS_%s)\n", name, name, name)
		fmt.Printf("$(OBJ_%s) : $(SRC_%s) $(DEPS_%s)\n", name, name, name)
		fmt.Printf("\[email protected] -p $(dir [email protected])\n")
		fmt.Printf("\t$(GOC) $(GOFLAGS) -c -o [email protected] $(SRC_%s)\n", name)
	}
	return name
}

// subpackages returns the set of packages in the given srcDir whose
// import paths start with dir.
func subpackages(ctxt *build.Context, srcDir string, dir string) map[string]bool {
	subs := map[string]bool{dir: true}

	// Find all packages under srcDir whose import paths start with dir.
	buildutil.ForEachPackage(ctxt, func(pkg string, err error) {
		if err != nil {
			log.Fatalf("unexpected error in ForEachPackage: %v", err)
		}

		if !strings.HasPrefix(pkg, path.Join(dir, "")) {
			return
		}

		p, err := ctxt.Import(pkg, "", build.FindOnly)
		if err != nil {
			log.Fatalf("unexpected: package %s can not be located by build context: %s", pkg, err)
		}
		if p.SrcRoot == "" {
			log.Fatalf("unexpected: could not determine srcDir for package %s: %s", pkg, err)
		}
		if p.SrcRoot != srcDir {
			return
		}

		subs[pkg] = true
	})

	return subs
}

// imports returns a map of all import directories (recursively) used by the app.
// The return value maps full directory names to original import names.
func imports(ctxt *build.Context, srcDir string, gopath []string) (map[string]string, error) {
	pkg, err := ctxt.ImportDir(srcDir, 0)
	if err != nil {
		return nil, fmt.Errorf("unable to analyze source: %v", err)
	}

	// Resolve all non-standard-library imports
	result := make(map[string]string)
	for _, v := range pkg.Imports {
		if !strings.Contains(v, ".") {
			continue
		}
		src, err := findInGopath(v, gopath)
		if err != nil {
			return nil, fmt.Errorf("unable to find import %v in gopath %v: %v", v, gopath, err)
		}
		result[src] = v
		im, err := imports(ctxt, src, gopath)
		if err != nil {
			return nil, fmt.Errorf("unable to parse package %v: %v", src, err)
		}
		for k, v := range im {
			result[k] = v
		}
	}
	return result, nil
}

// PackageDoc gets the documentation for the package with the specified import
// path and writes it to out.
func PackageDoc(ctxt *build.Context, fset *token.FileSet, srcDir string, importPath string) (*Doc, error) {
	buildPkg, err := ctxt.Import(importPath, srcDir, build.ImportComment)
	if err != nil {
		return nil, err
	}
	// only parse .go files in the specified package
	filter := func(info os.FileInfo) bool {
		for _, fname := range buildPkg.GoFiles {
			if fname == info.Name() {
				return true
			}
		}
		return false
	}
	// TODO we've already parsed the files via go/loader...can we avoid doing it again?
	pkgs, err := parser.ParseDir(fset, buildPkg.Dir, filter, parser.PackageClauseOnly|parser.ParseComments)
	if err != nil {
		return nil, err
	}
	if astPkg, ok := pkgs[buildPkg.Name]; ok {
		docPkg := doc.New(astPkg, importPath, 0)
		// TODO: we could also include package-level constants, vars, and functions (like the go doc command)
		return &Doc{
			Name: buildPkg.Name,
			Decl: "package " + buildPkg.Name, // TODO: add '// import "pkg"' (like godoc)
			Doc:  docPkg.Doc,
		}, nil
	}
	return nil, errors.New("No documentation found for " + buildPkg.Name)
}

func resolvePackageSpec(ctx *build.Context, cwd string, src io.Reader, spec string) string {
	if strings.HasSuffix(spec, ".go") {
		d := path.Dir(spec)
		if !buildutil.IsAbsPath(ctx, d) {
			d = buildutil.JoinPath(ctx, cwd, d)
		}
		if bpkg, err := ctx.ImportDir(d, build.FindOnly); err == nil {
			return bpkg.ImportPath
		}
	}
	path := spec
	switch {
	case strings.HasPrefix(spec, "."):
		if bpkg, err := ctx.Import(spec, cwd, build.FindOnly); err == nil {
			path = bpkg.ImportPath
		}
	case strings.HasPrefix(spec, "/"):
		path = spec[1:]
	default:
		if p, ok := readImports(cwd, src)[spec]; ok {
			path = p
		}
	}
	return strings.TrimSuffix(path, "/")
}

// IsDir behaves like os.Stat plus IsDir,
// but uses the build context's file system interface, if any.
func IsDir(ctxt *build.Context, path string) bool {
	if ctxt.IsDir != nil {
		return ctxt.IsDir(path)
	}
	fi, err := os.Stat(path)
	return err == nil && fi.IsDir()
}

//Import imports a package.
//
//path is run through ToImport.
//
//If ctx is nil, the default context is used.
//
//N.B. we require a pointer to a build.Context for caching.
//Two build contexts with identical values that are not represented
//by the same pointer will have all packages imported by them
//cached separately.
func Import(ctx *build.Context, path string) (*Package, error) {
	if ctx == nil {
		ctx = defaultctx
	}
	root, path, err := ToImport(path)
	if err != nil {
		return nil, err
	}

	ident := ident{ctx, path}
	if pkg := pkgget(ident); pkg != nil {
		return pkg, nil
	}

	p, err := ctx.Import(path, root, 0)
	if err != nil {
		return nil, err
	}

	pkg := &Package{
		Context: ctx,
		Build:   p,
	}
	pkgset(ident, pkg)

	return pkg, nil
}

// guessImportPath finds the package containing filename, and returns
// its source directory (an element of $GOPATH) and its import path
// relative to it.
//
// TODO(adonovan): what about _test.go files that are not part of the
// package?
//
func guessImportPath(filename string, buildContext *build.Context) (srcdir, importPath string, err error) {
	absFile, err := filepath.Abs(filename)
	if err != nil {
		err = fmt.Errorf("can't form absolute path of %s", filename)
		return
	}
	absFileDir := segments(filepath.Dir(absFile))

	// Find the innermost directory in $GOPATH that encloses filename.
	minD := 1024
	for _, gopathDir := range buildContext.SrcDirs() {
		absDir, err := filepath.Abs(gopathDir)
		if err != nil {
			continue // e.g. non-existent dir on $GOPATH
		}
		d := prefixLen(segments(absDir), absFileDir)
		// If there are multiple matches,
		// prefer the innermost enclosing directory
		// (smallest d).
		if d >= 0 && d < minD {
			minD = d
			srcdir = gopathDir
			importPath = strings.Join(absFileDir[len(absFileDir)-minD:], string(os.PathSeparator))
		}
	}
	if srcdir == "" {
		err = fmt.Errorf("can't find package for file %s", filename)
	}
	return
}

// ContainingPackage returns the package containing filename.
//
// If filename is not absolute, it is interpreted relative to working directory dir.
// All I/O is via the build context's file system interface, if any.
//
// The '...Files []string' fields of the resulting build.Package are not
// populated (build.FindOnly mode).
//
// TODO(adonovan): call this from oracle when the tree thaws.
//
func ContainingPackage(ctxt *build.Context, dir, filename string) (*build.Package, error) {
	if !IsAbsPath(ctxt, filename) {
		filename = JoinPath(ctxt, dir, filename)
	}

	// We must not assume the file tree uses
	// "/" always,
	// `\` always,
	// or os.PathSeparator (which varies by platform),
	// but to make any progress, we are forced to assume that
	// paths will not use `\` unless the PathSeparator
	// is also `\`, thus we can rely on filepath.ToSlash for some sanity.

	dirSlash := path.Dir(filepath.ToSlash(filename)) + "/"

	// We assume that no source root (GOPATH[i] or GOROOT) contains any other.
	for _, srcdir := range ctxt.SrcDirs() {
		srcdirSlash := filepath.ToSlash(srcdir) + "/"
		if dirHasPrefix(dirSlash, srcdirSlash) {
			importPath := dirSlash[len(srcdirSlash) : len(dirSlash)-len("/")]
			return ctxt.Import(importPath, dir, build.FindOnly)
		}
	}

	return nil, fmt.Errorf("can't find package containing %s", filename)
}

// ForEachPackage calls the found function with the package path of
// each Go package it finds in any source directory of the specified
// build context (e.g. $GOROOT or an element of $GOPATH).
// All package paths are canonical, and thus may contain "/vendor/".
//
// If the package directory exists but could not be read, the second
// argument to the found function provides the error.
//
// All I/O is done via the build.Context file system interface,
// which must be concurrency-safe.
//
func ForEachPackage(ctxt *build.Context, found func(importPath string, err error)) {
	// We use a counting semaphore to limit
	// the number of parallel calls to ReadDir.
	sema := make(chan bool, 20)

	ch := make(chan item)

	var wg sync.WaitGroup
	for _, root := range ctxt.SrcDirs() {
		root := root
		wg.Add(1)
		go func() {
			allPackages(ctxt, sema, root, ch)
			wg.Done()
		}()
	}
	go func() {
		wg.Wait()
		close(ch)
	}()

	// All calls to found occur in the caller's goroutine.
	for i := range ch {
		found(i.importPath, i.err)
	}
}

// parseFiles parses the Go source files within directory dir and
// returns the ASTs of the ones that could be at least partially parsed,
// along with a list of I/O and parse errors encountered.
//
// I/O is done via ctxt, which may specify a virtual file system.
// displayPath is used to transform the filenames attached to the ASTs.
//
func parseFiles(fset *token.FileSet, ctxt *build.Context, displayPath func(string) string, dir string, files []string, mode parser.Mode) ([]*ast.File, []error) {
	if displayPath == nil {
		displayPath = func(path string) string { return path }
	}
	var wg sync.WaitGroup
	n := len(files)
	parsed := make([]*ast.File, n)
	errors := make([]error, n)
	for i, file := range files {
		if !buildutil.IsAbsPath(ctxt, file) {
			file = buildutil.JoinPath(ctxt, dir, file)
		}
		wg.Add(1)
		go func(i int, file string) {
			ioLimit <- true // wait
			defer func() {
				wg.Done()
				<-ioLimit // signal
			}()
			var rd io.ReadCloser
			var err error
			if ctxt.OpenFile != nil {
				rd, err = ctxt.OpenFile(file)
			} else {
				rd, err = os.Open(file)
			}
			if err != nil {
				errors[i] = err // open failed
				return
			}

			// ParseFile may return both an AST and an error.
			parsed[i], errors[i] = parser.ParseFile(fset, displayPath(file), rd, mode)
			rd.Close()
		}(i, file)
	}
	wg.Wait()

	// Eliminate nils, preserving order.
	var o int
	for _, f := range parsed {
		if f != nil {
			parsed[o] = f
			o++
		}
	}
	parsed = parsed[:o]

	o = 0
	for _, err := range errors {
		if err != nil {
			errors[o] = err
			o++
		}
	}
	errors = errors[:o]

	return parsed, errors
}

// build gets imports from source files.
func (w *walker) build(srcs []*source) ([]string, error) {
	// Add source files to walker, I skipped references here.
	w.srcs = make(map[string]*source)
	for _, src := range srcs {
		w.srcs[src.name] = src
	}

	w.fset = token.NewFileSet()

	// Find the package and associated files.
	ctxt := build.Context{
		GOOS:          runtime.GOOS,
		GOARCH:        runtime.GOARCH,
		CgoEnabled:    true,
		JoinPath:      path.Join,
		IsAbsPath:     path.IsAbs,
		SplitPathList: func(list string) []string { return strings.Split(list, ":") },
		IsDir:         func(path string) bool { panic("unexpected") },
		HasSubdir:     func(root, dir string) (rel string, ok bool) { panic("unexpected") },
		ReadDir:       func(dir string) (fi []os.FileInfo, err error) { return w.readDir(dir) },
		OpenFile:      func(path string) (r io.ReadCloser, err error) { return w.openFile(path) },
		Compiler:      "gc",
	}

	bpkg, err := ctxt.ImportDir(w.ImportPath, 0)
	// Continue if there are no Go source files; we still want the directory info.
	_, nogo := err.(*build.NoGoError)
	if err != nil {
		if nogo {
			err = nil
		} else {
			return nil, errors.New("doc.walker.build(): " + err.Error())
		}
	}

	// Parse the Go files

	files := make(map[string]*ast.File)
	for _, name := range append(bpkg.GoFiles, bpkg.CgoFiles...) {
		file, err := parser.ParseFile(w.fset, name, w.srcs[name].data, parser.ParseComments)
		if err != nil {
			//beego.Error("doc.walker.build():", err)
			continue
		}
		files[name] = file
	}

	w.ImportPath = strings.Replace(w.ImportPath, "\\", "/", -1)
	var imports []string
	for _, v := range bpkg.Imports {
		// Skip strandard library.
		if !utils.IsGoRepoPath(v) &&
			(utils.GetProjectPath(v) != utils.GetProjectPath(w.ImportPath)) {
			imports = append(imports, v)
		}
	}

	return imports, err
}

// defaultFindPackage locates the specified (possibly empty) package
// using go/build logic.  It returns an error if not found.
func defaultFindPackage(ctxt *build.Context, path string) (*build.Package, error) {
	// Import(srcDir="") disables local imports, e.g. import "./foo".
	bp, err := ctxt.Import(path, "", 0)
	if _, ok := err.(*build.NoGoError); ok {
		return bp, nil // empty directory is not an error
	}
	return bp, err
}

// build generates data from source files.
func (w *routerWalker) build(srcs []*source) (*Package, error) {
	// Add source files to walker, I skipped references here.
	w.srcs = make(map[string]*source)
	for _, src := range srcs {
		w.srcs[src.name] = src
	}

	w.fset = token.NewFileSet()

	// Find the package and associated files.
	ctxt := gobuild.Context{
		GOOS:          runtime.GOOS,
		GOARCH:        runtime.GOARCH,
		CgoEnabled:    true,
		JoinPath:      path.Join,
		IsAbsPath:     path.IsAbs,
		SplitPathList: func(list string) []string { return strings.Split(list, ":") },
		IsDir:         func(path string) bool { panic("unexpected") },
		HasSubdir:     func(root, dir string) (rel string, ok bool) { panic("unexpected") },
		ReadDir:       func(dir string) (fi []os.FileInfo, err error) { return w.readDir(dir) },
		OpenFile:      func(path string) (r io.ReadCloser, err error) { return w.openFile(path) },
		Compiler:      "gc",
	}

	bpkg, err := ctxt.ImportDir(w.pdoc.ImportPath, 0)
	// Continue if there are no Go source files; we still want the directory info.
	_, nogo := err.(*gobuild.NoGoError)
	if err != nil {
		if nogo {
			err = nil
		} else {
			return nil, errors.New("routerWalker.build -> " + err.Error())
		}
	}

	// Parse the Go files
	files := make(map[string]*ast.File)
	for _, name := range append(bpkg.GoFiles, bpkg.CgoFiles...) {
		file, err := parser.ParseFile(w.fset, name, w.srcs[name].data, parser.ParseComments)
		if err != nil {
			return nil, errors.New("routerWalker.build -> parse go files: " + err.Error())
		}
		files[name] = file
	}

	apkg, _ := ast.NewPackage(w.fset, files, simpleImporter, nil)

	mode := doc.Mode(0)
	if w.pdoc.ImportPath == "builtin" {
		mode |= doc.AllDecls
	}

	pdoc := doc.New(apkg, w.pdoc.ImportPath, mode)

	w.pdoc.Types = w.types(pdoc.Types)

	return w.pdoc, err
}

func ImportStdPkg(context *build.Context, path string, mode build.ImportMode) (*build.Package, error) {
	realpath := filepath.Join(context.GOROOT, "src", "pkg", path)
	if _, err := os.Stat(realpath); err != nil {
		realpath = filepath.Join(context.GOROOT, "src", path)
	}
	pkg, err := context.ImportDir(realpath, 0)
	pkg.ImportPath = path
	return pkg, err
}

// find_global_file returns the file path of the compiled package corresponding to the specified
// import, and a boolean stating whether such path is valid.
// TODO: Return only one value, possibly empty string if not found.
func find_global_file(imp string, context build.Context) (string, bool) {
	// gocode synthetically generates the builtin package
	// "unsafe", since the "unsafe.a" package doesn't really exist.
	// Thus, when the user request for the package "unsafe" we
	// would return synthetic global file that would be used
	// just as a key name to find this synthetic package
	if imp == "unsafe" {
		return "unsafe", true
	}

	pkgfile := fmt.Sprintf("%s.a", imp)

	// if lib-path is defined, use it
	if g_config.LibPath != "" {
		for _, p := range filepath.SplitList(g_config.LibPath) {
			pkg_path := filepath.Join(p, pkgfile)
			if file_exists(pkg_path) {
				log_found_package_maybe(imp, pkg_path)
				return pkg_path, true
			}
			// Also check the relevant pkg/OS_ARCH dir for the libpath, if provided.
			pkgdir := fmt.Sprintf("%s_%s", context.GOOS, context.GOARCH)
			pkg_path = filepath.Join(p, "pkg", pkgdir, pkgfile)
			if file_exists(pkg_path) {
				log_found_package_maybe(imp, pkg_path)
				return pkg_path, true
			}
			// Also check the relevant pkg/OS/ARCH dir for the libpath, if provided.
			pkg_path = filepath.Join(p, "pkg", context.GOOS, context.GOARCH, pkgfile)
			if file_exists(pkg_path) {
				log_found_package_maybe(imp, pkg_path)
				return pkg_path, true
			}
		}
	}

	p, err := context.Import(imp, "", build.AllowBinary|build.FindOnly)
	if err == nil {
		if g_config.Autobuild {
			err = autobuild(p)
			if err != nil && *g_debug {
				log.Printf("Autobuild error: %s\n", err)
			}
		}
		if file_exists(p.PkgObj) {
			log_found_package_maybe(imp, p.PkgObj)
			return p.PkgObj, true
		}
	}

	if *g_debug {
		log.Printf("Import path %q was not resolved\n", imp)
		log.Println("Gocode's build context is:")
		log_build_context(context)
	}
	return "", false
}

func ImportPaths(srcDir string, bctx *build.Context, pathFilter margo.PathFilterFunc) map[string]string {
	rootDirs := bctx.SrcDirs()

	importDir := func(dir string) *build.Package {
		p := quickImportDir(bctx, rootDirs, dir)
		if p != nil && p.Name != "" && p.ImportPath != "" {
			return p
		}
		return nil
	}

	srcImportPath := quickImportPath(srcDir)

	var pkgs []*build.Package
	for _, dir := range rootDirs {
		pkgs = append(pkgs, importablePackages(dir, importDir, pathFilter)...)
	}

	res := make(map[string]string, len(pkgs))
	res["unsafe"] = "" // this package doesn't exist on-disk

	const vdir = "/vendor/"
	var vendored []*build.Package
	for _, p := range pkgs {
		switch {
		case p.Name == "main":
		// it's rarely useful to import `package main`
		case p.ImportPath == "builtin":
		// this package exists for documentation only
		case strings.HasPrefix(p.ImportPath, vdir[1:]) || strings.Contains(p.ImportPath, vdir):
			// fill these in after everything else so we can tag them
			vendored = append(vendored, p)
		default:
			res[p.ImportPath] = importsName(p)
		}
	}
	if srcImportPath != "" {
		sfx := srcImportPath + "/"
		for _, p := range vendored {
			name := importsName(p) + " [vendored]"
			ipath := p.ImportPath
			vpos := strings.LastIndex(ipath, vdir)
			switch {
			case vpos > 0:
				pfx := ipath[:vpos+1]
				if strings.HasPrefix(sfx, pfx) {
					ipath := ipath[vpos+len(vdir):]
					res[ipath] = name
				}
			case strings.HasPrefix(ipath, vdir[1:]):
				ipath := ipath[len(vdir)-1:]
				res[ipath] = name
			}
		}
	}
	return res
}

// srcDir returns the absolute path of the srcdir containing pkg.
func srcDir(ctxt *build.Context, pkg string) (string, error) {
	for _, srcDir := range ctxt.SrcDirs() {
		path := buildutil.JoinPath(ctxt, srcDir, pkg)
		if buildutil.IsDir(ctxt, path) {
			return srcDir, nil
		}
	}
	return "", fmt.Errorf("src dir not found for package: %s", pkg)
}

// importRuntime locates the the runtime package and parses its files
// to *ast.Files. This is used to generate runtime type structures.
func parseRuntime(buildctx *build.Context, fset *token.FileSet) ([]*ast.File, error) {
	buildpkg, err := buildctx.Import("github.com/go-llvm/llgo/pkg/runtime", "", 0)
	if err != nil {
		return nil, err
	}
	filenames := make([]string, len(buildpkg.GoFiles))
	for i, f := range buildpkg.GoFiles {
		filenames[i] = path.Join(buildpkg.Dir, f)
	}
	return parseFiles(fset, filenames)
}

// FileExists returns true if the specified file exists,
// using the build context's file system interface.
func FileExists(ctxt *build.Context, path string) bool {
	if ctxt.OpenFile != nil {
		r, err := ctxt.OpenFile(path)
		if err != nil {
			return false
		}
		r.Close() // ignore error
		return true
	}
	_, err := os.Stat(path)
	return err == nil
}