Patchwork D6428: rust-discovery: using the children cache in add_missing

login
register
mail settings
Submitter phabricator
Date June 12, 2019, 6:17 p.m.
Message ID <e3ade7344a81f99dcfae81d7f8242ded@localhost.localdomain>
Download mbox | patch
Permalink /patch/40459/
State Not Applicable
Headers show

Comments

phabricator - June 12, 2019, 6:17 p.m.
gracinet updated this revision to Diff 15471.

REPOSITORY
  rHG Mercurial

CHANGES SINCE LAST UPDATE
  https://phab.mercurial-scm.org/D6428?vs=15228&id=15471

CHANGES SINCE LAST ACTION
  https://phab.mercurial-scm.org/D6428/new/

REVISION DETAIL
  https://phab.mercurial-scm.org/D6428

AFFECTED FILES
  rust/hg-core/src/discovery.rs

CHANGE DETAILS




To: gracinet, #hg-reviewers, kevincox
Cc: durin42, kevincox, mercurial-devel

Patch

diff --git a/rust/hg-core/src/discovery.rs b/rust/hg-core/src/discovery.rs
--- a/rust/hg-core/src/discovery.rs
+++ b/rust/hg-core/src/discovery.rs
@@ -228,20 +228,46 @@ 
     }
 
     /// Register revisions known as being missing
+    ///
+    /// We iterate on the children cache to consider the given missing
+    /// revisions together with their relevant descendents.
+    ///
+    /// Enforcing the children cache like we do is very much faster in
+    /// practice than using `dagop::range` except on very large undecided
+    /// sets, for which the discovery process will engage into sampling
+    /// that needs the children cache anyway.
     pub fn add_missing_revisions(
         &mut self,
         missing: impl IntoIterator<Item = Revision>,
     ) -> Result<(), GraphError> {
-        self.ensure_undecided()?;
-        let range = dagops::range(
-            &self.graph,
-            missing,
-            self.undecided.as_ref().unwrap().iter().cloned(),
-        )?;
+        self.ensure_children_cache()?;
+        self.ensure_undecided()?;  // for safety of possible future refactors
+        let children = self.children_cache.as_ref().unwrap();
+        let mut seen: HashSet<Revision> = HashSet::new();
+        let mut tovisit: VecDeque<Revision> = missing.into_iter().collect();
         let undecided_mut = self.undecided.as_mut().unwrap();
-        for missrev in range {
-            self.missing.insert(missrev);
-            undecided_mut.remove(&missrev);
+        while let Some(rev) = tovisit.pop_front() {
+            if !self.missing.insert(rev) {
+                // either it's known to be missing from a previous
+                // invocation, and there's no need to iterate on its
+                // children (we now they are all missing)
+                // or it's from a previous iteration of this loop
+                // and its children have already been queued
+                continue;
+            }
+            undecided_mut.remove(&rev);
+            match children.get(&rev) {
+                None => {
+                    continue;
+                }
+                Some(this_children) => {
+                    for child in this_children.iter().cloned() {
+                        if seen.insert(child) {
+                            tovisit.push_back(child);
+                        }
+                    }
+                }
+            }
         }
         Ok(())
     }
@@ -531,6 +557,22 @@ 
     }
 
     #[test]
+    fn test_add_missing_early_continue() -> Result<(), GraphError> {
+        eprintln!("test_add_missing_early_stop");
+        let mut disco = full_disco();
+        disco.add_common_revisions(vec![13, 3, 4])?;
+        disco.ensure_children_cache()?;
+        // 12 is grand-child of 6 through 9
+        // passing them in this order maximizes the chances of the
+        // early continue to do the wrong thing
+        disco.add_missing_revisions(vec![6, 9, 12])?;
+        assert_eq!(sorted_undecided(&disco), vec![5, 7, 10, 11]);
+        assert_eq!(sorted_missing(&disco), vec![6, 9, 12]);
+        assert!(!disco.is_complete());
+        Ok(())
+    }
+
+    #[test]
     fn test_limit_sample_no_need_to() {
         let sample = vec![1, 2, 3, 4];
         assert_eq!(full_disco().limit_sample(sample, 10), vec![1, 2, 3, 4]);