D7798: rust-nodemap: special case for prefixes of NULL_NODE

[gracinet (Georges Racinet)]

gracinet updated this revision to Diff 19138.

REPOSITORY
  rHG Mercurial

CHANGES SINCE LAST UPDATE
  https://phab.mercurial-scm.org/D7798?vs=19047&id=19138

BRANCH
  default

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

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

AFFECTED FILES
  rust/hg-core/src/revlog/nodemap.rs

CHANGE DETAILS

diff --git a/rust/hg-core/src/revlog/nodemap.rs b/rust/hg-core/src/revlog/nodemap.rs
--- a/rust/hg-core/src/revlog/nodemap.rs
+++ b/rust/hg-core/src/revlog/nodemap.rs
@@ -13,8 +13,8 @@
 //! is used in a more abstract context.
 
 use super::{
-    node::get_nybble, Node, NodeError, NodePrefix, NodePrefixRef, Revision,
-    RevlogIndex,
+    node::get_nybble, node::NULL_NODE, Node, NodeError, NodePrefix,
+    NodePrefixRef, Revision, RevlogIndex, NULL_REVISION,
 };
 use std::fmt;
 use std::mem;
@@ -209,6 +209,31 @@
         })
 }
 
+/// validate that the candidate's node starts indeed with given prefix,
+/// and treat ambiguities related to `NULL_REVISION`.
+///
+/// From the data in the NodeTree, one can only conclude that some
+/// revision is the only one for a *subprefix* of the one being looked up.
+fn validate_candidate<'p>(
+    idx: &impl RevlogIndex,
+    prefix: NodePrefixRef<'p>,
+    rev: Option<Revision>,
+) -> Result<Option<Revision>, NodeMapError> {
+    if prefix.is_prefix_of(&NULL_NODE) {
+        // NULL_REVISION always matches a prefix made only of zeros
+        // and any other *valid* result is an ambiguity
+        match rev {
+            None => Ok(Some(NULL_REVISION)),
+            Some(r) => match has_prefix_or_none(idx, prefix, r)? {
+                None => Ok(Some(NULL_REVISION)),
+                _ => Err(NodeMapError::MultipleResults),
+            },
+        }
+    } else {
+        rev.map_or(Ok(None), |r| has_prefix_or_none(idx, prefix, r))
+    }
+}
+
 impl NodeTree {
     /// Initiate a NodeTree from an immutable slice-like of `Block`
     ///
@@ -282,9 +307,6 @@
     }
 
     /// Main working method for `NodeTree` searches
-    ///
-    /// This partial implementation lacks
-    /// - special cases for NULL_REVISION
     fn lookup<'p>(
         &self,
         prefix: NodePrefixRef<'p>,
@@ -519,9 +541,7 @@
         idx: &impl RevlogIndex,
         prefix: NodePrefixRef<'a>,
     ) -> Result<Option<Revision>, NodeMapError> {
-        self.lookup(prefix.clone()).and_then(|opt| {
-            opt.map_or(Ok(None), |rev| has_prefix_or_none(idx, prefix, rev))
-        })
+        validate_candidate(idx, prefix.clone(), self.lookup(prefix)?)
     }
 }
 
@@ -645,8 +665,9 @@
 
         assert_eq!(nt.find_hex(&idx, "0"), Err(MultipleResults));
         assert_eq!(nt.find_hex(&idx, "01"), Ok(Some(9)));
-        assert_eq!(nt.find_hex(&idx, "00"), Ok(Some(0)));
+        assert_eq!(nt.find_hex(&idx, "00"), Err(MultipleResults));
         assert_eq!(nt.find_hex(&idx, "00a"), Ok(Some(0)));
+        assert_eq!(nt.find_hex(&idx, "000"), Ok(Some(NULL_REVISION)));
     }
 
     #[test]
@@ -665,7 +686,8 @@
         };
         assert_eq!(nt.find_hex(&idx, "10")?, Some(1));
         assert_eq!(nt.find_hex(&idx, "c")?, Some(2));
-        assert_eq!(nt.find_hex(&idx, "00")?, Some(0));
+        assert_eq!(nt.find_hex(&idx, "00"), Err(MultipleResults));
+        assert_eq!(nt.find_hex(&idx, "000")?, Some(NULL_REVISION));
         assert_eq!(nt.find_hex(&idx, "01")?, Some(9));
         Ok(())
     }



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