[pinpoint] Calculate distances between Changes.

dashboard/dashboard/pinpoint/models/job.py

Index: dashboard/dashboard/pinpoint/models/job.py
diff --git a/dashboard/dashboard/pinpoint/models/job.py b/dashboard/dashboard/pinpoint/models/job.py
index a2bf223084ee3787ffaf551eec2d48e5847920e5..bc95bfcd8dd3eb1ef2bf11d61812b9e40ed1366c 100644
--- a/dashboard/dashboard/pinpoint/models/job.py
+++ b/dashboard/dashboard/pinpoint/models/job.py
@@ -213,6 +213,9 @@ class _JobState(object):
     # _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 = {}
@@ -223,12 +226,24 @@ class _JobState(object):
     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)
@@ -257,11 +272,16 @@ class _JobState(object):
       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
@@ -315,6 +335,7 @@ class _JobState(object):
     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,
@@ -353,6 +374,14 @@ class _JobState(object):
     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: