Add option (u)nknown to bisect-builds.py.

tools/bisect-builds.py

 #!/usr/bin/env python
 # Copyright (c) 2012 The Chromium Authors. All rights reserved.
 # Use of this source code is governed by a BSD-style license that can be
 # found in the LICENSE file.
 
 """Snapshot Build Bisect Tool
 
 This script bisects a snapshot archive using binary search. It starts at
 a bad revision (it will try to guess HEAD) and asks for a last known-good
 revision. It will then binary search across this revision range by downloading,
@@ skipping 23 matching lines @@
 
 DONE_MESSAGE = 'You are probably looking for a change made after ' \
                '%s (known good), but no later than %s (first known bad).'
 
 ###############################################################################
 
 import math
 import optparse
 import os
 import pipes
+import random
 import re
 import shutil
 import subprocess
 import sys
 import tempfile
 import threading
 import urllib
 from distutils.version import LooseVersion
 from xml.etree import ElementTree
 import zipfile
@@ skipping 280 matching lines @@
   except Exception, e:
     pass
 
   return (subproc.returncode, stdout, stderr)
 
 
 def AskIsGoodBuild(rev, official_builds, status, stdout, stderr):
   """Ask the user whether build |rev| is good or bad."""
   # Loop until we get a response that we can parse.
   while True:
-    response = raw_input('Revision %s is [(g)ood/(b)ad/(q)uit]: ' % str(rev))
-    if response and response in ('g', 'b'):
-      return response == 'g'
+    response = raw_input('Revision %s is [(g)ood/(b)ad/(u)nknown/(q)uit]: ' %
+                         str(rev))
+    if response and response in ('g', 'b', 'u'):
+      return response
     if response and response == 'q':
       raise SystemExit()
 
 
+class DownloadJob(object):
+  """DownloadJob represents a task to download a given Chromium revision."""
+  def __init__(self, context, name, rev, zipfile):
+    super(DownloadJob, self).__init__()
+    # Store off the input parameters.
+    self.context = context
+    self.name = name
+    self.rev = rev
+    self.zipfile = zipfile
+    self.quit_event = threading.Event()
+    self.progress_event = threading.Event()
+
+  def Start(self):
+    """Starts the download."""
+    fetchargs = (self.context,
+                 self.rev,
+                 self.zipfile,
+                 self.quit_event,
+                 self.progress_event)
+    self.thread = threading.Thread(target=FetchRevision,
+                                   name=self.name,
+                                   args=fetchargs)
+    self.thread.start()
+
+  def Stop(self):
+    """Stops the download which must have been started previously."""
+    self.quit_event.set()
+    self.thread.join()
+    os.unlink(self.zipfile)
+
+  def WaitFor(self):
+    """Prints a message and waits for the download to complete. The download
+    must have been started previously."""
+    print "Downloading revision %s..." % str(self.rev)
+    self.progress_event.set()  # Display progress of download.
+    self.thread.join()
+
+
 def Bisect(platform,
            official_builds,
            good_rev=0,
            bad_rev=0,
            num_runs=1,
            try_args=(),
            profile=None,
-           predicate=AskIsGoodBuild):
+           evaluate=AskIsGoodBuild):
   """Given known good and known bad revisions, run a binary search on all
   archived revisions to determine the last known good revision.
 
   @param platform Which build to download/run ('mac', 'win', 'linux64', etc.).
   @param official_builds Specify build type (Chromium or Official build).
   @param good_rev Number/tag of the last known good revision.
   @param bad_rev Number/tag of the first known bad revision.
   @param num_runs Number of times to run each build for asking good/bad.
   @param try_args A tuple of arguments to pass to the test application.
   @param profile The name of the user profile to run with.
-  @param predicate A predicate function which returns True iff the argument
-                   chromium revision is good.
+  @param evaluate A function which returns 'g' if the argument Chromium

[Robert Sesek, 2012/05/31 19:46:10]

Since this can now bisect official builds, just say "if the argument build is
good"

[Alexei Svitkine (slow), 2012/05/31 20:08:15]

Done.

