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

login
register
mail settings
Submitter phabricator
Date Jan. 6, 2020, 7:26 p.m.
Message ID <differential-rev-PHID-DREV-sxoq6qqgmje25pejtwp4-req@mercurial-scm.org>
Download mbox | patch
Permalink /patch/44157/
State Superseded
Headers show

Comments

phabricator - Jan. 6, 2020, 7:26 p.m.
gracinet created this revision.
Herald added subscribers: mercurial-devel, kevincox, durin42.
Herald added a reviewer: hg-reviewers.

REVISION SUMMARY
  We have to behave as though NULL_NODE was stored in the node tree,
  although we don't store it.

REPOSITORY
  rHG Mercurial

BRANCH
  default

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

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

CHANGE DETAILS




To: gracinet, #hg-reviewers
Cc: durin42, kevincox, mercurial-devel
phabricator - Feb. 7, 2020, 7:52 p.m.
marmoute added a comment.
marmoute accepted this revision.


  looks good to me too.

REPOSITORY
  rHG Mercurial

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

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

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

Patch

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(())
     }