rust-performance: introduce FastHashMap type alias for HashMap

Rust's default hashing is slow, because it is meant for preventing collision
attacks.
For all of the current Rust code, we don't care about those attacks, because
if an person with bad intentions has write access to your repo, you have other
issues.

I've chosen to use the TwoXHash crate because it was made by a reputable member
of the Rust community and has very good benchmarks.

For now it does not seem to improve performance by much for the current code,
but it's something else to not worry about when benchmarking code: in a
previous experiment with copytracing in Rust, it accounted for more than 10%
of the time of the entire script.

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

rust/Cargo.lock

@@ -1,440 +1,524
 # This file is automatically @generated by Cargo.
 # It is not intended for manual editing.
 [[package]]
 name = "aho-corasick"
 version = "0.7.6"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 dependencies = [
  "memchr 2.2.1 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
 [[package]]
 name = "arrayvec"
 version = "0.4.12"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 dependencies = [
  "nodrop 0.1.14 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
 [[package]]
 name = "autocfg"
 version = "0.1.6"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 
 [[package]]
 name = "bitflags"
 version = "1.2.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 
 [[package]]
 name = "byteorder"
 version = "1.3.2"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 
 [[package]]
+name = "c2-chacha"
+version = "0.2.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "lazy_static 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)",
+ "ppv-lite86 0.2.5 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
 name = "cfg-if"
 version = "0.1.10"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 
 [[package]]
 name = "cloudabi"
 version = "0.0.3"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 dependencies = [
  "bitflags 1.2.1 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
 [[package]]
 name = "cpython"
 version = "0.3.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 dependencies = [
  "libc 0.2.64 (registry+https://github.com/rust-lang/crates.io-index)",
  "num-traits 0.2.8 (registry+https://github.com/rust-lang/crates.io-index)",
  "python27-sys 0.3.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "python3-sys 0.3.0 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
 [[package]]
 name = "crossbeam-deque"
 version = "0.7.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 dependencies = [
  "crossbeam-epoch 0.7.2 (registry+https://github.com/rust-lang/crates.io-index)",
  "crossbeam-utils 0.6.6 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
 [[package]]
 name = "crossbeam-epoch"
 version = "0.7.2"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 dependencies = [
  "arrayvec 0.4.12 (registry+https://github.com/rust-lang/crates.io-index)",
  "cfg-if 0.1.10 (registry+https://github.com/rust-lang/crates.io-index)",
  "crossbeam-utils 0.6.6 (registry+https://github.com/rust-lang/crates.io-index)",
  "lazy_static 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "memoffset 0.5.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "scopeguard 1.0.0 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
 [[package]]
 name = "crossbeam-queue"
 version = "0.1.2"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 dependencies = [
  "crossbeam-utils 0.6.6 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
 [[package]]
 name = "crossbeam-utils"
 version = "0.6.6"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 dependencies = [
  "cfg-if 0.1.10 (registry+https://github.com/rust-lang/crates.io-index)",
  "lazy_static 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
 [[package]]
 name = "either"
 version = "1.5.3"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 
 [[package]]
 name = "fuchsia-cprng"
 version = "0.1.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 
 [[package]]
+name = "getrandom"
+version = "0.1.12"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "cfg-if 0.1.10 (registry+https://github.com/rust-lang/crates.io-index)",
+ "libc 0.2.64 (registry+https://github.com/rust-lang/crates.io-index)",
+ "wasi 0.7.0 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
 name = "hg-core"
 version = "0.1.0"
 dependencies = [
  "byteorder 1.3.2 (registry+https://github.com/rust-lang/crates.io-index)",
  "lazy_static 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "memchr 2.2.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "rand 0.6.5 (registry+https://github.com/rust-lang/crates.io-index)",
  "rand_pcg 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)",
  "rayon 1.2.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "regex 1.3.1 (registry+https://github.com/rust-lang/crates.io-index)",
+ "twox-hash 1.5.0 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
 [[package]]
 name = "hg-cpython"
 version = "0.1.0"
 dependencies = [
  "cpython 0.3.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "hg-core 0.1.0",
  "libc 0.2.64 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
 [[package]]
 name = "hgdirectffi"
 version = "0.1.0"
 dependencies = [
  "hg-core 0.1.0",
  "libc 0.2.64 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
 [[package]]
 name = "lazy_static"
 version = "1.4.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 
 [[package]]
 name = "libc"
 version = "0.2.64"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 
 [[package]]
 name = "memchr"
 version = "2.2.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 
 [[package]]
 name = "memoffset"
 version = "0.5.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 dependencies = [
  "rustc_version 0.2.3 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
 [[package]]
 name = "nodrop"
 version = "0.1.14"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 
 [[package]]
 name = "num-traits"
 version = "0.2.8"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 dependencies = [
  "autocfg 0.1.6 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
 [[package]]
 name = "num_cpus"
 version = "1.10.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 dependencies = [
  "libc 0.2.64 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
 [[package]]
+name = "ppv-lite86"
+version = "0.2.5"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[[package]]
 name = "python27-sys"
 version = "0.3.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 dependencies = [
  "libc 0.2.64 (registry+https://github.com/rust-lang/crates.io-index)",
  "regex 1.3.1 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
 [[package]]
 name = "python3-sys"
 version = "0.3.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 dependencies = [
  "libc 0.2.64 (registry+https://github.com/rust-lang/crates.io-index)",
  "regex 1.3.1 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
 [[package]]
 name = "rand"
 version = "0.6.5"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 dependencies = [
  "autocfg 0.1.6 (registry+https://github.com/rust-lang/crates.io-index)",
  "libc 0.2.64 (registry+https://github.com/rust-lang/crates.io-index)",
  "rand_chacha 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "rand_core 0.4.2 (registry+https://github.com/rust-lang/crates.io-index)",
  "rand_hc 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "rand_isaac 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "rand_jitter 0.1.4 (registry+https://github.com/rust-lang/crates.io-index)",
  "rand_os 0.1.3 (registry+https://github.com/rust-lang/crates.io-index)",
  "rand_pcg 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)",
  "rand_xorshift 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "winapi 0.3.8 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
 [[package]]
+name = "rand"
+version = "0.7.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "getrandom 0.1.12 (registry+https://github.com/rust-lang/crates.io-index)",
+ "libc 0.2.64 (registry+https://github.com/rust-lang/crates.io-index)",
+ "rand_chacha 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)",
+ "rand_core 0.5.1 (registry+https://github.com/rust-lang/crates.io-index)",
+ "rand_hc 0.2.0 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
 name = "rand_chacha"
 version = "0.1.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 dependencies = [
  "autocfg 0.1.6 (registry+https://github.com/rust-lang/crates.io-index)",
  "rand_core 0.3.1 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
 [[package]]
+name = "rand_chacha"
+version = "0.2.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "c2-chacha 0.2.2 (registry+https://github.com/rust-lang/crates.io-index)",
+ "rand_core 0.5.1 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
 name = "rand_core"
 version = "0.3.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 dependencies = [
  "rand_core 0.4.2 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
 [[package]]
 name = "rand_core"
 version = "0.4.2"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 
 [[package]]
+name = "rand_core"
+version = "0.5.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "getrandom 0.1.12 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
 name = "rand_hc"
 version = "0.1.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 dependencies = [
  "rand_core 0.3.1 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
 [[package]]
+name = "rand_hc"
+version = "0.2.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "rand_core 0.5.1 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
 name = "rand_isaac"
 version = "0.1.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 dependencies = [
  "rand_core 0.3.1 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
 [[package]]
 name = "rand_jitter"
 version = "0.1.4"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 dependencies = [
  "libc 0.2.64 (registry+https://github.com/rust-lang/crates.io-index)",
  "rand_core 0.4.2 (registry+https://github.com/rust-lang/crates.io-index)",
  "winapi 0.3.8 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
 [[package]]
 name = "rand_os"
 version = "0.1.3"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 dependencies = [
  "cloudabi 0.0.3 (registry+https://github.com/rust-lang/crates.io-index)",
  "fuchsia-cprng 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "libc 0.2.64 (registry+https://github.com/rust-lang/crates.io-index)",
  "rand_core 0.4.2 (registry+https://github.com/rust-lang/crates.io-index)",
  "rdrand 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "winapi 0.3.8 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
 [[package]]
 name = "rand_pcg"
 version = "0.1.2"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 dependencies = [
  "autocfg 0.1.6 (registry+https://github.com/rust-lang/crates.io-index)",
  "rand_core 0.4.2 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
 [[package]]
 name = "rand_xorshift"
 version = "0.1.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 dependencies = [
  "rand_core 0.3.1 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
 [[package]]
 name = "rayon"
 version = "1.2.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 dependencies = [
  "crossbeam-deque 0.7.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "either 1.5.3 (registry+https://github.com/rust-lang/crates.io-index)",
  "rayon-core 1.6.0 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
 [[package]]
 name = "rayon-core"
 version = "1.6.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 dependencies = [
  "crossbeam-deque 0.7.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "crossbeam-queue 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)",
  "crossbeam-utils 0.6.6 (registry+https://github.com/rust-lang/crates.io-index)",
  "lazy_static 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "num_cpus 1.10.1 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
 [[package]]
 name = "rdrand"
 version = "0.4.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 dependencies = [
  "rand_core 0.3.1 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
 [[package]]
 name = "regex"
 version = "1.3.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 dependencies = [
  "aho-corasick 0.7.6 (registry+https://github.com/rust-lang/crates.io-index)",
  "memchr 2.2.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "regex-syntax 0.6.12 (registry+https://github.com/rust-lang/crates.io-index)",
  "thread_local 0.3.6 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
 [[package]]
 name = "regex-syntax"
 version = "0.6.12"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 
 [[package]]
 name = "rustc_version"
 version = "0.2.3"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 dependencies = [
  "semver 0.9.0 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
 [[package]]
 name = "scopeguard"
 version = "1.0.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 
 [[package]]
 name = "semver"
 version = "0.9.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 dependencies = [
  "semver-parser 0.7.0 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
 [[package]]
 name = "semver-parser"
 version = "0.7.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 
 [[package]]
 name = "thread_local"
 version = "0.3.6"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 dependencies = [
  "lazy_static 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
 [[package]]
+name = "twox-hash"
+version = "1.5.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "rand 0.7.2 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
+name = "wasi"
+version = "0.7.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[[package]]
 name = "winapi"
 version = "0.3.8"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 dependencies = [
  "winapi-i686-pc-windows-gnu 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "winapi-x86_64-pc-windows-gnu 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
 [[package]]
 name = "winapi-i686-pc-windows-gnu"
 version = "0.4.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 
 [[package]]
 name = "winapi-x86_64-pc-windows-gnu"
 version = "0.4.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 
 [metadata]
 "checksum aho-corasick 0.7.6 (registry+https://github.com/rust-lang/crates.io-index)" = "58fb5e95d83b38284460a5fda7d6470aa0b8844d283a0b614b8535e880800d2d"
 "checksum arrayvec 0.4.12 (registry+https://github.com/rust-lang/crates.io-index)" = "cd9fd44efafa8690358b7408d253adf110036b88f55672a933f01d616ad9b1b9"
 "checksum autocfg 0.1.6 (registry+https://github.com/rust-lang/crates.io-index)" = "b671c8fb71b457dd4ae18c4ba1e59aa81793daacc361d82fcd410cef0d491875"
 "checksum bitflags 1.2.1 (registry+https://github.com/rust-lang/crates.io-index)" = "cf1de2fe8c75bc145a2f577add951f8134889b4795d47466a54a5c846d691693"
 "checksum byteorder 1.3.2 (registry+https://github.com/rust-lang/crates.io-index)" = "a7c3dd8985a7111efc5c80b44e23ecdd8c007de8ade3b96595387e812b957cf5"
+"checksum c2-chacha 0.2.2 (registry+https://github.com/rust-lang/crates.io-index)" = "7d64d04786e0f528460fc884753cf8dddcc466be308f6026f8e355c41a0e4101"
 "checksum cfg-if 0.1.10 (registry+https://github.com/rust-lang/crates.io-index)" = "4785bdd1c96b2a846b2bd7cc02e86b6b3dbf14e7e53446c4f54c92a361040822"
 "checksum cloudabi 0.0.3 (registry+https://github.com/rust-lang/crates.io-index)" = "ddfc5b9aa5d4507acaf872de71051dfd0e309860e88966e1051e462a077aac4f"
 "checksum cpython 0.3.0 (registry+https://github.com/rust-lang/crates.io-index)" = "85532c648315aeb0829ad216a6a29aa3212cf9319bc7f6daf1404aa0bdd1485f"
 "checksum crossbeam-deque 0.7.1 (registry+https://github.com/rust-lang/crates.io-index)" = "b18cd2e169ad86297e6bc0ad9aa679aee9daa4f19e8163860faf7c164e4f5a71"
 "checksum crossbeam-epoch 0.7.2 (registry+https://github.com/rust-lang/crates.io-index)" = "fedcd6772e37f3da2a9af9bf12ebe046c0dfe657992377b4df982a2b54cd37a9"
 "checksum crossbeam-queue 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)" = "7c979cd6cfe72335896575c6b5688da489e420d36a27a0b9eb0c73db574b4a4b"
 "checksum crossbeam-utils 0.6.6 (registry+https://github.com/rust-lang/crates.io-index)" = "04973fa96e96579258a5091af6003abde64af786b860f18622b82e026cca60e6"
 "checksum either 1.5.3 (registry+https://github.com/rust-lang/crates.io-index)" = "bb1f6b1ce1c140482ea30ddd3335fc0024ac7ee112895426e0a629a6c20adfe3"
 "checksum fuchsia-cprng 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "a06f77d526c1a601b7c4cdd98f54b5eaabffc14d5f2f0296febdc7f357c6d3ba"
+"checksum getrandom 0.1.12 (registry+https://github.com/rust-lang/crates.io-index)" = "473a1265acc8ff1e808cd0a1af8cee3c2ee5200916058a2ca113c29f2d903571"
 "checksum lazy_static 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "e2abad23fbc42b3700f2f279844dc832adb2b2eb069b2df918f455c4e18cc646"
 "checksum libc 0.2.64 (registry+https://github.com/rust-lang/crates.io-index)" = "74dfca3d9957906e8d1e6a0b641dc9a59848e793f1da2165889fd4f62d10d79c"
 "checksum memchr 2.2.1 (registry+https://github.com/rust-lang/crates.io-index)" = "88579771288728879b57485cc7d6b07d648c9f0141eb955f8ab7f9d45394468e"
 "checksum memoffset 0.5.1 (registry+https://github.com/rust-lang/crates.io-index)" = "ce6075db033bbbb7ee5a0bbd3a3186bbae616f57fb001c485c7ff77955f8177f"
 "checksum nodrop 0.1.14 (registry+https://github.com/rust-lang/crates.io-index)" = "72ef4a56884ca558e5ddb05a1d1e7e1bfd9a68d9ed024c21704cc98872dae1bb"
 "checksum num-traits 0.2.8 (registry+https://github.com/rust-lang/crates.io-index)" = "6ba9a427cfca2be13aa6f6403b0b7e7368fe982bfa16fccc450ce74c46cd9b32"
 "checksum num_cpus 1.10.1 (registry+https://github.com/rust-lang/crates.io-index)" = "bcef43580c035376c0705c42792c294b66974abbfd2789b511784023f71f3273"
+"checksum ppv-lite86 0.2.5 (registry+https://github.com/rust-lang/crates.io-index)" = "e3cbf9f658cdb5000fcf6f362b8ea2ba154b9f146a61c7a20d647034c6b6561b"
 "checksum python27-sys 0.3.0 (registry+https://github.com/rust-lang/crates.io-index)" = "372555e88a6bc8109eb641380240dc8d25a128fc48363ec9075664daadffdd5b"
 "checksum python3-sys 0.3.0 (registry+https://github.com/rust-lang/crates.io-index)" = "f3a8ebed3f1201fda179f3960609dbbc10cd8c75e9f2afcb03788278f367d8ea"
 "checksum rand 0.6.5 (registry+https://github.com/rust-lang/crates.io-index)" = "6d71dacdc3c88c1fde3885a3be3fbab9f35724e6ce99467f7d9c5026132184ca"
+"checksum rand 0.7.2 (registry+https://github.com/rust-lang/crates.io-index)" = "3ae1b169243eaf61759b8475a998f0a385e42042370f3a7dbaf35246eacc8412"
 "checksum rand_chacha 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "556d3a1ca6600bfcbab7c7c91ccb085ac7fbbcd70e008a98742e7847f4f7bcef"
+"checksum rand_chacha 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)" = "03a2a90da8c7523f554344f921aa97283eadf6ac484a6d2a7d0212fa7f8d6853"
 "checksum rand_core 0.3.1 (registry+https://github.com/rust-lang/crates.io-index)" = "7a6fdeb83b075e8266dcc8762c22776f6877a63111121f5f8c7411e5be7eed4b"
 "checksum rand_core 0.4.2 (registry+https://github.com/rust-lang/crates.io-index)" = "9c33a3c44ca05fa6f1807d8e6743f3824e8509beca625669633be0acbdf509dc"
+"checksum rand_core 0.5.1 (registry+https://github.com/rust-lang/crates.io-index)" = "90bde5296fc891b0cef12a6d03ddccc162ce7b2aff54160af9338f8d40df6d19"
 "checksum rand_hc 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "7b40677c7be09ae76218dc623efbf7b18e34bced3f38883af07bb75630a21bc4"
+"checksum rand_hc 0.2.0 (registry+https://github.com/rust-lang/crates.io-index)" = "ca3129af7b92a17112d59ad498c6f81eaf463253766b90396d39ea7a39d6613c"
 "checksum rand_isaac 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "ded997c9d5f13925be2a6fd7e66bf1872597f759fd9dd93513dd7e92e5a5ee08"
 "checksum rand_jitter 0.1.4 (registry+https://github.com/rust-lang/crates.io-index)" = "1166d5c91dc97b88d1decc3285bb0a99ed84b05cfd0bc2341bdf2d43fc41e39b"
 "checksum rand_os 0.1.3 (registry+https://github.com/rust-lang/crates.io-index)" = "7b75f676a1e053fc562eafbb47838d67c84801e38fc1ba459e8f180deabd5071"
 "checksum rand_pcg 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)" = "abf9b09b01790cfe0364f52bf32995ea3c39f4d2dd011eac241d2914146d0b44"
 "checksum rand_xorshift 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "cbf7e9e623549b0e21f6e97cf8ecf247c1a8fd2e8a992ae265314300b2455d5c"
 "checksum rayon 1.2.0 (registry+https://github.com/rust-lang/crates.io-index)" = "83a27732a533a1be0a0035a111fe76db89ad312f6f0347004c220c57f209a123"
 "checksum rayon-core 1.6.0 (registry+https://github.com/rust-lang/crates.io-index)" = "98dcf634205083b17d0861252431eb2acbfb698ab7478a2d20de07954f47ec7b"
 "checksum rdrand 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "678054eb77286b51581ba43620cc911abf02758c91f93f479767aed0f90458b2"
 "checksum regex 1.3.1 (registry+https://github.com/rust-lang/crates.io-index)" = "dc220bd33bdce8f093101afe22a037b8eb0e5af33592e6a9caafff0d4cb81cbd"
 "checksum regex-syntax 0.6.12 (registry+https://github.com/rust-lang/crates.io-index)" = "11a7e20d1cce64ef2fed88b66d347f88bd9babb82845b2b858f3edbf59a4f716"
 "checksum rustc_version 0.2.3 (registry+https://github.com/rust-lang/crates.io-index)" = "138e3e0acb6c9fb258b19b67cb8abd63c00679d2851805ea151465464fe9030a"
 "checksum scopeguard 1.0.0 (registry+https://github.com/rust-lang/crates.io-index)" = "b42e15e59b18a828bbf5c58ea01debb36b9b096346de35d941dcb89009f24a0d"
 "checksum semver 0.9.0 (registry+https://github.com/rust-lang/crates.io-index)" = "1d7eb9ef2c18661902cc47e535f9bc51b78acd254da71d375c2f6720d9a40403"
 "checksum semver-parser 0.7.0 (registry+https://github.com/rust-lang/crates.io-index)" = "388a1df253eca08550bef6c72392cfe7c30914bf41df5269b68cbd6ff8f570a3"
 "checksum thread_local 0.3.6 (registry+https://github.com/rust-lang/crates.io-index)" = "c6b53e329000edc2b34dbe8545fd20e55a333362d0a321909685a19bd28c3f1b"
+"checksum twox-hash 1.5.0 (registry+https://github.com/rust-lang/crates.io-index)" = "3bfd5b7557925ce778ff9b9ef90e3ade34c524b5ff10e239c69a42d546d2af56"
+"checksum wasi 0.7.0 (registry+https://github.com/rust-lang/crates.io-index)" = "b89c3ce4ce14bdc6fb6beaf9ec7928ca331de5df7e5ea278375642a2f478570d"
 "checksum winapi 0.3.8 (registry+https://github.com/rust-lang/crates.io-index)" = "8093091eeb260906a183e6ae1abdba2ef5ef2257a21801128899c3fc699229c6"
 "checksum winapi-i686-pc-windows-gnu 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "ac3b87c63620426dd9b991e5ce0329eff545bccbbb34f3be09ff6fb6ab51b7b6"
 "checksum winapi-x86_64-pc-windows-gnu 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "712e227841d057c1ee1cd2fb22fa7e5a5461ae8e48fa2ca79ec42cfc1931183f"

rust/hg-core/Cargo.toml

@@ -1,18 +1,19
 [package]
 name = "hg-core"
 version = "0.1.0"
 authors = ["Georges Racinet <[e-mail]>"]
 description = "Mercurial pure Rust core library, with no assumption on Python bindings (FFI)"
 edition = "2018"
 
 [lib]
 name = "hg"
 
 [dependencies]
 byteorder = "1.3.1"
 lazy_static = "1.3.0"
 memchr = "2.2.0"
 rand = "0.6.5"
 rand_pcg = "0.1.1"
+rayon = "1.2.0"
 regex = "1.1.0"
-rayon = "1.2.0"
+twox-hash = "1.5.0"

rust/hg-core/src/dirstate.rs

@@ -1,82 +1,81
 // dirstate module
 //
 // Copyright 2019 Raphaël Gomès <[e-mail]>
 //
 // This software may be used and distributed according to the terms of the
 // GNU General Public License version 2 or any later version.
 
-use crate::{utils::hg_path::HgPathBuf, DirstateParseError};
+use crate::{utils::hg_path::HgPathBuf, DirstateParseError, FastHashMap};
 use std::collections::hash_map;
-use std::collections::HashMap;
 use std::convert::TryFrom;
 
 pub mod dirs_multiset;
 pub mod dirstate_map;
 pub mod parsers;
 pub mod status;
 
 #[derive(Debug, PartialEq, Clone)]
 pub struct DirstateParents {
     pub p1: [u8; 20],
     pub p2: [u8; 20],
 }
 
 /// The C implementation uses all signed types. This will be an issue
 /// either when 4GB+ source files are commonplace or in 2038, whichever
 /// comes first.
 #[derive(Debug, PartialEq, Copy, Clone)]
 pub struct DirstateEntry {
     pub state: EntryState,
     pub mode: i32,
     pub mtime: i32,
     pub size: i32,
 }
 
 /// A `DirstateEntry` with a size of `-2` means that it was merged from the
 /// other parent. This allows revert to pick the right status back during a
 /// merge.
 pub const SIZE_FROM_OTHER_PARENT: i32 = -2;
 
-pub type StateMap = HashMap<HgPathBuf, DirstateEntry>;
+pub type StateMap = FastHashMap<HgPathBuf, DirstateEntry>;
 pub type StateMapIter<'a> = hash_map::Iter<'a, HgPathBuf, DirstateEntry>;
-pub type CopyMap = HashMap<HgPathBuf, HgPathBuf>;
+pub type CopyMap = FastHashMap<HgPathBuf, HgPathBuf>;
 pub type CopyMapIter<'a> = hash_map::Iter<'a, HgPathBuf, HgPathBuf>;
 
 #[derive(Copy, Clone, Debug, Eq, PartialEq)]
 pub enum EntryState {
     Normal,
     Added,
     Removed,
     Merged,
     Unknown,
 }
 
 impl TryFrom<u8> for EntryState {
     type Error = DirstateParseError;
 
     fn try_from(value: u8) -> Result<Self, Self::Error> {
         match value {
             b'n' => Ok(EntryState::Normal),
             b'a' => Ok(EntryState::Added),
             b'r' => Ok(EntryState::Removed),
             b'm' => Ok(EntryState::Merged),
             b'?' => Ok(EntryState::Unknown),
             _ => Err(DirstateParseError::CorruptedEntry(format!(
                 "Incorrect entry state {}",
                 value
             ))),
         }
     }
 }
 
 impl Into<u8> for EntryState {
     fn into(self) -> u8 {
         match self {
             EntryState::Normal => b'n',
             EntryState::Added => b'a',
             EntryState::Removed => b'r',
             EntryState::Merged => b'm',
             EntryState::Unknown => b'?',
         }
     }
 }

rust/hg-core/src/dirstate/dirs_multiset.rs

@@ -1,335 +1,334
 // dirs_multiset.rs
 //
 // Copyright 2019 Raphaël Gomès <[e-mail]>
 //
 // This software may be used and distributed according to the terms of the
 // GNU General Public License version 2 or any later version.
 
 //! A multiset of directory names.
 //!
 //! Used to counts the references to directories in a manifest or dirstate.
 use crate::utils::hg_path::{HgPath, HgPathBuf};
 use crate::{
     dirstate::EntryState, utils::files, DirstateEntry, DirstateMapError,
+    FastHashMap,
 };
 use std::collections::hash_map::{self, Entry};
-use std::collections::HashMap;
 
 // could be encapsulated if we care API stability more seriously
 pub type DirsMultisetIter<'a> = hash_map::Keys<'a, HgPathBuf, u32>;
 
 #[derive(PartialEq, Debug)]
 pub struct DirsMultiset {
-    inner: HashMap<HgPathBuf, u32>,
+    inner: FastHashMap<HgPathBuf, u32>,
 }
 
 impl DirsMultiset {
     /// Initializes the multiset from a dirstate.
     ///
     /// If `skip_state` is provided, skips dirstate entries with equal state.
     pub fn from_dirstate(
-        vec: &HashMap<HgPathBuf, DirstateEntry>,
+        vec: &FastHashMap<HgPathBuf, DirstateEntry>,
         skip_state: Option<EntryState>,
     ) -> Self {
         let mut multiset = DirsMultiset {
-            inner: HashMap::new(),
+            inner: FastHashMap::default(),
         };
 
         for (filename, DirstateEntry { state, .. }) in vec {
             // This `if` is optimized out of the loop
             if let Some(skip) = skip_state {
                 if skip != *state {
                     multiset.add_path(filename);
                 }
             } else {
                 multiset.add_path(filename);
             }
         }
 
         multiset
     }
 
     /// Initializes the multiset from a manifest.
     pub fn from_manifest(vec: &Vec<HgPathBuf>) -> Self {
         let mut multiset = DirsMultiset {
-            inner: HashMap::new(),
+            inner: FastHashMap::default(),
         };
 
         for filename in vec {
             multiset.add_path(filename);
         }
 
         multiset
     }
 
     /// Increases the count of deepest directory contained in the path.
     ///
     /// If the directory is not yet in the map, adds its parents.
     pub fn add_path(&mut self, path: &HgPath) -> Result<(), DirstateMapError> {
         for subpath in files::find_dirs(path) {
             if subpath.as_bytes().last() == Some(&b'/') {
                 // TODO Remove this once PathAuditor is certified
                 // as the only entrypoint for path data
                 return Err(DirstateMapError::ConsecutiveSlashes);
             }
             if let Some(val) = self.inner.get_mut(subpath) {
                 *val += 1;
                 break;
             }
             self.inner.insert(subpath.to_owned(), 1);
         }
         Ok(())
     }
 
     /// Decreases the count of deepest directory contained in the path.
     ///
     /// If it is the only reference, decreases all parents until one is
     /// removed.
     /// If the directory is not in the map, something horrible has happened.
     pub fn delete_path(
         &mut self,
         path: &HgPath,
     ) -> Result<(), DirstateMapError> {
         for subpath in files::find_dirs(path) {
             match self.inner.entry(subpath.to_owned()) {
                 Entry::Occupied(mut entry) => {
                     let val = entry.get().clone();
                     if val > 1 {
                         entry.insert(val - 1);
                         break;
                     }
                     entry.remove();
                 }
                 Entry::Vacant(_) => {
                     return Err(DirstateMapError::PathNotFound(
                         path.to_owned(),
                     ))
                 }
             };
         }
 
         Ok(())
     }
 
     pub fn contains(&self, key: &HgPath) -> bool {
         self.inner.contains_key(key)
     }
 
     pub fn iter(&self) -> DirsMultisetIter {
         self.inner.keys()
     }
 
     pub fn len(&self) -> usize {
         self.inner.len()
     }
 }
 
 #[cfg(test)]
 mod tests {
     use super::*;
-    use std::collections::HashMap;
 
     #[test]
     fn test_delete_path_path_not_found() {
         let mut map = DirsMultiset::from_manifest(&vec![]);
         let path = HgPathBuf::from_bytes(b"doesnotexist/");
         assert_eq!(
             Err(DirstateMapError::PathNotFound(path.to_owned())),
             map.delete_path(&path)
         );
     }
 
     #[test]
     fn test_delete_path_empty_path() {
         let mut map = DirsMultiset::from_manifest(&vec![HgPathBuf::new()]);
         let path = HgPath::new(b"");
         assert_eq!(Ok(()), map.delete_path(path));
         assert_eq!(
             Err(DirstateMapError::PathNotFound(path.to_owned())),
             map.delete_path(path)
         );
     }
 
     #[test]
     fn test_delete_path_successful() {
         let mut map = DirsMultiset {
             inner: [("", 5), ("a", 3), ("a/b", 2), ("a/c", 1)]
                 .iter()
                 .map(|(k, v)| (HgPathBuf::from_bytes(k.as_bytes()), *v))
                 .collect(),
         };
 
         assert_eq!(Ok(()), map.delete_path(HgPath::new(b"a/b/")));
         eprintln!("{:?}", map);
         assert_eq!(Ok(()), map.delete_path(HgPath::new(b"a/b/")));
         eprintln!("{:?}", map);
         assert_eq!(
             Err(DirstateMapError::PathNotFound(HgPathBuf::from_bytes(
                 b"a/b/"
             ))),
             map.delete_path(HgPath::new(b"a/b/"))
         );
 
         assert_eq!(2, *map.inner.get(HgPath::new(b"a")).unwrap());
         assert_eq!(1, *map.inner.get(HgPath::new(b"a/c")).unwrap());
         eprintln!("{:?}", map);
         assert_eq!(Ok(()), map.delete_path(HgPath::new(b"a/")));
         eprintln!("{:?}", map);
 
         assert_eq!(Ok(()), map.delete_path(HgPath::new(b"a/c/")));
         assert_eq!(
             Err(DirstateMapError::PathNotFound(HgPathBuf::from_bytes(
                 b"a/c/"
             ))),
             map.delete_path(HgPath::new(b"a/c/"))
         );
     }
 
     #[test]
     fn test_add_path_empty_path() {
         let mut map = DirsMultiset::from_manifest(&vec![]);
         let path = HgPath::new(b"");
         map.add_path(path);
 
         assert_eq!(1, map.len());
     }
 
     #[test]
     fn test_add_path_successful() {
         let mut map = DirsMultiset::from_manifest(&vec![]);
 
         map.add_path(HgPath::new(b"a/"));
         assert_eq!(1, *map.inner.get(HgPath::new(b"a")).unwrap());
         assert_eq!(1, *map.inner.get(HgPath::new(b"")).unwrap());
         assert_eq!(2, map.len());
 
         // Non directory should be ignored
         map.add_path(HgPath::new(b"a"));
         assert_eq!(1, *map.inner.get(HgPath::new(b"a")).unwrap());
         assert_eq!(2, map.len());
 
         // Non directory will still add its base
         map.add_path(HgPath::new(b"a/b"));
         assert_eq!(2, *map.inner.get(HgPath::new(b"a")).unwrap());
         assert_eq!(2, map.len());
 
         // Duplicate path works
         map.add_path(HgPath::new(b"a/"));
         assert_eq!(3, *map.inner.get(HgPath::new(b"a")).unwrap());
 
         // Nested dir adds to its base
         map.add_path(HgPath::new(b"a/b/"));
         assert_eq!(4, *map.inner.get(HgPath::new(b"a")).unwrap());
         assert_eq!(1, *map.inner.get(HgPath::new(b"a/b")).unwrap());
 
         // but not its base's base, because it already existed
         map.add_path(HgPath::new(b"a/b/c/"));
         assert_eq!(4, *map.inner.get(HgPath::new(b"a")).unwrap());
         assert_eq!(2, *map.inner.get(HgPath::new(b"a/b")).unwrap());
 
         map.add_path(HgPath::new(b"a/c/"));
         assert_eq!(1, *map.inner.get(HgPath::new(b"a/c")).unwrap());
 
         let expected = DirsMultiset {
             inner: [("", 2), ("a", 5), ("a/b", 2), ("a/b/c", 1), ("a/c", 1)]
                 .iter()
                 .map(|(k, v)| (HgPathBuf::from_bytes(k.as_bytes()), *v))
                 .collect(),
         };
         assert_eq!(map, expected);
     }
 
     #[test]
     fn test_dirsmultiset_new_empty() {
         let new = DirsMultiset::from_manifest(&vec![]);
         let expected = DirsMultiset {
-            inner: HashMap::new(),
+            inner: FastHashMap::default(),
         };
         assert_eq!(expected, new);
 
-        let new = DirsMultiset::from_dirstate(&HashMap::new(), None);
+        let new = DirsMultiset::from_dirstate(&FastHashMap::default(), None);
         let expected = DirsMultiset {
-            inner: HashMap::new(),
+            inner: FastHashMap::default(),
         };
         assert_eq!(expected, new);
     }
 
     #[test]
     fn test_dirsmultiset_new_no_skip() {
         let input_vec = ["a/", "b/", "a/c", "a/d/"]
             .iter()
             .map(|e| HgPathBuf::from_bytes(e.as_bytes()))
             .collect();
         let expected_inner = [("", 2), ("a", 3), ("b", 1), ("a/d", 1)]
             .iter()
             .map(|(k, v)| (HgPathBuf::from_bytes(k.as_bytes()), *v))
             .collect();
 
         let new = DirsMultiset::from_manifest(&input_vec);
         let expected = DirsMultiset {
             inner: expected_inner,
         };
         assert_eq!(expected, new);
 
         let input_map = ["a/", "b/", "a/c", "a/d/"]
             .iter()
             .map(|f| {
                 (
                     HgPathBuf::from_bytes(f.as_bytes()),
                     DirstateEntry {
                         state: EntryState::Normal,
                         mode: 0,
                         mtime: 0,
                         size: 0,
                     },
                 )
             })
             .collect();
         let expected_inner = [("", 2), ("a", 3), ("b", 1), ("a/d", 1)]
             .iter()
             .map(|(k, v)| (HgPathBuf::from_bytes(k.as_bytes()), *v))
             .collect();
 
         let new = DirsMultiset::from_dirstate(&input_map, None);
         let expected = DirsMultiset {
             inner: expected_inner,
         };
         assert_eq!(expected, new);
     }
 
     #[test]
     fn test_dirsmultiset_new_skip() {
         let input_map = [
             ("a/", EntryState::Normal),
             ("a/b/", EntryState::Normal),
             ("a/c", EntryState::Removed),
             ("a/d/", EntryState::Merged),
         ]
         .iter()
         .map(|(f, state)| {
             (
                 HgPathBuf::from_bytes(f.as_bytes()),
                 DirstateEntry {
                     state: *state,
                     mode: 0,
                     mtime: 0,
                     size: 0,
                 },
             )
         })
         .collect();
 
         // "a" incremented with "a/c" and "a/d/"
         let expected_inner = [("", 1), ("a", 2), ("a/d", 1)]
             .iter()
             .map(|(k, v)| (HgPathBuf::from_bytes(k.as_bytes()), *v))
             .collect();
 
         let new =
             DirsMultiset::from_dirstate(&input_map, Some(EntryState::Normal));
         let expected = DirsMultiset {
             inner: expected_inner,
         };
         assert_eq!(expected, new);
     }
 }

rust/hg-core/src/dirstate/dirstate_map.rs

@@ -1,427 +1,427
 // dirstate_map.rs
 //
 // Copyright 2019 Raphaël Gomès <[e-mail]>
 //
 // This software may be used and distributed according to the terms of the
 // GNU General Public License version 2 or any later version.
 
 use crate::{
     dirstate::{parsers::PARENT_SIZE, EntryState, SIZE_FROM_OTHER_PARENT},
     pack_dirstate, parse_dirstate,
     utils::{
         files::normalize_case,
         hg_path::{HgPath, HgPathBuf},
     },
     CopyMap, DirsMultiset, DirstateEntry, DirstateError, DirstateMapError,
-    DirstateParents, DirstateParseError, StateMap,
+    DirstateParents, DirstateParseError, FastHashMap, StateMap,
 };
 use core::borrow::Borrow;
-use std::collections::{HashMap, HashSet};
+use std::collections::HashSet;
 use std::convert::TryInto;
 use std::iter::FromIterator;
 use std::ops::Deref;
 use std::time::Duration;
 
-pub type FileFoldMap = HashMap<HgPathBuf, HgPathBuf>;
+pub type FileFoldMap = FastHashMap<HgPathBuf, HgPathBuf>;
 
 const NULL_ID: [u8; 20] = [0; 20];
 const MTIME_UNSET: i32 = -1;
 
 #[derive(Default)]
 pub struct DirstateMap {
     state_map: StateMap,
     pub copy_map: CopyMap,
     file_fold_map: Option<FileFoldMap>,
     pub dirs: Option<DirsMultiset>,
     pub all_dirs: Option<DirsMultiset>,
     non_normal_set: HashSet<HgPathBuf>,
     other_parent_set: HashSet<HgPathBuf>,
     parents: Option<DirstateParents>,
     dirty_parents: bool,
 }
 
 /// Should only really be used in python interface code, for clarity
 impl Deref for DirstateMap {
     type Target = StateMap;
 
     fn deref(&self) -> &Self::Target {
         &self.state_map
     }
 }
 
 impl FromIterator<(HgPathBuf, DirstateEntry)> for DirstateMap {
     fn from_iter<I: IntoIterator<Item = (HgPathBuf, DirstateEntry)>>(
         iter: I,
     ) -> Self {
         Self {
             state_map: iter.into_iter().collect(),
             ..Self::default()
         }
     }
 }
 
 impl DirstateMap {
     pub fn new() -> Self {
         Self::default()
     }
 
     pub fn clear(&mut self) {
         self.state_map.clear();
         self.copy_map.clear();
         self.file_fold_map = None;
         self.non_normal_set.clear();
         self.other_parent_set.clear();
         self.set_parents(&DirstateParents {
             p1: NULL_ID,
             p2: NULL_ID,
         })
     }
 
     /// Add a tracked file to the dirstate
     pub fn add_file(
         &mut self,
         filename: &HgPath,
         old_state: EntryState,
         entry: DirstateEntry,
     ) -> Result<(), DirstateMapError> {
         if old_state == EntryState::Unknown || old_state == EntryState::Removed
         {
             if let Some(ref mut dirs) = self.dirs {
                 dirs.add_path(filename)?;
             }
         }
         if old_state == EntryState::Unknown {
             if let Some(ref mut all_dirs) = self.all_dirs {
                 all_dirs.add_path(filename)?;
             }
         }
         self.state_map.insert(filename.to_owned(), entry.to_owned());
 
         if entry.state != EntryState::Normal || entry.mtime == MTIME_UNSET {
             self.non_normal_set.insert(filename.to_owned());
         }
 
         if entry.size == SIZE_FROM_OTHER_PARENT {
             self.other_parent_set.insert(filename.to_owned());
         }
         Ok(())
     }
 
     /// Mark a file as removed in the dirstate.
     ///
     /// The `size` parameter is used to store sentinel values that indicate
     /// the file's previous state.  In the future, we should refactor this
     /// to be more explicit about what that state is.
     pub fn remove_file(
         &mut self,
         filename: &HgPath,
         old_state: EntryState,
         size: i32,
     ) -> Result<(), DirstateMapError> {
         if old_state != EntryState::Unknown && old_state != EntryState::Removed
         {
             if let Some(ref mut dirs) = self.dirs {
                 dirs.delete_path(filename)?;
             }
         }
         if old_state == EntryState::Unknown {
             if let Some(ref mut all_dirs) = self.all_dirs {
                 all_dirs.add_path(filename);
             }
         }
 
         if let Some(ref mut file_fold_map) = self.file_fold_map {
             file_fold_map.remove(&normalize_case(filename));
         }
         self.state_map.insert(
             filename.to_owned(),
             DirstateEntry {
                 state: EntryState::Removed,
                 mode: 0,
                 size,
                 mtime: 0,
             },
         );
         self.non_normal_set.insert(filename.to_owned());
         Ok(())
     }
 
     /// Remove a file from the dirstate.
     /// Returns `true` if the file was previously recorded.
     pub fn drop_file(
         &mut self,
         filename: &HgPath,
         old_state: EntryState,
     ) -> Result<bool, DirstateMapError> {
         let exists = self.state_map.remove(filename).is_some();
 
         if exists {
             if old_state != EntryState::Removed {
                 if let Some(ref mut dirs) = self.dirs {
                     dirs.delete_path(filename)?;
                 }
             }
             if let Some(ref mut all_dirs) = self.all_dirs {
                 all_dirs.delete_path(filename)?;
             }
         }
         if let Some(ref mut file_fold_map) = self.file_fold_map {
             file_fold_map.remove(&normalize_case(filename));
         }
         self.non_normal_set.remove(filename);
 
         Ok(exists)
     }
 
     pub fn clear_ambiguous_times(
         &mut self,
         filenames: Vec<HgPathBuf>,
         now: i32,
     ) {
         for filename in filenames {
             let mut changed = false;
             self.state_map
                 .entry(filename.to_owned())
                 .and_modify(|entry| {
                     if entry.state == EntryState::Normal && entry.mtime == now
                     {
                         changed = true;
                         *entry = DirstateEntry {
                             mtime: MTIME_UNSET,
                             ..*entry
                         };
                     }
                 });
             if changed {
                 self.non_normal_set.insert(filename.to_owned());
             }
         }
     }
 
     pub fn non_normal_other_parent_entries(
         &self,
     ) -> (HashSet<HgPathBuf>, HashSet<HgPathBuf>) {
         let mut non_normal = HashSet::new();
         let mut other_parent = HashSet::new();
 
         for (
             filename,
             DirstateEntry {
                 state, size, mtime, ..
             },
         ) in self.state_map.iter()
         {
             if *state != EntryState::Normal || *mtime == MTIME_UNSET {
                 non_normal.insert(filename.to_owned());
             }
             if *state == EntryState::Normal && *size == SIZE_FROM_OTHER_PARENT
             {
                 other_parent.insert(filename.to_owned());
             }
         }
 
         (non_normal, other_parent)
     }
 
     /// Both of these setters and their uses appear to be the simplest way to
     /// emulate a Python lazy property, but it is ugly and unidiomatic.
     /// TODO One day, rewriting this struct using the typestate might be a
     /// good idea.
     pub fn set_all_dirs(&mut self) {
         if self.all_dirs.is_none() {
             self.all_dirs =
                 Some(DirsMultiset::from_dirstate(&self.state_map, None));
         }
     }
 
     pub fn set_dirs(&mut self) {
         if self.dirs.is_none() {
             self.dirs = Some(DirsMultiset::from_dirstate(
                 &self.state_map,
                 Some(EntryState::Removed),
             ));
         }
     }
 
     pub fn has_tracked_dir(&mut self, directory: &HgPath) -> bool {
         self.set_dirs();
         self.dirs.as_ref().unwrap().contains(directory)
     }
 
     pub fn has_dir(&mut self, directory: &HgPath) -> bool {
         self.set_all_dirs();
         self.all_dirs.as_ref().unwrap().contains(directory)
     }
 
     pub fn parents(
         &mut self,
         file_contents: &[u8],
     ) -> Result<&DirstateParents, DirstateError> {
         if let Some(ref parents) = self.parents {
             return Ok(parents);
         }
         let parents;
         if file_contents.len() == PARENT_SIZE * 2 {
             parents = DirstateParents {
                 p1: file_contents[..PARENT_SIZE].try_into().unwrap(),
                 p2: file_contents[PARENT_SIZE..PARENT_SIZE * 2]
                     .try_into()
                     .unwrap(),
             };
         } else if file_contents.is_empty() {
             parents = DirstateParents {
                 p1: NULL_ID,
                 p2: NULL_ID,
             };
         } else {
             return Err(DirstateError::Parse(DirstateParseError::Damaged));
         }
 
         self.parents = Some(parents);
         Ok(self.parents.as_ref().unwrap())
     }
 
     pub fn set_parents(&mut self, parents: &DirstateParents) {
         self.parents = Some(parents.clone());
         self.dirty_parents = true;
     }
 
     pub fn read(
         &mut self,
         file_contents: &[u8],
     ) -> Result<Option<DirstateParents>, DirstateError> {
         if file_contents.is_empty() {
             return Ok(None);
         }
 
         let parents = parse_dirstate(
             &mut self.state_map,
             &mut self.copy_map,
             file_contents,
         )?;
 
         if !self.dirty_parents {
             self.set_parents(&parents);
         }
 
         Ok(Some(parents))
     }
 
     pub fn pack(
         &mut self,
         parents: DirstateParents,
         now: Duration,
     ) -> Result<Vec<u8>, DirstateError> {
         let packed =
             pack_dirstate(&mut self.state_map, &self.copy_map, parents, now)?;
 
         self.dirty_parents = false;
 
         let result = self.non_normal_other_parent_entries();
         self.non_normal_set = result.0;
         self.other_parent_set = result.1;
         Ok(packed)
     }
 
     pub fn build_file_fold_map(&mut self) -> &FileFoldMap {
         if let Some(ref file_fold_map) = self.file_fold_map {
             return file_fold_map;
         }
-        let mut new_file_fold_map = FileFoldMap::new();
+        let mut new_file_fold_map = FileFoldMap::default();
         for (filename, DirstateEntry { state, .. }) in self.state_map.borrow()
         {
             if *state == EntryState::Removed {
                 new_file_fold_map
                     .insert(normalize_case(filename), filename.to_owned());
             }
         }
         self.file_fold_map = Some(new_file_fold_map);
         self.file_fold_map.as_ref().unwrap()
     }
 }
 
 #[cfg(test)]
 mod tests {
     use super::*;
 
     #[test]
     fn test_dirs_multiset() {
         let mut map = DirstateMap::new();
         assert!(map.dirs.is_none());
         assert!(map.all_dirs.is_none());
 
         assert_eq!(false, map.has_dir(HgPath::new(b"nope")));
         assert!(map.all_dirs.is_some());
         assert!(map.dirs.is_none());
 
         assert_eq!(false, map.has_tracked_dir(HgPath::new(b"nope")));
         assert!(map.dirs.is_some());
     }
 
     #[test]
     fn test_add_file() {
         let mut map = DirstateMap::new();
 
         assert_eq!(0, map.len());
 
         map.add_file(
             HgPath::new(b"meh"),
             EntryState::Normal,
             DirstateEntry {
                 state: EntryState::Normal,
                 mode: 1337,
                 mtime: 1337,
                 size: 1337,
             },
         );
 
         assert_eq!(1, map.len());
         assert_eq!(0, map.non_normal_set.len());
         assert_eq!(0, map.other_parent_set.len());
     }
 
     #[test]
     fn test_non_normal_other_parent_entries() {
         let map: DirstateMap = [
             (b"f1", (EntryState::Removed, 1337, 1337, 1337)),
             (b"f2", (EntryState::Normal, 1337, 1337, -1)),
             (b"f3", (EntryState::Normal, 1337, 1337, 1337)),
             (b"f4", (EntryState::Normal, 1337, -2, 1337)),
             (b"f5", (EntryState::Added, 1337, 1337, 1337)),
             (b"f6", (EntryState::Added, 1337, 1337, -1)),
             (b"f7", (EntryState::Merged, 1337, 1337, -1)),
             (b"f8", (EntryState::Merged, 1337, 1337, 1337)),
             (b"f9", (EntryState::Merged, 1337, -2, 1337)),
             (b"fa", (EntryState::Added, 1337, -2, 1337)),
             (b"fb", (EntryState::Removed, 1337, -2, 1337)),
         ]
         .iter()
         .map(|(fname, (state, mode, size, mtime))| {
             (
                 HgPathBuf::from_bytes(fname.as_ref()),
                 DirstateEntry {
                     state: *state,
                     mode: *mode,
                     size: *size,
                     mtime: *mtime,
                 },
             )
         })
         .collect();
 
         let non_normal = [
             b"f1", b"f2", b"f5", b"f6", b"f7", b"f8", b"f9", b"fa", b"fb",
         ]
         .iter()
         .map(|x| HgPathBuf::from_bytes(x.as_ref()))
         .collect();
 
         let mut other_parent = HashSet::new();
         other_parent.insert(HgPathBuf::from_bytes(b"f4"));
 
         assert_eq!(
             (non_normal, other_parent),
             map.non_normal_other_parent_entries()
         );
     }
 }

rust/hg-core/src/dirstate/parsers.rs

@@ -1,434 +1,433
 // Copyright 2019 Raphaël Gomès <[e-mail]>
 //
 // This software may be used and distributed according to the terms of the
 // GNU General Public License version 2 or any later version.
 
 use crate::utils::hg_path::HgPath;
 use crate::{
     dirstate::{CopyMap, EntryState, StateMap},
     DirstateEntry, DirstatePackError, DirstateParents, DirstateParseError,
 };
 use byteorder::{BigEndian, ReadBytesExt, WriteBytesExt};
 use std::convert::{TryFrom, TryInto};
 use std::io::Cursor;
 use std::time::Duration;
 
 /// Parents are stored in the dirstate as byte hashes.
 pub const PARENT_SIZE: usize = 20;
 /// Dirstate entries have a static part of 8 + 32 + 32 + 32 + 32 bits.
 const MIN_ENTRY_SIZE: usize = 17;
 
 // TODO parse/pack: is mutate-on-loop better for performance?
 
 pub fn parse_dirstate(
     state_map: &mut StateMap,
     copy_map: &mut CopyMap,
     contents: &[u8],
 ) -> Result<DirstateParents, DirstateParseError> {
     if contents.len() < PARENT_SIZE * 2 {
         return Err(DirstateParseError::TooLittleData);
     }
 
     let mut curr_pos = PARENT_SIZE * 2;
     let parents = DirstateParents {
         p1: contents[..PARENT_SIZE].try_into().unwrap(),
         p2: contents[PARENT_SIZE..curr_pos].try_into().unwrap(),
     };
 
     while curr_pos < contents.len() {
         if curr_pos + MIN_ENTRY_SIZE > contents.len() {
             return Err(DirstateParseError::Overflow);
         }
         let entry_bytes = &contents[curr_pos..];
 
         let mut cursor = Cursor::new(entry_bytes);
         let state = EntryState::try_from(cursor.read_u8()?)?;
         let mode = cursor.read_i32::<BigEndian>()?;
         let size = cursor.read_i32::<BigEndian>()?;
         let mtime = cursor.read_i32::<BigEndian>()?;
         let path_len = cursor.read_i32::<BigEndian>()? as usize;
 
         if path_len > contents.len() - curr_pos {
             return Err(DirstateParseError::Overflow);
         }
 
         // Slice instead of allocating a Vec needed for `read_exact`
         let path = &entry_bytes[MIN_ENTRY_SIZE..MIN_ENTRY_SIZE + (path_len)];
 
         let (path, copy) = match memchr::memchr(0, path) {
             None => (path, None),
             Some(i) => (&path[..i], Some(&path[(i + 1)..])),
         };
 
         if let Some(copy_path) = copy {
             copy_map.insert(
                 HgPath::new(path).to_owned(),
                 HgPath::new(copy_path).to_owned(),
             );
         };
         state_map.insert(
             HgPath::new(path).to_owned(),
             DirstateEntry {
                 state,
                 mode,
                 size,
                 mtime,
             },
         );
         curr_pos = curr_pos + MIN_ENTRY_SIZE + (path_len);
     }
 
     Ok(parents)
 }
 
 /// `now` is the duration in seconds since the Unix epoch
 pub fn pack_dirstate(
     state_map: &mut StateMap,
     copy_map: &CopyMap,
     parents: DirstateParents,
     now: Duration,
 ) -> Result<Vec<u8>, DirstatePackError> {
     // TODO move away from i32 before 2038.
     let now: i32 = now.as_secs().try_into().expect("time overflow");
 
     let expected_size: usize = state_map
         .iter()
         .map(|(filename, _)| {
             let mut length = MIN_ENTRY_SIZE + filename.len();
             if let Some(copy) = copy_map.get(filename) {
                 length += copy.len() + 1;
             }
             length
         })
         .sum();
     let expected_size = expected_size + PARENT_SIZE * 2;
 
     let mut packed = Vec::with_capacity(expected_size);
     let mut new_state_map = vec![];
 
     packed.extend(&parents.p1);
     packed.extend(&parents.p2);
 
     for (filename, entry) in state_map.iter() {
         let new_filename = filename.to_owned();
         let mut new_mtime: i32 = entry.mtime;
         if entry.state == EntryState::Normal && entry.mtime == now {
             // The file was last modified "simultaneously" with the current
             // write to dirstate (i.e. within the same second for file-
             // systems with a granularity of 1 sec). This commonly happens
             // for at least a couple of files on 'update'.
             // The user could change the file without changing its size
             // within the same second. Invalidate the file's mtime in
             // dirstate, forcing future 'status' calls to compare the
             // contents of the file if the size is the same. This prevents
             // mistakenly treating such files as clean.
             new_mtime = -1;
             new_state_map.push((
                 filename.to_owned(),
                 DirstateEntry {
                     mtime: new_mtime,
                     ..*entry
                 },
             ));
         }
         let mut new_filename = new_filename.into_vec();
         if let Some(copy) = copy_map.get(filename) {
             new_filename.push('\0' as u8);
             new_filename.extend(copy.bytes());
         }
 
         packed.write_u8(entry.state.into())?;
         packed.write_i32::<BigEndian>(entry.mode)?;
         packed.write_i32::<BigEndian>(entry.size)?;
         packed.write_i32::<BigEndian>(new_mtime)?;
         packed.write_i32::<BigEndian>(new_filename.len() as i32)?;
         packed.extend(new_filename)
     }
 
     if packed.len() != expected_size {
         return Err(DirstatePackError::BadSize(expected_size, packed.len()));
     }
 
     state_map.extend(new_state_map);
 
     Ok(packed)
 }
 
 #[cfg(test)]
 mod tests {
     use super::*;
-    use crate::utils::hg_path::HgPathBuf;
-    use std::collections::HashMap;
+    use crate::{utils::hg_path::HgPathBuf, FastHashMap};
 
     #[test]
     fn test_pack_dirstate_empty() {
-        let mut state_map: StateMap = HashMap::new();
-        let copymap = HashMap::new();
+        let mut state_map: StateMap = FastHashMap::default();
+        let copymap = FastHashMap::default();
         let parents = DirstateParents {
             p1: *b"12345678910111213141",
             p2: *b"00000000000000000000",
         };
         let now = Duration::new(15000000, 0);
         let expected = b"1234567891011121314100000000000000000000".to_vec();
 
         assert_eq!(
             expected,
             pack_dirstate(&mut state_map, &copymap, parents, now).unwrap()
         );
 
         assert!(state_map.is_empty())
     }
     #[test]
     fn test_pack_dirstate_one_entry() {
         let expected_state_map: StateMap = [(
             HgPathBuf::from_bytes(b"f1"),
             DirstateEntry {
                 state: EntryState::Normal,
                 mode: 0o644,
                 size: 0,
                 mtime: 791231220,
             },
         )]
         .iter()
         .cloned()
         .collect();
         let mut state_map = expected_state_map.clone();
 
-        let copymap = HashMap::new();
+        let copymap = FastHashMap::default();
         let parents = DirstateParents {
             p1: *b"12345678910111213141",
             p2: *b"00000000000000000000",
         };
         let now = Duration::new(15000000, 0);
         let expected = [
             49, 50, 51, 52, 53, 54, 55, 56, 57, 49, 48, 49, 49, 49, 50, 49,
             51, 49, 52, 49, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48,
             48, 48, 48, 48, 48, 48, 48, 48, 110, 0, 0, 1, 164, 0, 0, 0, 0, 47,
             41, 58, 244, 0, 0, 0, 2, 102, 49,
         ]
         .to_vec();
 
         assert_eq!(
             expected,
             pack_dirstate(&mut state_map, &copymap, parents, now).unwrap()
         );
 
         assert_eq!(expected_state_map, state_map);
     }
     #[test]
     fn test_pack_dirstate_one_entry_with_copy() {
         let expected_state_map: StateMap = [(
             HgPathBuf::from_bytes(b"f1"),
             DirstateEntry {
                 state: EntryState::Normal,
                 mode: 0o644,
                 size: 0,
                 mtime: 791231220,
             },
         )]
         .iter()
         .cloned()
         .collect();
         let mut state_map = expected_state_map.clone();
-        let mut copymap = HashMap::new();
+        let mut copymap = FastHashMap::default();
         copymap.insert(
             HgPathBuf::from_bytes(b"f1"),
             HgPathBuf::from_bytes(b"copyname"),
         );
         let parents = DirstateParents {
             p1: *b"12345678910111213141",
             p2: *b"00000000000000000000",
         };
         let now = Duration::new(15000000, 0);
         let expected = [
             49, 50, 51, 52, 53, 54, 55, 56, 57, 49, 48, 49, 49, 49, 50, 49,
             51, 49, 52, 49, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48,
             48, 48, 48, 48, 48, 48, 48, 48, 110, 0, 0, 1, 164, 0, 0, 0, 0, 47,
             41, 58, 244, 0, 0, 0, 11, 102, 49, 0, 99, 111, 112, 121, 110, 97,
             109, 101,
         ]
         .to_vec();
 
         assert_eq!(
             expected,
             pack_dirstate(&mut state_map, &copymap, parents, now).unwrap()
         );
         assert_eq!(expected_state_map, state_map);
     }
 
     #[test]
     fn test_parse_pack_one_entry_with_copy() {
         let mut state_map: StateMap = [(
             HgPathBuf::from_bytes(b"f1"),
             DirstateEntry {
                 state: EntryState::Normal,
                 mode: 0o644,
                 size: 0,
                 mtime: 791231220,
             },
         )]
         .iter()
         .cloned()
         .collect();
-        let mut copymap = HashMap::new();
+        let mut copymap = FastHashMap::default();
         copymap.insert(
             HgPathBuf::from_bytes(b"f1"),
             HgPathBuf::from_bytes(b"copyname"),
         );
         let parents = DirstateParents {
             p1: *b"12345678910111213141",
             p2: *b"00000000000000000000",
         };
         let now = Duration::new(15000000, 0);
         let result =
             pack_dirstate(&mut state_map, &copymap, parents.clone(), now)
                 .unwrap();
 
-        let mut new_state_map: StateMap = HashMap::new();
-        let mut new_copy_map: CopyMap = HashMap::new();
+        let mut new_state_map: StateMap = FastHashMap::default();
+        let mut new_copy_map: CopyMap = FastHashMap::default();
         let new_parents = parse_dirstate(
             &mut new_state_map,
             &mut new_copy_map,
             result.as_slice(),
         )
         .unwrap();
         assert_eq!(
             (parents, state_map, copymap),
             (new_parents, new_state_map, new_copy_map)
         )
     }
 
     #[test]
     fn test_parse_pack_multiple_entries_with_copy() {
         let mut state_map: StateMap = [
             (
                 HgPathBuf::from_bytes(b"f1"),
                 DirstateEntry {
                     state: EntryState::Normal,
                     mode: 0o644,
                     size: 0,
                     mtime: 791231220,
                 },
             ),
             (
                 HgPathBuf::from_bytes(b"f2"),
                 DirstateEntry {
                     state: EntryState::Merged,
                     mode: 0o777,
                     size: 1000,
                     mtime: 791231220,
                 },
             ),
             (
                 HgPathBuf::from_bytes(b"f3"),
                 DirstateEntry {
                     state: EntryState::Removed,
                     mode: 0o644,
                     size: 234553,
                     mtime: 791231220,
                 },
             ),
             (
                 HgPathBuf::from_bytes(b"f4\xF6"),
                 DirstateEntry {
                     state: EntryState::Added,
                     mode: 0o644,
                     size: -1,
                     mtime: -1,
                 },
             ),
         ]
         .iter()
         .cloned()
         .collect();
-        let mut copymap = HashMap::new();
+        let mut copymap = FastHashMap::default();
         copymap.insert(
             HgPathBuf::from_bytes(b"f1"),
             HgPathBuf::from_bytes(b"copyname"),
         );
         copymap.insert(
             HgPathBuf::from_bytes(b"f4\xF6"),
             HgPathBuf::from_bytes(b"copyname2"),
         );
         let parents = DirstateParents {
             p1: *b"12345678910111213141",
             p2: *b"00000000000000000000",
         };
         let now = Duration::new(15000000, 0);
         let result =
             pack_dirstate(&mut state_map, &copymap, parents.clone(), now)
                 .unwrap();
 
-        let mut new_state_map: StateMap = HashMap::new();
-        let mut new_copy_map: CopyMap = HashMap::new();
+        let mut new_state_map: StateMap = FastHashMap::default();
+        let mut new_copy_map: CopyMap = FastHashMap::default();
         let new_parents = parse_dirstate(
             &mut new_state_map,
             &mut new_copy_map,
             result.as_slice(),
         )
         .unwrap();
         assert_eq!(
             (parents, state_map, copymap),
             (new_parents, new_state_map, new_copy_map)
         )
     }
 
     #[test]
     /// https://www.mercurial-scm.org/repo/hg/rev/af3f26b6bba4
     fn test_parse_pack_one_entry_with_copy_and_time_conflict() {
         let mut state_map: StateMap = [(
             HgPathBuf::from_bytes(b"f1"),
             DirstateEntry {
                 state: EntryState::Normal,
                 mode: 0o644,
                 size: 0,
                 mtime: 15000000,
             },
         )]
         .iter()
         .cloned()
         .collect();
-        let mut copymap = HashMap::new();
+        let mut copymap = FastHashMap::default();
         copymap.insert(
             HgPathBuf::from_bytes(b"f1"),
             HgPathBuf::from_bytes(b"copyname"),
         );
         let parents = DirstateParents {
             p1: *b"12345678910111213141",
             p2: *b"00000000000000000000",
         };
         let now = Duration::new(15000000, 0);
         let result =
             pack_dirstate(&mut state_map, &copymap, parents.clone(), now)
                 .unwrap();
 
-        let mut new_state_map: StateMap = HashMap::new();
-        let mut new_copy_map: CopyMap = HashMap::new();
+        let mut new_state_map: StateMap = FastHashMap::default();
+        let mut new_copy_map: CopyMap = FastHashMap::default();
         let new_parents = parse_dirstate(
             &mut new_state_map,
             &mut new_copy_map,
             result.as_slice(),
         )
         .unwrap();
 
         assert_eq!(
             (
                 parents,
                 [(
                     HgPathBuf::from_bytes(b"f1"),
                     DirstateEntry {
                         state: EntryState::Normal,
                         mode: 0o644,
                         size: 0,
                         mtime: -1
                     }
                 )]
                 .iter()
                 .cloned()
                 .collect::<StateMap>(),
                 copymap,
             ),
             (new_parents, new_state_map, new_copy_map)
         )
     }
 }

rust/hg-core/src/discovery.rs

@@ -1,694 +1,694
 // discovery.rs
 //
 // Copyright 2019 Georges Racinet <[e-mail]>
 //
 // This software may be used and distributed according to the terms of the
 // GNU General Public License version 2 or any later version.
 
 //! Discovery operations
 //!
 //! This is a Rust counterpart to the `partialdiscovery` class of
 //! `mercurial.setdiscovery`
 
 use super::{Graph, GraphError, Revision, NULL_REVISION};
-use crate::ancestors::MissingAncestors;
-use crate::dagops;
+use crate::{ancestors::MissingAncestors, dagops, FastHashMap};
 use rand::seq::SliceRandom;
 use rand::{thread_rng, RngCore, SeedableRng};
 use std::cmp::{max, min};
-use std::collections::{HashMap, HashSet, VecDeque};
+use std::collections::{HashSet, VecDeque};
 
 type Rng = rand_pcg::Pcg32;
 
 pub struct PartialDiscovery<G: Graph + Clone> {
     target_heads: Option<Vec<Revision>>,
     graph: G, // plays the role of self._repo
     common: MissingAncestors<G>,
     undecided: Option<HashSet<Revision>>,
-    children_cache: Option<HashMap<Revision, Vec<Revision>>>,
+    children_cache: Option<FastHashMap<Revision, Vec<Revision>>>,
     missing: HashSet<Revision>,
     rng: Rng,
     respect_size: bool,
     randomize: bool,
 }
 
 pub struct DiscoveryStats {
     pub undecided: Option<usize>,
 }
 
 /// Update an existing sample to match the expected size
 ///
 /// The sample is updated with revisions exponentially distant from each
 /// element of `heads`.
 ///
 /// If a target size is specified, the sampling will stop once this size is
 /// reached. Otherwise sampling will happen until roots of the <revs> set are
 /// reached.
 ///
 /// - `revs`: set of revs we want to discover (if None, `assume` the whole dag
 ///   represented by `parentfn`
 /// - `heads`: set of DAG head revs
 /// - `sample`: a sample to update
 /// - `parentfn`: a callable to resolve parents for a revision
 /// - `quicksamplesize`: optional target size of the sample
 fn update_sample<I>(
     revs: Option<&HashSet<Revision>>,
     heads: impl IntoIterator<Item = Revision>,
     sample: &mut HashSet<Revision>,
     parentsfn: impl Fn(Revision) -> Result<I, GraphError>,
     quicksamplesize: Option<usize>,
 ) -> Result<(), GraphError>
 where
     I: Iterator<Item = Revision>,
 {
-    let mut distances: HashMap<Revision, u32> = HashMap::new();
+    let mut distances: FastHashMap<Revision, u32> = FastHashMap::default();
     let mut visit: VecDeque<Revision> = heads.into_iter().collect();
     let mut factor: u32 = 1;
     let mut seen: HashSet<Revision> = HashSet::new();
     while let Some(current) = visit.pop_front() {
         if !seen.insert(current) {
             continue;
         }
 
         let d = *distances.entry(current).or_insert(1);
         if d > factor {
             factor *= 2;
         }
         if d == factor {
             sample.insert(current);
             if let Some(sz) = quicksamplesize {
                 if sample.len() >= sz {
                     return Ok(());
                 }
             }
         }
         for p in parentsfn(current)? {
             if let Some(revs) = revs {
                 if !revs.contains(&p) {
                     continue;
                 }
             }
             distances.entry(p).or_insert(d + 1);
             visit.push_back(p);
         }
     }
     Ok(())
 }
 
 struct ParentsIterator {
     parents: [Revision; 2],
     cur: usize,
 }
 
 impl ParentsIterator {
     fn graph_parents(
         graph: &impl Graph,
         r: Revision,
     ) -> Result<ParentsIterator, GraphError> {
         Ok(ParentsIterator {
             parents: graph.parents(r)?,
             cur: 0,
         })
     }
 }
 
 impl Iterator for ParentsIterator {
     type Item = Revision;
 
     fn next(&mut self) -> Option<Revision> {
         if self.cur > 1 {
             return None;
         }
         let rev = self.parents[self.cur];
         self.cur += 1;
         if rev == NULL_REVISION {
             return self.next();
         }
         Some(rev)
     }
 }
 
 impl<G: Graph + Clone> PartialDiscovery<G> {
     /// Create a PartialDiscovery object, with the intent
     /// of comparing our `::<target_heads>` revset to the contents of another
     /// repo.
     ///
     /// For now `target_heads` is passed as a vector, and will be used
     /// at the first call to `ensure_undecided()`.
     ///
     /// If we want to make the signature more flexible,
     /// we'll have to make it a type argument of `PartialDiscovery` or a trait
     /// object since we'll keep it in the meanwhile
     ///
     /// The `respect_size` boolean controls how the sampling methods
     /// will interpret the size argument requested by the caller. If it's
     /// `false`, they are allowed to produce a sample whose size is more
     /// appropriate to the situation (typically bigger).
     ///
     /// The `randomize` boolean affects sampling, and specifically how
     /// limiting or last-minute expanding is been done:
     ///
     /// If `true`, both will perform random picking from `self.undecided`.
     /// This is currently the best for actual discoveries.
     ///
     /// If `false`, a reproductible picking strategy is performed. This is
     /// useful for integration tests.
     pub fn new(
         graph: G,
         target_heads: Vec<Revision>,
         respect_size: bool,
         randomize: bool,
     ) -> Self {
         let mut seed: [u8; 16] = [0; 16];
         if randomize {
             thread_rng().fill_bytes(&mut seed);
         }
         Self::new_with_seed(graph, target_heads, seed, respect_size, randomize)
     }
 
     pub fn new_with_seed(
         graph: G,
         target_heads: Vec<Revision>,
         seed: [u8; 16],
         respect_size: bool,
         randomize: bool,
     ) -> Self {
         PartialDiscovery {
             undecided: None,
             children_cache: None,
             target_heads: Some(target_heads),
             graph: graph.clone(),
             common: MissingAncestors::new(graph, vec![]),
             missing: HashSet::new(),
             rng: Rng::from_seed(seed),
             respect_size: respect_size,
             randomize: randomize,
         }
     }
 
     /// Extract at most `size` random elements from sample and return them
     /// as a vector
     fn limit_sample(
         &mut self,
         mut sample: Vec<Revision>,
         size: usize,
     ) -> Vec<Revision> {
         if !self.randomize {
             sample.sort();
             sample.truncate(size);
             return sample;
         }
         let sample_len = sample.len();
         if sample_len <= size {
             return sample;
         }
         let rng = &mut self.rng;
         let dropped_size = sample_len - size;
         let limited_slice = if size < dropped_size {
             sample.partial_shuffle(rng, size).0
         } else {
             sample.partial_shuffle(rng, dropped_size).1
         };
         limited_slice.to_owned()
     }
 
     /// Register revisions known as being common
     pub fn add_common_revisions(
         &mut self,
         common: impl IntoIterator<Item = Revision>,
     ) -> Result<(), GraphError> {
         let before_len = self.common.get_bases().len();
         self.common.add_bases(common);
         if self.common.get_bases().len() == before_len {
             return Ok(());
         }
         if let Some(ref mut undecided) = self.undecided {
             self.common.remove_ancestors_from(undecided)?;
         }
         Ok(())
     }
 
     /// Register revisions known as being missing
     ///
     /// # Performance note
     ///
     /// Except in the most trivial case, the first call of this method has
     /// the side effect of computing `self.undecided` set for the first time,
     /// and the related caches it might need for efficiency of its internal
     /// computation. This is typically faster if more information is
     /// available in `self.common`. Therefore, for good performance, the
     /// caller should avoid calling this too early.
     pub fn add_missing_revisions(
         &mut self,
         missing: impl IntoIterator<Item = Revision>,
     ) -> Result<(), GraphError> {
         let mut tovisit: VecDeque<Revision> = missing.into_iter().collect();
         if tovisit.is_empty() {
             return Ok(());
         }
         self.ensure_children_cache()?;
         self.ensure_undecided()?; // for safety of possible future refactors
         let children = self.children_cache.as_ref().unwrap();
         let mut seen: HashSet<Revision> = HashSet::new();
         let undecided_mut = self.undecided.as_mut().unwrap();
         while let Some(rev) = tovisit.pop_front() {
             if !self.missing.insert(rev) {
                 // either it's known to be missing from a previous
                 // invocation, and there's no need to iterate on its
                 // children (we now they are all missing)
                 // or it's from a previous iteration of this loop
                 // and its children have already been queued
                 continue;
             }
             undecided_mut.remove(&rev);
             match children.get(&rev) {
                 None => {
                     continue;
                 }
                 Some(this_children) => {
                     for child in this_children.iter().cloned() {
                         if seen.insert(child) {
                             tovisit.push_back(child);
                         }
                     }
                 }
             }
         }
         Ok(())
     }
 
     /// Do we have any information about the peer?
     pub fn has_info(&self) -> bool {
         self.common.has_bases()
     }
 
     /// Did we acquire full knowledge of our Revisions that the peer has?
     pub fn is_complete(&self) -> bool {
         self.undecided.as_ref().map_or(false, |s| s.is_empty())
     }
 
     /// Return the heads of the currently known common set of revisions.
     ///
     /// If the discovery process is not complete (see `is_complete()`), the
     /// caller must be aware that this is an intermediate state.
     ///
     /// On the other hand, if it is complete, then this is currently
     /// the only way to retrieve the end results of the discovery process.
     ///
     /// We may introduce in the future an `into_common_heads` call that
     /// would be more appropriate for normal Rust callers, dropping `self`
     /// if it is complete.
     pub fn common_heads(&self) -> Result<HashSet<Revision>, GraphError> {
         self.common.bases_heads()
     }
 
     /// Force first computation of `self.undecided`
     ///
     /// After this, `self.undecided.as_ref()` and `.as_mut()` can be
     /// unwrapped to get workable immutable or mutable references without
     /// any panic.
     ///
     /// This is an imperative call instead of an access with added lazyness
     /// to reduce easily the scope of mutable borrow for the caller,
     /// compared to undecided(&'a mut self) -> &'a… that would keep it
     /// as long as the resulting immutable one.
     fn ensure_undecided(&mut self) -> Result<(), GraphError> {
         if self.undecided.is_some() {
             return Ok(());
         }
         let tgt = self.target_heads.take().unwrap();
         self.undecided =
             Some(self.common.missing_ancestors(tgt)?.into_iter().collect());
         Ok(())
     }
 
     fn ensure_children_cache(&mut self) -> Result<(), GraphError> {
         if self.children_cache.is_some() {
             return Ok(());
         }
         self.ensure_undecided()?;
 
-        let mut children: HashMap<Revision, Vec<Revision>> = HashMap::new();
+        let mut children: FastHashMap<Revision, Vec<Revision>> =
+            FastHashMap::default();
         for &rev in self.undecided.as_ref().unwrap() {
             for p in ParentsIterator::graph_parents(&self.graph, rev)? {
                 children.entry(p).or_insert_with(|| Vec::new()).push(rev);
             }
         }
         self.children_cache = Some(children);
         Ok(())
     }
 
     /// Provide statistics about the current state of the discovery process
     pub fn stats(&self) -> DiscoveryStats {
         DiscoveryStats {
             undecided: self.undecided.as_ref().map(|s| s.len()),
         }
     }
 
     pub fn take_quick_sample(
         &mut self,
         headrevs: impl IntoIterator<Item = Revision>,
         size: usize,
     ) -> Result<Vec<Revision>, GraphError> {
         self.ensure_undecided()?;
         let mut sample = {
             let undecided = self.undecided.as_ref().unwrap();
             if undecided.len() <= size {
                 return Ok(undecided.iter().cloned().collect());
             }
             dagops::heads(&self.graph, undecided.iter())?
         };
         if sample.len() >= size {
             return Ok(self.limit_sample(sample.into_iter().collect(), size));
         }
         update_sample(
             None,
             headrevs,
             &mut sample,
             |r| ParentsIterator::graph_parents(&self.graph, r),
             Some(size),
         )?;
         Ok(sample.into_iter().collect())
     }
 
     /// Extract a sample from `self.undecided`, going from its heads and roots.
     ///
     /// The `size` parameter is used to avoid useless computations if
     /// it turns out to be bigger than the whole set of undecided Revisions.
     ///
     /// The sample is taken by using `update_sample` from the heads, then
     /// from the roots, working on the reverse DAG,
     /// expressed by `self.children_cache`.
     ///
     /// No effort is being made to complete or limit the sample to `size`
     /// but this method returns another interesting size that it derives
     /// from its knowledge of the structure of the various sets, leaving
     /// to the caller the decision to use it or not.
     fn bidirectional_sample(
         &mut self,
         size: usize,
     ) -> Result<(HashSet<Revision>, usize), GraphError> {
         self.ensure_undecided()?;
         {
             // we don't want to compute children_cache before this
             // but doing it after extracting self.undecided takes a mutable
             // ref to self while a shareable one is still active.
             let undecided = self.undecided.as_ref().unwrap();
             if undecided.len() <= size {
                 return Ok((undecided.clone(), size));
             }
         }
 
         self.ensure_children_cache()?;
         let revs = self.undecided.as_ref().unwrap();
         let mut sample: HashSet<Revision> = revs.clone();
 
         // it's possible that leveraging the children cache would be more
         // efficient here
         dagops::retain_heads(&self.graph, &mut sample)?;
         let revsheads = sample.clone(); // was again heads(revs) in python
 
         // update from heads
         update_sample(
             Some(revs),
             revsheads.iter().cloned(),
             &mut sample,
             |r| ParentsIterator::graph_parents(&self.graph, r),
             None,
         )?;
 
         // update from roots
         let revroots: HashSet<Revision> =
             dagops::roots(&self.graph, revs)?.into_iter().collect();
         let prescribed_size = max(size, min(revroots.len(), revsheads.len()));
 
         let children = self.children_cache.as_ref().unwrap();
         let empty_vec: Vec<Revision> = Vec::new();
         update_sample(
             Some(revs),
             revroots,
             &mut sample,
             |r| Ok(children.get(&r).unwrap_or(&empty_vec).iter().cloned()),
             None,
         )?;
         Ok((sample, prescribed_size))
     }
 
     /// Fill up sample up to the wished size with random undecided Revisions.
     ///
     /// This is intended to be used as a last resort completion if the
     /// regular sampling algorithm returns too few elements.
     fn random_complete_sample(
         &mut self,
         sample: &mut Vec<Revision>,
         size: usize,
     ) {
         let sample_len = sample.len();
         if size <= sample_len {
             return;
         }
         let take_from: Vec<Revision> = self
             .undecided
             .as_ref()
             .unwrap()
             .iter()
             .filter(|&r| !sample.contains(r))
             .cloned()
             .collect();
         sample.extend(self.limit_sample(take_from, size - sample_len));
     }
 
     pub fn take_full_sample(
         &mut self,
         size: usize,
     ) -> Result<Vec<Revision>, GraphError> {
         let (sample_set, prescribed_size) = self.bidirectional_sample(size)?;
         let size = if self.respect_size {
             size
         } else {
             prescribed_size
         };
         let mut sample =
             self.limit_sample(sample_set.into_iter().collect(), size);
         self.random_complete_sample(&mut sample, size);
         Ok(sample)
     }
 }
 
 #[cfg(test)]
 mod tests {
     use super::*;
     use crate::testing::SampleGraph;
 
     /// A PartialDiscovery as for pushing all the heads of `SampleGraph`
     ///
     /// To avoid actual randomness in these tests, we give it a fixed
     /// random seed, but by default we'll test the random version.
     fn full_disco() -> PartialDiscovery<SampleGraph> {
         PartialDiscovery::new_with_seed(
             SampleGraph,
             vec![10, 11, 12, 13],
             [0; 16],
             true,
             true,
         )
     }
 
     /// A PartialDiscovery as for pushing the 12 head of `SampleGraph`
     ///
     /// To avoid actual randomness in tests, we give it a fixed random seed.
     fn disco12() -> PartialDiscovery<SampleGraph> {
         PartialDiscovery::new_with_seed(
             SampleGraph,
             vec![12],
             [0; 16],
             true,
             true,
         )
     }
 
     fn sorted_undecided(
         disco: &PartialDiscovery<SampleGraph>,
     ) -> Vec<Revision> {
         let mut as_vec: Vec<Revision> =
             disco.undecided.as_ref().unwrap().iter().cloned().collect();
         as_vec.sort();
         as_vec
     }
 
     fn sorted_missing(disco: &PartialDiscovery<SampleGraph>) -> Vec<Revision> {
         let mut as_vec: Vec<Revision> =
             disco.missing.iter().cloned().collect();
         as_vec.sort();
         as_vec
     }
 
     fn sorted_common_heads(
         disco: &PartialDiscovery<SampleGraph>,
     ) -> Result<Vec<Revision>, GraphError> {
         let mut as_vec: Vec<Revision> =
             disco.common_heads()?.iter().cloned().collect();
         as_vec.sort();
         Ok(as_vec)
     }
 
     #[test]
     fn test_add_common_get_undecided() -> Result<(), GraphError> {
         let mut disco = full_disco();
         assert_eq!(disco.undecided, None);
         assert!(!disco.has_info());
         assert_eq!(disco.stats().undecided, None);
 
         disco.add_common_revisions(vec![11, 12])?;
         assert!(disco.has_info());
         assert!(!disco.is_complete());
         assert!(disco.missing.is_empty());
 
         // add_common_revisions did not trigger a premature computation
         // of `undecided`, let's check that and ask for them
         assert_eq!(disco.undecided, None);
         disco.ensure_undecided()?;
         assert_eq!(sorted_undecided(&disco), vec![5, 8, 10, 13]);
         assert_eq!(disco.stats().undecided, Some(4));
         Ok(())
     }
 
     /// in this test, we pretend that our peer misses exactly (8+10)::
     /// and we're comparing all our repo to it (as in a bare push)
     #[test]
     fn test_discovery() -> Result<(), GraphError> {
         let mut disco = full_disco();
         disco.add_common_revisions(vec![11, 12])?;
         disco.add_missing_revisions(vec![8, 10])?;
         assert_eq!(sorted_undecided(&disco), vec![5]);
         assert_eq!(sorted_missing(&disco), vec![8, 10, 13]);
         assert!(!disco.is_complete());
 
         disco.add_common_revisions(vec![5])?;
         assert_eq!(sorted_undecided(&disco), vec![]);
         assert_eq!(sorted_missing(&disco), vec![8, 10, 13]);
         assert!(disco.is_complete());
         assert_eq!(sorted_common_heads(&disco)?, vec![5, 11, 12]);
         Ok(())
     }
 
     #[test]
     fn test_add_missing_early_continue() -> Result<(), GraphError> {
         eprintln!("test_add_missing_early_stop");
         let mut disco = full_disco();
         disco.add_common_revisions(vec![13, 3, 4])?;
         disco.ensure_children_cache()?;
         // 12 is grand-child of 6 through 9
         // passing them in this order maximizes the chances of the
         // early continue to do the wrong thing
         disco.add_missing_revisions(vec![6, 9, 12])?;
         assert_eq!(sorted_undecided(&disco), vec![5, 7, 10, 11]);
         assert_eq!(sorted_missing(&disco), vec![6, 9, 12]);
         assert!(!disco.is_complete());
         Ok(())
     }
 
     #[test]
     fn test_limit_sample_no_need_to() {
         let sample = vec![1, 2, 3, 4];
         assert_eq!(full_disco().limit_sample(sample, 10), vec![1, 2, 3, 4]);
     }
 
     #[test]
     fn test_limit_sample_less_than_half() {
         assert_eq!(full_disco().limit_sample((1..6).collect(), 2), vec![4, 2]);
     }
 
     #[test]
     fn test_limit_sample_more_than_half() {
         assert_eq!(full_disco().limit_sample((1..4).collect(), 2), vec![3, 2]);
     }
 
     #[test]
     fn test_limit_sample_no_random() {
         let mut disco = full_disco();
         disco.randomize = false;
         assert_eq!(
             disco.limit_sample(vec![1, 8, 13, 5, 7, 3], 4),
             vec![1, 3, 5, 7]
         );
     }
 
     #[test]
     fn test_quick_sample_enough_undecided_heads() -> Result<(), GraphError> {
         let mut disco = full_disco();
         disco.undecided = Some((1..=13).collect());
 
         let mut sample_vec = disco.take_quick_sample(vec![], 4)?;
         sample_vec.sort();
         assert_eq!(sample_vec, vec![10, 11, 12, 13]);
         Ok(())
     }
 
     #[test]
     fn test_quick_sample_climbing_from_12() -> Result<(), GraphError> {
         let mut disco = disco12();
         disco.ensure_undecided()?;
 
         let mut sample_vec = disco.take_quick_sample(vec![12], 4)?;
         sample_vec.sort();
         // r12's only parent is r9, whose unique grand-parent through the
         // diamond shape is r4. This ends there because the distance from r4
         // to the root is only 3.
         assert_eq!(sample_vec, vec![4, 9, 12]);
         Ok(())
     }
 
     #[test]
     fn test_children_cache() -> Result<(), GraphError> {
         let mut disco = full_disco();
         disco.ensure_children_cache()?;
 
         let cache = disco.children_cache.unwrap();
         assert_eq!(cache.get(&2).cloned(), Some(vec![4]));
         assert_eq!(cache.get(&10).cloned(), None);
 
         let mut children_4 = cache.get(&4).cloned().unwrap();
         children_4.sort();
         assert_eq!(children_4, vec![5, 6, 7]);
 
         let mut children_7 = cache.get(&7).cloned().unwrap();
         children_7.sort();
         assert_eq!(children_7, vec![9, 11]);
 
         Ok(())
     }
 
     #[test]
     fn test_complete_sample() {
         let mut disco = full_disco();
         let undecided: HashSet<Revision> =
             [4, 7, 9, 2, 3].iter().cloned().collect();
         disco.undecided = Some(undecided);
 
         let mut sample = vec![0];
         disco.random_complete_sample(&mut sample, 3);
         assert_eq!(sample.len(), 3);
 
         let mut sample = vec![2, 4, 7];
         disco.random_complete_sample(&mut sample, 1);
         assert_eq!(sample.len(), 3);
     }
 
     #[test]
     fn test_bidirectional_sample() -> Result<(), GraphError> {
         let mut disco = full_disco();
         disco.undecided = Some((0..=13).into_iter().collect());
 
         let (sample_set, size) = disco.bidirectional_sample(7)?;
         assert_eq!(size, 7);
         let mut sample: Vec<Revision> = sample_set.into_iter().collect();
         sample.sort();
         // our DAG is a bit too small for the results to be really interesting
         // at least it shows that
         // - we went both ways
         // - we didn't take all Revisions (6 is not in the sample)
         assert_eq!(sample, vec![0, 1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 12, 13]);
         Ok(())
     }
 }

rust/hg-core/src/filepatterns.rs

@@ -1,379 +1,380
 // filepatterns.rs
 //
 // Copyright 2019 Raphaël Gomès <[e-mail]>
 //
 // This software may be used and distributed according to the terms of the
 // GNU General Public License version 2 or any later version.
 
 //! Handling of Mercurial-specific patterns.
 
-use crate::{utils::SliceExt, LineNumber, PatternError, PatternFileError};
+use crate::{
+    utils::SliceExt, FastHashMap, LineNumber, PatternError, PatternFileError,
+};
 use lazy_static::lazy_static;
 use regex::bytes::{NoExpand, Regex};
-use std::collections::HashMap;
 use std::fs::File;
 use std::io::Read;
 use std::path::{Path, PathBuf};
 use std::vec::Vec;
 
 lazy_static! {
     static ref RE_ESCAPE: Vec<Vec<u8>> = {
         let mut v: Vec<Vec<u8>> = (0..=255).map(|byte| vec![byte]).collect();
         let to_escape = b"()[]{}?*+-|^$\\.&~# \t\n\r\x0b\x0c";
         for byte in to_escape {
             v[*byte as usize].insert(0, b'\\');
         }
         v
     };
 }
 
 /// These are matched in order
 const GLOB_REPLACEMENTS: &[(&[u8], &[u8])] =
     &[(b"*/", b"(?:.*/)?"), (b"*", b".*"), (b"", b"[^/]*")];
 
 #[derive(Debug, Copy, Clone, PartialEq, Eq)]
 pub enum PatternSyntax {
     Regexp,
     /// Glob that matches at the front of the path
     RootGlob,
     /// Glob that matches at any suffix of the path (still anchored at
     /// slashes)
     Glob,
     Path,
     RelPath,
     RelGlob,
     RelRegexp,
     RootFiles,
 }
 
 /// Transforms a glob pattern into a regex
 fn glob_to_re(pat: &[u8]) -> Vec<u8> {
     let mut input = pat;
     let mut res: Vec<u8> = vec![];
     let mut group_depth = 0;
 
     while let Some((c, rest)) = input.split_first() {
         input = rest;
 
         match c {
             b'*' => {
                 for (source, repl) in GLOB_REPLACEMENTS {
                     if let Some(rest) = input.drop_prefix(source) {
                         input = rest;
                         res.extend(*repl);
                         break;
                     }
                 }
             }
             b'?' => res.extend(b"."),
             b'[' => {
                 match input.iter().skip(1).position(|b| *b == b']') {
                     None => res.extend(b"\\["),
                     Some(end) => {
                         // Account for the one we skipped
                         let end = end + 1;
 
                         res.extend(b"[");
 
                         for (i, b) in input[..end].iter().enumerate() {
                             if *b == b'!' && i == 0 {
                                 res.extend(b"^")
                             } else if *b == b'^' && i == 0 {
                                 res.extend(b"\\^")
                             } else if *b == b'\\' {
                                 res.extend(b"\\\\")
                             } else {
                                 res.push(*b)
                             }
                         }
                         res.extend(b"]");
                         input = &input[end + 1..];
                     }
                 }
             }
             b'{' => {
                 group_depth += 1;
                 res.extend(b"(?:")
             }
             b'}' if group_depth > 0 => {
                 group_depth -= 1;
                 res.extend(b")");
             }
             b',' if group_depth > 0 => res.extend(b"|"),
             b'\\' => {
                 let c = {
                     if let Some((c, rest)) = input.split_first() {
                         input = rest;
                         c
                     } else {
                         c
                     }
                 };
                 res.extend(&RE_ESCAPE[*c as usize])
             }
             _ => res.extend(&RE_ESCAPE[*c as usize]),
         }
     }
     res
 }
 
 fn escape_pattern(pattern: &[u8]) -> Vec<u8> {
     pattern
         .iter()
         .flat_map(|c| RE_ESCAPE[*c as usize].clone())
         .collect()
 }
 
 fn parse_pattern_syntax(kind: &[u8]) -> Result<PatternSyntax, PatternError> {
     match kind {
         b"re" => Ok(PatternSyntax::Regexp),
         b"path" => Ok(PatternSyntax::Path),
         b"relpath" => Ok(PatternSyntax::RelPath),
         b"rootfilesin" => Ok(PatternSyntax::RootFiles),
         b"relglob" => Ok(PatternSyntax::RelGlob),
         b"relre" => Ok(PatternSyntax::RelRegexp),
         b"glob" => Ok(PatternSyntax::Glob),
         b"rootglob" => Ok(PatternSyntax::RootGlob),
         _ => Err(PatternError::UnsupportedSyntax(
             String::from_utf8_lossy(kind).to_string(),
         )),
     }
 }
 
 /// Builds the regex that corresponds to the given pattern.
 /// If within a `syntax: regexp` context, returns the pattern,
 /// otherwise, returns the corresponding regex.
 fn _build_single_regex(
     syntax: PatternSyntax,
     pattern: &[u8],
     globsuffix: &[u8],
 ) -> Vec<u8> {
     if pattern.is_empty() {
         return vec![];
     }
     match syntax {
         PatternSyntax::Regexp => pattern.to_owned(),
         PatternSyntax::RelRegexp => {
             if pattern[0] == b'^' {
                 return pattern.to_owned();
             }
             [b".*", pattern].concat()
         }
         PatternSyntax::Path | PatternSyntax::RelPath => {
             if pattern == b"." {
                 return vec![];
             }
             [escape_pattern(pattern).as_slice(), b"(?:/|$)"].concat()
         }
         PatternSyntax::RootFiles => {
             let mut res = if pattern == b"." {
                 vec![]
             } else {
                 // Pattern is a directory name.
                 [escape_pattern(pattern).as_slice(), b"/"].concat()
             };
 
             // Anything after the pattern must be a non-directory.
             res.extend(b"[^/]+$");
             res
         }
         PatternSyntax::RelGlob => {
             let glob_re = glob_to_re(pattern);
             if let Some(rest) = glob_re.drop_prefix(b"[^/]*") {
                 [b".*", rest, globsuffix].concat()
             } else {
                 [b"(?:|.*/)", glob_re.as_slice(), globsuffix].concat()
             }
         }
         PatternSyntax::Glob | PatternSyntax::RootGlob => {
             [glob_to_re(pattern).as_slice(), globsuffix].concat()
         }
     }
 }
 
 const GLOB_SPECIAL_CHARACTERS: [u8; 7] =
     [b'*', b'?', b'[', b']', b'{', b'}', b'\\'];
 
 /// Wrapper function to `_build_single_regex` that short-circuits 'exact' globs
 /// that don't need to be transformed into a regex.
 pub fn build_single_regex(
     kind: &[u8],
     pat: &[u8],
     globsuffix: &[u8],
 ) -> Result<Vec<u8>, PatternError> {
     let enum_kind = parse_pattern_syntax(kind)?;
     if enum_kind == PatternSyntax::RootGlob
         && !pat.iter().any(|b| GLOB_SPECIAL_CHARACTERS.contains(b))
     {
         let mut escaped = escape_pattern(pat);
         escaped.extend(b"(?:/|$)");
         Ok(escaped)
     } else {
         Ok(_build_single_regex(enum_kind, pat, globsuffix))
     }
 }
 
 lazy_static! {
-    static ref SYNTAXES: HashMap<&'static [u8], &'static [u8]> = {
-        let mut m = HashMap::new();
+    static ref SYNTAXES: FastHashMap<&'static [u8], &'static [u8]> = {
+        let mut m = FastHashMap::default();
 
         m.insert(b"re".as_ref(), b"relre:".as_ref());
         m.insert(b"regexp".as_ref(), b"relre:".as_ref());
         m.insert(b"glob".as_ref(), b"relglob:".as_ref());
         m.insert(b"rootglob".as_ref(), b"rootglob:".as_ref());
         m.insert(b"include".as_ref(), b"include".as_ref());
         m.insert(b"subinclude".as_ref(), b"subinclude".as_ref());
         m
     };
 }
 
 pub type PatternTuple = (Vec<u8>, LineNumber, Vec<u8>);
 type WarningTuple = (PathBuf, Vec<u8>);
 
 pub fn parse_pattern_file_contents<P: AsRef<Path>>(
     lines: &[u8],
     file_path: P,
     warn: bool,
 ) -> (Vec<PatternTuple>, Vec<WarningTuple>) {
     let comment_regex = Regex::new(r"((?:^|[^\\])(?:\\\\)*)#.*").unwrap();
     let comment_escape_regex = Regex::new(r"\\#").unwrap();
     let mut inputs: Vec<PatternTuple> = vec![];
     let mut warnings: Vec<WarningTuple> = vec![];
 
     let mut current_syntax = b"relre:".as_ref();
 
     for (line_number, mut line) in lines.split(|c| *c == b'\n').enumerate() {
         let line_number = line_number + 1;
 
         let line_buf;
         if line.contains(&b'#') {
             if let Some(cap) = comment_regex.captures(line) {
                 line = &line[..cap.get(1).unwrap().end()]
             }
             line_buf = comment_escape_regex.replace_all(line, NoExpand(b"#"));
             line = &line_buf;
         }
 
         let mut line = line.trim_end();
 
         if line.is_empty() {
             continue;
         }
 
         if let Some(syntax) = line.drop_prefix(b"syntax:") {
             let syntax = syntax.trim();
 
             if let Some(rel_syntax) = SYNTAXES.get(syntax) {
                 current_syntax = rel_syntax;
             } else if warn {
                 warnings
                     .push((file_path.as_ref().to_owned(), syntax.to_owned()));
             }
             continue;
         }
 
         let mut line_syntax: &[u8] = &current_syntax;
 
         for (s, rels) in SYNTAXES.iter() {
             if let Some(rest) = line.drop_prefix(rels) {
                 line_syntax = rels;
                 line = rest;
                 break;
             }
             if let Some(rest) = line.drop_prefix(&[s, &b":"[..]].concat()) {
                 line_syntax = rels;
                 line = rest;
                 break;
             }
         }
 
         inputs.push((
             [line_syntax, line].concat(),
             line_number,
             line.to_owned(),
         ));
     }
     (inputs, warnings)
 }
 
 pub fn read_pattern_file<P: AsRef<Path>>(
     file_path: P,
     warn: bool,
 ) -> Result<(Vec<PatternTuple>, Vec<WarningTuple>), PatternFileError> {
     let mut f = File::open(file_path.as_ref())?;
     let mut contents = Vec::new();
 
     f.read_to_end(&mut contents)?;
 
     Ok(parse_pattern_file_contents(&contents, file_path, warn))
 }
 
 #[cfg(test)]
 mod tests {
     use super::*;
 
     #[test]
     fn escape_pattern_test() {
         let untouched = br#"!"%',/0123456789:;<=>@ABCDEFGHIJKLMNOPQRSTUVWXYZ_`abcdefghijklmnopqrstuvwxyz"#;
         assert_eq!(escape_pattern(untouched), untouched.to_vec());
         // All escape codes
         assert_eq!(
             escape_pattern(br#"()[]{}?*+-|^$\\.&~# \t\n\r\v\f"#),
             br#"\(\)\[\]\{\}\?\*\+\-\|\^\$\\\\\.\&\~\#\ \\t\\n\\r\\v\\f"#
                 .to_vec()
         );
     }
 
     #[test]
     fn glob_test() {
         assert_eq!(glob_to_re(br#"?"#), br#"."#);
         assert_eq!(glob_to_re(br#"*"#), br#"[^/]*"#);
         assert_eq!(glob_to_re(br#"**"#), br#".*"#);
         assert_eq!(glob_to_re(br#"**/a"#), br#"(?:.*/)?a"#);
         assert_eq!(glob_to_re(br#"a/**/b"#), br#"a/(?:.*/)?b"#);
         assert_eq!(glob_to_re(br#"[a*?!^][^b][!c]"#), br#"[a*?!^][\^b][^c]"#);
         assert_eq!(glob_to_re(br#"{a,b}"#), br#"(?:a|b)"#);
         assert_eq!(glob_to_re(br#".\*\?"#), br#"\.\*\?"#);
     }
 
     #[test]
     fn test_parse_pattern_file_contents() {
         let lines = b"syntax: glob\n*.elc";
 
         assert_eq!(
             vec![(b"relglob:*.elc".to_vec(), 2, b"*.elc".to_vec())],
             parse_pattern_file_contents(lines, Path::new("file_path"), false)
                 .0,
         );
 
         let lines = b"syntax: include\nsyntax: glob";
 
         assert_eq!(
             parse_pattern_file_contents(lines, Path::new("file_path"), false)
                 .0,
             vec![]
         );
         let lines = b"glob:**.o";
         assert_eq!(
             parse_pattern_file_contents(lines, Path::new("file_path"), false)
                 .0,
             vec![(b"relglob:**.o".to_vec(), 1, b"**.o".to_vec())]
         );
     }
 
     #[test]
     fn test_build_single_regex_shortcut() {
         assert_eq!(
             br"(?:/|$)".to_vec(),
             build_single_regex(b"rootglob", b"", b"").unwrap()
         );
         assert_eq!(
             br"whatever(?:/|$)".to_vec(),
             build_single_regex(b"rootglob", b"whatever", b"").unwrap()
         );
         assert_eq!(
             br"[^/]*\.o".to_vec(),
             build_single_regex(b"rootglob", b"*.o", b"").unwrap()
         );
     }
 }

rust/hg-core/src/lib.rs

@@ -1,166 +1,173
 // Copyright 2018 Georges Racinet <[e-mail]>
 //
 // This software may be used and distributed according to the terms of the
 // GNU General Public License version 2 or any later version.
 mod ancestors;
 pub mod dagops;
 pub use ancestors::{AncestorsIterator, LazyAncestors, MissingAncestors};
 mod dirstate;
 pub mod discovery;
 pub mod testing; // unconditionally built, for use from integration tests
 pub use dirstate::{
     dirs_multiset::{DirsMultiset, DirsMultisetIter},
     dirstate_map::DirstateMap,
     parsers::{pack_dirstate, parse_dirstate, PARENT_SIZE},
     status::status,
     CopyMap, CopyMapIter, DirstateEntry, DirstateParents, EntryState,
     StateMap, StateMapIter,
 };
 mod filepatterns;
 pub mod matchers;
 pub mod utils;
 
 use crate::utils::hg_path::HgPathBuf;
 pub use filepatterns::{
     build_single_regex, read_pattern_file, PatternSyntax, PatternTuple,
 };
+use std::collections::HashMap;
+use twox_hash::RandomXxHashBuilder64;
 
 /// Mercurial revision numbers
 ///
 /// As noted in revlog.c, revision numbers are actually encoded in
 /// 4 bytes, and are liberally converted to ints, whence the i32
 pub type Revision = i32;
 
 /// Marker expressing the absence of a parent
 ///
 /// Independently of the actual representation, `NULL_REVISION` is guaranteed
 /// to be smaller that all existing revisions.
 pub const NULL_REVISION: Revision = -1;
 
 /// Same as `mercurial.node.wdirrev`
 ///
 /// This is also equal to `i32::max_value()`, but it's better to spell
 /// it out explicitely, same as in `mercurial.node`
 pub const WORKING_DIRECTORY_REVISION: Revision = 0x7fffffff;
 
 /// The simplest expression of what we need of Mercurial DAGs.
 pub trait Graph {
     /// Return the two parents of the given `Revision`.
     ///
     /// Each of the parents can be independently `NULL_REVISION`
     fn parents(&self, rev: Revision) -> Result<[Revision; 2], GraphError>;
 }
 
 pub type LineNumber = usize;
 
+/// Rust's default hasher is too slow because it tries to prevent collision
+/// attacks. We are not concerned about those: if an ill-minded person has
+/// write access to your repository, you have other issues.
+pub type FastHashMap<K, V> = HashMap<K, V, RandomXxHashBuilder64>;
+
 #[derive(Clone, Debug, PartialEq)]
 pub enum GraphError {
     ParentOutOfRange(Revision),
     WorkingDirectoryUnsupported,
 }
 
 #[derive(Clone, Debug, PartialEq)]
 pub enum DirstateParseError {
     TooLittleData,
     Overflow,
     CorruptedEntry(String),
     Damaged,
 }
 
 impl From<std::io::Error> for DirstateParseError {
     fn from(e: std::io::Error) -> Self {
         DirstateParseError::CorruptedEntry(e.to_string())
     }
 }
 
 impl ToString for DirstateParseError {
     fn to_string(&self) -> String {
         use crate::DirstateParseError::*;
         match self {
             TooLittleData => "Too little data for dirstate.".to_string(),
             Overflow => "Overflow in dirstate.".to_string(),
             CorruptedEntry(e) => format!("Corrupted entry: {:?}.", e),
             Damaged => "Dirstate appears to be damaged.".to_string(),
         }
     }
 }
 
 #[derive(Debug, PartialEq)]
 pub enum DirstatePackError {
     CorruptedEntry(String),
     CorruptedParent,
     BadSize(usize, usize),
 }
 
 impl From<std::io::Error> for DirstatePackError {
     fn from(e: std::io::Error) -> Self {
         DirstatePackError::CorruptedEntry(e.to_string())
     }
 }
 #[derive(Debug, PartialEq)]
 pub enum DirstateMapError {
     PathNotFound(HgPathBuf),
     EmptyPath,
     ConsecutiveSlashes,
 }
 
 impl ToString for DirstateMapError {
     fn to_string(&self) -> String {
         use crate::DirstateMapError::*;
         match self {
             PathNotFound(_) => "expected a value, found none".to_string(),
             EmptyPath => "Overflow in dirstate.".to_string(),
             ConsecutiveSlashes => {
                 "found invalid consecutive slashes in path".to_string()
             }
         }
     }
 }
 
 pub enum DirstateError {
     Parse(DirstateParseError),
     Pack(DirstatePackError),
     Map(DirstateMapError),
     IO(std::io::Error),
 }
 
 impl From<DirstateParseError> for DirstateError {
     fn from(e: DirstateParseError) -> Self {
         DirstateError::Parse(e)
     }
 }
 
 impl From<DirstatePackError> for DirstateError {
     fn from(e: DirstatePackError) -> Self {
         DirstateError::Pack(e)
     }
 }
 
 #[derive(Debug)]
 pub enum PatternError {
     UnsupportedSyntax(String),
 }
 
 #[derive(Debug)]
 pub enum PatternFileError {
     IO(std::io::Error),
     Pattern(PatternError, LineNumber),
 }
 
 impl From<std::io::Error> for PatternFileError {
     fn from(e: std::io::Error) -> Self {
         PatternFileError::IO(e)
     }
 }
 
 impl From<DirstateMapError> for DirstateError {
     fn from(e: DirstateMapError) -> Self {
         DirstateError::Map(e)
     }
 }
 
 impl From<std::io::Error> for DirstateError {
     fn from(e: std::io::Error) -> Self {
         DirstateError::IO(e)
     }
 }

rust/hg-cpython/src/parsers.rs

@@ -1,175 +1,175
 // parsers.rs
 //
 // Copyright 2019 Raphaël Gomès <[e-mail]>
 //
 // This software may be used and distributed according to the terms of the
 // GNU General Public License version 2 or any later version.
 
 //! Bindings for the `hg::dirstate::parsers` module provided by the
 //! `hg-core` package.
 //!
 //! From Python, this will be seen as `mercurial.rustext.parsers`
 use cpython::{
     exc, PyBytes, PyDict, PyErr, PyInt, PyModule, PyResult, PyTuple, Python,
     PythonObject, ToPyObject,
 };
 use hg::{
     pack_dirstate, parse_dirstate, utils::hg_path::HgPathBuf,
-    DirstatePackError, DirstateParents, DirstateParseError, PARENT_SIZE,
+    DirstatePackError, DirstateParents, DirstateParseError, FastHashMap,
+    PARENT_SIZE,
 };
-use std::collections::HashMap;
 use std::convert::TryInto;
 
 use crate::dirstate::{extract_dirstate, make_dirstate_tuple};
 use std::time::Duration;
 
 fn parse_dirstate_wrapper(
     py: Python,
     dmap: PyDict,
     copymap: PyDict,
     st: PyBytes,
 ) -> PyResult<PyTuple> {
-    let mut dirstate_map = HashMap::new();
-    let mut copies = HashMap::new();
+    let mut dirstate_map = FastHashMap::default();
+    let mut copies = FastHashMap::default();
 
     match parse_dirstate(&mut dirstate_map, &mut copies, st.data(py)) {
         Ok(parents) => {
             for (filename, entry) in &dirstate_map {
                 dmap.set_item(
                     py,
                     PyBytes::new(py, filename.as_ref()),
                     make_dirstate_tuple(py, entry)?,
                 )?;
             }
             for (path, copy_path) in copies {
                 copymap.set_item(
                     py,
                     PyBytes::new(py, path.as_ref()),
                     PyBytes::new(py, copy_path.as_ref()),
                 )?;
             }
             Ok(
                 (PyBytes::new(py, &parents.p1), PyBytes::new(py, &parents.p2))
                     .to_py_object(py),
             )
         }
         Err(e) => Err(PyErr::new::<exc::ValueError, _>(
             py,
             match e {
                 DirstateParseError::TooLittleData => {
                     "too little data for parents".to_string()
                 }
                 DirstateParseError::Overflow => {
                     "overflow in dirstate".to_string()
                 }
                 DirstateParseError::CorruptedEntry(e) => e,
                 DirstateParseError::Damaged => {
                     "dirstate appears to be damaged".to_string()
                 }
             },
         )),
     }
 }
 
 fn pack_dirstate_wrapper(
     py: Python,
     dmap: PyDict,
     copymap: PyDict,
     pl: PyTuple,
     now: PyInt,
 ) -> PyResult<PyBytes> {
     let p1 = pl.get_item(py, 0).extract::<PyBytes>(py)?;
     let p1: &[u8] = p1.data(py);
     let p2 = pl.get_item(py, 1).extract::<PyBytes>(py)?;
     let p2: &[u8] = p2.data(py);
 
     let mut dirstate_map = extract_dirstate(py, &dmap)?;
 
-    let copies: Result<HashMap<HgPathBuf, HgPathBuf>, PyErr> = copymap
+    let copies: Result<FastHashMap<HgPathBuf, HgPathBuf>, PyErr> = copymap
         .items(py)
         .iter()
         .map(|(key, value)| {
             Ok((
                 HgPathBuf::from_bytes(key.extract::<PyBytes>(py)?.data(py)),
                 HgPathBuf::from_bytes(value.extract::<PyBytes>(py)?.data(py)),
             ))
         })
         .collect();
 
     if p1.len() != PARENT_SIZE || p2.len() != PARENT_SIZE {
         return Err(PyErr::new::<exc::ValueError, _>(
             py,
             "expected a 20-byte hash".to_string(),
         ));
     }
 
     match pack_dirstate(
         &mut dirstate_map,
         &copies?,
         DirstateParents {
             p1: p1.try_into().unwrap(),
             p2: p2.try_into().unwrap(),
         },
         Duration::from_secs(now.as_object().extract::<u64>(py)?),
     ) {
         Ok(packed) => {
             for (filename, entry) in &dirstate_map {
                 dmap.set_item(
                     py,
                     PyBytes::new(py, filename.as_ref()),
                     make_dirstate_tuple(py, entry)?,
                 )?;
             }
             Ok(PyBytes::new(py, &packed))
         }
         Err(error) => Err(PyErr::new::<exc::ValueError, _>(
             py,
             match error {
                 DirstatePackError::CorruptedParent => {
                     "expected a 20-byte hash".to_string()
                 }
                 DirstatePackError::CorruptedEntry(e) => e,
                 DirstatePackError::BadSize(expected, actual) => {
                     format!("bad dirstate size: {} != {}", actual, expected)
                 }
             },
         )),
     }
 }
 
 /// Create the module, with `__package__` given from parent
 pub fn init_parsers_module(py: Python, package: &str) -> PyResult<PyModule> {
     let dotted_name = &format!("{}.parsers", package);
     let m = PyModule::new(py, dotted_name)?;
 
     m.add(py, "__package__", package)?;
     m.add(py, "__doc__", "Parsers - Rust implementation")?;
 
     m.add(
         py,
         "parse_dirstate",
         py_fn!(
             py,
             parse_dirstate_wrapper(dmap: PyDict, copymap: PyDict, st: PyBytes)
         ),
     )?;
     m.add(
         py,
         "pack_dirstate",
         py_fn!(
             py,
             pack_dirstate_wrapper(
                 dmap: PyDict,
                 copymap: PyDict,
                 pl: PyTuple,
                 now: PyInt
             )
         ),
     )?;
 
     let sys = PyModule::import(py, "sys")?;
     let sys_modules: PyDict = sys.get(py, "modules")?.extract(py)?;
     sys_modules.set_item(py, dotted_name, &m)?;
 
     Ok(m)
 }