[pinpoint] Change refactor.

This patch is trying to accomplish two major objectives:

* Make Change.deps (now Change.commits) ordered. In the case of multiple DEPS
  rolls, e.g. clank@1 chromium@2 v8@3, we need them in order to know that v8@3
  is the one to display in the UI.

* Simplify and correct the Change.Midpoint() logic. It was incorrect in the case
  of change_a == chromium@1, change_b == chromium@1 v8@4. It was giving no
  midpoint, when we expected chromium@1 v8@2. Hopefully the logic is easier to
  follow now.

In addition, I've tacked on some other things that were on my wishlist:
* Rename Dep to Commit.
* Split change.py into separate modules for Change, Commit, and Patch.
* Make the Change.Midpoint() unit tests much easier to grok and write.

Review-Url: https://chromiumcodereview.appspot.com/3013013002
Committed: https://chromium.googlesource.com/external/github.com/catapult-project/catapult/+/5638c631c865e13614c71c6b68bc5a1f69806742

[dtu, 2017-09-12 07:31:19]

Description was changed from

==========
[pinpoint] Change refactor.

BUG=catapult:#
==========

to

==========
This patch is trying to accomplish two major objectives:

* Make Change.deps (now Change.commits) ordered. In the case of multiple DEPS
  rolls, e.g. clank@1 chromium@2 v8@3, we need them in order to know that v8@3
  is the one to display in the UI.

* Simplify and correct the Change.Midpoint() logic. It was incorrect in the case
  of change_a == chromium@1, change_b == chromium@1 v8@4. It was giving no
  midpoint, when we expected chromium@1 v8@2.

In addition, I've tacked on some other things that were on my wishlist:
* Rename Dep to Commit.
* Split change.py into separate modules for Change, Commit, and Patch.
* Make the Change.Midpoint() unit tests much easier to grok and write.
==========

[dtu, 2017-09-12 07:31:20]

dtu@chromium.org changed reviewers:
+ perezju@chromium.org, simonhatch@chromium.org, sullivan@chromium.org

[dtu, 2017-09-12 07:32:27]

Description was changed from

==========
This patch is trying to accomplish two major objectives:

* Make Change.deps (now Change.commits) ordered. In the case of multiple DEPS
  rolls, e.g. clank@1 chromium@2 v8@3, we need them in order to know that v8@3
  is the one to display in the UI.

* Simplify and correct the Change.Midpoint() logic. It was incorrect in the case
  of change_a == chromium@1, change_b == chromium@1 v8@4. It was giving no
  midpoint, when we expected chromium@1 v8@2.

In addition, I've tacked on some other things that were on my wishlist:
* Rename Dep to Commit.
* Split change.py into separate modules for Change, Commit, and Patch.
* Make the Change.Midpoint() unit tests much easier to grok and write.
==========

to

==========
This patch is trying to accomplish two major objectives:

* Make Change.deps (now Change.commits) ordered. In the case of multiple DEPS
  rolls, e.g. clank@1 chromium@2 v8@3, we need them in order to know that v8@3
  is the one to display in the UI.

* Simplify and correct the Change.Midpoint() logic. It was incorrect in the case
  of change_a == chromium@1, change_b == chromium@1 v8@4. It was giving no
  midpoint, when we expected chromium@1 v8@2. Hopefully the logic is easier to
  follow now.

In addition, I've tacked on some other things that were on my wishlist:
* Rename Dep to Commit.
* Split change.py into separate modules for Change, Commit, and Patch.
* Make the Change.Midpoint() unit tests much easier to grok and write.
==========

[dtu, 2017-09-12 08:03:16]

Making `deps` ordered is a breaking, incompatible change. I've tacked on a bunch
of other breaking changes, so we can avoid a big data migration after launch.

We do still have to do a data migration for the isolate info.

[perezju, 2017-09-12 10:59:55]

Added a few comments for now; will probably have a second pass after any changes
you make.

https://codereview.chromium.org/3013013002/diff/20001/dashboard/dashboard/pin...
File dashboard/dashboard/pinpoint/models/change/change.py (right):

https://codereview.chromium.org/3013013002/diff/20001/dashboard/dashboard/pin...
dashboard/dashboard/pinpoint/models/change/change.py:37: def id_string(self):
add docstrings explaining difference between str(change) and change.id_string

https://codereview.chromium.org/3013013002/diff/20001/dashboard/dashboard/pin...
dashboard/dashboard/pinpoint/models/change/change.py:139: for commit_a in
commits_a:
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]
  ...

