This is an archive of the discontinued Mercurial Phabricator instance.

Differential D10329

rust: Remove the compile-time 'dirstate-tree' feature flag
ClosedPublic

Authored by SimonSapin on Apr 8 2021, 3:52 PM.

Details

Reviewers
marmoute
pulkit
Group Reviewers
hg-reviewers
Commits
rHG441024b279a6: rust: Remove the compile-time 'dirstate-tree' feature flag
Summary

This code has compiler errors since it is not built on CI and nobody has been
working on it for some time.

We (Octobus) are still pursuing status optimizations based on a tree data
structure for the dirstate, but upcoming patches will use a run-time opt-in
instead of compile-time, so that at least corresponding Rust code keeps
compiling when other changes are made.

Diff Detail

Repository
rHG Mercurial
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

SimonSapin created this revision.Apr 8 2021, 3:52 PM
marmoute accepted this revision.Apr 8 2021, 11:36 PM
marmoute added a subscriber: marmoute.

This is all true.

pulkit accepted this revision.Apr 11 2021, 5:26 PM
This revision is now accepted and ready to land.Apr 11 2021, 5:26 PM

Revision Contents
Changeset List

Diff 26802

rust/hg-core/Cargo.toml

version = "1.0.16" version = "1.0.16"
features = ["zlib"] features = ["zlib"]
default-features = false default-features = false
[dev-dependencies] [dev-dependencies]
clap = "*" clap = "*"
pretty_assertions = "0.6.1" pretty_assertions = "0.6.1"
tempfile = "3.1.0" tempfile = "3.1.0"
[features]
# Use a (still unoptimized) tree for the dirstate instead of the current flat
# dirstate. This is not yet recommended for performance reasons. A future
# version might make it the default, or make it a runtime option.
dirstate-tree = []

rust/hg-core/src/dirstate.rs