+                  revision is good, 'b' if it's bad or 'u' if unknown.
 
   Threading is used to fetch Chromium revisions in the background, speeding up
   the user's experience. For example, suppose the bounds of the search are
   good_rev=0, bad_rev=100. The first revision to be checked is 50. Depending on
   whether revision 50 is good or bad, the next revision to check will be either
   25 or 75. So, while revision 50 is being checked, the script will download
   revisions 25 and 75 in the background. Once the good/bad verdict on rev 50 is
   known:
 
     - If rev 50 is good, the download of rev 25 is cancelled, and the next test
@@ skipping 23 matching lines @@
   if len(revlist) < 2:  # Don't have enough builds to bisect.
     msg = 'We don\'t have enough builds to bisect. revlist: %s' % revlist
     raise RuntimeError(msg)
 
   # Figure out our bookends and first pivot point; fetch the pivot revision.
   good = 0
   bad = len(revlist) - 1
   pivot = bad / 2
   rev = revlist[pivot]
   zipfile = _GetDownloadPath(rev)
-  progress_event = threading.Event()
-  progress_event.set()
-  print "Downloading revision %s..." % str(rev)
-  FetchRevision(context, rev, zipfile,
-                quit_event=None, progress_event=progress_event)
+  base_fetch = DownloadJob(context, 'base_fetch', rev, zipfile)
+  base_fetch.Start()
+  base_fetch.WaitFor()
 
   # Binary search time!
   while zipfile and bad - good > 1:
     # Pre-fetch next two possible pivots
     #   - down_pivot is the next revision to check if the current revision turns
     #     out to be bad.
     #   - up_pivot is the next revision to check if the current revision turns
     #     out to be good.
     down_pivot = int((pivot - good) / 2) + good
-    down_thread = None
+    down_fetch = None
     if down_pivot != pivot and down_pivot != good:
       down_rev = revlist[down_pivot]
-      down_zipfile = _GetDownloadPath(down_rev)
-      down_quit_event = threading.Event()
-      down_progress_event = threading.Event()
-      fetchargs = (context,
-                   down_rev,
-                   down_zipfile,
-                   down_quit_event,
-                   down_progress_event)
-      down_thread = threading.Thread(target=FetchRevision,
-                                     name='down_fetch',
-                                     args=fetchargs)
-      down_thread.start()
+      down_fetch = DownloadJob(context, 'down_fetch', down_rev,
+                               _GetDownloadPath(down_rev))
+      down_fetch.Start()
 
     up_pivot = int((bad - pivot) / 2) + pivot
-    up_thread = None
+    up_fetch = None
     if up_pivot != pivot and up_pivot != bad:
       up_rev = revlist[up_pivot]
-      up_zipfile = _GetDownloadPath(up_rev)
-      up_quit_event = threading.Event()
-      up_progress_event = threading.Event()
-      fetchargs = (context,
-                   up_rev,
-                   up_zipfile,
-                   up_quit_event,
-                   up_progress_event)
-      up_thread = threading.Thread(target=FetchRevision,
-                                   name='up_fetch',
-                                   args=fetchargs)
-      up_thread.start()
+      up_fetch = DownloadJob(context, 'up_fetch', up_rev,
+                             _GetDownloadPath(up_rev))
+      up_fetch.Start()
 
     # Run test on the pivot revision.
     (status, stdout, stderr) = RunRevision(context,
                                            rev,
                                            zipfile,
                                            profile,
                                            num_runs,
                                            try_args)
     os.unlink(zipfile)
     zipfile = None
 
-    # Call the predicate function to see if the current revision is good or bad.
+    # Call the evaluate function to see if the current revision is good or bad.
     # On that basis, kill one of the background downloads and complete the
     # other, as described in the comments above.
     try:
-      if predicate(rev, official_builds, status, stdout, stderr):
+      answer = evaluate(rev, official_builds, status, stdout, stderr)
+      if answer == 'g':
         good = pivot
-        if down_thread:
-          down_quit_event.set()  # Kill the download of older revision.
-          down_thread.join()
-          os.unlink(down_zipfile)
-        if up_thread:
-          print "Downloading revision %s..." % str(up_rev)
-          up_progress_event.set()  # Display progress of download.
-          up_thread.join()  # Wait for newer revision to finish downloading.
+        if down_fetch:
+          down_fetch.Stop()  # Kill the download of the older revision.
+        if up_fetch:
+          up_fetch.WaitFor()
           pivot = up_pivot
