We have to behave as though NULL_NODE was stored in the node tree,
although we don't store it.
| Automatic diff as part of commit; lint not applicable. |
| Automatic diff as part of commit; unit tests not applicable. |
| Path | Packages | |||
|---|---|---|---|---|
| M | rust/hg-core/src/revlog/nodemap.rs (40 lines) |
| // Copyright 2018-2020 Georges Racinet <georges.racinet@octobus.net> | // Copyright 2018-2020 Georges Racinet <georges.racinet@octobus.net> | ||||
| // and Mercurial contributors | // and Mercurial contributors | ||||
| // | // | ||||
| // This software may be used and distributed according to the terms of the | // This software may be used and distributed according to the terms of the | ||||
| // GNU General Public License version 2 or any later version. | // GNU General Public License version 2 or any later version. | ||||
| //! Indexing facilities for fast retrieval of `Revision` from `Node` | //! Indexing facilities for fast retrieval of `Revision` from `Node` | ||||
| //! | //! | ||||
| //! This provides a variation on the 16-ary radix tree that is | //! This provides a variation on the 16-ary radix tree that is | ||||
| //! provided as "nodetree" in revlog.c, ready for append-only persistence | //! provided as "nodetree" in revlog.c, ready for append-only persistence | ||||
| //! on disk. | //! on disk. | ||||
| //! | //! | ||||
| //! Following existing implicit conventions, the "nodemap" terminology | //! Following existing implicit conventions, the "nodemap" terminology | ||||
| //! is used in a more abstract context. | //! is used in a more abstract context. | ||||
| use super::{ | use super::{ | ||||
| Node, NodeError, NodePrefix, NodePrefixRef, Revision, RevlogIndex, | node::NULL_NODE, Node, NodeError, NodePrefix, NodePrefixRef, Revision, | ||||
| RevlogIndex, NULL_REVISION, | |||||
| }; | }; | ||||
| use std::fmt; | use std::fmt; | ||||
| use std::mem; | use std::mem; | ||||
| use std::ops::Deref; | use std::ops::Deref; | ||||
| use std::ops::Index; | use std::ops::Index; | ||||
| use std::slice; | use std::slice; | ||||
| if prefix.is_prefix_of(node) { | if prefix.is_prefix_of(node) { | ||||
| Some(rev) | Some(rev) | ||||
| } else { | } else { | ||||
| None | None | ||||
| } | } | ||||
| }) | }) | ||||
| } | } | ||||
| /// 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( | |||||
| idx: &impl RevlogIndex, | |||||
| prefix: NodePrefixRef, | |||||
| 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 { | impl NodeTree { | ||||
| /// Initiate a NodeTree from an immutable slice-like of `Block` | /// Initiate a NodeTree from an immutable slice-like of `Block` | ||||
| /// | /// | ||||
| /// We keep `readonly` and clone its root block if it isn't empty. | /// We keep `readonly` and clone its root block if it isn't empty. | ||||
| fn new(readonly: Box<dyn Deref<Target = [Block]> + Send>) -> Self { | fn new(readonly: Box<dyn Deref<Target = [Block]> + Send>) -> Self { | ||||
| let root = readonly | let root = readonly | ||||
| .last() | .last() | ||||
| .map(|b| b.clone()) | .map(|b| b.clone()) | ||||
| /// | /// | ||||
| /// A `NodeTree` always has at least the mutable root block. | /// A `NodeTree` always has at least the mutable root block. | ||||
| #[allow(dead_code)] | #[allow(dead_code)] | ||||
| fn is_empty(&self) -> bool { | fn is_empty(&self) -> bool { | ||||
| false | false | ||||
| } | } | ||||
| /// Main working method for `NodeTree` searches | /// Main working method for `NodeTree` searches | ||||
| /// | |||||
| /// This partial implementation lacks special cases for NULL_REVISION | |||||
| fn lookup<'p>( | fn lookup<'p>( | ||||
| &self, | &self, | ||||
| prefix: NodePrefixRef<'p>, | prefix: NodePrefixRef<'p>, | ||||
| ) -> Result<Option<Revision>, NodeMapError> { | ) -> Result<Option<Revision>, NodeMapError> { | ||||
| for visit_item in self.visit(prefix) { | for visit_item in self.visit(prefix) { | ||||
| if let Some(opt) = visit_item.final_revision() { | if let Some(opt) = visit_item.final_revision() { | ||||
| return Ok(opt); | return Ok(opt); | ||||
| } | } | ||||
| } | } | ||||
| impl NodeMap for NodeTree { | impl NodeMap for NodeTree { | ||||
| fn find_bin<'a>( | fn find_bin<'a>( | ||||
| &self, | &self, | ||||
| idx: &impl RevlogIndex, | idx: &impl RevlogIndex, | ||||
| prefix: NodePrefixRef<'a>, | prefix: NodePrefixRef<'a>, | ||||
| ) -> Result<Option<Revision>, NodeMapError> { | ) -> Result<Option<Revision>, NodeMapError> { | ||||
| self.lookup(prefix.clone()).and_then(|opt| { | validate_candidate(idx, prefix.clone(), self.lookup(prefix)?) | ||||
| opt.map_or(Ok(None), |rev| has_prefix_or_none(idx, prefix, rev)) | |||||
| }) | |||||
| } | } | ||||
| } | } | ||||
| #[cfg(test)] | #[cfg(test)] | ||||
| mod tests { | mod tests { | ||||
| use super::NodeMapError::*; | use super::NodeMapError::*; | ||||
| use super::*; | use super::*; | ||||
| use crate::revlog::node::{hex_pad_right, Node}; | use crate::revlog::node::{hex_pad_right, Node}; | ||||
| let mut idx = TestIndex::new(); | let mut idx = TestIndex::new(); | ||||
| pad_insert(&mut idx, 9, "012"); | pad_insert(&mut idx, 9, "012"); | ||||
| pad_insert(&mut idx, 0, "00a"); | pad_insert(&mut idx, 0, "00a"); | ||||
| let nt = sample_nodetree(); | let nt = sample_nodetree(); | ||||
| assert_eq!(nt.find_hex(&idx, "0"), Err(MultipleResults)); | 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, "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, "00a"), Ok(Some(0))); | ||||
| assert_eq!(nt.find_hex(&idx, "000"), Ok(Some(NULL_REVISION))); | |||||
| } | } | ||||
| #[test] | #[test] | ||||
| fn test_mutated_find() -> Result<(), NodeMapError> { | fn test_mutated_find() -> Result<(), NodeMapError> { | ||||
| let mut idx = TestIndex::new(); | let mut idx = TestIndex::new(); | ||||
| pad_insert(&mut idx, 9, "012"); | pad_insert(&mut idx, 9, "012"); | ||||
| pad_insert(&mut idx, 0, "00a"); | pad_insert(&mut idx, 0, "00a"); | ||||
| pad_insert(&mut idx, 2, "cafe"); | pad_insert(&mut idx, 2, "cafe"); | ||||
| pad_insert(&mut idx, 3, "15"); | pad_insert(&mut idx, 3, "15"); | ||||
| pad_insert(&mut idx, 1, "10"); | pad_insert(&mut idx, 1, "10"); | ||||
| let nt = NodeTree { | let nt = NodeTree { | ||||
| readonly: sample_nodetree().readonly, | readonly: sample_nodetree().readonly, | ||||
| growable: vec![block![0: Rev(1), 5: Rev(3)]], | growable: vec![block![0: Rev(1), 5: Rev(3)]], | ||||
| root: block![0: Block(1), 1:Block(3), 12: Rev(2)], | root: block![0: Block(1), 1:Block(3), 12: Rev(2)], | ||||
| }; | }; | ||||
| assert_eq!(nt.find_hex(&idx, "10")?, Some(1)); | assert_eq!(nt.find_hex(&idx, "10")?, Some(1)); | ||||
| assert_eq!(nt.find_hex(&idx, "c")?, Some(2)); | 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)); | assert_eq!(nt.find_hex(&idx, "01")?, Some(9)); | ||||
| Ok(()) | Ok(()) | ||||
| } | } | ||||
| struct TestNtIndex { | struct TestNtIndex { | ||||
| index: TestIndex, | index: TestIndex, | ||||
| nt: NodeTree, | nt: NodeTree, | ||||
| } | } | ||||