[pinpoint] Calculate distances between Changes.

dashboard/dashboard/pinpoint/models/job.py

 # Copyright 2016 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.
 
 import collections
 import logging
 import os
 import traceback
 
 from google.appengine.api import taskqueue
@@ skipping 195 matching lines @@
       repeat_count: The number of attempts to automatically run per Change.
     """
     # _quests is mutable. Any modification should mutate the existing list
     # in-place rather than assign a new list, because every Attempt references
     # this object and will be updated automatically if it's mutated.
     self._quests = list(quests)
 
     # _changes can be in arbitrary order. Client should not assume that the
     # list of Changes is sorted in any particular order.
     self._changes = []
+    # _change_distances[i] contains the distance, in commits, between
+    # _changes[i-1] and _changes[i]. _change_distances[0] is always 0.
+    self._change_distances = []
 
     # A mapping from a Change to a list of Attempts on that Change.
     self._attempts = {}
 
     self._repeat_count = repeat_count
 
   def AddAttempt(self, change):
     assert change in self._attempts
     self._attempts[change].append(attempt_module.Attempt(self._quests, change))
 
-  def AddChange(self, change, index=None):
-    if index:
-      self._changes.insert(index, change)
-    else:
-      self._changes.append(change)
+  def AddChange(self, change, index=None, distances=(None, None)):
+    if index is None:
+      index = len(self._changes)
 
+    # Compute distances, if needed.
+    left, right = distances
+    if left is None:
+      left = _ChangeDistance(self._changes[index - 1], change) if index else 0
+    if right is None and index < len(self._changes):
+      right = _ChangeDistance(change, self._changes[index])
+
+    # Insert into _changes and _change_distances.
+    if right is not None:
+      self._change_distances[index] = right
+    self._change_distances.insert(index, left)
+    self._changes.insert(index, change)
+
+    # Add Attempts.
     self._attempts[change] = []
     for _ in xrange(self._repeat_count):
       self.AddAttempt(change)
 
   def Explore(self):
     """Compare Changes and bisect by adding additional Changes as needed.
 
     For every pair of adjacent Changes, compare their results as probability
     distributions. If more information is needed to establish statistical
     confidence, add an additional Attempt. If the results are different, find
     the midpoint of the Changes and add it to the Job.
 
     The midpoint can only be added if the second Change represents a commit that
     comes after the first Change. Otherwise, this method won't explore further.
     For example, if Change A is repo@abc, and Change B is repo@abc + patch,
     there's no way to pick additional Changes to try.
     """
     # Compare every pair of Changes.
     # TODO: The list may Change while iterating through it.
     # TODO: Use JobState.Differences().
     for index in xrange(1, len(self._changes)):
       change_a = self._changes[index - 1]
       change_b = self._changes[index]
 
       comparison_result = self._Compare(change_a, change_b)
       if comparison_result == _DIFFERENT:
         # Different: Bisect and add an additional Change to the job.
         try:
-          midpoint = change_module.Change.Midpoint(change_a, change_b)
+          midpoint, distances = change_module.Change.Midpoint(change_a,
+                                                              change_b)
         except change_module.NonLinearError:
           continue
+        left, right = distances
+        if not (left and right):
+          continue
+
         logging.info('Adding Change %s.', midpoint)
-        self.AddChange(midpoint, index)
+        self.AddChange(midpoint, index, distances)
       elif comparison_result == _SAME:
         # The same: Do nothing.
         continue
       elif comparison_result == _UNKNOWN:
         # Unknown: Add an Attempt to the Change with the fewest Attempts.
         change = min(change_a, change_b, key=lambda c: len(self._attempts[c]))
         self.AddAttempt(change)
 
   def ScheduleWork(self):
     work_left = False
@@ skipping 33 matching lines @@
 
       result_values.append(change_result_values)
 
     attempts = []
     for c in self._changes:
       attempts.append([attempt.AsDict() for attempt in self._attempts[c]])
 
     return {
         'quests': map(str, self._quests),
         'changes': [change.AsDict() for change in self._changes],
+        'change_distances': self._change_distances,
         # TODO: Use JobState.Differences().
         'comparisons': comparisons,
         'result_values': result_values,
         'attempts': attempts,
     }
 
   def _Compare(self, change_a, change_b):
     attempts_a = self._attempts[change_a]
     attempts_b = self._attempts[change_b]
 
@@ skipping 18 matching lines @@
     # Here, "the same" means that we fail to reject the null hypothesis. We can
     # never be completely sure that the two Changes have the same results, but
     # we've run everything that we planned to, and didn't detect any difference.
     if (len(attempts_a) >= self._repeat_count and
         len(attempts_b) >= self._repeat_count):
       return _SAME
 
     return _UNKNOWN
 
 
+def _ChangeDistance(change_a, change_b):
+  try:
+    _, distances = change_module.Change.Midpoint(change_a, change_b)
+    return sum(distances)
+  except change_module.NonLinearError:
+    return 1
+
+
 def _CombineResultsPerQuest(attempts):
   aggregate_results = collections.defaultdict(list)
   for attempt in attempts:
     if not attempt.completed:
       continue
 
     for quest, results in attempt.result_values.iteritems():
       aggregate_results[quest] += results
 
   return aggregate_results
 
 
 def _CompareValues(values_a, values_b):
   if not (values_a and values_b):
     return _UNKNOWN
 
   try:
     p_value = mann_whitney_u.MannWhitneyU(values_a, values_b)
   except ValueError:
     return _UNKNOWN
 
   if p_value < _SIGNIFICANCE_LEVEL:
     return _DIFFERENT
   else:
     return _UNKNOWN