-          zipfile = up_zipfile
-      else:
+          zipfile = up_fetch.zipfile
+      elif answer == 'b':
         bad = pivot
-        if up_thread:
-          up_quit_event.set()  # Kill download of newer revision.
-          up_thread.join()
-          os.unlink(up_zipfile)
-        if down_thread:
-          print "Downloading revision %s..." % str(down_rev)
-          down_progress_event.set()  # Display progress of download.
-          down_thread.join()  # Wait for older revision to finish downloading.
+        if up_fetch:
+          up_fetch.Stop()  # Kill the download of the newer revision.
+        if down_fetch:
+          down_fetch.WaitFor()
           pivot = down_pivot
-          zipfile = down_zipfile
+          zipfile = down_fetch.zipfile
+      else:  # answer == 'u'

[Robert Sesek, 2012/05/31 19:46:10]

I'd just make this an elseif and then have an else with something like
NOTREACHED()

[Alexei Svitkine (slow), 2012/05/31 20:08:15]

Done.

+        # Nuke the revision from the revlist and choose a new pivot.
+        revlist.pop(pivot)
+        bad -= 1  # Assumes bad >= pivot.
+
+        fetch = None
+        if bad - good > 1:
+          # Randomly use down_pivot or up_pivot without affecting the range.
+          # Do this instead of setting the pivot to the midpoint of the new
+          # range because adjacent revisions are likely affected by the same
+          # issue that caused the (u)nknown response.
+          if up_fetch and down_fetch:
+            fetch = random.choice([up_fetch, down_fetch])

[Robert Sesek, 2012/05/31 19:46:10]

Any reason to do this instead of [up_fetch, down_fetch][bad % 2]? Gives a
similar pseudorandom effect. (or len(revlist))

[Alexei Svitkine (slow), 2012/05/31 20:08:15]

I like len(revlist), since this will alternate between using up/down. Done!

+          elif up_fetch:
+            fetch = up_fetch
+          else:
+            fetch = down_fetch
+          if fetch:

[Robert Sesek, 2012/05/31 19:46:10]

When would |fetch| be None still?

[Alexei Svitkine (slow), 2012/05/31 20:08:15]

If |down_fetch| is None, which I assumed could happen based on the structure of
the above code, which does:

 if up_fetch:
   up_fetch.Stop()
 if down_fetch:
   ...

... Instead of using an elif.

Although, I haven't reasoned whether such a case is possible. If it's not then,
we should change the code above too.

Let me think about it.

[Alexei Svitkine (slow), 2012/05/31 20:26:46]

So, this condition could happen if there are only 3 revisions in the revlist,
and bad=0,pivot=1,good=2. Since (good - bad > 1), this still qualified for entry
into the loop, but since there are no revisions between bad and pivot and pivot
and good, both down_fetch and up_fetch are None.

However, in this scenario, if we get the 'u' answer, we will have trimmed the
revlist to just two revisions, and hence bad - good > 1 will no longer hold, so
you're right that this shouldn't not happen here (if my reasoning is correct).

I'll remove the check here, but not above.

[Alexei Svitkine (slow), 2012/05/31 20:32:52]

Done.

+            fetch.WaitFor()
+            if fetch == up_fetch:
+              pivot = up_pivot - 1  # Subtracts 1 because revlist was resized.
+            else:
+              pivot = down_pivot
+            zipfile = fetch.zipfile
+
+        if down_fetch and fetch != down_fetch:
+          down_fetch.Stop()
+        if up_fetch and fetch != up_fetch:
+          up_fetch.Stop()
     except SystemExit:
       print "Cleaning up..."
       for f in [_GetDownloadPath(revlist[down_pivot]),
                 _GetDownloadPath(revlist[up_pivot])]:
         try:
           os.unlink(f)
         except OSError:
           pass
       sys.exit(0)
 
@@ skipping 121 matching lines @@
     print '  ' + WEBKIT_CHANGELOG_URL % (first_known_bad_webkit_rev,
                                          last_known_good_webkit_rev)
   print 'CHANGELOG URL:'
   if opts.official_builds:
     print OFFICIAL_CHANGELOG_URL % (last_known_good_rev, first_known_bad_rev)
   else:
     print '  ' + CHANGELOG_URL % (last_known_good_rev, first_known_bad_rev)
 
 if __name__ == '__main__':
   sys.exit(main())