[pinpoint] Calculate distances between Changes.

dashboard/dashboard/pinpoint/models/change/change.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 itertools
 
 from dashboard.pinpoint.models.change import commit as commit_module
 from dashboard.pinpoint.models.change import patch as patch_module
 
@@ skipping 55 matching lines @@
                     for commit in data['commits'])
     if 'patch' in data:
       patch = patch_module.Patch.FromDict(data['patch'])
     else:
       patch = None
 
     return cls(commits, patch=patch)
 
   @classmethod
   def Midpoint(cls, change_a, change_b):
     """Returns a Change halfway between the two given Changes.

[perezju, 2017/09/20 15:29:41]

After thinking through this, I think the important invariant that makes this
work (and why you complained about my example on your previous CL that: "These A
and B are only possible if the user explicitly set it that way") is that:

 for each pair (commit_a, commit_b) in zip(change_a.commits, change_b.commits)

 at most one of those pairs has a distance > 1; specifically the pair of commits
for the deepest nested DEP'ed repo which we most recently expanded into; commit
pairs for all other repos should be adjacent to each other (distance == 1).

Does that make sense? Is it correct?

If so, we should probably make that requirement explicit in the code. Should
also help to simplify the logic (I think) and make it easier to understand.

 
     This function does two passes over the Changes' Commits:
     * The first pass attempts to match the lengths of the Commit lists by
       expanding DEPS to fill in any repositories that are missing from one,
       but included in the other.
     * The second pass takes the midpoint of every matched pair of Commits,
       expanding DEPS rolls as it comes across them.
 
     A NonLinearError is raised if there is no valid midpoint. The Changes are
     not linear if any of the following is true:
       * They have different patches.
       * Their repositories don't match even after expanding DEPS rolls.
-      * The left Change comes after the right Change.
-      * They are the same or adjacent.
+      * The left Change does not come before the right Change.
     See change_test.py for examples of linear and nonlinear Changes.
 
+    If the range has an even number of Changes, the midpoint is the Change just
+    before the halfway point. The range includes both change_a and change_b;
+    i.e. if change_a and change_b are adjacent or the same, the midpoint is
+    change_a.
+
     Args:
       change_a: The first Change in the range.
       change_b: The last Change in the range.
 
     Returns:
-      A new Change representing the midpoint.
-      The Change before the midpoint if the range has an even number of commits.
+      A tuple of (Change, (left, right)). left and right are the distances

[perezju, 2017/09/19 15:58:05]

I think it's cleaner if it returns just (change, left, right)

+      between the midpoint and change_a and change_b, respectively.
 
     Raises:
       NonLinearError: The Changes are not linear.
     """
     if change_a.patch != change_b.patch:
       raise commit_module.NonLinearError(
           'Change A has patch "%s" and Change B has patch "%s".' %
           (change_a.patch, change_b.patch))
 
     commits_a = list(change_a.commits)
     commits_b = list(change_b.commits)
 
     _ExpandDepsToMatchRepositories(commits_a, commits_b)
-    commits_midpoint = _FindMidpoints(commits_a, commits_b)
+    midpoints = _FindMidpoints(commits_a, commits_b)
+    commits_midpoint, distances = zip(*midpoints)
 
-    if commits_a == commits_midpoint:
-      raise commit_module.NonLinearError('Changes are the same or adjacent.')
-
-    return cls(commits_midpoint, change_a.patch)
+    midpoint = cls(commits_midpoint, change_a.patch)
+    distances = tuple(map(max, zip(*distances)))
+    return midpoint, distances
 
 
 def _ExpandDepsToMatchRepositories(commits_a, commits_b):
   """Expands DEPS in a Commit list to match the repositories in another.
 
   Given two lists of Commits, with one bigger than the other, this function
   looks through the DEPS files for smaller commit list to fill out any missing
   Commits that are already in the bigger commit list.
 
   Mutates the lists in-place, and doesn't return anything. The lists will not
@@ skipping 23 matching lines @@
     # Look through commits_b for any extra slots to fill with the DEPS.
     for commit_b in commits_b[len(commits_a):]:
       dep_a = _FindCommitWithRepository(deps_a, commit_b.repository)
       if dep_a:
         commits_a.append(dep_a)
       else:
         break
 
 
 def _FindMidpoints(commits_a, commits_b):
-  """Returns the midpoint of two Commit lists.
+  """Returns the midpoints of two Commit lists.
 
   Loops through each pair of Commits and takes the midpoint. If the repositories
   don't match, a NonLinearError is raised. If the Commits are adjacent and
   represent a DEPS roll, the differing DEPs are added to the end of the lists.
 
   Args:
     commits_a: A list of Commits.
     commits_b: A list of Commits.
 
   Returns:
-    A list of Commits, each of which is the midpoint of the respective Commit in
-    commits_a and commits_b.
+    A list of tuples. Each tuple is the result of Commit.Midpoint().
 
   Raises:
     NonLinearError: The lists have a different number of commits even after
       expanding DEPS rolls, a Commit pair contains differing repositories, or a
       Commit pair is in the wrong order.
   """
-  commits_midpoint = []
+  midpoints = []
 
   for commit_a, commit_b in itertools.izip_longest(commits_a, commits_b):
     if not (commit_a and commit_b):
       # If the commit lists are not the same length, bail out. That could happen
       # if commits_b has a repository that was not found in the DEPS of
       # commits_a (or vice versa); or a DEPS roll added or removed a DEP.
       raise commit_module.NonLinearError(
           'Changes have a different number of commits.')
 
-    commit_midpoint = commit_module.Commit.Midpoint(commit_a, commit_b)
-    commits_midpoint.append(commit_midpoint)
-    if commit_a == commit_midpoint != commit_b:
+    midpoint, distances = commit_module.Commit.Midpoint(commit_a, commit_b)
+    midpoints.append((midpoint, distances))
+
+    if sum(distances) == 1:
       # Commits are adjacent.
       # Add any DEPS changes to the commit lists.
       deps_a = commit_a.Deps()
       deps_b = commit_b.Deps()

[perezju, 2017/09/20 15:29:41]

The logic would be clearer if we would raise the error here in case of
mismatching DEPS. So the check for mismatching length above is not needed.

Actually, would it make sense to ignore added or removed DEPS, and just add to
both lists of commits the changed DEPS that both have?

       commits_a += sorted(
           dep for dep in deps_a.difference(deps_b)
           if not _FindCommitWithRepository(commits_a, dep.repository))
       commits_b += sorted(
           dep for dep in deps_b.difference(deps_a)
           if not _FindCommitWithRepository(commits_b, dep.repository))
 
-  return commits_midpoint
+  return midpoints
 
 
 def _FindCommitWithRepository(commits, repository):
   for commit in commits:
     if commit.repository == repository:
       return commit
   return None