dirstate: Remove the flat Rust DirstateMap implementation Before this changeset we had two Rust implementations of `DirstateMap`. This removes the "flat" DirstateMap so that the "tree" DirstateMap is always used when Rust enabled. This simplifies the code a lot, and will enable (in the next changeset) further removal of a trait abstraction. This is a performance regression when: * Rust is enabled, and * The repository uses the legacy dirstate-v1 file format, and * For `hg status`, unknown files are not listed (such as with `-mard`) The regression is about 100 milliseconds for `hg status -mard` on a semi-large repository (mozilla-central), from ~320ms to ~420ms. We deem this to be small enough to be worth it. The new dirstate-v2 is still experimental at this point, but we aim to stabilize it (though not yet enable it by default for new repositories) in Mercurial 6.0. Eventually, upgrating repositories to dirsate-v2 will eliminate this regression (and enable other performance improvements). # Background The flat DirstateMap was introduced with the first Rust implementation of the status algorithm. It works similarly to the previous Python + C one, with a single `HashMap` that associates file paths to a `DirstateEntry` (where Python has a dict). We later added the tree DirstateMap where the root of the tree contains nodes for files and directories that are directly at the root of the repository, and nodes for directories can contain child nodes representing the files and directly that *they* contain directly. The shape of this tree mirrors that of the working directory in the filesystem. This enables the status algorithm to traverse this tree in tandem with traversing the filesystem tree, which in turns enables a more efficient algorithm. Furthermore, the new dirstate-v2 file format is also based on a tree of the same shape. The tree DirstateMap can access a dirstate-v2 file without parsing it: binary data in a single large (possibly memory-mapped) bytes buffer is traversed on demand. This allows `DirstateMap` creation to take `O(1)` time. (Mutation works by creating new in-memory nodes with copy-on-write semantics, and serialization is append-mostly.) The tradeoff is that for "legacy" repositories that use the dirstate-v1 file format, parsing that file into a tree DirstateMap takes more time. Profiling shows that this time is dominated by `HashMap`. For a dirstate containing `F` files with an average `D` directory depth, the flat DirstateMap does parsing in `O(F)` number of HashMap operations but the tree DirstateMap in `O(F × D)` operations, since each node has its own HashMap containing its child nodes. This slower costs ~140ms on an old snapshot of mozilla-central, and ~80ms on an old snapshot of the Netbeans repository. The status algorithm is faster, but with `-mard` (when not listing unknown files) it is typically not faster *enough* to compensate the slower parsing. Both Rust implementations are always faster than the Python + C implementation # Benchmark results All benchmarks are run on changeset 98c0408324e6, with repositories that use the dirstate-v1 file format, on a server with 4 CPU cores and 4 CPU threads (no HyperThreading). `hg status` benchmarks show wall clock times of the entire command as the average and standard deviation of serveral runs, collected by https://github.com/sharkdp/hyperfine and reformated. Parsing benchmarks are wall clock time of the Rust function that converts a bytes buffer of the dirstate file into the `DirstateMap` data structure as used by the status algorithm. A single run each, collected by running `hg status` this environment variable: RUST_LOG=hg::dirstate::dirstate_map=trace,hg::dirstate_tree::dirstate_map=trace Benchmark 1: Rust flat DirstateMap → Rust tree DirstateMap hg status mozilla-clean 562.3 ms ± 2.0 ms → 462.5 ms ± 0.6 ms 1.22 ± 0.00 times faster mozilla-dirty 859.6 ms ± 2.2 ms → 719.5 ms ± 3.2 ms 1.19 ± 0.01 times faster mozilla-ignored 558.2 ms ± 3.0 ms → 457.9 ms ± 2.9 ms 1.22 ± 0.01 times faster mozilla-unknowns 859.4 ms ± 5.7 ms → 716.0 ms ± 4.7 ms 1.20 ± 0.01 times faster netbeans-clean 336.5 ms ± 0.9 ms → 339.5 ms ± 0.4 ms 0.99 ± 0.00 times faster netbeans-dirty 491.4 ms ± 1.6 ms → 475.1 ms ± 1.2 ms 1.03 ± 0.00 times faster netbeans-ignored 343.7 ms ± 1.0 ms → 347.8 ms ± 0.4 ms 0.99 ± 0.00 times faster netbeans-unknowns 484.3 ms ± 1.0 ms → 466.0 ms ± 1.2 ms 1.04 ± 0.00 times faster hg status -mard mozilla-clean 317.3 ms ± 0.6 ms → 422.5 ms ± 1.2 ms 0.75 ± 0.00 times faster mozilla-dirty 315.4 ms ± 0.6 ms → 417.7 ms ± 1.1 ms 0.76 ± 0.00 times faster mozilla-ignored 314.6 ms ± 0.6 ms → 417.4 ms ± 1.0 ms 0.75 ± 0.00 times faster mozilla-unknowns 312.9 ms ± 0.9 ms → 417.3 ms ± 1.6 ms 0.75 ± 0.00 times faster netbeans-clean 212.0 ms ± 0.6 ms → 283.6 ms ± 0.8 ms 0.75 ± 0.00 times faster netbeans-dirty 211.4 ms ± 1.0 ms → 283.4 ms ± 1.6 ms 0.75 ± 0.01 times faster netbeans-ignored 211.4 ms ± 0.9 ms → 283.9 ms ± 0.8 ms 0.74 ± 0.01 times faster netbeans-unknowns 211.1 ms ± 0.6 ms → 283.4 ms ± 1.0 ms 0.74 ± 0.00 times faster Parsing mozilla-clean 38.4ms → 177.6ms mozilla-dirty 38.8ms → 177.0ms mozilla-ignored 38.8ms → 178.0ms mozilla-unknowns 38.7ms → 176.9ms netbeans-clean 16.5ms → 97.3ms netbeans-dirty 16.5ms → 98.4ms netbeans-ignored 16.9ms → 97.4ms netbeans-unknowns 16.9ms → 96.3ms Benchmark 2: Python + C dirstatemap → Rust tree DirstateMap hg status mozilla-clean 1261.0 ms ± 3.6 ms → 461.1 ms ± 0.5 ms 2.73 ± 0.00 times faster mozilla-dirty 2293.4 ms ± 9.1 ms → 719.6 ms ± 3.6 ms 3.19 ± 0.01 times faster mozilla-ignored 1240.4 ms ± 2.3 ms → 457.7 ms ± 1.9 ms 2.71 ± 0.00 times faster mozilla-unknowns 2283.3 ms ± 9.0 ms → 719.7 ms ± 3.8 ms 3.17 ± 0.01 times faster netbeans-clean 879.7 ms ± 3.5 ms → 339.9 ms ± 0.5 ms 2.59 ± 0.00 times faster netbeans-dirty 1257.3 ms ± 4.7 ms → 474.6 ms ± 1.6 ms 2.65 ± 0.01 times faster netbeans-ignored 943.9 ms ± 1.9 ms → 347.3 ms ± 1.1 ms 2.72 ± 0.00 times faster netbeans-unknowns 1188.1 ms ± 5.0 ms → 465.2 ms ± 2.3 ms 2.55 ± 0.01 times faster hg status -mard mozilla-clean 903.2 ms ± 3.6 ms → 423.4 ms ± 2.2 ms 2.13 ± 0.01 times faster mozilla-dirty 884.6 ms ± 4.5 ms → 417.3 ms ± 1.4 ms 2.12 ± 0.01 times faster mozilla-ignored 881.9 ms ± 1.3 ms → 417.3 ms ± 0.8 ms 2.11 ± 0.00 times faster mozilla-unknowns 878.5 ms ± 1.9 ms → 416.4 ms ± 0.9 ms 2.11 ± 0.00 times faster netbeans-clean 434.9 ms ± 1.8 ms → 284.0 ms ± 0.8 ms 1.53 ± 0.01 times faster netbeans-dirty 434.1 ms ± 0.8 ms → 283.1 ms ± 0.8 ms 1.53 ± 0.00 times faster netbeans-ignored 431.7 ms ± 1.1 ms → 283.6 ms ± 1.8 ms 1.52 ± 0.01 times faster netbeans-unknowns 433.0 ms ± 1.3 ms → 283.5 ms ± 0.7 ms 1.53 ± 0.00 times faster Differential Revision: https://phab.mercurial-scm.org/D11516

     1

