Add microfactory to bootstrap a go program with minimal overhead

microfactory is a tool to incrementally compile a go program. It's
similar to `go install`, but doesn't require a GOPATH. A package->path
mapping can be specified as command line options. All input files are
hashed, and if any change, the necessary packages will be rebuilt.

microfactory can (re)build itself as necessary, so combined with a shell
script that runs `go run microfactory.go` the first time, it can
bootstrap a go program entirely from sources with just a working goroot.

Time to build soong_ui only using source & GOROOT:

            first time    no-change incremental
microfactory  1400ms               15ms
go install     670ms              130ms

While microfactory takes longer the first time, almost half of that time
is from `go run` and building microfactory for use later. If
microfactory only has to build soong_ui, it's about 580ms.

Test: USE_SOONG_UI=true m -j blueprint_tools
Test: go test -bench . build/soong/cmd/microfactory/microfactory_test.go
Change-Id: I4d2b9825788144fa10042bbd804482e44f459a54

3 files changed, 971 insertions, 0 deletions

diff --git a/cmd/microfactory/Android.bp b/cmd/microfactory/Android.bp
new file mode 100644
index 00000000..a457f439
--- /dev/null
+++ b/cmd/microfactory/Android.bp
@@ -0,0 +1,23 @@
+// Copyright 2017 Google Inc. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+blueprint_go_binary {
+    name: "microfactory",
+    srcs: [
+        "microfactory.go",
+    ],
+    testSrcs: [
+        "microfactory_test.go",
+    ],
+}
diff --git a/cmd/microfactory/microfactory.go b/cmd/microfactory/microfactory.go
new file mode 100644
index 00000000..3ed5a2c3
--- /dev/null
+++ b/cmd/microfactory/microfactory.go
@@ -0,0 +1,526 @@
+// Copyright 2017 Google Inc. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+// Microfactory is a tool to incrementally compile a go program. It's similar
+// to `go install`, but doesn't require a GOPATH. A package->path mapping can
+// be specified as command line options:
+//
+//   -pkg-path android/soong=build/soong
+//   -pkg-path github.com/google/blueprint=build/blueprint
+//
+// The paths can be relative to the current working directory, or an absolute
+// path. Both packages and paths are compared with full directory names, so the
+// android/soong-test package wouldn't be mapped in the above case.
+//
+// Microfactory will ignore *_test.go files, and limits *_darwin.go and
+// *_linux.go files to MacOS and Linux respectively. It does not support build
+// tags or any other suffixes.
+//
+// Builds are incremental by package. All input files are hashed, and if the
+// hash of an input or dependency changes, the package is rebuilt.
+//
+// It also exposes the -trimpath option from go's compiler so that embedded
+// path names (such as in log.Llongfile) are relative paths instead of absolute
+// paths.
+//
+// If you don't have a previously built version of Microfactory, when used with
+// -s <microfactory_src_dir> -b <microfactory_bin_file>, Microfactory can
+// rebuild itself as necessary. Combined with a shell script like soong_ui.bash
+// that uses `go run` to run Microfactory for the first time, go programs can be
+// quickly bootstrapped entirely from source (and a standard go distribution).
+package main
+
+import (
+	"bytes"
+	"crypto/sha1"
+	"flag"
+	"fmt"
+	"go/ast"
+	"go/parser"
+	"go/token"
+	"io"
+	"io/ioutil"
+	"os"
+	"os/exec"
+	"path/filepath"
+	"runtime"
+	"sort"
+	"strconv"
+	"strings"
+	"sync"
+	"syscall"
+)
+
+var (
+	race    = false
+	verbose = false
+
+	goToolDir = filepath.Join(runtime.GOROOT(), "pkg", "tool", runtime.GOOS+"_"+runtime.GOARCH)
+)
+
+type GoPackage struct {
+	Name string
+
+	// Inputs
+	deps  []*GoPackage
+	files []string
+
+	// Outputs
+	pkgDir     string
+	output     string
+	hashResult []byte
+
+	// Status
+	mutex    sync.Mutex
+	compiled bool
+	failed   error
+	rebuilt  bool
+}
+
+// FindDeps searches all applicable go files in `path`, parses all of them
+// for import dependencies that exist in pkgMap, then recursively does the
+// same for all of those dependencies.
+func (p *GoPackage) FindDeps(path string, pkgMap *pkgPathMapping) error {
+	return p.findDeps(path, pkgMap, make(map[string]*GoPackage))
+}
+
+// findDeps is the recursive version of FindDeps. allPackages is the map of
+// all locally defined packages so that the same dependency of two different
+// packages is only resolved once.
+func (p *GoPackage) findDeps(path string, pkgMap *pkgPathMapping, allPackages map[string]*GoPackage) error {
+	// If this ever becomes too slow, we can look at reading the files once instead of twice
+	// But that just complicates things today, and we're already really fast.
+	foundPkgs, err := parser.ParseDir(token.NewFileSet(), path, func(fi os.FileInfo) bool {
+		name := fi.Name()
+		if fi.IsDir() || strings.HasSuffix(name, "_test.go") || name[0] == '.' || name[0] == '_' {
+			return false
+		}
+		if runtime.GOOS != "darwin" && strings.HasSuffix(name, "_darwin.go") {
+			return false
+		}
+		if runtime.GOOS != "linux" && strings.HasSuffix(name, "_linux.go") {
+			return false
+		}
+		return true
+	}, parser.ImportsOnly)
+	if err != nil {
+		return fmt.Errorf("Error parsing directory %q: %v", path, err)
+	}
+
+	var foundPkg *ast.Package
+	// foundPkgs is a map[string]*ast.Package, but we only want one package
+	if len(foundPkgs) != 1 {
+		return fmt.Errorf("Expected one package in %q, got %d", path, len(foundPkgs))
+	}
+	// Extract the first (and only) entry from the map.
+	for _, pkg := range foundPkgs {
+		foundPkg = pkg
+	}
+
+	var deps []string
+	localDeps := make(map[string]bool)
+
+	for filename, astFile := range foundPkg.Files {
+		p.files = append(p.files, filename)
+
+		for _, importSpec := range astFile.Imports {
+			name, err := strconv.Unquote(importSpec.Path.Value)
+			if err != nil {
+				return fmt.Errorf("%s: invalid quoted string: <%s> %v", filename, importSpec.Path.Value, err)
+			}
+
+			if pkg, ok := allPackages[name]; ok && pkg != nil {
+				if pkg != nil {
+					if _, ok := localDeps[name]; !ok {
+						deps = append(deps, name)
+						localDeps[name] = true
+					}
+				}
+				continue
+			}
+
+			var pkgPath string
+			if path, ok, err := pkgMap.Path(name); err != nil {
+				return err
+			} else if !ok {
+				// Probably in the stdlib, compiler will fail we a reasonable error message otherwise.
+				// Mark it as such so that we don't try to decode its path again.
+				allPackages[name] = nil
+				continue
+			} else {
+				pkgPath = path
+			}
+
+			pkg := &GoPackage{
+				Name: name,
+			}
+			deps = append(deps, name)
+			allPackages[name] = pkg
+			localDeps[name] = true
+
+			if err := pkg.findDeps(pkgPath, pkgMap, allPackages); err != nil {
+				return err
+			}
+		}
+	}
+
+	sort.Strings(p.files)
+
+	if verbose {
+		fmt.Fprintf(os.Stderr, "Package %q depends on %v\n", p.Name, deps)
+	}
+
+	for _, dep := range deps {
+		p.deps = append(p.deps, allPackages[dep])
+	}
+
+	return nil
+}
+
+func (p *GoPackage) Compile(outDir, trimPath string) error {
+	p.mutex.Lock()
+	defer p.mutex.Unlock()
+	if p.compiled {
+		return p.failed
+	}
+	p.compiled = true
+
+	// Build all dependencies in parallel, then fail if any of them failed.
+	var wg sync.WaitGroup
+	for _, dep := range p.deps {
+		wg.Add(1)
+		go func(dep *GoPackage) {
+			defer wg.Done()
+			dep.Compile(outDir, trimPath)
+		}(dep)
+	}
+	wg.Wait()
+	for _, dep := range p.deps {
+		if dep.failed != nil {
+			p.failed = dep.failed
+			return p.failed
+		}
+	}
+
+	p.pkgDir = filepath.Join(outDir, p.Name)
+	p.output = filepath.Join(p.pkgDir, p.Name) + ".a"
+	shaFile := p.output + ".hash"
+
+	hash := sha1.New()
+	fmt.Fprintln(hash, runtime.GOOS, runtime.GOARCH, runtime.Version())
+
+	cmd := exec.Command(filepath.Join(goToolDir, "compile"),
+		"-o", p.output,
+		"-p", p.Name,
+		"-complete", "-pack", "-nolocalimports")
+	if race {
+		cmd.Args = append(cmd.Args, "-race")
+		fmt.Fprintln(hash, "-race")
+	}
+	if trimPath != "" {
+		cmd.Args = append(cmd.Args, "-trimpath", trimPath)
+		fmt.Fprintln(hash, trimPath)
+	}
+	for _, dep := range p.deps {
+		cmd.Args = append(cmd.Args, "-I", dep.pkgDir)
+		hash.Write(dep.hashResult)
+	}
+	for _, filename := range p.files {
+		cmd.Args = append(cmd.Args, filename)
+		fmt.Fprintln(hash, filename)
+
+		// Hash the contents of the input files
+		f, err := os.Open(filename)
+		if err != nil {
+			f.Close()
+			err = fmt.Errorf("%s: %v", filename, err)
+			p.failed = err
+			return err
+		}
+		_, err = io.Copy(hash, f)
+		if err != nil {
+			f.Close()
+			err = fmt.Errorf("%s: %v", filename, err)
+			p.failed = err
+			return err
+		}
+		f.Close()
+	}
+	p.hashResult = hash.Sum(nil)
+
+	var rebuild bool
+	if _, err := os.Stat(p.output); err != nil {
+		rebuild = true
+	}
+	if !rebuild {
+		if oldSha, err := ioutil.ReadFile(shaFile); err == nil {
+			rebuild = !bytes.Equal(oldSha, p.hashResult)
+		} else {
+			rebuild = true
+		}
+	}
+
+	if !rebuild {
+		return nil
+	}
+
+	err := os.RemoveAll(p.pkgDir)
+	if err != nil {
+		err = fmt.Errorf("%s: %v", p.Name, err)
+		p.failed = err
+		return err
+	}
+
+	err = os.MkdirAll(filepath.Dir(p.output), 0777)
+	if err != nil {
+		err = fmt.Errorf("%s: %v", p.Name, err)
+		p.failed = err
+		return err
+	}
+
+	cmd.Stdin = nil
+	cmd.Stdout = os.Stdout
+	cmd.Stderr = os.Stderr
+	if verbose {
+		fmt.Fprintln(os.Stderr, cmd.Args)
+	}
+	err = cmd.Run()
+	if err != nil {
+		err = fmt.Errorf("%s: %v", p.Name, err)
+		p.failed = err
+		return err
+	}
+
+	err = ioutil.WriteFile(shaFile, p.hashResult, 0666)
+	if err != nil {
+		err = fmt.Errorf("%s: %v", p.Name, err)
+		p.failed = err
+		return err
+	}
+
+	p.rebuilt = true
+
+	return nil
+}
+
+func (p *GoPackage) Link(out string) error {
+	if p.Name != "main" {
+		return fmt.Errorf("Can only link main package")
+	}
+
+	shaFile := filepath.Join(filepath.Dir(out), "."+filepath.Base(out)+"_hash")
+
+	if !p.rebuilt {
+		if _, err := os.Stat(out); err != nil {
+			p.rebuilt = true
+		} else if oldSha, err := ioutil.ReadFile(shaFile); err != nil {
+			p.rebuilt = true
+		} else {
+			p.rebuilt = !bytes.Equal(oldSha, p.hashResult)
+		}
+	}
+	if !p.rebuilt {
+		return nil
+	}
+
+	err := os.Remove(shaFile)
+	if err != nil && !os.IsNotExist(err) {
+		return err
+	}
+	err = os.Remove(out)
+	if err != nil && !os.IsNotExist(err) {
+		return err
+	}
+
+	cmd := exec.Command(filepath.Join(goToolDir, "link"), "-o", out)
+	if race {
+		cmd.Args = append(cmd.Args, "-race")
+	}
+	for _, dep := range p.deps {
+		cmd.Args = append(cmd.Args, "-L", dep.pkgDir)
+	}
+	cmd.Args = append(cmd.Args, p.output)
+	cmd.Stdin = nil
+	cmd.Stdout = os.Stdout
+	cmd.Stderr = os.Stderr
+	if verbose {
+		fmt.Fprintln(os.Stderr, cmd.Args)
+	}
+	err = cmd.Run()
+	if err != nil {
+		return err
+	}
+
+	return ioutil.WriteFile(shaFile, p.hashResult, 0666)
+}
+
+// rebuildMicrofactory checks to see if microfactory itself needs to be rebuilt,
+// and if does, it will launch a new copy instead of returning.
+func rebuildMicrofactory(mybin, mysrc string, pkgMap *pkgPathMapping) {
+	intermediates := filepath.Join(filepath.Dir(mybin), "."+filepath.Base(mybin)+"_intermediates")
+
+	err := os.MkdirAll(intermediates, 0777)
+	if err != nil {
+		fmt.Fprintln(os.Stderr, "Failed to create intermediates directory: %v", err)
+		os.Exit(1)
+	}
+
+	pkg := &GoPackage{
+		Name: "main",
+	}
+
+	if err := pkg.FindDeps(mysrc, pkgMap); err != nil {
+		fmt.Fprintln(os.Stderr, err)
+		os.Exit(1)
+	}
+
+	if err := pkg.Compile(intermediates, mysrc); err != nil {
+		fmt.Fprintln(os.Stderr, err)
+		os.Exit(1)
+	}
+
+	if err := pkg.Link(mybin); err != nil {
+		fmt.Fprintln(os.Stderr, err)
+		os.Exit(1)
+	}
+
+	if !pkg.rebuilt {
+		return
+	}
+
+	cmd := exec.Command(mybin, os.Args[1:]...)
+	cmd.Stdin = os.Stdin
+	cmd.Stdout = os.Stdout
+	cmd.Stderr = os.Stderr
+	if err := cmd.Run(); err == nil {
+		os.Exit(0)
+	} else if e, ok := err.(*exec.ExitError); ok {
+		os.Exit(e.ProcessState.Sys().(syscall.WaitStatus).ExitStatus())
+	}
+	os.Exit(1)
+}
+
+func main() {
+	var output, mysrc, mybin, trimPath string
+	var pkgMap pkgPathMapping
+
+	flags := flag.NewFlagSet("", flag.ExitOnError)
+	flags.BoolVar(&race, "race", false, "enable data race detection.")
+	flags.BoolVar(&verbose, "v", false, "Verbose")
+	flags.StringVar(&output, "o", "", "Output file")
+	flags.StringVar(&mysrc, "s", "", "Microfactory source directory (for rebuilding microfactory if necessary)")
+	flags.StringVar(&mybin, "b", "", "Microfactory binary location")
+	flags.StringVar(&trimPath, "trimpath", "", "remove prefix from recorded source file paths")
+	flags.Var(&pkgMap, "pkg-path", "Mapping of package prefixes to file paths")
+	err := flags.Parse(os.Args[1:])
+
+	if err == flag.ErrHelp || flags.NArg() != 1 || output == "" {
+		fmt.Fprintln(os.Stderr, "Usage:", os.Args[0], "-o out/binary <main-package>")
+		flags.PrintDefaults()
+		os.Exit(1)
+	}
+
+	if mybin != "" && mysrc != "" {
+		rebuildMicrofactory(mybin, mysrc, &pkgMap)
+	}
+
+	mainPackage := &GoPackage{
+		Name: "main",
+	}
+
+	if path, ok, err := pkgMap.Path(flags.Arg(0)); err != nil {
+		fmt.Fprintln(os.Stderr, "Error finding main path:", err)
+		os.Exit(1)
+	} else if !ok {
+		fmt.Fprintln(os.Stderr, "Cannot find path for", flags.Arg(0))
+	} else {
+		if err := mainPackage.FindDeps(path, &pkgMap); err != nil {
+			fmt.Fprintln(os.Stderr, err)
+			os.Exit(1)
+		}
+	}
+
+	intermediates := filepath.Join(filepath.Dir(output), "."+filepath.Base(output)+"_intermediates")
+
+	err = os.MkdirAll(intermediates, 0777)
+	if err != nil {
+		fmt.Fprintln(os.Stderr, "Failed to create intermediates directory: %ve", err)
+		os.Exit(1)
+	}
+
+	err = mainPackage.Compile(intermediates, trimPath)
+	if err != nil {
+		fmt.Fprintln(os.Stderr, "Failed to compile:", err)
+		os.Exit(1)
+	}
+
+	err = mainPackage.Link(output)
+	if err != nil {
+		fmt.Fprintln(os.Stderr, "Failed to link:", err)
+		os.Exit(1)
+	}
+}
+
+// pkgPathMapping can be used with flag.Var to parse -pkg-path arguments of
+// <package-prefix>=<path-prefix> mappings.
+type pkgPathMapping struct {
+	pkgs []string
+
+	paths map[string]string
+}
+
+func (pkgPathMapping) String() string {
+	return "<package-prefix>=<path-prefix>"
+}
+
+func (p *pkgPathMapping) Set(value string) error {
+	equalPos := strings.Index(value, "=")
+	if equalPos == -1 {
+		return fmt.Errorf("Argument must be in the form of: %q", p.String())
+	}
+
+	pkgPrefix := strings.TrimSuffix(value[:equalPos], "/")
+	pathPrefix := strings.TrimSuffix(value[equalPos+1:], "/")
+
+	if p.paths == nil {
+		p.paths = make(map[string]string)
+	}
+	if _, ok := p.paths[pkgPrefix]; ok {
+		return fmt.Errorf("Duplicate package prefix: %q", pkgPrefix)
+	}
+
+	p.pkgs = append(p.pkgs, pkgPrefix)
+	p.paths[pkgPrefix] = pathPrefix
+
+	return nil
+}
+
+// Path takes a package name, applies the path mappings and returns the resulting path.
+//
+// If the package isn't mapped, we'll return false to prevent compilation attempts.
+func (p *pkgPathMapping) Path(pkg string) (string, bool, error) {
+	if p.paths == nil {
+		return "", false, fmt.Errorf("No package mappings")
+	}
+
+	for _, pkgPrefix := range p.pkgs {
+		if pkg == pkgPrefix {
+			return p.paths[pkgPrefix], true, nil
+		} else if strings.HasPrefix(pkg, pkgPrefix+"/") {
+			return filepath.Join(p.paths[pkgPrefix], strings.TrimPrefix(pkg, pkgPrefix+"/")), true, nil
+		}
+	}
+
+	return "", false, nil
+}
diff --git a/cmd/microfactory/microfactory_test.go b/cmd/microfactory/microfactory_test.go
new file mode 100644
index 00000000..296a8446
--- /dev/null
+++ b/cmd/microfactory/microfactory_test.go
@@ -0,0 +1,422 @@
+// Copyright 2017 Google Inc. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package main
+
+import (
+	"flag"
+	"io/ioutil"
+	"os"
+	"path/filepath"
+	"reflect"
+	"runtime"
+	"testing"
+	"time"
+)
+
+func TestSimplePackagePathMap(t *testing.T) {
+	t.Parallel()
+
+	var pkgMap pkgPathMapping
+	flags := flag.NewFlagSet("", flag.ContinueOnError)
+	flags.Var(&pkgMap, "m", "")
+	err := flags.Parse([]string{
+		"-m", "android/soong=build/soong/",
+		"-m", "github.com/google/blueprint/=build/blueprint",
+	})
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	compare := func(got, want interface{}) {
+		if !reflect.DeepEqual(got, want) {
+			t.Errorf("Unexpected values in .pkgs:\nwant: %v\n got: %v",
+				want, got)
+		}
+	}
+
+	wantPkgs := []string{"android/soong", "github.com/google/blueprint"}
+	compare(pkgMap.pkgs, wantPkgs)
+	compare(pkgMap.paths[wantPkgs[0]], "build/soong")
+	compare(pkgMap.paths[wantPkgs[1]], "build/blueprint")
+
+	got, ok, err := pkgMap.Path("android/soong/ui/test")
+	if err != nil {
+		t.Error("Unexpected error in pkgMap.Path(soong):", err)
+	} else if !ok {
+		t.Error("Expected a result from pkgMap.Path(soong)")
+	} else {
+		compare(got, "build/soong/ui/test")
+	}
+
+	got, ok, err = pkgMap.Path("github.com/google/blueprint")
+	if err != nil {
+		t.Error("Unexpected error in pkgMap.Path(blueprint):", err)
+	} else if !ok {
+		t.Error("Expected a result from pkgMap.Path(blueprint)")
+	} else {
+		compare(got, "build/blueprint")
+	}
+}
+
+func TestBadPackagePathMap(t *testing.T) {
+	t.Parallel()
+
+	var pkgMap pkgPathMapping
+	if _, _, err := pkgMap.Path("testing"); err == nil {
+		t.Error("Expected error if no maps are specified")
+	}
+	if err := pkgMap.Set(""); err == nil {
+		t.Error("Expected error with blank argument, but none returned")
+	}
+	if err := pkgMap.Set("a=a"); err != nil {
+		t.Error("Unexpected error: %v", err)
+	}
+	if err := pkgMap.Set("a=b"); err == nil {
+		t.Error("Expected error with duplicate package prefix, but none returned")
+	}
+	if _, ok, err := pkgMap.Path("testing"); err != nil {
+		t.Error("Unexpected error: %v", err)
+	} else if ok {
+		t.Error("Expected testing to be consider in the stdlib")
+	}
+}
+
+// TestSingleBuild ensures that just a basic build works.
+func TestSingleBuild(t *testing.T) {
+	t.Parallel()
+
+	setupDir(t, func(dir string, loadPkg loadPkgFunc) {
+		// The output binary
+		out := filepath.Join(dir, "out", "test")
+
+		pkg := loadPkg()
+
+		if err := pkg.Compile(filepath.Join(dir, "out"), ""); err != nil {
+			t.Fatalf("Got error when compiling:", err)
+		}
+
+		if err := pkg.Link(out); err != nil {
+			t.Fatal("Got error when linking:", err)
+		}
+
+		if _, err := os.Stat(out); err != nil {
+			t.Error("Cannot stat output:", err)
+		}
+	})
+}
+
+// testBuildAgain triggers two builds, running the modify function in between
+// each build. It verifies that the second build did or did not actually need
+// to rebuild anything based on the shouldRebuild argument.
+func testBuildAgain(t *testing.T,
+	shouldRecompile, shouldRelink bool,
+	modify func(dir string, loadPkg loadPkgFunc),
+	after func(pkg *GoPackage)) {
+
+	t.Parallel()
+
+	setupDir(t, func(dir string, loadPkg loadPkgFunc) {
+		// The output binary
+		out := filepath.Join(dir, "out", "test")
+
+		pkg := loadPkg()
+
+		if err := pkg.Compile(filepath.Join(dir, "out"), ""); err != nil {
+			t.Fatal("Got error when compiling:", err)
+		}
+
+		if err := pkg.Link(out); err != nil {
+			t.Fatal("Got error when linking:", err)
+		}
+
+		var firstTime time.Time
+		if stat, err := os.Stat(out); err == nil {
+			firstTime = stat.ModTime()
+		} else {
+			t.Fatal("Failed to stat output file:", err)
+		}
+
+		// mtime on HFS+ (the filesystem on darwin) are stored with 1
+		// second granularity, so the timestamp checks will fail unless
+		// we wait at least a second. Sleeping 1.1s to be safe.
+		if runtime.GOOS == "darwin" {
+			time.Sleep(1100 * time.Millisecond)
+		}
+
+		modify(dir, loadPkg)
+
+		pkg = loadPkg()
+
+		if err := pkg.Compile(filepath.Join(dir, "out"), ""); err != nil {
+			t.Fatal("Got error when compiling:", err)
+		}
+		if shouldRecompile {
+			if !pkg.rebuilt {
+				t.Fatal("Package should have recompiled, but was not recompiled.")
+			}
+		} else {
+			if pkg.rebuilt {
+				t.Fatal("Package should not have needed to be recompiled, but was recompiled.")
+			}
+		}
+
+		if err := pkg.Link(out); err != nil {
+			t.Fatal("Got error while linking:", err)
+		}
+		if shouldRelink {
+			if !pkg.rebuilt {
+				t.Error("Package should have relinked, but was not relinked.")
+			}
+		} else {
+			if pkg.rebuilt {
+				t.Error("Package should not have needed to be relinked, but was relinked.")
+			}
+		}
+
+		if stat, err := os.Stat(out); err == nil {
+			if shouldRelink {
+				if stat.ModTime() == firstTime {
+					t.Error("Output timestamp should be different, but both were", firstTime)
+				}
+			} else {
+				if stat.ModTime() != firstTime {
+					t.Error("Output timestamp should be the same.")
+					t.Error(" first:", firstTime)
+					t.Error("second:", stat.ModTime())
+				}
+			}
+		} else {
+			t.Fatal("Failed to stat output file:", err)
+		}
+
+		after(pkg)
+	})
+}
+
+// TestRebuildAfterNoChanges ensures that we don't rebuild if nothing
+// changes
+func TestRebuildAfterNoChanges(t *testing.T) {
+	testBuildAgain(t, false, false, func(dir string, loadPkg loadPkgFunc) {}, func(pkg *GoPackage) {})
+}
+
+// TestRebuildAfterTimestamp ensures that we don't rebuild because
+// timestamps of important files have changed. We should only rebuild if the
+// content hashes are different.
+func TestRebuildAfterTimestampChange(t *testing.T) {
+	testBuildAgain(t, false, false, func(dir string, loadPkg loadPkgFunc) {
+		// Ensure that we've spent some amount of time asleep
+		time.Sleep(100 * time.Millisecond)
+
+		newTime := time.Now().Local()
+		os.Chtimes(filepath.Join(dir, "test.fact"), newTime, newTime)
+		os.Chtimes(filepath.Join(dir, "main/main.go"), newTime, newTime)
+		os.Chtimes(filepath.Join(dir, "a/a.go"), newTime, newTime)
+		os.Chtimes(filepath.Join(dir, "a/b.go"), newTime, newTime)
+		os.Chtimes(filepath.Join(dir, "b/a.go"), newTime, newTime)
+	}, func(pkg *GoPackage) {})
+}
+
+// TestRebuildAfterGoChange ensures that we rebuild after a content change
+// to a package's go file.
+func TestRebuildAfterGoChange(t *testing.T) {
+	testBuildAgain(t, true, true, func(dir string, loadPkg loadPkgFunc) {
+		if err := ioutil.WriteFile(filepath.Join(dir, "a", "a.go"), []byte(go_a_a+"\n"), 0666); err != nil {
+			t.Fatal("Error writing a/a.go:", err)
+		}
+	}, func(pkg *GoPackage) {
+		if !pkg.deps[0].rebuilt {
+			t.Fatal("android/soong/a should have rebuilt")
+		}
+		if !pkg.deps[1].rebuilt {
+			t.Fatal("android/soong/b should have rebuilt")
+		}
+	})
+}
+
+// TestRebuildAfterMainChange ensures that we don't rebuild any dependencies
+// if only the main package's go files are touched.
+func TestRebuildAfterMainChange(t *testing.T) {
+	testBuildAgain(t, true, true, func(dir string, loadPkg loadPkgFunc) {
+		if err := ioutil.WriteFile(filepath.Join(dir, "main", "main.go"), []byte(go_main_main+"\n"), 0666); err != nil {
+			t.Fatal("Error writing main/main.go:", err)
+		}
+	}, func(pkg *GoPackage) {
+		if pkg.deps[0].rebuilt {
+			t.Fatal("android/soong/a should not have rebuilt")
+		}
+		if pkg.deps[1].rebuilt {
+			t.Fatal("android/soong/b should not have rebuilt")
+		}
+	})
+}
+
+// TestRebuildAfterRemoveOut ensures that we rebuild if the output file is
+// missing, even if everything else doesn't need rebuilding.
+func TestRebuildAfterRemoveOut(t *testing.T) {
+	testBuildAgain(t, false, true, func(dir string, loadPkg loadPkgFunc) {
+		if err := os.Remove(filepath.Join(dir, "out", "test")); err != nil {
+			t.Fatal("Failed to remove output:", err)
+		}
+	}, func(pkg *GoPackage) {})
+}
+
+// TestRebuildAfterPartialBuild ensures that even if the build was interrupted
+// between the recompile and relink stages, we'll still relink when we run again.
+func TestRebuildAfterPartialBuild(t *testing.T) {
+	testBuildAgain(t, false, true, func(dir string, loadPkg loadPkgFunc) {
+		if err := ioutil.WriteFile(filepath.Join(dir, "main", "main.go"), []byte(go_main_main+"\n"), 0666); err != nil {
+			t.Fatal("Error writing main/main.go:", err)
+		}
+
+		pkg := loadPkg()
+
+		if err := pkg.Compile(filepath.Join(dir, "out"), ""); err != nil {
+			t.Fatal("Got error when compiling:", err)
+		}
+		if !pkg.rebuilt {
+			t.Fatal("Package should have recompiled, but was not recompiled.")
+		}
+	}, func(pkg *GoPackage) {})
+}
+
+// BenchmarkInitialBuild computes how long a clean build takes (for tiny test
+// inputs).
+func BenchmarkInitialBuild(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		setupDir(b, func(dir string, loadPkg loadPkgFunc) {
+			pkg := loadPkg()
+			if err := pkg.Compile(filepath.Join(dir, "out"), ""); err != nil {
+				b.Fatal("Got error when compiling:", err)
+			}
+
+			if err := pkg.Link(filepath.Join(dir, "out", "test")); err != nil {
+				b.Fatal("Got error when linking:", err)
+			}
+		})
+	}
+}
+
+// BenchmarkMinIncrementalBuild computes how long an incremental build that
+// doesn't actually need to build anything takes.
+func BenchmarkMinIncrementalBuild(b *testing.B) {
+	setupDir(b, func(dir string, loadPkg loadPkgFunc) {
+		pkg := loadPkg()
+
+		if err := pkg.Compile(filepath.Join(dir, "out"), ""); err != nil {
+			b.Fatal("Got error when compiling:", err)
+		}
+
+		if err := pkg.Link(filepath.Join(dir, "out", "test")); err != nil {
+			b.Fatal("Got error when linking:", err)
+		}
+
+		b.ResetTimer()
+
+		for i := 0; i < b.N; i++ {
+			pkg := loadPkg()
+
+			if err := pkg.Compile(filepath.Join(dir, "out"), ""); err != nil {
+				b.Fatal("Got error when compiling:", err)
+			}
+
+			if err := pkg.Link(filepath.Join(dir, "out", "test")); err != nil {
+				b.Fatal("Got error when linking:", err)
+			}
+
+			if pkg.rebuilt {
+				b.Fatal("Should not have rebuilt anything")
+			}
+		}
+	})
+}
+
+///////////////////////////////////////////////////////
+// Templates used to create fake compilable packages //
+///////////////////////////////////////////////////////
+
+const go_main_main = `
+package main
+import (
+	"fmt"
+	"android/soong/a"
+	"android/soong/b"
+)
+func main() {
+	fmt.Println(a.Stdout, b.Stdout)
+}
+`
+
+const go_a_a = `
+package a
+import "os"
+var Stdout = os.Stdout
+`
+
+const go_a_b = `
+package a
+`
+
+const go_b_a = `
+package b
+import "android/soong/a"
+var Stdout = a.Stdout
+`
+
+type T interface {
+	Fatal(args ...interface{})
+	Fatalf(format string, args ...interface{})
+}
+
+type loadPkgFunc func() *GoPackage
+
+func setupDir(t T, test func(dir string, loadPkg loadPkgFunc)) {
+	dir, err := ioutil.TempDir("", "test")
+	if err != nil {
+		t.Fatalf("Error creating temporary directory: %#v", err)
+	}
+	defer os.RemoveAll(dir)
+
+	writeFile := func(name, contents string) {
+		if err := ioutil.WriteFile(filepath.Join(dir, name), []byte(contents), 0666); err != nil {
+			t.Fatalf("Error writing %q: %#v", name, err)
+		}
+	}
+	mkdir := func(name string) {
+		if err := os.Mkdir(filepath.Join(dir, name), 0777); err != nil {
+			t.Fatalf("Error creating %q directory: %#v", name, err)
+		}
+	}
+	mkdir("main")
+	mkdir("a")
+	mkdir("b")
+	writeFile("main/main.go", go_main_main)
+	writeFile("a/a.go", go_a_a)
+	writeFile("a/b.go", go_a_b)
+	writeFile("b/a.go", go_b_a)
+
+	loadPkg := func() *GoPackage {
+		pkg := &GoPackage{
+			Name: "main",
+		}
+		pkgMap := &pkgPathMapping{}
+		pkgMap.Set("android/soong=" + dir)
+		if err := pkg.FindDeps(filepath.Join(dir, "main"), pkgMap); err != nil {
+			t.Fatalf("Error finding deps: %v", err)
+		}
+		return pkg
+	}
+
+	test(dir, loadPkg)
+}