This is an archive of the discontinued Mercurial Phabricator instance.

rebase: rewrite core algorithm (issue5578) (issue5630)
ClosedPublic

Authored by quark on Jul 10 2017, 3:15 PM.

Details

Summary

"defineparents" is the core algorithm of rebase. The old code has too many
tech debts (like outdated comments, confusing assertions, etc) and is very
error-prone to be improved. This patch rewrites "defineparents" to make the
code easier to reason about, and solve a bunch of issues, including:

  • Assertion error: no base found (demonstrated by D212, issue5578)
  • Asymmetric result (demonstrated by D211, "F with one parent")
  • Wrong new parent (demonstrated by D262, "C':A'A'")
  • "revlog index out of range" (demonstrated by D262, issue5630)
  • "nothing to merge" (demonstrated by D262)

As a side effect, merge base decision has been made more solid - rebase now
prints out explicitly what could go wrong when it cannot find a unique
suitable merge base.

.. fix:: Issue 5578, Issue 5630

Core rebase algorithm has been rewritten to be more robust.

Diff Detail

Repository
rHG Mercurial
Lint
Lint Skipped
Unit
Unit Tests Skipped

Event Timeline

quark created this revision.Jul 10 2017, 3:15 PM
krbullock edited subscribers, added: mercurial-devel; removed: reviewers.Jul 10 2017, 4:11 PM
durin42 requested changes to this revision.Jul 14 2017, 3:16 PM
durin42 added a subscriber: durin42.
durin42 added inline comments.
hgext/rebase.py
994–1006

I can't figure out what this comment is trying to tell me. Why on earth would, given the graph I see, rebase rewrite my explicit 'hg rebase -r E -d F' into having B' as the destination?

1012

Again, I'm confused. What's the rebase operation in play that is linearizing here? I don't even know how I'd spell that on the command line.

1038

Could you expand this docstring to explain what this means? I think that might make the whole change easier to review.

1138

Define ALLSRC - it's not in the codebase prior to this change.

This revision now requires changes to proceed.Jul 14 2017, 3:16 PM
quark added inline comments.Jul 14 2017, 4:25 PM
hgext/rebase.py
994–1006

Good catch. Will add more text here.

1012

This is for multi-dest. I'll move it to a future patch.

1038

This docstring was unchanged - it is the same as the original function.

1138

Side effect of splitting. Will avoid using ALLSRC.

quark edited edge metadata.Jul 14 2017, 4:28 PM
quark updated this revision to Diff 156.

Almost there.

hgext/rebase.py
1006

How did C' end up in a separate subgraph? I thought it was moving to F?

(I suspect this is also some multi-dest stuff...)

quark updated this revision to Diff 161.Jul 14 2017, 5:20 PM
quark marked an inline comment as done.Jul 14 2017, 5:20 PM
quark added inline comments.
hgext/rebase.py
1006

Good catch! Side effect of split again. Updated the comment.

durin42 accepted this revision.Jul 14 2017, 5:23 PM
This revision is now accepted and ready to land.Jul 14 2017, 5:23 PM
quark abandoned this revision.Jul 18 2017, 1:41 PM
quark marked an inline comment as done.Aug 10 2017, 11:30 PM
quark edited the summary of this revision. (Show Details)
quark retitled this revision from rebase: rewrite defineparents to rebase: rewrite core algorithm (issue5578) (issue5630).
quark updated this revision to Diff 753.
This revision is now accepted and ready to land.Aug 10 2017, 11:30 PM
quark updated this revision to Diff 754.Aug 10 2017, 11:34 PM
quark planned changes to this revision.Aug 10 2017, 11:40 PM
quark added inline comments.
tests/test-rebase-obsolete.t
1064–1065

This case needs investigation.

quark edited the summary of this revision. (Show Details)Aug 11 2017, 1:41 AM
quark updated this revision to Diff 765.
This revision is now accepted and ready to land.Aug 11 2017, 1:41 AM
martinvonz added inline comments.
hgext/rebase.py
392

IIUC, the reason you no longer need to pass destancestors and obsoletenotrebased is because they are now calculated on the fly instead of upfront. It seems like that might be slower, but I haven't spent time thinking about under what circumstances it might be. Have you? Could it be noticeable even in the worst case you can think of, or would it be completely drowned by rebase's other costs (such as writing revlogs and working copy files)?

1004

Should this be a wrapper of cl.isancestor() instead? Looks like that's how you use it.

1009