#testcases dirstate-v1 dirstate-v2

     2

     3

#if no-rust

     4

  $ hg init repo0 --config format.exp-dirstate-v2=1

     5

  abort: dirstate v2 format requested by config but not supported (requires Rust extensions)

     6

  [255]

     7

#endif

     8

     9

#if dirstate-v2

    10

#require rust

    11

  $ echo '[format]' >> $HGRCPATH

    12

  $ echo 'exp-dirstate-v2=1' >> $HGRCPATH

    13

#endif

    14

    15

  $ hg init repo1

    16

  $ cd repo1

    17

  $ mkdir a b a/1 b/1 b/2

    18

  $ touch in_root a/in_a b/in_b a/1/in_a_1 b/1/in_b_1 b/2/in_b_2

    19

    20

hg status in repo root:

    21

    22

  $ hg status

    23

  ? a/1/in_a_1

    24

  ? a/in_a

    25

  ? b/1/in_b_1

    26

  ? b/2/in_b_2

    27

  ? b/in_b

    28

  ? in_root

    29

    30

hg status . in repo root:

    31

    32

  $ hg status .

    33

  ? a/1/in_a_1

    34

  ? a/in_a

    35

  ? b/1/in_b_1

    36

  ? b/2/in_b_2

    37

  ? b/in_b

    38

  ? in_root

    39

    40

  $ hg status --cwd a

    41

  ? a/1/in_a_1

    42

  ? a/in_a

    43

  ? b/1/in_b_1

    44

  ? b/2/in_b_2

    45

  ? b/in_b

    46

  ? in_root

    47

  $ hg status --cwd a .

    48

  ? 1/in_a_1

    49

  ? in_a

    50

  $ hg status --cwd a ..

    51

  ? 1/in_a_1

    52

  ? in_a

    53

  ? ../b/1/in_b_1

    54

  ? ../b/2/in_b_2

    55

  ? ../b/in_b

    56

  ? ../in_root

    57

    58

  $ hg status --cwd b

    59

  ? a/1/in_a_1

    60

  ? a/in_a

    61

  ? b/1/in_b_1

    62

  ? b/2/in_b_2

    63

  ? b/in_b

    64

  ? in_root

    65

  $ hg status --cwd b .

    66

  ? 1/in_b_1

    67

  ? 2/in_b_2

    68

  ? in_b

    69

  $ hg status --cwd b ..

    70

  ? ../a/1/in_a_1

    71

  ? ../a/in_a

    72

  ? 1/in_b_1

    73

  ? 2/in_b_2

    74

  ? in_b

    75

  ? ../in_root

    76

    77

  $ hg status --cwd a/1

    78

  ? a/1/in_a_1

    79

  ? a/in_a

    80

  ? b/1/in_b_1

    81

  ? b/2/in_b_2

    82

  ? b/in_b

    83

  ? in_root

    84

  $ hg status --cwd a/1 .

    85

  ? in_a_1

    86

  $ hg status --cwd a/1 ..

    87

  ? in_a_1

    88

  ? ../in_a

    89

    90

  $ hg status --cwd b/1

    91

  ? a/1/in_a_1

    92

  ? a/in_a

    93

  ? b/1/in_b_1

    94

  ? b/2/in_b_2

    95

  ? b/in_b

    96

  ? in_root

    97

  $ hg status --cwd b/1 .

    98

  ? in_b_1

    99

  $ hg status --cwd b/1 ..

   100

  ? in_b_1

   101

  ? ../2/in_b_2

   102

  ? ../in_b

   103

   104

  $ hg status --cwd b/2

   105

  ? a/1/in_a_1

   106

  ? a/in_a

   107

  ? b/1/in_b_1

   108

  ? b/2/in_b_2

   109

  ? b/in_b

   110

  ? in_root

   111

  $ hg status --cwd b/2 .

   112

  ? in_b_2

   113

  $ hg status --cwd b/2 ..

   114

  ? ../1/in_b_1

   115

  ? in_b_2

   116

  ? ../in_b

   117

   118

