mercurial-scm/hg: rust/hg-core/src/revlog/nodemap.rs annotate

annotate rust/hg-core/src/revlog/nodemap.rs @ 44183:e52401a95b94

rust-nodemap: NodeMap trait with simplest implementation We're defining here only a small part of the immutable methods it will have at the end. This is so we can focus in the following changesets on the needed abstractions for a mutable append-only serializable version. The first implementor exposes the actual lookup algorithm in its simplest form. It will have to be expanded to account for the missing methods, and the special cases related to NULL_NODE. Differential Revision: https://phab.mercurial-scm.org/D7791

author	Georges Racinet <georges.racinet@octobus.net>
date	Thu, 23 Jan 2020 17:18:13 +0100
parents	63db6657d280
children	220d4d2e3185

rev	line source
44142 63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	1 // Copyright 2018-2020 Georges Racinet <georges.racinet@octobus.net>
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	2 // and Mercurial contributors
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	3 //
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	4 // This software may be used and distributed according to the terms of the
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	5 // GNU General Public License version 2 or any later version.
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	6 //! Indexing facilities for fast retrieval of `Revision` from `Node`
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	7 //!
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	8 //! This provides a variation on the 16-ary radix tree that is
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	9 //! provided as "nodetree" in revlog.c, ready for append-only persistence
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	10 //! on disk.
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	11 //!
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	12 //! Following existing implicit conventions, the "nodemap" terminology
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	13 //! is used in a more abstract context.
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	14
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	15 use super::{
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	16 Node, NodeError, NodePrefix, NodePrefixRef, Revision, RevlogIndex,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	17 };
44142 63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	18 use std::fmt;
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	19 use std::ops::Deref;
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	20
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	21 #[derive(Debug, PartialEq)]
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	22 pub enum NodeMapError {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	23 MultipleResults,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	24 InvalidNodePrefix(NodeError),
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	25 /// A `Revision` stored in the nodemap could not be found in the index
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	26 RevisionNotInIndex(Revision),
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	27 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	28
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	29 impl From<NodeError> for NodeMapError {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	30 fn from(err: NodeError) -> Self {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	31 NodeMapError::InvalidNodePrefix(err)
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	32 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	33 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	34
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	35 /// Mapping system from Mercurial nodes to revision numbers.
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	36 ///
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	37 /// ## `RevlogIndex` and `NodeMap`
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	38 ///
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	39 /// One way to think about their relationship is that
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	40 /// the `NodeMap` is a prefix-oriented reverse index of the `Node` information
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	41 /// carried by a [`RevlogIndex`].
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	42 ///
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	43 /// Many of the methods in this trait take a `RevlogIndex` argument
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	44 /// which is used for validation of their results. This index must naturally
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	45 /// be the one the `NodeMap` is about, and it must be consistent.
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	46 ///
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	47 /// Notably, the `NodeMap` must not store
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	48 /// information about more `Revision` values than there are in the index.
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	49 /// In these methods, an encountered `Revision` is not in the index, a
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	50 /// [`RevisionNotInIndex`] error is returned.
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	51 ///
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	52 /// In insert operations, the rule is thus that the `NodeMap` must always
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	53 /// be updated after the `RevlogIndex`
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	54 /// be updated first, and the `NodeMap` second.
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	55 ///
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	56 /// [`RevisionNotInIndex`]: enum.NodeMapError.html#variant.RevisionNotInIndex
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	57 /// [`RevlogIndex`]: ../trait.RevlogIndex.html
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	58 pub trait NodeMap {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	59 /// Find the unique `Revision` having the given `Node`
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	60 ///
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	61 /// If no Revision matches the given `Node`, `Ok(None)` is returned.
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	62 fn find_node(
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	63 &self,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	64 index: &impl RevlogIndex,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	65 node: &Node,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	66 ) -> Result<Option<Revision>, NodeMapError> {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	67 self.find_bin(index, node.into())
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	68 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	69
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	70 /// Find the unique Revision whose `Node` starts with a given binary prefix
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	71 ///
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	72 /// If no Revision matches the given prefix, `Ok(None)` is returned.
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	73 ///
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	74 /// If several Revisions match the given prefix, a [`MultipleResults`]
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	75 /// error is returned.
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	76 fn find_bin<'a>(
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	77 &self,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	78 idx: &impl RevlogIndex,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	79 prefix: NodePrefixRef<'a>,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	80 ) -> Result<Option<Revision>, NodeMapError>;
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	81
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	82 /// Find the unique Revision whose `Node` hexadecimal string representation
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	83 /// starts with a given prefix
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	84 ///
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	85 /// If no Revision matches the given prefix, `Ok(None)` is returned.
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	86 ///
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	87 /// If several Revisions match the given prefix, a [`MultipleResults`]
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	88 /// error is returned.
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	89 fn find_hex(
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	90 &self,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	91 idx: &impl RevlogIndex,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	92 prefix: &str,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	93 ) -> Result<Option<Revision>, NodeMapError> {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	94 self.find_bin(idx, NodePrefix::from_hex(prefix)?.borrow())
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	95 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	96 }
44142 63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	97
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	98 /// Low level NodeTree [`Blocks`] elements
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	99 ///
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	100 /// These are exactly as for instance on persistent storage.
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	101 type RawElement = i32;
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	102
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	103 /// High level representation of values in NodeTree
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	104 /// [`Blocks`](struct.Block.html)
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	105 ///
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	106 /// This is the high level representation that most algorithms should
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	107 /// use.
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	108 #[derive(Clone, Debug, Eq, PartialEq)]
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	109 enum Element {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	110 Rev(Revision),
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	111 Block(usize),
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	112 None,
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	113 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	114
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	115 impl From<RawElement> for Element {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	116 /// Conversion from low level representation, after endianness conversion.
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	117 ///
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	118 /// See [`Block`](struct.Block.html) for explanation about the encoding.
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	119 fn from(raw: RawElement) -> Element {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	120 if raw >= 0 {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	121 Element::Block(raw as usize)
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	122 } else if raw == -1 {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	123 Element::None
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	124 } else {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	125 Element::Rev(-raw - 2)
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	126 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	127 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	128 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	129
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	130 impl From<Element> for RawElement {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	131 fn from(element: Element) -> RawElement {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	132 match element {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	133 Element::None => 0,
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	134 Element::Block(i) => i as RawElement,
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	135 Element::Rev(rev) => -rev - 2,
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	136 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	137 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	138 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	139
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	140 /// A logical block of the `NodeTree`, packed with a fixed size.
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	141 ///
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	142 /// These are always used in container types implementing `Index<Block>`,
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	143 /// such as `&Block`
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	144 ///
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	145 /// As an array of integers, its ith element encodes that the
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	146 /// ith potential edge from the block, representing the ith hexadecimal digit
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	147 /// (nybble) `i` is either:
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	148 ///
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	149 /// - absent (value -1)
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	150 /// - another `Block` in the same indexable container (value ≥ 0)
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	151 /// - a `Revision` leaf (value ≤ -2)
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	152 ///
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	153 /// Endianness has to be fixed for consistency on shared storage across
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	154 /// different architectures.
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	155 ///
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	156 /// A key difference with the C `nodetree` is that we need to be
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	157 /// able to represent the [`Block`] at index 0, hence -1 is the empty marker
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	158 /// rather than 0 and the `Revision` range upper limit of -2 instead of -1.
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	159 ///
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	160 /// Another related difference is that `NULL_REVISION` (-1) is not
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	161 /// represented at all, because we want an immutable empty nodetree
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	162 /// to be valid.
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	163
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	164 #[derive(Clone, PartialEq)]
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	165 pub struct Block([RawElement; 16]);
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	166
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	167 impl Block {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	168 fn new() -> Self {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	169 Block([-1; 16])
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	170 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	171
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	172 fn get(&self, nybble: u8) -> Element {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	173 Element::from(RawElement::from_be(self.0[nybble as usize]))
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	174 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	175
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	176 fn set(&mut self, nybble: u8, element: Element) {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	177 self.0[nybble as usize] = RawElement::to_be(element.into())
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	178 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	179 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	180
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	181 impl fmt::Debug for Block {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	182 /// sparse representation for testing and debugging purposes
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	183 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	184 f.debug_map()
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	185 .entries((0..16).filter_map(\|i\| match self.get(i) {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	186 Element::None => None,
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	187 element => Some((i, element)),
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	188 }))
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	189 .finish()
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	190 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	191 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	192
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	193 /// A 16-radix tree with the root block at the end
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	194 pub struct NodeTree {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	195 readonly: Box<dyn Deref<Target = [Block]> + Send>,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	196 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	197
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	198 /// Return `None` unless the `Node` for `rev` has given prefix in `index`.
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	199 fn has_prefix_or_none<'p>(
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	200 idx: &impl RevlogIndex,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	201 prefix: NodePrefixRef<'p>,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	202 rev: Revision,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	203 ) -> Result<Option<Revision>, NodeMapError> {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	204 idx.node(rev)
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	205 .ok_or_else(\|\| NodeMapError::RevisionNotInIndex(rev))
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	206 .map(\|node\| {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	207 if prefix.is_prefix_of(node) {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	208 Some(rev)
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	209 } else {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	210 None
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	211 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	212 })
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	213 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	214
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	215 impl NodeTree {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	216 /// Main working method for `NodeTree` searches
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	217 ///
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	218 /// This partial implementation lacks special cases for NULL_REVISION
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	219 fn lookup<'p>(
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	220 &self,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	221 prefix: NodePrefixRef<'p>,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	222 ) -> Result<Option<Revision>, NodeMapError> {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	223 let blocks: &[Block] = &*self.readonly;
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	224 if blocks.is_empty() {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	225 return Ok(None);
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	226 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	227 let mut visit = blocks.len() - 1;
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	228 for i in 0..prefix.len() {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	229 let nybble = prefix.get_nybble(i);
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	230 match blocks[visit].get(nybble) {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	231 Element::None => return Ok(None),
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	232 Element::Rev(r) => return Ok(Some(r)),
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	233 Element::Block(idx) => visit = idx,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	234 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	235 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	236 Err(NodeMapError::MultipleResults)
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	237 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	238 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	239
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	240 impl From<Vec<Block>> for NodeTree {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	241 fn from(vec: Vec<Block>) -> Self {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	242 NodeTree {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	243 readonly: Box::new(vec),
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	244 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	245 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	246 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	247
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	248 impl fmt::Debug for NodeTree {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	249 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	250 let blocks: &[Block] = &*self.readonly;
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	251 write!(f, "readonly: {:?}", blocks)
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	252 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	253 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	254
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	255 impl NodeMap for NodeTree {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	256 fn find_bin<'a>(
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	257 &self,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	258 idx: &impl RevlogIndex,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	259 prefix: NodePrefixRef<'a>,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	260 ) -> Result<Option<Revision>, NodeMapError> {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	261 self.lookup(prefix.clone()).and_then(\|opt\| {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	262 opt.map_or(Ok(None), \|rev\| has_prefix_or_none(idx, prefix, rev))
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	263 })
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	264 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	265 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	266
44142 63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	267 #[cfg(test)]
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	268 mod tests {
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	269 use super::NodeMapError::*;
44142 63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	270 use super::*;
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	271 use crate::revlog::node::{hex_pad_right, Node};
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	272 use std::collections::HashMap;
44142 63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	273
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	274 /// Creates a `Block` using a syntax close to the `Debug` output
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	275 macro_rules! block {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	276 {$($nybble:tt : $variant:ident($val:tt)),*} => (
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	277 {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	278 let mut block = Block::new();
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	279 $(block.set($nybble, Element::$variant($val)));*;
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	280 block
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	281 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	282 )
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	283 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	284
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	285 #[test]
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	286 fn test_block_debug() {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	287 let mut block = Block::new();
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	288 block.set(1, Element::Rev(3));
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	289 block.set(10, Element::Block(0));
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	290 assert_eq!(format!("{:?}", block), "{1: Rev(3), 10: Block(0)}");
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	291 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	292
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	293 #[test]
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	294 fn test_block_macro() {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	295 let block = block! {5: Block(2)};
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	296 assert_eq!(format!("{:?}", block), "{5: Block(2)}");
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	297
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	298 let block = block! {13: Rev(15), 5: Block(2)};
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	299 assert_eq!(format!("{:?}", block), "{5: Block(2), 13: Rev(15)}");
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	300 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	301
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	302 #[test]
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	303 fn test_raw_block() {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	304 let mut raw = [-1; 16];
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	305 raw[0] = 0;
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	306 raw[1] = RawElement::to_be(15);
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	307 raw[2] = RawElement::to_be(-2);
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	308 raw[3] = RawElement::to_be(-1);
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	309 raw[4] = RawElement::to_be(-3);
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	310 let block = Block(raw);
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	311 assert_eq!(block.get(0), Element::Block(0));
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	312 assert_eq!(block.get(1), Element::Block(15));
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	313 assert_eq!(block.get(3), Element::None);
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	314 assert_eq!(block.get(2), Element::Rev(0));
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	315 assert_eq!(block.get(4), Element::Rev(1));
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	316 }
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	317
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	318 type TestIndex = HashMap<Revision, Node>;
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	319
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	320 impl RevlogIndex for TestIndex {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	321 fn node(&self, rev: Revision) -> Option<&Node> {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	322 self.get(&rev)
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	323 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	324
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	325 fn len(&self) -> usize {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	326 self.len()
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	327 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	328 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	329
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	330 /// Pad hexadecimal Node prefix with zeros on the right, then insert
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	331 ///
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	332 /// This avoids having to repeatedly write very long hexadecimal
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	333 /// strings for test data, and brings actual hash size independency.
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	334 fn pad_insert(idx: &mut TestIndex, rev: Revision, hex: &str) {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	335 idx.insert(rev, Node::from_hex(&hex_pad_right(hex)).unwrap());
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	336 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	337
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	338 fn sample_nodetree() -> NodeTree {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	339 NodeTree::from(vec![
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	340 block![0: Rev(9)],
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	341 block![0: Rev(0), 1: Rev(9)],
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	342 block![0: Block(1), 1:Rev(1)],
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	343 ])
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	344 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	345
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	346 #[test]
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	347 fn test_nt_debug() {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	348 let nt = sample_nodetree();
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	349 assert_eq!(
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	350 format!("{:?}", nt),
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	351 "readonly: \
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	352 [{0: Rev(9)}, {0: Rev(0), 1: Rev(9)}, {0: Block(1), 1: Rev(1)}]"
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	353 );
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	354 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	355
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	356 #[test]
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	357 fn test_immutable_find_simplest() -> Result<(), NodeMapError> {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	358 let mut idx: TestIndex = HashMap::new();
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	359 pad_insert(&mut idx, 1, "1234deadcafe");
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	360
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	361 let nt = NodeTree::from(vec![block![1: Rev(1)]]);
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	362 assert_eq!(nt.find_hex(&idx, "1")?, Some(1));
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	363 assert_eq!(nt.find_hex(&idx, "12")?, Some(1));
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	364 assert_eq!(nt.find_hex(&idx, "1234de")?, Some(1));
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	365 assert_eq!(nt.find_hex(&idx, "1a")?, None);
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	366 assert_eq!(nt.find_hex(&idx, "ab")?, None);
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	367
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	368 // and with full binary Nodes
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	369 assert_eq!(nt.find_node(&idx, idx.get(&1).unwrap())?, Some(1));
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	370 let unknown = Node::from_hex(&hex_pad_right("3d")).unwrap();
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	371 assert_eq!(nt.find_node(&idx, &unknown)?, None);
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	372 Ok(())
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	373 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	374
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	375 #[test]
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	376 fn test_immutable_find_one_jump() {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	377 let mut idx = TestIndex::new();
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	378 pad_insert(&mut idx, 9, "012");
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	379 pad_insert(&mut idx, 0, "00a");
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	380
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	381 let nt = sample_nodetree();
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	382
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	383 assert_eq!(nt.find_hex(&idx, "0"), Err(MultipleResults));
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	384 assert_eq!(nt.find_hex(&idx, "01"), Ok(Some(9)));
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	385 assert_eq!(nt.find_hex(&idx, "00"), Ok(Some(0)));
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	386 assert_eq!(nt.find_hex(&idx, "00a"), Ok(Some(0)));
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	387 }
44142 63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	388 }

Mercurial > public > mercurial-scm > hg

annotate rust/hg-core/src/revlog/nodemap.rs @ 44183:e52401a95b94