annotate rust/hg-core/src/dirstate.rs @ 45562:b51167d70f5a

rust: add `dirstate_tree` module Mercurial needs to represent the filesystem hierarchy on which it operates, for example in the dirstate. Its current on-disk representation is an unsorted, flat structure that gets transformed in the current Rust code into a `HashMap`. This loses the hierarchical information of the dirstate, leading to some unfortunate performance and algorithmic compromises. This module adds an implementation of a radix tree that is specialized for representing the dirstate: its unit is the path component. I have made no efforts to optimize either its memory footprint or its insertion speed: they're pretty bad for now. Following will be a few patches that modify the dirstate.status logic to use that new hierarchical information, fixing issue 6335 in the same swing. Differential Revision: https://phab.mercurial-scm.org/D9085
author Raphaël Gomès <rgomes@octobus.net>
date Fri, 25 Sep 2020 17:51:34 +0200
parents 5ac243a92e37
children e604a3c03ab9
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
42748
7cae6bc29ff9 rust-parsers: switch to parse/pack_dirstate to mutate-on-loop
Raphaël Gomès <rgomes@octobus.net>
parents: 42609
diff changeset
1 // dirstate module
7cae6bc29ff9 rust-parsers: switch to parse/pack_dirstate to mutate-on-loop
Raphaël Gomès <rgomes@octobus.net>
parents: 42609
diff changeset
2 //
7cae6bc29ff9 rust-parsers: switch to parse/pack_dirstate to mutate-on-loop
Raphaël Gomès <rgomes@octobus.net>
parents: 42609
diff changeset
3 // Copyright 2019 Raphaël Gomès <rgomes@octobus.net>
7cae6bc29ff9 rust-parsers: switch to parse/pack_dirstate to mutate-on-loop
Raphaël Gomès <rgomes@octobus.net>
parents: 42609
diff changeset
4 //
7cae6bc29ff9 rust-parsers: switch to parse/pack_dirstate to mutate-on-loop
Raphaël Gomès <rgomes@octobus.net>
parents: 42609
diff changeset
5 // This software may be used and distributed according to the terms of the
7cae6bc29ff9 rust-parsers: switch to parse/pack_dirstate to mutate-on-loop
Raphaël Gomès <rgomes@octobus.net>
parents: 42609
diff changeset
6 // GNU General Public License version 2 or any later version.
7cae6bc29ff9 rust-parsers: switch to parse/pack_dirstate to mutate-on-loop
Raphaël Gomès <rgomes@octobus.net>
parents: 42609
diff changeset
7
43826
5ac243a92e37 rust-performance: introduce FastHashMap type alias for HashMap
Raphaël Gomès <rgomes@octobus.net>
parents: 43605
diff changeset
8 use crate::{utils::hg_path::HgPathBuf, DirstateParseError, FastHashMap};
42886
7083ac37314f rust-dirstate: provide CopyMapIter and StateMapIter types
Yuya Nishihara <yuya@tcha.org>
parents: 42802
diff changeset
9 use std::collections::hash_map;
42749
7ceded4419a3 rust-dirstate: use EntryState enum instead of literals
Raphaël Gomès <rgomes@octobus.net>
parents: 42748
diff changeset
10 use std::convert::TryFrom;
42748
7cae6bc29ff9 rust-parsers: switch to parse/pack_dirstate to mutate-on-loop
Raphaël Gomès <rgomes@octobus.net>
parents: 42609
diff changeset
11
42536
2dcee6497b0b rust-dirstate: add "dirs" Rust implementation
Raphaël Gomès <rgomes@octobus.net>
parents: 42424
diff changeset
12 pub mod dirs_multiset;
42753
fce6dc93a510 rust-dirstate: rust implementation of dirstatemap
Raphaël Gomès <rgomes@octobus.net>
parents: 42749
diff changeset
13 pub mod dirstate_map;
45562
b51167d70f5a rust: add `dirstate_tree` module
Raphaël Gomès <rgomes@octobus.net>
parents: 43826
diff changeset
14 pub mod dirstate_tree;
42424
d3b5cbe311d9 rust-dirstate: create dirstate submodule
Raphaël Gomès <rgomes@octobus.net>
parents:
diff changeset
15 pub mod parsers;
43271
99394e6c5d12 rust-dirstate-status: add first Rust implementation of `dirstate.status`
Raphaël Gomès <rgomes@octobus.net>
parents: 42957
diff changeset
16 pub mod status;
42424
d3b5cbe311d9 rust-dirstate: create dirstate submodule
Raphaël Gomès <rgomes@octobus.net>
parents:
diff changeset
17
42748
7cae6bc29ff9 rust-parsers: switch to parse/pack_dirstate to mutate-on-loop
Raphaël Gomès <rgomes@octobus.net>
parents: 42609
diff changeset
18 #[derive(Debug, PartialEq, Clone)]
7cae6bc29ff9 rust-parsers: switch to parse/pack_dirstate to mutate-on-loop
Raphaël Gomès <rgomes@octobus.net>
parents: 42609
diff changeset
19 pub struct DirstateParents {
7cae6bc29ff9 rust-parsers: switch to parse/pack_dirstate to mutate-on-loop
Raphaël Gomès <rgomes@octobus.net>
parents: 42609
diff changeset
20 pub p1: [u8; 20],
7cae6bc29ff9 rust-parsers: switch to parse/pack_dirstate to mutate-on-loop
Raphaël Gomès <rgomes@octobus.net>
parents: 42609
diff changeset
21 pub p2: [u8; 20],
42424
d3b5cbe311d9 rust-dirstate: create dirstate submodule
Raphaël Gomès <rgomes@octobus.net>
parents:
diff changeset
22 }
d3b5cbe311d9 rust-dirstate: create dirstate submodule
Raphaël Gomès <rgomes@octobus.net>
parents:
diff changeset
23
d3b5cbe311d9 rust-dirstate: create dirstate submodule
Raphaël Gomès <rgomes@octobus.net>
parents:
diff changeset
24 /// The C implementation uses all signed types. This will be an issue
d3b5cbe311d9 rust-dirstate: create dirstate submodule
Raphaël Gomès <rgomes@octobus.net>
parents:
diff changeset
25 /// either when 4GB+ source files are commonplace or in 2038, whichever
d3b5cbe311d9 rust-dirstate: create dirstate submodule
Raphaël Gomès <rgomes@octobus.net>
parents:
diff changeset
26 /// comes first.
42748
7cae6bc29ff9 rust-parsers: switch to parse/pack_dirstate to mutate-on-loop
Raphaël Gomès <rgomes@octobus.net>
parents: 42609
diff changeset
27 #[derive(Debug, PartialEq, Copy, Clone)]
42424
d3b5cbe311d9 rust-dirstate: create dirstate submodule
Raphaël Gomès <rgomes@octobus.net>
parents:
diff changeset
28 pub struct DirstateEntry {
42749
7ceded4419a3 rust-dirstate: use EntryState enum instead of literals
Raphaël Gomès <rgomes@octobus.net>
parents: 42748
diff changeset
29 pub state: EntryState,
42424
d3b5cbe311d9 rust-dirstate: create dirstate submodule
Raphaël Gomès <rgomes@octobus.net>
parents:
diff changeset
30 pub mode: i32,
d3b5cbe311d9 rust-dirstate: create dirstate submodule
Raphaël Gomès <rgomes@octobus.net>
parents:
diff changeset
31 pub mtime: i32,
d3b5cbe311d9 rust-dirstate: create dirstate submodule
Raphaël Gomès <rgomes@octobus.net>
parents:
diff changeset
32 pub size: i32,
d3b5cbe311d9 rust-dirstate: create dirstate submodule
Raphaël Gomès <rgomes@octobus.net>
parents:
diff changeset
33 }
d3b5cbe311d9 rust-dirstate: create dirstate submodule
Raphaël Gomès <rgomes@octobus.net>
parents:
diff changeset
34
43605
8210c3f46912 rust: introduce SIZE_FROM_OTHER_PARENT constant
Raphaël Gomès <rgomes@octobus.net>
parents: 43271
diff changeset
35 /// A `DirstateEntry` with a size of `-2` means that it was merged from the
8210c3f46912 rust: introduce SIZE_FROM_OTHER_PARENT constant
Raphaël Gomès <rgomes@octobus.net>
parents: 43271
diff changeset
36 /// other parent. This allows revert to pick the right status back during a
8210c3f46912 rust: introduce SIZE_FROM_OTHER_PARENT constant
Raphaël Gomès <rgomes@octobus.net>
parents: 43271
diff changeset
37 /// merge.
8210c3f46912 rust: introduce SIZE_FROM_OTHER_PARENT constant
Raphaël Gomès <rgomes@octobus.net>
parents: 43271
diff changeset
38 pub const SIZE_FROM_OTHER_PARENT: i32 = -2;
8210c3f46912 rust: introduce SIZE_FROM_OTHER_PARENT constant
Raphaël Gomès <rgomes@octobus.net>
parents: 43271
diff changeset
39
43826
5ac243a92e37 rust-performance: introduce FastHashMap type alias for HashMap
Raphaël Gomès <rgomes@octobus.net>
parents: 43605
diff changeset
40 pub type StateMap = FastHashMap<HgPathBuf, DirstateEntry>;
42957
7a01778bc7b7 rust-hgpath: replace all paths and filenames with HgPath/HgPathBuf
Raphaël Gomès <rgomes@octobus.net>
parents: 42886
diff changeset
41 pub type StateMapIter<'a> = hash_map::Iter<'a, HgPathBuf, DirstateEntry>;
43826
5ac243a92e37 rust-performance: introduce FastHashMap type alias for HashMap
Raphaël Gomès <rgomes@octobus.net>
parents: 43605
diff changeset
42 pub type CopyMap = FastHashMap<HgPathBuf, HgPathBuf>;
42957
7a01778bc7b7 rust-hgpath: replace all paths and filenames with HgPath/HgPathBuf
Raphaël Gomès <rgomes@octobus.net>
parents: 42886
diff changeset
43 pub type CopyMapIter<'a> = hash_map::Iter<'a, HgPathBuf, HgPathBuf>;
42536
2dcee6497b0b rust-dirstate: add "dirs" Rust implementation
Raphaël Gomès <rgomes@octobus.net>
parents: 42424
diff changeset
44
42749
7ceded4419a3 rust-dirstate: use EntryState enum instead of literals
Raphaël Gomès <rgomes@octobus.net>
parents: 42748
diff changeset
45 #[derive(Copy, Clone, Debug, Eq, PartialEq)]
7ceded4419a3 rust-dirstate: use EntryState enum instead of literals
Raphaël Gomès <rgomes@octobus.net>
parents: 42748
diff changeset
46 pub enum EntryState {
7ceded4419a3 rust-dirstate: use EntryState enum instead of literals
Raphaël Gomès <rgomes@octobus.net>
parents: 42748
diff changeset
47 Normal,
7ceded4419a3 rust-dirstate: use EntryState enum instead of literals
Raphaël Gomès <rgomes@octobus.net>
parents: 42748
diff changeset
48 Added,
7ceded4419a3 rust-dirstate: use EntryState enum instead of literals
Raphaël Gomès <rgomes@octobus.net>
parents: 42748
diff changeset
49 Removed,
7ceded4419a3 rust-dirstate: use EntryState enum instead of literals
Raphaël Gomès <rgomes@octobus.net>
parents: 42748
diff changeset
50 Merged,
7ceded4419a3 rust-dirstate: use EntryState enum instead of literals
Raphaël Gomès <rgomes@octobus.net>
parents: 42748
diff changeset
51 Unknown,
7ceded4419a3 rust-dirstate: use EntryState enum instead of literals
Raphaël Gomès <rgomes@octobus.net>
parents: 42748
diff changeset
52 }
7ceded4419a3 rust-dirstate: use EntryState enum instead of literals
Raphaël Gomès <rgomes@octobus.net>
parents: 42748
diff changeset
53
7ceded4419a3 rust-dirstate: use EntryState enum instead of literals
Raphaël Gomès <rgomes@octobus.net>
parents: 42748
diff changeset
54 impl TryFrom<u8> for EntryState {
7ceded4419a3 rust-dirstate: use EntryState enum instead of literals
Raphaël Gomès <rgomes@octobus.net>
parents: 42748
diff changeset
55 type Error = DirstateParseError;
7ceded4419a3 rust-dirstate: use EntryState enum instead of literals
Raphaël Gomès <rgomes@octobus.net>
parents: 42748
diff changeset
56
7ceded4419a3 rust-dirstate: use EntryState enum instead of literals
Raphaël Gomès <rgomes@octobus.net>
parents: 42748
diff changeset
57 fn try_from(value: u8) -> Result<Self, Self::Error> {
7ceded4419a3 rust-dirstate: use EntryState enum instead of literals
Raphaël Gomès <rgomes@octobus.net>
parents: 42748
diff changeset
58 match value {
7ceded4419a3 rust-dirstate: use EntryState enum instead of literals
Raphaël Gomès <rgomes@octobus.net>
parents: 42748
diff changeset
59 b'n' => Ok(EntryState::Normal),
7ceded4419a3 rust-dirstate: use EntryState enum instead of literals
Raphaël Gomès <rgomes@octobus.net>
parents: 42748
diff changeset
60 b'a' => Ok(EntryState::Added),
7ceded4419a3 rust-dirstate: use EntryState enum instead of literals
Raphaël Gomès <rgomes@octobus.net>
parents: 42748
diff changeset
61 b'r' => Ok(EntryState::Removed),
7ceded4419a3 rust-dirstate: use EntryState enum instead of literals
Raphaël Gomès <rgomes@octobus.net>
parents: 42748
diff changeset
62 b'm' => Ok(EntryState::Merged),
7ceded4419a3 rust-dirstate: use EntryState enum instead of literals
Raphaël Gomès <rgomes@octobus.net>
parents: 42748
diff changeset
63 b'?' => Ok(EntryState::Unknown),
7ceded4419a3 rust-dirstate: use EntryState enum instead of literals
Raphaël Gomès <rgomes@octobus.net>
parents: 42748
diff changeset
64 _ => Err(DirstateParseError::CorruptedEntry(format!(
7ceded4419a3 rust-dirstate: use EntryState enum instead of literals
Raphaël Gomès <rgomes@octobus.net>
parents: 42748
diff changeset
65 "Incorrect entry state {}",
7ceded4419a3 rust-dirstate: use EntryState enum instead of literals
Raphaël Gomès <rgomes@octobus.net>
parents: 42748
diff changeset
66 value
7ceded4419a3 rust-dirstate: use EntryState enum instead of literals
Raphaël Gomès <rgomes@octobus.net>
parents: 42748
diff changeset
67 ))),
7ceded4419a3 rust-dirstate: use EntryState enum instead of literals
Raphaël Gomès <rgomes@octobus.net>
parents: 42748
diff changeset
68 }
7ceded4419a3 rust-dirstate: use EntryState enum instead of literals
Raphaël Gomès <rgomes@octobus.net>
parents: 42748
diff changeset
69 }
7ceded4419a3 rust-dirstate: use EntryState enum instead of literals
Raphaël Gomès <rgomes@octobus.net>
parents: 42748
diff changeset
70 }
7ceded4419a3 rust-dirstate: use EntryState enum instead of literals
Raphaël Gomès <rgomes@octobus.net>
parents: 42748
diff changeset
71
7ceded4419a3 rust-dirstate: use EntryState enum instead of literals
Raphaël Gomès <rgomes@octobus.net>
parents: 42748
diff changeset
72 impl Into<u8> for EntryState {
7ceded4419a3 rust-dirstate: use EntryState enum instead of literals
Raphaël Gomès <rgomes@octobus.net>
parents: 42748
diff changeset
73 fn into(self) -> u8 {
7ceded4419a3 rust-dirstate: use EntryState enum instead of literals
Raphaël Gomès <rgomes@octobus.net>
parents: 42748
diff changeset
74 match self {
7ceded4419a3 rust-dirstate: use EntryState enum instead of literals
Raphaël Gomès <rgomes@octobus.net>
parents: 42748
diff changeset
75 EntryState::Normal => b'n',
7ceded4419a3 rust-dirstate: use EntryState enum instead of literals
Raphaël Gomès <rgomes@octobus.net>
parents: 42748
diff changeset
76 EntryState::Added => b'a',
7ceded4419a3 rust-dirstate: use EntryState enum instead of literals
Raphaël Gomès <rgomes@octobus.net>
parents: 42748
diff changeset
77 EntryState::Removed => b'r',
7ceded4419a3 rust-dirstate: use EntryState enum instead of literals
Raphaël Gomès <rgomes@octobus.net>
parents: 42748
diff changeset
78 EntryState::Merged => b'm',
7ceded4419a3 rust-dirstate: use EntryState enum instead of literals
Raphaël Gomès <rgomes@octobus.net>
parents: 42748
diff changeset
79 EntryState::Unknown => b'?',
7ceded4419a3 rust-dirstate: use EntryState enum instead of literals
Raphaël Gomès <rgomes@octobus.net>
parents: 42748
diff changeset
80 }
7ceded4419a3 rust-dirstate: use EntryState enum instead of literals
Raphaël Gomès <rgomes@octobus.net>
parents: 42748
diff changeset
81 }
7ceded4419a3 rust-dirstate: use EntryState enum instead of literals
Raphaël Gomès <rgomes@octobus.net>
parents: 42748
diff changeset
82 }