https://codereview.chromium.org/3013013002/diff/20001/dashboard/dashboard/pin...
dashboard/dashboard/pinpoint/models/change/change.py:175: for commit_a, commit_b
in itertools.izip_longest(commits_a, commits_b):
at this point the two lists should be the same size, so izip should be enough?

https://codereview.chromium.org/3013013002/diff/20001/dashboard/dashboard/pin...
File dashboard/dashboard/pinpoint/models/change/commit.py (right):

https://codereview.chromium.org/3013013002/diff/20001/dashboard/dashboard/pin...
dashboard/dashboard/pinpoint/models/change/commit.py:18: class
AdjacentCommitsWarning(Exception):
I'm not trilled about "raising" warnings as exceptions. Could there be another
way around this?

https://codereview.chromium.org/3013013002/diff/20001/dashboard/dashboard/pin...
dashboard/dashboard/pinpoint/models/change/commit.py:67:
_AddRepository(repository_url)
nit: make _AddRepository to return the repository so you can avoid the immediate
call to _Repository.

https://codereview.chromium.org/3013013002/diff/20001/dashboard/dashboard/pin...
dashboard/dashboard/pinpoint/models/change/commit.py:96: repository =
repository_from_url
Wouldn't it be safer to check for leading 'https?:' and raise an error if a
repository_url is given that has not been registered (or alternative
_AddRepository instead)?

https://codereview.chromium.org/3013013002/diff/20001/dashboard/dashboard/pin...
dashboard/dashboard/pinpoint/models/change/commit.py:123: SameCommitWarning: The
Commits are the same.
I think these warnings raised as exceptions are awkward.

Instead I would suggest in both cases either:

- return None to signal "there is no midpoint" (but there is also no error)
- return commit_a, and let the caller worry about special casing for that.

https://codereview.chromium.org/3013013002/diff/20001/dashboard/dashboard/pin...
dashboard/dashboard/pinpoint/models/change/commit.py:139: raise
NonLinearError('The commits are in the wrong order: %s and %s' %
nit: Rephrase as "Commit {a} does not come before {b}" (in general there might
not be a "right" order between two commits)

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

https://codereview.chromium.org/3013013002/diff/20001/dashboard/dashboard/pin...
File dashboard/dashboard/pinpoint/models/change/change.py (right):

https://codereview.chromium.org/3013013002/diff/20001/dashboard/dashboard/pin...
dashboard/dashboard/pinpoint/models/change/change.py:37: def id_string(self):
On 2017/09/12 10:59:54, perezju wrote:
> add docstrings explaining difference between str(change) and change.id_string

Done.

https://codereview.chromium.org/3013013002/diff/20001/dashboard/dashboard/pin...
dashboard/dashboard/pinpoint/models/change/change.py:139: for commit_a in
commits_a:
On 2017/09/12 10:59:54, perezju wrote:
> 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]
>   ...

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.

https://codereview.chromium.org/3013013002/diff/20001/dashboard/dashboard/pin...
dashboard/dashboard/pinpoint/models/change/change.py:175: for commit_a, commit_b
in itertools.izip_longest(commits_a, commits_b):
On 2017/09/12 10:59:54, perezju wrote:
> at this point the two lists should be the same size, so izip should be enough?

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.

https://codereview.chromium.org/3013013002/diff/20001/dashboard/dashboard/pin...
File dashboard/dashboard/pinpoint/models/change/commit.py (right):

https://codereview.chromium.org/3013013002/diff/20001/dashboard/dashboard/pin...
dashboard/dashboard/pinpoint/models/change/commit.py:18: class
AdjacentCommitsWarning(Exception):
On 2017/09/12 10:59:54, perezju wrote:
> I'm not trilled about "raising" warnings as exceptions. Could there be another
> way around this?

Done.

https://codereview.chromium.org/3013013002/diff/20001/dashboard/dashboard/pin...
dashboard/dashboard/pinpoint/models/change/commit.py:67:
_AddRepository(repository_url)
On 2017/09/12 10:59:54, perezju wrote:
> nit: make _AddRepository to return the repository so you can avoid the
immediate
> call to _Repository.

Done.

https://codereview.chromium.org/3013013002/diff/20001/dashboard/dashboard/pin...
dashboard/dashboard/pinpoint/models/change/commit.py:96: repository =
repository_from_url
On 2017/09/12 10:59:54, perezju wrote:
> Wouldn't it be safer to check for leading 'https?:' and raise an error if a
> repository_url is given that has not been registered (or alternative
> _AddRepository instead)? 

Done.

