Good catch. Will add more text here.

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

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

Side effect of splitting. Will avoid using ALLSRC.

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

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

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

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

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.

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

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?

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?

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

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

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.

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

Copy. Will change.

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.

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.

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.

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.

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

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.

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

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

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.

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.

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!

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

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

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

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

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?

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.

Typo in "inlcude".

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

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.

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.

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.