( )⚙ D10560 dirstate-tree: Borrow paths from the "on disk" bytes

This is an archive of the discontinued Mercurial Phabricator instance.

Differential D10560

dirstate-tree: Borrow paths from the "on disk" bytes
ClosedPublic

Authored by SimonSapin on May 3 2021, 6:26 AM.

Details

Reviewers
Alphare
Group Reviewers
hg-reviewers
Commits
rHGecfe0819ada5: dirstate-tree: Borrow paths from the "on disk" bytes
rHG1794efd140df: dirstate-tree: Borrow paths from the "on disk" bytes
Summary

Use std::borrow::Cow to avoid some memory allocations and copying.

Diff Detail

Repository
rHG Mercurial
Branch
default
Lint
No Linters Available
Unit
No Unit Test Coverage

Event Timeline

SimonSapin created this revision.May 3 2021, 6:26 AM
Alphare accepted this revision.May 3 2021, 12:45 PM
This revision is now accepted and ready to land.May 3 2021, 12:45 PM
baymax updated this revision to Diff 27636.May 6 2021, 12:04 PM

✅ refresh by Heptapod after a successful CI run (🐙 💚)

SimonSapin added a commit: rHG1794efd140df: dirstate-tree: Borrow paths from the "on disk" bytes.May 6 2021, 12:58 PM
Closed by commit rHG1794efd140df: dirstate-tree: Borrow paths from the "on disk" bytes (authored by SimonSapin). · Explain Why
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

