[Findit] Use results from heuristic analysis to do faster culprit finding.

scripts/slave/recipes/findit/chromium/compile.py

Index: scripts/slave/recipes/findit/chromium/compile.py
diff --git a/scripts/slave/recipes/findit/chromium/compile.py b/scripts/slave/recipes/findit/chromium/compile.py
index 194d4af194c3b00d23031abbf112b4a30fff29c3..9d049c890dc19cd165e7f3213f1cfa005fbc9b80 100644
--- a/scripts/slave/recipes/findit/chromium/compile.py
+++ b/scripts/slave/recipes/findit/chromium/compile.py
@@ -19,6 +19,7 @@ DEPS = [
     'recipe_engine/platform',
     'recipe_engine/properties',
     'recipe_engine/python',
+    'recipe_engine/raw_io',
     'recipe_engine/step',
 ]
 
@@ -39,6 +40,9 @@ PROPERTIES = {
     'use_analyze': Property(
         kind=Single(bool, empty_val=False, required=False), default=True,
         help='Use analyze to filter out affected targets.'),
+    'suspected_revisions': Property(
+        kind=List(basestring), default=[],
+        help='A list of suspected revisions from heuristic analysis.'),
 }
 
 
@@ -46,6 +50,7 @@ class CompileResult(object):
   SKIPPED = 'skipped'  # No compile is needed.
   PASSED = 'passed'  # Compile passed.
   FAILED = 'failed'  # Compile failed.
