comparison rust/hg-core/src/revlog/nodemap.rs @ 44387:00d251d32007

rust-nodemap: special case for prefixes of NULL_NODE

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

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

44386:8f7c6656ac79

//!
//! Following existing implicit conventions, the "nodemap" terminology
//! is used in a more abstract context.

use super::{
    Node, NodeError, NodePrefix, NodePrefixRef, Revision, RevlogIndex,
};

use std::fmt;
use std::mem;
use std::ops::Deref;

                None
            }
        })
}

impl NodeTree {
    /// Initiate a NodeTree from an immutable slice-like of `Block`
    ///
    /// We keep `readonly` and clone its root block if it isn't empty.
    fn new(readonly: Box<dyn Deref<Target = [Block]> + Send>) -> Self {

    fn is_empty(&self) -> bool {
        false
    }

    /// Main working method for `NodeTree` searches
    ///
    /// This partial implementation lacks special cases for NULL_REVISION
    fn lookup<'p>(
        &self,
        prefix: NodePrefixRef<'p>,
    ) -> Result<Option<Revision>, NodeMapError> {
        for visit_item in self.visit(prefix) {

    fn find_bin<'a>(
        &self,
        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))
        })
    }
}

#[cfg(test)]
mod tests {

        let nt = sample_nodetree();

        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, "00a"), Ok(Some(0)));
    }

    #[test]
    fn test_mutated_find() -> Result<(), NodeMapError> {
        let mut idx = TestIndex::new();

            growable: vec![block![0: Rev(1), 5: Rev(3)]],
            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, "c")?, Some(2));
        assert_eq!(nt.find_hex(&idx, "00")?, Some(0));
        assert_eq!(nt.find_hex(&idx, "01")?, Some(9));
        Ok(())
    }

    struct TestNtIndex {

44387:00d251d32007

//!
//! Following existing implicit conventions, the "nodemap" terminology
//! is used in a more abstract context.

use super::{
    node::NULL_NODE, Node, NodeError, NodePrefix, NodePrefixRef, Revision,
    RevlogIndex, NULL_REVISION,
};

use std::fmt;
use std::mem;
use std::ops::Deref;

                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 {
    /// Initiate a NodeTree from an immutable slice-like of `Block`
    ///
    /// We keep `readonly` and clone its root block if it isn't empty.
    fn new(readonly: Box<dyn Deref<Target = [Block]> + Send>) -> Self {

    fn is_empty(&self) -> bool {
        false
    }

    /// Main working method for `NodeTree` searches
    fn lookup<'p>(
        &self,
        prefix: NodePrefixRef<'p>,
    ) -> Result<Option<Revision>, NodeMapError> {
        for visit_item in self.visit(prefix) {

    fn find_bin<'a>(
        &self,
        idx: &impl RevlogIndex,
        prefix: NodePrefixRef<'a>,
    ) -> Result<Option<Revision>, NodeMapError> {
        validate_candidate(idx, prefix.clone(), self.lookup(prefix)?)
    }
}

#[cfg(test)]
mod tests {

        let nt = sample_nodetree();

        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"), Err(MultipleResults));
        assert_eq!(nt.find_hex(&idx, "00a"), Ok(Some(0)));
        assert_eq!(nt.find_hex(&idx, "000"), Ok(Some(NULL_REVISION)));
    }

    #[test]
    fn test_mutated_find() -> Result<(), NodeMapError> {
        let mut idx = TestIndex::new();

            growable: vec![block![0: Rev(1), 5: Rev(3)]],
            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, "c")?, Some(2));
        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(())
    }

    struct TestNtIndex {