Cache for successful test runs

By default don't re-run tests that have already run successfully, to
reduce latency between making a change and seeing if it fixed the last
thing that you were trying to fix.
diff --git a/tools/run_tests/jobset.py b/tools/run_tests/jobset.py
index bb1c862..7a6d979 100755
--- a/tools/run_tests/jobset.py
+++ b/tools/run_tests/jobset.py
@@ -1,6 +1,8 @@
 """Run a group of subprocesses and then finish."""
 
+import hashlib
 import multiprocessing
+import os
 import random
 import subprocess
 import sys
@@ -75,30 +77,43 @@
   sys.stdout.flush()
 
 
+def which(filename):
+  if '/' in filename:
+    return filename
+  for path in os.environ['PATH'].split(os.pathsep):
+    if os.path.exists(os.path.join(path, filename)):
+      return os.path.join(path, filename)
+  raise Exception('%s not found' % filename)
+
+
 class Job(object):
   """Manages one job."""
 
-  def __init__(self, cmdline, newline_on_success):
-    self._cmdline = ' '.join(cmdline)
+  def __init__(self, cmdline, bin_hash, newline_on_success):
+    self._cmdline = cmdline
+    self._bin_hash = bin_hash
     self._tempfile = tempfile.TemporaryFile()
     self._process = subprocess.Popen(args=cmdline,
                                      stderr=subprocess.STDOUT,
                                      stdout=self._tempfile)
     self._state = _RUNNING
     self._newline_on_success = newline_on_success
-    message('START', self._cmdline)
+    message('START', ' '.join(self._cmdline))
 
-  def state(self):
+  def state(self, update_cache):
     """Poll current state of the job. Prints messages at completion."""
     if self._state == _RUNNING and self._process.poll() is not None:
       if self._process.returncode != 0:
         self._state = _FAILURE
         self._tempfile.seek(0)
         stdout = self._tempfile.read()
-        message('FAILED', '%s [ret=%d]' % (self._cmdline, self._process.returncode), stdout)
+        message('FAILED', '%s [ret=%d]' % (
+            ' '.join(self._cmdline), self._process.returncode), stdout)
       else:
         self._state = _SUCCESS
-        message('PASSED', '%s' % self._cmdline, do_newline=self._newline_on_success)
+        message('PASSED', '%s' % ' '.join(self._cmdline),
+                do_newline=self._newline_on_success)
+        update_cache.finished(self._cmdline, self._bin_hash)
     return self._state
 
   def kill(self):
@@ -110,7 +125,7 @@
 class Jobset(object):
   """Manages one run of jobs."""
 
-  def __init__(self, check_cancelled, maxjobs, newline_on_success):
+  def __init__(self, check_cancelled, maxjobs, newline_on_success, cache):
     self._running = set()
     self._check_cancelled = check_cancelled
     self._cancelled = False
@@ -118,6 +133,7 @@
     self._completed = 0
     self._maxjobs = maxjobs
     self._newline_on_success = newline_on_success
+    self._cache = cache
 
   def start(self, cmdline):
     """Start a job. Return True on success, False on failure."""
@@ -125,7 +141,10 @@
       if self.cancelled(): return False
       self.reap()
     if self.cancelled(): return False
-    self._running.add(Job(cmdline, self._newline_on_success))
+    with open(which(cmdline[0])) as f:
+      bin_hash = hashlib.sha1(f.read()).hexdigest()
+    if self._cache.should_run(cmdline, bin_hash):
+      self._running.add(Job(cmdline, bin_hash, self._newline_on_success))
     return True
 
   def reap(self):
@@ -133,7 +152,7 @@
     while self._running:
       dead = set()
       for job in self._running:
-        st = job.state()
+        st = job.state(self._cache)
         if st == _RUNNING: continue
         if st == _FAILURE: self._failures += 1
         dead.add(job)
@@ -165,13 +184,24 @@
   return False
 
 
+# cache class that caches nothing
+class NoCache(object):
+  def should_run(self, cmdline, bin_hash):
+    return True
+
+  def finished(self, cmdline, bin_hash):
+    pass
+
+
 def run(cmdlines,
         check_cancelled=_never_cancelled,
         maxjobs=None,
-        newline_on_success=False):
+        newline_on_success=False,
+        cache=None):
   js = Jobset(check_cancelled,
               maxjobs if maxjobs is not None else _DEFAULT_MAX_JOBS,
-              newline_on_success)
+              newline_on_success,
+              cache if cache is not None else NoCache())
   for cmdline in shuffle_iteratable(cmdlines):
     if not js.start(cmdline):
       break