diff --git a/datahopper/go/bot_metrics/bot_metrics.go b/datahopper/go/bot_metrics/bot_metrics.go
index 58a5b0c..444ea68 100644
--- a/datahopper/go/bot_metrics/bot_metrics.go
+++ b/datahopper/go/bot_metrics/bot_metrics.go
@@ -263,10 +263,10 @@
 			}
 
 			// For each commit covered by the task, record the lag time.
-			if err := c.Recurse(func(commit *repograph.Commit) (bool, error) {
+			if err := c.Recurse(func(commit *repograph.Commit) error {
 				// Prevent us from tracing through the entire commit history.
 				if commit.Timestamp.Before(now.Add(-COMMIT_TASK_WINDOW)) {
-					return false, nil
+					return repograph.ErrStopRecursing
 				}
 
 				// Get the cached data for this commit.
@@ -292,7 +292,7 @@
 						})
 						if err == task_cfg_cache.ErrNoSuchEntry {
 							sklog.Warningf("TaskCfgCache has no entry for %s@%s.", repoUrl, commit.Hash)
-							return true, nil
+							return nil
 						} else if err != nil {
 							// Some old commits only have tasks without jobs. Skip them.
 							if strings.Contains(err.Error(), "is not reachable by any Job") {
@@ -300,9 +300,9 @@
 									Tasks: map[string]*specs.TaskSpec{},
 									Jobs:  map[string]*specs.JobSpec{},
 								}
-								return false, nil
+								return repograph.ErrStopRecursing
 							}
-							return false, err
+							return err
 						}
 						cfg = c
 						cfgs[commit] = cfg
@@ -320,7 +320,7 @@
 					}
 
 					if _, ok := cfg.Tasks[t.Name]; !ok {
-						return false, nil
+						return repograph.ErrStopRecursing
 					}
 				}
 
@@ -331,12 +331,12 @@
 				// one, record the lag time and keep recursing.
 				if best, ok := cData.Tasks[t.Name]; !ok || best > d {
 					cData.Tasks[t.Name] = d
-					return true, nil
+					return nil
 				}
 
 				// This commit was covered by a previous task,
 				// so all previous commits will also be covered.
-				return false, nil
+				return repograph.ErrStopRecursing
 			}); err != nil {
 				return err
 			}
diff --git a/datahopper/go/datahopper/jobs.go b/datahopper/go/datahopper/jobs.go
index f63bba9..835cb2b 100644
--- a/datahopper/go/datahopper/jobs.go
+++ b/datahopper/go/datahopper/jobs.go
@@ -380,19 +380,19 @@
 	}
 	var commit *repograph.Commit
 	var cfg *specs.TasksCfg
