Patchwork [2,of,2,V2] rebase: calculate ancestors for --base separately (issue5420)

login
register
mail settings
Submitter Jun Wu
Date Nov. 17, 2016, 11:49 p.m.
Message ID <e5451a607d1ca53b2446.1479426598@x1c>
Download mbox | patch
Permalink /patch/17633/
State Accepted
Headers show

Comments

Jun Wu - Nov. 17, 2016, 11:49 p.m.
# HG changeset patch
# User Jun Wu <quark@fb.com>
# Date 1479426495 0
#      Thu Nov 17 23:48:15 2016 +0000
# Node ID e5451a607d1ca53b2446ab049375e5dd5a055bb8
# Parent  87e0edc93d87b88e2925877469d8c142e01737fc
# Available At https://bitbucket.org/quark-zju/hg-draft
#              hg pull https://bitbucket.org/quark-zju/hg-draft -r e5451a607d1c
rebase: calculate ancestors for --base separately (issue5420)

Previously, the --base option only works with a single "branch" - if there
are multiple branching points, "rebase" will error out with:

  abort: source is ancestor of destination

This happens if the user has multiple draft branches with different
branching points, and uses "hg rebase -b 'draft()' -d master". The error
message looks cryptic to users who don't know the implementation detail.

This patch changes the logic to calculate ancestors for each "base" branch
so it would work in the multiple branching points case.

Note: if there are multiple bases where some of them are rebasable, while
some of them aren't because the branching point is the destination, the
current behavior is to abort with "nothing to rebase", which seems wrong.
However, that issue is not introduced by this patch - it exists for "-s" as
well. I have reported it as issue5422 and should be solved separately.
Augie Fackler - Nov. 19, 2016, 1:40 a.m.
On Thu, Nov 17, 2016 at 11:49:58PM +0000, Jun Wu wrote:
> # HG changeset patch
> # User Jun Wu <quark@fb.com>
> # Date 1479426495 0
> #      Thu Nov 17 23:48:15 2016 +0000
> # Node ID e5451a607d1ca53b2446ab049375e5dd5a055bb8
> # Parent  87e0edc93d87b88e2925877469d8c142e01737fc
> # Available At https://bitbucket.org/quark-zju/hg-draft
> #              hg pull https://bitbucket.org/quark-zju/hg-draft -r e5451a607d1c
> rebase: calculate ancestors for --base separately (issue5420)

These are queued, thanks.