combining patterns with root and patterns without a root works

   119

   120

  $ hg st a/in_a re:.*b$

   121

  ? a/in_a

   122

  ? b/in_b

   123

   124

tweaking defaults works

   125

  $ hg status --cwd a --config ui.tweakdefaults=yes

   126

  ? 1/in_a_1

   127

  ? in_a

   128

  ? ../b/1/in_b_1

   129

  ? ../b/2/in_b_2

   130

  ? ../b/in_b

   131

  ? ../in_root

   132

  $ HGPLAIN=1 hg status --cwd a --config ui.tweakdefaults=yes

   133

  ? a/1/in_a_1 (glob)

   134

  ? a/in_a (glob)

   135

  ? b/1/in_b_1 (glob)

   136

  ? b/2/in_b_2 (glob)

   137

  ? b/in_b (glob)

   138

  ? in_root

   139

  $ HGPLAINEXCEPT=tweakdefaults hg status --cwd a --config ui.tweakdefaults=yes

   140

  ? 1/in_a_1

   141

  ? in_a

   142

  ? ../b/1/in_b_1

   143

  ? ../b/2/in_b_2

   144

  ? ../b/in_b

   145

  ? ../in_root (glob)

   146

   147

relative paths can be requested

   148

   149

  $ hg status --cwd a --config ui.relative-paths=yes

   150

  ? 1/in_a_1

   151

  ? in_a

   152

  ? ../b/1/in_b_1

   153

  ? ../b/2/in_b_2

   154

  ? ../b/in_b

   155

  ? ../in_root

   156

   157

  $ hg status --cwd a . --config ui.relative-paths=legacy

   158

  ? 1/in_a_1

   159

  ? in_a

   160

  $ hg status --cwd a . --config ui.relative-paths=no

   161

  ? a/1/in_a_1

   162

  ? a/in_a

   163

   164