https://codereview.chromium.org/3013013002/diff/20001/dashboard/dashboard/pin...
dashboard/dashboard/pinpoint/models/change/commit.py:123: SameCommitWarning: The
Commits are the same.
On 2017/09/12 10:59:54, perezju wrote:
> I think these warnings raised as exceptions are awkward.
> 
> Instead I would suggest in both cases either:
> 
> - return None to signal "there is no midpoint" (but there is also no error)
> - return commit_a, and let the caller worry about special casing for that.

Done.

https://codereview.chromium.org/3013013002/diff/20001/dashboard/dashboard/pin...
dashboard/dashboard/pinpoint/models/change/commit.py:139: raise
NonLinearError('The commits are in the wrong order: %s and %s' %
On 2017/09/12 10:59:54, perezju wrote:
> nit: Rephrase as "Commit {a} does not come before {b}" (in general there might
> not be a "right" order between two commits)

Done. Do you mean e.g. they're in the same repository but on different branches?

[shatch, 2017-09-13 00:53:37]

lgtm once perezu is happy with it

[perezju, 2017-09-13 12:52:24]

I'm going to rs-lgtm this mostly so you that can land the refactor and don't
block other work that may depend on that.

However at this point I'm no longer sure whether the midpoint logic is correct
at all.

Since this CL is getting too big I would suggest to just sprinkle some TODO's on
some of the observations I make below, and then let's have another careful
review on the midpoint computation logic as a follow up.

https://codereview.chromium.org/3013013002/diff/20001/dashboard/dashboard/pin...
File dashboard/dashboard/pinpoint/models/change/change.py (right):

https://codereview.chromium.org/3013013002/diff/20001/dashboard/dashboard/pin...
dashboard/dashboard/pinpoint/models/change/change.py:139: for commit_a in
commits_a:
On 2017/09/12 22:31:16, dtu wrote:
> Is it any less scary if we're not modifying the existing list items and only
> appending to the end? :)