-	if err := head.Recurse(func(c *repograph.Commit) (bool, error) {
+	if err := head.Recurse(func(c *repograph.Commit) error {
 		tasksCfg, err := tcc.Get(ctx, types.RepoState{
 			Repo:     repoUrl,
 			Revision: c.Hash,
 		})
 		if err == task_cfg_cache.ErrNoSuchEntry {
-			return true, nil
+			return nil
 		} else if err != nil {
-			return false, err
+			return err
 		}
 		cfg = tasksCfg
 		commit = c
-		return false, nil
+		return repograph.ErrStopRecursing
 	}); err != nil {
 		return nil, nil, err
 	}
@@ -432,12 +432,12 @@
 
 		// Iterate backwards to find the most-recently tested commit. We're not going to worry about
 		// merges -- if a job was run on both branches, we'll use the first commit we come across.
-		if err := head.Recurse(func(c *repograph.Commit) (bool, error) {
+		if err := head.Recurse(func(c *repograph.Commit) error {
 			// Stop if this commit is outside the scheduling window.
 			if in, err := m.window.TestCommitHash(repoUrl, c.Hash); err != nil {
-				return false, sklog.FmtErrorf("TestCommitHash: %s", err)
+				return sklog.FmtErrorf("TestCommitHash: %s", err)
 			} else if !in {
-				return false, nil
+				return repograph.ErrStopRecursing
 			}
 			rs := types.RepoState{
 				Repo:     repoUrl,
@@ -447,7 +447,7 @@
 			for name := range todo {
 				jobs, err := m.jCache.GetJobsByRepoState(name, rs)
 				if err != nil {
-					return false, sklog.FmtErrorf("GetJobsByRepoState: %s", err)
+					return sklog.FmtErrorf("GetJobsByRepoState: %s", err)
 				}
 				for _, j := range jobs {
 					if j.Done() {
@@ -457,12 +457,12 @@
 				}
 			}
 			if len(todo) == 0 {
-				return false, nil
+				return repograph.ErrStopRecursing
 			}
 			// Check that the remaining JobSpecs are still valid at this commit.
 			taskCfg, err := m.taskCfgCache.Get(ctx, rs)
 			if err != nil {
-				return false, sklog.FmtErrorf("Error reading TaskCfg for %q at %q: %s", repoUrl, c.Hash, err)
+				return sklog.FmtErrorf("Error reading TaskCfg for %q at %q: %s", repoUrl, c.Hash, err)
 			}
 			for name := range todo {
 				if _, ok := taskCfg.Jobs[name]; !ok {
@@ -472,7 +472,10 @@
 					times[name] = c.Timestamp
 				}
 			}
-			return len(todo) > 0, nil
+			if len(todo) > 0 {
+				return nil
+			}
+			return repograph.ErrStopRecursing
 		}); err != nil {
 			return err
 		}
diff --git a/datahopper/go/datahopper/jobs_test.go b/datahopper/go/datahopper/jobs_test.go
index 25f54d2..a53d12a 100644
--- a/datahopper/go/datahopper/jobs_test.go
+++ b/datahopper/go/datahopper/jobs_test.go
@@ -465,7 +465,7 @@
 	check("0", c1age, c2age)
 
 	// Revert back to c1 (no Perf task) and check that Perf job disappears.
-	content, err := repo.Repo().GetFile(ctx, "infra/bots/tasks.json", c1)
+	content, err := repo.GetFile(ctx, "infra/bots/tasks.json", c1)
 	assert.NoError(t, err)
 	gb.Add(ctx, "infra/bots/tasks.json", content)
 	c3 := gb.CommitMsgAt(ctx, "c3", c1time.Add(10*time.Second)) // 5 seconds after c2
diff --git a/datahopper/go/datahopper/main.go b/datahopper/go/datahopper/main.go
index ee0d04d..95d20ce 100644
--- a/datahopper/go/datahopper/main.go
+++ b/datahopper/go/datahopper/main.go
@@ -174,18 +174,10 @@
 		skiaGauge := metrics2.GetInt64Metric("repo_commits", map[string]string{"repo": "skia"})
 		infraGauge := metrics2.GetInt64Metric("repo_commits", map[string]string{"repo": "infra"})
 		for range time.Tick(5 * time.Minute) {
-			nSkia, err := repos[common.REPO_SKIA].Repo().NumCommits(ctx)
-			if err != nil {
-				sklog.Errorf("Failed to get number of commits for Skia: %s", err)
-			} else {
-				skiaGauge.Update(nSkia)
-			}
-			nInfra, err := repos[common.REPO_SKIA_INFRA].Repo().NumCommits(ctx)
-			if err != nil {
-				sklog.Errorf("Failed to get number of commits for Infra: %s", err)
-			} else {
-				infraGauge.Update(nInfra)
-			}
+			nSkia := repos[common.REPO_SKIA].Len()
+			skiaGauge.Update(int64(nSkia))
+			nInfra := repos[common.REPO_SKIA_INFRA].Len()
+			infraGauge.Update(int64(nInfra))
 		}
 	}()
 
diff --git a/go/git/repograph/graph.go b/go/git/repograph/graph.go
index 5ab447b..4943bd0 100644
--- a/go/git/repograph/graph.go
+++ b/go/git/repograph/graph.go
@@ -7,6 +7,7 @@
 import (
 	"context"
 	"encoding/gob"
+	"errors"
 	"fmt"
 	"io"
 	"path"
@@ -27,55 +28,56 @@
 	CACHE_FILE = "sk_gitrepo.gob"
 )
 
+var (
+	ErrStopRecursing = errors.New("Stop recursing")
+)
+
 // Commit represents a commit in a Git repo.
 type Commit struct {
 	*vcsinfo.LongCommit
 	ParentIndices []int
+	parents       []*Commit
 	repo          *Graph
 }
 
 // Parents returns the parents of this commit.
 func (c *Commit) GetParents() []*Commit {
-	rv := make([]*Commit, 0, len(c.ParentIndices))
-	for _, idx := range c.ParentIndices {
-		rv = append(rv, c.repo.commitsData[idx])
-	}
-	return rv
+	return c.parents
 }
 
 // Recurse runs the given function recursively over commit history, starting
 // at the given commit. The function accepts the current Commit as a parameter.
-// Returning false from the function indicates that recursion should stop for
-// the current branch, however, recursion will continue for any other branches
-// until they are similarly terminated. Returning an error causes recursion to
-// stop without properly terminating other branchces. The error will bubble to
-// the top and be returned. Here's an example of printing out the entire
-// ancestry of a given commit:
+// Returning ErrStopRecursing from the function indicates that recursion should
+// stop for the current branch, however, recursion will continue for any other
+// branches until they are similarly terminated. Returning any other error
+// causes recursion to stop without properly terminating other branches. The
+// error will bubble to the top and be returned. Here's an example of printing
+// out the entire ancestry of a given commit:
 //
-// commit.Recurse(func(c *Commit) (bool, error) {
+// commit.Recurse(func(c *Commit) error {
 // 	sklog.Info(c.Hash)
-// 	return true, nil
+// 	return nil
 // })
-func (c *Commit) Recurse(f func(*Commit) (bool, error)) error {
-	return c.recurse(f, make(map[*Commit]bool, len(c.repo.commitsData)))
+func (c *Commit) Recurse(f func(*Commit) error) error {
+	return c.recurse(f, make(map[*Commit]bool, c.repo.Len()))
 }
 
 // recurse is a helper function used by Recurse.
-func (c *Commit) recurse(f func(*Commit) (bool, error), visited map[*Commit]bool) error {
+func (c *Commit) recurse(f func(*Commit) error, visited map[*Commit]bool) (rvErr error) {
 	// For large repos, we may not have enough stack space to recurse
 	// through the whole commit history. Since most commits only have
 	// one parent, avoid recursion when possible.
 	for {
 		visited[c] = true
-		keepGoing, err := f(c)
-		if err != nil {
+		if err := f(c); err == ErrStopRecursing {
+			return nil
+		} else if err != nil {
 			return err
 		}
-		if !keepGoing {
+		if len(c.parents) == 0 {
 			return nil
-		}
-		if len(c.ParentIndices) == 1 {
-			p := c.repo.commitsData[c.ParentIndices[0]]
+		} else if len(c.parents) == 1 {
+			p := c.parents[0]
 			if visited[p] {
 				return nil
 			}
@@ -84,27 +86,43 @@
 			break
 		}
 	}
-	for _, parentIdx := range c.ParentIndices {
-		p := c.repo.commitsData[parentIdx]
-		if visited[p] {
-			continue
-		}
-		if err := p.recurse(f, visited); err != nil {
-			return err
+	if len(c.Parents) > 1 {
+		for _, p := range c.parents {
+			if visited[p] {
+				continue
+			}
+			if err := p.recurse(f, visited); err != nil {
+				return err
+			}
 		}
 	}
 	return nil
 }
 
+// AllCommits returns the hashes of all commits reachable from this Commit, in
+// reverse topological order.
+func (c *Commit) AllCommits() ([]string, error) {
+	commits := make(map[*Commit]bool, c.repo.Len())
+	if err := c.recurse(func(c *Commit) error {
+		return nil
+	}, commits); err != nil {
+		return nil, err
+	}
+
+	// Topologically sort the commits.
+	sorted := topologicalSortHelper(commits)
+	return CommitSlice(sorted).Hashes(), nil
+}
+
 // HasAncestor returns true iff the given commit is an ancestor of this commit.
 func (c *Commit) HasAncestor(other string) bool {
 	found := false
-	if err := c.Recurse(func(commit *Commit) (bool, error) {
+	if err := c.Recurse(func(commit *Commit) error {
 		if commit.Hash == other {
 			found = true
-			return false, nil
+			return ErrStopRecursing
 		}
-		return true, nil
+		return nil
 	}); err != nil {
 		// Our function doesn't return an error, so we shouldn't hit
 		// this case.
@@ -113,11 +131,25 @@
 	return found
 }
 
+// Less compares this Commit to the other Commit and returns true if it is
+// considered "less" than the other. This is used as a helper function in
+// sorting to ensure stability. Uses the timestamp as the primary sort function
+// and the hash as a tie breaker. Note that, because we sort in reverse
+// chronological order, this has the opposite meaning that it seems it should.
+func (c *Commit) Less(other *Commit) bool {
+	if c.Timestamp.Equal(other.Timestamp) {
+		// If the timestamps are equal, just use the commit hash as an
+		// arbitrary way of comparing the two.
+		return c.Hash > other.Hash
+	}
+	return c.Timestamp.After(other.Timestamp)
+}
+
 // Helpers for sorting.
 type CommitSlice []*Commit
 
 func (s CommitSlice) Len() int           { return len(s) }
-func (s CommitSlice) Less(a, b int) bool { return s[a].Timestamp.After(s[b].Timestamp) }
+func (s CommitSlice) Less(a, b int) bool { return s[a].Less(s[b]) }
 func (s CommitSlice) Swap(a, b int)      { s[a], s[b] = s[b], s[a] }
 
 // Hashes returns a slice of commit hashes corresponding to the commits in s.
@@ -134,8 +166,9 @@
 	branches    []*git.Branch
 	commits     map[string]int
 	commitsData []*Commit
-	mtx         sync.RWMutex
+	graphMtx    sync.RWMutex
 	repo        *git.Repo
+	repoMtx     sync.Mutex
 }
 
 // gobGraph is a utility struct used for serializing a Graph using gob.
@@ -166,6 +199,9 @@
 	}
 	for _, c := range rv.commitsData {
 		c.repo = rv
+		for _, parentIdx := range c.ParentIndices {
+			c.parents = append(c.parents, rv.commitsData[parentIdx])
+		}
 	}
 	return rv, nil
 }
@@ -182,27 +218,24 @@
 	return New(repo)
 }
 
-// Repo returns the underlying git.Repo object.
-func (r *Graph) Repo() *git.Repo {
-	return r.repo
-}
-
 // Len returns the number of commits in the repo.
 func (r *Graph) Len() int {
-	r.mtx.RLock()
-	defer r.mtx.RUnlock()
+	r.graphMtx.RLock()
+	defer r.graphMtx.RUnlock()
 	return len(r.commitsData)
 }
 
+// addCommit adds the commit with the given hash to the Graph. Assumes that the
+// caller holds r.repoMtx and r.graphMtx.
 func (r *Graph) addCommit(ctx context.Context, hash string) error {
 	d, err := r.repo.Details(ctx, hash)
 	if err != nil {
 		return fmt.Errorf("repograph.Graph: Failed to obtain Git commit details: %s", err)
 	}
 
-	var parents []int
+	var parentIndices []int
+	var parents []*Commit
 	if len(d.Parents) > 0 {
-		parentIndices := make([]int, 0, len(d.Parents))
 		for _, h := range d.Parents {
 			if h == "" {
 				continue
@@ -212,15 +245,14 @@
 				return fmt.Errorf("repograph.Graph: Could not find parent commit %q", h)
 			}
 			parentIndices = append(parentIndices, p)
-		}
-		if len(parentIndices) > 0 {
-			parents = parentIndices
+			parents = append(parents, r.commitsData[p])
 		}
 	}
 
 	c := &Commit{
 		LongCommit:    d,
-		ParentIndices: parents,
+		ParentIndices: parentIndices,
+		parents:       parents,
 		repo:          r,
 	}
 	r.commits[hash] = len(r.commitsData)
@@ -243,8 +275,8 @@
 }
 
 func (r *Graph) update(ctx context.Context, returnNewCommits bool) ([]*vcsinfo.LongCommit, error) {
-	r.mtx.Lock()
-	defer r.mtx.Unlock()
+	r.repoMtx.Lock()
+	defer r.repoMtx.Unlock()
 
 	// Update the local copy.
 	sklog.Infof("Updating repograph.Graph...")
@@ -260,6 +292,8 @@
 	}
 
 	// Load new commits from the repo.
+	r.graphMtx.Lock()
+	defer r.graphMtx.Unlock()
 	var newCommits []*vcsinfo.LongCommit
 	if returnNewCommits {
 		newCommits = []*vcsinfo.LongCommit{}
@@ -342,8 +376,8 @@
 
 // Branches returns the list of known branches in the repo.
 func (r *Graph) Branches() []string {
-	r.mtx.RLock()
-	defer r.mtx.RUnlock()
+	r.graphMtx.RLock()
+	defer r.graphMtx.RUnlock()
 	rv := make([]string, 0, len(r.branches))
 	for _, b := range r.branches {
 		rv = append(rv, b.Name)
@@ -368,8 +402,8 @@
 // function does not understand complex ref types (eg. HEAD~3); only branch
 // names and full commit hashes are accepted.
 func (r *Graph) Get(ref string) *Commit {
-	r.mtx.RLock()
-	defer r.mtx.RUnlock()
+	r.graphMtx.RLock()
+	defer r.graphMtx.RUnlock()
 	if c, ok := r.commits[ref]; ok {
 		return r.commitsData[c]
 	}
@@ -385,28 +419,27 @@
 
 // RecurseAllBranches runs the given function recursively over the entire commit
 // history, starting at each of the known branch heads. The function accepts the
-// current Commit as a parameter. Returning false from the function indicates
-// that recursion should stop for the current branch, however, recursion will
-// continue for any other branches until they are similarly terminated.
-// Returning an error causes recursion to stop without properly terminating
-// other branchces. The error will bubble to the top and be returned. Here's an
-// example of printing out all of the commits in the repo:
+// current Commit as a parameter. Returning ErrStopRecursing from the function
+// indicates that recursion should stop for the current branch, however,
+// recursion will continue for any other branches until they are similarly
+// terminated. Returning any other error causes recursion to stop without
+// properly terminating other branches. The error will bubble to the top and be
+// returned. Here's an example of printing out all of the commits in the repo:
 //
 // repo.RecurseAllBranches(func(c *Commit) (bool, error) {
 //      sklog.Info(c.Hash)
 //      return true, nil
 // })
-func (r *Graph) RecurseAllBranches(f func(*Commit) (bool, error)) error {
-	r.mtx.RLock()
-	defer r.mtx.RUnlock()
-	visited := make(map[*Commit]bool, len(r.commitsData))
-	for _, b := range r.branches {
-		c, ok := r.commits[b.Head]
-		if !ok {
-			return fmt.Errorf("Branch %s points to unknown commit %s", b.Name, b.Head)
+func (r *Graph) RecurseAllBranches(f func(*Commit) error) error {
+	branches := r.Branches()
+	visited := make(map[*Commit]bool, r.Len())
+	for _, b := range branches {
+		c := r.Get(b)
+		if c == nil {
+			return fmt.Errorf("Branch %s not found", b)
 		}
-		if _, ok := visited[r.commitsData[c]]; !ok {
-			if err := r.commitsData[c].recurse(f, visited); err != nil {
+		if _, ok := visited[c]; !ok {
+			if err := c.recurse(f, visited); err != nil {
 				return err
 			}
 		}
@@ -414,15 +447,165 @@
 	return nil
 }
 
+// RevList is the equivalent of "git rev-list --topo-order from..to".
+// Each argument is a commit hash or a branch name. The commits are returned
+// in reverse topological order. Per "git rev-list" docs, the returned commit
+// hashes consist of all commits reachable from "to" and not reachable from
+// "from". In the typical case of linear git history, this just means the
+// commits on the line after "from" up through "to", but with branches and
+// merges it's possible that there are entire sub-graphs which are reachable
+// from "to" but not "from".
+func (r *Graph) RevList(from, to string) ([]string, error) {
+	fromCommit := r.Get(from)
+	if fromCommit == nil {
+		return nil, fmt.Errorf("Unknown commit %q", from)
+	}
+	toCommit := r.Get(to)
+	if toCommit == nil {
+		return nil, fmt.Errorf("Unknown commit %q", to)
+	}
+	// Shortcut: if the commits are the same, return now.
+	if fromCommit == toCommit {
+		return []string{}, nil
+	}
+
+	// Find all of the excluded commits.
+	exclude := make(map[*Commit]bool, r.Len())
+	if err := fromCommit.recurse(func(c *Commit) error {
+		return nil
+	}, exclude); err != nil {
+		return nil, err
+	}
+
+	// Find the included commits.
+	include := make(map[*Commit]bool, r.Len())
+	if err := toCommit.recurse(func(c *Commit) error {
+		if exclude[c] {
+			return ErrStopRecursing
+		}
+		return nil
+	}, include); err != nil {
+		return nil, err
+	}
+
+	// include may contain some commits from the exclude map; remove them.
+	for c, _ := range include {
+		if exclude[c] {
+			delete(include, c)
+		}
+	}
+
+	// Topologically sort the commits.
+	sorted := topologicalSortHelper(include)
+	return CommitSlice(sorted).Hashes(), nil
+}
+
+// TopologicalSort returns a slice containing the given commits in reverse
+// topological order, ie. every commit is listed before any of its parents.
+func TopologicalSort(commits []*Commit) []*Commit {
+	commitsMap := make(map[*Commit]bool, len(commits))
+	for _, c := range commits {
+		commitsMap[c] = true
+	}
+	return topologicalSortHelper(commitsMap)
+}
+
+// Helper function for TopologicalSort; the caller provides the map, which is
+// modified by topologicalSortHelper.
+func topologicalSortHelper(commits map[*Commit]bool) []*Commit {
+	// children maps each commit to those commits which have it as a parent.
+	children := make(map[*Commit]map[*Commit]bool, len(commits))
+	for c, _ := range commits {
+		for _, p := range c.parents {
+			if commits[p] {
+				subMap, ok := children[p]
+				if !ok {
+					subMap = map[*Commit]bool{}
+					children[p] = subMap
+				}
+				subMap[c] = true
+			}
+		}
+	}
+
+	// Sort the commits topologically.
+	rv := make([]*Commit, 0, len(commits))
+	followBranch := func(c *Commit) {
+		for len(children[c]) == 0 {
+			// Add this commit to rv.
+			rv = append(rv, c)
+			delete(commits, c)
+
+			// Remove this commit from its parents' children, so
+			// that they can be processed.
+			for _, p := range c.parents {
+				if commits[p] {
+					delete(children[p], c)
+				}
+			}
+
+			// Find a parent to process next.
+			var next *Commit
+			for _, p := range c.parents {
+				if commits[p] && len(children[p]) == 0 {
+					// We are ready to process this parent.
+					if next == nil || p.Less(next) {
+						next = p
+					}
+				}
+			}
+			if next != nil {
+				c = next
+			} else {
+				// None of this commit's parents are ready; we can't do
+				// any more.
+				return
+			}
+		}
+	}
+	for len(commits) > 0 {
+		var next *Commit
+		for commit, _ := range commits {
+			if len(children[commit]) == 0 {
+				// We are ready to process this commit.
+				if next == nil || commit.Less(next) {
+					next = commit
+				}
+			}
+		}
+		if next == nil {
+			sklog.Error("No commits are ready to process!")
+			// Return so that we don't loop forever.
+			return rv
+		}
+		followBranch(next)
+	}
+	return rv
+}
+
+// IsAncestor returns true iff A is an ancestor of B, where A and B are either
+// commit hashes or branch names.
+func (r *Graph) IsAncestor(a, b string) (bool, error) {
+	aCommit := r.Get(a)
+	if aCommit == nil {
+		return false, fmt.Errorf("No such commit %q", a)
+	}
+	bCommit := r.Get(b)
+	if bCommit == nil {
+		return false, fmt.Errorf("No such commit %q", b)
+	}
+	return bCommit.HasAncestor(aCommit.Hash), nil
+}
+
 // Return any commits at or after the given timestamp.
 func (r *Graph) GetCommitsNewerThan(ts time.Time) ([]*vcsinfo.LongCommit, error) {
 	commits := []*Commit{}
-	if err := r.RecurseAllBranches(func(c *Commit) (bool, error) {
+	if err := r.RecurseAllBranches(func(c *Commit) error {
 		if !c.Timestamp.Before(ts) {
 			commits = append(commits, c)
-			return true, nil
+			return nil
 		}
-		return false, nil
+		return ErrStopRecursing
 	}); err != nil {
 		return nil, err
 	}
@@ -462,6 +645,20 @@
 	return commits[:n], nil
 }
 
+// TempCheckout returns a git.TempCheckout of the underlying git.Repo.
+func (r *Graph) TempCheckout(ctx context.Context) (*git.TempCheckout, error) {
+	r.repoMtx.Lock()
+	defer r.repoMtx.Unlock()
+	return r.repo.TempCheckout(ctx)
+}
+
+// GetFile returns the contents of the given file at the given commit.
+func (r *Graph) GetFile(ctx context.Context, fileName, commit string) (string, error) {
+	r.repoMtx.Lock()
+	defer r.repoMtx.Unlock()
+	return r.repo.GetFile(ctx, fileName, commit)
+}
+
 // Map is a convenience type for dealing with multiple Graphs for different
 // repos. The keys are repository URLs.
 type Map map[string]*Graph
diff --git a/go/git/repograph/graph_test.go b/go/git/repograph/graph_test.go
index 132ddf1..37dba92 100644
--- a/go/git/repograph/graph_test.go
+++ b/go/git/repograph/graph_test.go
@@ -4,12 +4,17 @@
 	"context"
 	"fmt"
 	"io/ioutil"
+	"os"
 	"path"
+	"sort"
 	"testing"
+	"time"
 
 	assert "github.com/stretchr/testify/require"
 	"go.skia.org/infra/go/deepequal"
+	"go.skia.org/infra/go/git"
 	git_testutils "go.skia.org/infra/go/git/testutils"
+	"go.skia.org/infra/go/sklog"
 	"go.skia.org/infra/go/testutils"
 	"go.skia.org/infra/go/util"
 )
@@ -97,7 +102,7 @@
 	assert.Equal(t, []*Commit{c4, c3}, c5.GetParents())
 	assert.Equal(t, []*Commit{c2}, c4.GetParents())
 	assert.Equal(t, []*Commit{c1}, c2.GetParents())
-	assert.Equal(t, []*Commit{}, c1.GetParents())
+	assert.Equal(t, []*Commit(nil), c1.GetParents())
 	assert.Equal(t, []*Commit{c2}, c3.GetParents())
 
 	// Ensure that we can start in an empty dir and check out from scratch properly.
@@ -111,8 +116,12 @@
 	m1 := repo.Get("master")
 	m2 := repo2.Get("master")
 	// These will confuse AssertDeepEqual.
-	m1.repo = nil
-	m2.repo = nil
+	for _, c := range repo.commitsData {
+		c.repo = nil
+	}
+	for _, c := range repo2.commitsData {
+		c.repo = nil
+	}
 	deepequal.AssertDeepEqual(t, m1, m2)
 }
 
@@ -144,25 +153,29 @@
 	head := repo.Get("master")
 	assert.NotNil(t, head)
 	gotCommits := map[*Commit]bool{}
-	assert.NoError(t, head.Recurse(func(c *Commit) (bool, error) {
+	assert.NoError(t, head.Recurse(func(c *Commit) error {
 		assert.False(t, gotCommits[c])
 		gotCommits[c] = true
-		return true, nil
+		return nil
 	}))
 	assert.Equal(t, len(commits), len(gotCommits))
 	for _, c := range commits {
 		assert.True(t, gotCommits[c])
 	}
+	// AllCommits is the same thing as the above.
+	allCommits, err := head.AllCommits()
+	assert.NoError(t, err)
+	assert.Equal(t, len(allCommits), len(gotCommits))
 
 	// Verify that we properly return early when the passed-in function
 	// return false.
 	gotCommits = map[*Commit]bool{}
-	assert.NoError(t, head.Recurse(func(c *Commit) (bool, error) {
+	assert.NoError(t, head.Recurse(func(c *Commit) error {
 		gotCommits[c] = true
 		if c == c3 || c == c4 {
-			return false, nil
+			return ErrStopRecursing
 		}
-		return true, nil
+		return nil
 	}))
 	assert.False(t, gotCommits[c1])
 	assert.False(t, gotCommits[c2])
@@ -170,12 +183,12 @@
 	// Verify that we properly exit immediately when the passed-in function
 	// returns an error.
 	gotCommits = map[*Commit]bool{}
-	assert.Error(t, head.Recurse(func(c *Commit) (bool, error) {
+	assert.Error(t, head.Recurse(func(c *Commit) error {
 		gotCommits[c] = true
 		if c == c4 {
-			return false, fmt.Errorf("STOP!")
+			return fmt.Errorf("STOP!")
 		}
-		return true, nil
+		return nil
 	}))
 	assert.False(t, gotCommits[c1])
 	assert.False(t, gotCommits[c2])
@@ -196,10 +209,10 @@
 
 	test := func() {
 		gotCommits := map[*Commit]bool{}
-		assert.NoError(t, repo.RecurseAllBranches(func(c *Commit) (bool, error) {
+		assert.NoError(t, repo.RecurseAllBranches(func(c *Commit) error {
 			assert.False(t, gotCommits[c])
 			gotCommits[c] = true
-			return true, nil
+			return nil
 		}))
 		assert.Equal(t, len(commits), len(gotCommits))
 		for _, c := range commits {
@@ -229,27 +242,27 @@
 
 	// Verify that we still stop recursion when requested.
 	gotCommits := map[*Commit]bool{}
-	assert.NoError(t, repo.RecurseAllBranches(func(c *Commit) (bool, error) {
+	assert.NoError(t, repo.RecurseAllBranches(func(c *Commit) error {
 		gotCommits[c] = true
 		if c == c3 || c == c4 {
-			return false, nil
+			return ErrStopRecursing
 		}
-		return true, nil
+		return nil
 	}))
 	assert.False(t, gotCommits[c1])
 	assert.False(t, gotCommits[c2])
 
 	// Verify that we error out properly.
 	gotCommits = map[*Commit]bool{}
-	assert.Error(t, repo.RecurseAllBranches(func(c *Commit) (bool, error) {
+	assert.Error(t, repo.RecurseAllBranches(func(c *Commit) error {
 		gotCommits[c] = true
 		// Because of nondeterministic map iteration and the added
 		// branches, we have to halt way back at c2 in order to have
 		// a sane, deterministic test case.
 		if c == c2 {
-			return false, fmt.Errorf("STOP!")
+			return fmt.Errorf("STOP!")
 		}
-		return true, nil
+		return nil
 	}))
 	assert.False(t, gotCommits[c1])
 	assert.True(t, gotCommits[c2])
@@ -346,9 +359,9 @@
 	assert.NoError(t, err)
 	assert.False(t, anc)
 
-	assert.NoError(t, c6.Recurse(func(c *Commit) (bool, error) {
+	assert.NoError(t, c6.Recurse(func(c *Commit) error {
 		assert.NotEqual(t, c, c3)
-		return true, nil
+		return nil
 	}))
 }
 
@@ -465,3 +478,365 @@
 	assert.Equal(t, 1, len(newCommits))
 	assert.Equal(t, mergeCommit, newCommits[0].Hash)
 }
+
+func TestRevList(t *testing.T) {
+	testutils.MediumTest(t)
+
+	ctx := context.Background()
+	gb := git_testutils.GitInit(t, ctx)
+	defer gb.Cleanup()
+	commits := git_testutils.GitSetup(ctx, gb)
+
+	tmpDir, err := ioutil.TempDir("", "")
+	assert.NoError(t, err)
+	defer testutils.RemoveAll(t, tmpDir)
+	d1 := path.Join(tmpDir, "1")
+	assert.NoError(t, os.Mkdir(d1, os.ModePerm))
+	co, err := git.NewCheckout(ctx, gb.Dir(), d1)
+	assert.NoError(t, err)
+	d2 := path.Join(tmpDir, "2")
+	assert.NoError(t, os.Mkdir(d2, os.ModePerm))
+	g, err := NewGraph(ctx, gb.Dir(), d2)
+	assert.NoError(t, err)
+	assert.NoError(t, g.Update(ctx))
+
+	check := func(from, to string, expectOrig []string) {
+		expect := util.CopyStringSlice(expectOrig)
+		revs, err := co.RevList(ctx, fmt.Sprintf("%s..%s", from, to))
+		assert.NoError(t, err)
+		// Sanity check; assert that the commits returned from git are
+		// in reverse topological order.
+		assertHashesTopoSorted(t, g, revs)
+
+		// Topological sorting is not deterministic, so we can't compare
+		// the slices directly.
+		sort.Strings(expect)
+		sort.Strings(revs)
+		deepequal.AssertDeepEqual(t, expect, revs)
+
+		revs, err = g.RevList(from, to)
+		assert.NoError(t, err)
+		assertHashesTopoSorted(t, g, revs)
+		sort.Strings(revs)
+		deepequal.AssertDeepEqual(t, expect, revs)
+	}
+
+	check(commits[0], commits[4], commits[1:])
+	check(commits[1], commits[2], commits[2:3])
+	check(commits[1], commits[4], commits[2:5])
+	check(commits[2], commits[4], commits[3:5])
+	check(commits[3], commits[4], []string{commits[2], commits[4]})
+}
+
+// Assert that the given Commits are in reverse topological order.
+func assertTopoSorted(t *testing.T, commits []*Commit) {
+	// Collect all commits in a map so we can quickly check for their
+	// presence in the commits slice.
+	commitsMap := make(map[*Commit]bool, len(commits))
+	for _, c := range commits {
+		// Assert that each parent is not yet visited.
+		parents := c.GetParents()
+		for _, p := range parents {
+			assert.False(t, commitsMap[p])
+		}
+		commitsMap[c] = true
+	}
+
+	// Ensure that we don't mix lines of history. Practically this means,
+	// for each commit:
+	// - If it has one parent and its parent has one child,
+	//   they are adjacent in the sorted slice.
+	// - If it has multiple parents, it is adjacent to one of them.
+	// - If it has multiple children, it is adjacent to one of them.
+
+	// Create a mapping from commits to their children.
+	children := make(map[*Commit]map[*Commit]bool, len(commits))
+	for _, c := range commits {
+		for _, p := range c.parents {
+			// Don't include parents which aren't in the slice.
+			if !commitsMap[p] {
+				continue
+			}
+			subMap, ok := children[p]
+			if !ok {
+				subMap = map[*Commit]bool{}
+				children[p] = subMap
+			}
+			subMap[c] = true
+		}
+	}
+
+	// Verify that the above cases are true for each commit in the slice.
+	for idx, c := range commits {
+		sklog.Errorf("Check %d / %d", idx, len(commits))
+
+		// If the commit has one parent, and its parent has one child,
+		// they should be adjacent.
+		if len(c.parents) == 1 && len(children[c.parents[0]]) == 1 {
+			// Expect that we're not at the end of the commits slice
+			// since the parent should be listed after the current
+			// commit.
+			assert.True(t, len(commits) > idx+1)
+			assert.Equal(t, c.parents[0], commits[idx+1])
+		}
+
+		// If the commit has multiple parents, it should be adjacent to
+		// one of them.
+		if len(c.parents) > 1 {
+			expectParentAdjacent := false
+			parentIsAdjacent := false
+			for _, p := range c.parents {
+				// Only include parents which are in the slice.
+				if commitsMap[p] {
+					expectParentAdjacent = true
+					if len(commits) > idx+1 && commits[idx+1] == p {
+						parentIsAdjacent = true
+						break
+					}
+				}
+			}
+			assert.Equal(t, expectParentAdjacent, parentIsAdjacent)
+		}
+
+		// If the commit has multiple children, it should be adjacent
+		// to one of them.
+		if len(children[c]) > 1 {
+			assert.True(t, idx > 0)
+			childIsAdjacent := false
+			for child, _ := range children[c] {
+				if commits[idx-1] == child {
+					childIsAdjacent = true
+					break
+				}
+			}
+			assert.True(t, childIsAdjacent)
+		}
+	}
+}
+
+// Assert that the given commit hashses are in reverse topological order.
+func assertHashesTopoSorted(t *testing.T, repo *Graph, hashes []string) {
+	commits := make([]*Commit, 0, len(hashes))
+	for _, hash := range hashes {
+		commits = append(commits, repo.Get(hash))
+	}
+	assertTopoSorted(t, commits)
+}
+
+func TestTopoSort(t *testing.T) {
+	testutils.LargeTest(t)
+
+	ctx := context.Background()
+
+	check := func(commits []*Commit) {
+		sorted := TopologicalSort(commits)
+
+		// Ensure that all of the commits are in the resulting slice.
+		assert.Equal(t, len(commits), len(sorted))
+		found := make(map[*Commit]bool, len(commits))
+		for _, c := range sorted {
+			found[c] = true
+		}
+		for _, c := range commits {
+			assert.True(t, found[c])
+		}
+		assertTopoSorted(t, sorted)
+	}
+	checkGraph := func(g *Graph) {
+		sets := util.PowerSet(len(g.commitsData))
+		for _, set := range sets {
+			inp := make([]*Commit, 0, len(g.commitsData))
+			for _, idx := range set {
+				inp = append(inp, g.commitsData[idx])
+			}
+			check(inp)
+		}
+	}
+	checkGitBuilder := func(gb *git_testutils.GitBuilder, expect []string) {
+		tmpDir, err := ioutil.TempDir("", "")
+		assert.NoError(t, err)
+		defer testutils.RemoveAll(t, tmpDir)
+		g, err := NewGraph(ctx, gb.Dir(), tmpDir)
+		assert.NoError(t, err)
+		assert.NoError(t, g.Update(ctx))
+		checkGraph(g)
+
+		// Test stability by verifying that we get the expected ordering
+		// for the entire repo, multiple times.
+		for i := 0; i < 10; i++ {
+			sorted := CommitSlice(TopologicalSort(g.commitsData)).Hashes()
+			deepequal.AssertDeepEqual(t, expect, sorted)
+		}
+	}
+
+	// Test topological sorting using the default test repo.
+	{
+		gb := git_testutils.GitInit(t, ctx)
+		defer gb.Cleanup()
+		commits := git_testutils.GitSetup(ctx, gb)
+
+		// GitSetup doesn't wait between commits, which means that the
+		// timestamps might be equal. Adjust the expectations
+		// accordingly.
+		expect := []string{commits[4], commits[3], commits[2], commits[1], commits[0]}
+		tmpDir, err := ioutil.TempDir("", "")
+		assert.NoError(t, err)
+		defer testutils.RemoveAll(t, tmpDir)
+		g, err := NewGraph(ctx, gb.Dir(), tmpDir)
+		assert.NoError(t, err)
+		assert.NoError(t, g.Update(ctx))
+		c3 := g.Get(commits[3])
+		c2 := g.Get(commits[2])
+		if c3.Timestamp.Equal(c2.Timestamp) && c3.Hash < c2.Hash {
+			expect[1], expect[2] = expect[2], expect[1]
+		}
+		checkGitBuilder(gb, expect)
+	}
+
+	// Verify that we use the timestamp as a tie-breaker.
+	{
+		gb := git_testutils.GitInit(t, ctx)
+		defer gb.Cleanup()
+		gb.Add(ctx, "file0", "contents")
+		ts := time.Unix(1552403492, 0)
+		c0 := gb.CommitMsgAt(ctx, "Initial commit", ts)
+		assert.Equal(t, c0, "c48b90c8ccc70b4d2bd146e4f708c398f78e2dd6") // Hashes are deterministic.
+		ts = ts.Add(2 * time.Second)
+		gb.Add(ctx, "file1", "contents")
+		c1 := gb.CommitMsgAt(ctx, "Child 1", ts)
+		gb.CreateBranchAtCommit(ctx, "otherbranch", c0)
+		ts = ts.Add(2 * time.Second)
+		gb.Add(ctx, "file2", "contents")
+		c2 := gb.CommitMsgAt(ctx, "Child 2", ts)
+		// c1 and c2 both have c0 as a parent. The topological ordering
+		// is ambiguous unless we use the timestamp as a tie-breaker, in
+		// which case c2 should always come before c1, since it is more
+		// recent.
+		checkGitBuilder(gb, []string{c2, c1, c0})
+	}
+
+	// Same as above, but the child commits have the same timestamp. Verify
+	// that we use the commit hash as a secondary tie-breaker.
+	{
+		gb := git_testutils.GitInit(t, ctx)
+		defer gb.Cleanup()
+		gb.Add(ctx, "file0", "contents")
+		ts := time.Unix(1552403492, 0)
+		c0 := gb.CommitMsgAt(ctx, "Initial commit", ts)
+		assert.Equal(t, c0, "c48b90c8ccc70b4d2bd146e4f708c398f78e2dd6") // Hashes are deterministic.
+		ts = ts.Add(2 * time.Second)
+		gb.Add(ctx, "file1", "contents")
+		c1 := gb.CommitMsgAt(ctx, "Child 1", ts)
+		assert.Equal(t, c1, "dc24e5b042cdcf995a182815ef37f659e8ec20cc")
+		gb.CreateBranchAtCommit(ctx, "otherbranch", c0)
+		gb.Add(ctx, "file2", "contents")
+		c2 := gb.CommitMsgAt(ctx, "Child 2", ts)
+		assert.Equal(t, c2, "06d29d7f828723c79c9eba25696111c628ab5a7e")
+		// c1 and c2 both have c0 as a parent, and they both have the
+		// same timestamp. The topological ordering is ambiguous even
+		// with the timestamp as a tie-breaker, so we have to use the
+		// commit hash.
+		checkGitBuilder(gb, []string{c1, c2, c0})
+	}
+
+	// Extend the above to ensure that, in the case of a merge, we follow
+	// the parent with the newer timestamp.
+	{
+		gb := git_testutils.GitInit(t, ctx)
+		defer gb.Cleanup()
+		gb.Add(ctx, "file0", "contents")
+		ts := time.Unix(1552403492, 0)
+		c0 := gb.CommitMsgAt(ctx, "Initial commit", ts)
+		assert.Equal(t, c0, "c48b90c8ccc70b4d2bd146e4f708c398f78e2dd6") // Hashes are deterministic.
+		ts = ts.Add(2 * time.Second)
+		gb.Add(ctx, "file1", "contents")
+		c1 := gb.CommitMsgAt(ctx, "Child 1", ts)
+		assert.Equal(t, c1, "dc24e5b042cdcf995a182815ef37f659e8ec20cc")
+		gb.CreateBranchAtCommit(ctx, "otherbranch", c0)
+		gb.Add(ctx, "file2", "contents")
+		c2 := gb.CommitMsgAt(ctx, "Child 2", ts)
+		assert.Equal(t, c2, "06d29d7f828723c79c9eba25696111c628ab5a7e")
+		gb.CheckoutBranch(ctx, "master")
+		c3 := gb.CommitGen(ctx, "file1")
+		ts = ts.Add(10 * time.Second)
+		c4 := gb.CommitGenAt(ctx, "file1", ts)
+		gb.CheckoutBranch(ctx, "otherbranch")
+		c5 := gb.CommitGen(ctx, "file2")
+		c6 := gb.CommitGenAt(ctx, "file2", ts.Add(-time.Second))
+		gb.CheckoutBranch(ctx, "master")
+		c7 := gb.MergeBranch(ctx, "otherbranch")
+		checkGitBuilder(gb, []string{c7, c4, c3, c1, c6, c5, c2, c0})
+	}
+}
+
+func TestIsAncestor(t *testing.T) {
+	testutils.MediumTest(t)
+
+	ctx := context.Background()
+	gb := git_testutils.GitInit(t, ctx)
+	defer gb.Cleanup()
+	commits := git_testutils.GitSetup(ctx, gb)
+
+	tmpDir, err := ioutil.TempDir("", "")
+	assert.NoError(t, err)
+	defer testutils.RemoveAll(t, tmpDir)
+	d1 := path.Join(tmpDir, "1")
+	assert.NoError(t, os.Mkdir(d1, os.ModePerm))
+	co, err := git.NewCheckout(ctx, gb.Dir(), d1)
+	assert.NoError(t, err)
+	d2 := path.Join(tmpDir, "2")
+	assert.NoError(t, os.Mkdir(d2, os.ModePerm))
+	g, err := NewGraph(ctx, gb.Dir(), d2)
+	assert.NoError(t, err)
+	assert.NoError(t, g.Update(ctx))
+
+	sklog.Infof("4. %s", commits[4][:4])
+	sklog.Infof("    |    \\")
+	sklog.Infof("3. %s   |", commits[3][:4])
+	sklog.Infof("    |     |")
+	sklog.Infof("    | 2. %s", commits[2][:4])
+	sklog.Infof("    |     |")
+	sklog.Infof("    |    /")
+	sklog.Infof("1. %s", commits[1][:4])
+	sklog.Infof("    |")
+	sklog.Infof("0. %s", commits[0][:4])
+
+	check := func(a, b string, expect bool) {
+		// Compare against actual git.
+		got, err := co.IsAncestor(ctx, a, b)
+		assert.NoError(t, err)
+		assert.Equal(t, expect, got)
+		got, err = g.IsAncestor(a, b)
+		assert.NoError(t, err)
+		assert.Equal(t, expect, got)
+	}
+	check(commits[0], commits[0], true)
+	check(commits[0], commits[1], true)
+	check(commits[0], commits[2], true)
+	check(commits[0], commits[3], true)
+	check(commits[0], commits[4], true)
+
+	check(commits[1], commits[0], false)
+	check(commits[1], commits[1], true)
+	check(commits[1], commits[2], true)
+	check(commits[1], commits[3], true)
+	check(commits[1], commits[4], true)
+
+	check(commits[2], commits[0], false)
+	check(commits[2], commits[1], false)
+	check(commits[2], commits[2], true)
+	check(commits[2], commits[3], false)
+	check(commits[2], commits[4], true)
+
+	check(commits[3], commits[0], false)
+	check(commits[3], commits[1], false)
+	check(commits[3], commits[2], false)
+	check(commits[3], commits[3], true)
+	check(commits[3], commits[4], true)
+
+	check(commits[4], commits[0], false)
+	check(commits[4], commits[1], false)
+	check(commits[4], commits[2], false)
+	check(commits[4], commits[3], false)
+	check(commits[4], commits[4], true)
+}
diff --git a/go/git/testutils/git_builder.go b/go/git/testutils/git_builder.go
index ff93215..e636ea4 100644
--- a/go/git/testutils/git_builder.go
+++ b/go/git/testutils/git_builder.go
@@ -45,7 +45,8 @@
 
 	g.run(ctx, "git", "init")
 	g.run(ctx, "git", "remote", "add", "origin", ".")
-
+	g.run(ctx, "git", "config", "--local", "user.name", "test")
+	g.run(ctx, "git", "config", "--local", "user.email", "test@google.com")
 	return g
 }
 
diff --git a/go/util/util.go b/go/util/util.go
index b10a10d..4130f3b 100644
--- a/go/util/util.go
+++ b/go/util/util.go
@@ -1205,3 +1205,20 @@
 		return AskForConfirmation(format, args...)
 	}
 }
+
+// PowerSet returns a slice of slices representing the power set of the indices
+// of a slice.
+func PowerSet(n int) [][]int {
+	if n == 0 {
+		return [][]int{[]int{}}
+	}
+	subs := PowerSet(n - 1)
+	addl := [][]int{}
+	for _, sub := range subs {
+		cpy := make([]int, len(sub)+1)
+		copy(cpy, sub)
+		cpy[len(cpy)-1] = n - 1
+		addl = append(addl, cpy)
+	}
+	return append(subs, addl...)
+}
diff --git a/go/util/util_test.go b/go/util/util_test.go
index 2350032..3010ad4 100644
--- a/go/util/util_test.go
+++ b/go/util/util_test.go
@@ -949,3 +949,14 @@
 	testGt([]string{"a", "b", "d"}, []string{"a", "b", "c", "d"})
 	testGt([]string{"a", "c", "b"}, []string{"a", "b", "c"})
 }
+
+func TestPowerSet(t *testing.T) {
+	testutils.SmallTest(t)
+	test := func(inp int, expect [][]int) {
+		deepequal.AssertDeepEqual(t, expect, PowerSet(inp))
+	}
+	test(0, [][]int{[]int{}})
+	test(1, [][]int{[]int{}, []int{0}})
+	test(2, [][]int{[]int{}, []int{0}, []int{1}, []int{0, 1}})
+	test(3, [][]int{[]int{}, []int{0}, []int{1}, []int{0, 1}, []int{2}, []int{0, 2}, []int{1, 2}, []int{0, 1, 2}})
+}
diff --git a/task_scheduler/go/blacklist/blacklist.go b/task_scheduler/go/blacklist/blacklist.go
index f8c716f..3000b2b1 100644
--- a/task_scheduler/go/blacklist/blacklist.go
+++ b/task_scheduler/go/blacklist/blacklist.go
@@ -154,7 +154,7 @@
 	if !ok {
 		return nil, fmt.Errorf("Unknown repo %s", repoName)
 	}
-	commits, err := repo.Repo().RevList(ctx, fmt.Sprintf("%s..%s", startCommit, endCommit))
+	commits, err := repo.RevList(startCommit, endCommit)
 	if err != nil {
 		return nil, err
 	}
diff --git a/task_scheduler/go/db/cache/cache_test.go b/task_scheduler/go/db/cache/cache_test.go
index d5da9ef..4747edf 100644
--- a/task_scheduler/go/db/cache/cache_test.go
+++ b/task_scheduler/go/db/cache/cache_test.go
@@ -991,12 +991,12 @@
 	})
 
 	var firstCommit *repograph.Commit
-	err = repo.RecurseAllBranches(func(c *repograph.Commit) (bool, error) {
+	err = repo.RecurseAllBranches(func(c *repograph.Commit) error {
 		ts, err := grt("a.git", c.Hash)
 		assert.NoError(t, err)
 		assert.True(t, c.Timestamp.Equal(ts))
 		firstCommit = c
-		return true, nil
+		return nil
 	})
 	assert.NoError(t, err)
 
diff --git a/task_scheduler/go/scheduling/perftest/perftest.go b/task_scheduler/go/scheduling/perftest/perftest.go
index a5f1a43..7ba7e2b 100644
--- a/task_scheduler/go/scheduling/perftest/perftest.go
+++ b/task_scheduler/go/scheduling/perftest/perftest.go
@@ -265,10 +265,13 @@
 	repo, err := repograph.NewGraph(ctx, repoName, workdir)
 	assertNoError(err)
 	assertNoError(repo.Update(ctx))
-	head, err := repo.Repo().RevParse(ctx, "HEAD")
-	assertNoError(err)
+	headCommit := repo.Get("master")
+	if headCommit == nil {
+		sklog.Fatal("Could not find HEAD of master.")
+	}
+	head := headCommit.Hash
 
-	commits, err := repo.Repo().RevList(ctx, head)
+	commits, err := repo.Get(head).AllCommits()
 	assertNoError(err)
 	assertDeepEqual([]string{head}, commits)
 
@@ -351,7 +354,7 @@
 
 	// Add more commits to the repo.
 	makeDummyCommits(ctx, repoDir, 200)
-	commits, err = repo.Repo().RevList(ctx, fmt.Sprintf("%s..HEAD", head))
+	commits, err = repo.RevList(head, "master")
 	assertNoError(err)
 
 	// Start the profiler.
diff --git a/task_scheduler/go/scheduling/task_scheduler.go b/task_scheduler/go/scheduling/task_scheduler.go
index 78953f3..00d629f 100644
--- a/task_scheduler/go/scheduling/task_scheduler.go
+++ b/task_scheduler/go/scheduling/task_scheduler.go
@@ -550,25 +550,25 @@
 	var stealFrom *types.Task
 
 	// Run the helper function to recurse on commit history.
-	if err := revision.Recurse(func(commit *repograph.Commit) (bool, error) {
+	if err := revision.Recurse(func(commit *repograph.Commit) error {
 		// Determine whether any task already includes this commit.
 		prev, err := cache.GetTaskForCommit(repoName, commit.Hash, taskName)
 		if err != nil {
-			return false, err
+			return err
 		}
 
 		// If the blamelist is too large, just use a single commit.
 		if len(commitsBuf) > MAX_BLAMELIST_COMMITS {
 			commitsBuf = append(commitsBuf[:0], revision)
 			//sklog.Warningf("Found too many commits for %s @ %s; using single-commit blamelist.", taskName, revision.Hash)
-			return false, ERR_BLAMELIST_DONE
+			return ERR_BLAMELIST_DONE
 		}
 
 		// If we're stealing commits from a previous task but the current
 		// commit is not in any task's blamelist, we must have scrolled past
 		// the beginning of the tasks. Just return.
 		if prev == nil && stealFrom != nil {
-			return false, nil
+			return repograph.ErrStopRecursing
 		}
 
 		// If a previous task already included this commit, we have to make a decision.
@@ -589,17 +589,17 @@
 					for _, c := range stealFrom.Commits {
 						ptr := repo.Get(c)
 						if ptr == nil {
-							return false, fmt.Errorf("No such commit: %q", c)
+							return fmt.Errorf("No such commit: %q", c)
 						}
 						commitsBuf = append(commitsBuf, ptr)
 					}
-					return false, ERR_BLAMELIST_DONE
+					return ERR_BLAMELIST_DONE
 				}
 			}
 			if stealFrom == nil || prev.Id != stealFrom.Id {
 				// If we've hit a commit belonging to a different task,
 				// we're done.
-				return false, nil
+				return repograph.ErrStopRecursing
 			}
 		}
 
@@ -613,11 +613,11 @@
 		}
 		if newTasks[rs][taskName] {
 			sklog.Infof("Task Spec %s was added in %s; stopping blamelist calculation.", taskName, commit.Hash)
-			return false, nil
+			return repograph.ErrStopRecursing
 		}
 
 		// Recurse on the commit's parents.
-		return true, nil
+		return nil
 
 	}); err != nil && err != ERR_BLAMELIST_DONE {
 		return nil, nil, err
@@ -1349,7 +1349,7 @@
 
 // recurseAllBranches runs the given func on every commit on all branches, with
 // some Task Scheduler-specific exceptions.
-func (s *TaskScheduler) RecurseAllBranches(ctx context.Context, fn func(string, *repograph.Graph, *repograph.Commit) (bool, error)) error {
+func (s *TaskScheduler) RecurseAllBranches(ctx context.Context, fn func(string, *repograph.Graph, *repograph.Commit) error) error {
 	for repoUrl, r := range s.repos {
 		blacklistBranches := BRANCH_BLACKLIST[repoUrl]
 		blacklistCommits := make(map[*repograph.Commit]string, len(blacklistBranches))
@@ -1359,22 +1359,22 @@
 				blacklistCommits[c] = b
 			}
 		}
-		if err := r.RecurseAllBranches(func(c *repograph.Commit) (bool, error) {
+		if err := r.RecurseAllBranches(func(c *repograph.Commit) error {
 			if blacklistBranch, ok := blacklistCommits[c]; ok {
 				sklog.Infof("Skipping blacklisted branch %q", blacklistBranch)
-				return false, nil
+				return repograph.ErrStopRecursing
 			}
 			for head, blacklistBranch := range blacklistCommits {
-				isAncestor, err := r.Repo().IsAncestor(ctx, c.Hash, head.Hash)
+				isAncestor, err := r.IsAncestor(c.Hash, head.Hash)
 				if err != nil {
-					return false, err
+					return err
 				} else if isAncestor {
 					sklog.Infof("Skipping blacklisted branch %q (--is-ancestor)", blacklistBranch)
-					return false, nil
+					return repograph.ErrStopRecursing
 				}
 			}
 			if !s.window.TestCommit(repoUrl, c) {
-				return false, nil
+				return repograph.ErrStopRecursing
 			}
 			return fn(repoUrl, r, c)
 		}); err != nil {
@@ -1390,10 +1390,10 @@
 
 	// Find all new Jobs for all new commits.
 	newJobs := []*types.Job{}
-	if err := s.RecurseAllBranches(ctx, func(repoUrl string, r *repograph.Graph, c *repograph.Commit) (bool, error) {
+	if err := s.RecurseAllBranches(ctx, func(repoUrl string, r *repograph.Graph, c *repograph.Commit) error {
 		// If this commit isn't in scheduling range, stop recursing.
 		if !s.window.TestCommit(repoUrl, c) {
-			return false, nil
+			return repograph.ErrStopRecursing
 		}
 
 		rs := types.RepoState{
@@ -1408,9 +1408,9 @@
 				// TODO(borenet): We should consider canceling the jobs
 				// (how?) since we can never fulfill them.
 				sklog.Errorf("Failed to obtain new jobs due to permanent error: %s", err)
-				return true, nil
+				return nil
 			}
-			return false, err
+			return err
 		}
 		alreadyScheduledAllJobs := true
 		for name, spec := range cfg.Jobs {
@@ -1419,9 +1419,9 @@
 				if spec.Trigger == specs.TRIGGER_ANY_BRANCH {
 					shouldRun = true
 				} else if spec.Trigger == specs.TRIGGER_MASTER_ONLY {
-					isAncestor, err := r.Repo().IsAncestor(ctx, c.Hash, "master")
+					isAncestor, err := r.IsAncestor(c.Hash, "master")
 					if err != nil {
-						return false, err
+						return err
 					} else if isAncestor {
 						shouldRun = true
 					}
@@ -1430,7 +1430,7 @@
 			if shouldRun {
 				prevJobs, err := s.jCache.GetJobsByRepoState(name, rs)
 				if err != nil {
-					return false, err
+					return err
 				}
 				alreadyScheduled := false
 				for _, prev := range prevJobs {
@@ -1454,7 +1454,7 @@
 							sklog.Errorf("Got ErrNoSuchEntry after a successful call to GetOrCacheRepoState! Job %s; RepoState: %+v", name, rs)
 							continue
 						}
-						return false, err
+						return err
 					}
 					newJobs = append(newJobs, j)
 				}
@@ -1464,15 +1464,15 @@
 		// stop recursing, under the assumption that we've already
 		// scheduled all of the jobs for the ones before it.
 		if alreadyScheduledAllJobs {
-			return false, nil
+			return repograph.ErrStopRecursing
 		}
 		if c.Hash == "50537e46e4f0999df0a4707b227000cfa8c800ff" {
 			// Stop recursing here, since Jobs were added
 			// in this commit and previous commits won't be
 			// valid.
-			return false, nil
+			return repograph.ErrStopRecursing
 		}
-		return true, nil
+		return nil
 	}); err != nil {
 		return err
 	}
@@ -1489,12 +1489,12 @@
 func (s *TaskScheduler) updateAddedTaskSpecs(ctx context.Context) error {
 	defer metrics2.FuncTimer().Stop()
 	repoStates := []types.RepoState{}
-	if err := s.RecurseAllBranches(ctx, func(repoUrl string, r *repograph.Graph, c *repograph.Commit) (bool, error) {
+	if err := s.RecurseAllBranches(ctx, func(repoUrl string, r *repograph.Graph, c *repograph.Commit) error {
 		repoStates = append(repoStates, types.RepoState{
 			Repo:     repoUrl,
 			Revision: c.Hash,
 		})
-		return true, nil
+		return nil
 	}); err != nil {
 		return err
 	}
diff --git a/task_scheduler/go/scheduling/task_scheduler_test.go b/task_scheduler/go/scheduling/task_scheduler_test.go
index 215c753..6812eb5 100644
--- a/task_scheduler/go/scheduling/task_scheduler_test.go
+++ b/task_scheduler/go/scheduling/task_scheduler_test.go
@@ -1878,13 +1878,12 @@
 
 	// Add some commits.
 	makeDummyCommits(ctx, gb, 10)
-	assert.NoError(t, s.repos[gb.RepoUrl()].Repo().Update(ctx))
-	commits, err := s.repos[gb.RepoUrl()].Repo().RevList(ctx, "HEAD")
+	assert.NoError(t, s.repos[gb.RepoUrl()].Update(ctx))
+	commits, err := s.repos[gb.RepoUrl()].Get("master").AllCommits()
 	assert.NoError(t, err)
 
 	// Run one task. Ensure that it's at tip-of-tree.
-	head, err := s.repos[gb.RepoUrl()].Repo().RevParse(ctx, "HEAD")
-	assert.NoError(t, err)
+	head := s.repos[gb.RepoUrl()].Get("master").Hash
 	swarmingClient.MockBots([]*swarming_api.SwarmingRpcsBotInfo{bot1})
 	assert.NoError(t, s.updateRepos(ctx))
 	assert.NoError(t, s.MainLoop(ctx))
@@ -2071,8 +2070,7 @@
 	assert.NoError(t, s.MainLoop(ctx))
 	assert.NoError(t, s.tCache.Update())
 	assert.Equal(t, 0, len(s.queue))
-	head, err := s.repos[gb.RepoUrl()].Repo().RevParse(ctx, "HEAD")
-	assert.NoError(t, err)
+	head := s.repos[gb.RepoUrl()].Get("master").Hash
 	tasks, err := s.tCache.GetTasksForCommits(gb.RepoUrl(), []string{head})
 	assert.NoError(t, err)
 	assert.Equal(t, 1, len(tasks[head]))
@@ -2081,8 +2079,8 @@
 	// Add some commits to the repo.
 	gb.CheckoutBranch(ctx, "master")
 	makeDummyCommits(ctx, gb, 8)
-	assert.NoError(t, s.repos[gb.RepoUrl()].Repo().Update(ctx))
-	commits, err := s.repos[gb.RepoUrl()].Repo().RevList(ctx, fmt.Sprintf("%s..HEAD", head))
+	assert.NoError(t, s.repos[gb.RepoUrl()].Update(ctx))
+	commits, err := s.repos[gb.RepoUrl()].RevList(head, "master")
 	assert.Nil(t, err)
 	assert.Equal(t, 8, len(commits))
 	assert.NoError(t, s.updateRepos(ctx)) // Most tests want this.
@@ -2866,7 +2864,7 @@
 	// Add some commits to test blamelist calculation.
 	makeDummyCommits(ctx, gb, 7)
 	assert.NoError(t, s.updateRepos(ctx))
-	hashes, err := s.repos[gb.RepoUrl()].Repo().RevList(ctx, "HEAD")
+	hashes, err := s.repos[gb.RepoUrl()].Get("master").AllCommits()
 	assert.NoError(t, err)
 
 	return ctx, gb, hashes, d, s, func() {
diff --git a/task_scheduler/go/syncer/syncer.go b/task_scheduler/go/syncer/syncer.go
index a35c39f..6f22359 100644
--- a/task_scheduler/go/syncer/syncer.go
+++ b/task_scheduler/go/syncer/syncer.go
@@ -86,7 +86,7 @@
 				rvErr <- fmt.Errorf("Unknown repo: %s", rs.Repo)
 				return
 			}
-			gr, err = tempGitRepo(ctx, repo.Repo(), rs)
+			gr, err = tempGitRepo(ctx, repo, rs)
 		}
 		if err != nil {
 			rvErr <- err
@@ -197,7 +197,7 @@
 
 // tempGitRepo creates a git repository in a temporary directory, gets it into
 // the given RepoState, and returns its location.
-func tempGitRepo(ctx context.Context, repo *git.Repo, rs types.RepoState) (rv *git.TempCheckout, rvErr error) {
+func tempGitRepo(ctx context.Context, repo *repograph.Graph, rs types.RepoState) (rv *git.TempCheckout, rvErr error) {
 	defer metrics2.FuncTimer().Stop()
 
 	if rs.IsTryJob() {
diff --git a/task_scheduler/go/testutils/swarming_helpers.go b/task_scheduler/go/testutils/swarming_helpers.go
index 4317b70..415031c 100644
--- a/task_scheduler/go/testutils/swarming_helpers.go
+++ b/task_scheduler/go/testutils/swarming_helpers.go
@@ -23,16 +23,11 @@
 	botId := 0
 	rv := []*swarming_api.SwarmingRpcsBotInfo{}
 	for _, repo := range repos {
-		branches, err := repo.Repo().Branches(ctx)
-		if err != nil {
-			sklog.Error(err)
-			continue
-		}
-		for _, branch := range branches {
+		for _, branch := range repo.BranchHeads() {
 			if branch.Name != "master" {
 				continue
 			}
-			contents, err := repo.Repo().GetFile(ctx, specs.TASKS_CFG_FILE, branch.Head)
+			contents, err := repo.GetFile(ctx, specs.TASKS_CFG_FILE, branch.Head)
 			if err != nil {
 				sklog.Error(err)
 				continue
diff --git a/task_scheduler/go/tryjobs/tryjobs_test.go b/task_scheduler/go/tryjobs/tryjobs_test.go
index 49ca48a..a2f6674 100644
--- a/task_scheduler/go/tryjobs/tryjobs_test.go
+++ b/task_scheduler/go/tryjobs/tryjobs_test.go
@@ -144,7 +144,7 @@
 }
 
 func TestGetRevision(t *testing.T) {
-	ctx, trybots, _, mock, cleanup := setup(t)
+	_, trybots, _, mock, cleanup := setup(t)
 	defer cleanup()
 
 	// Get the (only) commit from the repo.
@@ -153,8 +153,7 @@
 	}
 	_, r, _, err := trybots.getRepo(props)
 	assert.NoError(t, err)
-	c, err := r.Repo().RevParse(ctx, "master")
-	assert.NoError(t, err)
+	c := r.Get("master").Hash
 
 	// Fake response from Gerrit.
 	ci := &gerrit.ChangeInfo{