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

  $ hg init
  $ echo a > a
  $ hg commit -A -ma
  adding a

  $ echo b >> a
  $ hg commit -mb

  $ echo c >> a
  $ hg commit -mc

  $ hg up 1
  1 files updated, 0 files merged, 0 files removed, 0 files unresolved
  $ echo d >> a
  $ hg commit -md
  created new head

  $ hg up 1
  1 files updated, 0 files merged, 0 files removed, 0 files unresolved
  $ echo e >> a
  $ hg commit -me
  created new head

  $ hg up 1
  1 files updated, 0 files merged, 0 files removed, 0 files unresolved

Should fail because not at a head:

  $ hg merge
  abort: branch 'default' has 3 heads - please merge with an explicit rev
  (run 'hg heads .' to see heads)
  [255]

  $ hg up
  1 files updated, 0 files merged, 0 files removed, 0 files unresolved

Should fail because > 2 heads:

  $ HGMERGE=internal:other; export HGMERGE
  $ hg merge
  abort: branch 'default' has 3 heads - please merge with an explicit rev
  (run 'hg heads .' to see heads)
  [255]

Should succeed:

  $ hg merge 2
  0 files updated, 1 files merged, 0 files removed, 0 files unresolved
  (branch merge, don't forget to commit)
  $ hg commit -mm1

Should succeed - 2 heads:

  $ hg merge -P
  changeset:   3:ea9ff125ff88
  parent:      1:1846eede8b68
  user:        test
  date:        Thu Jan 01 00:00:00 1970 +0000
  summary:     d
  
  $ hg merge
  0 files updated, 1 files merged, 0 files removed, 0 files unresolved
  (branch merge, don't forget to commit)
  $ hg commit -mm2

Should fail because at tip:

  $ hg merge
  abort: nothing to merge
  [255]

  $ hg up 0
  1 files updated, 0 files merged, 0 files removed, 0 files unresolved

Should fail because there is only one head:

  $ hg merge
  abort: nothing to merge
  (use 'hg update' instead)
  [255]

  $ hg up 3
  1 files updated, 0 files merged, 0 files removed, 0 files unresolved

  $ echo f >> a
  $ hg branch foobranch
  marked working directory as branch foobranch
  (branches are permanent and global, did you want a bookmark?)
  $ hg commit -mf

Should fail because merge with other branch:

  $ hg merge
  abort: branch 'foobranch' has one head - please merge with an explicit rev
  (run 'hg heads' to see all heads)
  [255]


Test for issue2043: ensure that 'merge -P' shows ancestors of 6 that
are not ancestors of 7, regardless of where their least common
ancestor is.

Merge preview not affected by common ancestor:

  $ hg up -q 7
  $ hg merge -q -P 6
  2:2d95304fed5d
  4:f25cbe84d8b3
  5:a431fabd6039
  6:e88e33f3bf62