tests/test-rebase-transaction.t

dirstate-tree: Avoid BTreeMap double-lookup when inserting a dirstate entry

The child nodes of a given node in the tree-shaped dirstate are kept in a
`BTreeMap` where keys are file names as strings. Finding or inserting a value
in the map takes `O(log(n))` string comparisons, which adds up when constructing
the tree.

The `entry` API allows finding a "spot" in the map that may or may not be
occupied and then access that value or insert a new one without doing map
lookup again. However the current API is limited in that calling `entry`
requires an owned key (and so a memory allocation), even if it ends up not
being used in the case where the map already has a value with an equal key.

This is still a win, with 4% better end-to-end time for `hg status` measured
here with hyperfine:

```
Benchmark #1: ../hg2/hg status -R $REPO --config=experimental.dirstate-tree.in-memory=1
  Time (mean ± σ):      1.337 s ±  0.018 s    [User: 892.9 ms, System: 437.5 ms]
  Range (min … max):    1.316 s …  1.373 s    10 runs

Benchmark #2: ./hg status -R $REPO --config=experimental.dirstate-tree.in-memory=1
  Time (mean ± σ):      1.291 s ±  0.008 s    [User: 853.4 ms, System: 431.1 ms]
  Range (min … max):    1.283 s …  1.309 s    10 runs

Summary
  './hg status -R $REPO --config=experimental.dirstate-tree.in-memory=1' ran
    1.04 ± 0.02 times faster than '../hg2/hg status -R $REPO --config=experimental.dirstate-tree.in-memory=1'
```

* ./hg is this revision
* ../hg2/hg is its parent
* $REPO is an old snapshot of mozilla-central

Differential Revision: https://phab.mercurial-scm.org/D10550

#testcases continuecommand continueflag
Rebasing using a single transaction

  $ cat >> $HGRCPATH <<EOF
  > [extensions]
  > rebase=
  > drawdag=$TESTDIR/drawdag.py
  > 
  > [rebase]
  > singletransaction=True
  > 
  > [phases]
  > publish=False
  > 
  > [alias]
  > tglog = log -G --template "{rev}: {desc}"
  > EOF

#if continueflag
  $ cat >> $HGRCPATH <<EOF
  > [alias]
  > continue = rebase --continue
  > EOF
#endif

Check that a simple rebase works

  $ hg init simple && cd simple
  $ hg debugdrawdag <<'EOF'
  >   Z
  >   |
  >   | D
  >   | |
  >   | C
  >   | |
  >   Y B
  >   |/
  >   A
  > EOF
- We should only see one status stored message. It comes from the start.
  $ hg rebase --debug -b D -d Z | grep 'status stored'
  rebase status stored
  $ hg tglog
  o  5: D
  |
  o  4: C
  |
  o  3: B
  |
  o  2: Z
  |
  o  1: Y
  |
  o  0: A
  
  $ cd ..

Check that --collapse works

  $ hg init collapse && cd collapse
  $ hg debugdrawdag <<'EOF'
  >   Z
  >   |
  >   | D
  >   | |
  >   | C
  >   | |
  >   Y B
  >   |/
  >   A
  > EOF
- We should only see two status stored messages. One from the start, one from
- cmdutil.commitforceeditor() which forces tr.writepending()
  $ hg rebase --collapse --debug -b D -d Z | grep 'status stored'
  rebase status stored
  rebase status stored
  $ hg tglog
  o  3: Collapsed revision
  |  * B
  |  * C
  |  * D
  o  2: Z
  |
  o  1: Y
  |
  o  0: A
  
  $ cd ..

With --collapse, check that conflicts can be resolved and rebase can then be
continued

  $ hg init collapse-conflict && cd collapse-conflict
  $ hg debugdrawdag <<'EOF'
  >   Z   # Z/conflict=Z
  >   |
  >   | D
  >   | |
  >   | C # C/conflict=C
  >   | |
  >   Y B
  >   |/
  >   A
  > EOF
  $ hg rebase --collapse -b D -d Z
  rebasing 1:112478962961 B "B"
  rebasing 3:c26739dbe603 C "C"
  merging conflict
  warning: conflicts while merging conflict! (edit, then use 'hg resolve --mark')
  unresolved conflicts (see 'hg resolve', then 'hg rebase --continue')
  [240]
  $ hg tglog
  o  5: D
  |
  | @  4: Z
  | |
  % |  3: C
  | |
  | o  2: Y
  | |
  o |  1: B
  |/
  o  0: A
  
  $ hg st
  M conflict
  A B
  A C
  ? conflict.orig
  $ echo resolved > conflict
  $ hg resolve -m
  (no more unresolved files)
  continue: hg rebase --continue
  $ hg continue
  already rebased 1:112478962961 B "B" as 79bc8f4973ce
  rebasing 3:c26739dbe603 C "C"
  rebasing 5:d24bb333861c D tip "D"
  saved backup bundle to $TESTTMP/collapse-conflict/.hg/strip-backup/112478962961-b5b34645-rebase.hg
  $ hg tglog
  o  3: Collapsed revision
  |  * B
  |  * C
  |  * D
  o  2: Z
  |
  o  1: Y
  |
  o  0: A
  
  $ cd ..

With --collapse, check that the commit message editing can be canceled and
rebase can then be continued

  $ hg init collapse-cancel-editor && cd collapse-cancel-editor
  $ hg debugdrawdag <<'EOF'
  >   Z
  >   |
  >   | D
  >   | |
  >   | C
  >   | |
  >   Y B
  >   |/
  >   A
  > EOF
  $ HGEDITOR=false hg --config ui.interactive=1 rebase --collapse -b D -d Z
  rebasing 1:112478962961 B "B"
  rebasing 3:26805aba1e60 C "C"
  rebasing 5:f585351a92f8 D tip "D"
  transaction abort!
  rollback completed
  abort: edit failed: false exited with status 1
  [250]
  $ hg tglog
  o  5: D
  |
  | o  4: Z
  | |
  o |  3: C
  | |
  | o  2: Y
  | |
  o |  1: B
  |/
  o  0: A
  
  $ hg continue
  rebasing 1:112478962961 B "B"
  rebasing 3:26805aba1e60 C "C"
  rebasing 5:f585351a92f8 D tip "D"
  saved backup bundle to $TESTTMP/collapse-cancel-editor/.hg/strip-backup/112478962961-cb2a9b47-rebase.hg
  $ hg tglog
  o  3: Collapsed revision
  |  * B
  |  * C
  |  * D
  o  2: Z
  |
  o  1: Y
  |
  o  0: A
  
  $ cd ..