This is an archive of the discontinued Mercurial Phabricator instance.

Differential D10490

dirstate-tree: Add has_dir and has_tracked_dir
ClosedPublic

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

Details

Reviewers
Alphare
Group Reviewers
hg-reviewers
Commits
rHG52906934b775: dirstate-tree: Add has_dir and has_tracked_dir
rHG715b14e1c188: dirstate-tree: Add has_dir and has_tracked_dir
Summary

A node without a DirstateMap entry represents a directory.

Only some values of EntryState represent tracked files.
A directory is considered "tracked" if it contains any descendant file that
is tracked. To avoid a sub-tree traversal in has_tracked_dir we add a
counter for this. A boolean flag would become insufficent when we implement
remove_file and drop_file.

add_file_node is more general than needed here, in anticipation of adding
the add_file and remove_file methods.

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 27140.Apr 20 2021, 1:03 PM

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

Alphare added a subscriber: Alphare.Apr 22 2021, 5:10 AM
Alphare added inline comments.
rust/hg-core/src/dirstate_tree/dirstate_map.rs
57

Not always true: a file that used to be a directory with one or more children that have all been marked as removed will have children.

SimonSapin added inline comments.May 3 2021, 6:02 AM
rust/hg-core/src/dirstate_tree/dirstate_map.rs
57

Indeed. I’ll remove this comment.

SimonSapin updated this revision to Diff 27316.May 3 2021, 6:24 AM
Alphare accepted this revision.May 3 2021, 9:01 AM
This revision is now accepted and ready to land.May 3 2021, 9:01 AM
SimonSapin added a commit: rHG715b14e1c188: dirstate-tree: Add has_dir and has_tracked_dir.May 6 2021, 12:52 PM
Closed by commit rHG715b14e1c188: dirstate-tree: Add has_dir and has_tracked_dir (authored by SimonSapin). · Explain Why
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

Diff 27650

rust/hg-core/src/dirstate.rs

pub enum EntryState { pub enum EntryState {
Normal, Normal,
Added, Added,
Removed, Removed,
Merged, Merged,
Unknown, Unknown,
} }
impl EntryState {
pub fn is_tracked(self) -> bool {
use EntryState::*;
match self {
Normal | Added | Merged => true,
Removed | Unknown => false,
}
}
}
impl TryFrom<u8> for EntryState { impl TryFrom<u8> for EntryState {
type Error = HgError; type Error = HgError;
fn try_from(value: u8) -> Result<Self, Self::Error> { fn try_from(value: u8) -> Result<Self, Self::Error> {
match value { match value {
b'n' => Ok(EntryState::Normal), b'n' => Ok(EntryState::Normal),
b'a' => Ok(EntryState::Added), b'a' => Ok(EntryState::Added),
b'r' => Ok(EntryState::Removed), b'r' => Ok(EntryState::Removed),

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.
type ChildNodes = BTreeMap<WithBasename<HgPathBuf>, Node>; type ChildNodes = BTreeMap<WithBasename<HgPathBuf>, Node>;
/// Represents a file or a directory
#[derive(Default)] #[derive(Default)]
struct Node { struct Node {
/// `None` for directories
entry: Option<DirstateEntry>, entry: Option<DirstateEntry>,
copy_source: Option<HgPathBuf>, copy_source: Option<HgPathBuf>,
children: ChildNodes, children: ChildNodes,
AlphareUnsubmitted
Not Done

Not always true: a file that used to be a directory with one or more children that have all been marked as removed will have children.

Alphare: Not always true: a file that used to be a directory with one or more children that have all…
SimonSapinAuthorUnsubmitted
Done

Indeed. I’ll remove this comment.

SimonSapin: Indeed. I’ll remove this comment.
/// How many (non-inclusive) descendants of this node are tracked files
tracked_descendants_count: usize,
}
impl Node {
/// Whether this node has a `DirstateEntry` with `.state.is_tracked()`
fn is_tracked_file(&self) -> bool {
if let Some(entry) = &self.entry {
entry.state.is_tracked()
} else {
false
}
}
} }
/// `(full_path, entry, copy_source)` /// `(full_path, entry, copy_source)`
type NodeDataMut<'a> = ( type NodeDataMut<'a> = (
&'a WithBasename<HgPathBuf>, &'a WithBasename<HgPathBuf>,
&'a mut Option<DirstateEntry>, &'a mut Option<DirstateEntry>,
&'a mut Option<HgPathBuf>, &'a mut Option<HgPathBuf>,
); );
component = next_component; component = next_component;
children = &child.children; children = &child.children;
} else { } else {
return Some(child); return Some(child);
} }
} }
} }
/// Returns a mutable reference to the node at `path` if it exists
///
/// This takes `root` instead of `&mut self` so that callers can mutate /// This takes `root` instead of `&mut self` so that callers can mutate
/// other fields while the returned borrow is still valid /// other fields while the returned borrow is still valid
fn get_node_mut<'tree>( fn get_node_mut<'tree>(
root: &'tree mut ChildNodes, root: &'tree mut ChildNodes,
path: &HgPath, path: &HgPath,
) -> Option<&'tree mut Node> { ) -> Option<&'tree mut Node> {
Self::each_and_get(root, path, |_| {})
}
/// Call `each` for each ancestor node of the one at `path` (not including
/// that node itself), starting from nearest the root.
///
/// Panics (possibly after some calls to `each`) if there is no node at
/// `path`.
fn for_each_ancestor_node<'tree>(
&mut self,
path: &HgPath,
each: impl FnMut(&mut Node),
) {
let parent = path.parent();
if !parent.is_empty() {
Self::each_and_get(&mut self.root, parent, each)
.expect("missing dirstate node");
}
}
/// Common implementation detail of `get_node_mut` and
/// `for_each_ancestor_node`
fn each_and_get<'tree>(
root: &'tree mut ChildNodes,
path: &HgPath,
mut each: impl FnMut(&mut Node),
) -> Option<&'tree mut Node> {
let mut children = root; let mut children = 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_mut(component)?; let child = children.get_mut(component)?;
each(child);
if let Some(next_component) = components.next() { if let Some(next_component) = components.next() {
component = next_component; component = next_component;
children = &mut child.children; children = &mut child.children;
} else { } else {
return Some(child); return Some(child);
} }
} }
} }
if let Some(source) = &new_copy_source { if let Some(source) = &new_copy_source {
if node.copy_source.is_none() && source.is_some() { if node.copy_source.is_none() && source.is_some() {
self.nodes_with_copy_source_count += 1 self.nodes_with_copy_source_count += 1
} }
if node.copy_source.is_some() && source.is_none() { if node.copy_source.is_some() && source.is_none() {
self.nodes_with_copy_source_count -= 1 self.nodes_with_copy_source_count -= 1
} }
} }
let tracked_count_increment =
match (node.is_tracked_file(), new_entry.state.is_tracked()) {
(false, true) => 1,
(true, false) => -1,
_ => 0,
};
node.entry = Some(new_entry); node.entry = Some(new_entry);
if let Some(source) = new_copy_source { if let Some(source) = new_copy_source {
node.copy_source = source node.copy_source = source
} }
// Borrow of `self.root` through `node` ends here
match tracked_count_increment {
1 => self.for_each_ancestor_node(path, |node| {
node.tracked_descendants_count += 1
}),
// We can’t use `+= -1` because the counter is unsigned
-1 => self.for_each_ancestor_node(path, |node| {
node.tracked_descendants_count -= 1
}),
_ => {}
}
} }
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.
// //
fn iter_other_parent_paths( fn iter_other_parent_paths(
&mut self, &mut self,
) -> Box<dyn Iterator<Item = &HgPathBuf> + Send + '_> { ) -> Box<dyn Iterator<Item = &HgPathBuf> + Send + '_> {
todo!() todo!()
} }
fn has_tracked_dir( fn has_tracked_dir(
&mut self, &mut self,
_directory: &HgPath, directory: &HgPath,
) -> Result<bool, DirstateMapError> { ) -> Result<bool, DirstateMapError> {
todo!() if let Some(node) = self.get_node(directory) {
// A node without a `DirstateEntry` was created to hold child
// nodes, and is therefore a directory.
Ok(node.entry.is_none() && node.tracked_descendants_count > 0)
} else {
Ok(false)
}
} }
fn has_dir( fn has_dir(
&mut self, &mut self,
_directory: &HgPath, directory: &HgPath,
) -> Result<bool, DirstateMapError> { ) -> Result<bool, DirstateMapError> {
todo!() if let Some(node) = self.get_node(directory) {
// A node without a `DirstateEntry` was created to hold child
// nodes, and is therefore a directory.
Ok(node.entry.is_none())
} else {
Ok(false)
}
} }
fn parents( fn parents(
&mut self, &mut self,
file_contents: &[u8], file_contents: &[u8],
) -> Result<&DirstateParents, DirstateError> { ) -> Result<&DirstateParents, DirstateError> {
if self.parents.is_none() { if self.parents.is_none() {
let parents = if !file_contents.is_empty() { let parents = if !file_contents.is_empty() {
Ok(packed) Ok(packed)
} }
fn build_file_fold_map(&mut self) -> &FastHashMap<HgPathBuf, HgPathBuf> { fn build_file_fold_map(&mut self) -> &FastHashMap<HgPathBuf, HgPathBuf> {
todo!() todo!()
} }
fn set_all_dirs(&mut self) -> Result<(), DirstateMapError> { fn set_all_dirs(&mut self) -> Result<(), DirstateMapError> {
todo!() // Do nothing, this `DirstateMap` does not a separate `all_dirs` that
// needs to be recomputed
Ok(())
} }
fn set_dirs(&mut self) -> Result<(), DirstateMapError> { fn set_dirs(&mut self) -> Result<(), DirstateMapError> {
todo!() // Do nothing, this `DirstateMap` does not a separate `dirs` that needs
// to be recomputed
Ok(())
} }
fn status<'a>( fn status<'a>(
&'a self, &'a self,
_matcher: &'a (dyn Matcher + Sync), _matcher: &'a (dyn Matcher + Sync),
_root_dir: PathBuf, _root_dir: PathBuf,
_ignore_files: Vec<PathBuf>, _ignore_files: Vec<PathBuf>,
_options: StatusOptions, _options: StatusOptions,