Diff 27335

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

} }
/// Using a plain `HgPathBuf` of the full path from the repository root as a /// Using a plain `HgPathBuf` of the full path from the repository root as a
/// map key would also work: all paths in a given map have the same parent /// map key would also work: all paths in a given map have the same parent
/// path, so comparing full paths gives the same result as comparing base /// path, so comparing full paths gives the same result as comparing base
/// names. However `BTreeMap` would waste time always re-comparing the same /// names. However `BTreeMap` would waste time always re-comparing the same
/// string prefix. /// string prefix.
pub(super) type ChildNodes<'on_disk> = pub(super) type ChildNodes<'on_disk> =
FastHashMap<WithBasename<HgPathBuf>, Node<'on_disk>>; FastHashMap<WithBasename<Cow<'on_disk, HgPath>>, Node<'on_disk>>;
/// Represents a file or a directory /// Represents a file or a directory
#[derive(Default)] #[derive(Default)]
pub(super) struct Node<'on_disk> { pub(super) struct Node<'on_disk> {
/// `None` for directories /// `None` for directories
pub(super) entry: Option<DirstateEntry>, pub(super) entry: Option<DirstateEntry>,
pub(super) copy_source: Option<Cow<'on_disk, HgPath>>, pub(super) copy_source: Option<Cow<'on_disk, HgPath>>,
if self.on_disk.is_empty() { if self.on_disk.is_empty() {
return Ok(None); return Ok(None);
} }
let parents = parse_dirstate_entries( let parents = parse_dirstate_entries(
self.on_disk, self.on_disk,
|path, entry, copy_source| { |path, entry, copy_source| {
let tracked = entry.state.is_tracked(); let tracked = entry.state.is_tracked();
let node = Self::get_or_insert_node_tracing_ancestors( let node = Self::get_or_insert_node(
&mut self.root, &mut self.root,
path, path,
WithBasename::to_cow_borrowed,
|ancestor| { |ancestor| {
if tracked { if tracked {
ancestor.tracked_descendants_count += 1 ancestor.tracked_descendants_count += 1
} }
}, },
); );
assert!( assert!(
node.entry.is_none(), node.entry.is_none(),
component = next_component; component = next_component;
children = &mut child.children; children = &mut child.children;
} else { } else {
return Some(child); return Some(child);
} }
} }
} }
fn get_or_insert_node<'tree>( fn get_or_insert_node<'tree, 'path>(
root: &'tree mut ChildNodes<'on_disk>, root: &'tree mut ChildNodes<'on_disk>,
path: &HgPath, path: &'path HgPath,
) -> &'tree mut Node<'on_disk> { to_cow: impl Fn(
Self::get_or_insert_node_tracing_ancestors(root, path, |_| {}) WithBasename<&'path HgPath>,
} ) -> WithBasename<Cow<'on_disk, HgPath>>,
fn get_or_insert_node_tracing_ancestors<'tree>(
root: &'tree mut ChildNodes<'on_disk>,
path: &HgPath,
mut each_ancestor: impl FnMut(&mut Node), mut each_ancestor: impl FnMut(&mut Node),
) -> &'tree mut Node<'on_disk> { ) -> &'tree mut Node<'on_disk> {
let mut child_nodes = root; let mut child_nodes = root;
let mut inclusive_ancestor_paths = let mut inclusive_ancestor_paths =
WithBasename::inclusive_ancestors_of(path); WithBasename::inclusive_ancestors_of(path);
let mut ancestor_path = inclusive_ancestor_paths let mut ancestor_path = inclusive_ancestor_paths
.next() .next()
.expect("expected at least one inclusive ancestor"); .expect("expected at least one inclusive ancestor");
loop { loop {
// TODO: can we avoid allocating an owned key in cases where the // TODO: can we avoid allocating an owned key in cases where the
// map already contains that key, without introducing double // map already contains that key, without introducing double
// lookup? // lookup?
let child_node = let child_node =
child_nodes.entry(ancestor_path.to_owned()).or_default(); child_nodes.entry(to_cow(ancestor_path)).or_default();
if let Some(next) = inclusive_ancestor_paths.next() { if let Some(next) = inclusive_ancestor_paths.next() {
each_ancestor(child_node); each_ancestor(child_node);
ancestor_path = next; ancestor_path = next;
child_nodes = &mut child_node.children; child_nodes = &mut child_node.children;
} else { } else {
return child_node; return child_node;
} }
} }
} }
fn add_or_remove_file( fn add_or_remove_file(
&mut self, &mut self,
path: &HgPath, path: &HgPath,
old_state: EntryState, old_state: EntryState,
new_entry: DirstateEntry, new_entry: DirstateEntry,
) { ) {
let tracked_count_increment = let tracked_count_increment =
match (old_state.is_tracked(), new_entry.state.is_tracked()) { match (old_state.is_tracked(), new_entry.state.is_tracked()) {
(false, true) => 1, (false, true) => 1,
(true, false) => -1, (true, false) => -1,
_ => 0, _ => 0,
}; };
let node = Self::get_or_insert_node_tracing_ancestors( let node = Self::get_or_insert_node(
&mut self.root, &mut self.root,
path, path,
WithBasename::to_cow_owned,
|ancestor| { |ancestor| {
// We can’t use `+= increment` because the counter is unsigned, // We can’t use `+= increment` because the counter is unsigned,
// and we want debug builds to detect accidental underflow // and we want debug builds to detect accidental underflow
// through zero // through zero
match tracked_count_increment { match tracked_count_increment {
1 => ancestor.tracked_descendants_count += 1, 1 => ancestor.tracked_descendants_count += 1,
-1 => ancestor.tracked_descendants_count -= 1, -1 => ancestor.tracked_descendants_count -= 1,
_ => {} _ => {}
}) })
} }
fn copy_map_insert( fn copy_map_insert(
&mut self, &mut self,
key: HgPathBuf, key: HgPathBuf,
value: HgPathBuf, value: HgPathBuf,
) -> Option<HgPathBuf> { ) -> Option<HgPathBuf> {
let node = Self::get_or_insert_node(&mut self.root, &key); let node = Self::get_or_insert_node(
&mut self.root,
&key,
WithBasename::to_cow_owned,
|_ancestor| {},
);
if node.copy_source.is_none() { if node.copy_source.is_none() {
self.nodes_with_copy_source_count += 1 self.nodes_with_copy_source_count += 1
} }
node.copy_source.replace(value.into()).map(Cow::into_owned) node.copy_source.replace(value.into()).map(Cow::into_owned)
} }
fn len(&self) -> usize { fn len(&self) -> usize {
self.nodes_with_entry_count self.nodes_with_entry_count

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

use crate::utils::hg_path::HgPath; use crate::utils::hg_path::HgPath;
use std::borrow::Borrow; use std::borrow::{Borrow, Cow};
/// Wraps `HgPath` or `HgPathBuf` to make it behave "as" its last path /// Wraps `HgPath` or `HgPathBuf` to make it behave "as" its last path
/// component, a.k.a. its base name (as in Python’s `os.path.basename`), but /// component, a.k.a. its base name (as in Python’s `os.path.basename`), but
/// also allow recovering the full path. /// also allow recovering the full path.
/// ///
/// "Behaving as" means that equality and comparison consider only the base /// "Behaving as" means that equality and comparison consider only the base
/// name, and `std::borrow::Borrow` is implemented to return only the base /// name, and `std::borrow::Borrow` is implemented to return only the base
/// name. This allows using the base name as a map key while still being able /// name. This allows using the base name as a map key while still being able
} }
impl<T: AsRef<HgPath> + Ord> Ord for WithBasename<T> { impl<T: AsRef<HgPath> + Ord> Ord for WithBasename<T> {
fn cmp(&self, other: &Self) -> std::cmp::Ordering { fn cmp(&self, other: &Self) -> std::cmp::Ordering {
self.base_name().cmp(other.base_name()) self.base_name().cmp(other.base_name())
} }
} }
impl<T: ?Sized + ToOwned> WithBasename<&'_ T> { impl<'a> WithBasename<&'a HgPath> {
pub fn to_owned(&self) -> WithBasename<T::Owned> { pub fn to_cow_borrowed(self) -> WithBasename<Cow<'a, HgPath>> {
WithBasename {
full_path: Cow::Borrowed(self.full_path),
base_name_start: self.base_name_start,
}
}
pub fn to_cow_owned<'b>(self) -> WithBasename<Cow<'b, HgPath>> {
WithBasename { WithBasename {
full_path: self.full_path.to_owned(), full_path: Cow::Owned(self.full_path.to_owned()),
base_name_start: self.base_name_start, base_name_start: self.base_name_start,
} }
} }
} }
impl<'a> WithBasename<&'a HgPath> { impl<'a> WithBasename<&'a HgPath> {
/// Returns an iterator of `WithBasename<&HgPath>` for the ancestor /// Returns an iterator of `WithBasename<&HgPath>` for the ancestor
/// directory paths of the given `path`, as well as `path` itself. /// directory paths of the given `path`, as well as `path` itself.