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

annotate rust/hg-core/src/revlog/nodemap.rs @ 50818:28c0fcff24e5 stable

rhg: fix the bug where sparse config is interpreted as relglob instead of glob relglob apparently (in contrast with relpath) matches everywhere in the tree, whereas glob only matches at the root. The python version interprets these patterns as "glob" (see "normalize(include, b'glob', ...)" in match.py)

author	Arseniy Alekseyev <aalekseyev@janestreet.com>
date	Thu, 10 Aug 2023 19:00:19 +0100
parents	3894763d92f8
children	1928b770e3e7 eccf7dc7c91e

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::{
46432 18a261b11b20 rust: Remove hex parsing from the nodemap Simon Sapin <simon.sapin@octobus.net> parents: 46431 diff changeset	16 node::NULL_NODE, Node, NodePrefix, Revision, RevlogIndex, NULL_REVISION,
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	17 };
44356 d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	18
46390 0800aa42bb4c rust: use the bytes-cast crate to parse persistent nodemaps Simon Sapin <simon.sapin@octobus.net> parents: 44973 diff changeset	19 use bytes_cast::{unaligned, BytesCast};
44388 5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	20 use std::cmp::max;
44142 63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	21 use std::fmt;
46390 0800aa42bb4c rust: use the bytes-cast crate to parse persistent nodemaps Simon Sapin <simon.sapin@octobus.net> parents: 44973 diff changeset	22 use std::mem::{self, align_of, size_of};
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	23 use std::ops::Deref;
44184 220d4d2e3185 rust-nodemap: abstracting the indexing Georges Racinet <georges.racinet@octobus.net> parents: 44183 diff changeset	24 use std::ops::Index;
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	25
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	26 #[derive(Debug, PartialEq)]
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	27 pub enum NodeMapError {
50415 f2deaca3450e rustdoc: fixed or introduced crossrefs in nodemap.rs Georges Racinet <georges.racinet@octobus.net> parents: 50412 diff changeset	28 /// A `NodePrefix` matches several [`Revision`]s.
50416 3894763d92f8 rustdoc: nodemap doc refreshing Georges Racinet <georges.racinet@octobus.net> parents: 50415 diff changeset	29 ///
3894763d92f8 rustdoc: nodemap doc refreshing Georges Racinet <georges.racinet@octobus.net> parents: 50415 diff changeset	30 /// This can be returned by methods meant for (at most) one match.
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	31 MultipleResults,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	32 /// 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	33 RevisionNotInIndex(Revision),
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
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	36 /// 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	37 ///
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	38 /// ## `RevlogIndex` and `NodeMap`
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	39 ///
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	40 /// One way to think about their relationship is that
50416 3894763d92f8 rustdoc: nodemap doc refreshing Georges Racinet <georges.racinet@octobus.net> parents: 50415 diff changeset	41 /// the `NodeMap` is a prefix-oriented reverse index of the [`Node`]
3894763d92f8 rustdoc: nodemap doc refreshing Georges Racinet <georges.racinet@octobus.net> parents: 50415 diff changeset	42 /// information carried by a [`RevlogIndex`].
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	43 ///
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	44 /// 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	45 /// 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	46 /// 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	47 ///
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	48 /// Notably, the `NodeMap` must not store
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	49 /// 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	50 /// In these methods, an encountered `Revision` is not in the index, a
50416 3894763d92f8 rustdoc: nodemap doc refreshing Georges Racinet <georges.racinet@octobus.net> parents: 50415 diff changeset	51 /// [RevisionNotInIndex](NodeMapError) error is returned.
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	52 ///
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	53 /// In insert operations, the rule is thus that the `NodeMap` must always
50416 3894763d92f8 rustdoc: nodemap doc refreshing Georges Racinet <georges.racinet@octobus.net> parents: 50415 diff changeset	54 /// be updated after the `RevlogIndex` it is about.
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	55 pub trait NodeMap {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	56 /// 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	57 ///
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	58 /// 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	59 fn find_node(
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	60 &self,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	61 index: &impl RevlogIndex,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	62 node: &Node,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	63 ) -> Result<Option<Revision>, NodeMapError> {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	64 self.find_bin(index, node.into())
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	65 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	66
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	67 /// 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	68 ///
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	69 /// 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	70 ///
50412 331a3cbe1c9e rustdoc: fixed warnings about links Georges Racinet <georges.racinet@octobus.net> parents: 49930 diff changeset	71 /// If several Revisions match the given prefix, a
331a3cbe1c9e rustdoc: fixed warnings about links Georges Racinet <georges.racinet@octobus.net> parents: 49930 diff changeset	72 /// [MultipleResults](NodeMapError) error is returned.
49930 e98fd81bb151 rust-clippy: fix most warnings in `hg-core` Rapha?l Gom?s <rgomes@octobus.net> parents: 49095 diff changeset	73 fn find_bin(
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	74 &self,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	75 idx: &impl RevlogIndex,
46431 645ee7225fab rust: Make NodePrefix allocation-free and Copy, remove NodePrefixRef Simon Sapin <simon.sapin@octobus.net> parents: 46428 diff changeset	76 prefix: NodePrefix,
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	77 ) -> Result<Option<Revision>, NodeMapError>;
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	78
44388 5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	79 /// Give the size of the shortest node prefix that determines
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	80 /// the revision uniquely.
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	81 ///
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	82 /// From a binary node prefix, if it is matched in the node map, this
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	83 /// returns the number of hexadecimal digits that would had sufficed
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	84 /// to find the revision uniquely.
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	85 ///
50415 f2deaca3450e rustdoc: fixed or introduced crossrefs in nodemap.rs Georges Racinet <georges.racinet@octobus.net> parents: 50412 diff changeset	86 /// Returns `None` if no [`Revision`] could be found for the prefix.
44388 5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	87 ///
50412 331a3cbe1c9e rustdoc: fixed warnings about links Georges Racinet <georges.racinet@octobus.net> parents: 49930 diff changeset	88 /// If several Revisions match the given prefix, a
331a3cbe1c9e rustdoc: fixed warnings about links Georges Racinet <georges.racinet@octobus.net> parents: 49930 diff changeset	89 /// [MultipleResults](NodeMapError) error is returned.
49930 e98fd81bb151 rust-clippy: fix most warnings in `hg-core` Rapha?l Gom?s <rgomes@octobus.net> parents: 49095 diff changeset	90 fn unique_prefix_len_bin(
44388 5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	91 &self,
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	92 idx: &impl RevlogIndex,
46431 645ee7225fab rust: Make NodePrefix allocation-free and Copy, remove NodePrefixRef Simon Sapin <simon.sapin@octobus.net> parents: 46428 diff changeset	93 node_prefix: NodePrefix,
44388 5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	94 ) -> Result<Option<usize>, NodeMapError>;
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	95
50416 3894763d92f8 rustdoc: nodemap doc refreshing Georges Racinet <georges.racinet@octobus.net> parents: 50415 diff changeset	96 /// Same as [unique_prefix_len_bin](Self::unique_prefix_len_bin), with
3894763d92f8 rustdoc: nodemap doc refreshing Georges Racinet <georges.racinet@octobus.net> parents: 50415 diff changeset	97 /// a full [`Node`] as input
44388 5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	98 fn unique_prefix_len_node(
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	99 &self,
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	100 idx: &impl RevlogIndex,
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	101 node: &Node,
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	102 ) -> Result<Option<usize>, NodeMapError> {
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	103 self.unique_prefix_len_bin(idx, node.into())
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	104 }
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	105 }
44142 63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	106
44356 d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	107 pub trait MutableNodeMap: NodeMap {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	108 fn insert<I: RevlogIndex>(
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	109 &mut self,
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	110 index: &I,
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	111 node: &Node,
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	112 rev: Revision,
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	113 ) -> Result<(), NodeMapError>;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	114 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	115
50412 331a3cbe1c9e rustdoc: fixed warnings about links Georges Racinet <georges.racinet@octobus.net> parents: 49930 diff changeset	116 /// Low level NodeTree [`Block`] elements
44142 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 /// These are exactly as for instance on persistent storage.
46390 0800aa42bb4c rust: use the bytes-cast crate to parse persistent nodemaps Simon Sapin <simon.sapin@octobus.net> parents: 44973 diff changeset	119 type RawElement = unaligned::I32Be;
44142 63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	120
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	121 /// High level representation of values in NodeTree
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	122 /// [`Blocks`](struct.Block.html)
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	123 ///
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	124 /// 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	125 /// use.
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	126 #[derive(Clone, Debug, Eq, PartialEq)]
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	127 enum Element {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	128 Rev(Revision),
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	129 Block(usize),
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	130 None,
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	131 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	132
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	133 impl From<RawElement> for Element {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	134 /// 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	135 ///
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	136 /// 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	137 fn from(raw: RawElement) -> Element {
46390 0800aa42bb4c rust: use the bytes-cast crate to parse persistent nodemaps Simon Sapin <simon.sapin@octobus.net> parents: 44973 diff changeset	138 let int = raw.get();
0800aa42bb4c rust: use the bytes-cast crate to parse persistent nodemaps Simon Sapin <simon.sapin@octobus.net> parents: 44973 diff changeset	139 if int >= 0 {
0800aa42bb4c rust: use the bytes-cast crate to parse persistent nodemaps Simon Sapin <simon.sapin@octobus.net> parents: 44973 diff changeset	140 Element::Block(int as usize)
0800aa42bb4c rust: use the bytes-cast crate to parse persistent nodemaps Simon Sapin <simon.sapin@octobus.net> parents: 44973 diff changeset	141 } else if int == -1 {
44142 63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	142 Element::None
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	143 } else {
46390 0800aa42bb4c rust: use the bytes-cast crate to parse persistent nodemaps Simon Sapin <simon.sapin@octobus.net> parents: 44973 diff changeset	144 Element::Rev(-int - 2)
44142 63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	145 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	146 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	147 }
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 impl From<Element> for RawElement {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	150 fn from(element: Element) -> RawElement {
46390 0800aa42bb4c rust: use the bytes-cast crate to parse persistent nodemaps Simon Sapin <simon.sapin@octobus.net> parents: 44973 diff changeset	151 RawElement::from(match element {
44142 63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	152 Element::None => 0,
46390 0800aa42bb4c rust: use the bytes-cast crate to parse persistent nodemaps Simon Sapin <simon.sapin@octobus.net> parents: 44973 diff changeset	153 Element::Block(i) => i as i32,
44142 63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	154 Element::Rev(rev) => -rev - 2,
46390 0800aa42bb4c rust: use the bytes-cast crate to parse persistent nodemaps Simon Sapin <simon.sapin@octobus.net> parents: 44973 diff changeset	155 })
44142 63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	156 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	157 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	158
50416 3894763d92f8 rustdoc: nodemap doc refreshing Georges Racinet <georges.racinet@octobus.net> parents: 50415 diff changeset	159 const ELEMENTS_PER_BLOCK: usize = 16; // number of different values in a nybble
3894763d92f8 rustdoc: nodemap doc refreshing Georges Racinet <georges.racinet@octobus.net> parents: 50415 diff changeset	160
3894763d92f8 rustdoc: nodemap doc refreshing Georges Racinet <georges.racinet@octobus.net> parents: 50415 diff changeset	161 /// A logical block of the [`NodeTree`], packed with a fixed size.
44142 63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	162 ///
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	163 /// 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	164 /// such as `&Block`
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	165 ///
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	166 /// 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	167 /// 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	168 /// (nybble) `i` is either:
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	169 ///
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	170 /// - absent (value -1)
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	171 /// - another `Block` in the same indexable container (value ≥ 0)
50415 f2deaca3450e rustdoc: fixed or introduced crossrefs in nodemap.rs Georges Racinet <georges.racinet@octobus.net> parents: 50412 diff changeset	172 /// - a [`Revision`] leaf (value ≤ -2)
44142 63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	173 ///
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	174 /// 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	175 /// different architectures.
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	176 ///
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	177 /// 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	178 /// able to represent the [`Block`] at index 0, hence -1 is the empty marker
50415 f2deaca3450e rustdoc: fixed or introduced crossrefs in nodemap.rs Georges Racinet <georges.racinet@octobus.net> parents: 50412 diff changeset	179 /// rather than 0 and the [`Revision`] range upper limit of -2 instead of -1.
44142 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 /// 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	182 /// 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	183 /// to be valid.
46390 0800aa42bb4c rust: use the bytes-cast crate to parse persistent nodemaps Simon Sapin <simon.sapin@octobus.net> parents: 44973 diff changeset	184 #[derive(Copy, Clone, BytesCast, PartialEq)]
0800aa42bb4c rust: use the bytes-cast crate to parse persistent nodemaps Simon Sapin <simon.sapin@octobus.net> parents: 44973 diff changeset	185 #[repr(transparent)]
0800aa42bb4c rust: use the bytes-cast crate to parse persistent nodemaps Simon Sapin <simon.sapin@octobus.net> parents: 44973 diff changeset	186 pub struct Block([RawElement; ELEMENTS_PER_BLOCK]);
44142 63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	187
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	188 impl Block {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	189 fn new() -> Self {
46390 0800aa42bb4c rust: use the bytes-cast crate to parse persistent nodemaps Simon Sapin <simon.sapin@octobus.net> parents: 44973 diff changeset	190 let absent_node = RawElement::from(-1);
0800aa42bb4c rust: use the bytes-cast crate to parse persistent nodemaps Simon Sapin <simon.sapin@octobus.net> parents: 44973 diff changeset	191 Block([absent_node; ELEMENTS_PER_BLOCK])
44142 63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	192 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	193
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	194 fn get(&self, nybble: u8) -> Element {
46390 0800aa42bb4c rust: use the bytes-cast crate to parse persistent nodemaps Simon Sapin <simon.sapin@octobus.net> parents: 44973 diff changeset	195 self.0[nybble as usize].into()
44142 63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	196 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	197
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	198 fn set(&mut self, nybble: u8, element: Element) {
46390 0800aa42bb4c rust: use the bytes-cast crate to parse persistent nodemaps Simon Sapin <simon.sapin@octobus.net> parents: 44973 diff changeset	199 self.0[nybble as usize] = element.into()
44142 63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	200 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	201 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	202
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	203 impl fmt::Debug for Block {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	204 /// sparse representation for testing and debugging purposes
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	205 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	206 f.debug_map()
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	207 .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	208 Element::None => None,
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	209 element => Some((i, element)),
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	210 }))
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	211 .finish()
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	212 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	213 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	214
44185 a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	215 /// A mutable 16-radix tree with the root block logically at the end
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	216 ///
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	217 /// Because of the append only nature of our node trees, we need to
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	218 /// keep the original untouched and store new blocks separately.
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	219 ///
50416 3894763d92f8 rustdoc: nodemap doc refreshing Georges Racinet <georges.racinet@octobus.net> parents: 50415 diff changeset	220 /// The mutable root [`Block`] is kept apart so that we don't have to rebump
44185 a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	221 /// it on each insertion.
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	222 pub struct NodeTree {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	223 readonly: Box<dyn Deref<Target = [Block]> + Send>,
44185 a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	224 growable: Vec<Block>,
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	225 root: Block,
44389 6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44388 diff changeset	226 masked_inner_blocks: usize,
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	227 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	228
44184 220d4d2e3185 rust-nodemap: abstracting the indexing Georges Racinet <georges.racinet@octobus.net> parents: 44183 diff changeset	229 impl Index<usize> for NodeTree {
220d4d2e3185 rust-nodemap: abstracting the indexing Georges Racinet <georges.racinet@octobus.net> parents: 44183 diff changeset	230 type Output = Block;
220d4d2e3185 rust-nodemap: abstracting the indexing Georges Racinet <georges.racinet@octobus.net> parents: 44183 diff changeset	231
220d4d2e3185 rust-nodemap: abstracting the indexing Georges Racinet <georges.racinet@octobus.net> parents: 44183 diff changeset	232 fn index(&self, i: usize) -> &Block {
44185 a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	233 let ro_len = self.readonly.len();
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	234 if i < ro_len {
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	235 &self.readonly[i]
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	236 } else if i == ro_len + self.growable.len() {
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	237 &self.root
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	238 } else {
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	239 &self.growable[i - ro_len]
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	240 }
44184 220d4d2e3185 rust-nodemap: abstracting the indexing Georges Racinet <georges.racinet@octobus.net> parents: 44183 diff changeset	241 }
220d4d2e3185 rust-nodemap: abstracting the indexing Georges Racinet <georges.racinet@octobus.net> parents: 44183 diff changeset	242 }
220d4d2e3185 rust-nodemap: abstracting the indexing Georges Racinet <georges.racinet@octobus.net> parents: 44183 diff changeset	243
50416 3894763d92f8 rustdoc: nodemap doc refreshing Georges Racinet <georges.racinet@octobus.net> parents: 50415 diff changeset	244 /// Return `None` unless the [`Node`] for `rev` has given prefix in `idx`.
44385 a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	245 fn has_prefix_or_none(
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	246 idx: &impl RevlogIndex,
46431 645ee7225fab rust: Make NodePrefix allocation-free and Copy, remove NodePrefixRef Simon Sapin <simon.sapin@octobus.net> parents: 46428 diff changeset	247 prefix: NodePrefix,
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	248 rev: Revision,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	249 ) -> Result<Option<Revision>, NodeMapError> {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	250 idx.node(rev)
49930 e98fd81bb151 rust-clippy: fix most warnings in `hg-core` Rapha?l Gom?s <rgomes@octobus.net> parents: 49095 diff changeset	251 .ok_or(NodeMapError::RevisionNotInIndex(rev))
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	252 .map(\|node\| {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	253 if prefix.is_prefix_of(node) {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	254 Some(rev)
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	255 } else {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	256 None
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	257 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	258 })
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	259 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	260
44387 00d251d32007 rust-nodemap: special case for prefixes of NULL_NODE Georges Racinet <georges.racinet@octobus.net> parents: 44385 diff changeset	261 /// validate that the candidate's node starts indeed with given prefix,
50416 3894763d92f8 rustdoc: nodemap doc refreshing Georges Racinet <georges.racinet@octobus.net> parents: 50415 diff changeset	262 /// and treat ambiguities related to [`NULL_REVISION`].
44387 00d251d32007 rust-nodemap: special case for prefixes of NULL_NODE Georges Racinet <georges.racinet@octobus.net> parents: 44385 diff changeset	263 ///
00d251d32007 rust-nodemap: special case for prefixes of NULL_NODE Georges Racinet <georges.racinet@octobus.net> parents: 44385 diff changeset	264 /// From the data in the NodeTree, one can only conclude that some
00d251d32007 rust-nodemap: special case for prefixes of NULL_NODE Georges Racinet <georges.racinet@octobus.net> parents: 44385 diff changeset	265 /// revision is the only one for a subprefix of the one being looked up.
00d251d32007 rust-nodemap: special case for prefixes of NULL_NODE Georges Racinet <georges.racinet@octobus.net> parents: 44385 diff changeset	266 fn validate_candidate(
00d251d32007 rust-nodemap: special case for prefixes of NULL_NODE Georges Racinet <georges.racinet@octobus.net> parents: 44385 diff changeset	267 idx: &impl RevlogIndex,
46431 645ee7225fab rust: Make NodePrefix allocation-free and Copy, remove NodePrefixRef Simon Sapin <simon.sapin@octobus.net> parents: 46428 diff changeset	268 prefix: NodePrefix,
44388 5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	269 candidate: (Option<Revision>, usize),
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	270 ) -> Result<(Option<Revision>, usize), NodeMapError> {
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	271 let (rev, steps) = candidate;
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	272 if let Some(nz_nybble) = prefix.first_different_nybble(&NULL_NODE) {
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	273 rev.map_or(Ok((None, steps)), \|r\| {
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	274 has_prefix_or_none(idx, prefix, r)
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	275 .map(\|opt\| (opt, max(steps, nz_nybble + 1)))
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	276 })
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	277 } else {
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	278 // the prefix is only made of zeros; NULL_REVISION always matches it
44387 00d251d32007 rust-nodemap: special case for prefixes of NULL_NODE Georges Racinet <georges.racinet@octobus.net> parents: 44385 diff changeset	279 // and any other valid result is an ambiguity
00d251d32007 rust-nodemap: special case for prefixes of NULL_NODE Georges Racinet <georges.racinet@octobus.net> parents: 44385 diff changeset	280 match rev {
44388 5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	281 None => Ok((Some(NULL_REVISION), steps + 1)),
44387 00d251d32007 rust-nodemap: special case for prefixes of NULL_NODE Georges Racinet <georges.racinet@octobus.net> parents: 44385 diff changeset	282 Some(r) => match has_prefix_or_none(idx, prefix, r)? {
44388 5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	283 None => Ok((Some(NULL_REVISION), steps + 1)),
44387 00d251d32007 rust-nodemap: special case for prefixes of NULL_NODE Georges Racinet <georges.racinet@octobus.net> parents: 44385 diff changeset	284 _ => Err(NodeMapError::MultipleResults),
00d251d32007 rust-nodemap: special case for prefixes of NULL_NODE Georges Racinet <georges.racinet@octobus.net> parents: 44385 diff changeset	285 },
00d251d32007 rust-nodemap: special case for prefixes of NULL_NODE Georges Racinet <georges.racinet@octobus.net> parents: 44385 diff changeset	286 }
00d251d32007 rust-nodemap: special case for prefixes of NULL_NODE Georges Racinet <georges.racinet@octobus.net> parents: 44385 diff changeset	287 }
00d251d32007 rust-nodemap: special case for prefixes of NULL_NODE Georges Racinet <georges.racinet@octobus.net> parents: 44385 diff changeset	288 }
00d251d32007 rust-nodemap: special case for prefixes of NULL_NODE Georges Racinet <georges.racinet@octobus.net> parents: 44385 diff changeset	289
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	290 impl NodeTree {
44185 a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	291 /// Initiate a NodeTree from an immutable slice-like of `Block`
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	292 ///
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	293 /// We keep `readonly` and clone its root block if it isn't empty.
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	294 fn new(readonly: Box<dyn Deref<Target = [Block]> + Send>) -> Self {
44973 26114bd6ec60 rust: do a clippy pass Rapha?l Gom?s <rgomes@octobus.net> parents: 44390 diff changeset	295 let root = readonly.last().cloned().unwrap_or_else(Block::new);
44185 a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	296 NodeTree {
44973 26114bd6ec60 rust: do a clippy pass Rapha?l Gom?s <rgomes@octobus.net> parents: 44390 diff changeset	297 readonly,
44185 a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	298 growable: Vec::new(),
44973 26114bd6ec60 rust: do a clippy pass Rapha?l Gom?s <rgomes@octobus.net> parents: 44390 diff changeset	299 root,
44389 6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44388 diff changeset	300 masked_inner_blocks: 0,
44185 a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	301 }
44184 220d4d2e3185 rust-nodemap: abstracting the indexing Georges Racinet <georges.racinet@octobus.net> parents: 44183 diff changeset	302 }
220d4d2e3185 rust-nodemap: abstracting the indexing Georges Racinet <georges.racinet@octobus.net> parents: 44183 diff changeset	303
44385 a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	304 /// Create from an opaque bunch of bytes
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	305 ///
50416 3894763d92f8 rustdoc: nodemap doc refreshing Georges Racinet <georges.racinet@octobus.net> parents: 50415 diff changeset	306 /// The created [`NodeTreeBytes`] from `bytes`,
44385 a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	307 /// of which exactly `amount` bytes are used.
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	308 ///
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	309 /// - `buffer` could be derived from `PyBuffer` and `Mmap` objects.
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	310 /// - `amount` is expressed in bytes, and is not automatically derived from
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	311 /// `bytes`, so that a caller that manages them atomically can perform
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	312 /// temporary disk serializations and still rollback easily if needed.
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	313 /// First use-case for this would be to support Mercurial shell hooks.
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	314 ///
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	315 /// panics if `buffer` is smaller than `amount`
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	316 pub fn load_bytes(
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	317 bytes: Box<dyn Deref<Target = [u8]> + Send>,
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	318 amount: usize,
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	319 ) -> Self {
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	320 NodeTree::new(Box::new(NodeTreeBytes::new(bytes, amount)))
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	321 }
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	322
50415 f2deaca3450e rustdoc: fixed or introduced crossrefs in nodemap.rs Georges Racinet <georges.racinet@octobus.net> parents: 50412 diff changeset	323 /// Retrieve added [`Block`]s and the original immutable data
44385 a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	324 pub fn into_readonly_and_added(
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	325 self,
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	326 ) -> (Box<dyn Deref<Target = [Block]> + Send>, Vec<Block>) {
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	327 let mut vec = self.growable;
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	328 let readonly = self.readonly;
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	329 if readonly.last() != Some(&self.root) {
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	330 vec.push(self.root);
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	331 }
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	332 (readonly, vec)
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	333 }
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	334
50415 f2deaca3450e rustdoc: fixed or introduced crossrefs in nodemap.rs Georges Racinet <georges.racinet@octobus.net> parents: 50412 diff changeset	335 /// Retrieve added [`Block]s as bytes, ready to be written to persistent
44385 a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	336 /// storage
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	337 pub fn into_readonly_and_added_bytes(
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	338 self,
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	339 ) -> (Box<dyn Deref<Target = [Block]> + Send>, Vec<u8>) {
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	340 let (readonly, vec) = self.into_readonly_and_added();
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	341 // Prevent running `v`'s destructor so we are in complete control
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	342 // of the allocation.
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	343 let vec = mem::ManuallyDrop::new(vec);
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	344
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	345 // Transmute the `Vec<Block>` to a `Vec<u8>`. Blocks are contiguous
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	346 // bytes, so this is perfectly safe.
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	347 let bytes = unsafe {
46390 0800aa42bb4c rust: use the bytes-cast crate to parse persistent nodemaps Simon Sapin <simon.sapin@octobus.net> parents: 44973 diff changeset	348 // Check for compatible allocation layout.
0800aa42bb4c rust: use the bytes-cast crate to parse persistent nodemaps Simon Sapin <simon.sapin@octobus.net> parents: 44973 diff changeset	349 // (Optimized away by constant-folding + dead code elimination.)
0800aa42bb4c rust: use the bytes-cast crate to parse persistent nodemaps Simon Sapin <simon.sapin@octobus.net> parents: 44973 diff changeset	350 assert_eq!(size_of::<Block>(), 64);
0800aa42bb4c rust: use the bytes-cast crate to parse persistent nodemaps Simon Sapin <simon.sapin@octobus.net> parents: 44973 diff changeset	351 assert_eq!(align_of::<Block>(), 1);
44385 a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	352
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	353 // /!\ Any use of `vec` after this is use-after-free.
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	354 // TODO: use `into_raw_parts` once stabilized
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	355 Vec::from_raw_parts(
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	356 vec.as_ptr() as *mut u8,
46390 0800aa42bb4c rust: use the bytes-cast crate to parse persistent nodemaps Simon Sapin <simon.sapin@octobus.net> parents: 44973 diff changeset	357 vec.len() * size_of::<Block>(),
0800aa42bb4c rust: use the bytes-cast crate to parse persistent nodemaps Simon Sapin <simon.sapin@octobus.net> parents: 44973 diff changeset	358 vec.capacity() * size_of::<Block>(),
44385 a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	359 )
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	360 };
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	361 (readonly, bytes)
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	362 }
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	363
44185 a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	364 /// Total number of blocks
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	365 fn len(&self) -> usize {
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	366 self.readonly.len() + self.growable.len() + 1
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	367 }
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	368
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	369 /// Implemented for completeness
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	370 ///
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	371 /// A `NodeTree` always has at least the mutable root block.
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	372 #[allow(dead_code)]
44184 220d4d2e3185 rust-nodemap: abstracting the indexing Georges Racinet <georges.racinet@octobus.net> parents: 44183 diff changeset	373 fn is_empty(&self) -> bool {
44185 a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	374 false
44184 220d4d2e3185 rust-nodemap: abstracting the indexing Georges Racinet <georges.racinet@octobus.net> parents: 44183 diff changeset	375 }
220d4d2e3185 rust-nodemap: abstracting the indexing Georges Racinet <georges.racinet@octobus.net> parents: 44183 diff changeset	376
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	377 /// Main working method for `NodeTree` searches
44388 5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	378 ///
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	379 /// The first returned value is the result of analysing `NodeTree` data
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	380 /// alone: whereas `None` guarantees that the given prefix is absent
50415 f2deaca3450e rustdoc: fixed or introduced crossrefs in nodemap.rs Georges Racinet <georges.racinet@octobus.net> parents: 50412 diff changeset	381 /// from the [`NodeTree`] data (but still could match [`NULL_NODE`]), with
f2deaca3450e rustdoc: fixed or introduced crossrefs in nodemap.rs Georges Racinet <georges.racinet@octobus.net> parents: 50412 diff changeset	382 /// `Some(rev)`, it is to be understood that `rev` is the unique
f2deaca3450e rustdoc: fixed or introduced crossrefs in nodemap.rs Georges Racinet <georges.racinet@octobus.net> parents: 50412 diff changeset	383 /// [`Revision`] that could match the prefix. Actually, all that can
f2deaca3450e rustdoc: fixed or introduced crossrefs in nodemap.rs Georges Racinet <georges.racinet@octobus.net> parents: 50412 diff changeset	384 /// be inferred from
44388 5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	385 /// the `NodeTree` data is that `rev` is the revision with the longest
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	386 /// common node prefix with the given prefix.
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	387 ///
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	388 /// The second returned value is the size of the smallest subprefix
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	389 /// of `prefix` that would give the same result, i.e. not the
50415 f2deaca3450e rustdoc: fixed or introduced crossrefs in nodemap.rs Georges Racinet <georges.racinet@octobus.net> parents: 50412 diff changeset	390 /// [MultipleResults](NodeMapError) error variant (again, using only the
f2deaca3450e rustdoc: fixed or introduced crossrefs in nodemap.rs Georges Racinet <georges.racinet@octobus.net> parents: 50412 diff changeset	391 /// data of the [`NodeTree`]).
44388 5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	392 fn lookup(
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	393 &self,
46431 645ee7225fab rust: Make NodePrefix allocation-free and Copy, remove NodePrefixRef Simon Sapin <simon.sapin@octobus.net> parents: 46428 diff changeset	394 prefix: NodePrefix,
44388 5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	395 ) -> Result<(Option<Revision>, usize), NodeMapError> {
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	396 for (i, visit_item) in self.visit(prefix).enumerate() {
44186 796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	397 if let Some(opt) = visit_item.final_revision() {
44388 5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	398 return Ok((opt, i + 1));
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	399 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	400 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	401 Err(NodeMapError::MultipleResults)
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	402 }
44186 796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	403
49095 b97835b2e2d4 rust-nodemap: remove unnecessary explicit lifetime Martin von Zweigbergk <martinvonz@google.com> parents: 46432 diff changeset	404 fn visit(&self, prefix: NodePrefix) -> NodeTreeVisitor {
44186 796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	405 NodeTreeVisitor {
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	406 nt: self,
44973 26114bd6ec60 rust: do a clippy pass Rapha?l Gom?s <rgomes@octobus.net> parents: 44390 diff changeset	407 prefix,
44186 796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	408 visit: self.len() - 1,
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	409 nybble_idx: 0,
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	410 done: false,
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	411 }
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	412 }
44356 d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	413 /// Return a mutable reference for `Block` at index `idx`.
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	414 ///
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	415 /// If `idx` lies in the immutable area, then the reference is to
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	416 /// a newly appended copy.
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	417 ///
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	418 /// Returns (new_idx, glen, mut_ref) where
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	419 ///
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	420 /// - `new_idx` is the index of the mutable `Block`
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	421 /// - `mut_ref` is a mutable reference to the mutable Block.
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	422 /// - `glen` is the new length of `self.growable`
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	423 ///
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	424 /// Note: the caller wouldn't be allowed to query `self.growable.len()`
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	425 /// itself because of the mutable borrow taken with the returned `Block`
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	426 fn mutable_block(&mut self, idx: usize) -> (usize, &mut Block, usize) {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	427 let ro_blocks = &self.readonly;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	428 let ro_len = ro_blocks.len();
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	429 let glen = self.growable.len();
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	430 if idx < ro_len {
44389 6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44388 diff changeset	431 self.masked_inner_blocks += 1;
44973 26114bd6ec60 rust: do a clippy pass Rapha?l Gom?s <rgomes@octobus.net> parents: 44390 diff changeset	432 self.growable.push(ro_blocks[idx]);
44356 d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	433 (glen + ro_len, &mut self.growable[glen], glen + 1)
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	434 } else if glen + ro_len == idx {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	435 (idx, &mut self.root, glen)
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	436 } else {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	437 (idx, &mut self.growable[idx - ro_len], glen)
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	438 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	439 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	440
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	441 /// Main insertion method
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	442 ///
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	443 /// This will dive in the node tree to find the deepest `Block` for
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	444 /// `node`, split it as much as needed and record `node` in there.
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	445 /// The method then backtracks, updating references in all the visited
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	446 /// blocks from the root.
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	447 ///
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	448 /// All the mutated `Block` are copied first to the growable part if
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	449 /// needed. That happens for those in the immutable part except the root.
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	450 pub fn insert<I: RevlogIndex>(
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	451 &mut self,
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	452 index: &I,
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	453 node: &Node,
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	454 rev: Revision,
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	455 ) -> Result<(), NodeMapError> {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	456 let ro_len = &self.readonly.len();
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	457
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	458 let mut visit_steps: Vec<_> = self.visit(node.into()).collect();
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	459 let read_nybbles = visit_steps.len();
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	460 // visit_steps cannot be empty, since we always visit the root block
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	461 let deepest = visit_steps.pop().unwrap();
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	462
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	463 let (mut block_idx, mut block, mut glen) =
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	464 self.mutable_block(deepest.block_idx);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	465
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	466 if let Element::Rev(old_rev) = deepest.element {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	467 let old_node = index
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	468 .node(old_rev)
49930 e98fd81bb151 rust-clippy: fix most warnings in `hg-core` Rapha?l Gom?s <rgomes@octobus.net> parents: 49095 diff changeset	469 .ok_or(NodeMapError::RevisionNotInIndex(old_rev))?;
44356 d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	470 if old_node == node {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	471 return Ok(()); // avoid creating lots of useless blocks
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	472 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	473
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	474 // Looping over the tail of nybbles in both nodes, creating
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	475 // new blocks until we find the difference
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	476 let mut new_block_idx = ro_len + glen;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	477 let mut nybble = deepest.nybble;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	478 for nybble_pos in read_nybbles..node.nybbles_len() {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	479 block.set(nybble, Element::Block(new_block_idx));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	480
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	481 let new_nybble = node.get_nybble(nybble_pos);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	482 let old_nybble = old_node.get_nybble(nybble_pos);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	483
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	484 if old_nybble == new_nybble {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	485 self.growable.push(Block::new());
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	486 block = &mut self.growable[glen];
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	487 glen += 1;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	488 new_block_idx += 1;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	489 nybble = new_nybble;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	490 } else {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	491 let mut new_block = Block::new();
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	492 new_block.set(old_nybble, Element::Rev(old_rev));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	493 new_block.set(new_nybble, Element::Rev(rev));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	494 self.growable.push(new_block);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	495 break;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	496 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	497 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	498 } else {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	499 // Free slot in the deepest block: no splitting has to be done
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	500 block.set(deepest.nybble, Element::Rev(rev));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	501 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	502
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	503 // Backtrack over visit steps to update references
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	504 while let Some(visited) = visit_steps.pop() {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	505 let to_write = Element::Block(block_idx);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	506 if visit_steps.is_empty() {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	507 self.root.set(visited.nybble, to_write);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	508 break;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	509 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	510 let (new_idx, block, _) = self.mutable_block(visited.block_idx);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	511 if block.get(visited.nybble) == to_write {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	512 break;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	513 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	514 block.set(visited.nybble, to_write);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	515 block_idx = new_idx;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	516 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	517 Ok(())
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	518 }
44389 6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44388 diff changeset	519
44390 d518994384a4 rust-nodemap: a method for full invalidation Georges Racinet <georges.racinet@octobus.net> parents: 44389 diff changeset	520 /// Make the whole `NodeTree` logically empty, without touching the
d518994384a4 rust-nodemap: a method for full invalidation Georges Racinet <georges.racinet@octobus.net> parents: 44389 diff changeset	521 /// immutable part.
d518994384a4 rust-nodemap: a method for full invalidation Georges Racinet <georges.racinet@octobus.net> parents: 44389 diff changeset	522 pub fn invalidate_all(&mut self) {
d518994384a4 rust-nodemap: a method for full invalidation Georges Racinet <georges.racinet@octobus.net> parents: 44389 diff changeset	523 self.root = Block::new();
d518994384a4 rust-nodemap: a method for full invalidation Georges Racinet <georges.racinet@octobus.net> parents: 44389 diff changeset	524 self.growable = Vec::new();
d518994384a4 rust-nodemap: a method for full invalidation Georges Racinet <georges.racinet@octobus.net> parents: 44389 diff changeset	525 self.masked_inner_blocks = self.readonly.len();
d518994384a4 rust-nodemap: a method for full invalidation Georges Racinet <georges.racinet@octobus.net> parents: 44389 diff changeset	526 }
d518994384a4 rust-nodemap: a method for full invalidation Georges Racinet <georges.racinet@octobus.net> parents: 44389 diff changeset	527
44389 6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44388 diff changeset	528 /// Return the number of blocks in the readonly part that are currently
6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44388 diff changeset	529 /// masked in the mutable part.
6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44388 diff changeset	530 ///
6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44388 diff changeset	531 /// The `NodeTree` structure has no efficient way to know how many blocks
6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44388 diff changeset	532 /// are already unreachable in the readonly part.
44390 d518994384a4 rust-nodemap: a method for full invalidation Georges Racinet <georges.racinet@octobus.net> parents: 44389 diff changeset	533 ///
d518994384a4 rust-nodemap: a method for full invalidation Georges Racinet <georges.racinet@octobus.net> parents: 44389 diff changeset	534 /// After a call to `invalidate_all()`, the returned number can be actually
d518994384a4 rust-nodemap: a method for full invalidation Georges Racinet <georges.racinet@octobus.net> parents: 44389 diff changeset	535 /// bigger than the whole readonly part, a conventional way to mean that
d518994384a4 rust-nodemap: a method for full invalidation Georges Racinet <georges.racinet@octobus.net> parents: 44389 diff changeset	536 /// all the readonly blocks have been masked. This is what is really
d518994384a4 rust-nodemap: a method for full invalidation Georges Racinet <georges.racinet@octobus.net> parents: 44389 diff changeset	537 /// useful to the caller and does not require to know how many were
d518994384a4 rust-nodemap: a method for full invalidation Georges Racinet <georges.racinet@octobus.net> parents: 44389 diff changeset	538 /// actually unreachable to begin with.
44389 6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44388 diff changeset	539 pub fn masked_readonly_blocks(&self) -> usize {
6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44388 diff changeset	540 if let Some(readonly_root) = self.readonly.last() {
6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44388 diff changeset	541 if readonly_root == &self.root {
6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44388 diff changeset	542 return 0;
6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44388 diff changeset	543 }
6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44388 diff changeset	544 } else {
6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44388 diff changeset	545 return 0;
6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44388 diff changeset	546 }
6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44388 diff changeset	547 self.masked_inner_blocks + 1
6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44388 diff changeset	548 }
44186 796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	549 }
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	550
44385 a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	551 pub struct NodeTreeBytes {
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	552 buffer: Box<dyn Deref<Target = [u8]> + Send>,
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	553 len_in_blocks: usize,
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	554 }
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	555
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	556 impl NodeTreeBytes {
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	557 fn new(
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	558 buffer: Box<dyn Deref<Target = [u8]> + Send>,
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	559 amount: usize,
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	560 ) -> Self {
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	561 assert!(buffer.len() >= amount);
46390 0800aa42bb4c rust: use the bytes-cast crate to parse persistent nodemaps Simon Sapin <simon.sapin@octobus.net> parents: 44973 diff changeset	562 let len_in_blocks = amount / size_of::<Block>();
44385 a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	563 NodeTreeBytes {
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	564 buffer,
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	565 len_in_blocks,
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	566 }
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	567 }
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	568 }
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	569
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	570 impl Deref for NodeTreeBytes {
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	571 type Target = [Block];
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	572
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	573 fn deref(&self) -> &[Block] {
46390 0800aa42bb4c rust: use the bytes-cast crate to parse persistent nodemaps Simon Sapin <simon.sapin@octobus.net> parents: 44973 diff changeset	574 Block::slice_from_bytes(&self.buffer, self.len_in_blocks)
0800aa42bb4c rust: use the bytes-cast crate to parse persistent nodemaps Simon Sapin <simon.sapin@octobus.net> parents: 44973 diff changeset	575 // `NodeTreeBytes::new` already asserted that `self.buffer` is
0800aa42bb4c rust: use the bytes-cast crate to parse persistent nodemaps Simon Sapin <simon.sapin@octobus.net> parents: 44973 diff changeset	576 // large enough.
0800aa42bb4c rust: use the bytes-cast crate to parse persistent nodemaps Simon Sapin <simon.sapin@octobus.net> parents: 44973 diff changeset	577 .unwrap()
0800aa42bb4c rust: use the bytes-cast crate to parse persistent nodemaps Simon Sapin <simon.sapin@octobus.net> parents: 44973 diff changeset	578 .0
44385 a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	579 }
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	580 }
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	581
46431 645ee7225fab rust: Make NodePrefix allocation-free and Copy, remove NodePrefixRef Simon Sapin <simon.sapin@octobus.net> parents: 46428 diff changeset	582 struct NodeTreeVisitor<'n> {
44186 796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	583 nt: &'n NodeTree,
46431 645ee7225fab rust: Make NodePrefix allocation-free and Copy, remove NodePrefixRef Simon Sapin <simon.sapin@octobus.net> parents: 46428 diff changeset	584 prefix: NodePrefix,
44186 796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	585 visit: usize,
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	586 nybble_idx: usize,
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	587 done: bool,
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	588 }
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	589
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	590 #[derive(Debug, PartialEq, Clone)]
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	591 struct NodeTreeVisitItem {
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	592 block_idx: usize,
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	593 nybble: u8,
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	594 element: Element,
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	595 }
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	596
46431 645ee7225fab rust: Make NodePrefix allocation-free and Copy, remove NodePrefixRef Simon Sapin <simon.sapin@octobus.net> parents: 46428 diff changeset	597 impl<'n> Iterator for NodeTreeVisitor<'n> {
44186 796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	598 type Item = NodeTreeVisitItem;
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	599
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	600 fn next(&mut self) -> Option<Self::Item> {
46431 645ee7225fab rust: Make NodePrefix allocation-free and Copy, remove NodePrefixRef Simon Sapin <simon.sapin@octobus.net> parents: 46428 diff changeset	601 if self.done \|\| self.nybble_idx >= self.prefix.nybbles_len() {
44186 796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	602 return None;
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	603 }
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	604
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	605 let nybble = self.prefix.get_nybble(self.nybble_idx);
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	606 self.nybble_idx += 1;
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	607
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	608 let visit = self.visit;
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	609 let element = self.nt[visit].get(nybble);
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	610 if let Element::Block(idx) = element {
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	611 self.visit = idx;
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	612 } else {
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	613 self.done = true;
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	614 }
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	615
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	616 Some(NodeTreeVisitItem {
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	617 block_idx: visit,
44973 26114bd6ec60 rust: do a clippy pass Rapha?l Gom?s <rgomes@octobus.net> parents: 44390 diff changeset	618 nybble,
26114bd6ec60 rust: do a clippy pass Rapha?l Gom?s <rgomes@octobus.net> parents: 44390 diff changeset	619 element,
44186 796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	620 })
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	621 }
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	622 }
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	623
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	624 impl NodeTreeVisitItem {
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	625 // Return `Some(opt)` if this item is final, with `opt` being the
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	626 // `Revision` that it may represent.
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	627 //
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	628 // If the item is not terminal, return `None`
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	629 fn final_revision(&self) -> Option<Option<Revision>> {
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	630 match self.element {
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	631 Element::Block(_) => None,
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	632 Element::Rev(r) => Some(Some(r)),
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	633 Element::None => Some(None),
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	634 }
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	635 }
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	636 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	637
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	638 impl From<Vec<Block>> for NodeTree {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	639 fn from(vec: Vec<Block>) -> Self {
44185 a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	640 Self::new(Box::new(vec))
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	641 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	642 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	643
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	644 impl fmt::Debug for NodeTree {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	645 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
44185 a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	646 let readonly: &[Block] = &*self.readonly;
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	647 write!(
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	648 f,
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	649 "readonly: {:?}, growable: {:?}, root: {:?}",
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	650 readonly, self.growable, self.root
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	651 )
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	652 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	653 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	654
44356 d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	655 impl Default for NodeTree {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	656 /// Create a fully mutable empty NodeTree
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	657 fn default() -> Self {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	658 NodeTree::new(Box::new(Vec::new()))
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	659 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	660 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	661
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	662 impl NodeMap for NodeTree {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	663 fn find_bin<'a>(
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	664 &self,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	665 idx: &impl RevlogIndex,
46431 645ee7225fab rust: Make NodePrefix allocation-free and Copy, remove NodePrefixRef Simon Sapin <simon.sapin@octobus.net> parents: 46428 diff changeset	666 prefix: NodePrefix,
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	667 ) -> Result<Option<Revision>, NodeMapError> {
46431 645ee7225fab rust: Make NodePrefix allocation-free and Copy, remove NodePrefixRef Simon Sapin <simon.sapin@octobus.net> parents: 46428 diff changeset	668 validate_candidate(idx, prefix, self.lookup(prefix)?)
44388 5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	669 .map(\|(opt, _shortest)\| opt)
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	670 }
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	671
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	672 fn unique_prefix_len_bin<'a>(
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	673 &self,
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	674 idx: &impl RevlogIndex,
46431 645ee7225fab rust: Make NodePrefix allocation-free and Copy, remove NodePrefixRef Simon Sapin <simon.sapin@octobus.net> parents: 46428 diff changeset	675 prefix: NodePrefix,
44388 5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	676 ) -> Result<Option<usize>, NodeMapError> {
46431 645ee7225fab rust: Make NodePrefix allocation-free and Copy, remove NodePrefixRef Simon Sapin <simon.sapin@octobus.net> parents: 46428 diff changeset	677 validate_candidate(idx, prefix, self.lookup(prefix)?)
44388 5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	678 .map(\|(opt, shortest)\| opt.map(\|_rev\| shortest))
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	679 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	680 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	681
44142 63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	682 #[cfg(test)]
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	683 mod tests {
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	684 use super::NodeMapError::*;
44142 63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	685 use super::*;
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	686 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	687 use std::collections::HashMap;
44142 63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	688
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	689 /// 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	690 macro_rules! block {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	691 {$($nybble:tt : $variant:ident($val:tt)),*} => (
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	692 {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	693 let mut block = Block::new();
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	694 $(block.set($nybble, Element::$variant($val)));*;
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	695 block
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	696 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	697 )
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	698 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	699
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	700 #[test]
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	701 fn test_block_debug() {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	702 let mut block = Block::new();
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	703 block.set(1, Element::Rev(3));
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	704 block.set(10, Element::Block(0));
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	705 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	706 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	707
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	708 #[test]
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	709 fn test_block_macro() {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	710 let block = block! {5: Block(2)};
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	711 assert_eq!(format!("{:?}", block), "{5: Block(2)}");
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	712
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	713 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	714 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	715 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	716
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	717 #[test]
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	718 fn test_raw_block() {
44385 a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	719 let mut raw = [255u8; 64];
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	720
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	721 let mut counter = 0;
46390 0800aa42bb4c rust: use the bytes-cast crate to parse persistent nodemaps Simon Sapin <simon.sapin@octobus.net> parents: 44973 diff changeset	722 for val in [0_i32, 15, -2, -1, -3].iter() {
0800aa42bb4c rust: use the bytes-cast crate to parse persistent nodemaps Simon Sapin <simon.sapin@octobus.net> parents: 44973 diff changeset	723 for byte in val.to_be_bytes().iter() {
44385 a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	724 raw[counter] = *byte;
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	725 counter += 1;
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	726 }
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	727 }
46390 0800aa42bb4c rust: use the bytes-cast crate to parse persistent nodemaps Simon Sapin <simon.sapin@octobus.net> parents: 44973 diff changeset	728 let (block, _) = Block::from_bytes(&raw).unwrap();
44142 63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	729 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	730 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	731 assert_eq!(block.get(3), Element::None);
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	732 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	733 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	734 }
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	735
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	736 type TestIndex = HashMap<Revision, Node>;
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	737
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	738 impl RevlogIndex for TestIndex {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	739 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	740 self.get(&rev)
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	741 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	742
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	743 fn len(&self) -> usize {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	744 self.len()
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	745 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	746 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	747
44356 d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	748 /// Pad hexadecimal Node prefix with zeros on the right
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	749 ///
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	750 /// 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	751 /// strings for test data, and brings actual hash size independency.
44356 d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	752 #[cfg(test)]
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	753 fn pad_node(hex: &str) -> Node {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	754 Node::from_hex(&hex_pad_right(hex)).unwrap()
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	755 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	756
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	757 /// Pad hexadecimal Node prefix with zeros on the right, then insert
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	758 fn pad_insert(idx: &mut TestIndex, rev: Revision, hex: &str) {
44356 d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	759 idx.insert(rev, pad_node(hex));
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	760 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	761
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	762 fn sample_nodetree() -> NodeTree {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	763 NodeTree::from(vec![
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	764 block![0: Rev(9)],
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	765 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	766 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	767 ])
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	768 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	769
46432 18a261b11b20 rust: Remove hex parsing from the nodemap Simon Sapin <simon.sapin@octobus.net> parents: 46431 diff changeset	770 fn hex(s: &str) -> NodePrefix {
18a261b11b20 rust: Remove hex parsing from the nodemap Simon Sapin <simon.sapin@octobus.net> parents: 46431 diff changeset	771 NodePrefix::from_hex(s).unwrap()
18a261b11b20 rust: Remove hex parsing from the nodemap Simon Sapin <simon.sapin@octobus.net> parents: 46431 diff changeset	772 }
18a261b11b20 rust: Remove hex parsing from the nodemap Simon Sapin <simon.sapin@octobus.net> parents: 46431 diff changeset	773
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	774 #[test]
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	775 fn test_nt_debug() {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	776 let nt = sample_nodetree();
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	777 assert_eq!(
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	778 format!("{:?}", nt),
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	779 "readonly: \
44185 a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	780 [{0: Rev(9)}, {0: Rev(0), 1: Rev(9)}, {0: Block(1), 1: Rev(1)}], \
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	781 growable: [], \
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	782 root: {0: Block(1), 1: Rev(1)}",
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	783 );
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	784 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	785
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	786 #[test]
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	787 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	788 let mut idx: TestIndex = HashMap::new();
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	789 pad_insert(&mut idx, 1, "1234deadcafe");
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	790
44185 a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	791 let nt = NodeTree::from(vec![block! {1: Rev(1)}]);
46432 18a261b11b20 rust: Remove hex parsing from the nodemap Simon Sapin <simon.sapin@octobus.net> parents: 46431 diff changeset	792 assert_eq!(nt.find_bin(&idx, hex("1"))?, Some(1));
18a261b11b20 rust: Remove hex parsing from the nodemap Simon Sapin <simon.sapin@octobus.net> parents: 46431 diff changeset	793 assert_eq!(nt.find_bin(&idx, hex("12"))?, Some(1));
18a261b11b20 rust: Remove hex parsing from the nodemap Simon Sapin <simon.sapin@octobus.net> parents: 46431 diff changeset	794 assert_eq!(nt.find_bin(&idx, hex("1234de"))?, Some(1));
18a261b11b20 rust: Remove hex parsing from the nodemap Simon Sapin <simon.sapin@octobus.net> parents: 46431 diff changeset	795 assert_eq!(nt.find_bin(&idx, hex("1a"))?, None);
18a261b11b20 rust: Remove hex parsing from the nodemap Simon Sapin <simon.sapin@octobus.net> parents: 46431 diff changeset	796 assert_eq!(nt.find_bin(&idx, hex("ab"))?, None);
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	797
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	798 // and with full binary Nodes
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	799 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	800 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	801 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	802 Ok(())
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	803 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	804
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	805 #[test]
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	806 fn test_immutable_find_one_jump() {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	807 let mut idx = TestIndex::new();
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	808 pad_insert(&mut idx, 9, "012");
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	809 pad_insert(&mut idx, 0, "00a");
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	810
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	811 let nt = sample_nodetree();
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	812
46432 18a261b11b20 rust: Remove hex parsing from the nodemap Simon Sapin <simon.sapin@octobus.net> parents: 46431 diff changeset	813 assert_eq!(nt.find_bin(&idx, hex("0")), Err(MultipleResults));
18a261b11b20 rust: Remove hex parsing from the nodemap Simon Sapin <simon.sapin@octobus.net> parents: 46431 diff changeset	814 assert_eq!(nt.find_bin(&idx, hex("01")), Ok(Some(9)));
18a261b11b20 rust: Remove hex parsing from the nodemap Simon Sapin <simon.sapin@octobus.net> parents: 46431 diff changeset	815 assert_eq!(nt.find_bin(&idx, hex("00")), Err(MultipleResults));
18a261b11b20 rust: Remove hex parsing from the nodemap Simon Sapin <simon.sapin@octobus.net> parents: 46431 diff changeset	816 assert_eq!(nt.find_bin(&idx, hex("00a")), Ok(Some(0)));
18a261b11b20 rust: Remove hex parsing from the nodemap Simon Sapin <simon.sapin@octobus.net> parents: 46431 diff changeset	817 assert_eq!(nt.unique_prefix_len_bin(&idx, hex("00a")), Ok(Some(3)));
18a261b11b20 rust: Remove hex parsing from the nodemap Simon Sapin <simon.sapin@octobus.net> parents: 46431 diff changeset	818 assert_eq!(nt.find_bin(&idx, hex("000")), Ok(Some(NULL_REVISION)));
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	819 }
44185 a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	820
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	821 #[test]
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	822 fn test_mutated_find() -> Result<(), NodeMapError> {
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	823 let mut idx = TestIndex::new();
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	824 pad_insert(&mut idx, 9, "012");
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	825 pad_insert(&mut idx, 0, "00a");
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	826 pad_insert(&mut idx, 2, "cafe");
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	827 pad_insert(&mut idx, 3, "15");
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	828 pad_insert(&mut idx, 1, "10");
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	829
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	830 let nt = NodeTree {
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	831 readonly: sample_nodetree().readonly,
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	832 growable: vec![block![0: Rev(1), 5: Rev(3)]],
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	833 root: block![0: Block(1), 1:Block(3), 12: Rev(2)],
44389 6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44388 diff changeset	834 masked_inner_blocks: 1,
44185 a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	835 };
46432 18a261b11b20 rust: Remove hex parsing from the nodemap Simon Sapin <simon.sapin@octobus.net> parents: 46431 diff changeset	836 assert_eq!(nt.find_bin(&idx, hex("10"))?, Some(1));
18a261b11b20 rust: Remove hex parsing from the nodemap Simon Sapin <simon.sapin@octobus.net> parents: 46431 diff changeset	837 assert_eq!(nt.find_bin(&idx, hex("c"))?, Some(2));
18a261b11b20 rust: Remove hex parsing from the nodemap Simon Sapin <simon.sapin@octobus.net> parents: 46431 diff changeset	838 assert_eq!(nt.unique_prefix_len_bin(&idx, hex("c"))?, Some(1));
18a261b11b20 rust: Remove hex parsing from the nodemap Simon Sapin <simon.sapin@octobus.net> parents: 46431 diff changeset	839 assert_eq!(nt.find_bin(&idx, hex("00")), Err(MultipleResults));
18a261b11b20 rust: Remove hex parsing from the nodemap Simon Sapin <simon.sapin@octobus.net> parents: 46431 diff changeset	840 assert_eq!(nt.find_bin(&idx, hex("000"))?, Some(NULL_REVISION));
18a261b11b20 rust: Remove hex parsing from the nodemap Simon Sapin <simon.sapin@octobus.net> parents: 46431 diff changeset	841 assert_eq!(nt.unique_prefix_len_bin(&idx, hex("000"))?, Some(3));
18a261b11b20 rust: Remove hex parsing from the nodemap Simon Sapin <simon.sapin@octobus.net> parents: 46431 diff changeset	842 assert_eq!(nt.find_bin(&idx, hex("01"))?, Some(9));
44389 6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44388 diff changeset	843 assert_eq!(nt.masked_readonly_blocks(), 2);
44185 a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	844 Ok(())
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	845 }
44356 d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	846
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	847 struct TestNtIndex {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	848 index: TestIndex,
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	849 nt: NodeTree,
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	850 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	851
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	852 impl TestNtIndex {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	853 fn new() -> Self {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	854 TestNtIndex {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	855 index: HashMap::new(),
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	856 nt: NodeTree::default(),
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	857 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	858 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	859
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	860 fn insert(
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	861 &mut self,
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	862 rev: Revision,
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	863 hex: &str,
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	864 ) -> Result<(), NodeMapError> {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	865 let node = pad_node(hex);
49930 e98fd81bb151 rust-clippy: fix most warnings in `hg-core` Rapha?l Gom?s <rgomes@octobus.net> parents: 49095 diff changeset	866 self.index.insert(rev, node);
44356 d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	867 self.nt.insert(&self.index, &node, rev)?;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	868 Ok(())
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	869 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	870
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	871 fn find_hex(
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	872 &self,
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	873 prefix: &str,
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	874 ) -> Result<Option<Revision>, NodeMapError> {
46432 18a261b11b20 rust: Remove hex parsing from the nodemap Simon Sapin <simon.sapin@octobus.net> parents: 46431 diff changeset	875 self.nt.find_bin(&self.index, hex(prefix))
44356 d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	876 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	877
44388 5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	878 fn unique_prefix_len_hex(
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	879 &self,
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	880 prefix: &str,
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	881 ) -> Result<Option<usize>, NodeMapError> {
46432 18a261b11b20 rust: Remove hex parsing from the nodemap Simon Sapin <simon.sapin@octobus.net> parents: 46431 diff changeset	882 self.nt.unique_prefix_len_bin(&self.index, hex(prefix))
44388 5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	883 }
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	884
44356 d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	885 /// Drain `added` and restart a new one
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	886 fn commit(self) -> Self {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	887 let mut as_vec: Vec<Block> =
49930 e98fd81bb151 rust-clippy: fix most warnings in `hg-core` Rapha?l Gom?s <rgomes@octobus.net> parents: 49095 diff changeset	888 self.nt.readonly.iter().copied().collect();
44356 d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	889 as_vec.extend(self.nt.growable);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	890 as_vec.push(self.nt.root);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	891
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	892 Self {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	893 index: self.index,
49930 e98fd81bb151 rust-clippy: fix most warnings in `hg-core` Rapha?l Gom?s <rgomes@octobus.net> parents: 49095 diff changeset	894 nt: NodeTree::from(as_vec),
44356 d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	895 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	896 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	897 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	898
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	899 #[test]
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	900 fn test_insert_full_mutable() -> Result<(), NodeMapError> {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	901 let mut idx = TestNtIndex::new();
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	902 idx.insert(0, "1234")?;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	903 assert_eq!(idx.find_hex("1")?, Some(0));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	904 assert_eq!(idx.find_hex("12")?, Some(0));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	905
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	906 // let's trigger a simple split
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	907 idx.insert(1, "1a34")?;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	908 assert_eq!(idx.nt.growable.len(), 1);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	909 assert_eq!(idx.find_hex("12")?, Some(0));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	910 assert_eq!(idx.find_hex("1a")?, Some(1));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	911
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	912 // reinserting is a no_op
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	913 idx.insert(1, "1a34")?;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	914 assert_eq!(idx.nt.growable.len(), 1);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	915 assert_eq!(idx.find_hex("12")?, Some(0));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	916 assert_eq!(idx.find_hex("1a")?, Some(1));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	917
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	918 idx.insert(2, "1a01")?;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	919 assert_eq!(idx.nt.growable.len(), 2);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	920 assert_eq!(idx.find_hex("1a"), Err(NodeMapError::MultipleResults));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	921 assert_eq!(idx.find_hex("12")?, Some(0));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	922 assert_eq!(idx.find_hex("1a3")?, Some(1));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	923 assert_eq!(idx.find_hex("1a0")?, Some(2));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	924 assert_eq!(idx.find_hex("1a12")?, None);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	925
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	926 // now let's make it split and create more than one additional block
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	927 idx.insert(3, "1a345")?;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	928 assert_eq!(idx.nt.growable.len(), 4);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	929 assert_eq!(idx.find_hex("1a340")?, Some(1));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	930 assert_eq!(idx.find_hex("1a345")?, Some(3));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	931 assert_eq!(idx.find_hex("1a341")?, None);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	932
44389 6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44388 diff changeset	933 // there's no readonly block to mask
6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44388 diff changeset	934 assert_eq!(idx.nt.masked_readonly_blocks(), 0);
44356 d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	935 Ok(())
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	936 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	937
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	938 #[test]
44388 5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	939 fn test_unique_prefix_len_zero_prefix() {
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	940 let mut idx = TestNtIndex::new();
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	941 idx.insert(0, "00000abcd").unwrap();
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	942
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	943 assert_eq!(idx.find_hex("000"), Err(NodeMapError::MultipleResults));
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	944 // in the nodetree proper, this will be found at the first nybble
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	945 // yet the correct answer for unique_prefix_len is not 1, nor 1+1,
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	946 // but the first difference with `NULL_NODE`
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	947 assert_eq!(idx.unique_prefix_len_hex("00000a"), Ok(Some(6)));
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	948 assert_eq!(idx.unique_prefix_len_hex("00000ab"), Ok(Some(6)));
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	949
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	950 // same with odd result
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	951 idx.insert(1, "00123").unwrap();
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	952 assert_eq!(idx.unique_prefix_len_hex("001"), Ok(Some(3)));
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	953 assert_eq!(idx.unique_prefix_len_hex("0012"), Ok(Some(3)));
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	954
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	955 // these are unchanged of course
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	956 assert_eq!(idx.unique_prefix_len_hex("00000a"), Ok(Some(6)));
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	957 assert_eq!(idx.unique_prefix_len_hex("00000ab"), Ok(Some(6)));
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	958 }
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	959
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44387 diff changeset	960 #[test]
44356 d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	961 fn test_insert_extreme_splitting() -> Result<(), NodeMapError> {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	962 // check that the splitting loop is long enough
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	963 let mut nt_idx = TestNtIndex::new();
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	964 let nt = &mut nt_idx.nt;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	965 let idx = &mut nt_idx.index;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	966
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	967 let node0_hex = hex_pad_right("444444");
49930 e98fd81bb151 rust-clippy: fix most warnings in `hg-core` Rapha?l Gom?s <rgomes@octobus.net> parents: 49095 diff changeset	968 let mut node1_hex = hex_pad_right("444444");
44356 d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	969 node1_hex.pop();
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	970 node1_hex.push('5');
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	971 let node0 = Node::from_hex(&node0_hex).unwrap();
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	972 let node1 = Node::from_hex(&node1_hex).unwrap();
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	973
49930 e98fd81bb151 rust-clippy: fix most warnings in `hg-core` Rapha?l Gom?s <rgomes@octobus.net> parents: 49095 diff changeset	974 idx.insert(0, node0);
44356 d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	975 nt.insert(idx, &node0, 0)?;
49930 e98fd81bb151 rust-clippy: fix most warnings in `hg-core` Rapha?l Gom?s <rgomes@octobus.net> parents: 49095 diff changeset	976 idx.insert(1, node1);
44356 d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	977 nt.insert(idx, &node1, 1)?;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	978
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	979 assert_eq!(nt.find_bin(idx, (&node0).into())?, Some(0));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	980 assert_eq!(nt.find_bin(idx, (&node1).into())?, Some(1));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	981 Ok(())
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	982 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	983
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	984 #[test]
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	985 fn test_insert_partly_immutable() -> Result<(), NodeMapError> {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	986 let mut idx = TestNtIndex::new();
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	987 idx.insert(0, "1234")?;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	988 idx.insert(1, "1235")?;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	989 idx.insert(2, "131")?;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	990 idx.insert(3, "cafe")?;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	991 let mut idx = idx.commit();
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	992 assert_eq!(idx.find_hex("1234")?, Some(0));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	993 assert_eq!(idx.find_hex("1235")?, Some(1));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	994 assert_eq!(idx.find_hex("131")?, Some(2));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	995 assert_eq!(idx.find_hex("cafe")?, Some(3));
44389 6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44388 diff changeset	996 // we did not add anything since init from readonly
6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44388 diff changeset	997 assert_eq!(idx.nt.masked_readonly_blocks(), 0);
44356 d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	998
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	999 idx.insert(4, "123A")?;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	1000 assert_eq!(idx.find_hex("1234")?, Some(0));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	1001 assert_eq!(idx.find_hex("1235")?, Some(1));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	1002 assert_eq!(idx.find_hex("131")?, Some(2));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	1003 assert_eq!(idx.find_hex("cafe")?, Some(3));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	1004 assert_eq!(idx.find_hex("123A")?, Some(4));
44389 6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44388 diff changeset	1005 // we masked blocks for all prefixes of "123", including the root
6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44388 diff changeset	1006 assert_eq!(idx.nt.masked_readonly_blocks(), 4);
44356 d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	1007
44389 6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44388 diff changeset	1008 eprintln!("{:?}", idx.nt);
44356 d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	1009 idx.insert(5, "c0")?;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	1010 assert_eq!(idx.find_hex("cafe")?, Some(3));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	1011 assert_eq!(idx.find_hex("c0")?, Some(5));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	1012 assert_eq!(idx.find_hex("c1")?, None);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	1013 assert_eq!(idx.find_hex("1234")?, Some(0));
44389 6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44388 diff changeset	1014 // inserting "c0" is just splitting the 'c' slot of the mutable root,
6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44388 diff changeset	1015 // it doesn't mask anything
6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44388 diff changeset	1016 assert_eq!(idx.nt.masked_readonly_blocks(), 4);
44356 d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	1017
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	1018 Ok(())
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	1019 }
44385 a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	1020
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	1021 #[test]
44390 d518994384a4 rust-nodemap: a method for full invalidation Georges Racinet <georges.racinet@octobus.net> parents: 44389 diff changeset	1022 fn test_invalidate_all() -> Result<(), NodeMapError> {
d518994384a4 rust-nodemap: a method for full invalidation Georges Racinet <georges.racinet@octobus.net> parents: 44389 diff changeset	1023 let mut idx = TestNtIndex::new();
d518994384a4 rust-nodemap: a method for full invalidation Georges Racinet <georges.racinet@octobus.net> parents: 44389 diff changeset	1024 idx.insert(0, "1234")?;
d518994384a4 rust-nodemap: a method for full invalidation Georges Racinet <georges.racinet@octobus.net> parents: 44389 diff changeset	1025 idx.insert(1, "1235")?;
d518994384a4 rust-nodemap: a method for full invalidation Georges Racinet <georges.racinet@octobus.net> parents: 44389 diff changeset	1026 idx.insert(2, "131")?;
d518994384a4 rust-nodemap: a method for full invalidation Georges Racinet <georges.racinet@octobus.net> parents: 44389 diff changeset	1027 idx.insert(3, "cafe")?;
d518994384a4 rust-nodemap: a method for full invalidation Georges Racinet <georges.racinet@octobus.net> parents: 44389 diff changeset	1028 let mut idx = idx.commit();
d518994384a4 rust-nodemap: a method for full invalidation Georges Racinet <georges.racinet@octobus.net> parents: 44389 diff changeset	1029
d518994384a4 rust-nodemap: a method for full invalidation Georges Racinet <georges.racinet@octobus.net> parents: 44389 diff changeset	1030 idx.nt.invalidate_all();
d518994384a4 rust-nodemap: a method for full invalidation Georges Racinet <georges.racinet@octobus.net> parents: 44389 diff changeset	1031
d518994384a4 rust-nodemap: a method for full invalidation Georges Racinet <georges.racinet@octobus.net> parents: 44389 diff changeset	1032 assert_eq!(idx.find_hex("1234")?, None);
d518994384a4 rust-nodemap: a method for full invalidation Georges Racinet <georges.racinet@octobus.net> parents: 44389 diff changeset	1033 assert_eq!(idx.find_hex("1235")?, None);
d518994384a4 rust-nodemap: a method for full invalidation Georges Racinet <georges.racinet@octobus.net> parents: 44389 diff changeset	1034 assert_eq!(idx.find_hex("131")?, None);
d518994384a4 rust-nodemap: a method for full invalidation Georges Racinet <georges.racinet@octobus.net> parents: 44389 diff changeset	1035 assert_eq!(idx.find_hex("cafe")?, None);
d518994384a4 rust-nodemap: a method for full invalidation Georges Racinet <georges.racinet@octobus.net> parents: 44389 diff changeset	1036 // all the readonly blocks have been masked, this is the
d518994384a4 rust-nodemap: a method for full invalidation Georges Racinet <georges.racinet@octobus.net> parents: 44389 diff changeset	1037 // conventional expected response
d518994384a4 rust-nodemap: a method for full invalidation Georges Racinet <georges.racinet@octobus.net> parents: 44389 diff changeset	1038 assert_eq!(idx.nt.masked_readonly_blocks(), idx.nt.readonly.len() + 1);
d518994384a4 rust-nodemap: a method for full invalidation Georges Racinet <georges.racinet@octobus.net> parents: 44389 diff changeset	1039 Ok(())
d518994384a4 rust-nodemap: a method for full invalidation Georges Racinet <georges.racinet@octobus.net> parents: 44389 diff changeset	1040 }
d518994384a4 rust-nodemap: a method for full invalidation Georges Racinet <georges.racinet@octobus.net> parents: 44389 diff changeset	1041
d518994384a4 rust-nodemap: a method for full invalidation Georges Racinet <georges.racinet@octobus.net> parents: 44389 diff changeset	1042 #[test]
44385 a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	1043 fn test_into_added_empty() {
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	1044 assert!(sample_nodetree().into_readonly_and_added().1.is_empty());
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	1045 assert!(sample_nodetree()
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	1046 .into_readonly_and_added_bytes()
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	1047 .1
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	1048 .is_empty());
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	1049 }
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	1050
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	1051 #[test]
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	1052 fn test_into_added_bytes() -> Result<(), NodeMapError> {
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	1053 let mut idx = TestNtIndex::new();
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	1054 idx.insert(0, "1234")?;
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	1055 let mut idx = idx.commit();
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	1056 idx.insert(4, "cafe")?;
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	1057 let (_, bytes) = idx.nt.into_readonly_and_added_bytes();
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	1058
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	1059 // only the root block has been changed
46390 0800aa42bb4c rust: use the bytes-cast crate to parse persistent nodemaps Simon Sapin <simon.sapin@octobus.net> parents: 44973 diff changeset	1060 assert_eq!(bytes.len(), size_of::<Block>());
44385 a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	1061 // big endian for -2
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	1062 assert_eq!(&bytes[4..2 * 4], [255, 255, 255, 254]);
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	1063 // big endian for -6
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	1064 assert_eq!(&bytes[12 * 4..13 * 4], [255, 255, 255, 250]);
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	1065 Ok(())
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	1066 }
44142 63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	1067 }

Mercurial > public > mercurial-scm > hg

annotate rust/hg-core/src/revlog/nodemap.rs @ 50818:28c0fcff24e5 stable