This is an archive of the discontinued Mercurial Phabricator instance.

Differential D470

rebase: sort destmap topologically
ClosedPublic

Authored by quark on Aug 22 2017, 1:16 AM.

Details

Reviewers
None
Group Reviewers
hg-reviewers
Commits
rHG32528419db64: rebase: sort destmap topologically
Summary

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.

The multi-destination feature seems quite usable now so its documentation
was formally added.

.. feature:: Rebase with multi-destinations (experimental)

Previously, rebase only supports one unique destination. Now ``SRC`` and
``ALLSRC`` can be used in rebase destination revset to precisely define
destination per each individual source revision.

For example, the following command could move some orphaned changesets to
reasonable new places so they become no longer orphaned::

  hg rebase
    -r 'orphan()-obsolete()'
    -d 'max((successors(max(roots(ALLSRC) & ::SRC)^)-obsolete())::)'

This feature is disabled by default. To enable it, set
``experimental.rebase.multidest`` to ``true``.

Diff Detail

Repository
rHG Mercurial
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

quark created this revision.Aug 22 2017, 1:16 AM
quark edited the summary of this revision. (Show Details)Aug 25 2017, 12:08 AM
quark updated this revision to Diff 1276.
martinvonz added a subscriber: martinvonz.Aug 28 2017, 3:09 AM

I don't know why, but "make doc" seems to start failing with this patch.

quark updated this revision to Diff 1332.Aug 28 2017, 3:23 AM
quark added inline comments.Aug 28 2017, 3:25 AM
hgext/rebase.py
606

Good catch! It was an unmatched backtick.

martinvonz added a comment.Aug 29 2017, 5:51 PM

The multi-destination feature seems quite usable now so its documentation
was formally added.

It does seem quite usable, but I'm still hesitant to document it. I'd prefer to keep it undocumented (and thus not protected by BC guarantees, I think), so we are more free to change it. What do you think?

quark added a comment.Aug 29 2017, 6:08 PM
In D470#9096, @martinvonz wrote:

The multi-destination feature seems quite usable now so its documentation
was formally added.

It does seem quite usable, but I'm still hesitant to document it. I'd prefer to keep it undocumented (and thus not protected by BC guarantees, I think), so we are more free to change it. What do you think?

Works for me. I can move the docstring to normal comments.

quark added a comment.Aug 29 2017, 6:10 PM

Actually, I'd like to get it documented somehow so people can try it out. I think we can gate it with an experimental config flag.

martinvonz added a comment.Aug 29 2017, 6:13 PM
In D470#9100, @quark wrote:

Actually, I'd like to get it documented somehow so people can try it out. I think we can gate it with an experimental config flag.

Sounds good.

quark edited the summary of this revision. (Show Details)Aug 29 2017, 9:40 PM
quark added a child revision: D565: rebase: remove an unnecessary adjustdest in clearrebased.
quark updated this revision to Diff 1419.
martinvonz added a comment.Aug 30 2017, 1:39 AM

I'm dropping the documentation from this patch and queuing this and its descendants mostly because I depend on D527 for an internal release. I hope you don't mind too much.

hgext/rebase.py
633

Will this still be visible even if the config is off?

Closed by commit rHG32528419db64: rebase: sort destmap topologically (authored by quark). · Explain WhyAug 30 2017, 2:02 AM
This revision was automatically updated to reflect the committed changes.
quark added a comment.Aug 30 2017, 3:58 PM

Thanks! I think we can add documentation later.

hgext/rebase.py
633

Good catch.

Revision Contents
Changeset List

Diff 1427

hgext/rebase.py

