view tests/test-mq-qqueue.t @ 17970:0b03454abae7

ancestor: faster algorithm for difference of ancestor sets

One of the major reasons rebase is slow in large repositories is
the computation of the detach set: the set of ancestors of the
changesets to rebase not in the destination parent. This is currently
done via a revset that does two walks all the way to the root of
the DAG. Instead of doing that, to find ancestors of a set <revs>
not in another set <common> we walk up the tree in reverse revision
number order, maintaining sets of nodes visited from <revs>, <common>
or both.

For the common case where the sets are close both topologically and
in revision number (relative to repository size), this has been
found to speed up rebase by around 15-20%. When the nodes are farther
apart and the DAG is highly branching, it is harder to say which
would win.

Here's how long computing the detach set takes in a linear repository
with over 400000 changesets, rebasing near tip:

Rebasing across 4 changesets
Revset method: 2.2s
New algorithm: 0.00015s

Rebasing across 250 changesets
Revset method: 2.2s
New algorithm: 0.00069s

Rebasing across 10000 changesets
Revset method: 2.4s
New algorithm: 0.019s

  $ echo "[extensions]" >> $HGRCPATH
  $ echo "mq=" >> $HGRCPATH

  $ hg init foo
  $ cd foo
  $ echo a > a
  $ hg ci -qAm a

Default queue:

  $ hg qqueue
  patches (active)

  $ echo b > a
  $ hg qnew -fgDU somestuff

Applied patches in default queue:

  $ hg qap
  somestuff

Try to change patch (create succeeds, switch fails):

  $ hg qqueue foo --create
  abort: new queue created, but cannot make active as patches are applied
  [255]

  $ hg qqueue
  foo
  patches (active)

Empty default queue:

  $ hg qpop
  popping somestuff
  patch queue now empty

Switch queue:

  $ hg qqueue foo
  $ hg qqueue
  foo (active)
  patches

List queues, quiet:

  $ hg qqueue --quiet
  foo
  patches

Fail creating queue with already existing name:

  $ hg qqueue --create foo
  abort: queue "foo" already exists
  [255]

  $ hg qqueue
  foo (active)
  patches

Create new queue for rename:

  $ hg qqueue --create bar

  $ hg qqueue
  bar (active)
  foo
  patches

Rename queue, same name:

  $ hg qqueue --rename bar
  abort: can't rename "bar" to its current name
  [255]

Rename queue to existing:

  $ hg qqueue --rename foo
  abort: queue "foo" already exists
  [255]

Rename queue:

  $ hg qqueue --rename buz

  $ hg qqueue
  buz (active)
  foo
  patches

Switch back to previous queue:

  $ hg qqueue foo
  $ hg qqueue --delete buz

  $ hg qqueue
  foo (active)
  patches

Create queue for purge:

  $ hg qqueue --create purge-me

  $ hg qqueue
  foo
  patches
  purge-me (active)

Create patch for purge:

  $ hg qnew patch-purge-me

  $ ls -1d .hg/patches-purge-me 2>/dev/null || true
  .hg/patches-purge-me

  $ hg qpop -a
  popping patch-purge-me
  patch queue now empty

Purge queue:

  $ hg qqueue foo
  $ hg qqueue --purge purge-me

  $ hg qqueue
  foo (active)
  patches

  $ ls -1d .hg/patches-purge-me 2>/dev/null || true

Unapplied patches:

  $ hg qun
  $ echo c > a
  $ hg qnew -fgDU otherstuff

Fail switching back:

  $ hg qqueue patches
  abort: new queue created, but cannot make active as patches are applied
  [255]

Fail deleting current:

  $ hg qqueue foo --delete
  abort: cannot delete currently active queue
  [255]

Switch back and delete foo:

  $ hg qpop -a
  popping otherstuff
  patch queue now empty

  $ hg qqueue patches
  $ hg qqueue foo --delete
  $ hg qqueue
  patches (active)

Tricky cases:

  $ hg qqueue store --create
  $ hg qnew journal

  $ hg qqueue
  patches
  store (active)

  $ hg qpop -a
  popping journal
  patch queue now empty

  $ hg qqueue patches
  $ hg qun
  somestuff

Invalid names:

  $ hg qqueue test/../../bar --create
  abort: invalid queue name, may not contain the characters ":\/."
  [255]

  $ hg qqueue . --create
  abort: invalid queue name, may not contain the characters ":\/."
  [255]

  $ cd ..