view tests/test-issue660.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

http://mercurial.selenic.com/bts/issue660 and:
http://mercurial.selenic.com/bts/issue322

  $ hg init
  $ echo a > a
  $ mkdir b
  $ echo b > b/b
  $ hg commit -A -m "a is file, b is dir"
  adding a
  adding b/b

File replaced with directory:

  $ rm a
  $ mkdir a
  $ echo a > a/a

Should fail - would corrupt dirstate:

  $ hg add a/a
  abort: file 'a' in dirstate clashes with 'a/a'
  [255]

Removing shadow:

  $ hg rm --after a

Should succeed - shadow removed:

  $ hg add a/a

Directory replaced with file:

  $ rm -r b
  $ echo b > b

Should fail - would corrupt dirstate:

  $ hg add b
  abort: directory 'b' already in dirstate
  [255]

Removing shadow:

  $ hg rm --after b/b

Should succeed - shadow removed:

  $ hg add b

Look what we got:

  $ hg st
  A a/a
  A b
  R a
  R b/b

Revert reintroducing shadow - should fail:

  $ rm -r a b
  $ hg revert b/b
  abort: file 'b' in dirstate clashes with 'b/b'
  [255]

Revert all - should succeed:

  $ hg revert --all
  undeleting a
  forgetting a/a (glob)
  forgetting b
  undeleting b/b (glob)

  $ hg st

addremove:

  $ rm -r a b
  $ mkdir a
  $ echo a > a/a
  $ echo b > b

  $ hg addremove -s 0
  removing a
  adding a/a
  adding b
  removing b/b

  $ hg st
  A a/a
  A b
  R a
  R b/b

commit:

  $ hg ci -A -m "a is dir, b is file"
  $ hg st --all
  C a/a
  C b

Long directory replaced with file:

  $ mkdir d
  $ mkdir d/d
  $ echo d > d/d/d
  $ hg commit -A -m "d is long directory"
  adding d/d/d

  $ rm -r d
  $ echo d > d

Should fail - would corrupt dirstate:

  $ hg add d
  abort: directory 'd' already in dirstate
  [255]

Removing shadow:

  $ hg rm --after d/d/d

Should succeed - shadow removed:

  $ hg add d
  $ hg ci -md

Update should work at least with clean working directory:

  $ rm -r a b d
  $ hg up -r 0
  2 files updated, 0 files merged, 0 files removed, 0 files unresolved

  $ hg st --all
  C a
  C b/b

  $ rm -r a b
  $ hg up -r 1
  2 files updated, 0 files merged, 0 files removed, 0 files unresolved

  $ hg st --all
  C a/a
  C b