(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.

https://codereview.chromium.org/3013013002/diff/20001/dashboard/dashboard/pin...
dashboard/dashboard/pinpoint/models/change/change.py:175: for commit_a, commit_b
in itertools.izip_longest(commits_a, commits_b):
On 2017/09/12 22:31:16, dtu wrote:
> On 2017/09/12 10:59:54, perezju wrote:
> > at this point the two lists should be the same size, so izip should be
enough?
> 
> 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.

(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?

https://codereview.chromium.org/3013013002/diff/20001/dashboard/dashboard/pin...
File dashboard/dashboard/pinpoint/models/change/commit.py (right):

https://codereview.chromium.org/3013013002/diff/20001/dashboard/dashboard/pin...
dashboard/dashboard/pinpoint/models/change/commit.py:139: raise
NonLinearError('The commits are in the wrong order: %s and %s' %
On 2017/09/12 22:31:16, dtu wrote:
> On 2017/09/12 10:59:54, perezju wrote:
> > nit: Rephrase as "Commit {a} does not come before {b}" (in general there
might
> > not be a "right" order between two commits)
> 
> Done. Do you mean e.g. they're in the same repository but on different
branches?

Yep exactly. This may not be common since we tend to keep a pretty linear
history, so was mostly a nit.

https://codereview.chromium.org/3013013002/diff/80001/dashboard/dashboard/pin...
File dashboard/dashboard/pinpoint/models/change/change.py (right):

https://codereview.chromium.org/3013013002/diff/80001/dashboard/dashboard/pin...
dashboard/dashboard/pinpoint/models/change/change.py:130: in the DEPS of the
other Commit list.
(Let's revisit again on a follow up CL)

Add a test to exercise this case.

https://codereview.chromium.org/3013013002/diff/80001/dashboard/dashboard/pin...
dashboard/dashboard/pinpoint/models/change/change.py:198: commits_a += sorted(
:( :( :(

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

https://codereview.chromium.org/3013013002/diff/20001/dashboard/dashboard/pin...
File dashboard/dashboard/pinpoint/models/change/change.py (right):

https://codereview.chromium.org/3013013002/diff/20001/dashboard/dashboard/pin...
dashboard/dashboard/pinpoint/models/change/change.py:139: for commit_a in
commits_a:
On 2017/09/13 12:52:23, perezju wrote:
> On 2017/09/12 22:31:16, dtu wrote:
> > Is it any less scary if we're not modifying the existing list items and only
> > appending to the end? :)
> 
> (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.

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.

https://codereview.chromium.org/3013013002/diff/20001/dashboard/dashboard/pin...
dashboard/dashboard/pinpoint/models/change/change.py:175: for commit_a, commit_b
in itertools.izip_longest(commits_a, commits_b):
On 2017/09/13 12:52:23, perezju wrote:
> On 2017/09/12 22:31:16, dtu wrote:
> > On 2017/09/12 10:59:54, perezju wrote:
> > > at this point the two lists should be the same size, so izip should be
> enough?
> > 
> > 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.
> 
> (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. :(

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.

> 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?

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]

https://codereview.chromium.org/3013013002/diff/80001/dashboard/dashboard/pin...
File dashboard/dashboard/pinpoint/models/change/change.py (right):

https://codereview.chromium.org/3013013002/diff/80001/dashboard/dashboard/pin...
dashboard/dashboard/pinpoint/models/change/change.py:130: in the DEPS of the
other Commit list.
On 2017/09/13 12:52:24, perezju wrote:
> (Let's revisit again on a follow up CL)
> 
> Add a test to exercise this case.

testDifferingCommitCount is the test for this case.

https://codereview.chromium.org/3013013002/diff/80001/dashboard/dashboard/pin...
dashboard/dashboard/pinpoint/models/change/change.py:198: commits_a += sorted(
On 2017/09/13 12:52:24, perezju wrote:
> :( :( :(

:( :( :(

[dtu, 2017-09-13 15:56:28]

For another complex case where you would need to modify the list as you're
iterating over it:

Let's say:
chromium@10 is a DEPS roll that contains one commit, v8@9 -> v8@10
v8@10 is another DEPS roll that rolls v8/build@0 -> v8/build@10

A: chromium@9
B: chromium@10

We loop through the commits, and first look at chromium, take the midpoint and
find that it's a DEPS roll, then expand it.

A: chromium@9  v8@9
B: chromium@10 v8@10
midpoint: chromium@9

We continue looping, and look at v8, take the midpoint and find that it's a DEPS
roll, then expand it.

A: chromium@9  v8@9  v8/build@0
B: chromium@10 v8@10 v8/build@10
midpoint: chromium@9 v8@9

We continue looping, and look at v8/build, and find the midpoint.

A: chromium@9  v8@9  v8/build@0
B: chromium@10 v8@10 v8/build@10
midpoint: chromium@9  v8@9  v8/build@5

We run out of items. We are done.
If we didn't modify the list as we were looping through it, we wouldn't be able
to expand the second DEPS roll.

[dtu, 2017-09-13 16:59:22]

The CQ bit was checked by dtu@chromium.org

[commit-bot: I haz the power, 2017-09-13 16:59:27]

CQ is trying da patch.

Follow status at:
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2017-09-13 17:33:19]

CQ is committing da patch.

Bot data: {"patchset_id": 80001, "attempt_start_ts": 1505321962270310,
"parent_rev": "2070d1f7afd90ab81380dcc5a8d1701e335e020e", "commit_rev":
"5638c631c865e13614c71c6b68bc5a1f69806742"}

[commit-bot: I haz the power, 2017-09-13 17:33:25]

Description was changed from

==========
This patch is trying to accomplish two major objectives:

* Make Change.deps (now Change.commits) ordered. In the case of multiple DEPS
  rolls, e.g. clank@1 chromium@2 v8@3, we need them in order to know that v8@3
  is the one to display in the UI.

* Simplify and correct the Change.Midpoint() logic. It was incorrect in the case
  of change_a == chromium@1, change_b == chromium@1 v8@4. It was giving no
  midpoint, when we expected chromium@1 v8@2. Hopefully the logic is easier to
  follow now.

In addition, I've tacked on some other things that were on my wishlist:
* Rename Dep to Commit.
* Split change.py into separate modules for Change, Commit, and Patch.
* Make the Change.Midpoint() unit tests much easier to grok and write.
==========

to

==========
This patch is trying to accomplish two major objectives:

* Make Change.deps (now Change.commits) ordered. In the case of multiple DEPS
  rolls, e.g. clank@1 chromium@2 v8@3, we need them in order to know that v8@3
  is the one to display in the UI.

* Simplify and correct the Change.Midpoint() logic. It was incorrect in the case
  of change_a == chromium@1, change_b == chromium@1 v8@4. It was giving no
  midpoint, when we expected chromium@1 v8@2. Hopefully the logic is easier to
  follow now.

In addition, I've tacked on some other things that were on my wishlist:
* Rename Dep to Commit.
* Split change.py into separate modules for Change, Commit, and Patch.
* Make the Change.Midpoint() unit tests much easier to grok and write.

Review-Url: https://chromiumcodereview.appspot.com/3013013002
Committed:
https://chromium.googlesource.com/external/github.com/catapult-project/catapu...
==========

[commit-bot: I haz the power, 2017-09-13 17:33:27]

Committed patchset #5 (id:80001) as
https://chromium.googlesource.com/external/github.com/catapult-project/catapu...