This is an archive of the discontinued Mercurial Phabricator instance.

Differential D10487

dirstate-tree: Maintain a counter of DirstateEntry’s and copy sources
ClosedPublic

Authored by SimonSapin on Apr 20 2021, 10:17 AM.

Details

Reviewers
Alphare
Group Reviewers
hg-reviewers
Commits
rHG214ae40e136b: dirstate-tree: Maintain a counter of DirstateEntry’s and copy sources
rHG40b0c37c2dd2: dirstate-tree: Maintain a counter of DirstateEntry’s and copy sources
Summary

This allows implementing len for DirstateMap and CopyMap efficiently,
without traversing the tree.

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 20 2021, 10:17 AM
baymax updated this revision to Diff 27137.Apr 20 2021, 1:03 PM

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

Alphare accepted this revision.Apr 22 2021, 4:48 AM
Alphare added a subscriber: Alphare.
Alphare added inline comments.
rust/hg-core/src/dirstate_tree/dirstate_map.rs
125

I'd have used a dedicated enum, but this is fine for a private function.

This revision is now accepted and ready to land.Apr 22 2021, 4:48 AM
SimonSapin added inline comments.May 3 2021, 5:51 AM
rust/hg-core/src/dirstate_tree/dirstate_map.rs
125

Yeah, it’s not great, but a later refactor removes that parameter anyway (pushes its handling to callers).

I could potentially backport that change to simplify review, but it’s not trivial because there’s a number of other changesets in-between.

Revision Contents
Changeset List

Diff 27647

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

use crate::StateMapIter; use crate::StateMapIter;
use crate::StatusError; use crate::StatusError;
use crate::StatusOptions; use crate::StatusOptions;
pub struct DirstateMap { pub struct DirstateMap {
parents: Option<DirstateParents>, parents: Option<DirstateParents>,
dirty_parents: bool, dirty_parents: bool,
root: ChildNodes, root: ChildNodes,
/// Number of nodes anywhere in the tree that have `.entry.is_some()`.
nodes_with_entry_count: usize,
/// Number of nodes anywhere in the tree that have
/// `.copy_source.is_some()`.
nodes_with_copy_source_count: usize,
} }
/// 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.
type ChildNodes = BTreeMap<WithBasename<HgPathBuf>, Node>; type ChildNodes = BTreeMap<WithBasename<HgPathBuf>, Node>;
); );
impl DirstateMap { impl DirstateMap {
pub fn new() -> Self { pub fn new() -> Self {
Self { Self {
parents: None, parents: None,
dirty_parents: false, dirty_parents: false,
root: ChildNodes::new(), root: ChildNodes::new(),
nodes_with_entry_count: 0,
nodes_with_copy_source_count: 0,
} }
} }
fn get_node(&self, path: &HgPath) -> Option<&Node> { fn get_node(&self, path: &HgPath) -> Option<&Node> {
let mut children = &self.root; let mut children = &self.root;
let mut components = path.components(); let mut components = path.components();
let mut component = let mut component =
components.next().expect("expected at least one components"); components.next().expect("expected at least one components");
loop { loop {
let child = children.get(component)?; let child = children.get(component)?;
if let Some(next_component) = components.next() { if let Some(next_component) = components.next() {
component = next_component; component = next_component;
children = &child.children; children = &child.children;
} else { } else {
return Some(child); return Some(child);
} }
} }
} }
fn get_or_insert_node(&mut self, path: &HgPath) -> &mut Node { /// This takes `root` instead of `&mut self` so that callers can mutate
let mut child_nodes = &mut self.root; /// other fields while the returned borrow is still valid
fn get_or_insert_node<'tree>(
root: &'tree mut ChildNodes,
path: &HgPath,
) -> &'tree mut Node {
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 double lookup in all cases without allocating // TODO: can we avoid double lookup in all cases without allocating
// an owned key in cases where the map already contains that key? // an owned key in cases where the map already contains that key?
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;
} }
} }
} }
/// The meaning of `new_copy_source` is:
///
/// * `Some(Some(x))`: set `Node::copy_source` to `Some(x)`
AlphareUnsubmitted
Not Done

I'd have used a dedicated enum, but this is fine for a private function.

Alphare: I'd have used a dedicated enum, but this is fine for a private function.
SimonSapinAuthorUnsubmitted
Done

Yeah, it’s not great, but a later refactor removes that parameter anyway (pushes its handling to callers).

I could potentially backport that change to simplify review, but it’s not trivial because there’s a number of other changesets in-between.

