Show More
@@ -253,7 +253,7 b' mod tests {' | |||
|
253 | 253 | /// Pad an hexadecimal string to reach `NODE_NYBBLES_LENGTH` |
|
254 | 254 | /// |
|
255 | 255 | /// The padding is made with zeros |
|
256 | fn hex_pad_right(hex: &str) -> String { | |
|
256 | pub fn hex_pad_right(hex: &str) -> String { | |
|
257 | 257 | let mut res = hex.to_string(); |
|
258 | 258 | while res.len() < NODE_NYBBLES_LENGTH { |
|
259 | 259 | res.push('0'); |
@@ -362,3 +362,6 b' mod tests {' | |||
|
362 | 362 | Ok(()) |
|
363 | 363 | } |
|
364 | 364 | } |
|
365 | ||
|
366 | #[cfg(test)] | |
|
367 | pub use tests::hex_pad_right; |
@@ -12,8 +12,88 b'' | |||
|
12 | 12 | //! Following existing implicit conventions, the "nodemap" terminology |
|
13 | 13 | //! is used in a more abstract context. |
|
14 | 14 | |
|
15 |
use super:: |
|
|
15 | use super::{ | |
|
16 | Node, NodeError, NodePrefix, NodePrefixRef, Revision, RevlogIndex, | |
|
17 | }; | |
|
16 | 18 | use std::fmt; |
|
19 | use std::ops::Deref; | |
|
20 | ||
|
21 | #[derive(Debug, PartialEq)] | |
|
22 | pub enum NodeMapError { | |
|
23 | MultipleResults, | |
|
24 | InvalidNodePrefix(NodeError), | |
|
25 | /// A `Revision` stored in the nodemap could not be found in the index | |
|
26 | RevisionNotInIndex(Revision), | |
|
27 | } | |
|
28 | ||
|
29 | impl From<NodeError> for NodeMapError { | |
|
30 | fn from(err: NodeError) -> Self { | |
|
31 | NodeMapError::InvalidNodePrefix(err) | |
|
32 | } | |
|
33 | } | |
|
34 | ||
|
35 | /// Mapping system from Mercurial nodes to revision numbers. | |
|
36 | /// | |
|
37 | /// ## `RevlogIndex` and `NodeMap` | |
|
38 | /// | |
|
39 | /// One way to think about their relationship is that | |
|
40 | /// the `NodeMap` is a prefix-oriented reverse index of the `Node` information | |
|
41 | /// carried by a [`RevlogIndex`]. | |
|
42 | /// | |
|
43 | /// Many of the methods in this trait take a `RevlogIndex` argument | |
|
44 | /// which is used for validation of their results. This index must naturally | |
|
45 | /// be the one the `NodeMap` is about, and it must be consistent. | |
|
46 | /// | |
|
47 | /// Notably, the `NodeMap` must not store | |
|
48 | /// information about more `Revision` values than there are in the index. | |
|
49 | /// In these methods, an encountered `Revision` is not in the index, a | |
|
50 | /// [`RevisionNotInIndex`] error is returned. | |
|
51 | /// | |
|
52 | /// In insert operations, the rule is thus that the `NodeMap` must always | |
|
53 | /// be updated after the `RevlogIndex` | |
|
54 | /// be updated first, and the `NodeMap` second. | |
|
55 | /// | |
|
56 | /// [`RevisionNotInIndex`]: enum.NodeMapError.html#variant.RevisionNotInIndex | |
|
57 | /// [`RevlogIndex`]: ../trait.RevlogIndex.html | |
|
58 | pub trait NodeMap { | |
|
59 | /// Find the unique `Revision` having the given `Node` | |
|
60 | /// | |
|
61 | /// If no Revision matches the given `Node`, `Ok(None)` is returned. | |
|
62 | fn find_node( | |
|
63 | &self, | |
|
64 | index: &impl RevlogIndex, | |
|
65 | node: &Node, | |
|
66 | ) -> Result<Option<Revision>, NodeMapError> { | |
|
67 | self.find_bin(index, node.into()) | |
|
68 | } | |
|
69 | ||
|
70 | /// Find the unique Revision whose `Node` starts with a given binary prefix | |
|
71 | /// | |
|
72 | /// If no Revision matches the given prefix, `Ok(None)` is returned. | |
|
73 | /// | |
|
74 | /// If several Revisions match the given prefix, a [`MultipleResults`] | |
|
75 | /// error is returned. | |
|
76 | fn find_bin<'a>( | |
|
77 | &self, | |
|
78 | idx: &impl RevlogIndex, | |
|
79 | prefix: NodePrefixRef<'a>, | |
|
80 | ) -> Result<Option<Revision>, NodeMapError>; | |
|
81 | ||
|
82 | /// Find the unique Revision whose `Node` hexadecimal string representation | |
|
83 | /// starts with a given prefix | |
|
84 | /// | |
|
85 | /// If no Revision matches the given prefix, `Ok(None)` is returned. | |
|
86 | /// | |
|
87 | /// If several Revisions match the given prefix, a [`MultipleResults`] | |
|
88 | /// error is returned. | |
|
89 | fn find_hex( | |
|
90 | &self, | |
|
91 | idx: &impl RevlogIndex, | |
|
92 | prefix: &str, | |
|
93 | ) -> Result<Option<Revision>, NodeMapError> { | |
|
94 | self.find_bin(idx, NodePrefix::from_hex(prefix)?.borrow()) | |
|
95 | } | |
|
96 | } | |
|
17 | 97 | |
|
18 | 98 | /// Low level NodeTree [`Blocks`] elements |
|
19 | 99 | /// |
@@ -110,9 +190,86 b' impl fmt::Debug for Block {' | |||
|
110 | 190 | } |
|
111 | 191 | } |
|
112 | 192 | |
|
193 | /// A 16-radix tree with the root block at the end | |
|
194 | pub struct NodeTree { | |
|
195 | readonly: Box<dyn Deref<Target = [Block]> + Send>, | |
|
196 | } | |
|
197 | ||
|
198 | /// Return `None` unless the `Node` for `rev` has given prefix in `index`. | |
|
199 | fn has_prefix_or_none<'p>( | |
|
200 | idx: &impl RevlogIndex, | |
|
201 | prefix: NodePrefixRef<'p>, | |
|
202 | rev: Revision, | |
|
203 | ) -> Result<Option<Revision>, NodeMapError> { | |
|
204 | idx.node(rev) | |
|
205 | .ok_or_else(|| NodeMapError::RevisionNotInIndex(rev)) | |
|
206 | .map(|node| { | |
|
207 | if prefix.is_prefix_of(node) { | |
|
208 | Some(rev) | |
|
209 | } else { | |
|
210 | None | |
|
211 | } | |
|
212 | }) | |
|
213 | } | |
|
214 | ||
|
215 | impl NodeTree { | |
|
216 | /// Main working method for `NodeTree` searches | |
|
217 | /// | |
|
218 | /// This partial implementation lacks special cases for NULL_REVISION | |
|
219 | fn lookup<'p>( | |
|
220 | &self, | |
|
221 | prefix: NodePrefixRef<'p>, | |
|
222 | ) -> Result<Option<Revision>, NodeMapError> { | |
|
223 | let blocks: &[Block] = &*self.readonly; | |
|
224 | if blocks.is_empty() { | |
|
225 | return Ok(None); | |
|
226 | } | |
|
227 | let mut visit = blocks.len() - 1; | |
|
228 | for i in 0..prefix.len() { | |
|
229 | let nybble = prefix.get_nybble(i); | |
|
230 | match blocks[visit].get(nybble) { | |
|
231 | Element::None => return Ok(None), | |
|
232 | Element::Rev(r) => return Ok(Some(r)), | |
|
233 | Element::Block(idx) => visit = idx, | |
|
234 | } | |
|
235 | } | |
|
236 | Err(NodeMapError::MultipleResults) | |
|
237 | } | |
|
238 | } | |
|
239 | ||
|
240 | impl From<Vec<Block>> for NodeTree { | |
|
241 | fn from(vec: Vec<Block>) -> Self { | |
|
242 | NodeTree { | |
|
243 | readonly: Box::new(vec), | |
|
244 | } | |
|
245 | } | |
|
246 | } | |
|
247 | ||
|
248 | impl fmt::Debug for NodeTree { | |
|
249 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
|
250 | let blocks: &[Block] = &*self.readonly; | |
|
251 | write!(f, "readonly: {:?}", blocks) | |
|
252 | } | |
|
253 | } | |
|
254 | ||
|
255 | impl NodeMap for NodeTree { | |
|
256 | fn find_bin<'a>( | |
|
257 | &self, | |
|
258 | idx: &impl RevlogIndex, | |
|
259 | prefix: NodePrefixRef<'a>, | |
|
260 | ) -> Result<Option<Revision>, NodeMapError> { | |
|
261 | self.lookup(prefix.clone()).and_then(|opt| { | |
|
262 | opt.map_or(Ok(None), |rev| has_prefix_or_none(idx, prefix, rev)) | |
|
263 | }) | |
|
264 | } | |
|
265 | } | |
|
266 | ||
|
113 | 267 | #[cfg(test)] |
|
114 | 268 | mod tests { |
|
269 | use super::NodeMapError::*; | |
|
115 | 270 | use super::*; |
|
271 | use crate::revlog::node::{hex_pad_right, Node}; | |
|
272 | use std::collections::HashMap; | |
|
116 | 273 | |
|
117 | 274 | /// Creates a `Block` using a syntax close to the `Debug` output |
|
118 | 275 | macro_rules! block { |
@@ -157,4 +314,75 b' mod tests {' | |||
|
157 | 314 | assert_eq!(block.get(2), Element::Rev(0)); |
|
158 | 315 | assert_eq!(block.get(4), Element::Rev(1)); |
|
159 | 316 | } |
|
317 | ||
|
318 | type TestIndex = HashMap<Revision, Node>; | |
|
319 | ||
|
320 | impl RevlogIndex for TestIndex { | |
|
321 | fn node(&self, rev: Revision) -> Option<&Node> { | |
|
322 | self.get(&rev) | |
|
160 | 323 | } |
|
324 | ||
|
325 | fn len(&self) -> usize { | |
|
326 | self.len() | |
|
327 | } | |
|
328 | } | |
|
329 | ||
|
330 | /// Pad hexadecimal Node prefix with zeros on the right, then insert | |
|
331 | /// | |
|
332 | /// This avoids having to repeatedly write very long hexadecimal | |
|
333 | /// strings for test data, and brings actual hash size independency. | |
|
334 | fn pad_insert(idx: &mut TestIndex, rev: Revision, hex: &str) { | |
|
335 | idx.insert(rev, Node::from_hex(&hex_pad_right(hex)).unwrap()); | |
|
336 | } | |
|
337 | ||
|
338 | fn sample_nodetree() -> NodeTree { | |
|
339 | NodeTree::from(vec![ | |
|
340 | block![0: Rev(9)], | |
|
341 | block![0: Rev(0), 1: Rev(9)], | |
|
342 | block![0: Block(1), 1:Rev(1)], | |
|
343 | ]) | |
|
344 | } | |
|
345 | ||
|
346 | #[test] | |
|
347 | fn test_nt_debug() { | |
|
348 | let nt = sample_nodetree(); | |
|
349 | assert_eq!( | |
|
350 | format!("{:?}", nt), | |
|
351 | "readonly: \ | |
|
352 | [{0: Rev(9)}, {0: Rev(0), 1: Rev(9)}, {0: Block(1), 1: Rev(1)}]" | |
|
353 | ); | |
|
354 | } | |
|
355 | ||
|
356 | #[test] | |
|
357 | fn test_immutable_find_simplest() -> Result<(), NodeMapError> { | |
|
358 | let mut idx: TestIndex = HashMap::new(); | |
|
359 | pad_insert(&mut idx, 1, "1234deadcafe"); | |
|
360 | ||
|
361 | let nt = NodeTree::from(vec![block![1: Rev(1)]]); | |
|
362 | assert_eq!(nt.find_hex(&idx, "1")?, Some(1)); | |
|
363 | assert_eq!(nt.find_hex(&idx, "12")?, Some(1)); | |
|
364 | assert_eq!(nt.find_hex(&idx, "1234de")?, Some(1)); | |
|
365 | assert_eq!(nt.find_hex(&idx, "1a")?, None); | |
|
366 | assert_eq!(nt.find_hex(&idx, "ab")?, None); | |
|
367 | ||
|
368 | // and with full binary Nodes | |
|
369 | assert_eq!(nt.find_node(&idx, idx.get(&1).unwrap())?, Some(1)); | |
|
370 | let unknown = Node::from_hex(&hex_pad_right("3d")).unwrap(); | |
|
371 | assert_eq!(nt.find_node(&idx, &unknown)?, None); | |
|
372 | Ok(()) | |
|
373 | } | |
|
374 | ||
|
375 | #[test] | |
|
376 | fn test_immutable_find_one_jump() { | |
|
377 | let mut idx = TestIndex::new(); | |
|
378 | pad_insert(&mut idx, 9, "012"); | |
|
379 | pad_insert(&mut idx, 0, "00a"); | |
|
380 | ||
|
381 | let nt = sample_nodetree(); | |
|
382 | ||
|
383 | assert_eq!(nt.find_hex(&idx, "0"), Err(MultipleResults)); | |
|
384 | assert_eq!(nt.find_hex(&idx, "01"), Ok(Some(9))); | |
|
385 | assert_eq!(nt.find_hex(&idx, "00"), Ok(Some(0))); | |
|
386 | assert_eq!(nt.find_hex(&idx, "00a"), Ok(Some(0))); | |
|
387 | } | |
|
388 | } |
General Comments 0
You need to be logged in to leave comments.
Login now