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

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

… 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.)

Differential Revision: https://phab.mercurial-scm.org/D10922

--- a/rust/hg-core/src/dirstate_tree/dirstate_map.rs	Mon Jun 28 15:52:10 2021 +0200
+++ b/rust/hg-core/src/dirstate_tree/dirstate_map.rs	Mon Jun 28 16:50:19 2021 +0200
@@ -332,6 +332,15 @@
         }
     }
 
+    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 {
         match self {
             NodeRef::InMemory(_path, node) => node.tracked_descendants_count,
@@ -349,7 +358,11 @@
 
     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,
 }
 
@@ -421,6 +434,7 @@
                         if tracked {
                             ancestor.tracked_descendants_count += 1
                         }
+                        ancestor.descendants_with_entry_count += 1
                     },
                 )?;
                 assert!(
@@ -547,6 +561,7 @@
         old_state: EntryState,
         new_entry: DirstateEntry,
     ) -> Result<(), DirstateV2ParseError> {
+        let had_entry = old_state != EntryState::Unknown;
         let tracked_count_increment =
             match (old_state.is_tracked(), new_entry.state.is_tracked()) {
                 (false, true) => 1,
@@ -560,6 +575,10 @@
             path,
             WithBasename::to_cow_owned,
             |ancestor| {
+                if !had_entry {
+                    ancestor.descendants_with_entry_count += 1;
+                }
+
                 // We can’t use `+= increment` because the counter is unsigned,
                 // and we want debug builds to detect accidental underflow
                 // through zero
@@ -570,7 +589,7 @@
                 }
             },
         )?;
-        if !node.data.has_entry() {
+        if !had_entry {
             self.nodes_with_entry_count += 1
         }
         node.data = NodeData::Entry(new_entry);
@@ -755,6 +774,9 @@
                     recur(on_disk, &mut node.children, rest)?
                 {
                     dropped = d;
+                    if dropped.had_entry {
+                        node.descendants_with_entry_count -= 1;
+                    }
                     if dropped.was_tracked {
                         node.tracked_descendants_count -= 1;
                     }
@@ -899,7 +921,8 @@
         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.state()?.is_none())
+            let state = node.state()?;
+            Ok(state.is_none() && node.descendants_with_entry_count() > 0)
         } else {
             Ok(false)
         }

--- a/rust/hg-core/src/dirstate_tree/on_disk.rs	Mon Jun 28 15:52:10 2021 +0200
+++ b/rust/hg-core/src/dirstate_tree/on_disk.rs	Mon Jun 28 16:50:19 2021 +0200
@@ -76,6 +76,7 @@
 
     copy_source: OptPathSlice,
     children: ChildNodes,
+    pub(super) descendants_with_entry_count: Size,
     pub(super) tracked_descendants_count: Size,
 
     /// Dependending on the value of `state`:
@@ -172,7 +173,7 @@
 /// Make sure that size-affecting changes are made knowingly
 fn _static_assert_size_of() {
     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.
@@ -360,6 +361,9 @@
             ),
             copy_source: self.copy_source(on_disk)?.map(Cow::Borrowed),
             data: self.node_data()?,
+            descendants_with_entry_count: self
+                .descendants_with_entry_count
+                .get(),
             tracked_descendants_count: self.tracked_descendants_count.get(),
         })
     }
@@ -565,6 +569,9 @@
                         // Could only panic for paths over 4 GiB
                         .expect("dirstate-v2 offset overflow")
                         .into(),
+                    descendants_with_entry_count: node
+                        .descendants_with_entry_count
+                        .into(),
                     tracked_descendants_count: node
                         .tracked_descendants_count
                         .into(),