SimonSapin: Yeah, it’s not great, but a later refactor removes that parameter anyway (pushes its handling…
/// * `Some(None)`: set `Node::copy_source` to `None`
/// * `None`: leave `Node::copy_source` unchanged
fn add_file_node(
&mut self,
path: &HgPath,
new_entry: DirstateEntry,
new_copy_source: Option<Option<HgPathBuf>>,
) {
let node = Self::get_or_insert_node(&mut self.root, path);
if node.entry.is_none() {
self.nodes_with_entry_count += 1
}
if let Some(source) = &new_copy_source {
if node.copy_source.is_none() && source.is_some() {
self.nodes_with_copy_source_count += 1
}
if node.copy_source.is_some() && source.is_none() {
self.nodes_with_copy_source_count -= 1
}
}
node.entry = Some(new_entry);
if let Some(source) = new_copy_source {
node.copy_source = source
}
}
fn iter_nodes<'a>( fn iter_nodes<'a>(
&'a self, &'a self,
) -> impl Iterator<Item = (&'a WithBasename<HgPathBuf>, &'a Node)> + 'a ) -> impl Iterator<Item = (&'a WithBasename<HgPathBuf>, &'a Node)> + 'a
{ {
// Depth first tree traversal. // Depth first tree traversal.
// //
// If we could afford internal iteration and recursion, // If we could afford internal iteration and recursion,
// this would look like: // this would look like:
} }
impl super::dispatch::DirstateMapMethods for DirstateMap { impl super::dispatch::DirstateMapMethods for DirstateMap {
fn clear(&mut self) { fn clear(&mut self) {
self.set_parents(&DirstateParents { self.set_parents(&DirstateParents {
p1: NULL_NODE, p1: NULL_NODE,
p2: NULL_NODE, p2: NULL_NODE,
}); });
self.root.clear() self.root.clear();
self.nodes_with_entry_count = 0;
self.nodes_with_copy_source_count = 0;
} }
fn add_file( fn add_file(
&mut self, &mut self,
_filename: &HgPath, _filename: &HgPath,
_old_state: EntryState, _old_state: EntryState,
_entry: DirstateEntry, _entry: DirstateEntry,
) -> Result<(), DirstateMapError> { ) -> Result<(), DirstateMapError> {
) -> Result<Option<&'a DirstateParents>, DirstateError> { ) -> Result<Option<&'a DirstateParents>, DirstateError> {
if file_contents.is_empty() { if file_contents.is_empty() {
return Ok(None); return Ok(None);
} }
let parents = parse_dirstate_entries( let parents = parse_dirstate_entries(
file_contents, file_contents,
|path, entry, copy_source| { |path, entry, copy_source| {
let node = self.get_or_insert_node(path); self.add_file_node(
node.entry = Some(*entry); path,
node.copy_source = copy_source.map(HgPath::to_owned); *entry,
Some(copy_source.map(HgPath::to_owned)),
)
}, },
)?; )?;
if !self.dirty_parents { if !self.dirty_parents {
self.set_parents(parents); self.set_parents(parents);
} }
Ok(Some(parents)) Ok(Some(parents))
Vec<PatternFileWarning>, Vec<PatternFileWarning>,
), ),
StatusError, StatusError,
> { > {
todo!() todo!()
} }
fn copy_map_len(&self) -> usize { fn copy_map_len(&self) -> usize {
todo!() self.nodes_with_copy_source_count
} }
fn copy_map_iter(&self) -> CopyMapIter<'_> { fn copy_map_iter(&self) -> CopyMapIter<'_> {
Box::new(self.iter_nodes().filter_map(|(path, node)| { Box::new(self.iter_nodes().filter_map(|(path, node)| {
node.copy_source node.copy_source
.as_ref() .as_ref()
.map(|copy_source| (path.full_path(), copy_source)) .map(|copy_source| (path.full_path(), copy_source))
})) }))
&mut self, &mut self,
_key: HgPathBuf, _key: HgPathBuf,
_value: HgPathBuf, _value: HgPathBuf,
) -> Option<HgPathBuf> { ) -> Option<HgPathBuf> {
todo!() todo!()
} }
fn len(&self) -> usize { fn len(&self) -> usize {
todo!() self.nodes_with_entry_count
} }
fn contains_key(&self, key: &HgPath) -> bool { fn contains_key(&self, key: &HgPath) -> bool {
self.get(key).is_some() self.get(key).is_some()
} }
fn get(&self, key: &HgPath) -> Option<&DirstateEntry> { fn get(&self, key: &HgPath) -> Option<&DirstateEntry> {
self.get_node(key)?.entry.as_ref() self.get_node(key)?.entry.as_ref()
} }
fn iter(&self) -> StateMapIter<'_> { fn iter(&self) -> StateMapIter<'_> {
Box::new(self.iter_nodes().filter_map(|(path, node)| { Box::new(self.iter_nodes().filter_map(|(path, node)| {
node.entry.as_ref().map(|entry| (path.full_path(), entry)) node.entry.as_ref().map(|entry| (path.full_path(), entry))
})) }))
} }
} }