[pinpoint] Change refactor.

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
+
+
+class Change(collections.namedtuple('Change', ('commits', 'patch'))):
+  """A particular set of Commits with or without an additional patch applied.
+
+  For example, a Change might sync to src@9064a40 and catapult@8f26966,
+  then apply patch 2423293002.
+  """
+
+  def __new__(cls, commits, patch=None):
+    """Creates a Change.
+
+    Args:
+      commits: An iterable of Commits representing this Change's dependencies.
+      patch: An optional Patch to apply to the Change.
+    """
+    if not commits:
+      raise TypeError('At least one commit required.')
+    return super(Change, cls).__new__(cls, tuple(commits), patch)
+
+  def __str__(self):
+    string = ' '.join(str(commit) for commit in self.commits)
+    if self.patch:
+      string += ' + ' + str(self.patch)
+    return string
+
+  @property
+  def id_string(self):

[perezju, 2017/09/12 10:59:54]

add docstrings explaining difference between str(change) and change.id_string

[dtu, 2017/09/12 22:31:16]

Done.

+    string = ' '.join(commit.id_string for commit in self.commits)
+    if self.patch:
+      string += ' + ' + self.patch.id_string
+    return string
+
+  @property
+  def base_commit(self):
+    return self.commits[0]
+
+  @property
+  def deps(self):
+    return tuple(self.commits[1:])
+
+  def AsDict(self):
+    return {
+        'commits': [commit.AsDict() for commit in self.commits],
+        'patch': self.patch.AsDict() if self.patch else None,
+    }
+
+  @classmethod
+  def FromDict(cls, data):
+    commits = tuple(commit_module.Commit.FromDict(commit)
+                    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.
+
+    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.
+    See change_test.py for examples of linear and nonlinear Changes.
+
+    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.
+
+    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)
+
+    if commits_a == commits_midpoint:
+      raise commit_module.NonLinearError('Changes are the same or adjacent.')
+
+    return cls(commits_midpoint, change_a.patch)
+
+
+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.
+
+  Example:
+    commits_a == [chromium@a, v8@c]
+    commits_b == [chromium@b]
+    This function looks through the DEPS file at chromium@b to find v8, then
+    appends that v8 Commit to commits_b, making the lists match.
+
+  Args:
+    commits_a: A list of Commits.
+    commits_b: A list of Commits.
+  """
+  # The lists may be given in any order. Let's make commits_b the bigger list.
+  if len(commits_a) > len(commits_b):
+    commits_a, commits_b = commits_b, commits_a
+
+  # Loop through every DEPS file in commits_a.
+  for commit_a in commits_a:

[perezju, 2017/09/12 10:59:54]

this looks scary, modifying the list while iterating over it.

Could it be rewritten as something like:

commit_idx = 0
while len(commits_a) < len(commits_b):
  commit_a = commits_a[commit_idx]
  ...

[dtu, 2017/09/12 22:31:16]

Is it any less scary if we're not modifying the existing list items and only
appending to the end? :)

To me, that loop is same thing but with an extra loop variable and the two loop
conditions swapped places:

commit_idx = 0
while len(commits_a) < len(commits_b):
  if commit_idx >= len(commits_a):
    break
  commit_a = commits_a[commit_idx]

  ...

  commit_idx += 1

Note that this function cannot guarantee that the lists will ever be the same
length. If e.g. all the DEPS were empty, there'd be nothing to add to commits_a.
I've included this in the function docstring.

[perezju, 2017/09/13 12:52:23]

(Let's revisit again on a follow up CL)

It's still scary. When you append items you modify the list.

Does the loop stop when you exhaust the items on the original list? Does it keep
going and also process the newly added items? I could go and look up what is the
Python semantics for this (and I can almost guess the right answer).

But I don't want to have to be worrying about this when trying to understand
what the code does. The algorithm is already quite intricate, let's try to make
it as easy to understand as possible.

[dtu, 2017/09/13 15:49:26]

It keeps going. I've used izip specifically instead of zip below as well, since
it uses generators and therefore will also keep going.

I do agree that it's difficult to understand. I don't know how to make it easier
-- although this loop could potentially be refactored to avoid the modification
during iteration, the other loop would be incorrect without it.

+    if len(commits_a) == len(commits_b):
+      break
+    deps_a = commit_a.Deps()
+
+    # 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.
+
+  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.
+
+  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 = []
+
+  for commit_a, commit_b in itertools.izip_longest(commits_a, commits_b):

[perezju, 2017/09/12 10:59:54]

at this point the two lists should be the same size, so izip should be enough?

[dtu, 2017/09/12 22:31:16]

In practical cases, yes, but there's no invariant in the code to guarantee that.
The "if not" just below is a guard against the case where they aren't the same
size. I've added a comment with examples of what might cause them to be
different sizes.

[perezju, 2017/09/13 12:52:23]

(Let's revisit again on a follow up CL)

I was going to suggest to move the "same size" check to the top, to bail out
early if that's the case.

But I've just noted that this is not enough because here too you're modifying
the lists you're iterating over. :(

At this point I'm not even sure that the algorithm is correct for some tricky
pairs of changes.

Consider for example a sequence of changes across 3 repositories:

src@8 + v8@4 + foo@2 [A]
src@9 + v8@4 + foo@2
src@10 + v8@4 + foo@2
src@10 + v8@5 + foo@2
src@10 + v8@6 + foo@2
src@10 + v8@7 + foo@2
src@10 + v8@8 + foo@2
src@10 + v8@8 + foo@3
src@10 + v8@8 + foo@4 [B]

Your "midpoint" between A and B (if I'm not totally confused, which is
admittedly a possibility) would yield:

src@9 + v8@6 + foo@3

But that's not even a combination of commits that was ever built, maybe foo@3
depends on some change introduced by v8@7. Right?

[dtu, 2017/09/13 15:49:26]

That's right. If a DEPS roll adds or removes a DEP, the lists can become
different sizes during the loop iteration. So all the checks are done inside the
loop.
These A and B are only possible if the user explicitly set it that way, and at
that point it's unknown what their intention is. Taking the midpoint of each
repository is a reasonable guess.

In a real bisect the deps are only expanded as needed, and we would have:

(Assuming src@10 and v8@8 are the DEPS rolls. I've parenthesized the commits
that are not included in the original Changes but are added in
_ExpandDepsToMatchRepositories.)

src@8 [A]
src@9
src@9 (+ v8@4)
src@9 + v8@5
src@9 + v8@6
src@9 + v8@7 (+ foo@2)
src@9 + v8@7 + foo@3
src@10 (+ v8@8 + foo@4) [B]

+    if not (commit_a and commit_b):
+      raise commit_module.NonLinearError(
+          'Changes have a different number of commits.')
+
+    try:
+      # Commits are not adjacent.
+      commit_midpoint = commit_module.Commit.Midpoint(commit_a, commit_b)
+    except commit_module.SameCommitWarning:
+      # Commits are the same.
+      commit_midpoint = commit_a
+    except commit_module.AdjacentCommitsWarning:
+      # Commits are adjacent.
+      commit_midpoint = commit_a
+
+      # Add any DEPS changes to the commit lists.
+      deps_a = commit_a.Deps()
+      deps_b = commit_b.Deps()
+      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))
+
+    commits_midpoint.append(commit_midpoint)
+
+  return commits_midpoint
+
+
+def _FindCommitWithRepository(commits, repository):
+  for commit in commits:
+    if commit.repository == repository:
+      return commit
+  return None