diff --git a/rules/scripts/BUILD b/rules/scripts/BUILD
index 5941449..43824ed 100644
--- a/rules/scripts/BUILD
+++ b/rules/scripts/BUILD
@@ -20,10 +20,19 @@
     ],
 )
 
+py_library(
+    name = "bitstreams_workspace",
+    srcs = [
+        "bitstreams_workspace.py",
+    ],
+)
+
 py_test(
     name = "bitstreams_workspace_test",
     srcs = [
-        "bitstreams_workspace.py",
         "bitstreams_workspace_test.py",
     ],
+    deps = [
+        ":bitstreams_workspace",
+    ],
 )
diff --git a/rules/scripts/bitstreams_workspace.py b/rules/scripts/bitstreams_workspace.py
index 21de475..1aa6c16 100755
--- a/rules/scripts/bitstreams_workspace.py
+++ b/rules/scripts/bitstreams_workspace.py
@@ -63,6 +63,7 @@
 
 
 class BitstreamCache(object):
+
     def __init__(self, bucket_url, cachedir, latest_update, offline=False):
         """Initialize the Bitstream Cache Manager."""
         if bucket_url[-1] != '/':
@@ -76,6 +77,14 @@
         self.offline = offline
         self.available = {}
 
+    @staticmethod
+    def MakeWithDefaults() -> 'BitstreamCache':
+        """Create a BitstreamCache with default parameters."""
+        args = parser.parse_args([])
+        cache = BitstreamCache(args.bucket_url, args.cache, args.latest_update,
+                               args.offline)
+        return cache
+
     def InitRepository(self):
         """Create the cache directory and symlink it into the bazel repository dir."""
         os.makedirs(self.cachedir, exist_ok=True)
diff --git a/rules/scripts/bitstreams_workspace_test.py b/rules/scripts/bitstreams_workspace_test.py
index 7e00782..09abb00 100644
--- a/rules/scripts/bitstreams_workspace_test.py
+++ b/rules/scripts/bitstreams_workspace_test.py
@@ -11,6 +11,11 @@
 
 class TestBitstreamCache(unittest.TestCase):
 
+    def test_make_with_default(self):
+        # Changes to command-line argument defaults could break this method, so
+        # it's important to at least have code coverage.
+        BitstreamCache.MakeWithDefaults()
+
     def test_get_from_cache(self):
         BITSTREAM_ORIG = 'lowrisc_systems_chip_earlgrey_cw310_0.1.bit.orig'
         BITSTREAM_SPLICE = 'lowrisc_systems_chip_earlgrey_cw310_0.1.bit.splice'
