Mercurial > hg
changeset 34006:32528419db64
rebase: sort destmap topologically
Previously rebase source and destination could not overlap. But with the
multi-destination support, source and destination could reasonably partially
overlap. That requires another topological sort on `{sourcerev: destrev}`
graph (destmap). This patch implements that.
If a revision's destination is itself, the error message gets changed from
"source is ancestor of destination" to "source and destination form a
cycle". Not marking as BC since automation should depend on exit code, not
error message.
Differential Revision: https://phab.mercurial-scm.org/D470
| author | Jun Wu <quark@fb.com> |
|---|---|
| date | Mon, 21 Aug 2017 20:22:07 -0700 |
| parents | 5e83a8fe6bc4 |
| children | 06b0cc2588de |
| files | hgext/rebase.py tests/test-rebase-dest.t tests/test-rebase-named-branches.t tests/test-rebase-scenario-global.t |
| diffstat | 4 files changed, 219 insertions(+), 15 deletions(-) [+] |
line wrap: on
line diff
--- a/hgext/rebase.py Tue Aug 29 17:27:37 2017 -0700 +++ b/hgext/rebase.py Mon Aug 21 20:22:07 2017 -0700 @@ -361,7 +361,7 @@ self.ui.status(_('reopening closed branch head %s\n') % dest) def _performrebase(self, tr): - repo, ui, opts = self.repo, self.ui, self.opts + repo, ui = self.repo, self.ui if self.keepbranchesf: # insert _savebranch at the start of extrafns so if # there's a user-provided extrafn it can clobber branch if @@ -384,10 +384,17 @@ # if we fail before the transaction closes. self.storestatus() - sortedrevs = repo.revs('sort(%ld, -topo)', self.state) cands = [k for k, v in self.state.iteritems() if v == revtodo] total = len(cands) pos = 0 + for subset in sortsource(self.destmap): + pos = self._performrebasesubset(tr, subset, pos, total) + ui.progress(_('rebasing'), None) + ui.note(_('rebase merging completed\n')) + + def _performrebasesubset(self, tr, subset, pos, total): + repo, ui, opts = self.repo, self.ui, self.opts + sortedrevs = repo.revs('sort(%ld, -topo)', subset) for rev in sortedrevs: dest = self.destmap[rev] ctx = repo[rev] @@ -449,9 +456,7 @@ else: ui.status(_('already rebased %s as %s\n') % (desc, repo[self.state[rev]])) - - ui.progress(_('rebasing'), None) - ui.note(_('rebase merging completed\n')) + return pos def _finishrebase(self): repo, ui, opts = self.repo, self.ui, self.opts @@ -969,6 +974,18 @@ | B | ... |/ |/ A A + + Besides, adjust dest according to existing rebase information. For example, + + B C D B needs to be rebased on top of C, C needs to be rebased on top + \|/ of D. We will rebase C first. + A + + C' After rebasing C, when considering B's destination, use C' + | instead of the original C. + B D + \ / + A """ # pick already rebased revs with same dest from state as interesting source dest = destmap[rev] @@ -981,6 +998,12 @@ candidate = repo.revs('max(%ld and (::%d))', source, prev).first() if candidate is not None: adjusted = state[candidate] + if adjusted == dest and dest in state: + adjusted = state[dest] + if adjusted == revtodo: + # sortsource should produce an order that makes this impossible + raise error.ProgrammingError( + 'rev %d should be rebased already at this time' % dest) result.append(adjusted) return result @@ -1128,6 +1151,12 @@ 'moving at least one of its parents') % (rev, repo[rev])) + # Source should not be ancestor of dest. The check here guarantees it's + # impossible. With multi-dest, the initial check does not cover complex + # cases since we don't have abstractions to dry-run rebase cheaply. + if any(p != nullrev and isancestor(rev, p) for p in newps): + raise error.Abort(_('source is ancestor of destination')) + # "rebasenode" updates to new p1, use the corresponding merge base. if bases[0] != nullrev: base = bases[0] @@ -1354,6 +1383,31 @@ repo.ui.warn(_('rebase aborted\n')) return 0 +def sortsource(destmap): + """yield source revisions in an order that we only rebase things once + + If source and destination overlaps, we should filter out revisions + depending on other revisions which hasn't been rebased yet. + + Yield a sorted list of revisions each time. + + For example, when rebasing A to B, B to C. This function yields [B], then + [A], indicating B needs to be rebased first. + + Raise if there is a cycle so the rebase is impossible. + """ + srcset = set(destmap) + while srcset: + srclist = sorted(srcset) + result = [] + for r in srclist: + if destmap[r] not in srcset: + result.append(r) + if not result: + raise error.Abort(_('source and destination form a cycle')) + srcset -= set(result) + yield result + def buildstate(repo, destmap, collapse, obsoletenotrebased): '''Define which revisions are going to be rebased and where @@ -1372,12 +1426,21 @@ if set(destmap.values()) & mqapplied: raise error.Abort(_('cannot rebase onto an applied mq patch')) - roots = list(repo.set('roots(%ld)', rebaseset)) + # Get "cycle" error early by exhausting the generator. + sortedsrc = list(sortsource(destmap)) # a list of sorted revs + if not sortedsrc: + raise error.Abort(_('no matching revisions')) + + # Only check the first batch of revisions to rebase not depending on other + # rebaseset. This means "source is ancestor of destination" for the second + # (and following) batches of revisions are not checked here. We rely on + # "defineparents" to do that check. + roots = list(repo.set('roots(%ld)', sortedsrc[0])) if not roots: raise error.Abort(_('no matching revisions')) roots.sort() state = dict.fromkeys(rebaseset, revtodo) - emptyrebase = True + emptyrebase = (len(sortedsrc) == 1) for root in roots: dest = repo[destmap[root.rev()]] commonbase = root.ancestor(dest)
--- a/tests/test-rebase-dest.t Tue Aug 29 17:27:37 2017 -0700 +++ b/tests/test-rebase-dest.t Mon Aug 21 20:22:07 2017 -0700 @@ -204,7 +204,7 @@ > | > Z > EOS - abort: source is ancestor of destination + abort: source and destination form a cycle [255] Switch roots: @@ -291,22 +291,163 @@ |/ o 0: A -Source overlaps with destination (not handled well currently): +Source overlaps with destination: $ rebasewithdag -s 'B+C+D' -d 'map(SRC, "B:C,C:D")' <<'EOS' > B C D > \|/ > A > EOS + rebasing 2:dc0947a82db8 "C" (C) rebasing 1:112478962961 "B" (B) - rebasing 2:dc0947a82db8 "C" (C) - o 5: C + o 5: B + | + o 4: C + | + o 3: D + | + o 0: A + +Detect cycles early: + + $ rebasewithdag -r 'all()-Z' -d 'map(SRC, "A:B,B:C,C:D,D:B")' <<'EOS' + > A B C + > \|/ + > | D + > |/ + > Z + > EOS + abort: source and destination form a cycle + [255] + +Detect source is ancestor of dest in runtime: + + $ rebasewithdag -r 'C+B' -d 'map(SRC, "C:B,B:D")' -q <<'EOS' + > D + > | + > B C + > \| + > A + > EOS + abort: source is ancestor of destination + [255] + +"Already rebased" fast path still works: + + $ rebasewithdag -r 'all()' -d 'SRC^' <<'EOS' + > E F + > /| | + > B C D + > \|/ + > A + > EOS + already rebased 1:112478962961 "B" (B) + already rebased 2:dc0947a82db8 "C" (C) + already rebased 3:b18e25de2cf5 "D" (D) + already rebased 4:312782b8f06e "E" (E) + already rebased 5:ad6717a6a58e "F" (F tip) + o 5: F | o 3: D | - | o 4: B orphan + | o 4: E + | |\ + +---o 2: C | | - | x 2: C + | o 1: B |/ o 0: A +Massively rewrite the DAG: + + $ rebasewithdag -r 'all()' -d 'map(SRC, "A:I,I:null,H:A,B:J,J:C,C:H,D:E,F:G,G:K,K:D,E:B")' <<'EOS' + > D G K + > | | | + > C F J + > | | | + > B E I + > \| | + > A H + > EOS + rebasing 4:701514e1408d "I" (I) + rebasing 0:426bada5c675 "A" (A) + rebasing 1:e7050b6e5048 "H" (H) + rebasing 5:26805aba1e60 "C" (C) + rebasing 7:cf89f86b485b "J" (J) + rebasing 2:112478962961 "B" (B) + rebasing 3:7fb047a69f22 "E" (E) + rebasing 8:f585351a92f8 "D" (D) + rebasing 10:ae41898d7875 "K" (K tip) + rebasing 9:711f53bbef0b "G" (G) + rebasing 6:64a8289d2492 "F" (F) + o 21: F + | + o 20: G + | + o 19: K + | + o 18: D + | + o 17: E + | + o 16: B + | + o 15: J + | + o 14: C + | + o 13: H + | + o 12: A + | + o 11: I + +Resolve instability: + + $ rebasewithdag <<'EOF' -r 'orphan()-obsolete()' -d 'max((successors(max(roots(ALLSRC) & ::SRC)^)-obsolete())::)' + > F2 + > | + > J E E2 + > | |/ + > I2 I | E3 + > \| |/ + > H | G + > | | | + > B2 D F + > | |/ # rebase: B -> B2 + > N C # amend: E -> E2 + > | | # amend: E2 -> E3 + > M B # rebase: F -> F2 + > \| # amend: I -> I2 + > A + > EOF + rebasing 16:5c432343bf59 "J" (J tip) + rebasing 3:26805aba1e60 "C" (C) + rebasing 6:f585351a92f8 "D" (D) + rebasing 10:ffebc37c5d0b "E3" (E3) + rebasing 13:fb184bcfeee8 "F2" (F2) + rebasing 11:dc838ab4c0da "G" (G) + o 22: G + | + o 21: F2 + | + o 20: E3 + | + o 19: D + | + o 18: C + | + o 17: J + | + o 15: I2 + | + o 12: H + | + o 5: B2 + | + o 4: N + | + o 2: M + | + o 0: A +
--- a/tests/test-rebase-named-branches.t Tue Aug 29 17:27:37 2017 -0700 +++ b/tests/test-rebase-named-branches.t Mon Aug 21 20:22:07 2017 -0700 @@ -245,7 +245,7 @@ @ 0: 'A' $ hg rebase -s 5 -d 6 - abort: source is ancestor of destination + abort: source and destination form a cycle [255] $ hg rebase -s 6 -d 5
--- a/tests/test-rebase-scenario-global.t Tue Aug 29 17:27:37 2017 -0700 +++ b/tests/test-rebase-scenario-global.t Mon Aug 21 20:22:07 2017 -0700 @@ -264,7 +264,7 @@ F onto G - rebase onto a descendant: $ hg rebase -s 5 -d 6 - abort: source is ancestor of destination + abort: source and destination form a cycle [255] G onto B - merge revision with both parents not in ancestors of target: