( )⚙ D10922 dirstate-tree: Keep a counter of descendant nodes that have an entry

This is an archive of the discontinued Mercurial Phabricator instance.

Differential D10922

dirstate-tree: Keep a counter of descendant nodes that have an entry
ClosedPublic

Authored by SimonSapin on Jul 2 2021, 8:36 AM.

Details

Reviewers
Alphare
Group Reviewers
hg-reviewers
Commits
rHGca8121d26732: dirstate-tree: Keep a counter of descendant nodes that have an entry
Summary

… and change the DirstateMap::has_dir method to be based on this counter
being non-zero instead of the mere presence of a node.

A node with zero descendent with an entry currently should be removed from
the tree, but soon we’ll make the dirstate track additional nodes.
(Specifically, for non-ignored directories in order to keep track of their
mtime and optimize status by doing fewer read_dir calls.)

Diff Detail

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

Event Timeline

SimonSapin created this revision.Jul 2 2021, 8:36 AM
Alphare accepted this revision.Jul 2 2021, 12:18 PM
This revision is now accepted and ready to land.Jul 2 2021, 12:18 PM

Revision Contents
Changeset List

Diff 28723

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

NodeRef::InMemory(_path, node) => match &node.data { NodeRef::InMemory(_path, node) => match &node.data {
NodeData::CachedDirectory { mtime } => Some(mtime), NodeData::CachedDirectory { mtime } => Some(mtime),
_ => None, _ => None,
}, },
NodeRef::OnDisk(node) => node.cached_directory_mtime(), NodeRef::OnDisk(node) => node.cached_directory_mtime(),
} }
} }
pub(super) fn descendants_with_entry_count(&self) -> u32 {
match self {
NodeRef::InMemory(_path, node) => {
node.descendants_with_entry_count
}
NodeRef::OnDisk(node) => node.descendants_with_entry_count.get(),
}
}
pub(super) fn tracked_descendants_count(&self) -> u32 { pub(super) fn tracked_descendants_count(&self) -> u32 {
match self { match self {
NodeRef::InMemory(_path, node) => node.tracked_descendants_count, NodeRef::InMemory(_path, node) => node.tracked_descendants_count,
NodeRef::OnDisk(node) => node.tracked_descendants_count.get(), NodeRef::OnDisk(node) => node.tracked_descendants_count.get(),
} }
} }
} }
/// 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> {
pub(super) data: NodeData, pub(super) data: NodeData,
pub(super) copy_source: Option<Cow<'on_disk, HgPath>>, pub(super) copy_source: Option<Cow<'on_disk, HgPath>>,
pub(super) children: ChildNodes<'on_disk>, pub(super) children: ChildNodes<'on_disk>,
/// How many (non-inclusive) descendants of this node are tracked files /// How many (non-inclusive) descendants of this node have an entry.
pub(super) descendants_with_entry_count: u32,
/// How many (non-inclusive) descendants of this node have an entry whose
/// state is "tracked".
pub(super) tracked_descendants_count: u32, pub(super) tracked_descendants_count: u32,
} }
pub(super) enum NodeData { pub(super) enum NodeData {
Entry(DirstateEntry), Entry(DirstateEntry),
CachedDirectory { mtime: on_disk::Timestamp }, CachedDirectory { mtime: on_disk::Timestamp },
None, None,
} }
map.on_disk, map.on_disk,
&mut map.root, &mut map.root,
path, path,
WithBasename::to_cow_borrowed, WithBasename::to_cow_borrowed,
|ancestor| { |ancestor| {
if tracked { if tracked {
ancestor.tracked_descendants_count += 1 ancestor.tracked_descendants_count += 1
} }
ancestor.descendants_with_entry_count += 1
}, },
)?; )?;
assert!( assert!(
!node.data.has_entry(), !node.data.has_entry(),
"duplicate dirstate entry in read" "duplicate dirstate entry in read"
); );
assert!( assert!(
node.copy_source.is_none(), node.copy_source.is_none(),
} }
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,
) -> Result<(), DirstateV2ParseError> { ) -> Result<(), DirstateV2ParseError> {
let had_entry = old_state != EntryState::Unknown;
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( let node = Self::get_or_insert_node(
self.on_disk, self.on_disk,
&mut self.root, &mut self.root,
path, path,
WithBasename::to_cow_owned, WithBasename::to_cow_owned,
|ancestor| { |ancestor| {
if !had_entry {
ancestor.descendants_with_entry_count += 1;
}
// 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,
_ => {} _ => {}
} }
}, },
)?; )?;
if !node.data.has_entry() { if !had_entry {
self.nodes_with_entry_count += 1 self.nodes_with_entry_count += 1
} }
node.data = NodeData::Entry(new_entry); node.data = NodeData::Entry(new_entry);
Ok(()) Ok(())
} }
fn iter_nodes<'tree>( fn iter_nodes<'tree>(
&'tree self, &'tree self,
return Ok(None); return Ok(None);
}; };
let dropped; let dropped;
if let Some(rest) = rest_of_path { if let Some(rest) = rest_of_path {
if let Some((d, removed)) = if let Some((d, removed)) =
recur(on_disk, &mut node.children, rest)? recur(on_disk, &mut node.children, rest)?
{ {
dropped = d; dropped = d;
if dropped.had_entry {
node.descendants_with_entry_count -= 1;
}
if dropped.was_tracked { if dropped.was_tracked {
node.tracked_descendants_count -= 1; node.tracked_descendants_count -= 1;
} }
// Directory caches must be invalidated when removing a // Directory caches must be invalidated when removing a
// child node // child node
if removed { if removed {
if let NodeData::CachedDirectory { .. } = &node.data { if let NodeData::CachedDirectory { .. } = &node.data {
Ok(false) Ok(false)
} }
} }
fn has_dir(&mut self, directory: &HgPath) -> Result<bool, DirstateError> { fn has_dir(&mut self, directory: &HgPath) -> Result<bool, DirstateError> {
if let Some(node) = self.get_node(directory)? { if let Some(node) = self.get_node(directory)? {
// A node without a `DirstateEntry` was created to hold child // A node without a `DirstateEntry` was created to hold child
// nodes, and is therefore a directory. // nodes, and is therefore a directory.
Ok(node.state()?.is_none()) let state = node.state()?;
Ok(state.is_none() && node.descendants_with_entry_count() > 0)
} else { } else {
Ok(false) Ok(false)
} }
} }
#[timed] #[timed]
fn pack_v1( fn pack_v1(
&mut self, &mut self,

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

pub(super) struct Node { pub(super) struct Node {
full_path: PathSlice, full_path: PathSlice,
/// In bytes from `self.full_path.start` /// In bytes from `self.full_path.start`
base_name_start: Size, base_name_start: Size,
copy_source: OptPathSlice, copy_source: OptPathSlice,
children: ChildNodes, children: ChildNodes,
pub(super) descendants_with_entry_count: Size,
pub(super) tracked_descendants_count: Size, pub(super) tracked_descendants_count: Size,
/// Dependending on the value of `state`: /// Dependending on the value of `state`:
/// ///
/// * A null byte: `data` is not used. /// * A null byte: `data` is not used.
/// ///
/// * A `n`, `a`, `r`, or `m` ASCII byte: `state` and `data` together /// * A `n`, `a`, `r`, or `m` ASCII byte: `state` and `data` together
/// represent a dirstate entry like in the v1 format. /// represent a dirstate entry like in the v1 format.
type PathSlice = Slice; type PathSlice = Slice;
/// Either nothing if `start == 0`, or a `HgPath` of `len` bytes /// Either nothing if `start == 0`, or a `HgPath` of `len` bytes
type OptPathSlice = Slice; type OptPathSlice = Slice;
/// Make sure that size-affecting changes are made knowingly /// Make sure that size-affecting changes are made knowingly
fn _static_assert_size_of() { fn _static_assert_size_of() {
let _ = std::mem::transmute::<Header, [u8; 88]>; let _ = std::mem::transmute::<Header, [u8; 88]>;
let _ = std::mem::transmute::<Node, [u8; 45]>; let _ = std::mem::transmute::<Node, [u8; 49]>;
} }
/// Unexpected file format found in `.hg/dirstate` with the "v2" format. /// Unexpected file format found in `.hg/dirstate` with the "v2" format.
/// ///
/// This should only happen if Mercurial is buggy or a repository is corrupted. /// This should only happen if Mercurial is buggy or a repository is corrupted.
#[derive(Debug)] #[derive(Debug)]
pub struct DirstateV2ParseError; pub struct DirstateV2ParseError;
on_disk: &'on_disk [u8], on_disk: &'on_disk [u8],
) -> Result<dirstate_map::Node<'on_disk>, DirstateV2ParseError> { ) -> Result<dirstate_map::Node<'on_disk>, DirstateV2ParseError> {
Ok(dirstate_map::Node { Ok(dirstate_map::Node {
children: dirstate_map::ChildNodes::OnDisk( children: dirstate_map::ChildNodes::OnDisk(
self.children(on_disk)?, self.children(on_disk)?,
), ),
copy_source: self.copy_source(on_disk)?.map(Cow::Borrowed), copy_source: self.copy_source(on_disk)?.map(Cow::Borrowed),
data: self.node_data()?, data: self.node_data()?,
descendants_with_entry_count: self
.descendants_with_entry_count
.get(),
tracked_descendants_count: self.tracked_descendants_count.get(), tracked_descendants_count: self.tracked_descendants_count.get(),
}) })
} }
} }
impl Entry { impl Entry {
fn from_timestamp(timestamp: Timestamp) -> Self { fn from_timestamp(timestamp: Timestamp) -> Self {
// Safety: both types implement the `ByteCast` trait, so we could // Safety: both types implement the `ByteCast` trait, so we could
Node { Node {
children, children,
copy_source, copy_source,
full_path, full_path,
base_name_start: u32::try_from(path.base_name_start()) base_name_start: u32::try_from(path.base_name_start())
// Could only panic for paths over 4 GiB // Could only panic for paths over 4 GiB
.expect("dirstate-v2 offset overflow") .expect("dirstate-v2 offset overflow")
.into(), .into(),
descendants_with_entry_count: node
.descendants_with_entry_count
.into(),
tracked_descendants_count: node tracked_descendants_count: node
.tracked_descendants_count .tracked_descendants_count
.into(), .into(),
state, state,
data, data,
} }
} }
NodeRef::OnDisk(node) => Node { NodeRef::OnDisk(node) => Node {