commands.status.relative overrides ui.relative-paths

   165

   166

  $ cat >> $HGRCPATH <<EOF

   167

  > [ui]

   168

  > relative-paths = False

   169

  > [commands]

   170

  > status.relative = True

   171

  > EOF

   172

  $ hg status --cwd a

   173

  ? 1/in_a_1

   174

  ? in_a

   175

  ? ../b/1/in_b_1

   176

  ? ../b/2/in_b_2

   177

  ? ../b/in_b

   178

  ? ../in_root

   179

  $ HGPLAIN=1 hg status --cwd a

   180

  ? a/1/in_a_1 (glob)

   181

  ? a/in_a (glob)

   182

  ? b/1/in_b_1 (glob)

   183

  ? b/2/in_b_2 (glob)

   184

  ? b/in_b (glob)

   185

  ? in_root

   186

   187

if relative paths are explicitly off, tweakdefaults doesn't change it

   188

  $ cat >> $HGRCPATH <<EOF

   189

  > [commands]

   190

  > status.relative = False

   191

  > EOF

   192

  $ hg status --cwd a --config ui.tweakdefaults=yes

   193

  ? a/1/in_a_1

   194

  ? a/in_a

   195

  ? b/1/in_b_1

   196

  ? b/2/in_b_2

   197

  ? b/in_b

   198

  ? in_root

   199

   200

  $ cd ..

   201

   202

  $ hg init repo2

   203

  $ cd repo2

   204

  $ touch modified removed deleted ignored

   205

  $ echo "^ignored$" > .hgignore

   206

  $ hg ci -A -m 'initial checkin'

   207

  adding .hgignore

   208

  adding deleted

   209

  adding modified

   210

  adding removed

   211

  $ touch modified added unknown ignored

   212

  $ hg add added

   213

  $ hg remove removed

   214

  $ rm deleted

   215

   216

hg status:

   217

   218

  $ hg status

   219

  A added

   220

  R removed

   221

  ! deleted

   222

  ? unknown

   223

   224

hg status modified added removed deleted unknown never-existed ignored:

   225

   226

  $ hg status modified added removed deleted unknown never-existed ignored

   227

  never-existed: * (glob)

   228

  A added

   229

  R removed

   230

  ! deleted

   231

  ? unknown

   232

   233

  $ hg copy modified copied

   234

   235

hg status -C:

   236

   237

  $ hg status -C

   238

  A added

   239

  A copied

   240

    modified

   241

  R removed

   242

  ! deleted

   243

  ? unknown

   244

   245