self.external = externalparent(self.repo, self.state, destancestors) self.external = externalparent(self.repo, self.state, destancestors)
for destrev in sorted(set(destmap.values())): for destrev in sorted(set(destmap.values())):
dest = self.repo[destrev] dest = self.repo[destrev]
if dest.closesbranch() and not self.keepbranchesf: if dest.closesbranch() and not self.keepbranchesf:
self.ui.status(_('reopening closed branch head %s\n') % dest) self.ui.status(_('reopening closed branch head %s\n') % dest)
def _performrebase(self, tr): def _performrebase(self, tr):
repo, ui, opts = self.repo, self.ui, self.opts repo, ui = self.repo, self.ui
if self.keepbranchesf: if self.keepbranchesf:
# insert _savebranch at the start of extrafns so if # insert _savebranch at the start of extrafns so if
# there's a user-provided extrafn it can clobber branch if # there's a user-provided extrafn it can clobber branch if
# desired # desired
self.extrafns.insert(0, _savebranch) self.extrafns.insert(0, _savebranch)
if self.collapsef: if self.collapsef:
branches = set() branches = set()
for rev in self.state: for rev in self.state:
branches.add(repo[rev].branch()) branches.add(repo[rev].branch())
if len(branches) > 1: if len(branches) > 1:
raise error.Abort(_('cannot collapse multiple named ' raise error.Abort(_('cannot collapse multiple named '
'branches')) 'branches'))
# Keep track of the active bookmarks in order to reset them later # Keep track of the active bookmarks in order to reset them later
self.activebookmark = self.activebookmark or repo._activebookmark self.activebookmark = self.activebookmark or repo._activebookmark
if self.activebookmark: if self.activebookmark:
bookmarks.deactivate(repo) bookmarks.deactivate(repo)
# Store the state before we begin so users can run 'hg rebase --abort' # Store the state before we begin so users can run 'hg rebase --abort'
# if we fail before the transaction closes. # if we fail before the transaction closes.
self.storestatus() self.storestatus()
sortedrevs = repo.revs('sort(%ld, -topo)', self.state)
cands = [k for k, v in self.state.iteritems() if v == revtodo] cands = [k for k, v in self.state.iteritems() if v == revtodo]
total = len(cands) total = len(cands)
pos = 0 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: for rev in sortedrevs:
dest = self.destmap[rev] dest = self.destmap[rev]
ctx = repo[rev] ctx = repo[rev]
desc = _ctxdesc(ctx) desc = _ctxdesc(ctx)
if self.state[rev] == rev: if self.state[rev] == rev:
ui.status(_('already rebased %s\n') % desc) ui.status(_('already rebased %s\n') % desc)
elif self.state[rev] == revtodo: elif self.state[rev] == revtodo:
pos += 1 pos += 1
ui.warn(_('note: rebase of %d:%s created no changes ' ui.warn(_('note: rebase of %d:%s created no changes '
'to commit\n') % (rev, ctx)) 'to commit\n') % (rev, ctx))
self.skipped.add(rev) self.skipped.add(rev)
self.state[rev] = p1 self.state[rev] = p1
ui.debug('next revision set to %s\n' % p1) ui.debug('next revision set to %s\n' % p1)
else: else:
ui.status(_('already rebased %s as %s\n') % ui.status(_('already rebased %s as %s\n') %
(desc, repo[self.state[rev]])) (desc, repo[self.state[rev]]))
return pos
ui.progress(_('rebasing'), None)
ui.note(_('rebase merging completed\n'))
def _finishrebase(self): def _finishrebase(self):
repo, ui, opts = self.repo, self.ui, self.opts repo, ui, opts = self.repo, self.ui, self.opts
if self.collapsef and not self.keepopen: if self.collapsef and not self.keepopen:
p1, p2, _base = defineparents(repo, min(self.state), self.destmap, p1, p2, _base = defineparents(repo, min(self.state), self.destmap,
self.state) self.state)
editopt = opts.get('edit') editopt = opts.get('edit')
editform = 'rebase.collapse' editform = 'rebase.collapse'
deleted, there is no hook presently available for this. deleted, there is no hook presently available for this.
If a rebase is interrupted to manually resolve a conflict, it can be If a rebase is interrupted to manually resolve a conflict, it can be
continued with --continue/-c or aborted with --abort/-a. continued with --continue/-c or aborted with --abort/-a.
.. container:: verbose .. container:: verbose
Examples: Examples:
quarkAuthorUnsubmitted
Not Done

Good catch! It was an unmatched backtick.

quark: Good catch! It was an unmatched backtick.
- move "local changes" (current commit back to branching point) - move "local changes" (current commit back to branching point)
to the current branch tip after a pull:: to the current branch tip after a pull::
hg rebase hg rebase
- move a single changeset to the stable branch:: - move a single changeset to the stable branch::
hg rebase -r 5f493448 -d stable hg rebase -r 5f493448 -d stable
- collapse a sequence of changes into a single commit:: - collapse a sequence of changes into a single commit::
hg rebase --collapse -r 1520:1525 -d . hg rebase --collapse -r 1520:1525 -d .
- move a named branch while preserving its name:: - move a named branch while preserving its name::
hg rebase -r "branch(featureX)" -d 1.3 --keepbranches hg rebase -r "branch(featureX)" -d 1.3 --keepbranches
Configuration Options: Configuration Options:
martinvonzUnsubmitted
Not Done

