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

Simple commands:

  $ echo foo
  foo
  $ printf 'oh no'
  oh no (no-eol)
  $ printf 'bar\nbaz\n' | cat
  bar
  baz

Multi-line command:

  $ foo() {
  >     echo bar
  > }
  $ foo
  bar

Return codes before inline python:

  $ sh -c 'exit 1'
  [1]

Doctest commands:

  >>> print 'foo'
  foo
  $ echo interleaved
  interleaved
  >>> for c in 'xyz':
  ...     print c
  x
  y
  z
  >>> print
  

Regular expressions:

  $ echo foobarbaz
  foobar.* (re)
  $ echo barbazquux
  .*quux.* (re)

Globs:

  $ printf '* \\foobarbaz {10}\n'
  \* \\fo?bar* {10} (glob)

Literal match ending in " (re)":

  $ echo 'foo (re)'
  foo (re)

Windows: \r\n is handled like \n and can be escaped:

#if windows
  $ printf 'crlf\r\ncr\r\tcrlf\r\ncrlf\r\n'
  crlf
  cr\r (no-eol) (esc)
  \tcrlf (esc)
  crlf\r (esc)
#endif

Combining esc with other markups - and handling lines ending with \r instead of \n:

  $ printf 'foo/bar\r'
  foo/bar\r (no-eol) (glob) (esc)
#if windows
  $ printf 'foo\\bar\r'
  foo/bar\r (no-eol) (glob) (esc)
#endif
  $ printf 'foo/bar\rfoo/bar\r'
  foo.bar\r \(no-eol\) (re) (esc)
  foo.bar\r \(no-eol\) (re)

testing hghave

  $ "$TESTDIR/hghave" true
  $ "$TESTDIR/hghave" false
  skipped: missing feature: nail clipper
  [1]
  $ "$TESTDIR/hghave" no-true
  skipped: system supports yak shaving
  [1]
  $ "$TESTDIR/hghave" no-false

Conditional sections based on hghave:

#if true
  $ echo tested
  tested
#else
  $ echo skipped
#endif

#if false
  $ echo skipped
#else
  $ echo tested
  tested
#endif

#if no-false
  $ echo tested
  tested
#else
  $ echo skipped
#endif

#if no-true
  $ echo skipped
#else
  $ echo tested
  tested
#endif

Exit code:

  $ (exit 1)
  [1]