hg status -A:

   246

   247

  $ hg status -A

   248

  A added

   249

  A copied

   250

    modified

   251

  R removed

   252

  ! deleted

   253

  ? unknown

   254

  I ignored

   255

  C .hgignore

   256

  C modified

   257

   258

  $ hg status -A -T '{status} {path} {node|shortest}\n'

   259

  A added ffff

   260

  A copied ffff

   261

  R removed ffff

   262

  ! deleted ffff

   263

  ? unknown ffff

   264

  I ignored ffff

   265

  C .hgignore ffff

   266

  C modified ffff

   267

   268

  $ hg status -A -Tjson

   269

  [

   270

   {

   271

    "itemtype": "file",

   272

    "path": "added",

   273

    "status": "A"

   274

   },

   275

   {

   276

    "itemtype": "file",

   277

    "path": "copied",

   278

    "source": "modified",

   279

    "status": "A"

   280

   },

   281

   {

   282

    "itemtype": "file",

   283

    "path": "removed",

   284

    "status": "R"

   285

   },

   286

   {

   287

    "itemtype": "file",

   288

    "path": "deleted",

   289

    "status": "!"

   290

   },

   291

   {

   292

    "itemtype": "file",

   293

    "path": "unknown",

   294

    "status": "?"

   295

   },

   296

   {

   297

    "itemtype": "file",

   298

    "path": "ignored",

   299

    "status": "I"

   300

   },

   301

   {

   302

    "itemtype": "file",

   303

    "path": ".hgignore",

   304

    "status": "C"

   305

   },

   306

   {

   307

    "itemtype": "file",

   308

    "path": "modified",

   309

    "status": "C"

   310

   }

   311

  ]

   312

   313

  $ hg status -A -Tpickle > pickle

   314

  >>> from __future__ import print_function

   315

  >>> from mercurial import util

   316

  >>> pickle = util.pickle

   317

  >>> data = sorted((x[b'status'].decode(), x[b'path'].decode()) for x in pickle.load(open("pickle", r"rb")))

   318

  >>> for s, p in data: print("%s %s" % (s, p))

   319

  ! deleted

   320

  ? pickle

   321

  ? unknown

   322

  A added

   323

  A copied

   324

  C .hgignore

   325

  C modified

   326

  I ignored

   327

  R removed

   328

  $ rm pickle

   329

   330

  $ echo "^ignoreddir$" > .hgignore

   331

  $ mkdir ignoreddir

   332

  $ touch ignoreddir/file

   333

   334

Test templater support:

   335

   336

  $ hg status -AT "[{status}]\t{if(source, '{source} -> ')}{path}\n"

   337

  [M]	.hgignore

   338

  [A]	added

   339

  [A]	modified -> copied

   340

  [R]	removed

   341

  [!]	deleted

   342

  [?]	ignored

   343

  [?]	unknown

   344

  [I]	ignoreddir/file

   345

  [C]	modified

   346

  $ hg status -AT default

   347

  M .hgignore

   348

  A added

   349

  A copied

   350

    modified

   351

  R removed

   352

  ! deleted

   353

  ? ignored

   354

  ? unknown

   355

  I ignoreddir/file

   356

  C modified

   357

  $ hg status -T compact

   358

  abort: "status" not in template map

   359

  [255]

   360

   361

hg status ignoreddir/file:

   362

   363

  $ hg status ignoreddir/file

   364

   365

hg status -i ignoreddir/file:

   366

   367

  $ hg status -i ignoreddir/file

   368

  I ignoreddir/file

   369

  $ cd ..

   370

   371

Check 'status -q' and some combinations

   372

   373

  $ hg init repo3

   374

  $ cd repo3

   375

  $ touch modified removed deleted ignored

   376

  $ echo "^ignored$" > .hgignore

   377

  $ hg commit -A -m 'initial checkin'

   378

  adding .hgignore

   379

  adding deleted

   380

  adding modified

   381

  adding removed

   382

  $ touch added unknown ignored

   383

  $ hg add added

   384

  $ echo "test" >> modified

   385

  $ hg remove removed

   386

  $ rm deleted

   387

  $ hg copy modified copied

   388

   389

Specify working directory revision explicitly, that should be the same as

   390

"hg status"

   391

   392

  $ hg status --change "wdir()"

   393

  M modified

   394

  A added

   395

  A copied

   396

  R removed

   397

  ! deleted

   398

  ? unknown

   399

   400

Run status with 2 different flags.

   401

Check if result is the same or different.

   402

If result is not as expected, raise error

   403

   404

  $ assert() {