Will this still be visible even if the config is off?

martinvonz: Will this still be visible even if the config is off?
quarkAuthorUnsubmitted
Not Done

Good catch.

quark: Good catch.
You can make rebase require a destination if you set the following config You can make rebase require a destination if you set the following config
option:: option::
[commands] [commands]
rebase.requiredest = True rebase.requiredest = True
By default, rebase will close the transaction after each commit. For By default, rebase will close the transaction after each commit. For
/| | / /| | /
F G |/ F G |/
K | | -> K K | | -> K
| C D | | C D |
| |/ | | |/ |
| B | ... | B | ...
|/ |/ |/ |/
A A 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 # pick already rebased revs with same dest from state as interesting source
dest = destmap[rev] dest = destmap[rev]
source = [s for s, d in state.items() if d > 0 and destmap[s] == dest] source = [s for s, d in state.items() if d > 0 and destmap[s] == dest]
result = [] result = []
for prev in repo.changelog.parentrevs(rev): for prev in repo.changelog.parentrevs(rev):
adjusted = dest adjusted = dest
if prev != nullrev: if prev != nullrev:
candidate = repo.revs('max(%ld and (::%d))', source, prev).first() candidate = repo.revs('max(%ld and (::%d))', source, prev).first()
if candidate is not None: if candidate is not None:
adjusted = state[candidate] 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) result.append(adjusted)
return result return result
def _checkobsrebase(repo, ui, rebaseobsrevs, rebaseobsskipped): def _checkobsrebase(repo, ui, rebaseobsrevs, rebaseobsskipped):
""" """
Abort if rebase will create divergence or rebase is noop because of markers Abort if rebase will create divergence or rebase is noop because of markers
`rebaseobsrevs`: set of obsolete revision in source `rebaseobsrevs`: set of obsolete revision in source
# C # rebase -r C -d D # C # rebase -r C -d D
# /| # None of A and B will be changed to D and rebase fails. # /| # None of A and B will be changed to D and rebase fails.
# A B D # A B D
if set(newps) == set(oldps) and dest not in newps: if set(newps) == set(oldps) and dest not in newps:
raise error.Abort(_('cannot rebase %d:%s without ' raise error.Abort(_('cannot rebase %d:%s without '
'moving at least one of its parents') 'moving at least one of its parents')
% (rev, repo[rev])) % (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. # "rebasenode" updates to new p1, use the corresponding merge base.
if bases[0] != nullrev: if bases[0] != nullrev:
base = bases[0] base = bases[0]
else: else:
base = None base = None
# Check if the merge will contain unwanted changes. That may happen if # Check if the merge will contain unwanted changes. That may happen if
# there are multiple special (non-changelog ancestor) merge bases, which # there are multiple special (non-changelog ancestor) merge bases, which
bookmarks.activate(repo, activebookmark) bookmarks.activate(repo, activebookmark)
finally: finally:
clearstatus(repo) clearstatus(repo)
clearcollapsemsg(repo) clearcollapsemsg(repo)
repo.ui.warn(_('rebase aborted\n')) repo.ui.warn(_('rebase aborted\n'))
return 0 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): def buildstate(repo, destmap, collapse, obsoletenotrebased):
'''Define which revisions are going to be rebased and where '''Define which revisions are going to be rebased and where
repo: repo repo: repo
destmap: {srcrev: destrev} destmap: {srcrev: destrev}
''' '''
rebaseset = destmap.keys() rebaseset = destmap.keys()
originalwd = repo['.'].rev() originalwd = repo['.'].rev()
_setrebasesetvisibility(repo, set(rebaseset) | {originalwd}) _setrebasesetvisibility(repo, set(rebaseset) | {originalwd})
# This check isn't strictly necessary, since mq detects commits over an # This check isn't strictly necessary, since mq detects commits over an
# applied patch. But it prevents messing up the working directory when # applied patch. But it prevents messing up the working directory when
# a partially completed rebase is blocked by mq. # a partially completed rebase is blocked by mq.
if 'qtip' in repo.tags(): if 'qtip' in repo.tags():
mqapplied = set(repo[s.node].rev() for s in repo.mq.applied) mqapplied = set(repo[s.node].rev() for s in repo.mq.applied)
if set(destmap.values()) & mqapplied: if set(destmap.values()) & mqapplied:
raise error.Abort(_('cannot rebase onto an applied mq patch')) 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: if not roots:
raise error.Abort(_('no matching revisions')) raise error.Abort(_('no matching revisions'))
roots.sort() roots.sort()
state = dict.fromkeys(rebaseset, revtodo) state = dict.fromkeys(rebaseset, revtodo)
emptyrebase = True emptyrebase = (len(sortedsrc) == 1)
for root in roots: for root in roots:
dest = repo[destmap[root.rev()]] dest = repo[destmap[root.rev()]]
commonbase = root.ancestor(dest) commonbase = root.ancestor(dest)
if commonbase == root: if commonbase == root:
raise error.Abort(_('source is ancestor of destination')) raise error.Abort(_('source is ancestor of destination'))
if commonbase == dest: if commonbase == dest:
wctx = repo[None] wctx = repo[None]
if dest == wctx.p1(): if dest == wctx.p1():

tests/test-rebase-dest.t

$ rebasewithdag -s B -d 'SRC' <<'EOS' $ rebasewithdag -s B -d 'SRC' <<'EOS'
> C > C
> | > |
> B > B
> | > |
> Z > Z
> EOS > EOS
abort: source is ancestor of destination abort: source and destination form a cycle
[255] [255]
Switch roots: Switch roots:
$ rebasewithdag -s 'all() - roots(all())' -d 'roots(all()) - ::SRC' <<'EOS' $ rebasewithdag -s 'all() - roots(all())' -d 'roots(all()) - ::SRC' <<'EOS'
> C F > C F
> | | > | |
> B E > B E
o 1: B o 1: B
| |
| o 8: F | o 8: F
|/ |/
| o 2: E | o 2: E
|/ |/
o 0: A 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' $ rebasewithdag -s 'B+C+D' -d 'map(SRC, "B:C,C:D")' <<'EOS'
> B C D > B C D
> \|/ > \|/
> A > A
> EOS > EOS
rebasing 1:112478962961 "B" (B)
rebasing 2:dc0947a82db8 "C" (C) rebasing 2:dc0947a82db8 "C" (C)
o 5: C rebasing 1:112478962961 "B" (B)
o 5: B
|
o 4: C
| |
o 3: D o 3: D
| |
| o 4: B orphan 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: E
| |\
+---o 2: C
| | | |
| x 2: C | o 1: B
|/ |/
o 0: A 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

tests/test-rebase-named-branches.t

| | | |
o | 2: 'dev-one named branch' dev-one o | 2: 'dev-one named branch' dev-one
| | | |
| o 1: 'E' | o 1: 'E'
|/ |/
@ 0: 'A' @ 0: 'A'
$ hg rebase -s 5 -d 6 $ hg rebase -s 5 -d 6
abort: source is ancestor of destination abort: source and destination form a cycle
[255] [255]
$ hg rebase -s 6 -d 5 $ hg rebase -s 6 -d 5
rebasing 6:3944801ae4ea "dev-two named branch" rebasing 6:3944801ae4ea "dev-two named branch"
rebasing 7:3bdb949809d9 "B" rebasing 7:3bdb949809d9 "B"
rebasing 8:a0d543090fa4 "C" rebasing 8:a0d543090fa4 "C"
rebasing 9:e9f862ce8bad "D" (tip) rebasing 9:e9f862ce8bad "D" (tip)
saved backup bundle to $TESTTMP/a1/.hg/strip-backup/3944801ae4ea-fb46ed74-rebase.hg (glob) saved backup bundle to $TESTTMP/a1/.hg/strip-backup/3944801ae4ea-fb46ed74-rebase.hg (glob)

tests/test-rebase-scenario-global.t

$ hg rebase -s 6 -d 5 $ hg rebase -s 6 -d 5
nothing to rebase nothing to rebase
[1] [1]
F onto G - rebase onto a descendant: F onto G - rebase onto a descendant:
$ hg rebase -s 5 -d 6 $ hg rebase -s 5 -d 6
abort: source is ancestor of destination abort: source and destination form a cycle
[255] [255]
G onto B - merge revision with both parents not in ancestors of target: G onto B - merge revision with both parents not in ancestors of target:
$ hg rebase -s 6 -d 1 $ hg rebase -s 6 -d 1
rebasing 6:eea13746799a "G" rebasing 6:eea13746799a "G"
abort: cannot rebase 6:eea13746799a without moving at least one of its parents abort: cannot rebase 6:eea13746799a without moving at least one of its parents
[255] [255]