view tests/test-issue5979.t @ 45562:b51167d70f5a

rust: add `dirstate_tree` module

Mercurial needs to represent the filesystem hierarchy on which it operates, for
example in the dirstate. Its current on-disk representation is an unsorted, flat
structure that gets transformed in the current Rust code into a `HashMap`.
This loses the hierarchical information of the dirstate, leading to some
unfortunate performance and algorithmic compromises.

This module adds an implementation of a radix tree that is specialized for
representing the dirstate: its unit is the path component. I have made no
efforts to optimize either its memory footprint or its insertion speed: they're
pretty bad for now.

Following will be a few patches that modify the dirstate.status logic to use
that new hierarchical information, fixing issue 6335 in the same swing.

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

  $ hg init r1
  $ cd r1
  $ hg ci --config ui.allowemptycommit=true -m c0
  $ hg ci --config ui.allowemptycommit=true -m c1
  $ hg ci --config ui.allowemptycommit=true -m c2
  $ hg co -q 0
  $ hg ci --config ui.allowemptycommit=true -m c3
  created new head
  $ hg co -q 3
  $ hg merge --quiet
  $ hg ci --config ui.allowemptycommit=true -m c4

  $ hg log -G -T'{desc}'
  @    c4
  |\
  | o  c3
  | |
  o |  c2
  | |
  o |  c1
  |/
  o  c0
  

  >>> from mercurial import hg
  >>> from mercurial import ui as uimod
  >>> repo = hg.repository(uimod.ui())
  >>> for anc in repo.changelog.ancestors([4], inclusive=True):
  ...   print(anc)
  4
  3
  2
  1
  0