// dirstate module // dirstate module
// //
// Copyright 2019 Raphaël Gomès <rgomes@octobus.net> // Copyright 2019 Raphaël Gomès <rgomes@octobus.net>
// //
// This software may be used and distributed according to the terms of the // This software may be used and distributed according to the terms of the
// GNU General Public License version 2 or any later version. // GNU General Public License version 2 or any later version.
use crate::errors::HgError; use crate::errors::HgError;
use crate::revlog::Node; use crate::revlog::Node;
use crate::{utils::hg_path::HgPathBuf, FastHashMap}; use crate::{utils::hg_path::HgPathBuf, FastHashMap};
use bytes_cast::{unaligned, BytesCast}; use bytes_cast::{unaligned, BytesCast};
use std::collections::hash_map; use std::collections::hash_map;
use std::convert::TryFrom; use std::convert::TryFrom;
pub mod dirs_multiset; pub mod dirs_multiset;
pub mod dirstate_map; pub mod dirstate_map;
#[cfg(feature = "dirstate-tree")]
pub mod dirstate_tree;
pub mod parsers; pub mod parsers;
pub mod status; pub mod status;
#[derive(Debug, PartialEq, Clone, BytesCast)] #[derive(Debug, PartialEq, Clone, BytesCast)]
#[repr(C)] #[repr(C)]
pub struct DirstateParents { pub struct DirstateParents {
pub p1: Node, pub p1: Node,
pub p2: Node, pub p2: Node,
length: unaligned::I32Be, length: unaligned::I32Be,
} }
/// A `DirstateEntry` with a size of `-2` means that it was merged from the /// 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 /// other parent. This allows revert to pick the right status back during a
/// merge. /// merge.
pub const SIZE_FROM_OTHER_PARENT: i32 = -2; pub const SIZE_FROM_OTHER_PARENT: i32 = -2;
#[cfg(not(feature = "dirstate-tree"))]
pub type StateMap = FastHashMap<HgPathBuf, DirstateEntry>; pub type StateMap = FastHashMap<HgPathBuf, DirstateEntry>;
#[cfg(not(feature = "dirstate-tree"))]
pub type StateMapIter<'a> = hash_map::Iter<'a, HgPathBuf, DirstateEntry>; pub type StateMapIter<'a> = hash_map::Iter<'a, HgPathBuf, DirstateEntry>;
#[cfg(feature = "dirstate-tree")]
pub type StateMap = dirstate_tree::tree::Tree;
#[cfg(feature = "dirstate-tree")]
pub type StateMapIter<'a> = dirstate_tree::iter::Iter<'a>;
pub type CopyMap = FastHashMap<HgPathBuf, HgPathBuf>; pub type CopyMap = FastHashMap<HgPathBuf, HgPathBuf>;
pub type CopyMapIter<'a> = hash_map::Iter<'a, HgPathBuf, HgPathBuf>; pub type CopyMapIter<'a> = hash_map::Iter<'a, HgPathBuf, HgPathBuf>;
#[derive(Copy, Clone, Debug, Eq, PartialEq)] #[derive(Copy, Clone, Debug, Eq, PartialEq)]
pub enum EntryState { pub enum EntryState {
Normal, Normal,
Added, Added,
Removed, Removed,

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

pub struct DirsMultiset { pub struct DirsMultiset {
inner: FastHashMap<HgPathBuf, u32>, inner: FastHashMap<HgPathBuf, u32>,
} }
impl DirsMultiset { impl DirsMultiset {
/// Initializes the multiset from a dirstate. /// Initializes the multiset from a dirstate.
/// ///
/// If `skip_state` is provided, skips dirstate entries with equal state. /// If `skip_state` is provided, skips dirstate entries with equal state.
#[cfg(not(feature = "dirstate-tree"))]
pub fn from_dirstate( pub fn from_dirstate(
dirstate: &StateMap, dirstate: &StateMap,
skip_state: Option<EntryState>, skip_state: Option<EntryState>,
) -> Result<Self, DirstateMapError> { ) -> Result<Self, DirstateMapError> {
let mut multiset = DirsMultiset { let mut multiset = DirsMultiset {
inner: FastHashMap::default(), inner: FastHashMap::default(),
}; };
for (filename, DirstateEntry { state, .. }) in dirstate.iter() { for (filename, DirstateEntry { state, .. }) in dirstate.iter() {
// This `if` is optimized out of the loop // This `if` is optimized out of the loop
if let Some(skip) = skip_state { if let Some(skip) = skip_state {
if skip != *state { if skip != *state {
multiset.add_path(filename)?; multiset.add_path(filename)?;
} }
} else { } else {
multiset.add_path(filename)?; multiset.add_path(filename)?;
} }
} }
Ok(multiset) Ok(multiset)
} }
/// Initializes the multiset from a dirstate.
///
/// If `skip_state` is provided, skips dirstate entries with equal state.
#[cfg(feature = "dirstate-tree")]
pub fn from_dirstate(
dirstate: &StateMap,
skip_state: Option<EntryState>,
) -> Result<Self, DirstateMapError> {
let mut multiset = DirsMultiset {
inner: FastHashMap::default(),
};
for (filename, DirstateEntry { state, .. }) in dirstate.iter() {
// 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)?;
}
}
Ok(multiset)
}
/// Initializes the multiset from a manifest. /// Initializes the multiset from a manifest.
pub fn from_manifest( pub fn from_manifest(
manifest: &[impl AsRef<HgPath>], manifest: &[impl AsRef<HgPath>],
) -> Result<Self, DirstateMapError> { ) -> Result<Self, DirstateMapError> {
let mut multiset = DirsMultiset { let mut multiset = DirsMultiset {
inner: FastHashMap::default(), inner: FastHashMap::default(),
}; };

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

&self, &self,
) -> (&HashSet<HgPathBuf>, &HashSet<HgPathBuf>) { ) -> (&HashSet<HgPathBuf>, &HashSet<HgPathBuf>) {
( (
self.non_normal_set.as_ref().unwrap(), self.non_normal_set.as_ref().unwrap(),
self.other_parent_set.as_ref().unwrap(), self.other_parent_set.as_ref().unwrap(),
) )
} }
#[cfg(not(feature = "dirstate-tree"))]
pub fn set_non_normal_other_parent_entries(&mut self, force: bool) { pub fn set_non_normal_other_parent_entries(&mut self, force: bool) {
if !force if !force
&& self.non_normal_set.is_some() && self.non_normal_set.is_some()
&& self.other_parent_set.is_some() && self.other_parent_set.is_some()
{ {
return; return;
} }
let mut non_normal = HashSet::new(); let mut non_normal = HashSet::new();
if *state == EntryState::Normal && *size == SIZE_FROM_OTHER_PARENT if *state == EntryState::Normal && *size == SIZE_FROM_OTHER_PARENT
{ {
other_parent.insert(filename.to_owned()); other_parent.insert(filename.to_owned());
} }
} }
self.non_normal_set = Some(non_normal); self.non_normal_set = Some(non_normal);
self.other_parent_set = Some(other_parent); self.other_parent_set = Some(other_parent);
} }
#[cfg(feature = "dirstate-tree")]
pub fn set_non_normal_other_parent_entries(&mut self, force: bool) {
if !force
&& self.non_normal_set.is_some()
&& self.other_parent_set.is_some()
{
return;
}
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());
}
}
self.non_normal_set = Some(non_normal);
self.other_parent_set = Some(other_parent);
}
/// Both of these setters and their uses appear to be the simplest way to /// 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. /// emulate a Python lazy property, but it is ugly and unidiomatic.
/// TODO One day, rewriting this struct using the typestate might be a /// TODO One day, rewriting this struct using the typestate might be a
/// good idea. /// good idea.
pub fn set_all_dirs(&mut self) -> Result<(), DirstateMapError> { pub fn set_all_dirs(&mut self) -> Result<(), DirstateMapError> {
if self.all_dirs.is_none() { if self.all_dirs.is_none() {
self.all_dirs = self.all_dirs =
let packed = let packed =
pack_dirstate(&mut self.state_map, &self.copy_map, parents, now)?; pack_dirstate(&mut self.state_map, &self.copy_map, parents, now)?;
self.dirty_parents = false; self.dirty_parents = false;
self.set_non_normal_other_parent_entries(true); self.set_non_normal_other_parent_entries(true);
Ok(packed) Ok(packed)
} }
#[cfg(not(feature = "dirstate-tree"))]
pub fn build_file_fold_map(&mut self) -> &FileFoldMap { pub fn build_file_fold_map(&mut self) -> &FileFoldMap {
if let Some(ref file_fold_map) = self.file_fold_map { if let Some(ref file_fold_map) = self.file_fold_map {
return file_fold_map; return file_fold_map;
} }
let mut new_file_fold_map = FileFoldMap::default(); let mut new_file_fold_map = FileFoldMap::default();
for (filename, DirstateEntry { state, .. }) in self.state_map.iter() { for (filename, DirstateEntry { state, .. }) in self.state_map.iter() {
if *state != EntryState::Removed { if *state != EntryState::Removed {
new_file_fold_map new_file_fold_map
.insert(normalize_case(&filename), filename.to_owned()); .insert(normalize_case(&filename), filename.to_owned());
} }
} }
self.file_fold_map = Some(new_file_fold_map); self.file_fold_map = Some(new_file_fold_map);
self.file_fold_map.as_ref().unwrap() self.file_fold_map.as_ref().unwrap()
} }
#[cfg(feature = "dirstate-tree")]
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::default();
for (filename, DirstateEntry { state, .. }) in self.state_map.iter() {
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)] #[cfg(test)]
mod tests { mod tests {
use super::*; use super::*;
#[test] #[test]
fn test_dirs_multiset() { fn test_dirs_multiset() {

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

  • This file was deleted.
// dirstate_tree.rs
//
// Copyright 2020, Raphaël Gomès <rgomes@octobus.net>
//
// This software may be used and distributed according to the terms of the
// GNU General Public License version 2 or any later version.
//! Special-case radix tree that matches a filesystem hierarchy for use in the
//! dirstate.
//! It has not been optimized at all yet.
pub mod iter;
pub mod node;
pub mod tree;

rust/hg-core/src/dirstate/dirstate_tree/iter.rs

  • This file was deleted.
// iter.rs
//
// Copyright 2020, Raphaël Gomès <rgomes@octobus.net>
//
// This software may be used and distributed according to the terms of the
// GNU General Public License version 2 or any later version.
use super::node::{Node, NodeKind};
use super::tree::Tree;
use crate::dirstate::dirstate_tree::node::Directory;
use crate::dirstate::status::Dispatch;
use crate::utils::hg_path::{hg_path_to_path_buf, HgPath, HgPathBuf};
use crate::DirstateEntry;
use std::borrow::Cow;
use std::collections::VecDeque;
use std::iter::{FromIterator, FusedIterator};
use std::path::PathBuf;
impl FromIterator<(HgPathBuf, DirstateEntry)> for Tree {
fn from_iter<T: IntoIterator<Item = (HgPathBuf, DirstateEntry)>>(
iter: T,
) -> Self {
let mut tree = Self::new();
for (path, entry) in iter {
tree.insert(path, entry);
}
tree
}
}
/// Iterator of all entries in the dirstate tree.
///
/// It has no particular ordering.
pub struct Iter<'a> {
to_visit: VecDeque<(Cow<'a, [u8]>, &'a Node)>,
}
impl<'a> Iter<'a> {
pub fn new(node: &'a Node) -> Iter<'a> {
let mut to_visit = VecDeque::new();
to_visit.push_back((Cow::Borrowed(&b""[..]), node));
Self { to_visit }
}
}
impl<'a> Iterator for Iter<'a> {
type Item = (HgPathBuf, DirstateEntry);
fn next(&mut self) -> Option<Self::Item> {
while let Some((base_path, node)) = self.to_visit.pop_front() {
match &node.kind {
NodeKind::Directory(dir) => {
add_children_to_visit(
&mut self.to_visit,
&base_path,
&dir,
);
if let Some(file) = &dir.was_file {
return Some((
HgPathBuf::from_bytes(&base_path),
file.entry,
));
}
}
NodeKind::File(file) => {
if let Some(dir) = &file.was_directory {
add_children_to_visit(
&mut self.to_visit,
&base_path,
&dir,
);
}
return Some((
HgPathBuf::from_bytes(&base_path),
file.entry,
));
}
}
}
None
}
}
impl<'a> FusedIterator for Iter<'a> {}
/// Iterator of all entries in the dirstate tree, with a special filesystem
/// handling for the directories containing said entries.
///
/// It checks every directory on-disk to see if it has become a symlink, to
/// prevent a potential security issue.
/// Using this information, it may dispatch `status` information early: it
/// returns canonical paths along with `Shortcut`s, which are either a
/// `DirstateEntry` or a `Dispatch`, if the fate of said path has already been
/// determined.
///
/// Like `Iter`, it has no particular ordering.
pub struct FsIter<'a> {
root_dir: PathBuf,
to_visit: VecDeque<(Cow<'a, [u8]>, &'a Node)>,
shortcuts: VecDeque<(HgPathBuf, StatusShortcut)>,
}
impl<'a> FsIter<'a> {
pub fn new(node: &'a Node, root_dir: PathBuf) -> FsIter<'a> {
let mut to_visit = VecDeque::new();
to_visit.push_back((Cow::Borrowed(&b""[..]), node));
Self {
root_dir,
to_visit,
shortcuts: Default::default(),
}
}
/// Mercurial tracks symlinks but *not* what they point to.
/// If a directory is moved and symlinked:
///
/// ```bash
/// $ mkdir foo
/// $ touch foo/a
/// $ # commit...
/// $ mv foo bar
/// $ ln -s bar foo
/// ```
/// We need to dispatch the new symlink as `Unknown` and all the
/// descendents of the directory it replace as `Deleted`.
fn dispatch_symlinked_directory(
&mut self,
path: impl AsRef<HgPath>,
node: &Node,
) {
let path = path.as_ref();
self.shortcuts.push_back((
path.to_owned(),
StatusShortcut::Dispatch(Dispatch::Unknown),
));
for (file, _) in node.iter() {
self.shortcuts.push_back((
path.join(&file),
StatusShortcut::Dispatch(Dispatch::Deleted),
));
}
}
/// Returns `true` if the canonical `path` of a directory corresponds to a
/// symlink on disk. It means it was moved and symlinked after the last
/// dirstate update.
///
/// # Special cases
///
/// Returns `false` for the repository root.
/// Returns `false` on io error, error handling is outside of the iterator.
fn directory_became_symlink(&mut self, path: &HgPath) -> bool {
if path.is_empty() {
return false;
}
let filename_as_path = match hg_path_to_path_buf(&path) {
Ok(p) => p,
_ => return false,
};
let meta = self.root_dir.join(filename_as_path).symlink_metadata();
match meta {
Ok(ref m) if m.file_type().is_symlink() => true,
_ => false,
}
}
}
/// Returned by `FsIter`, since the `Dispatch` of any given entry may already
/// be determined during the iteration. This is necessary for performance
/// reasons, since hierarchical information is needed to `Dispatch` an entire
/// subtree efficiently.
#[derive(Debug, Copy, Clone)]
pub enum StatusShortcut {
/// A entry in the dirstate for further inspection
Entry(DirstateEntry),
/// The result of the status of the corresponding file
Dispatch(Dispatch),
}
impl<'a> Iterator for FsIter<'a> {
type Item = (HgPathBuf, StatusShortcut);
fn next(&mut self) -> Option<Self::Item> {
// If any paths have already been `Dispatch`-ed, return them
if let Some(res) = self.shortcuts.pop_front() {
return Some(res);
}
while let Some((base_path, node)) = self.to_visit.pop_front() {
match &node.kind {
NodeKind::Directory(dir) => {
let canonical_path = HgPath::new(&base_path);
if self.directory_became_symlink(canonical_path) {
// Potential security issue, don't do a normal
// traversal, force the results.
self.dispatch_symlinked_directory(
canonical_path,
&node,
);
continue;
}
add_children_to_visit(
&mut self.to_visit,
&base_path,
&dir,
);
if let Some(file) = &dir.was_file {
return Some((
HgPathBuf::from_bytes(&base_path),
StatusShortcut::Entry(file.entry),
));
}
}
NodeKind::File(file) => {
if let Some(dir) = &file.was_directory {
add_children_to_visit(
&mut self.to_visit,
&base_path,
&dir,
);
}
return Some((
HgPathBuf::from_bytes(&base_path),
StatusShortcut::Entry(file.entry),
));
}
}
}
None
}
}
impl<'a> FusedIterator for FsIter<'a> {}
fn join_path<'a, 'b>(path: &'a [u8], other: &'b [u8]) -> Cow<'b, [u8]> {
if path.is_empty() {
other.into()
} else {
[path, &b"/"[..], other].concat().into()
}
}
/// Adds all children of a given directory `dir` to the visit queue `to_visit`
/// prefixed by a `base_path`.
fn add_children_to_visit<'a>(
to_visit: &mut VecDeque<(Cow<'a, [u8]>, &'a Node)>,
base_path: &[u8],
dir: &'a Directory,
) {
to_visit.extend(dir.children.iter().map(|(path, child)| {
let full_path = join_path(&base_path, &path);
(full_path, child)
}));
}
#[cfg(test)]
mod tests {
use super::*;
use crate::utils::hg_path::HgPath;
use crate::{EntryState, FastHashMap};
use std::collections::HashSet;
#[test]
fn test_iteration() {
let mut tree = Tree::new();
assert_eq!(
tree.insert(
HgPathBuf::from_bytes(b"foo/bar"),
DirstateEntry {
state: EntryState::Merged,
mode: 41,
mtime: 42,
size: 43,
}
),
None
);
assert_eq!(
tree.insert(
HgPathBuf::from_bytes(b"foo2"),
DirstateEntry {
state: EntryState::Merged,
mode: 40,
mtime: 41,
size: 42,
}
),
None
);
assert_eq!(
tree.insert(
HgPathBuf::from_bytes(b"foo/baz"),
DirstateEntry {
state: EntryState::Normal,
mode: 0,
mtime: 0,
size: 0,
}
),
None
);
assert_eq!(
tree.insert(
HgPathBuf::from_bytes(b"foo/bap/nested"),
DirstateEntry {
state: EntryState::Normal,
mode: 0,
mtime: 0,
size: 0,
}
),
None
);
assert_eq!(tree.len(), 4);
let results: HashSet<_> =
tree.iter().map(|(c, _)| c.to_owned()).collect();
dbg!(&results);
assert!(results.contains(HgPath::new(b"foo2")));
assert!(results.contains(HgPath::new(b"foo/bar")));
assert!(results.contains(HgPath::new(b"foo/baz")));
assert!(results.contains(HgPath::new(b"foo/bap/nested")));
let mut iter = tree.iter();
assert!(iter.next().is_some());
assert!(iter.next().is_some());
assert!(iter.next().is_some());
assert!(iter.next().is_some());
assert_eq!(None, iter.next());
assert_eq!(None, iter.next());
drop(iter);
assert_eq!(
tree.insert(
HgPathBuf::from_bytes(b"foo/bap/nested/a"),
DirstateEntry {
state: EntryState::Normal,
mode: 0,
mtime: 0,
size: 0,
}
),
None
);
let results: FastHashMap<_, _> = tree.iter().collect();
assert!(results.contains_key(HgPath::new(b"foo2")));
assert!(results.contains_key(HgPath::new(b"foo/bar")));
assert!(results.contains_key(HgPath::new(b"foo/baz")));
// Is a dir but `was_file`, so it's listed as a removed file
assert!(results.contains_key(HgPath::new(b"foo/bap/nested")));
assert!(results.contains_key(HgPath::new(b"foo/bap/nested/a")));
// insert removed file (now directory) after nested file
assert_eq!(
tree.insert(
HgPathBuf::from_bytes(b"a/a"),
DirstateEntry {
state: EntryState::Normal,
mode: 0,
mtime: 0,
size: 0,
}
),
None
);
// `insert` returns `None` for a directory
assert_eq!(
tree.insert(
HgPathBuf::from_bytes(b"a"),
DirstateEntry {
state: EntryState::Removed,
mode: 0,
mtime: 0,
size: 0,
}
),
None
);
let results: FastHashMap<_, _> = tree.iter().collect();
assert!(results.contains_key(HgPath::new(b"a")));
assert!(results.contains_key(HgPath::new(b"a/a")));
}
}

rust/hg-core/src/dirstate/dirstate_tree/node.rs

  • This file was deleted.
// node.rs
//
// Copyright 2020, Raphaël Gomès <rgomes@octobus.net>
//
// This software may be used and distributed according to the terms of the
// GNU General Public License version 2 or any later version.
use super::iter::Iter;
use crate::utils::hg_path::HgPathBuf;
use crate::{DirstateEntry, EntryState, FastHashMap};
/// Represents a filesystem directory in the dirstate tree
#[derive(Debug, Default, Clone, PartialEq)]
pub struct Directory {
/// Contains the old file information if it existed between changesets.
/// Happens if a file `foo` is marked as removed, removed from the
/// filesystem then a directory `foo` is created and at least one of its
/// descendents is added to Mercurial.
pub(super) was_file: Option<Box<File>>,
pub(super) children: FastHashMap<Vec<u8>, Node>,
}
/// Represents a filesystem file (or symlink) in the dirstate tree
#[derive(Debug, Clone, PartialEq)]
pub struct File {
/// Contains the old structure if it existed between changesets.
/// Happens all descendents of `foo` marked as removed and removed from
/// the filesystem, then a file `foo` is created and added to Mercurial.
pub(super) was_directory: Option<Box<Directory>>,
pub(super) entry: DirstateEntry,
}
#[derive(Debug, Clone, PartialEq)]
pub enum NodeKind {
Directory(Directory),
File(File),
}
#[derive(Debug, Default, Clone, PartialEq)]
pub struct Node {
pub kind: NodeKind,
}
impl Default for NodeKind {
fn default() -> Self {
NodeKind::Directory(Default::default())
}
}
impl Node {
pub fn insert(
&mut self,
path: &[u8],
new_entry: DirstateEntry,
) -> InsertResult {
let mut split = path.splitn(2, |&c| c == b'/');
let head = split.next().unwrap_or(b"");
let tail = split.next().unwrap_or(b"");
// Are we're modifying the current file ? Is the the end of the path ?
let is_current_file = tail.is_empty() && head.is_empty();
// Potentially Replace the current file with a directory if it's marked
// as `Removed`
if !is_current_file {
if let NodeKind::File(file) = &mut self.kind {
if file.entry.state == EntryState::Removed {
self.kind = NodeKind::Directory(Directory {
was_file: Some(Box::from(file.clone())),
children: Default::default(),
})
}
}
}
match &mut self.kind {
NodeKind::Directory(directory) => {
Node::insert_in_directory(directory, new_entry, head, tail)
}
NodeKind::File(file) => {
if is_current_file {
let new = Self {
kind: NodeKind::File(File {
entry: new_entry,
..file.clone()
}),
};
InsertResult {
did_insert: false,
old_entry: Some(std::mem::replace(self, new)),
}
} else {
match file.entry.state {
EntryState::Removed => {
unreachable!("Removed file turning into a directory was dealt with earlier")
}
_ => {
Node::insert_in_file(
file, new_entry, head, tail,
)
}
}
}
}
}
}
/// The current file still exists and is not marked as `Removed`.
/// Insert the entry in its `was_directory`.
fn insert_in_file(
file: &mut File,
new_entry: DirstateEntry,
head: &[u8],
tail: &[u8],
) -> InsertResult {
if let Some(d) = &mut file.was_directory {
Node::insert_in_directory(d, new_entry, head, tail)
} else {
let mut dir = Directory {
was_file: None,
children: FastHashMap::default(),
};
let res =
Node::insert_in_directory(&mut dir, new_entry, head, tail);
file.was_directory = Some(Box::new(dir));
res
}
}
/// Insert an entry in the subtree of `directory`
fn insert_in_directory(
directory: &mut Directory,
new_entry: DirstateEntry,
head: &[u8],
tail: &[u8],
) -> InsertResult {
let mut res = InsertResult::default();
if let Some(node) = directory.children.get_mut(head) {
// Node exists
match &mut node.kind {
NodeKind::Directory(subdir) => {
if tail.is_empty() {
let becomes_file = Self {
kind: NodeKind::File(File {
was_directory: Some(Box::from(subdir.clone())),
entry: new_entry,
}),
};
let old_entry = directory
.children
.insert(head.to_owned(), becomes_file);
return InsertResult {
did_insert: true,
old_entry,
};
} else {
res = node.insert(tail, new_entry);
}
}
NodeKind::File(_) => {
res = node.insert(tail, new_entry);
}
}
} else if tail.is_empty() {
// File does not already exist
directory.children.insert(
head.to_owned(),
Self {
kind: NodeKind::File(File {
was_directory: None,
entry: new_entry,
}),
},
);
res.did_insert = true;
} else {
// Directory does not already exist
let mut nested = Self {
kind: NodeKind::Directory(Directory {
was_file: None,
children: Default::default(),
}),
};
res = nested.insert(tail, new_entry);
directory.children.insert(head.to_owned(), nested);
}
res
}
/// Removes an entry from the tree, returns a `RemoveResult`.
pub fn remove(&mut self, path: &[u8]) -> RemoveResult {
let empty_result = RemoveResult::default();
if path.is_empty() {
return empty_result;
}
let mut split = path.splitn(2, |&c| c == b'/');
let head = split.next();
let tail = split.next().unwrap_or(b"");
let head = match head {
None => {
return empty_result;
}
Some(h) => h,
};
if head == path {
match &mut self.kind {
NodeKind::Directory(d) => {
return Node::remove_from_directory(head, d);
}
NodeKind::File(f) => {
if let Some(d) = &mut f.was_directory {
let RemoveResult { old_entry, .. } =
Node::remove_from_directory(head, d);
return RemoveResult {
cleanup: false,
old_entry,
};
}
}
}
empty_result
} else {
// Look into the dirs
match &mut self.kind {
NodeKind::Directory(d) => {
if let Some(child) = d.children.get_mut(head) {
let mut res = child.remove(tail);
if res.cleanup {
d.children.remove(head);
}
res.cleanup =
d.children.is_empty() && d.was_file.is_none();
res
} else {
empty_result
}
}
NodeKind::File(f) => {
if let Some(d) = &mut f.was_directory {
if let Some(child) = d.children.get_mut(head) {
let RemoveResult { cleanup, old_entry } =
child.remove(tail);
if cleanup {
d.children.remove(head);
}
if d.children.is_empty() && d.was_file.is_none() {
f.was_directory = None;
}
return RemoveResult {
cleanup: false,
old_entry,
};
}
}
empty_result
}
}
}
}
fn remove_from_directory(head: &[u8], d: &mut Directory) -> RemoveResult {
if let Some(node) = d.children.get_mut(head) {
return match &mut node.kind {
NodeKind::Directory(d) => {
if let Some(f) = &mut d.was_file {
let entry = f.entry;
d.was_file = None;
RemoveResult {
cleanup: false,
old_entry: Some(entry),
}
} else {
RemoveResult::default()
}
}
NodeKind::File(f) => {
let entry = f.entry;
let mut cleanup = false;
match &f.was_directory {
None => {
if d.children.len() == 1 {
cleanup = true;
}
d.children.remove(head);
}
Some(dir) => {
node.kind = NodeKind::Directory(*dir.clone());
}
}
RemoveResult {
cleanup,
old_entry: Some(entry),
}
}
};
}
RemoveResult::default()
}
pub fn get(&self, path: &[u8]) -> Option<&Node> {
if path.is_empty() {
return Some(&self);
}
let mut split = path.splitn(2, |&c| c == b'/');
let head = split.next();
let tail = split.next().unwrap_or(b"");
let head = match head {
None => {
return Some(&self);
}
Some(h) => h,
};
match &self.kind {
NodeKind::Directory(d) => {
if let Some(child) = d.children.get(head) {
return child.get(tail);
}
}
NodeKind::File(f) => {
if let Some(d) = &f.was_directory {
if let Some(child) = d.children.get(head) {
return child.get(tail);
}
}
}
}
None
}
pub fn get_mut(&mut self, path: &[u8]) -> Option<&mut NodeKind> {
if path.is_empty() {
return Some(&mut self.kind);
}
let mut split = path.splitn(2, |&c| c == b'/');
let head = split.next();
let tail = split.next().unwrap_or(b"");
let head = match head {
None => {
return Some(&mut self.kind);
}
Some(h) => h,
};
match &mut self.kind {
NodeKind::Directory(d) => {
if let Some(child) = d.children.get_mut(head) {
return child.get_mut(tail);
}
}
NodeKind::File(f) => {
if let Some(d) = &mut f.was_directory {
if let Some(child) = d.children.get_mut(head) {
return child.get_mut(tail);
}
}
}
}
None
}
pub fn iter(&self) -> Iter {
Iter::new(self)
}
}
/// Information returned to the caller of an `insert` operation for integrity.
#[derive(Debug, Default)]
pub struct InsertResult {
/// Whether the insertion resulted in an actual insertion and not an
/// update
pub(super) did_insert: bool,
/// The entry that was replaced, if it exists
pub(super) old_entry: Option<Node>,
}
/// Information returned to the caller of a `remove` operation integrity.
#[derive(Debug, Default)]
pub struct RemoveResult {
/// If the caller needs to remove the current node
pub(super) cleanup: bool,
/// The entry that was replaced, if it exists
pub(super) old_entry: Option<DirstateEntry>,
}
impl<'a> IntoIterator for &'a Node {
type Item = (HgPathBuf, DirstateEntry);
type IntoIter = Iter<'a>;
fn into_iter(self) -> Self::IntoIter {
self.iter()
}
}

rust/hg-core/src/dirstate/dirstate_tree/tree.rs

  • This file was deleted.
// tree.rs
//
// Copyright 2020, Raphaël Gomès <rgomes@octobus.net>
//
// This software may be used and distributed according to the terms of the
// GNU General Public License version 2 or any later version.
use super::iter::Iter;
use super::node::{Directory, Node, NodeKind};
use crate::dirstate::dirstate_tree::iter::FsIter;
use crate::dirstate::dirstate_tree::node::{InsertResult, RemoveResult};
use crate::utils::hg_path::{HgPath, HgPathBuf};
use crate::DirstateEntry;
use std::path::PathBuf;
/// A specialized tree to represent the Mercurial dirstate.
///
/// # Advantages over a flat structure
///
/// The dirstate is inherently hierarchical, since it's a representation of the
/// file structure of the project. The current dirstate format is flat, and
/// while that affords us potentially great (unordered) iteration speeds, the
/// need to retrieve a given path is great enough that you need some kind of
/// hashmap or tree in a lot of cases anyway.
///
/// Going with a tree allows us to be smarter:
/// - Skipping an ignored directory means we don't visit its entire subtree
/// - Security auditing does not need to reconstruct paths backwards to check
/// for symlinked directories, this can be done during the iteration in a
/// very efficient fashion
/// - We don't need to build the directory information in another struct,
/// simplifying the code a lot, reducing the memory footprint and
/// potentially going faster depending on the implementation.
/// - We can use it to store a (platform-dependent) caching mechanism [1]
/// - And probably other types of optimizations.
///
/// Only the first two items in this list are implemented as of this commit.
///
/// [1]: https://www.mercurial-scm.org/wiki/DirsCachePlan
///
///
/// # Structure
///
/// It's a prefix (radix) tree with no fixed arity, with a granularity of a
/// folder, allowing it to mimic a filesystem hierarchy:
///
/// ```text
/// foo/bar
/// foo/baz
/// test
/// ```
/// Will be represented (simplified) by:
///
/// ```text
/// Directory(root):
/// - File("test")
/// - Directory("foo"):
/// - File("bar")
/// - File("baz")
/// ```
///
/// Moreover, it is special-cased for storing the dirstate and as such handles
/// cases that a simple `HashMap` would handle, but while preserving the
/// hierarchy.
/// For example:
///
/// ```shell
/// $ touch foo
/// $ hg add foo
/// $ hg commit -m "foo"
/// $ hg remove foo
/// $ rm foo
/// $ mkdir foo
/// $ touch foo/a
/// $ hg add foo/a
/// $ hg status
/// R foo
/// A foo/a
/// ```
/// To represent this in a tree, one needs to keep track of whether any given
/// file was a directory and whether any given directory was a file at the last
/// dirstate update. This tree stores that information, but only in the right
/// circumstances by respecting the high-level rules that prevent nonsensical
/// structures to exist:
/// - a file can only be added as a child of another file if the latter is
/// marked as `Removed`
/// - a file cannot replace a folder unless all its descendents are removed
///
/// This second rule is not checked by the tree for performance reasons, and
/// because high-level logic already prevents that state from happening.
///
/// # Ordering
///
/// It makes no guarantee of ordering for now.
#[derive(Debug, Default, Clone, PartialEq)]
pub struct Tree {
pub root: Node,
files_count: usize,
}
impl Tree {
pub fn new() -> Self {
Self {
root: Node {
kind: NodeKind::Directory(Directory {
was_file: None,
children: Default::default(),
}),
},
files_count: 0,
}
}
/// How many files (not directories) are stored in the tree, including ones
/// marked as `Removed`.
pub fn len(&self) -> usize {
self.files_count
}
pub fn is_empty(&self) -> bool {
self.len() == 0
}
/// Inserts a file in the tree and returns the previous entry if any.
pub fn insert(
&mut self,
path: impl AsRef<HgPath>,
kind: DirstateEntry,
) -> Option<DirstateEntry> {
let old = self.insert_node(path, kind);
match old?.kind {
NodeKind::Directory(_) => None,
NodeKind::File(f) => Some(f.entry),
}
}
/// Low-level insertion method that returns the previous node (directories
/// included).
fn insert_node(
&mut self,
path: impl AsRef<HgPath>,
kind: DirstateEntry,
) -> Option<Node> {
let InsertResult {
did_insert,
old_entry,
} = self.root.insert(path.as_ref().as_bytes(), kind);
self.files_count += if did_insert { 1 } else { 0 };
old_entry
}
/// Returns a reference to a node if it exists.
pub fn get_node(&self, path: impl AsRef<HgPath>) -> Option<&Node> {
self.root.get(path.as_ref().as_bytes())
}
/// Returns a reference to the entry corresponding to `path` if it exists.
pub fn get(&self, path: impl AsRef<HgPath>) -> Option<&DirstateEntry> {
if let Some(node) = self.get_node(&path) {
return match &node.kind {
NodeKind::Directory(d) => {
d.was_file.as_ref().map(|f| &f.entry)
}
NodeKind::File(f) => Some(&f.entry),
};
}
None
}
/// Returns `true` if an entry is found for the given `path`.
pub fn contains_key(&self, path: impl AsRef<HgPath>) -> bool {
self.get(path).is_some()
}
/// Returns a mutable reference to the entry corresponding to `path` if it
/// exists.
pub fn get_mut(
&mut self,
path: impl AsRef<HgPath>,
) -> Option<&mut DirstateEntry> {
if let Some(kind) = self.root.get_mut(path.as_ref().as_bytes()) {
return match kind {
NodeKind::Directory(d) => {
d.was_file.as_mut().map(|f| &mut f.entry)
}
NodeKind::File(f) => Some(&mut f.entry),
};
}
None
}
/// Returns an iterator over the paths and corresponding entries in the
/// tree.
pub fn iter(&self) -> Iter {
Iter::new(&self.root)
}
/// Returns an iterator of all entries in the tree, with a special
/// filesystem handling for the directories containing said entries. See
/// the documentation of `FsIter` for more.
pub fn fs_iter(&self, root_dir: PathBuf) -> FsIter {
FsIter::new(&self.root, root_dir)
}
/// Remove the entry at `path` and returns it, if it exists.
pub fn remove(
&mut self,
path: impl AsRef<HgPath>,
) -> Option<DirstateEntry> {
let RemoveResult { old_entry, .. } =
self.root.remove(path.as_ref().as_bytes());
self.files_count = self
.files_count
.checked_sub(if old_entry.is_some() { 1 } else { 0 })
.expect("removed too many files");
old_entry
}
}
impl<P: AsRef<HgPath>> Extend<(P, DirstateEntry)> for Tree {
fn extend<T: IntoIterator<Item = (P, DirstateEntry)>>(&mut self, iter: T) {
for (path, entry) in iter {
self.insert(path, entry);
}
}
}
impl<'a> IntoIterator for &'a Tree {
type Item = (HgPathBuf, DirstateEntry);
type IntoIter = Iter<'a>;
fn into_iter(self) -> Self::IntoIter {
self.iter()
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::dirstate::dirstate_tree::node::File;
use crate::{EntryState, FastHashMap};
use pretty_assertions::assert_eq;
impl Node {
/// Shortcut for getting children of a node in tests.
fn children(&self) -> Option<&FastHashMap<Vec<u8>, Node>> {
match &self.kind {
NodeKind::Directory(d) => Some(&d.children),
NodeKind::File(_) => None,
}
}
}
#[test]
fn test_dirstate_tree() {
let mut tree = Tree::new();
assert_eq!(
tree.insert_node(
HgPath::new(b"we/p"),
DirstateEntry {
state: EntryState::Normal,
mode: 0,
mtime: 0,
size: 0
}
),
None
);
dbg!(&tree);
assert!(tree.get_node(HgPath::new(b"we")).is_some());
let entry = DirstateEntry {
state: EntryState::Merged,
mode: 41,
mtime: 42,
size: 43,
};
assert_eq!(tree.insert_node(HgPath::new(b"foo/bar"), entry), None);
assert_eq!(
tree.get_node(HgPath::new(b"foo/bar")),
Some(&Node {
kind: NodeKind::File(File {
was_directory: None,
entry
})
})
);
// We didn't override the first entry we made
assert!(tree.get_node(HgPath::new(b"we")).is_some(),);
// Inserting the same key again
assert_eq!(
tree.insert_node(HgPath::new(b"foo/bar"), entry),
Some(Node {
kind: NodeKind::File(File {
was_directory: None,
entry
}),
})
);
// Inserting the two levels deep
assert_eq!(tree.insert_node(HgPath::new(b"foo/bar/baz"), entry), None);
// Getting a file "inside a file" should return `None`
assert_eq!(tree.get_node(HgPath::new(b"foo/bar/baz/bap"),), None);
assert_eq!(
tree.insert_node(HgPath::new(b"wasdir/subfile"), entry),
None,
);
let removed_entry = DirstateEntry {
state: EntryState::Removed,
mode: 0,
mtime: 0,
size: 0,
};
assert!(tree
.insert_node(HgPath::new(b"wasdir"), removed_entry)
.is_some());
assert_eq!(
tree.get_node(HgPath::new(b"wasdir")),
Some(&Node {
kind: NodeKind::File(File {
was_directory: Some(Box::new(Directory {
was_file: None,
children: [(
b"subfile".to_vec(),
Node {
kind: NodeKind::File(File {
was_directory: None,
entry,
})
}
)]
.to_vec()
.into_iter()
.collect()
})),
entry: removed_entry
})
})
);
assert!(tree.get(HgPath::new(b"wasdir/subfile")).is_some())
}
#[test]
fn test_insert_removed() {
let mut tree = Tree::new();
let entry = DirstateEntry {
state: EntryState::Merged,
mode: 1,
mtime: 2,
size: 3,
};
let removed_entry = DirstateEntry {
state: EntryState::Removed,
mode: 10,
mtime: 20,
size: 30,
};
assert_eq!(tree.insert_node(HgPath::new(b"foo"), entry), None);
assert_eq!(
tree.insert_node(HgPath::new(b"foo/a"), removed_entry),
None
);
// The insert should not turn `foo` into a directory as `foo` is not
// `Removed`.
match tree.get_node(HgPath::new(b"foo")).unwrap().kind {
NodeKind::Directory(_) => panic!("should be a file"),
NodeKind::File(_) => {}
}
let mut tree = Tree::new();
let entry = DirstateEntry {
state: EntryState::Merged,
mode: 1,
mtime: 2,
size: 3,
};
let removed_entry = DirstateEntry {
state: EntryState::Removed,
mode: 10,
mtime: 20,
size: 30,
};
// The insert *should* turn `foo` into a directory as it is `Removed`.
assert_eq!(tree.insert_node(HgPath::new(b"foo"), removed_entry), None);
assert_eq!(tree.insert_node(HgPath::new(b"foo/a"), entry), None);
match tree.get_node(HgPath::new(b"foo")).unwrap().kind {
NodeKind::Directory(_) => {}
NodeKind::File(_) => panic!("should be a directory"),
}
}
#[test]
fn test_get() {
let mut tree = Tree::new();
let entry = DirstateEntry {
state: EntryState::Merged,
mode: 1,
mtime: 2,
size: 3,
};
assert_eq!(tree.insert_node(HgPath::new(b"a/b/c"), entry), None);
assert_eq!(tree.files_count, 1);
assert_eq!(tree.get(HgPath::new(b"a/b/c")), Some(&entry));
assert_eq!(tree.get(HgPath::new(b"a/b")), None);
assert_eq!(tree.get(HgPath::new(b"a")), None);
assert_eq!(tree.get(HgPath::new(b"a/b/c/d")), None);
let entry2 = DirstateEntry {
state: EntryState::Removed,
mode: 0,
mtime: 5,
size: 1,
};
// was_directory
assert_eq!(tree.insert(HgPath::new(b"a/b"), entry2), None);
assert_eq!(tree.files_count, 2);
assert_eq!(tree.get(HgPath::new(b"a/b")), Some(&entry2));
assert_eq!(tree.get(HgPath::new(b"a/b/c")), Some(&entry));
let mut tree = Tree::new();
// was_file
assert_eq!(tree.insert_node(HgPath::new(b"a"), entry), None);
assert_eq!(tree.files_count, 1);
assert_eq!(tree.insert_node(HgPath::new(b"a/b"), entry2), None);
assert_eq!(tree.files_count, 2);
assert_eq!(tree.get(HgPath::new(b"a/b")), Some(&entry2));
}
#[test]
fn test_get_mut() {
let mut tree = Tree::new();
let mut entry = DirstateEntry {
state: EntryState::Merged,
mode: 1,
mtime: 2,
size: 3,
};
assert_eq!(tree.insert_node(HgPath::new(b"a/b/c"), entry), None);
assert_eq!(tree.files_count, 1);
assert_eq!(tree.get_mut(HgPath::new(b"a/b/c")), Some(&mut entry));
assert_eq!(tree.get_mut(HgPath::new(b"a/b")), None);
assert_eq!(tree.get_mut(HgPath::new(b"a")), None);
assert_eq!(tree.get_mut(HgPath::new(b"a/b/c/d")), None);
let mut entry2 = DirstateEntry {
state: EntryState::Removed,
mode: 0,
mtime: 5,
size: 1,
};
// was_directory
assert_eq!(tree.insert(HgPath::new(b"a/b"), entry2), None);
assert_eq!(tree.files_count, 2);
assert_eq!(tree.get_mut(HgPath::new(b"a/b")), Some(&mut entry2));
assert_eq!(tree.get_mut(HgPath::new(b"a/b/c")), Some(&mut entry));
let mut tree = Tree::new();
// was_file
assert_eq!(tree.insert_node(HgPath::new(b"a"), entry), None);
assert_eq!(tree.files_count, 1);
assert_eq!(tree.insert_node(HgPath::new(b"a/b"), entry2), None);
assert_eq!(tree.files_count, 2);
assert_eq!(tree.get_mut(HgPath::new(b"a/b")), Some(&mut entry2));
}
#[test]
fn test_remove() {
let mut tree = Tree::new();
assert_eq!(tree.files_count, 0);
assert_eq!(tree.remove(HgPath::new(b"foo")), None);
assert_eq!(tree.files_count, 0);
let entry = DirstateEntry {
state: EntryState::Normal,
mode: 0,
mtime: 0,
size: 0,
};
assert_eq!(tree.insert_node(HgPath::new(b"a/b/c"), entry), None);
assert_eq!(tree.files_count, 1);
assert_eq!(tree.remove(HgPath::new(b"a/b/c")), Some(entry));
assert_eq!(tree.files_count, 0);
assert_eq!(tree.insert_node(HgPath::new(b"a/b/x"), entry), None);
assert_eq!(tree.insert_node(HgPath::new(b"a/b/y"), entry), None);
assert_eq!(tree.insert_node(HgPath::new(b"a/b/z"), entry), None);
assert_eq!(tree.insert_node(HgPath::new(b"x"), entry), None);
assert_eq!(tree.insert_node(HgPath::new(b"y"), entry), None);
assert_eq!(tree.files_count, 5);
assert_eq!(tree.remove(HgPath::new(b"a/b/x")), Some(entry));
assert_eq!(tree.files_count, 4);
assert_eq!(tree.remove(HgPath::new(b"a/b/x")), None);
assert_eq!(tree.files_count, 4);
assert_eq!(tree.remove(HgPath::new(b"a/b/y")), Some(entry));
assert_eq!(tree.files_count, 3);
assert_eq!(tree.remove(HgPath::new(b"a/b/z")), Some(entry));
assert_eq!(tree.files_count, 2);
assert_eq!(tree.remove(HgPath::new(b"x")), Some(entry));
assert_eq!(tree.files_count, 1);
assert_eq!(tree.remove(HgPath::new(b"y")), Some(entry));
assert_eq!(tree.files_count, 0);
// `a` should have been cleaned up, no more files anywhere in its
// descendents
assert_eq!(tree.get_node(HgPath::new(b"a")), None);
assert_eq!(tree.root.children().unwrap().len(), 0);
let removed_entry = DirstateEntry {
state: EntryState::Removed,
..entry
};
assert_eq!(tree.insert(HgPath::new(b"a"), removed_entry), None);
assert_eq!(tree.insert_node(HgPath::new(b"a/b/x"), entry), None);
assert_eq!(tree.files_count, 2);
dbg!(&tree);
assert_eq!(tree.remove(HgPath::new(b"a")), Some(removed_entry));
assert_eq!(tree.files_count, 1);
dbg!(&tree);
assert_eq!(tree.remove(HgPath::new(b"a/b/x")), Some(entry));
assert_eq!(tree.files_count, 0);
// The entire tree should have been cleaned up, no more files anywhere
// in its descendents
assert_eq!(tree.root.children().unwrap().len(), 0);
let removed_entry = DirstateEntry {
state: EntryState::Removed,
..entry
};
assert_eq!(tree.insert(HgPath::new(b"a"), entry), None);
assert_eq!(
tree.insert_node(HgPath::new(b"a/b/x"), removed_entry),
None
);
assert_eq!(tree.files_count, 2);
dbg!(&tree);
assert_eq!(tree.remove(HgPath::new(b"a")), Some(entry));
assert_eq!(tree.files_count, 1);
dbg!(&tree);
assert_eq!(tree.remove(HgPath::new(b"a/b/x")), Some(removed_entry));
assert_eq!(tree.files_count, 0);
dbg!(&tree);
// The entire tree should have been cleaned up, no more files anywhere
// in its descendents
assert_eq!(tree.root.children().unwrap().len(), 0);
assert_eq!(tree.insert(HgPath::new(b"d"), entry), None);
assert_eq!(tree.insert(HgPath::new(b"d/d/d"), entry), None);
assert_eq!(tree.files_count, 2);
// Deleting the nested file should not delete the top directory as it
// used to be a file
assert_eq!(tree.remove(HgPath::new(b"d/d/d")), Some(entry));
assert_eq!(tree.files_count, 1);
assert!(tree.get_node(HgPath::new(b"d")).is_some());
assert!(tree.remove(HgPath::new(b"d")).is_some());
assert_eq!(tree.files_count, 0);
// Deleting the nested file should not delete the top file (other way
// around from the last case)
assert_eq!(tree.insert(HgPath::new(b"a/a"), entry), None);
assert_eq!(tree.files_count, 1);
assert_eq!(tree.insert(HgPath::new(b"a"), entry), None);
assert_eq!(tree.files_count, 2);
dbg!(&tree);
assert_eq!(tree.remove(HgPath::new(b"a/a")), Some(entry));
assert_eq!(tree.files_count, 1);
dbg!(&tree);
assert!(tree.get_node(HgPath::new(b"a")).is_some());
assert!(tree.get_node(HgPath::new(b"a/a")).is_none());
}
#[test]
fn test_was_directory() {
let mut tree = Tree::new();
let entry = DirstateEntry {
state: EntryState::Removed,
mode: 0,
mtime: 0,
size: 0,
};
assert_eq!(tree.insert_node(HgPath::new(b"a/b/c"), entry), None);
assert_eq!(tree.files_count, 1);
assert!(tree.insert_node(HgPath::new(b"a"), entry).is_some());
let new_a = tree.root.children().unwrap().get(&b"a".to_vec()).unwrap();
match &new_a.kind {
NodeKind::Directory(_) => panic!(),
NodeKind::File(f) => {
let dir = f.was_directory.clone().unwrap();
let c = dir
.children
.get(&b"b".to_vec())
.unwrap()
.children()
.unwrap()
.get(&b"c".to_vec())
.unwrap();
assert_eq!(
match &c.kind {
NodeKind::Directory(_) => panic!(),
NodeKind::File(f) => f.entry,
},
entry
);
}
}
assert_eq!(tree.files_count, 2);
dbg!(&tree);
assert_eq!(tree.remove(HgPath::new(b"a/b/c")), Some(entry));
assert_eq!(tree.files_count, 1);
dbg!(&tree);
let a = tree.get_node(HgPath::new(b"a")).unwrap();
match &a.kind {
NodeKind::Directory(_) => panic!(),
NodeKind::File(f) => {
// Directory in `was_directory` was emptied, should be removed
assert_eq!(f.was_directory, None);
}
}
}
#[test]
fn test_extend() {
let insertions = [
(
HgPathBuf::from_bytes(b"d"),
DirstateEntry {
state: EntryState::Added,
mode: 0,
mtime: -1,
size: -1,
},
),
(
HgPathBuf::from_bytes(b"b"),
DirstateEntry {
state: EntryState::Normal,
mode: 33188,
mtime: 1599647984,
size: 2,
},
),
(
HgPathBuf::from_bytes(b"a/a"),
DirstateEntry {
state: EntryState::Normal,
mode: 33188,
mtime: 1599647984,
size: 2,
},
),
(
HgPathBuf::from_bytes(b"d/d/d"),
DirstateEntry {
state: EntryState::Removed,
mode: 0,
mtime: 0,
size: 0,
},
),
]
.to_vec();
let mut tree = Tree::new();
tree.extend(insertions.clone().into_iter());
for (path, _) in &insertions {
assert!(tree.contains_key(path), true);
}
assert_eq!(tree.files_count, 4);
}
}

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

entries.push((path, entry)); entries.push((path, entry));
contents = rest; contents = rest;
} }
Ok((parents, entries, copies)) Ok((parents, entries, copies))
} }
/// `now` is the duration in seconds since the Unix epoch /// `now` is the duration in seconds since the Unix epoch
#[cfg(not(feature = "dirstate-tree"))]
pub fn pack_dirstate( pub fn pack_dirstate(
state_map: &mut StateMap, state_map: &mut StateMap,
copy_map: &CopyMap, copy_map: &CopyMap,
parents: DirstateParents, parents: DirstateParents,
now: Duration, now: Duration,
) -> Result<Vec<u8>, HgError> { ) -> Result<Vec<u8>, HgError> {
// TODO move away from i32 before 2038. // TODO move away from i32 before 2038.
let now: i32 = now.as_secs().try_into().expect("time overflow"); let now: i32 = now.as_secs().try_into().expect("time overflow");
"bad dirstate size: {} != {}", "bad dirstate size: {} != {}",
expected_size, expected_size,
packed.len() packed.len()
))); )));
} }
Ok(packed) Ok(packed)
} }
/// `now` is the duration in seconds since the Unix epoch
#[cfg(feature = "dirstate-tree")]
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(b'\0');
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)] #[cfg(test)]
mod tests { mod tests {
use super::*; use super::*;
use crate::{utils::hg_path::HgPathBuf, FastHashMap}; use crate::{utils::hg_path::HgPathBuf, FastHashMap};
use pretty_assertions::assert_eq; use pretty_assertions::assert_eq;
#[test] #[test]

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

// status.rs // status.rs
// //
// Copyright 2019 Raphaël Gomès <rgomes@octobus.net> // Copyright 2019 Raphaël Gomès <rgomes@octobus.net>
// //
// This software may be used and distributed according to the terms of the // This software may be used and distributed according to the terms of the
// GNU General Public License version 2 or any later version. // GNU General Public License version 2 or any later version.
//! Rust implementation of dirstate.status (dirstate.py). //! Rust implementation of dirstate.status (dirstate.py).
//! It is currently missing a lot of functionality compared to the Python one //! It is currently missing a lot of functionality compared to the Python one
//! and will only be triggered in narrow cases. //! and will only be triggered in narrow cases.
#[cfg(feature = "dirstate-tree")]
use crate::dirstate::dirstate_tree::iter::StatusShortcut;
#[cfg(not(feature = "dirstate-tree"))]
use crate::utils::path_auditor::PathAuditor; use crate::utils::path_auditor::PathAuditor;
use crate::{ use crate::{
dirstate::SIZE_FROM_OTHER_PARENT, dirstate::SIZE_FROM_OTHER_PARENT,
filepatterns::PatternFileWarning, filepatterns::PatternFileWarning,
matchers::{get_ignore_function, Matcher, VisitChildrenSet}, matchers::{get_ignore_function, Matcher, VisitChildrenSet},
utils::{ utils::{
files::{find_dirs, HgMetadata}, files::{find_dirs, HgMetadata},
hg_path::{ hg_path::{
} }
}) })
} }
/// Add the files in the dirstate to the results. /// Add the files in the dirstate to the results.
/// ///
/// This takes a mutable reference to the results to account for the /// This takes a mutable reference to the results to account for the
/// `extend` in timings /// `extend` in timings
#[cfg(feature = "dirstate-tree")]
#[timed]
pub fn extend_from_dmap(&self, results: &mut Vec<DispatchedPath<'a>>) {
results.par_extend(
self.dmap
.fs_iter(self.root_dir.clone())
.par_bridge()
.filter(|(path, _)| self.matcher.matches(path))
.map(move |(filename, shortcut)| {
let entry = match shortcut {
StatusShortcut::Entry(e) => e,
StatusShortcut::Dispatch(d) => {
return (Cow::Owned(filename), d)
}
};
let filename_as_path = match hg_path_to_path_buf(&filename)
{
Ok(f) => f,
Err(_) => {
return (
Cow::Owned(filename),
INVALID_PATH_DISPATCH,
)
}
};
let meta = self
.root_dir
.join(filename_as_path)
.symlink_metadata();
match meta {
Ok(m)
if !(m.file_type().is_file()
|| m.file_type().is_symlink()) =>
{
(
Cow::Owned(filename),
dispatch_missing(entry.state),
)
}
Ok(m) => {
let dispatch = dispatch_found(
&filename,
entry,
HgMetadata::from_metadata(m),
&self.dmap.copy_map,
self.options,
);
(Cow::Owned(filename), dispatch)
}
Err(e)
if e.kind() == ErrorKind::NotFound
|| e.raw_os_error() == Some(20) =>
{
// Rust does not yet have an `ErrorKind` for
// `NotADirectory` (errno 20)
// It happens if the dirstate contains `foo/bar`
// and foo is not a
// directory
(
Cow::Owned(filename),
dispatch_missing(entry.state),
)
}
Err(e) => {
(Cow::Owned(filename), dispatch_os_error(&e))
}
}
}),
);
}
/// Add the files in the dirstate to the results.
///
/// This takes a mutable reference to the results to account for the
/// `extend` in timings
#[cfg(not(feature = "dirstate-tree"))]
#[timed] #[timed]
pub fn extend_from_dmap(&self, results: &mut Vec<DispatchedPath<'a>>) { pub fn extend_from_dmap(&self, results: &mut Vec<DispatchedPath<'a>>) {
results.par_extend( results.par_extend(
self.dmap self.dmap
.par_iter() .par_iter()
.filter(|(path, _)| self.matcher.matches(path)) .filter(|(path, _)| self.matcher.matches(path))
.map(move |(filename, entry)| { .map(move |(filename, entry)| {
let filename: &HgPath = filename; let filename: &HgPath = filename;
} }
/// Checks all files that are in the dirstate but were not found during the /// Checks all files that are in the dirstate but were not found during the
/// working directory traversal. This means that the rest must /// working directory traversal. This means that the rest must
/// be either ignored, under a symlink or under a new nested repo. /// be either ignored, under a symlink or under a new nested repo.
/// ///
/// This takes a mutable reference to the results to account for the /// This takes a mutable reference to the results to account for the
/// `extend` in timings /// `extend` in timings
#[cfg(not(feature = "dirstate-tree"))]
#[timed] #[timed]
pub fn handle_unknowns(&self, results: &mut Vec<DispatchedPath<'a>>) { pub fn handle_unknowns(&self, results: &mut Vec<DispatchedPath<'a>>) {
let to_visit: Vec<(&HgPath, &DirstateEntry)> = let to_visit: Vec<(&HgPath, &DirstateEntry)> =
if results.is_empty() && self.matcher.matches_everything() { if results.is_empty() && self.matcher.matches_everything() {
self.dmap.iter().map(|(f, e)| (f.deref(), e)).collect() self.dmap.iter().map(|(f, e)| (f.deref(), e)).collect()
} else { } else {
// Only convert to a hashmap if needed. // Only convert to a hashmap if needed.
let old_results: FastHashMap<_, _> = let old_results: FastHashMap<_, _> =

rust/hg-core/src/operations/dirstate_status.rs

// dirstate_status.rs // dirstate_status.rs
// //
// Copyright 2019, Raphaël Gomès <rgomes@octobus.net> // Copyright 2019, Raphaël Gomès <rgomes@octobus.net>
// //
// This software may be used and distributed according to the terms of the // This software may be used and distributed according to the terms of the
// GNU General Public License version 2 or any later version. // GNU General Public License version 2 or any later version.
use crate::dirstate::status::{build_response, Dispatch, HgPathCow, Status}; use crate::dirstate::status::{build_response, Dispatch, HgPathCow, Status};
use crate::matchers::Matcher; use crate::matchers::Matcher;
use crate::{DirstateStatus, StatusError}; use crate::{DirstateStatus, StatusError};
/// A tuple of the paths that need to be checked in the filelog because it's /// A tuple of the paths that need to be checked in the filelog because it's
/// ambiguous whether they've changed, and the rest of the already dispatched /// ambiguous whether they've changed, and the rest of the already dispatched
/// files. /// files.
pub type LookupAndStatus<'a> = (Vec<HgPathCow<'a>>, DirstateStatus<'a>); pub type LookupAndStatus<'a> = (Vec<HgPathCow<'a>>, DirstateStatus<'a>);
#[cfg(feature = "dirstate-tree")]
impl<'a, M: Matcher + Sync> Status<'a, M> {
pub(crate) fn run(&self) -> Result<LookupAndStatus<'a>, StatusError> {
let (traversed_sender, traversed_receiver) =
crossbeam_channel::unbounded();
// Step 1: check the files explicitly mentioned by the user
let (work, mut results) = self.walk_explicit(traversed_sender.clone());
// Step 2: Check files in the dirstate
if !self.matcher.is_exact() {
self.extend_from_dmap(&mut results);
}
// Step 3: Check the working directory if listing unknowns
if !work.is_empty() {
// Hashmaps are quite a bit slower to build than vecs, so only
// build it if needed.
let mut old_results = None;
// Step 2: recursively check the working directory for changes if
// needed
for (dir, dispatch) in work {
match dispatch {
Dispatch::Directory { was_file } => {
if was_file {
results.push((dir.to_owned(), Dispatch::Removed));
}
if self.options.list_ignored
|| self.options.list_unknown
&& !self.dir_ignore(&dir)
{
if old_results.is_none() {
old_results =
Some(results.iter().cloned().collect());
}
self.traverse(
&dir,
old_results
.as_ref()
.expect("old results should exist"),
&mut results,
traversed_sender.clone(),
);
}
}
_ => {
unreachable!("There can only be directories in `work`")
}
}
}
}
drop(traversed_sender);
let traversed = traversed_receiver.into_iter().collect();
Ok(build_response(results, traversed))
}
}
#[cfg(not(feature = "dirstate-tree"))]
impl<'a, M: Matcher + Sync> Status<'a, M> { impl<'a, M: Matcher + Sync> Status<'a, M> {
pub(crate) fn run(&self) -> Result<LookupAndStatus<'a>, StatusError> { pub(crate) fn run(&self) -> Result<LookupAndStatus<'a>, StatusError> {
let (traversed_sender, traversed_receiver) = let (traversed_sender, traversed_receiver) =
crossbeam_channel::unbounded(); crossbeam_channel::unbounded();
// Step 1: check the files explicitly mentioned by the user // Step 1: check the files explicitly mentioned by the user
let (work, mut results) = self.walk_explicit(traversed_sender.clone()); let (work, mut results) = self.walk_explicit(traversed_sender.clone());

rust/hg-cpython/Cargo.toml

[package] [package]
name = "hg-cpython" name = "hg-cpython"
version = "0.1.0" version = "0.1.0"
authors = ["Georges Racinet <gracinet@anybox.fr>"] authors = ["Georges Racinet <gracinet@anybox.fr>"]
edition = "2018" edition = "2018"
[lib] [lib]
name='rusthg' name='rusthg'
crate-type = ["cdylib"] crate-type = ["cdylib"]
[features] [features]
default = ["python27"] default = ["python27"]
dirstate-tree = ["hg-core/dirstate-tree"]
# Features to build an extension module: # Features to build an extension module:
python27 = ["cpython/python27-sys", "cpython/extension-module-2-7"] python27 = ["cpython/python27-sys", "cpython/extension-module-2-7"]
python3 = ["cpython/python3-sys", "cpython/extension-module"] python3 = ["cpython/python3-sys", "cpython/extension-module"]
# Enable one of these features to build a test executable linked to libpython: # Enable one of these features to build a test executable linked to libpython:
# e.g. cargo test --no-default-features --features python27-bin # e.g. cargo test --no-default-features --features python27-bin
python27-bin = ["cpython/python27-sys"] python27-bin = ["cpython/python27-sys"]

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

impl DirstateMap { impl DirstateMap {
pub fn get_inner<'a>( pub fn get_inner<'a>(
&'a self, &'a self,
py: Python<'a>, py: Python<'a>,
) -> Ref<'a, RustDirstateMap> { ) -> Ref<'a, RustDirstateMap> {
self.inner(py).borrow() self.inner(py).borrow()
} }
#[cfg(not(feature = "dirstate-tree"))]
fn translate_key( fn translate_key(
py: Python, py: Python,
res: (&HgPathBuf, &DirstateEntry), res: (&HgPathBuf, &DirstateEntry),
) -> PyResult<Option<PyBytes>> { ) -> PyResult<Option<PyBytes>> {
Ok(Some(PyBytes::new(py, res.0.as_bytes()))) Ok(Some(PyBytes::new(py, res.0.as_bytes())))
} }
#[cfg(not(feature = "dirstate-tree"))]
fn translate_key_value( fn translate_key_value(
py: Python, py: Python,
res: (&HgPathBuf, &DirstateEntry), res: (&HgPathBuf, &DirstateEntry),
) -> PyResult<Option<(PyBytes, PyObject)>> { ) -> PyResult<Option<(PyBytes, PyObject)>> {
let (f, entry) = res; let (f, entry) = res;
Ok(Some(( Ok(Some((
PyBytes::new(py, f.as_bytes()), PyBytes::new(py, f.as_bytes()),
make_dirstate_tuple(py, &entry)?, make_dirstate_tuple(py, &entry)?,
))) )))
} }
#[cfg(feature = "dirstate-tree")]
fn translate_key(
py: Python,
res: (HgPathBuf, DirstateEntry),
) -> PyResult<Option<PyBytes>> {
Ok(Some(PyBytes::new(py, res.0.as_bytes())))
}
#[cfg(feature = "dirstate-tree")]
fn translate_key_value(
py: Python,
res: (HgPathBuf, DirstateEntry),
) -> PyResult<Option<(PyBytes, PyObject)>> {
let (f, entry) = res;
Ok(Some((
PyBytes::new(py, f.as_bytes()),
make_dirstate_tuple(py, &entry)?,
)))
}
} }
py_shared_iterator!( py_shared_iterator!(
DirstateMapKeysIterator, DirstateMapKeysIterator,
UnsafePyLeaked<StateMapIter<'static>>, UnsafePyLeaked<StateMapIter<'static>>,
DirstateMap::translate_key, DirstateMap::translate_key,
Option<PyBytes> Option<PyBytes>
); );
rust/hg-core/src/dirstate/dirstate_tree.rs