diff --git a/util/fpga/BUILD b/util/fpga/BUILD
new file mode 100644
index 0000000..9ce1891
--- /dev/null
+++ b/util/fpga/BUILD
@@ -0,0 +1,32 @@
+# Copyright lowRISC contributors.
+# Licensed under the Apache License, Version 2.0, see LICENSE for details.
+# SPDX-License-Identifier: Apache-2.0
+
+load("@rules_python//python:defs.bzl", "py_binary")
+load("@ot_python_deps//:requirements.bzl", "requirement")
+
+package(default_visibility = ["//visibility:public"])
+
+py_library(
+    name = "bitstream_bisect_support",
+    deps = [
+        "//rules/scripts:bitstreams_workspace",
+        requirement("typer"),
+        requirement("rich"),
+    ],
+)
+
+py_binary(
+    name = "bitstream_bisect",
+    srcs = ["bitstream_bisect.py"],
+    deps = [":bitstream_bisect_support"],
+)
+
+py_test(
+    name = "bitstream_bisect_test",
+    srcs = [
+        "bitstream_bisect.py",
+        "bitstream_bisect_test.py",
+    ],
+    deps = [":bitstream_bisect_support"],
+)
diff --git a/util/fpga/bitstream_bisect.py b/util/fpga/bitstream_bisect.py
new file mode 100644
index 0000000..2ec6e22
--- /dev/null
+++ b/util/fpga/bitstream_bisect.py
@@ -0,0 +1,413 @@
+# Copyright lowRISC contributors.
+# Licensed under the Apache License, Version 2.0, see LICENSE for details.
+# SPDX-License-Identifier: Apache-2.0
+r"""Efficiently bisect FPGA regressions with the bitstream cache.
+
+This tool bisects while minimizing the number of calls to the slow command.
+Under the hood, it actually runs up to two git bisects. The first bisect only
+tests commits that have cached bitstreams. The optional second bisect narrows
+down ambiguous results. (For more information on bisecting, see `man 1
+git-bisect` or <https://git-scm.com/docs/git-bisect>.)
+
+In the first phase, the tool classifies commits as good/bad/skip with the
+user-provided `--fast-command`. In the second phase, it uses `--slow-command`.
+These commands classify the current commit via their exit status. Exiting with 0
+indicates that the commit is good. Exiting with 125 indicates the commit cannot
+be tested. Exiting with any other status indicates that the commit is bad.
+
+Run bitstream_bisect.py with Bazel like so:
+
+./bazelisk.sh run //util/fpga:bitstream_bisect -- \
+    --good HEAD~30 \
+    --bad HEAD \
+    --fast-command "./bazelisk.sh test //sw/device/tests:uart_smoketest_fpga_cw310_rom" \
+    --slow-command "./bazelisk.sh test --define bitstream=vivado \
+        //sw/device/tests:uart_smoketest_fpga_cw310_rom"
+
+"""
+
+import abc
+import enum
+import os
+import re
+import shlex
+import string
+import subprocess
+from typing import Dict, List, Optional, Set, Tuple
+
+import rich
+import rich.console
+import typer
+
+from rules.scripts.bitstreams_workspace import BitstreamCache
+
+
+class CommitHash(str):
+    """A string representation of a Git commit hash.
+
+    The given string must contain only hex digits. It is canonicalized to
+    lowercase, but not canonicalized relative to the current git repository. As
+    such, two CommitHash objects may fail to compare equal even though git would
+    say they refer to the same commit.
+    """
+
+    def __new__(cls, s):
+        t = super().__new__(cls, s).lower()
+        if len(t) == 0 or len(set(t) - set(string.hexdigits)) > 0:
+            raise Exception("Invalid CommitHash input: '{}'".format(t))
+        return t
+
+
+class CommitJudgment(enum.Enum):
+    GOOD = enum.auto()
+    BAD = enum.auto()
+    SKIP = enum.auto()
+
+
+class BisectLog:
+    """A container and parser for the results of `git bisect log`.
+    """
+
+    class ParserBug(Exception):
+        pass
+
+    def __init__(self, log: str):
+        """Parse `log` and initialize the object."""
+        lines = [s.rstrip() for s in log.splitlines()]
+        self.judgments = BisectLog._extract_judgments(lines)
+        self.candidates = BisectLog._extract_candidates(lines)
+
+    @staticmethod
+    def _extract_judgments(
+            lines: List[str]) -> List[Tuple[CommitHash, CommitJudgment]]:
+        out = []
+        for line in lines:
+            if line == '' or line.startswith("#"):
+                continue
+            if line == 'git bisect start':
+                continue
+            match = re.match("^git bisect (good|bad|skip) ([0-9a-f]+)$", line)
+            if match is None:
+                raise BisectLog.ParserBug(
+                    "Failed to parse line: '{}'".format(line))
+            assert len(match.groups()) == 2
+            judgment, commit = match.groups()
+            if judgment == 'good':
+                out.append((CommitHash(commit), CommitJudgment.GOOD))
+            elif judgment == 'bad':
+                out.append((CommitHash(commit), CommitJudgment.BAD))
+            elif judgment == 'skip':
+                out.append((CommitHash(commit), CommitJudgment.SKIP))
+            else:
+                raise BisectLog.ParserBug("Unreachable")
+        return out
+
+    @staticmethod
+    def _extract_candidates(lines: List[str]) -> List[CommitHash]:
+        # Scan through the log to find a line indicating that there is a single
+        # first bad commit.
+        re_first_bad = re.compile(r"^# first bad commit: \[([0-9a-f]+)\] .*$")
+        for i, line in enumerate(lines):
+            match = re_first_bad.match(line)
+            if match is None:
+                continue
+            assert len(match.groups()) == 1
+            first_bad = match.group(1)
+            return [CommitHash(first_bad)]
+
+        # Scan through the log to find a sequence of possible first bad commits.
+        LOG_LINE_ONLY_SKIPPED = "# only skipped commits left to test"
+        candidate_lines = []
+        for i, line in reversed(list(enumerate(lines))):
+            # When only skipped commits remain, expect a sequence of "possible
+            # first bad commit" lines.
+            if line == LOG_LINE_ONLY_SKIPPED:
+                candidate_lines = lines[i + 1:]
+                break
+
+        re_possible_first_bad = re.compile(
+            r"^# possible first bad commit: \[([0-9a-f]+)\] .*$")
+        candidates = []
+        for line in candidate_lines:
+            match = re_possible_first_bad.match(line)
+            if match is None:
+                continue
+            assert len(match.groups()) == 1
+            commit = match.group(1)
+            candidates.append(CommitHash(commit))
+        return candidates
+
+
+class GitControllerABC(abc.ABC):
+    """An abstract Git interface that will never run the system `git`."""
+
+    @abc.abstractmethod
+    def _git(self, *args: str) -> Tuple[int, str, str]:
+        """Runs git with `args`. Returns (returncode, stdout, stderr)."""
+        pass
+
+    @abc.abstractmethod
+    def _git_no_capture_output(self, *args: str) -> int:
+        """Like `_git()`, but doesn't capture stdout/stderr."""
+        pass
+
+    def _git_checked(self, *args: str) -> Tuple[str, str]:
+        """Like _git(), but raises an exception when the returncode != 0."""
+        returncode, stdout, stderr = self._git(*args)
+        if returncode != 0:
+            lines = [
+                "Git exited with {}".format(returncode),
+                "---stdout---",
+                stdout,
+                "---stderr---",
+                stderr,
+            ]
+            raise Exception("\n".join(lines))
+        return (stdout, stderr)
+
+    def rev_parse(self, commitish: str) -> CommitHash:
+        stdout, _ = self._git_checked("rev-parse", commitish)
+        return CommitHash(stdout.rstrip())
+
+    def bisect_start(self):
+        self._git_checked("bisect", "start")
+
+    def bisect_reset(self):
+        self._git_checked("bisect", "reset")
+
+    def bisect_good(self, rev: CommitHash):
+        self._git_checked("bisect", "good", rev)
+
+    def bisect_bad(self, rev: CommitHash):
+        self._git_checked("bisect", "bad", rev)
+
+    def bisect_skip(self, rev: CommitHash):
+        self._git_checked("bisect", "skip", rev)
+
+    def bisect_run(self, *args: str) -> BisectLog:
+        """Executes `git bisect run` without capturing stdout/stderr."""
+        # Git's exit status is non-zero when bisect results are ambiguous.
+        _ = self._git_no_capture_output("bisect", "run", *args)
+        return self.bisect_log()
+
+    def bisect_log(self) -> BisectLog:
+        stdout, _ = self._git_checked("bisect", "log")
+        return BisectLog(stdout)
+
+    def bisect_view(self) -> List[Tuple[CommitHash, str]]:
+        stdout, _ = self._git_checked("bisect", "view", "--oneline",
+                                      "--no-abbrev-commit")
+        out = []
+        for line in stdout.splitlines():
+            commit, tail = line.split(" ", 1)
+            out.append((CommitHash(commit), tail))
+        return out
+
+
+class GitController(GitControllerABC):
+    """A concrete git controller that actually executes git commands."""
+
+    def __init__(self, git_binary: str, verbose: bool):
+        self._git_binary = git_binary
+        self._verbose = verbose
+        self._console = rich.console.Console()
+        self._env: Dict[str, str] = dict(os.environ)
+        # Prevent `git bisect view` from launching the `gitk` GUI.
+        self._env.pop("DISPLAY", None)
+
+    def _git(self, *args: str) -> Tuple[int, str, str]:
+        command = [self._git_binary] + list(args)
+        proc = subprocess.run(command,
+                              stdout=subprocess.PIPE,
+                              stderr=subprocess.PIPE,
+                              env=self._env,
+                              encoding="utf-8")
+        if self._verbose or proc.returncode != 0:
+            print()
+            command_str = " ".join(command)
+            rich.print(
+                "Command [green]{}[/green] exited with status {}".format(
+                    rich.markup.escape(command_str), proc.returncode))
+            rich.print(
+                rich.panel.Panel(rich.markup.escape(proc.stdout),
+                                 title="git stdout"))
+            rich.print(
+                rich.panel.Panel(rich.markup.escape(proc.stderr),
+                                 title="git stderr"))
+        return (proc.returncode, proc.stdout, proc.stderr)
+
+    def _git_no_capture_output(self, *args: str) -> int:
+        command = [self._git_binary] + list(args)
+        command_str = " ".join(command)
+        command_str = rich.markup.escape(command_str)
+        self._console.rule(
+            "Streaming output from [bold]{}".format(command_str))
+        proc = subprocess.run(["git"] + list(args), env=self._env)
+        self._console.rule("Git exited with status {}".format(proc.returncode))
+        self._console.print()
+        return proc.returncode
+
+
+class BisectSession:
+
+    def __init__(self,
+                 git: GitControllerABC,
+                 cache_keys: Set[CommitHash],
+                 visualize: bool = False):
+        self._git = git
+        self._cache_keys: Set[CommitHash] = cache_keys
+        self._console = rich.console.Console()
+        self._visualize = visualize
+
+    def run(self,
+            good_commit: CommitHash,
+            bad_commit: CommitHash,
+            fast_command: List[str],
+            slow_command: Optional[List[str]] = None) -> BisectLog:
+        """Run an unattended bisect session in one or two phases.
+
+        This method is conceptually equivalent to `git bisect run`. Unlike plain
+        `git bisect`, it runs in two phases. The first phase only operates on
+        cached bitstreams. This will only get us so far, so it optionally can
+        fall back to a slower command, e.g. one that builds the bitstreams it
+        tests.
+
+        Args:
+          good_commit:
+            Commit where `fast_command` and `slow_command` are known to succeed.
+          bad_commit:
+            Commit where `fast_command` and `slow_command` are known to fail.
+          fast_command:
+            A list of strings that represent a git-bisect script and args. These
+            are passed to `git-bisect run` in the first phase.
+          slow_command:
+            Just like `fast_command`, but for the second phase.  If this arg is
+            None, we skip the second phase.
+
+        Returns:
+          Parsed output from `git bisect log`, run after the final bisect phase.
+        """
+
+        self._git.bisect_start()
+        self._git.bisect_good(good_commit)
+        self._git.bisect_bad(bad_commit)
+
+        # Skip commits that aren't in the bitstream cache.
+        for commit, _ in self._git.bisect_view():
+            if commit not in self._cache_keys:
+                self._git.bisect_skip(commit)
+
+        self._maybe_visualize("Only testing commits with cached bitstreams")
+        bisect_log = self._git.bisect_run(*fast_command)
+
+        # Skip the second phase when results are unambiguous.
+        if len(bisect_log.candidates) == 1:
+            self._maybe_visualize("Final results")
+            self._git.bisect_reset()
+            return bisect_log
+
+        # Prepare a new git bisect session where we will run the slow script
+        # without the benefit of the bitstream cache. Replay all the "good" and
+        # "bad" commands, but none of the "skip" commands.
+        if slow_command is None:
+            self._git.bisect_reset()
+            return bisect_log
+
+        self._git.bisect_reset()
+        self._git.bisect_start()
+
+        # Replay only "good" and "bad" decisions from the previous phase. It's
+        # tempting to unconditionally skip cached commits, but it's better to
+        # simply reuse judgments from the previous phase. It's possible that the
+        # user-supplied `fast_command` chose to skip some cached commits for
+        # reasons outside the scope of this tool, and we now need to test them
+        # in the second phase.
+        for commit, judgment in bisect_log.judgments:
+            if judgment == CommitJudgment.GOOD:
+                self._git.bisect_good(commit)
+            elif judgment == CommitJudgment.BAD:
+                self._git.bisect_bad(commit)
+
+        self._maybe_visualize("Narrowing down ambiguous results")
+        bisect_log = self._git.bisect_run(*slow_command)
+
+        self._maybe_visualize("Final results")
+        self._git.bisect_reset()
+        return bisect_log
+
+    def _maybe_visualize(self, label: str):
+        """Prints a table summarizing the current range of commits."""
+        if not self._visualize:
+            return
+
+        table = rich.table.Table(
+            title="Bitstream Bisect Status: [bold]{}".format(label))
+        table.add_column("Commit")
+        table.add_column("Description")
+        table.add_column("Cached")
+        table.add_column("Judgment")
+
+        bisect_log = self._git.bisect_log()
+        judgment_dict: Dict[CommitHash,
+                            CommitJudgment] = dict(bisect_log.judgments)
+
+        for commit, description in self._git.bisect_view():
+            judgment = judgment_dict.get(commit)
+            table.add_row(commit, rich.markup.escape(description),
+                          "Cached" if commit in self._cache_keys else "",
+                          judgment.name if judgment else "")
+
+        self._console.print(table)
+
+
+app = typer.Typer(pretty_exceptions_enable=False,
+                  rich_markup_mode="rich",
+                  add_completion=False)
+
+
+@app.command(help=__doc__)
+def main(
+    good: str = typer.Option(..., help="Commit-ish for known-good revision."),
+    bad: str = typer.Option(..., help="Commit-ish for known-bad revision."),
+    fast_command: str = typer.Option(
+        ..., help="Command for testing commits with cached bitstreams."),
+    slow_command: Optional[str] = typer.Option(
+        None, help="Command that tests remaining commits in second phase."),
+    git_binary: str = typer.Option("/usr/bin/git", help="Path to Git binary."),
+    verbose: bool = typer.Option(
+        False, help="Log stdout/stderr of every git command."),
+):
+    # Escape the Bazel sandbox. Without this step, git would not find the .git/
+    # directory. Note that this works nicely with git worktrees.
+    workspace_dir = os.environ['BUILD_WORKSPACE_DIRECTORY']
+    os.chdir(workspace_dir)
+
+    # Create a Git controller capable of invoking the system's `git` binary. Use
+    # it to canonicalize potentially-symbolic "commitish" strings so we don't
+    # misinterpret them when a different commit is checked out.
+    git = GitController(git_binary, verbose)
+    good_commit = git.rev_parse(good)
+    bad_commit = git.rev_parse(bad)
+    print("Canonicalized good revision:", good_commit)
+    print("Canonicalized bad revision: ", bad_commit)
+
+    # NOTE: This will generate network traffic!
+    # Fetch a listing of the current bitstream cache.
+    bitstream_cache = BitstreamCache.MakeWithDefaults()
+    bitstream_cache.GetBitstreamsAvailable(refresh=True)
+    bitstream_cache_keys = set(bitstream_cache.available.keys())
+
+    fast_command_pieces = shlex.split(fast_command)
+    slow_command_pieces = shlex.split(
+        slow_command) if slow_command is not None else None
+
+    session = BisectSession(git, bitstream_cache_keys, visualize=True)
+    session.run(good_commit,
+                bad_commit,
+                fast_command_pieces,
+                slow_command=slow_command_pieces)
+    return 0
+
+
+if __name__ == '__main__':
+    app()
diff --git a/util/fpga/bitstream_bisect_test.py b/util/fpga/bitstream_bisect_test.py
new file mode 100644
index 0000000..ca222d0
--- /dev/null
+++ b/util/fpga/bitstream_bisect_test.py
@@ -0,0 +1,342 @@
+# Copyright lowRISC contributors.
+# Licensed under the Apache License, Version 2.0, see LICENSE for details.
+# SPDX-License-Identifier: Apache-2.0
+
+import unittest
+from typing import Tuple
+from unittest.mock import MagicMock, call
+
+from bitstream_bisect import (BisectLog, BisectSession, CommitHash,
+                              CommitJudgment, GitControllerABC)
+
+
+class MockableGitController(GitControllerABC):
+    """Provides stub implementations of GitControllerABC's abstract methods."""
+
+    def _git(self, *args: str) -> Tuple[int, str, str]:
+        raise Exception("_git unexpectedly called")
+
+    def _git_no_capture_output(self, *args: str) -> int:
+        returncode, _, _ = self._git(*args)
+        return returncode
+
+
+class TestCommitHash(unittest.TestCase):
+    """Test that CommitHash validates its inputs."""
+
+    def test_simple(self):
+        c = CommitHash("c1")
+        self.assertEqual(str(c), "c1")
+
+        c = CommitHash("deadbeef")
+        self.assertEqual(str(c), "deadbeef")
+        self.assertEqual(str(c), CommitHash("deadbeef"))
+
+    def test_non_lowercase(self):
+        c = CommitHash("C1")
+        self.assertEqual(str(c), "c1")
+        self.assertEqual(str(c), CommitHash("C1"))
+        self.assertEqual(str(c), CommitHash("c1"))
+
+        c = CommitHash("DEADBEEF")
+        self.assertEqual(str(c), "deadbeef")
+        self.assertEqual(str(c), CommitHash("DEADBEEF"))
+        self.assertEqual(str(c), CommitHash("deadbeef"))
+
+        c = CommitHash("DeAdBeEf")
+        self.assertEqual(str(c), "deadbeef")
+        self.assertEqual(str(c), CommitHash("DeAdBeEf"))
+        self.assertEqual(str(c), CommitHash("deadbeef"))
+
+    def test_invalid(self):
+        with self.assertRaises(Exception):
+            CommitHash("")
+        with self.assertRaises(Exception):
+            CommitHash("hello")
+        with self.assertRaises(Exception):
+            CommitHash("HEAD")
+
+
+class TestParseBisectLog(unittest.TestCase):
+
+    def test_one_line(self):
+        bisect_log = BisectLog("git bisect good c123")
+        self.assertEqual(bisect_log.judgments, [('c123', CommitJudgment.GOOD)])
+        self.assertEqual(bisect_log.candidates, [])
+
+        bisect_log = BisectLog("git bisect bad c123")
+        self.assertEqual(bisect_log.judgments, [('c123', CommitJudgment.BAD)])
+        self.assertEqual(bisect_log.candidates, [])
+
+        bisect_log = BisectLog("git bisect skip c123")
+        self.assertEqual(bisect_log.judgments, [('c123', CommitJudgment.SKIP)])
+        self.assertEqual(bisect_log.candidates, [])
+
+        bisect_log = BisectLog("")
+        self.assertEqual(bisect_log.judgments, [])
+        self.assertEqual(bisect_log.candidates, [])
+
+        bisect_log = BisectLog("git bisect start")
+        self.assertEqual(bisect_log.judgments, [])
+        self.assertEqual(bisect_log.candidates, [])
+
+    def test_unrecognized_actions_rejected(self):
+        """The parser should reject non-comment lines it doesn't understand."""
+        # Unexpected whitespace.
+        with self.assertRaises(BisectLog.ParserBug):
+            _ = BisectLog(" git bisect skip c123")
+        with self.assertRaises(BisectLog.ParserBug):
+            _ = BisectLog("git  bisect skip c123")
+        with self.assertRaises(BisectLog.ParserBug):
+            _ = BisectLog("git bisect  skip c123")
+        with self.assertRaises(BisectLog.ParserBug):
+            _ = BisectLog(" # git bisect  skip c123")
+        # Unrecognized action with commit.
+        with self.assertRaises(BisectLog.ParserBug):
+            _ = BisectLog("git bisect foo c123")
+        # Unrecognized action without commit.
+        with self.assertRaises(BisectLog.ParserBug):
+            _ = BisectLog("git bisect bar")
+
+    def test_unrecognized_comments_ignored(self):
+        bisect_log = BisectLog("# foo")
+        self.assertEqual(bisect_log.judgments, [])
+        self.assertEqual(bisect_log.candidates, [])
+
+    def test_candidates_simple(self):
+        bisect_log = BisectLog("")
+        self.assertEqual(bisect_log.judgments, [])
+        self.assertEqual(bisect_log.candidates, [])
+
+        bisect_log = BisectLog(
+            "# first bad commit: [c42] Commit description...")
+        self.assertEqual(bisect_log.judgments, [])
+        self.assertEqual(bisect_log.candidates, ["c42"])
+
+        bisect_log = BisectLog("""
+# only skipped commits left to test
+# possible first bad commit: [c123] Foo description
+# possible first bad commit: [c234] Bar description
+""")
+        self.assertEqual(bisect_log.judgments, [])
+        self.assertEqual(bisect_log.candidates, ["c123", "c234"])
+
+    def test_realistic_only_skipped_remain(self):
+        # This output was produced by `git` on a temporary repo.
+        BISECT_LOG = """# status: waiting for both good and bad commits
+# good: [0b47ff5f2ac78589cab7d9b93c4cabb9e4a1f736] First commit
+git bisect good 0b47ff5f2ac78589cab7d9b93c4cabb9e4a1f736
+# status: waiting for bad commit, 1 good commit known
+# bad: [4f166216806f44b1ddf67c4649d5e646cf9bbf22] Fourth commit
+git bisect bad 4f166216806f44b1ddf67c4649d5e646cf9bbf22
+# skip: [132c4e1f8773cd3e14e2f4de8a8b77422b74e28b] Third commit
+git bisect skip 132c4e1f8773cd3e14e2f4de8a8b77422b74e28b
+# skip: [8fe76ab59c4f7d43237292a57f1d84b774436224] Second commit
+git bisect skip 8fe76ab59c4f7d43237292a57f1d84b774436224
+# only skipped commits left to test
+# possible first bad commit: [4f166216806f44b1ddf67c4649d5e646cf9bbf22] Fourth commit
+# possible first bad commit: [132c4e1f8773cd3e14e2f4de8a8b77422b74e28b] Third commit
+# possible first bad commit: [8fe76ab59c4f7d43237292a57f1d84b774436224] Second commit
+# good: [8fe76ab59c4f7d43237292a57f1d84b774436224] Second commit
+git bisect good 8fe76ab59c4f7d43237292a57f1d84b774436224
+# only skipped commits left to test
+# possible first bad commit: [4f166216806f44b1ddf67c4649d5e646cf9bbf22] Fourth commit
+# possible first bad commit: [132c4e1f8773cd3e14e2f4de8a8b77422b74e28b] Third commit
+"""
+        bisect_log = BisectLog(BISECT_LOG)
+        self.assertEqual(bisect_log.candidates, [
+            "4f166216806f44b1ddf67c4649d5e646cf9bbf22",
+            "132c4e1f8773cd3e14e2f4de8a8b77422b74e28b"
+        ])
+        self.assertEqual(bisect_log.judgments, [
+            ("0b47ff5f2ac78589cab7d9b93c4cabb9e4a1f736", CommitJudgment.GOOD),
+            ("4f166216806f44b1ddf67c4649d5e646cf9bbf22", CommitJudgment.BAD),
+            ("132c4e1f8773cd3e14e2f4de8a8b77422b74e28b", CommitJudgment.SKIP),
+            ("8fe76ab59c4f7d43237292a57f1d84b774436224", CommitJudgment.SKIP),
+            ("8fe76ab59c4f7d43237292a57f1d84b774436224", CommitJudgment.GOOD),
+        ])
+
+    def test_realistic_has_first_bad_commit(self):
+        # This output was produced by `git` on a temporary repo.
+        BISECT_LOG = """git bisect start
+# status: waiting for both good and bad commits
+# good: [00722da469712cd917e59082601d189fe0c6507e] First commit
+git bisect good 00722da469712cd917e59082601d189fe0c6507e
+# status: waiting for bad commit, 1 good commit known
+# bad: [3e2031c1cb7b27e8bf36c85756c301279b8f9f30] Fourth commit
+git bisect bad 3e2031c1cb7b27e8bf36c85756c301279b8f9f30
+# bad: [dc5320f6d974d3fce7bcc03fd18d920c8b5e3cbf] Third commit
+git bisect bad dc5320f6d974d3fce7bcc03fd18d920c8b5e3cbf
+# bad: [d72b7491e6fdadb2ef742370410d5488a7bbfdba] Second commit
+git bisect bad d72b7491e6fdadb2ef742370410d5488a7bbfdba
+# first bad commit: [d72b7491e6fdadb2ef742370410d5488a7bbfdba] Second commit
+"""
+        bisect_log = BisectLog(BISECT_LOG)
+        self.assertEqual(bisect_log.candidates,
+                         ["d72b7491e6fdadb2ef742370410d5488a7bbfdba"])
+        self.assertEqual(bisect_log.judgments, [
+            ("00722da469712cd917e59082601d189fe0c6507e", CommitJudgment.GOOD),
+            ("3e2031c1cb7b27e8bf36c85756c301279b8f9f30", CommitJudgment.BAD),
+            ("dc5320f6d974d3fce7bcc03fd18d920c8b5e3cbf", CommitJudgment.BAD),
+            ("d72b7491e6fdadb2ef742370410d5488a7bbfdba", CommitJudgment.BAD),
+        ])
+
+
+class TestBisectSession(unittest.TestCase):
+
+    def test_two_cached_only_fast(self):
+        """Simple case with two cached commits and only the fast command."""
+
+        BISECT_LOG = """git bisect start
+# status: waiting for both good and bad commits
+# good: [c1] Fake good commit
+git bisect good c1
+# status: waiting for bad commit, 1 good commit known
+# bad: [c2] Fake bad commit
+git bisect bad c2
+# first bad commit: [c2] Fake bad commit
+"""
+
+        git = MockableGitController()
+        git._git = MagicMock(return_value=(0, "", ""))
+        git.bisect_view = MagicMock(return_value=[
+            (CommitHash("c1"), "Commit description"),
+            (CommitHash("c2"), "Commit description"),
+        ])
+        git.bisect_log = MagicMock(return_value=BisectLog(BISECT_LOG))
+
+        session = BisectSession(git, cache_keys=set(["c1", "c2"]))
+        result: BisectLog = session.run("c1", "c2", ["fast_script.sh"])
+
+        self.assertEqual(result.candidates, ["c2"])
+        git._git.assert_has_calls([
+            call("bisect", "start"),
+            call("bisect", "good", "c1"),
+            call("bisect", "bad", "c2"),
+            call('bisect', 'run', 'fast_script.sh'),
+            # We would expect `call('bisect', 'log')` here, but mocking
+            # `git.bisect_log()` prevented it from calling `git._git()`.
+            call('bisect', 'reset'),
+        ])
+        git.bisect_log.assert_called_once_with()
+        git.bisect_view.assert_called_once_with()
+
+    def test_only_fast(self):
+        """Mix of cached and uncached with only the fast command."""
+
+        BISECT_LOG = """git bisect start
+# status: waiting for both good and bad commits
+# skip: [c2] Skipped commit
+git bisect skip c2
+# good: [c1] Fake good commit
+git bisect good c1
+# status: waiting for bad commit, 1 good commit known
+# bad: [c3] Fake bad commit
+git bisect bad c3
+# only skipped commits left to test
+# possible first bad commit: [c2] Skipped commit
+# possible first bad commit: [c3] Fake bad commit
+"""
+
+        git = MockableGitController()
+        git._git = MagicMock(return_value=(0, "", ""))
+        git.bisect_view = MagicMock(return_value=[
+            (CommitHash("c1"), "Fake good commit"),
+            (CommitHash("c2"), "Skipped commit"),
+            (CommitHash("c3"), "Fake bad commit"),
+        ])
+
+        git.bisect_log = MagicMock(return_value=BisectLog(BISECT_LOG))
+
+        session = BisectSession(git, cache_keys=set(["c1", "c3"]))
+        bisect_log = session.run("c1", "c3", ["fast_script.sh"])
+
+        self.assertEqual(bisect_log.candidates, ["c2", "c3"])
+        git._git.assert_has_calls([
+            call("bisect", "start"),
+            call("bisect", "good", "c1"),
+            call("bisect", "bad", "c3"),
+            call("bisect", "skip", "c2"),
+            call('bisect', 'run', 'fast_script.sh'),
+            # We would expect `call('bisect', 'log')` here, but mocking
+            # `git.bisect_log()` prevented it from calling `git._git()`.
+        ])
+        git.bisect_log.assert_called_once_with()
+        git.bisect_view.assert_called_once_with()
+
+    def test_fast_and_slow(self):
+        """Mix of cached and uncached with fast and slow command."""
+
+        BISECT_LOG_1 = """git bisect start
+# status: waiting for both good and bad commits
+# good: [c1] Commit 1
+git bisect good c1
+# status: waiting for bad commit, 1 good commit known
+# bad: [c5] Commit 5
+git bisect bad c5
+# skip: [c3] Commit 3
+git bisect skip c3
+# skip: [c4] Commit 4
+git bisect skip c4
+# good: [c2] Commit 2
+git bisect good c2
+# only skipped commits left to test
+# possible first bad commit: [c3] Commit 3
+# possible first bad commit: [c4] Commit 4
+"""
+        BISECT_LOG_2 = """git bisect start
+# status: waiting for both good and bad commits
+# good: [c1] Commit 1
+git bisect good c1
+# status: waiting for bad commit, 1 good commit known
+# bad: [c5] Commit 5
+git bisect bad c5
+# good: [c2] Commit 2
+git bisect good c2
+# good: [c3] Commit 3
+git bisect good c3
+# bad: [c4] Commit 4
+git bisect bad c4
+# first bad commit: [c4] Commit 4
+"""
+        parsed_bisect_logs = [BisectLog(BISECT_LOG_1), BisectLog(BISECT_LOG_2)]
+
+        git = MockableGitController()
+        git._git = MagicMock(return_value=(0, "", ""))
+        git.bisect_log = MagicMock(side_effect=parsed_bisect_logs)
+
+        git.bisect_view = MagicMock(return_value=[
+            (CommitHash("c1"), "Commit 1"),
+            (CommitHash("c2"), "Commit 2"),
+            (CommitHash("c3"), "Commit 3"),
+            (CommitHash("c4"), "Commit 4"),
+            (CommitHash("c5"), "Commit 5"),
+        ])
+
+        session = BisectSession(git, cache_keys=set(["c1", "c2"]))
+        bisect_log = session.run("c1", "c5", ["fast_script.sh"],
+                                 ["slow_script.sh"])
+
+        self.assertEqual(bisect_log.candidates, ["c4"])
+
+        git._git.assert_has_calls([
+            call("bisect", "start"),
+            call("bisect", "good", "c1"),
+            call("bisect", "bad", "c5"),
+            call("bisect", "skip", "c3"),
+            call("bisect", "skip", "c4"),
+            call("bisect", "skip", "c5"),
+            call('bisect', 'run', 'fast_script.sh'),
+            call('bisect', 'reset'),
+            call('bisect', 'start'),
+            call('bisect', 'good', 'c1'),
+            call('bisect', 'bad', 'c5'),
+            call('bisect', 'good', 'c2'),
+            call('bisect', 'run', 'slow_script.sh'),
+        ])
+        git.bisect_log.assert_has_calls([call(), call()])
+        git.bisect_view.assert_called_once_with()
+
+
+if __name__ == '__main__':
+    unittest.main()