nit: Is this for converting to a list or for making a copy (of something that's already a list)? If the latter, I feel like oldps[:} is clearer.

1010

I think each step of the rebase effectively applies the diff in (rev - base) onto p1 (and p2 is only artificially added later to produce the graph we want), so I think we need to keep better track of the bases than using a set.

Here's a test that will fail after this patch (the manifest will contain A as well):

$ hg debugdrawdag <<'EOF'
>   D
>  /|
> B C
>  \|
>   A E
>   |/
>   Q
> EOF
$ hg rebase -d E -r 'B + C + D'
$ hg manifest --rev tip
B
C
E
Q
1019

This looks a bit weird. Would it work the same if you move it outside? Something like:

if oldps[1] == nullrev:
  assert dests[1] == nullrev
  newps = dests
  if newps != oldps: # maybe always true?
    bases.add(oldps[0])
else:
  newps = oldps[:]
  for i, p in enumerate(oldps):
     ....

Having written that and looked at adjustdest(), I see that the assertion would fail because adjustdest() would return [dest,dest] for a non-merge source. That seems surprising to me. Should adjustdest() be changed not to do that?

1025

I don't quite understand the responsibility of adjustdest() vs this method. Why would or why would we not let adjustdest() handle the merge cases too instead of doing that here?

1114

Here's another case where I believe bases should also be updated (they should be reversed).

tests/test-rebase-obsolete.t
1127

nit: seems unnecessary to even mention this now (the other tests don't)

quark added inline comments.Aug 12 2017, 2:06 PM
hgext/rebase.py
392

IIUC, the reason you no longer need to pass destancestors and obsoletenotrebased is because they are now calculated on the f ly instead of upfront.

Yes.

It seems like that might be slower

Practically, not necessarily. The new code uses the C ancestor code in revlog.c, which is 20x faster than the Python ancestor code (5bae936764).

I think having less states here makes the code more maintainable.

For the speedup, I think the low-level ancestor could maintain a LRU ancestor cache and application could hint it what to cache. The cache object might be managed automatically (by the revlog.c code), or manually (by explicitly passing it to to ancestor). Besides, I had a non-trivial idea to make ancestor testing roughly O(log N) instead of O(N). But those are non-trivial (involves native code) that I'd like to do them later.

1004

Line 1088 is not isancestor. I'm okay with having two functions here. Let me know what do you prefer.

1009

Copy. Will change.

1010

Interesting. I didn't know that we treat p1 specially here. If so, users can always construct an asymmetric case that feels wrong. For example, if we use B or C as E's parent in the above graph, p1 may not get chosen in one of the case.

In this diff, it's Line 1091 trying to be conservative. I'll add tests and a warning like D340 (Diff 770) line 1115.

1019

Maybe assert i == 0 is a better assertion here. If nullrev is considered part of the DAG, then I think it makes sense for adjustdest to return dest for p2.

1025

Good question. adjustdest was originally a replacement of nearestrebased and was only handling one destination. Then I found it has to deal with 2 parents differently so it became more complex.

Looking at its current usage at clearrebased, it's still different. clearrebased needs to just move bookmark to the adjusted destination. The code here need a double check before using that adjusted destination.

In theory, the code here could also just use the adjusted destination without checking. But as the comment above said, the merge commit may "lose a parent" surprisingly.

So I think the code here is to:

  1. Decide which parent not to move (not obey the adjusted destination).
  2. Handle the case when a parent is not moved to destination, will it still need to be moved?

For 2, an example is:

A
|\
B C   D

Rebasing A to D or E is an error since none of A's parents could be moved to those destinations. But if a user runs "rebase -s B+A -d D", then A needs to be moved to B'.

I'll add more comments here.

martinvonz added inline comments.Aug 12 2017, 5:16 PM
hgext/rebase.py
1004

It looks like it effectively is. You can rewrite it using isancestor(). The reason I brought this up at all was that cl.ancestor() returns a single ancestor even if there are multiple (as in criss-cross merges), which made me wonder what would happen if the wrong ancestor was returned. I don't think there can be a "wrong" ancestor for the uses here, but using isancestor() instead makes that clearer.

Also, it seems like isancestor(a,b) can be made faster than ancestors(a,b)==a can because it can stop walking when when the rev is lower than a's rev.

1010

I'm not sure I understand, but I don't think the user can influence the result (and I'm assuming you mean "as *D*'s parent", otherwise I can't make any sense of it). It should be fine to use either B' or C' as the new p1, as long as base is set to B or C (respectively).

1019

True, I can see the point about [nullrev,nullrev] being valid implying that any [X,X] should be valid.

How about the rest of my comment? I didn't understand what you meant by the first part of you reply.

tests/test-rebase-newancestor.t
287

Sorry, I forgot to ask before, but why did this change?

quark added inline comments.Aug 12 2017, 6:52 PM
hgext/rebase.py
1004

Good point. I was aware that isancestor could be slightly faster. I'll rewrite the merge base logic so it only uses isancestor.

1010

Sorry I wasn't clear. When there are multiple merge base candidates, we perform rules in this order:

  1. remove ancestors of source and destination since they can be decided by the merge.update(ancestor=None) without us passing an explicit ancestor.
  2. remove obsoleted parents with successor in destination, as explained by the next patch.
  3. if there are still non-unique candidates, what to do?

The current code for 3 will give up and let merge.update decide, which produces the sub-optimal result in your case. Choosing p1 (if changed) blindly is better then the current code as step 3. I feel it's worth a warning since the merge result is sub-optimal any way. The case I wanted to make was to say "1" must happen before "3". But it seems obvious so the case is not helpful.

Instead of picking p1 blindly, I wonder if we want passing all merge base candidates to the merge code to decide. The merge code seems to have "calculating bids for ancestor" logic suitable for this case. I'm trying that approach to see how it works.

1019

I concluded that part of the reasons that the old code is messy is because it uses too many ifs and relies heavily on the fact that Mercurial has only 2 parents. So I started with for as top-level block as a hint to make people think about making the code work for more than 2 parents. But it does not seem to serve that purpose well now. Single-parent case is still special, I'll change the structure.

tests/test-rebase-newancestor.t
287

Good catch! It turns out to be Line 1088, ancestor returns a single node where in this case we want multiple ancestor nodes. That should be solved by the isancestor change. Thanks!

quark marked 8 inline comments as done.Aug 13 2017, 12:09 AM
quark added inline comments.
hgext/rebase.py
1009

Actually oldps is a tuple so oldps[:] does not work.

quark edited the summary of this revision. (Show Details)Aug 13 2017, 12:10 AM
quark updated this revision to Diff 829.
martinvonz added inline comments.Aug 14 2017, 2:02 AM
hgext/rebase.py
1019

Yes, I think handling the single-parent case separately makes sense. The problem with the old structure was not that it handled 1 vs 2 parents differently but that it handled the 1st vs the 2nd parent differently. (I'm sure *you* have realized that, I'm just trying to help other readers who have been less involved.)

1088

missing "find" (?) before "desired" and misspelled "False"

1106

nit: move "x > np" into isancestor()

1107

In this case, maybe we shouldn't have added p to bases above? Maybe that block should be moved after this loop? Maybe it would be easier to keep track of the bases in a list that's initialized to [None,None]? Or maybe if the order of newps always matches oldps, can bases be calculated later and not mixed in with the calculation of newps?

1113

Thanks for catching this case and warning about it! I wonder if we should even error out early instead? Even if we decide to do that, feel free to leave it for a followup.

1114

Typo in "inlcude".

1115

It would probably be good to include the nodeid here just like we do on the line above, especially since the revision number may point to something else after the rebase is complete (if not using obsmarkers).

quark planned changes to this revision.

I made some improvements on merge base handling.

quark marked 3 inline comments as done.Aug 14 2017, 11:05 AM
quark updated this revision to Diff 869.
This revision is now accepted and ready to land.Aug 14 2017, 11:05 AM
quark added inline comments.Aug 14 2017, 11:06 AM
hgext/rebase.py
1107

No. New parents having an ancestor relationship does not mean the old parents have that relationship. It seems your test cases in test-rebase-obsolete.t would capture the behavior difference.

1113

An error makes sense to me. But it changes more tests. I'll do that after D340.

It's hard to detect it early without in-memory-changelog to do a dry-run rebase.

1115

This was just me being lazy. Ideally all these %d:%s thing should be a template config so we can hide revision numbers in production.

About the warning of unwanted changes, when thinking about it again, it seems sometimes people may want to do that kind of rebase. If we let them edit the merge result (ex. a merge conflict), than the workflow looks good - it's just the merge algorithm being suboptimal in that case. I guess in real-world cases it would most likely produce a merge conflict so am leaning towards a warning now.

martinvonz accepted this revision.Aug 14 2017, 12:45 PM

Finally done reviewing this. Thanks for the rewrite!

This revision was automatically updated to reflect the committed changes.