+  INFRA_FAILED = 'infra_failed'  # Infra failed.
 
 
 def _run_compile_at_revision(api, target_mastername, target_buildername,
@@ -107,7 +112,7 @@ def _run_compile_at_revision(api, target_mastername, target_buildername,
 
 def RunSteps(api, target_mastername, target_buildername,
              good_revision, bad_revision,
-             compile_targets, use_analyze):
+             compile_targets, use_analyze, suspected_revisions):
   bot_config = api.chromium_tests.create_bot_config_object(
       target_mastername, target_buildername)
   api.chromium_tests.configure_build(
@@ -117,36 +122,127 @@ def RunSteps(api, target_mastername, target_buildername,
   api.chromium_tests.prepare_checkout(
       bot_config,
       root_solution_revision=bad_revision)
+
+  # Retrieve revisions in the regression range. The returned revisions are in
+  # order from older one to newer one.

[lijeffrey, 2016/04/11 23:52:58]

nit: in order from oldest to newest.

[stgao, 2016/04/12 01:29:56]

Done.

   revisions_to_check = api.findit.revisions_between(good_revision, bad_revision)
 
+  # If suspected commits are provided, divide the big regression range into
+  # a list of smaller sub-ranges. A sub-range starts at the revision right
+  # before a suspected revision.
+  #
+  # Example (previous build cycle passed at r0):
+  #   Entire regression range: [r1, r2, r3, r4, ..., r10]
+  #   Suspected commits: [r5, r8]
+  # Then the sub-ranges are:
+  #   sub-range1: r7 and [r8, r9, r10]
+  #   sub-range2: r4 and [r5, r6, r7]

[lijeffrey, 2016/04/11 23:52:58]

nit: shouldn't this be r4 and [r5, r6]?

[stgao, 2016/04/12 01:29:56]

Good catch.

+  #   sub-range3: None and [r1, r2, r3]
+  #
+  # Sub-ranges with new revisions are checked first, because a compile failure

[lijeffrey, 2016/04/11 23:52:58]

per discussion, maybe include a comment how if there are 2 suspected CLs its is
more common than not that it is due to 2 conflicting changes, in which case the
later commit is the triggering culprit which is why we check the later one
first.

The comment as it is sounds like this is a corner case, when it's actually the
general case.

[stgao, 2016/04/12 01:29:56]

Done. Good idea.

+  # might be due to conflicting commits in which case the later one should be
+  # the beginning of the compile breakage.
+  #
+  # In a sub-range, we check the revision right before the suspected one (e.g.
+  # r7 and r4 above) first:
+  # * if that revision fails, the remaining revisions in the same sub-range
+  #   need no checking, because there are only two cases:
+  #     case 1: the culprit is that revision itself
+  #     case 2: the culprit is in a sub-range with older revisions
+  # * if that revision passes, we keep checking remaining revisions in the same
+  #   sub-range:
+  #     case 3: if any revision fails, the culprit is found since it is the
+  #       first failure after a row of pass.
+  #     case 4: if no revision fails, the culprit is either case 1 above or
+  #       there is no culprit and the compile failure is a flaky one.
+  #
+  # In the example above:
+  # * if r8 is the actual culprit, r7 should pass. We continue checking r8 which
+  #   should fail and we find r8.
+  # * if r5 is the actual culprit, r7 should fail. We skip [r8, r9, r10],
+  #   instead check r4 and r5 in the sub-range2 and find r5.
+  # * if r7 is the actual culprit, r7 should fail. We skip [r8, r9, r10],
+  #   instead check revisions in the sub-range2 which should all pass, and we
+  #   find r7.
+  # * if r1 is the actual culprit, we check r7 and r4 before checking the

[lijeffrey, 2016/04/11 23:52:58]

Question: So in this case, this is the worst, because we check r7, find it is
red, then have to go back to r4 (with no incremental compile benefit), then find
it's also red, and have to start over from r1 (again with no incremental compile
benefit), and possibly even worse it's actually r3? (I'll follow up with Dan to
see if artifacts from r0 are in fact cached somewhere and if we can access it it
should mitigate this problem even if we have to do r7 then r4 then r1)

[stgao, 2016/04/12 01:29:56]

If the failure is a CC or CXX compile failure, it won't be that worse, because 
usually only 2-4k objects need compiling.
For link failure, the worst case here might be an issue, because much more
objects need compiling. We could check how it goes in actual runs and then come
up with better solution in such case.

The cached artifacts from r0 will always be helpful in either case, especially
when the slave is not up-to-date enough.

+  #   sub-range3 in which r0 is skipped because it is known as good revision in
+  #   previous build cycle.
+  suspected_revision_index  = [

[lijeffrey, 2016/04/11 23:52:58]

nit: remove 1 space before =

[stgao, 2016/04/12 01:29:56]

Done.

+      revisions_to_check.index(r)
+        for r in set(suspected_revisions) if r in revisions_to_check]
+  if suspected_revision_index:
+    sub_ranges = []
+    remaining_revisions = revisions_to_check[:]
+    for index in sorted(suspected_revision_index, reverse=True):
+      if index > 0:
+        sub_ranges.append(remaining_revisions[index - 1:])
+        remaining_revisions = remaining_revisions[:index - 1]
+    # None is a placeholder for the known good revision.
+    sub_ranges.append([None] + remaining_revisions)
+  else:
+    sub_ranges = [[None] + revisions_to_check]
+
   compile_results = {}
   try_job_metadata = {
-      'regression_range_size': len(revisions_to_check)
+      'regression_range_size': len(revisions_to_check),
+      'sub_ranges': sub_ranges[:],
   }
   report = {
       'result': compile_results,
       'metadata': try_job_metadata,
   }
 
+  suspected_revision = None
+  revision_being_checked = None
+  found = False
   try:
-    for current_revision in revisions_to_check:
-      last_revision = None
-      compile_result = _run_compile_at_revision(
-          api, target_mastername, target_buildername,
-          current_revision, compile_targets, use_analyze)
-
-      compile_results[current_revision] = compile_result
-      last_revision = current_revision
-      if compile_result == CompileResult.FAILED:
-        break  # Found the culprit, no need to check later revisions.
+    while not found and sub_ranges:
+      first_revision = sub_ranges[0][0]
+      following_revisions = sub_ranges[0][1:]
+      sub_ranges.pop(0)
+
+      if first_revision is not None:  # No compile for the known good revision.
+        revision_being_checked = first_revision
+        compile_result = _run_compile_at_revision(
+            api, target_mastername, target_buildername,
+            first_revision, compile_targets, use_analyze)
+        compile_results[first_revision] = compile_result
+        if compile_result == CompileResult.FAILED:
+          # The first revision of this range already failed, thus either it is
+          # the culprit or the culprit is in a range with older revisions.
+          suspected_revision = first_revision
+          continue
+
+      # If first revision passed, the culprit is either in the current range or
+      # is the first revision of previous range as identified above.

[lijeffrey, 2016/04/11 23:52:58]

is this comment always true?

for example in our case, we have r5 and r8 as suspects, so r7 is the first
revision. If r7 passes, doesn't that mean the culprit should be in [r8, r9,
r10], but "or is the first revision of previous range" suggests it's also
possible it's r4?

