[pinpoint] Use _JobState.Differences() in _JobState.Explore().

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 219 matching lines @@
       self._changes.append(change)
 
     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.
+    distributions. 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)):
+    # This loop adds Changes to the _changes list while looping through it.

[perezju, 2017/09/19 13:54:52]

Actually, it doesn't. Because of "tuple" you're now iterating through a copy of
the original list. Which is fine!

[perezju, 2017/09/19 13:59:04]

Ah, ignore both my previous comments. I just noted why you need to yield the
index, and your comment here is indeed important.

[dtu, 2017/09/19 18:21:53]

Yep, the index is needed for the insertion. Since inserting elements
simultaneously uses and modifies the array indices, it's important to go
backwards.

+    # However, the loop index goes in reverse order and Changes are only added
+    # after the loop index, so the loop never encounters the modified items.
+    for index, change_b in reversed(tuple(self.Differences())):
       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)
-        except change_module.NonLinearError:
-          continue
-        logging.info('Adding Change %s.', midpoint)
-        self.AddChange(midpoint, index)
-      elif comparison_result == _SAME:
-        # The same: Do nothing.
+      try:
+        midpoint = change_module.Change.Midpoint(change_a, change_b)
+      except change_module.NonLinearError:
         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)
+
+      logging.info('Adding Change %s.', midpoint)
+      self.AddChange(midpoint, index)

[perezju, 2017/09/19 13:59:04]

Do we really need AddChange to be a public method?

[dtu, 2017/09/19 18:21:53]

One of the original interactivity feature plans was for the user to be able to
guide the course of the bisect by saying "please run this commit specifically."
While we might not expose something as low-level as AddChange() to the user, we
will probably want to use it to implement that kind of functionality.

 
   def ScheduleWork(self):
     work_left = False
     for attempts in self._attempts.itervalues():
       for attempt in attempts:
         if attempt.completed:
           continue
 
         attempt.ScheduleWork()
         work_left = True
 
     return work_left
 
   def Differences(self):
+    """Compares every pair of Changes and yields ones with different results.
+
+    This method loops through every pair of adjacent Changes. If they have
+    statistically different results, this method yields the latter one (which is
+    assumed to have caused the difference).
+
+    Yields:
+      Tuples of (change_index, Change).
+    """
     for index in xrange(1, len(self._changes)):
       change_a = self._changes[index - 1]
       change_b = self._changes[index]
       if self._Compare(change_a, change_b) == _DIFFERENT:
         yield index, change_b

[perezju, 2017/09/19 13:54:52]

Looking at what clients actually want, maybe it would be neater if you yield
(change_a, change_b)?

[dtu, 2017/09/19 18:21:53]

We will also need the index for AsDict(), below on line 316.

 
   def AsDict(self):
     comparisons = []
     for index in xrange(1, len(self._changes)):
       change_a = self._changes[index - 1]
       change_b = self._changes[index]
       comparisons.append(self._Compare(change_a, change_b))
 
     # result_values is a 3D array. result_values[change][quest] is a list of
     # all the result values for that Change and Quest.
@@ skipping 70 matching lines @@
 
   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