>
> Previously, the --base option only works with a single "branch" - if there
> are multiple branching points, "rebase" will error out with:
>
>   abort: source is ancestor of destination
>
> This happens if the user has multiple draft branches with different
> branching points, and uses "hg rebase -b 'draft()' -d master". The error
> message looks cryptic to users who don't know the implementation detail.
>
> This patch changes the logic to calculate ancestors for each "base" branch
> so it would work in the multiple branching points case.
>
> Note: if there are multiple bases where some of them are rebasable, while
> some of them aren't because the branching point is the destination, the
> current behavior is to abort with "nothing to rebase", which seems wrong.
> However, that issue is not introduced by this patch - it exists for "-s" as
> well. I have reported it as issue5422 and should be solved separately.
>
> diff --git a/hgext/rebase.py b/hgext/rebase.py
> --- a/hgext/rebase.py
> +++ b/hgext/rebase.py
> @@ -722,10 +722,17 @@ def _definesets(ui, repo, destf=None, sr
>              destf = str(dest)
>
> -        commonanc = repo.revs('ancestor(%ld, %d)', base, dest).first()
> -        if commonanc is not None:
> -            rebaseset = repo.revs('(%d::(%ld) - %d)::',
> -                                  commonanc, base, commonanc)
> -        else:
> -            rebaseset = []
> +        # calculate ancestors for individual bases
> +        realbases = []
> +        for b in repo.revs('roots(%ld)', base):
> +            # branching point
> +            bp = repo.revs('ancestor(%d, %d)', b, dest).first()
> +            if bp is None:
> +                continue
> +            # move b to be the direct child of the branching point
> +            b = repo.revs('%d::%d - %d', bp, b, bp).first()
> +            if b is not None:
> +                realbases.append(b)
> +
> +        rebaseset = repo.revs('%ld::', realbases)
>
>          if not rebaseset:
> diff --git a/tests/test-rebase-base.t b/tests/test-rebase-base.t
> new file mode 100644
> --- /dev/null
> +++ b/tests/test-rebase-base.t
> @@ -0,0 +1,94 @@
> +  $ cat >> $HGRCPATH <<EOF
> +  > [extensions]
> +  > rebase=
> +  > drawdag=$TESTDIR/drawdag.py
> +  >
> +  > [phases]
> +  > publish=False
> +  >
> +  > [alias]
> +  > tglog = log -G --template "{rev}: {desc}"
> +  > EOF
> +
> +  $ hg init a
> +  $ cd a
> +
> +  $ hg debugdrawdag <<EOS
> +  > g f
> +  > |/
> +  > e c d
> +  > | |/
> +  > | b
> +  > |/
> +  > a
> +  > EOS
> +
> +  $ cd ..
> +
> +Pick a single base:
> +
> +  $ cp -a a a1 && cd a1
> +  $ hg rebase -b c -d g -q
> +  $ hg tglog
> +  o  6: d
> +  |
> +  | o  5: c
> +  |/
> +  o  4: b
> +  |
> +  o  3: g
> +  |
> +  | o  2: f
> +  |/
> +  o  1: e
> +  |
> +  o  0: a
> +
> +  $ cd ..
> +
> +Pick a base that is already an descendant of dest:
> +
> +  $ cp -a a a2 && cd a2
> +  $ hg rebase -b g -d e
> +  nothing to rebase
> +  [1]
> +  $ hg rebase -b d -d a
> +  nothing to rebase
> +  [1]
> +  $ hg rebase -b d+c+f+e -d a
> +  nothing to rebase
> +  [1]
> +  $ cd ..
> +
> +Pick multiple bases (issue5420):
> +
> +  $ cp -a a a3 && cd a3
> +  $ hg rebase -b d+f -d g -q
> +  $ hg tglog
> +  o  6: f
> +  |
> +  | o  5: d
> +  | |
> +  | | o  4: c
> +  | |/
> +  | o  3: b
> +  |/
> +  o  2: g
> +  |
> +  o  1: e
> +  |
> +  o  0: a
> +
> +  $ cd ..
> +
> +Mixed rebasable and non-rebasable bases (unresolved, issue5422):
> +
> +  $ cp -a a a4 && cd a4
> +  $ hg debugdrawdag <<EOS
> +  > h
> +  > |
> +  > g
> +  > EOS
> +  $ hg rebase -b d+f+h -d g
> +  nothing to rebase
> +  [1]
> _______________________________________________
> Mercurial-devel mailing list
> Mercurial-devel@mercurial-scm.org
> https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
Pierre-Yves David - Nov. 23, 2016, 3:54 p.m.
On 11/19/2016 02:40 AM, Augie Fackler wrote:
> On Thu, Nov 17, 2016 at 11:49:58PM +0000, Jun Wu wrote:
>> # HG changeset patch
>> # User Jun Wu <quark@fb.com>
>> # Date 1479426495 0
>> #      Thu Nov 17 23:48:15 2016 +0000
>> # Node ID e5451a607d1ca53b2446ab049375e5dd5a055bb8
>> # Parent  87e0edc93d87b88e2925877469d8c142e01737fc
>> # Available At https://bitbucket.org/quark-zju/hg-draft
>> #              hg pull https://bitbucket.org/quark-zju/hg-draft -r e5451a607d1c
>> rebase: calculate ancestors for --base separately (issue5420)
>
> These are queued, thanks.

I'm a bit concerned about the lack of test covering situation with merge 
commit. There could be pathological case lurking there. I'll try to a 
have a deeper look at what this change imply is that case before giving 
it a second accept stamp.

>> Previously, the --base option only works with a single "branch" - if there
>> are multiple branching points, "rebase" will error out with:
>>
>>   abort: source is ancestor of destination
>>
>> This happens if the user has multiple draft branches with different
>> branching points, and uses "hg rebase -b 'draft()' -d master". The error
>> message looks cryptic to users who don't know the implementation detail.
>>
>> This patch changes the logic to calculate ancestors for each "base" branch
>> so it would work in the multiple branching points case.
>>
>> Note: if there are multiple bases where some of them are rebasable, while
>> some of them aren't because the branching point is the destination, the
>> current behavior is to abort with "nothing to rebase", which seems wrong.
>> However, that issue is not introduced by this patch - it exists for "-s" as
>> well. I have reported it as issue5422 and should be solved separately.
>>
>> diff --git a/hgext/rebase.py b/hgext/rebase.py
>> --- a/hgext/rebase.py
>> +++ b/hgext/rebase.py
>> @@ -722,10 +722,17 @@ def _definesets(ui, repo, destf=None, sr
>>              destf = str(dest)
>>
>> -        commonanc = repo.revs('ancestor(%ld, %d)', base, dest).first()
>> -        if commonanc is not None:
>> -            rebaseset = repo.revs('(%d::(%ld) - %d)::',
>> -                                  commonanc, base, commonanc)
>> -        else:
>> -            rebaseset = []
>> +        # calculate ancestors for individual bases
>> +        realbases = []
>> +        for b in repo.revs('roots(%ld)', base):
>> +            # branching point
>> +            bp = repo.revs('ancestor(%d, %d)', b, dest).first()
>> +            if bp is None:
>> +                continue
>> +            # move b to be the direct child of the branching point
>> +            b = repo.revs('%d::%d - %d', bp, b, bp).first()
>> +            if b is not None:
>> +                realbases.append(b)
>> +
>> +        rebaseset = repo.revs('%ld::', realbases)
>>
>>          if not rebaseset:
>> diff --git a/tests/test-rebase-base.t b/tests/test-rebase-base.t
>> new file mode 100644
>> --- /dev/null
>> +++ b/tests/test-rebase-base.t
>> @@ -0,0 +1,94 @@
>> +  $ cat >> $HGRCPATH <<EOF
>> +  > [extensions]
>> +  > rebase=
>> +  > drawdag=$TESTDIR/drawdag.py
>> +  >
>> +  > [phases]
>> +  > publish=False
>> +  >
>> +  > [alias]
>> +  > tglog = log -G --template "{rev}: {desc}"
>> +  > EOF
>> +
>> +  $ hg init a
>> +  $ cd a
>> +
>> +  $ hg debugdrawdag <<EOS
>> +  > g f
>> +  > |/
>> +  > e c d
>> +  > | |/
>> +  > | b
>> +  > |/
>> +  > a
>> +  > EOS
>> +
>> +  $ cd ..
>> +
>> +Pick a single base:
>> +
>> +  $ cp -a a a1 && cd a1
>> +  $ hg rebase -b c -d g -q
>> +  $ hg tglog
>> +  o  6: d
>> +  |
>> +  | o  5: c
>> +  |/
>> +  o  4: b
>> +  |
>> +  o  3: g
>> +  |
>> +  | o  2: f
>> +  |/
>> +  o  1: e
>> +  |
>> +  o  0: a
>> +
>> +  $ cd ..
>> +
>> +Pick a base that is already an descendant of dest:
>> +
>> +  $ cp -a a a2 && cd a2
>> +  $ hg rebase -b g -d e
>> +  nothing to rebase
>> +  [1]
>> +  $ hg rebase -b d -d a
>> +  nothing to rebase
>> +  [1]
>> +  $ hg rebase -b d+c+f+e -d a
>> +  nothing to rebase
>> +  [1]
>> +  $ cd ..
>> +
>> +Pick multiple bases (issue5420):
>> +
>> +  $ cp -a a a3 && cd a3
>> +  $ hg rebase -b d+f -d g -q
>> +  $ hg tglog
>> +  o  6: f
>> +  |
>> +  | o  5: d
>> +  | |
>> +  | | o  4: c
>> +  | |/
>> +  | o  3: b
>> +  |/
>> +  o  2: g
>> +  |
>> +  o  1: e
>> +  |
>> +  o  0: a
>> +
>> +  $ cd ..
>> +
>> +Mixed rebasable and non-rebasable bases (unresolved, issue5422):
>> +
>> +  $ cp -a a a4 && cd a4
>> +  $ hg debugdrawdag <<EOS
>> +  > h
>> +  > |
>> +  > g
>> +  > EOS
>> +  $ hg rebase -b d+f+h -d g
>> +  nothing to rebase
>> +  [1]
>> _______________________________________________
>> Mercurial-devel mailing list
>> Mercurial-devel@mercurial-scm.org
>> https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
> _______________________________________________
> Mercurial-devel mailing list
> Mercurial-devel@mercurial-scm.org
> https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
>
Jun Wu - Nov. 25, 2016, 12:58 p.m.
I have added "pathological" cases I can think of in
patchwork.mercurial-scm.org/patch/17754/

I believe the current "--base" implementation is bug-free regarding to merges,
otherwise "-s" will have bugs, too.

Excerpts from Pierre-Yves David's message of 2016-11-23 16:54:51 +0100:
> 
> On 11/19/2016 02:40 AM, Augie Fackler wrote:
> > On Thu, Nov 17, 2016 at 11:49:58PM +0000, Jun Wu wrote:
> >> # HG changeset patch
> >> # User Jun Wu <quark@fb.com>
> >> # Date 1479426495 0
> >> #      Thu Nov 17 23:48:15 2016 +0000
> >> # Node ID e5451a607d1ca53b2446ab049375e5dd5a055bb8
> >> # Parent  87e0edc93d87b88e2925877469d8c142e01737fc
> >> # Available At https://bitbucket.org/quark-zju/hg-draft 
> >> #              hg pull https://bitbucket.org/quark-zju/hg-draft  -r e5451a607d1c
> >> rebase: calculate ancestors for --base separately (issue5420)
> >
> > These are queued, thanks.
> 
> I'm a bit concerned about the lack of test covering situation with merge 
> commit. There could be pathological case lurking there. I'll try to a 
> have a deeper look at what this change imply is that case before giving 
> it a second accept stamp.
> 
> >> Previously, the --base option only works with a single "branch" - if there
> >> are multiple branching points, "rebase" will error out with:
> >>
> >>   abort: source is ancestor of destination
> >>
> >> This happens if the user has multiple draft branches with different
> >> branching points, and uses "hg rebase -b 'draft()' -d master". The error
> >> message looks cryptic to users who don't know the implementation detail.
> >>
> >> This patch changes the logic to calculate ancestors for each "base" branch
> >> so it would work in the multiple branching points case.
> >>
> >> Note: if there are multiple bases where some of them are rebasable, while
> >> some of them aren't because the branching point is the destination, the
> >> current behavior is to abort with "nothing to rebase", which seems wrong.
> >> However, that issue is not introduced by this patch - it exists for "-s" as
> >> well. I have reported it as issue5422 and should be solved separately.
> >>
> >> diff --git a/hgext/rebase.py b/hgext/rebase.py
> >> --- a/hgext/rebase.py
> >> +++ b/hgext/rebase.py
> >> @@ -722,10 +722,17 @@ def _definesets(ui, repo, destf=None, sr
> >>              destf = str(dest)
> >>
> >> -        commonanc = repo.revs('ancestor(%ld, %d)', base, dest).first()
> >> -        if commonanc is not None:
> >> -            rebaseset = repo.revs('(%d::(%ld) - %d)::',
> >> -                                  commonanc, base, commonanc)
> >> -        else:
> >> -            rebaseset = []
> >> +        # calculate ancestors for individual bases
> >> +        realbases = []
> >> +        for b in repo.revs('roots(%ld)', base):
> >> +            # branching point
> >> +            bp = repo.revs('ancestor(%d, %d)', b, dest).first()
> >> +            if bp is None:
> >> +                continue
> >> +            # move b to be the direct child of the branching point
> >> +            b = repo.revs('%d::%d - %d', bp, b, bp).first()
> >> +            if b is not None:
> >> +                realbases.append(b)
> >> +
> >> +        rebaseset = repo.revs('%ld::', realbases)
> >>
> >>          if not rebaseset:
> >> diff --git a/tests/test-rebase-base.t b/tests/test-rebase-base.t
> >> new file mode 100644
> >> --- /dev/null
> >> +++ b/tests/test-rebase-base.t
> >> @@ -0,0 +1,94 @@
> >> +  $ cat >> $HGRCPATH <<EOF
> >> +  > [extensions]
> >> +  > rebase=
> >> +  > drawdag=$TESTDIR/drawdag.py
> >> +  >
> >> +  > [phases]
> >> +  > publish=False
> >> +  >
> >> +  > [alias]
> >> +  > tglog = log -G --template "{rev}: {desc}"
> >> +  > EOF
> >> +
> >> +  $ hg init a
> >> +  $ cd a
> >> +
> >> +  $ hg debugdrawdag <<EOS
> >> +  > g f
> >> +  > |/
> >> +  > e c d
> >> +  > | |/
> >> +  > | b
> >> +  > |/
> >> +  > a
> >> +  > EOS
> >> +
> >> +  $ cd ..
> >> +
> >> +Pick a single base:
> >> +
> >> +  $ cp -a a a1 && cd a1
> >> +  $ hg rebase -b c -d g -q
> >> +  $ hg tglog
> >> +  o  6: d
> >> +  |
> >> +  | o  5: c
> >> +  |/
> >> +  o  4: b
> >> +  |
> >> +  o  3: g
> >> +  |
> >> +  | o  2: f
> >> +  |/
> >> +  o  1: e
> >> +  |
> >> +  o  0: a
> >> +
> >> +  $ cd ..
> >> +
> >> +Pick a base that is already an descendant of dest:
> >> +
> >> +  $ cp -a a a2 && cd a2
> >> +  $ hg rebase -b g -d e
> >> +  nothing to rebase
> >> +  [1]
> >> +  $ hg rebase -b d -d a
> >> +  nothing to rebase
> >> +  [1]
> >> +  $ hg rebase -b d+c+f+e -d a
> >> +  nothing to rebase
> >> +  [1]
> >> +  $ cd ..
> >> +
> >> +Pick multiple bases (issue5420):
> >> +
> >> +  $ cp -a a a3 && cd a3
> >> +  $ hg rebase -b d+f -d g -q
> >> +  $ hg tglog
> >> +  o  6: f
> >> +  |
> >> +  | o  5: d
> >> +  | |
> >> +  | | o  4: c
> >> +  | |/
> >> +  | o  3: b
> >> +  |/
> >> +  o  2: g
> >> +  |
> >> +  o  1: e
> >> +  |
> >> +  o  0: a
> >> +
> >> +  $ cd ..
> >> +
> >> +Mixed rebasable and non-rebasable bases (unresolved, issue5422):
> >> +
> >> +  $ cp -a a a4 && cd a4
> >> +  $ hg debugdrawdag <<EOS
> >> +  > h
> >> +  > |
> >> +  > g
> >> +  > EOS
> >> +  $ hg rebase -b d+f+h -d g
> >> +  nothing to rebase
> >> +  [1]
> >> https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel 
> > https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel 
> >
>
Pierre-Yves David - Nov. 28, 2016, 1:42 a.m.
I finally took the time to look at this more in depth.

On 11/25/2016 01:58 PM, Jun Wu wrote:
> I have added "pathological" cases I can think of in
> patchwork.mercurial-scm.org/patch/17754/

Thanks for providing more test case including merge.

An underlying question of my question about case with merge was "Do we 
have behavior change, and if so, which one?". Moving from a crash to 
something somewhat correct is a good step. But if we may move from one 
action to another action, we have to be careful:

* What are the difference?
* Could we have user relying on the old behavior?
* Is the new behavior a big enough improvement to justify the change?

Unfortunately your new patches did not answer these questions :-/

I've poked a bit at this and:

* I could find behavior change (undocumented in your patches) that are 
not necessary a win),

* The code makes a simplification (get a single 'realbase' per base) 
that seems a bit too strong (hence the behavior change pointed above and 
example below), it seems like there is room for improvement here.

* I've found interesting merge combination uncovered by your tests.

Example of behavior change:
---------------------------

     E
     |\
     C D
     |/
     | F
     |/
     B
     |
     A

   running: hg rebase --base E --dest F

   rebaseset with 4.0: [C, D, E]
   rebaseset with this patch: [C, E]


Example of untested merge scenario
----------------------------------
   (a case were greatest common ancestors for both can be different
    from individual one while being still valid)

(trying your merge syntax)

   D     C1    A3     B3
   |    /     / \    / \
   M3 C0     A1  A2 B1  B2
   | /       |   |  |   |
   M2        M1  C1 C1  M3
   |
   M1
   |
   M0



To conclude, there I feel like there is too many undocumented or 
unexplored impact on existing behavior with this patch. Including 
already an identified change that would qualify to be investigated as a 
regression. We need to spend more time investigating here. Since there 
was 92 other patches ready for landing above that one, I've dropped it 
from hg-committed for now (+ the followup). We can call each other this 
week to discuss this further if you want help to move forward

Some suggestion for future similar work (or this patch):

* avoid using the root as a significant changeset for your test cases, 
the root is a limit value with sometime strange behavior (so it is good 
to test it independently)

* avoid using --quiet rebase in your test. Having output about what is 
happening helps understanding the test case and catching subtle breakage,

* I would use Capitale letter for your changeset or the full version of 
config flag (or both). My old eyes have trouble reading test full of "-b 
c -d g -q" :-p

* test case could be a bit more documented. having some section 
(underlined with ------) and minimal explanation of what is the test 
case will help the next poor soul reading it next (eg: the reviewer)

> I believe the current "--base" implementation is bug-free regarding to merges,
> otherwise "-s" will have bugs, too.

I'm a bit confused by this sentence. I know that rebase can handle merge 
when doing and actual rebase. However, the question we are focusing on 
here is the definition of the rebaseset. That definition is trivial in 
the --src case, so I'm not sure why you are bringing it up.

Cheers,

> Excerpts from Pierre-Yves David's message of 2016-11-23 16:54:51 +0100:
>>
>> On 11/19/2016 02:40 AM, Augie Fackler wrote:
>>> On Thu, Nov 17, 2016 at 11:49:58PM +0000, Jun Wu wrote:
>>>> # HG changeset patch
>>>> # User Jun Wu <quark@fb.com>
>>>> # Date 1479426495 0
>>>> #      Thu Nov 17 23:48:15 2016 +0000
>>>> # Node ID e5451a607d1ca53b2446ab049375e5dd5a055bb8
>>>> # Parent  87e0edc93d87b88e2925877469d8c142e01737fc
>>>> # Available At https://bitbucket.org/quark-zju/hg-draft
>>>> #              hg pull https://bitbucket.org/quark-zju/hg-draft  -r e5451a607d1c
>>>> rebase: calculate ancestors for --base separately (issue5420)
>>>
>>> These are queued, thanks.
>>
>> I'm a bit concerned about the lack of test covering situation with merge
>> commit. There could be pathological case lurking there. I'll try to a
>> have a deeper look at what this change imply is that case before giving
>> it a second accept stamp.
>>
>>>> Previously, the --base option only works with a single "branch" - if there
>>>> are multiple branching points, "rebase" will error out with:
>>>>
>>>>   abort: source is ancestor of destination
>>>>
>>>> This happens if the user has multiple draft branches with different
>>>> branching points, and uses "hg rebase -b 'draft()' -d master". The error
>>>> message looks cryptic to users who don't know the implementation detail.
>>>>
>>>> This patch changes the logic to calculate ancestors for each "base" branch
>>>> so it would work in the multiple branching points case.
>>>>
>>>> Note: if there are multiple bases where some of them are rebasable, while
>>>> some of them aren't because the branching point is the destination, the
>>>> current behavior is to abort with "nothing to rebase", which seems wrong.
>>>> However, that issue is not introduced by this patch - it exists for "-s" as
>>>> well. I have reported it as issue5422 and should be solved separately.
>>>>
>>>> diff --git a/hgext/rebase.py b/hgext/rebase.py
>>>> --- a/hgext/rebase.py
>>>> +++ b/hgext/rebase.py
>>>> @@ -722,10 +722,17 @@ def _definesets(ui, repo, destf=None, sr
>>>>              destf = str(dest)
>>>>
>>>> -        commonanc = repo.revs('ancestor(%ld, %d)', base, dest).first()
>>>> -        if commonanc is not None:
>>>> -            rebaseset = repo.revs('(%d::(%ld) - %d)::',
>>>> -                                  commonanc, base, commonanc)
>>>> -        else:
>>>> -            rebaseset = []
>>>> +        # calculate ancestors for individual bases
>>>> +        realbases = []
>>>> +        for b in repo.revs('roots(%ld)', base):
>>>> +            # branching point
>>>> +            bp = repo.revs('ancestor(%d, %d)', b, dest).first()
>>>> +            if bp is None:
>>>> +                continue
>>>> +            # move b to be the direct child of the branching point
>>>> +            b = repo.revs('%d::%d - %d', bp, b, bp).first()
>>>> +            if b is not None:
>>>> +                realbases.append(b)
>>>> +
>>>> +        rebaseset = repo.revs('%ld::', realbases)
>>>>
>>>>          if not rebaseset:
>>>> diff --git a/tests/test-rebase-base.t b/tests/test-rebase-base.t
>>>> new file mode 100644
>>>> --- /dev/null
>>>> +++ b/tests/test-rebase-base.t
>>>> @@ -0,0 +1,94 @@
>>>> +  $ cat >> $HGRCPATH <<EOF
>>>> +  > [extensions]
>>>> +  > rebase=
>>>> +  > drawdag=$TESTDIR/drawdag.py
>>>> +  >
>>>> +  > [phases]
>>>> +  > publish=False
>>>> +  >
>>>> +  > [alias]
>>>> +  > tglog = log -G --template "{rev}: {desc}"
>>>> +  > EOF
>>>> +
>>>> +  $ hg init a
>>>> +  $ cd a
>>>> +
>>>> +  $ hg debugdrawdag <<EOS
>>>> +  > g f
>>>> +  > |/
>>>> +  > e c d
>>>> +  > | |/
>>>> +  > | b
>>>> +  > |/
>>>> +  > a
>>>> +  > EOS
>>>> +
>>>> +  $ cd ..
>>>> +
>>>> +Pick a single base:
>>>> +
>>>> +  $ cp -a a a1 && cd a1
>>>> +  $ hg rebase -b c -d g -q
>>>> +  $ hg tglog
>>>> +  o  6: d
>>>> +  |
>>>> +  | o  5: c
>>>> +  |/
>>>> +  o  4: b
>>>> +  |
>>>> +  o  3: g
>>>> +  |
>>>> +  | o  2: f
>>>> +  |/
>>>> +  o  1: e
>>>> +  |
>>>> +  o  0: a
>>>> +
>>>> +  $ cd ..
>>>> +
>>>> +Pick a base that is already an descendant of dest:
>>>> +
>>>> +  $ cp -a a a2 && cd a2
>>>> +  $ hg rebase -b g -d e
>>>> +  nothing to rebase
>>>> +  [1]
>>>> +  $ hg rebase -b d -d a
>>>> +  nothing to rebase
>>>> +  [1]
>>>> +  $ hg rebase -b d+c+f+e -d a
>>>> +  nothing to rebase
>>>> +  [1]
>>>> +  $ cd ..
>>>> +
>>>> +Pick multiple bases (issue5420):
>>>> +
>>>> +  $ cp -a a a3 && cd a3
>>>> +  $ hg rebase -b d+f -d g -q
>>>> +  $ hg tglog
>>>> +  o  6: f
>>>> +  |
>>>> +  | o  5: d
>>>> +  | |
>>>> +  | | o  4: c
>>>> +  | |/
>>>> +  | o  3: b
>>>> +  |/
>>>> +  o  2: g
>>>> +  |
>>>> +  o  1: e
>>>> +  |
>>>> +  o  0: a
>>>> +
>>>> +  $ cd ..
>>>> +
>>>> +Mixed rebasable and non-rebasable bases (unresolved, issue5422):
>>>> +
>>>> +  $ cp -a a a4 && cd a4
>>>> +  $ hg debugdrawdag <<EOS
>>>> +  > h
>>>> +  > |
>>>> +  > g
>>>> +  > EOS
>>>> +  $ hg rebase -b d+f+h -d g
>>>> +  nothing to rebase
>>>> +  [1]
>>>> https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
>>> https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
>>>
>>
Jun Wu - Nov. 28, 2016, 2:55 a.m.
Excerpts from Pierre-Yves David's message of 2016-11-28 02:42:21 +0100:
> I finally took the time to look at this more in depth.
> 
> On 11/25/2016 01:58 PM, Jun Wu wrote:
> > I have added "pathological" cases I can think of in
> > patchwork.mercurial-scm.org/patch/17754/
> 
> Thanks for providing more test case including merge.
> 
> An underlying question of my question about case with merge was "Do we 
> have behavior change, and if so, which one?". Moving from a crash to 
> something somewhat correct is a good step. But if we may move from one 
> action to another action, we have to be careful:
> 
> * What are the difference?
> * Could we have user relying on the old behavior?
> * Is the new behavior a big enough improvement to justify the change?
> 
> Unfortunately your new patches did not answer these questions :-/
> 
> I've poked a bit at this and:
> 
> * I could find behavior change (undocumented in your patches) that are 
> not necessary a win),
> 
> * The code makes a simplification (get a single 'realbase' per base) 
> that seems a bit too strong (hence the behavior change pointed above and 
> example below), it seems like there is room for improvement here.
> 
> * I've found interesting merge combination uncovered by your tests.
> 
> Example of behavior change:
> ---------------------------
> 
>      E
>      |\
>      C D
>      |/
>      | F
>      |/
>      B
>      |
>      A
> 
>    running: hg rebase --base E --dest F
> 
>    rebaseset with 4.0: [C, D, E]

I think I was testing against an incorrect version. Will try to fix it...

>    rebaseset with this patch: [C, E]
> 
> 
> Example of untested merge scenario
> ----------------------------------
>    (a case were greatest common ancestors for both can be different
>     from individual one while being still valid)
> 
> (trying your merge syntax)
> 
>    D     C1    A3     B3
>    |    /     / \    / \
>    M3 C0     A1  A2 B1  B2
>    | /       |   |  |   |
>    M2        M1  C1 C1  M3
>    |
>    M1
>    |
>    M0
> 
> 
> 
> To conclude, there I feel like there is too many undocumented or 
> unexplored impact on existing behavior with this patch. Including 
> already an identified change that would qualify to be investigated as a 
> regression. We need to spend more time investigating here. Since there 
> was 92 other patches ready for landing above that one, I've dropped it 
> from hg-committed for now (+ the followup). We can call each other this 
> week to discuss this further if you want help to move forward
> 
> Some suggestion for future similar work (or this patch):
> 
> * avoid using the root as a significant changeset for your test cases, 
> the root is a limit value with sometime strange behavior (so it is good 
> to test it independently)
> 
> * avoid using --quiet rebase in your test. Having output about what is 
> happening helps understanding the test case and catching subtle breakage,
> 
> * I would use Capitale letter for your changeset or the full version of 
> config flag (or both). My old eyes have trouble reading test full of "-b 
> c -d g -q" :-p
> 
> * test case could be a bit more documented. having some section 
> (underlined with ------) and minimal explanation of what is the test 
> case will help the next poor soul reading it next (eg: the reviewer)
> 
> > I believe the current "--base" implementation is bug-free regarding to merges,
> > otherwise "-s" will have bugs, too.
> 
> I'm a bit confused by this sentence. I know that rebase can handle merge 
> when doing and actual rebase. However, the question we are focusing on 
> here is the definition of the rebaseset. That definition is trivial in 
> the --src case, so I'm not sure why you are bringing it up.
> 
> Cheers,
> 
> > Excerpts from Pierre-Yves David's message of 2016-11-23 16:54:51 +0100:
> >>
> >> On 11/19/2016 02:40 AM, Augie Fackler wrote:
> >>> On Thu, Nov 17, 2016 at 11:49:58PM +0000, Jun Wu wrote:
> >>>> # HG changeset patch
> >>>> # User Jun Wu <quark@fb.com>
> >>>> # Date 1479426495 0
> >>>> #      Thu Nov 17 23:48:15 2016 +0000
> >>>> # Node ID e5451a607d1ca53b2446ab049375e5dd5a055bb8
> >>>> # Parent  87e0edc93d87b88e2925877469d8c142e01737fc
> >>>> # Available At https://bitbucket.org/quark-zju/hg-draft 
> >>>> #              hg pull https://bitbucket.org/quark-zju/hg-draft   -r e5451a607d1c
> >>>> rebase: calculate ancestors for --base separately (issue5420)
> >>>
> >>> These are queued, thanks.
> >>
> >> I'm a bit concerned about the lack of test covering situation with merge
> >> commit. There could be pathological case lurking there. I'll try to a
> >> have a deeper look at what this change imply is that case before giving
> >> it a second accept stamp.
> >>
> >>>> Previously, the --base option only works with a single "branch" - if there
> >>>> are multiple branching points, "rebase" will error out with:
> >>>>
> >>>>   abort: source is ancestor of destination
> >>>>
> >>>> This happens if the user has multiple draft branches with different
> >>>> branching points, and uses "hg rebase -b 'draft()' -d master". The error
> >>>> message looks cryptic to users who don't know the implementation detail.
> >>>>
> >>>> This patch changes the logic to calculate ancestors for each "base" branch
> >>>> so it would work in the multiple branching points case.
> >>>>
> >>>> Note: if there are multiple bases where some of them are rebasable, while
> >>>> some of them aren't because the branching point is the destination, the
> >>>> current behavior is to abort with "nothing to rebase", which seems wrong.
> >>>> However, that issue is not introduced by this patch - it exists for "-s" as
> >>>> well. I have reported it as issue5422 and should be solved separately.
> >>>>
> >>>> diff --git a/hgext/rebase.py b/hgext/rebase.py
> >>>> --- a/hgext/rebase.py
> >>>> +++ b/hgext/rebase.py
> >>>> @@ -722,10 +722,17 @@ def _definesets(ui, repo, destf=None, sr
> >>>>              destf = str(dest)
> >>>>
> >>>> -        commonanc = repo.revs('ancestor(%ld, %d)', base, dest).first()
> >>>> -        if commonanc is not None:
> >>>> -            rebaseset = repo.revs('(%d::(%ld) - %d)::',
> >>>> -                                  commonanc, base, commonanc)
> >>>> -        else:
> >>>> -            rebaseset = []
> >>>> +        # calculate ancestors for individual bases
> >>>> +        realbases = []
> >>>> +        for b in repo.revs('roots(%ld)', base):
> >>>> +            # branching point
> >>>> +            bp = repo.revs('ancestor(%d, %d)', b, dest).first()
> >>>> +            if bp is None:
> >>>> +                continue
> >>>> +            # move b to be the direct child of the branching point
> >>>> +            b = repo.revs('%d::%d - %d', bp, b, bp).first()
> >>>> +            if b is not None:
> >>>> +                realbases.append(b)
> >>>> +
> >>>> +        rebaseset = repo.revs('%ld::', realbases)
> >>>>
> >>>>          if not rebaseset:
> >>>> diff --git a/tests/test-rebase-base.t b/tests/test-rebase-base.t
> >>>> new file mode 100644
> >>>> --- /dev/null
> >>>> +++ b/tests/test-rebase-base.t
> >>>> @@ -0,0 +1,94 @@
> >>>> +  $ cat >> $HGRCPATH <<EOF
> >>>> +  > [extensions]
> >>>> +  > rebase=
> >>>> +  > drawdag=$TESTDIR/drawdag.py
> >>>> +  >
> >>>> +  > [phases]
> >>>> +  > publish=False
> >>>> +  >
> >>>> +  > [alias]
> >>>> +  > tglog = log -G --template "{rev}: {desc}"
> >>>> +  > EOF
> >>>> +
> >>>> +  $ hg init a
> >>>> +  $ cd a
> >>>> +
> >>>> +  $ hg debugdrawdag <<EOS
> >>>> +  > g f
> >>>> +  > |/
> >>>> +  > e c d
> >>>> +  > | |/
> >>>> +  > | b
> >>>> +  > |/
> >>>> +  > a
> >>>> +  > EOS
> >>>> +
> >>>> +  $ cd ..
> >>>> +
> >>>> +Pick a single base:
> >>>> +
> >>>> +  $ cp -a a a1 && cd a1
> >>>> +  $ hg rebase -b c -d g -q
> >>>> +  $ hg tglog
> >>>> +  o  6: d
> >>>> +  |
> >>>> +  | o  5: c
> >>>> +  |/
> >>>> +  o  4: b
> >>>> +  |
> >>>> +  o  3: g
> >>>> +  |
> >>>> +  | o  2: f
> >>>> +  |/
> >>>> +  o  1: e
> >>>> +  |
> >>>> +  o  0: a
> >>>> +
> >>>> +  $ cd ..
> >>>> +
> >>>> +Pick a base that is already an descendant of dest:
> >>>> +
> >>>> +  $ cp -a a a2 && cd a2
> >>>> +  $ hg rebase -b g -d e
> >>>> +  nothing to rebase
> >>>> +  [1]
> >>>> +  $ hg rebase -b d -d a
> >>>> +  nothing to rebase
> >>>> +  [1]
> >>>> +  $ hg rebase -b d+c+f+e -d a
> >>>> +  nothing to rebase
> >>>> +  [1]
> >>>> +  $ cd ..
> >>>> +
> >>>> +Pick multiple bases (issue5420):
> >>>> +
> >>>> +  $ cp -a a a3 && cd a3
> >>>> +  $ hg rebase -b d+f -d g -q
> >>>> +  $ hg tglog
> >>>> +  o  6: f
> >>>> +  |
> >>>> +  | o  5: d
> >>>> +  | |
> >>>> +  | | o  4: c
> >>>> +  | |/
> >>>> +  | o  3: b
> >>>> +  |/
> >>>> +  o  2: g
> >>>> +  |
> >>>> +  o  1: e
> >>>> +  |
> >>>> +  o  0: a
> >>>> +
> >>>> +  $ cd ..
> >>>> +
> >>>> +Mixed rebasable and non-rebasable bases (unresolved, issue5422):
> >>>> +
> >>>> +  $ cp -a a a4 && cd a4
> >>>> +  $ hg debugdrawdag <<EOS
> >>>> +  > h
> >>>> +  > |
> >>>> +  > g
> >>>> +  > EOS
> >>>> +  $ hg rebase -b d+f+h -d g
> >>>> +  nothing to rebase
> >>>> +  [1]
> >>>> https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel 
> >>> https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel 
> >>>
> >>
>

Patch

diff --git a/hgext/rebase.py b/hgext/rebase.py
--- a/hgext/rebase.py
+++ b/hgext/rebase.py
@@ -722,10 +722,17 @@  def _definesets(ui, repo, destf=None, sr
             destf = str(dest)
 
-        commonanc = repo.revs('ancestor(%ld, %d)', base, dest).first()
-        if commonanc is not None:
-            rebaseset = repo.revs('(%d::(%ld) - %d)::',
-                                  commonanc, base, commonanc)
-        else:
-            rebaseset = []
+        # calculate ancestors for individual bases
+        realbases = []
+        for b in repo.revs('roots(%ld)', base):
+            # branching point
+            bp = repo.revs('ancestor(%d, %d)', b, dest).first()
+            if bp is None:
+                continue
+            # move b to be the direct child of the branching point
+            b = repo.revs('%d::%d - %d', bp, b, bp).first()
+            if b is not None:
+                realbases.append(b)
+
+        rebaseset = repo.revs('%ld::', realbases)
 
         if not rebaseset:
diff --git a/tests/test-rebase-base.t b/tests/test-rebase-base.t
new file mode 100644
--- /dev/null
+++ b/tests/test-rebase-base.t
@@ -0,0 +1,94 @@ 
+  $ cat >> $HGRCPATH <<EOF
+  > [extensions]
+  > rebase=
+  > drawdag=$TESTDIR/drawdag.py
+  > 
+  > [phases]
+  > publish=False
+  > 
+  > [alias]
+  > tglog = log -G --template "{rev}: {desc}"
+  > EOF
+
+  $ hg init a
+  $ cd a
+
+  $ hg debugdrawdag <<EOS
+  > g f
+  > |/
+  > e c d
+  > | |/
+  > | b
+  > |/
+  > a
+  > EOS
+
+  $ cd ..
+
+Pick a single base:
+
+  $ cp -a a a1 && cd a1
+  $ hg rebase -b c -d g -q
+  $ hg tglog
+  o  6: d
+  |
+  | o  5: c
+  |/
+  o  4: b
+  |
+  o  3: g
+  |
+  | o  2: f
+  |/
+  o  1: e
+  |
+  o  0: a
+  
+  $ cd ..
+
+Pick a base that is already an descendant of dest:
+
+  $ cp -a a a2 && cd a2
+  $ hg rebase -b g -d e
+  nothing to rebase
+  [1]
+  $ hg rebase -b d -d a
+  nothing to rebase
+  [1]
+  $ hg rebase -b d+c+f+e -d a
+  nothing to rebase
+  [1]
+  $ cd ..
+
+Pick multiple bases (issue5420):
+
+  $ cp -a a a3 && cd a3
+  $ hg rebase -b d+f -d g -q
+  $ hg tglog
+  o  6: f
+  |
+  | o  5: d
+  | |
+  | | o  4: c
+  | |/
+  | o  3: b
+  |/
+  o  2: g
+  |
+  o  1: e
+  |
+  o  0: a
+  
+  $ cd ..
+
+Mixed rebasable and non-rebasable bases (unresolved, issue5422):
+
+  $ cp -a a a4 && cd a4
+  $ hg debugdrawdag <<EOS
+  > h
+  > |
+  > g
+  > EOS
+  $ hg rebase -b d+f+h -d g
+  nothing to rebase
+  [1]