[stgao, 2016/04/12 01:29:56]

Sorry for the confusion. I updated the wording and also the example above.

We test [r7,..., r10] before [r4, ..., r6].
If r7 passes, the culprit is in [r8, ..., r10].
If r7 fails and r4 passes, r7 might be the culprit. And this is the case
described here.

+      for revision in following_revisions:
+        revision_being_checked = revision
+        compile_result = _run_compile_at_revision(
+            api, target_mastername, target_buildername,
+            revision, compile_targets, use_analyze)
+        compile_results[revision] = compile_result
+        if compile_result == CompileResult.FAILED:
+          # First failure after a serial of pass.

[lijeffrey, 2016/04/11 23:52:58]

nit: a series of passes

[stgao, 2016/04/12 01:29:56]

Done.

+          suspected_revision = revision
+          found = True
+          break
+
+      if not found and suspected_revision is not None:
+        # If all revisions in the current range passed, and the first revision
+        # of previous range failed, the culprit is found too.
+        found = True
+  except api.step.InfraFailure:
+    compile_results[revision_being_checked] = CompileResult.INFRA_FAILED
+    raise
   finally:
     # Report the result.
     step_result = api.python.succeeding_step(
         'report', [json.dumps(report, indent=2)], as_log='report')
 
-    if (last_revision and
-        compile_results.get(last_revision) == CompileResult.FAILED):
-      step_result.presentation.step_text = '<br/>Culprit: %s' % last_revision
+    if found:
+      step_result.presentation.step_text = (
+          '<br/>Culprit: <a href="https://crrev.com/%s">%s</a>' % (
+              suspected_revision, suspected_revision))
 
     # Set the report as a build property too, so that it will be reported back
     # to Buildbucket and Findit will pull from there instead of buildbot master.
@@ -156,7 +252,9 @@ def RunSteps(api, target_mastername, target_buildername,
 
 
 def GenTests(api):
-  def props(compile_targets=None, use_analyze=False):
+  def props(compile_targets=None, use_analyze=False,
+            good_revision=None, bad_revision=None,
+            suspected_revisions=None):
     properties = {
         'mastername': 'tryserver.chromium.linux',
         'buildername': 'linux_variable',
@@ -164,12 +262,14 @@ def GenTests(api):
         'buildnumber': '1',
         'target_mastername': 'chromium.linux',
         'target_buildername': 'Linux Builder',
-        'good_revision': 'r0',
-        'bad_revision': 'r1',
+        'good_revision': good_revision or 'r0',
+        'bad_revision': bad_revision or 'r1',
         'use_analyze': use_analyze,
     }
     if compile_targets:
       properties['compile_targets'] = compile_targets
+    if suspected_revisions:
+      properties['suspected_revisions'] = suspected_revisions
     return api.properties(**properties) + api.platform.name('linux')
 
   yield (
@@ -317,3 +417,118 @@ def GenTests(api):
           })
       )
   )
+
+  # Entire regression range: (r1, r6]
+  # Suspected_revisions: [r4]
+  # Expected smaller ranges: [r3, [r4, r5, r6]], [None, [r2]]
+  # Actual culprit: r4
+  # Should only run compile on r3, and then r4.
+  yield (
+      api.test('find_culprit_in_middle_of_a_sub_range') +
+      props(compile_targets=['target_name'],
+            good_revision='r1',
+            bad_revision='r6',
+            suspected_revisions=['r4']) +
+      api.override_step_data(
+          'git commits in range',
+          api.raw_io.stream_output(
+              '\n'.join('r%d' % i for i in reversed(range(2, 7))))) +
+      api.override_step_data('test r3.check_targets',
+                             api.json.output({
+                                 'found': ['target_name'],
+                                 'not_found': [],
+                             })) +
+      api.override_step_data('test r4.check_targets',
+                             api.json.output({
+                                 'found': ['target_name'],
+                                 'not_found': [],
+                             })) +
+      api.override_step_data('test r4.compile', retcode=1)
+  )
+
+  # Entire regression range: (r1, r6]
+  # Suspected_revisions: [r4]
+  # Expected smaller ranges: [r3, [r4, r5, r6]], [None, [r2]]
+  # Actual culprit: r3
+  # Should only run compile on r3, and then r2.
+  yield (
+      api.test('find_culprit_at_first_revision_of_a_sub_range') +
+      props(compile_targets=['target_name'],
+            good_revision='r1',
+            bad_revision='r6',
+            suspected_revisions=['r4']) +
+      api.override_step_data(
+          'git commits in range',
+          api.raw_io.stream_output(
+              '\n'.join('r%d' % i for i in reversed(range(2, 7))))) +
+      api.override_step_data('test r3.check_targets',
+                             api.json.output({
+                                 'found': ['target_name'],
+                                 'not_found': [],
+                             })) +
+      api.override_step_data('test r3.compile', retcode=1) +
+      api.override_step_data('test r2.check_targets',
+                             api.json.output({
+                                 'found': ['target_name'],
+                                 'not_found': [],
+                             }))
+  )
+
+  # Entire regression range: (r1, r10]
+  # Suspected_revisions: [r4, r8]
+  # Expected smaller ranges:
+  #     [r7, [r8, r9, r10]], [r3, [r4, r5, r6]], [None, [r2]]
+  # Actual culprit: r4
+  # Should only run compile on r7(failed), then r3(pass) and r4(failed).
+  yield (
+      api.test('find_culprit_in_second_sub_range') +
+      props(compile_targets=['target_name'],
+            good_revision='r1',
+            bad_revision='r6',
+            suspected_revisions=['r4', 'r8']) +
+      api.override_step_data(
+          'git commits in range',
+          api.raw_io.stream_output(
+              '\n'.join('r%d' % i for i in reversed(range(2, 11))))) +
+      api.override_step_data('test r7.check_targets',
+                             api.json.output({
+                                 'found': ['target_name'],
+                                 'not_found': [],
+                             })) +
+      api.override_step_data('test r7.compile', retcode=1) +
+      api.override_step_data('test r3.check_targets',
+                             api.json.output({
+                                 'found': ['target_name'],
+                                 'not_found': [],
+                             })) +
+      api.override_step_data('test r4.check_targets',
+                             api.json.output({
+                                 'found': ['target_name'],
+                                 'not_found': [],
+                             })) +
+      api.override_step_data('test r4.compile', retcode=1)
+  )
+
+  # Entire regression range: (r1, r5]
+  # Suspected_revisions: [r2]
+  # Expected smaller ranges:
+  #     [None, r2, r3, r4, r5]
+  # Actual culprit: r2
+  # Should only run compile on r2(failed).
+  yield (
+      api.test('find_culprit_as_first_revision_of_entire_range') +
+      props(compile_targets=['target_name'],
+            good_revision='r1',
+            bad_revision='r5',
+            suspected_revisions=['r2']) +
+      api.override_step_data(
+          'git commits in range',
+          api.raw_io.stream_output(
+              '\n'.join('r%d' % i for i in reversed(range(2, 6))))) +
+      api.override_step_data('test r2.check_targets',
+                             api.json.output({
+                                 'found': ['target_name'],
+                                 'not_found': [],
+                             })) +
+      api.override_step_data('test r2.compile', retcode=1)
+  )