Show More
@@ -1,68 +1,68 b'' | |||||
1 | // Copyright 2018-2020 Georges Racinet <georges.racinet@octobus.net> |
|
1 | // Copyright 2018-2020 Georges Racinet <georges.racinet@octobus.net> | |
2 | // and Mercurial contributors |
|
2 | // and Mercurial contributors | |
3 | // |
|
3 | // | |
4 | // This software may be used and distributed according to the terms of the |
|
4 | // This software may be used and distributed according to the terms of the | |
5 | // GNU General Public License version 2 or any later version. |
|
5 | // GNU General Public License version 2 or any later version. | |
6 | //! Mercurial concepts for handling revision history |
|
6 | //! Mercurial concepts for handling revision history | |
7 |
|
7 | |||
8 | pub mod node; |
|
8 | pub mod node; | |
9 | pub mod nodemap; |
|
9 | pub mod nodemap; | |
10 | mod nodemap_docket; |
|
10 | mod nodemap_docket; | |
11 | pub mod path_encode; |
|
11 | pub mod path_encode; | |
12 |
pub use node::{ |
|
12 | pub use node::{FromHexError, Node, NodePrefix, NodePrefixRef}; | |
13 | pub mod changelog; |
|
13 | pub mod changelog; | |
14 | pub mod index; |
|
14 | pub mod index; | |
15 | pub mod manifest; |
|
15 | pub mod manifest; | |
16 | pub mod patch; |
|
16 | pub mod patch; | |
17 | pub mod revlog; |
|
17 | pub mod revlog; | |
18 |
|
18 | |||
19 | /// Mercurial revision numbers |
|
19 | /// Mercurial revision numbers | |
20 | /// |
|
20 | /// | |
21 | /// As noted in revlog.c, revision numbers are actually encoded in |
|
21 | /// As noted in revlog.c, revision numbers are actually encoded in | |
22 | /// 4 bytes, and are liberally converted to ints, whence the i32 |
|
22 | /// 4 bytes, and are liberally converted to ints, whence the i32 | |
23 | pub type Revision = i32; |
|
23 | pub type Revision = i32; | |
24 |
|
24 | |||
25 | /// Marker expressing the absence of a parent |
|
25 | /// Marker expressing the absence of a parent | |
26 | /// |
|
26 | /// | |
27 | /// Independently of the actual representation, `NULL_REVISION` is guaranteed |
|
27 | /// Independently of the actual representation, `NULL_REVISION` is guaranteed | |
28 | /// to be smaller than all existing revisions. |
|
28 | /// to be smaller than all existing revisions. | |
29 | pub const NULL_REVISION: Revision = -1; |
|
29 | pub const NULL_REVISION: Revision = -1; | |
30 |
|
30 | |||
31 | /// Same as `mercurial.node.wdirrev` |
|
31 | /// Same as `mercurial.node.wdirrev` | |
32 | /// |
|
32 | /// | |
33 | /// This is also equal to `i32::max_value()`, but it's better to spell |
|
33 | /// This is also equal to `i32::max_value()`, but it's better to spell | |
34 | /// it out explicitely, same as in `mercurial.node` |
|
34 | /// it out explicitely, same as in `mercurial.node` | |
35 | #[allow(clippy::unreadable_literal)] |
|
35 | #[allow(clippy::unreadable_literal)] | |
36 | pub const WORKING_DIRECTORY_REVISION: Revision = 0x7fffffff; |
|
36 | pub const WORKING_DIRECTORY_REVISION: Revision = 0x7fffffff; | |
37 |
|
37 | |||
38 | /// The simplest expression of what we need of Mercurial DAGs. |
|
38 | /// The simplest expression of what we need of Mercurial DAGs. | |
39 | pub trait Graph { |
|
39 | pub trait Graph { | |
40 | /// Return the two parents of the given `Revision`. |
|
40 | /// Return the two parents of the given `Revision`. | |
41 | /// |
|
41 | /// | |
42 | /// Each of the parents can be independently `NULL_REVISION` |
|
42 | /// Each of the parents can be independently `NULL_REVISION` | |
43 | fn parents(&self, rev: Revision) -> Result<[Revision; 2], GraphError>; |
|
43 | fn parents(&self, rev: Revision) -> Result<[Revision; 2], GraphError>; | |
44 | } |
|
44 | } | |
45 |
|
45 | |||
46 | #[derive(Clone, Debug, PartialEq)] |
|
46 | #[derive(Clone, Debug, PartialEq)] | |
47 | pub enum GraphError { |
|
47 | pub enum GraphError { | |
48 | ParentOutOfRange(Revision), |
|
48 | ParentOutOfRange(Revision), | |
49 | WorkingDirectoryUnsupported, |
|
49 | WorkingDirectoryUnsupported, | |
50 | } |
|
50 | } | |
51 |
|
51 | |||
52 | /// The Mercurial Revlog Index |
|
52 | /// The Mercurial Revlog Index | |
53 | /// |
|
53 | /// | |
54 | /// This is currently limited to the minimal interface that is needed for |
|
54 | /// This is currently limited to the minimal interface that is needed for | |
55 | /// the [`nodemap`](nodemap/index.html) module |
|
55 | /// the [`nodemap`](nodemap/index.html) module | |
56 | pub trait RevlogIndex { |
|
56 | pub trait RevlogIndex { | |
57 | /// Total number of Revisions referenced in this index |
|
57 | /// Total number of Revisions referenced in this index | |
58 | fn len(&self) -> usize; |
|
58 | fn len(&self) -> usize; | |
59 |
|
59 | |||
60 | fn is_empty(&self) -> bool { |
|
60 | fn is_empty(&self) -> bool { | |
61 | self.len() == 0 |
|
61 | self.len() == 0 | |
62 | } |
|
62 | } | |
63 |
|
63 | |||
64 | /// Return a reference to the Node or `None` if rev is out of bounds |
|
64 | /// Return a reference to the Node or `None` if rev is out of bounds | |
65 | /// |
|
65 | /// | |
66 | /// `NULL_REVISION` is not considered to be out of bounds. |
|
66 | /// `NULL_REVISION` is not considered to be out of bounds. | |
67 | fn node(&self, rev: Revision) -> Option<&Node>; |
|
67 | fn node(&self, rev: Revision) -> Option<&Node>; | |
68 | } |
|
68 | } |
@@ -1,459 +1,412 b'' | |||||
1 | // Copyright 2019-2020 Georges Racinet <georges.racinet@octobus.net> |
|
1 | // Copyright 2019-2020 Georges Racinet <georges.racinet@octobus.net> | |
2 | // |
|
2 | // | |
3 | // This software may be used and distributed according to the terms of the |
|
3 | // This software may be used and distributed according to the terms of the | |
4 | // GNU General Public License version 2 or any later version. |
|
4 | // GNU General Public License version 2 or any later version. | |
5 |
|
5 | |||
6 | //! Definitions and utilities for Revision nodes |
|
6 | //! Definitions and utilities for Revision nodes | |
7 | //! |
|
7 | //! | |
8 | //! In Mercurial code base, it is customary to call "a node" the binary SHA |
|
8 | //! In Mercurial code base, it is customary to call "a node" the binary SHA | |
9 | //! of a revision. |
|
9 | //! of a revision. | |
10 |
|
10 | |||
11 | use bytes_cast::BytesCast; |
|
11 | use bytes_cast::BytesCast; | |
12 |
use hex::{self, FromHex |
|
12 | use hex::{self, FromHex}; | |
13 | use std::convert::TryFrom; |
|
13 | use std::convert::TryFrom; | |
14 | use std::fmt; |
|
14 | use std::fmt; | |
15 |
|
15 | |||
16 | /// The length in bytes of a `Node` |
|
16 | /// The length in bytes of a `Node` | |
17 | /// |
|
17 | /// | |
18 | /// This constant is meant to ease refactors of this module, and |
|
18 | /// This constant is meant to ease refactors of this module, and | |
19 | /// are private so that calling code does not expect all nodes have |
|
19 | /// are private so that calling code does not expect all nodes have | |
20 | /// the same size, should we support several formats concurrently in |
|
20 | /// the same size, should we support several formats concurrently in | |
21 | /// the future. |
|
21 | /// the future. | |
22 | pub const NODE_BYTES_LENGTH: usize = 20; |
|
22 | pub const NODE_BYTES_LENGTH: usize = 20; | |
23 |
|
23 | |||
24 | /// Id of the null node. |
|
24 | /// Id of the null node. | |
25 | /// |
|
25 | /// | |
26 | /// Used to indicate the absence of node. |
|
26 | /// Used to indicate the absence of node. | |
27 | pub const NULL_NODE_ID: [u8; NODE_BYTES_LENGTH] = [0u8; NODE_BYTES_LENGTH]; |
|
27 | pub const NULL_NODE_ID: [u8; NODE_BYTES_LENGTH] = [0u8; NODE_BYTES_LENGTH]; | |
28 |
|
28 | |||
29 | /// The length in bytes of a `Node` |
|
29 | /// The length in bytes of a `Node` | |
30 | /// |
|
30 | /// | |
31 | /// see also `NODES_BYTES_LENGTH` about it being private. |
|
31 | /// see also `NODES_BYTES_LENGTH` about it being private. | |
32 | const NODE_NYBBLES_LENGTH: usize = 2 * NODE_BYTES_LENGTH; |
|
32 | const NODE_NYBBLES_LENGTH: usize = 2 * NODE_BYTES_LENGTH; | |
33 |
|
33 | |||
34 | /// Private alias for readability and to ease future change |
|
34 | /// Private alias for readability and to ease future change | |
35 | type NodeData = [u8; NODE_BYTES_LENGTH]; |
|
35 | type NodeData = [u8; NODE_BYTES_LENGTH]; | |
36 |
|
36 | |||
37 | /// Binary revision SHA |
|
37 | /// Binary revision SHA | |
38 | /// |
|
38 | /// | |
39 | /// ## Future changes of hash size |
|
39 | /// ## Future changes of hash size | |
40 | /// |
|
40 | /// | |
41 | /// To accomodate future changes of hash size, Rust callers |
|
41 | /// To accomodate future changes of hash size, Rust callers | |
42 | /// should use the conversion methods at the boundaries (FFI, actual |
|
42 | /// should use the conversion methods at the boundaries (FFI, actual | |
43 | /// computation of hashes and I/O) only, and only if required. |
|
43 | /// computation of hashes and I/O) only, and only if required. | |
44 | /// |
|
44 | /// | |
45 | /// All other callers outside of unit tests should just handle `Node` values |
|
45 | /// All other callers outside of unit tests should just handle `Node` values | |
46 | /// and never make any assumption on the actual length, using [`nybbles_len`] |
|
46 | /// and never make any assumption on the actual length, using [`nybbles_len`] | |
47 | /// if they need a loop boundary. |
|
47 | /// if they need a loop boundary. | |
48 | /// |
|
48 | /// | |
49 | /// All methods that create a `Node` either take a type that enforces |
|
49 | /// All methods that create a `Node` either take a type that enforces | |
50 | /// the size or fail immediately at runtime with [`ExactLengthRequired`]. |
|
50 | /// the size or return an error at runtime. | |
51 | /// |
|
51 | /// | |
52 | /// [`nybbles_len`]: #method.nybbles_len |
|
52 | /// [`nybbles_len`]: #method.nybbles_len | |
53 | /// [`ExactLengthRequired`]: struct.NodeError#variant.ExactLengthRequired |
|
|||
54 | #[derive(Clone, Debug, PartialEq, BytesCast)] |
|
53 | #[derive(Clone, Debug, PartialEq, BytesCast)] | |
55 | #[repr(transparent)] |
|
54 | #[repr(transparent)] | |
56 | pub struct Node { |
|
55 | pub struct Node { | |
57 | data: NodeData, |
|
56 | data: NodeData, | |
58 | } |
|
57 | } | |
59 |
|
58 | |||
60 | /// The node value for NULL_REVISION |
|
59 | /// The node value for NULL_REVISION | |
61 | pub const NULL_NODE: Node = Node { |
|
60 | pub const NULL_NODE: Node = Node { | |
62 | data: [0; NODE_BYTES_LENGTH], |
|
61 | data: [0; NODE_BYTES_LENGTH], | |
63 | }; |
|
62 | }; | |
64 |
|
63 | |||
65 | impl From<NodeData> for Node { |
|
64 | impl From<NodeData> for Node { | |
66 | fn from(data: NodeData) -> Node { |
|
65 | fn from(data: NodeData) -> Node { | |
67 | Node { data } |
|
66 | Node { data } | |
68 | } |
|
67 | } | |
69 | } |
|
68 | } | |
70 |
|
69 | |||
71 | /// Return an error if the slice has an unexpected length |
|
70 | /// Return an error if the slice has an unexpected length | |
72 | impl<'a> TryFrom<&'a [u8]> for &'a Node { |
|
71 | impl<'a> TryFrom<&'a [u8]> for &'a Node { | |
73 | type Error = (); |
|
72 | type Error = (); | |
74 |
|
73 | |||
75 | #[inline] |
|
74 | #[inline] | |
76 | fn try_from(bytes: &'a [u8]) -> Result<&'a Node, Self::Error> { |
|
75 | fn try_from(bytes: &'a [u8]) -> Result<&'a Node, Self::Error> { | |
77 | match Node::from_bytes(bytes) { |
|
76 | match Node::from_bytes(bytes) { | |
78 | Ok((node, rest)) if rest.is_empty() => Ok(node), |
|
77 | Ok((node, rest)) if rest.is_empty() => Ok(node), | |
79 | _ => Err(()), |
|
78 | _ => Err(()), | |
80 | } |
|
79 | } | |
81 | } |
|
80 | } | |
82 | } |
|
81 | } | |
83 |
|
82 | |||
84 | impl fmt::LowerHex for Node { |
|
83 | impl fmt::LowerHex for Node { | |
85 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { |
|
84 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { | |
86 | for &byte in &self.data { |
|
85 | for &byte in &self.data { | |
87 | write!(f, "{:02x}", byte)? |
|
86 | write!(f, "{:02x}", byte)? | |
88 | } |
|
87 | } | |
89 | Ok(()) |
|
88 | Ok(()) | |
90 | } |
|
89 | } | |
91 | } |
|
90 | } | |
92 |
|
91 | |||
93 |
#[derive(Debug |
|
92 | #[derive(Debug)] | |
94 | pub enum NodeError { |
|
93 | pub struct FromHexError; | |
95 | ExactLengthRequired(usize, String), |
|
|||
96 | PrefixTooLong(String), |
|
|||
97 | HexError(FromHexError, String), |
|
|||
98 | } |
|
|||
99 |
|
94 | |||
100 | /// Low level utility function, also for prefixes |
|
95 | /// Low level utility function, also for prefixes | |
101 | fn get_nybble(s: &[u8], i: usize) -> u8 { |
|
96 | fn get_nybble(s: &[u8], i: usize) -> u8 { | |
102 | if i % 2 == 0 { |
|
97 | if i % 2 == 0 { | |
103 | s[i / 2] >> 4 |
|
98 | s[i / 2] >> 4 | |
104 | } else { |
|
99 | } else { | |
105 | s[i / 2] & 0x0f |
|
100 | s[i / 2] & 0x0f | |
106 | } |
|
101 | } | |
107 | } |
|
102 | } | |
108 |
|
103 | |||
109 | impl Node { |
|
104 | impl Node { | |
110 | /// Retrieve the `i`th half-byte of the binary data. |
|
105 | /// Retrieve the `i`th half-byte of the binary data. | |
111 | /// |
|
106 | /// | |
112 | /// This is also the `i`th hexadecimal digit in numeric form, |
|
107 | /// This is also the `i`th hexadecimal digit in numeric form, | |
113 | /// also called a [nybble](https://en.wikipedia.org/wiki/Nibble). |
|
108 | /// also called a [nybble](https://en.wikipedia.org/wiki/Nibble). | |
114 | pub fn get_nybble(&self, i: usize) -> u8 { |
|
109 | pub fn get_nybble(&self, i: usize) -> u8 { | |
115 | get_nybble(&self.data, i) |
|
110 | get_nybble(&self.data, i) | |
116 | } |
|
111 | } | |
117 |
|
112 | |||
118 | /// Length of the data, in nybbles |
|
113 | /// Length of the data, in nybbles | |
119 | pub fn nybbles_len(&self) -> usize { |
|
114 | pub fn nybbles_len(&self) -> usize { | |
120 | // public exposure as an instance method only, so that we can |
|
115 | // public exposure as an instance method only, so that we can | |
121 | // easily support several sizes of hashes if needed in the future. |
|
116 | // easily support several sizes of hashes if needed in the future. | |
122 | NODE_NYBBLES_LENGTH |
|
117 | NODE_NYBBLES_LENGTH | |
123 | } |
|
118 | } | |
124 |
|
119 | |||
125 | /// Convert from hexadecimal string representation |
|
120 | /// Convert from hexadecimal string representation | |
126 | /// |
|
121 | /// | |
127 | /// Exact length is required. |
|
122 | /// Exact length is required. | |
128 | /// |
|
123 | /// | |
129 | /// To be used in FFI and I/O only, in order to facilitate future |
|
124 | /// To be used in FFI and I/O only, in order to facilitate future | |
130 | /// changes of hash format. |
|
125 | /// changes of hash format. | |
131 |
pub fn from_hex(hex: impl AsRef<[u8]>) -> Result<Node, |
|
126 | pub fn from_hex(hex: impl AsRef<[u8]>) -> Result<Node, FromHexError> { | |
132 | Ok(NodeData::from_hex(hex.as_ref()) |
|
127 | Ok(NodeData::from_hex(hex.as_ref()) | |
133 |
.map_err(| |
|
128 | .map_err(|_| FromHexError)? | |
134 | .into()) |
|
129 | .into()) | |
135 | } |
|
130 | } | |
136 |
|
131 | |||
137 | /// Provide access to binary data |
|
132 | /// Provide access to binary data | |
138 | /// |
|
133 | /// | |
139 | /// This is needed by FFI layers, for instance to return expected |
|
134 | /// This is needed by FFI layers, for instance to return expected | |
140 | /// binary values to Python. |
|
135 | /// binary values to Python. | |
141 | pub fn as_bytes(&self) -> &[u8] { |
|
136 | pub fn as_bytes(&self) -> &[u8] { | |
142 | &self.data |
|
137 | &self.data | |
143 | } |
|
138 | } | |
144 | } |
|
139 | } | |
145 |
|
140 | |||
146 | impl<T: AsRef<[u8]>> From<(FromHexError, T)> for NodeError { |
|
|||
147 | fn from(err_offender: (FromHexError, T)) -> Self { |
|
|||
148 | let (err, offender) = err_offender; |
|
|||
149 | let offender = String::from_utf8_lossy(offender.as_ref()).into_owned(); |
|
|||
150 | match err { |
|
|||
151 | FromHexError::InvalidStringLength => { |
|
|||
152 | NodeError::ExactLengthRequired(NODE_NYBBLES_LENGTH, offender) |
|
|||
153 | } |
|
|||
154 | _ => NodeError::HexError(err, offender), |
|
|||
155 | } |
|
|||
156 | } |
|
|||
157 | } |
|
|||
158 |
|
||||
159 | /// The beginning of a binary revision SHA. |
|
141 | /// The beginning of a binary revision SHA. | |
160 | /// |
|
142 | /// | |
161 | /// Since it can potentially come from an hexadecimal representation with |
|
143 | /// Since it can potentially come from an hexadecimal representation with | |
162 | /// odd length, it needs to carry around whether the last 4 bits are relevant |
|
144 | /// odd length, it needs to carry around whether the last 4 bits are relevant | |
163 | /// or not. |
|
145 | /// or not. | |
164 | #[derive(Debug, PartialEq)] |
|
146 | #[derive(Debug, PartialEq)] | |
165 | pub struct NodePrefix { |
|
147 | pub struct NodePrefix { | |
166 | buf: Vec<u8>, |
|
148 | buf: Vec<u8>, | |
167 | is_odd: bool, |
|
149 | is_odd: bool, | |
168 | } |
|
150 | } | |
169 |
|
151 | |||
170 | impl NodePrefix { |
|
152 | impl NodePrefix { | |
171 | /// Convert from hexadecimal string representation |
|
153 | /// Convert from hexadecimal string representation | |
172 | /// |
|
154 | /// | |
173 | /// Similarly to `hex::decode`, can be used with Unicode string types |
|
155 | /// Similarly to `hex::decode`, can be used with Unicode string types | |
174 | /// (`String`, `&str`) as well as bytes. |
|
156 | /// (`String`, `&str`) as well as bytes. | |
175 | /// |
|
157 | /// | |
176 | /// To be used in FFI and I/O only, in order to facilitate future |
|
158 | /// To be used in FFI and I/O only, in order to facilitate future | |
177 | /// changes of hash format. |
|
159 | /// changes of hash format. | |
178 |
pub fn from_hex(hex: impl AsRef<[u8]>) -> Result<Self, |
|
160 | pub fn from_hex(hex: impl AsRef<[u8]>) -> Result<Self, FromHexError> { | |
179 | let hex = hex.as_ref(); |
|
161 | let hex = hex.as_ref(); | |
180 | let len = hex.len(); |
|
162 | let len = hex.len(); | |
181 | if len > NODE_NYBBLES_LENGTH { |
|
163 | if len > NODE_NYBBLES_LENGTH { | |
182 |
return Err( |
|
164 | return Err(FromHexError); | |
183 | String::from_utf8_lossy(hex).to_owned().to_string(), |
|
|||
184 | )); |
|
|||
185 | } |
|
165 | } | |
186 |
|
166 | |||
187 | let is_odd = len % 2 == 1; |
|
167 | let is_odd = len % 2 == 1; | |
188 | let even_part = if is_odd { &hex[..len - 1] } else { hex }; |
|
168 | let even_part = if is_odd { &hex[..len - 1] } else { hex }; | |
189 | let mut buf: Vec<u8> = |
|
169 | let mut buf: Vec<u8> = | |
190 |
Vec::from_hex(&even_part).map_err(| |
|
170 | Vec::from_hex(&even_part).map_err(|_| FromHexError)?; | |
191 |
|
171 | |||
192 | if is_odd { |
|
172 | if is_odd { | |
193 | let latest_char = char::from(hex[len - 1]); |
|
173 | let latest_char = char::from(hex[len - 1]); | |
194 |
let latest_nybble = |
|
174 | let latest_nybble = | |
195 | ( |
|
175 | latest_char.to_digit(16).ok_or_else(|| FromHexError)? as u8; | |
196 | FromHexError::InvalidHexCharacter { |
|
|||
197 | c: latest_char, |
|
|||
198 | index: len - 1, |
|
|||
199 | }, |
|
|||
200 | hex, |
|
|||
201 | ) |
|
|||
202 | })? as u8; |
|
|||
203 | buf.push(latest_nybble << 4); |
|
176 | buf.push(latest_nybble << 4); | |
204 | } |
|
177 | } | |
205 | Ok(NodePrefix { buf, is_odd }) |
|
178 | Ok(NodePrefix { buf, is_odd }) | |
206 | } |
|
179 | } | |
207 |
|
180 | |||
208 | pub fn borrow(&self) -> NodePrefixRef { |
|
181 | pub fn borrow(&self) -> NodePrefixRef { | |
209 | NodePrefixRef { |
|
182 | NodePrefixRef { | |
210 | buf: &self.buf, |
|
183 | buf: &self.buf, | |
211 | is_odd: self.is_odd, |
|
184 | is_odd: self.is_odd, | |
212 | } |
|
185 | } | |
213 | } |
|
186 | } | |
214 | } |
|
187 | } | |
215 |
|
188 | |||
216 | #[derive(Clone, Debug, PartialEq)] |
|
189 | #[derive(Clone, Debug, PartialEq)] | |
217 | pub struct NodePrefixRef<'a> { |
|
190 | pub struct NodePrefixRef<'a> { | |
218 | buf: &'a [u8], |
|
191 | buf: &'a [u8], | |
219 | is_odd: bool, |
|
192 | is_odd: bool, | |
220 | } |
|
193 | } | |
221 |
|
194 | |||
222 | impl<'a> NodePrefixRef<'a> { |
|
195 | impl<'a> NodePrefixRef<'a> { | |
223 | pub fn len(&self) -> usize { |
|
196 | pub fn len(&self) -> usize { | |
224 | if self.is_odd { |
|
197 | if self.is_odd { | |
225 | self.buf.len() * 2 - 1 |
|
198 | self.buf.len() * 2 - 1 | |
226 | } else { |
|
199 | } else { | |
227 | self.buf.len() * 2 |
|
200 | self.buf.len() * 2 | |
228 | } |
|
201 | } | |
229 | } |
|
202 | } | |
230 |
|
203 | |||
231 | pub fn is_empty(&self) -> bool { |
|
204 | pub fn is_empty(&self) -> bool { | |
232 | self.len() == 0 |
|
205 | self.len() == 0 | |
233 | } |
|
206 | } | |
234 |
|
207 | |||
235 | pub fn is_prefix_of(&self, node: &Node) -> bool { |
|
208 | pub fn is_prefix_of(&self, node: &Node) -> bool { | |
236 | if self.is_odd { |
|
209 | if self.is_odd { | |
237 | let buf = self.buf; |
|
210 | let buf = self.buf; | |
238 | let last_pos = buf.len() - 1; |
|
211 | let last_pos = buf.len() - 1; | |
239 | node.data.starts_with(buf.split_at(last_pos).0) |
|
212 | node.data.starts_with(buf.split_at(last_pos).0) | |
240 | && node.data[last_pos] >> 4 == buf[last_pos] >> 4 |
|
213 | && node.data[last_pos] >> 4 == buf[last_pos] >> 4 | |
241 | } else { |
|
214 | } else { | |
242 | node.data.starts_with(self.buf) |
|
215 | node.data.starts_with(self.buf) | |
243 | } |
|
216 | } | |
244 | } |
|
217 | } | |
245 |
|
218 | |||
246 | /// Retrieve the `i`th half-byte from the prefix. |
|
219 | /// Retrieve the `i`th half-byte from the prefix. | |
247 | /// |
|
220 | /// | |
248 | /// This is also the `i`th hexadecimal digit in numeric form, |
|
221 | /// This is also the `i`th hexadecimal digit in numeric form, | |
249 | /// also called a [nybble](https://en.wikipedia.org/wiki/Nibble). |
|
222 | /// also called a [nybble](https://en.wikipedia.org/wiki/Nibble). | |
250 | pub fn get_nybble(&self, i: usize) -> u8 { |
|
223 | pub fn get_nybble(&self, i: usize) -> u8 { | |
251 | assert!(i < self.len()); |
|
224 | assert!(i < self.len()); | |
252 | get_nybble(self.buf, i) |
|
225 | get_nybble(self.buf, i) | |
253 | } |
|
226 | } | |
254 |
|
227 | |||
255 | /// Return the index first nybble that's different from `node` |
|
228 | /// Return the index first nybble that's different from `node` | |
256 | /// |
|
229 | /// | |
257 | /// If the return value is `None` that means that `self` is |
|
230 | /// If the return value is `None` that means that `self` is | |
258 | /// a prefix of `node`, but the current method is a bit slower |
|
231 | /// a prefix of `node`, but the current method is a bit slower | |
259 | /// than `is_prefix_of`. |
|
232 | /// than `is_prefix_of`. | |
260 | /// |
|
233 | /// | |
261 | /// Returned index is as in `get_nybble`, i.e., starting at 0. |
|
234 | /// Returned index is as in `get_nybble`, i.e., starting at 0. | |
262 | pub fn first_different_nybble(&self, node: &Node) -> Option<usize> { |
|
235 | pub fn first_different_nybble(&self, node: &Node) -> Option<usize> { | |
263 | let buf = self.buf; |
|
236 | let buf = self.buf; | |
264 | let until = if self.is_odd { |
|
237 | let until = if self.is_odd { | |
265 | buf.len() - 1 |
|
238 | buf.len() - 1 | |
266 | } else { |
|
239 | } else { | |
267 | buf.len() |
|
240 | buf.len() | |
268 | }; |
|
241 | }; | |
269 | for (i, item) in buf.iter().enumerate().take(until) { |
|
242 | for (i, item) in buf.iter().enumerate().take(until) { | |
270 | if *item != node.data[i] { |
|
243 | if *item != node.data[i] { | |
271 | return if *item & 0xf0 == node.data[i] & 0xf0 { |
|
244 | return if *item & 0xf0 == node.data[i] & 0xf0 { | |
272 | Some(2 * i + 1) |
|
245 | Some(2 * i + 1) | |
273 | } else { |
|
246 | } else { | |
274 | Some(2 * i) |
|
247 | Some(2 * i) | |
275 | }; |
|
248 | }; | |
276 | } |
|
249 | } | |
277 | } |
|
250 | } | |
278 | if self.is_odd && buf[until] & 0xf0 != node.data[until] & 0xf0 { |
|
251 | if self.is_odd && buf[until] & 0xf0 != node.data[until] & 0xf0 { | |
279 | Some(until * 2) |
|
252 | Some(until * 2) | |
280 | } else { |
|
253 | } else { | |
281 | None |
|
254 | None | |
282 | } |
|
255 | } | |
283 | } |
|
256 | } | |
284 | } |
|
257 | } | |
285 |
|
258 | |||
286 | /// A shortcut for full `Node` references |
|
259 | /// A shortcut for full `Node` references | |
287 | impl<'a> From<&'a Node> for NodePrefixRef<'a> { |
|
260 | impl<'a> From<&'a Node> for NodePrefixRef<'a> { | |
288 | fn from(node: &'a Node) -> Self { |
|
261 | fn from(node: &'a Node) -> Self { | |
289 | NodePrefixRef { |
|
262 | NodePrefixRef { | |
290 | buf: &node.data, |
|
263 | buf: &node.data, | |
291 | is_odd: false, |
|
264 | is_odd: false, | |
292 | } |
|
265 | } | |
293 | } |
|
266 | } | |
294 | } |
|
267 | } | |
295 |
|
268 | |||
296 | impl PartialEq<Node> for NodePrefixRef<'_> { |
|
269 | impl PartialEq<Node> for NodePrefixRef<'_> { | |
297 | fn eq(&self, other: &Node) -> bool { |
|
270 | fn eq(&self, other: &Node) -> bool { | |
298 | !self.is_odd && self.buf == other.data |
|
271 | !self.is_odd && self.buf == other.data | |
299 | } |
|
272 | } | |
300 | } |
|
273 | } | |
301 |
|
274 | |||
302 | #[cfg(test)] |
|
275 | #[cfg(test)] | |
303 | mod tests { |
|
276 | mod tests { | |
304 | use super::*; |
|
277 | use super::*; | |
305 |
|
278 | |||
306 | fn sample_node() -> Node { |
|
279 | fn sample_node() -> Node { | |
307 | let mut data = [0; NODE_BYTES_LENGTH]; |
|
280 | let mut data = [0; NODE_BYTES_LENGTH]; | |
308 | data.copy_from_slice(&[ |
|
281 | data.copy_from_slice(&[ | |
309 | 0x01, 0x23, 0x45, 0x67, 0x89, 0xab, 0xcd, 0xef, 0xfe, 0xdc, 0xba, |
|
282 | 0x01, 0x23, 0x45, 0x67, 0x89, 0xab, 0xcd, 0xef, 0xfe, 0xdc, 0xba, | |
310 | 0x98, 0x76, 0x54, 0x32, 0x10, 0xde, 0xad, 0xbe, 0xef, |
|
283 | 0x98, 0x76, 0x54, 0x32, 0x10, 0xde, 0xad, 0xbe, 0xef, | |
311 | ]); |
|
284 | ]); | |
312 | data.into() |
|
285 | data.into() | |
313 | } |
|
286 | } | |
314 |
|
287 | |||
315 | /// Pad an hexadecimal string to reach `NODE_NYBBLES_LENGTH` |
|
288 | /// Pad an hexadecimal string to reach `NODE_NYBBLES_LENGTH` | |
316 | ///check_hash |
|
289 | ///check_hash | |
317 | /// The padding is made with zeros |
|
290 | /// The padding is made with zeros | |
318 | pub fn hex_pad_right(hex: &str) -> String { |
|
291 | pub fn hex_pad_right(hex: &str) -> String { | |
319 | let mut res = hex.to_string(); |
|
292 | let mut res = hex.to_string(); | |
320 | while res.len() < NODE_NYBBLES_LENGTH { |
|
293 | while res.len() < NODE_NYBBLES_LENGTH { | |
321 | res.push('0'); |
|
294 | res.push('0'); | |
322 | } |
|
295 | } | |
323 | res |
|
296 | res | |
324 | } |
|
297 | } | |
325 |
|
298 | |||
326 | fn sample_node_hex() -> String { |
|
299 | fn sample_node_hex() -> String { | |
327 | hex_pad_right("0123456789abcdeffedcba9876543210deadbeef") |
|
300 | hex_pad_right("0123456789abcdeffedcba9876543210deadbeef") | |
328 | } |
|
301 | } | |
329 |
|
302 | |||
330 | #[test] |
|
303 | #[test] | |
331 | fn test_node_from_hex() { |
|
304 | fn test_node_from_hex() { | |
332 |
assert_eq!(Node::from_hex(&sample_node_hex()), |
|
305 | assert_eq!(Node::from_hex(&sample_node_hex()).unwrap(), sample_node()); | |
333 |
|
306 | |||
334 | let mut short = hex_pad_right("0123"); |
|
307 | let mut short = hex_pad_right("0123"); | |
335 | short.pop(); |
|
308 | short.pop(); | |
336 | short.pop(); |
|
309 | short.pop(); | |
337 | assert_eq!( |
|
310 | assert!(Node::from_hex(&short).is_err()); | |
338 | Node::from_hex(&short), |
|
|||
339 | Err(NodeError::ExactLengthRequired(NODE_NYBBLES_LENGTH, short)), |
|
|||
340 | ); |
|
|||
341 |
|
311 | |||
342 | let not_hex = hex_pad_right("012... oops"); |
|
312 | let not_hex = hex_pad_right("012... oops"); | |
343 | assert_eq!( |
|
313 | assert!(Node::from_hex(¬_hex).is_err(),); | |
344 | Node::from_hex(¬_hex), |
|
|||
345 | Err(NodeError::HexError( |
|
|||
346 | FromHexError::InvalidHexCharacter { c: '.', index: 3 }, |
|
|||
347 | not_hex, |
|
|||
348 | )), |
|
|||
349 | ); |
|
|||
350 | } |
|
314 | } | |
351 |
|
315 | |||
352 | #[test] |
|
316 | #[test] | |
353 | fn test_node_encode_hex() { |
|
317 | fn test_node_encode_hex() { | |
354 | assert_eq!(format!("{:x}", sample_node()), sample_node_hex()); |
|
318 | assert_eq!(format!("{:x}", sample_node()), sample_node_hex()); | |
355 | } |
|
319 | } | |
356 |
|
320 | |||
357 | #[test] |
|
321 | #[test] | |
358 |
fn test_prefix_from_hex() -> Result<(), |
|
322 | fn test_prefix_from_hex() -> Result<(), FromHexError> { | |
359 | assert_eq!( |
|
323 | assert_eq!( | |
360 | NodePrefix::from_hex("0e1")?, |
|
324 | NodePrefix::from_hex("0e1")?, | |
361 | NodePrefix { |
|
325 | NodePrefix { | |
362 | buf: vec![14, 16], |
|
326 | buf: vec![14, 16], | |
363 | is_odd: true |
|
327 | is_odd: true | |
364 | } |
|
328 | } | |
365 | ); |
|
329 | ); | |
366 | assert_eq!( |
|
330 | assert_eq!( | |
367 | NodePrefix::from_hex("0e1a")?, |
|
331 | NodePrefix::from_hex("0e1a")?, | |
368 | NodePrefix { |
|
332 | NodePrefix { | |
369 | buf: vec![14, 26], |
|
333 | buf: vec![14, 26], | |
370 | is_odd: false |
|
334 | is_odd: false | |
371 | } |
|
335 | } | |
372 | ); |
|
336 | ); | |
373 |
|
337 | |||
374 | // checking limit case |
|
338 | // checking limit case | |
375 | let node_as_vec = sample_node().data.iter().cloned().collect(); |
|
339 | let node_as_vec = sample_node().data.iter().cloned().collect(); | |
376 | assert_eq!( |
|
340 | assert_eq!( | |
377 | NodePrefix::from_hex(sample_node_hex())?, |
|
341 | NodePrefix::from_hex(sample_node_hex())?, | |
378 | NodePrefix { |
|
342 | NodePrefix { | |
379 | buf: node_as_vec, |
|
343 | buf: node_as_vec, | |
380 | is_odd: false |
|
344 | is_odd: false | |
381 | } |
|
345 | } | |
382 | ); |
|
346 | ); | |
383 |
|
347 | |||
384 | Ok(()) |
|
348 | Ok(()) | |
385 | } |
|
349 | } | |
386 |
|
350 | |||
387 | #[test] |
|
351 | #[test] | |
388 | fn test_prefix_from_hex_errors() { |
|
352 | fn test_prefix_from_hex_errors() { | |
389 | assert_eq!( |
|
353 | assert!(NodePrefix::from_hex("testgr").is_err()); | |
390 | NodePrefix::from_hex("testgr"), |
|
|||
391 | Err(NodeError::HexError( |
|
|||
392 | FromHexError::InvalidHexCharacter { c: 't', index: 0 }, |
|
|||
393 | "testgr".to_string() |
|
|||
394 | )) |
|
|||
395 | ); |
|
|||
396 | let mut long = format!("{:x}", NULL_NODE); |
|
354 | let mut long = format!("{:x}", NULL_NODE); | |
397 | long.push('c'); |
|
355 | long.push('c'); | |
398 |
|
|
356 | assert!(NodePrefix::from_hex(&long).is_err()) | |
399 | .expect_err("should be refused as too long") |
|
|||
400 | { |
|
|||
401 | NodeError::PrefixTooLong(s) => assert_eq!(s, long), |
|
|||
402 | err => panic!(format!("Should have been TooLong, got {:?}", err)), |
|
|||
403 | } |
|
|||
404 | } |
|
357 | } | |
405 |
|
358 | |||
406 | #[test] |
|
359 | #[test] | |
407 |
fn test_is_prefix_of() -> Result<(), |
|
360 | fn test_is_prefix_of() -> Result<(), FromHexError> { | |
408 | let mut node_data = [0; NODE_BYTES_LENGTH]; |
|
361 | let mut node_data = [0; NODE_BYTES_LENGTH]; | |
409 | node_data[0] = 0x12; |
|
362 | node_data[0] = 0x12; | |
410 | node_data[1] = 0xca; |
|
363 | node_data[1] = 0xca; | |
411 | let node = Node::from(node_data); |
|
364 | let node = Node::from(node_data); | |
412 | assert!(NodePrefix::from_hex("12")?.borrow().is_prefix_of(&node)); |
|
365 | assert!(NodePrefix::from_hex("12")?.borrow().is_prefix_of(&node)); | |
413 | assert!(!NodePrefix::from_hex("1a")?.borrow().is_prefix_of(&node)); |
|
366 | assert!(!NodePrefix::from_hex("1a")?.borrow().is_prefix_of(&node)); | |
414 | assert!(NodePrefix::from_hex("12c")?.borrow().is_prefix_of(&node)); |
|
367 | assert!(NodePrefix::from_hex("12c")?.borrow().is_prefix_of(&node)); | |
415 | assert!(!NodePrefix::from_hex("12d")?.borrow().is_prefix_of(&node)); |
|
368 | assert!(!NodePrefix::from_hex("12d")?.borrow().is_prefix_of(&node)); | |
416 | Ok(()) |
|
369 | Ok(()) | |
417 | } |
|
370 | } | |
418 |
|
371 | |||
419 | #[test] |
|
372 | #[test] | |
420 |
fn test_get_nybble() -> Result<(), |
|
373 | fn test_get_nybble() -> Result<(), FromHexError> { | |
421 | let prefix = NodePrefix::from_hex("dead6789cafe")?; |
|
374 | let prefix = NodePrefix::from_hex("dead6789cafe")?; | |
422 | assert_eq!(prefix.borrow().get_nybble(0), 13); |
|
375 | assert_eq!(prefix.borrow().get_nybble(0), 13); | |
423 | assert_eq!(prefix.borrow().get_nybble(7), 9); |
|
376 | assert_eq!(prefix.borrow().get_nybble(7), 9); | |
424 | Ok(()) |
|
377 | Ok(()) | |
425 | } |
|
378 | } | |
426 |
|
379 | |||
427 | #[test] |
|
380 | #[test] | |
428 | fn test_first_different_nybble_even_prefix() { |
|
381 | fn test_first_different_nybble_even_prefix() { | |
429 | let prefix = NodePrefix::from_hex("12ca").unwrap(); |
|
382 | let prefix = NodePrefix::from_hex("12ca").unwrap(); | |
430 | let prefref = prefix.borrow(); |
|
383 | let prefref = prefix.borrow(); | |
431 | let mut node = Node::from([0; NODE_BYTES_LENGTH]); |
|
384 | let mut node = Node::from([0; NODE_BYTES_LENGTH]); | |
432 | assert_eq!(prefref.first_different_nybble(&node), Some(0)); |
|
385 | assert_eq!(prefref.first_different_nybble(&node), Some(0)); | |
433 | node.data[0] = 0x13; |
|
386 | node.data[0] = 0x13; | |
434 | assert_eq!(prefref.first_different_nybble(&node), Some(1)); |
|
387 | assert_eq!(prefref.first_different_nybble(&node), Some(1)); | |
435 | node.data[0] = 0x12; |
|
388 | node.data[0] = 0x12; | |
436 | assert_eq!(prefref.first_different_nybble(&node), Some(2)); |
|
389 | assert_eq!(prefref.first_different_nybble(&node), Some(2)); | |
437 | node.data[1] = 0xca; |
|
390 | node.data[1] = 0xca; | |
438 | // now it is a prefix |
|
391 | // now it is a prefix | |
439 | assert_eq!(prefref.first_different_nybble(&node), None); |
|
392 | assert_eq!(prefref.first_different_nybble(&node), None); | |
440 | } |
|
393 | } | |
441 |
|
394 | |||
442 | #[test] |
|
395 | #[test] | |
443 | fn test_first_different_nybble_odd_prefix() { |
|
396 | fn test_first_different_nybble_odd_prefix() { | |
444 | let prefix = NodePrefix::from_hex("12c").unwrap(); |
|
397 | let prefix = NodePrefix::from_hex("12c").unwrap(); | |
445 | let prefref = prefix.borrow(); |
|
398 | let prefref = prefix.borrow(); | |
446 | let mut node = Node::from([0; NODE_BYTES_LENGTH]); |
|
399 | let mut node = Node::from([0; NODE_BYTES_LENGTH]); | |
447 | assert_eq!(prefref.first_different_nybble(&node), Some(0)); |
|
400 | assert_eq!(prefref.first_different_nybble(&node), Some(0)); | |
448 | node.data[0] = 0x13; |
|
401 | node.data[0] = 0x13; | |
449 | assert_eq!(prefref.first_different_nybble(&node), Some(1)); |
|
402 | assert_eq!(prefref.first_different_nybble(&node), Some(1)); | |
450 | node.data[0] = 0x12; |
|
403 | node.data[0] = 0x12; | |
451 | assert_eq!(prefref.first_different_nybble(&node), Some(2)); |
|
404 | assert_eq!(prefref.first_different_nybble(&node), Some(2)); | |
452 | node.data[1] = 0xca; |
|
405 | node.data[1] = 0xca; | |
453 | // now it is a prefix |
|
406 | // now it is a prefix | |
454 | assert_eq!(prefref.first_different_nybble(&node), None); |
|
407 | assert_eq!(prefref.first_different_nybble(&node), None); | |
455 | } |
|
408 | } | |
456 | } |
|
409 | } | |
457 |
|
410 | |||
458 | #[cfg(test)] |
|
411 | #[cfg(test)] | |
459 | pub use tests::hex_pad_right; |
|
412 | pub use tests::hex_pad_right; |
@@ -1,1101 +1,1101 b'' | |||||
1 | // Copyright 2018-2020 Georges Racinet <georges.racinet@octobus.net> |
|
1 | // Copyright 2018-2020 Georges Racinet <georges.racinet@octobus.net> | |
2 | // and Mercurial contributors |
|
2 | // and Mercurial contributors | |
3 | // |
|
3 | // | |
4 | // This software may be used and distributed according to the terms of the |
|
4 | // This software may be used and distributed according to the terms of the | |
5 | // GNU General Public License version 2 or any later version. |
|
5 | // GNU General Public License version 2 or any later version. | |
6 | //! Indexing facilities for fast retrieval of `Revision` from `Node` |
|
6 | //! Indexing facilities for fast retrieval of `Revision` from `Node` | |
7 | //! |
|
7 | //! | |
8 | //! This provides a variation on the 16-ary radix tree that is |
|
8 | //! This provides a variation on the 16-ary radix tree that is | |
9 | //! provided as "nodetree" in revlog.c, ready for append-only persistence |
|
9 | //! provided as "nodetree" in revlog.c, ready for append-only persistence | |
10 | //! on disk. |
|
10 | //! on disk. | |
11 | //! |
|
11 | //! | |
12 | //! Following existing implicit conventions, the "nodemap" terminology |
|
12 | //! Following existing implicit conventions, the "nodemap" terminology | |
13 | //! is used in a more abstract context. |
|
13 | //! is used in a more abstract context. | |
14 |
|
14 | |||
15 | use super::{ |
|
15 | use super::{ | |
16 |
node::NULL_NODE, |
|
16 | node::NULL_NODE, FromHexError, Node, NodePrefix, NodePrefixRef, Revision, | |
17 | RevlogIndex, NULL_REVISION, |
|
17 | RevlogIndex, NULL_REVISION, | |
18 | }; |
|
18 | }; | |
19 |
|
19 | |||
20 | use bytes_cast::{unaligned, BytesCast}; |
|
20 | use bytes_cast::{unaligned, BytesCast}; | |
21 | use std::cmp::max; |
|
21 | use std::cmp::max; | |
22 | use std::fmt; |
|
22 | use std::fmt; | |
23 | use std::mem::{self, align_of, size_of}; |
|
23 | use std::mem::{self, align_of, size_of}; | |
24 | use std::ops::Deref; |
|
24 | use std::ops::Deref; | |
25 | use std::ops::Index; |
|
25 | use std::ops::Index; | |
26 |
|
26 | |||
27 | #[derive(Debug, PartialEq)] |
|
27 | #[derive(Debug, PartialEq)] | |
28 | pub enum NodeMapError { |
|
28 | pub enum NodeMapError { | |
29 | MultipleResults, |
|
29 | MultipleResults, | |
30 |
InvalidNodePrefix |
|
30 | InvalidNodePrefix, | |
31 | /// A `Revision` stored in the nodemap could not be found in the index |
|
31 | /// A `Revision` stored in the nodemap could not be found in the index | |
32 | RevisionNotInIndex(Revision), |
|
32 | RevisionNotInIndex(Revision), | |
33 | } |
|
33 | } | |
34 |
|
34 | |||
35 |
impl From< |
|
35 | impl From<FromHexError> for NodeMapError { | |
36 |
fn from( |
|
36 | fn from(_: FromHexError) -> Self { | |
37 |
NodeMapError::InvalidNodePrefix |
|
37 | NodeMapError::InvalidNodePrefix | |
38 | } |
|
38 | } | |
39 | } |
|
39 | } | |
40 |
|
40 | |||
41 | /// Mapping system from Mercurial nodes to revision numbers. |
|
41 | /// Mapping system from Mercurial nodes to revision numbers. | |
42 | /// |
|
42 | /// | |
43 | /// ## `RevlogIndex` and `NodeMap` |
|
43 | /// ## `RevlogIndex` and `NodeMap` | |
44 | /// |
|
44 | /// | |
45 | /// One way to think about their relationship is that |
|
45 | /// One way to think about their relationship is that | |
46 | /// the `NodeMap` is a prefix-oriented reverse index of the `Node` information |
|
46 | /// the `NodeMap` is a prefix-oriented reverse index of the `Node` information | |
47 | /// carried by a [`RevlogIndex`]. |
|
47 | /// carried by a [`RevlogIndex`]. | |
48 | /// |
|
48 | /// | |
49 | /// Many of the methods in this trait take a `RevlogIndex` argument |
|
49 | /// Many of the methods in this trait take a `RevlogIndex` argument | |
50 | /// which is used for validation of their results. This index must naturally |
|
50 | /// which is used for validation of their results. This index must naturally | |
51 | /// be the one the `NodeMap` is about, and it must be consistent. |
|
51 | /// be the one the `NodeMap` is about, and it must be consistent. | |
52 | /// |
|
52 | /// | |
53 | /// Notably, the `NodeMap` must not store |
|
53 | /// Notably, the `NodeMap` must not store | |
54 | /// information about more `Revision` values than there are in the index. |
|
54 | /// information about more `Revision` values than there are in the index. | |
55 | /// In these methods, an encountered `Revision` is not in the index, a |
|
55 | /// In these methods, an encountered `Revision` is not in the index, a | |
56 | /// [`RevisionNotInIndex`] error is returned. |
|
56 | /// [`RevisionNotInIndex`] error is returned. | |
57 | /// |
|
57 | /// | |
58 | /// In insert operations, the rule is thus that the `NodeMap` must always |
|
58 | /// In insert operations, the rule is thus that the `NodeMap` must always | |
59 | /// be updated after the `RevlogIndex` |
|
59 | /// be updated after the `RevlogIndex` | |
60 | /// be updated first, and the `NodeMap` second. |
|
60 | /// be updated first, and the `NodeMap` second. | |
61 | /// |
|
61 | /// | |
62 | /// [`RevisionNotInIndex`]: enum.NodeMapError.html#variant.RevisionNotInIndex |
|
62 | /// [`RevisionNotInIndex`]: enum.NodeMapError.html#variant.RevisionNotInIndex | |
63 | /// [`RevlogIndex`]: ../trait.RevlogIndex.html |
|
63 | /// [`RevlogIndex`]: ../trait.RevlogIndex.html | |
64 | pub trait NodeMap { |
|
64 | pub trait NodeMap { | |
65 | /// Find the unique `Revision` having the given `Node` |
|
65 | /// Find the unique `Revision` having the given `Node` | |
66 | /// |
|
66 | /// | |
67 | /// If no Revision matches the given `Node`, `Ok(None)` is returned. |
|
67 | /// If no Revision matches the given `Node`, `Ok(None)` is returned. | |
68 | fn find_node( |
|
68 | fn find_node( | |
69 | &self, |
|
69 | &self, | |
70 | index: &impl RevlogIndex, |
|
70 | index: &impl RevlogIndex, | |
71 | node: &Node, |
|
71 | node: &Node, | |
72 | ) -> Result<Option<Revision>, NodeMapError> { |
|
72 | ) -> Result<Option<Revision>, NodeMapError> { | |
73 | self.find_bin(index, node.into()) |
|
73 | self.find_bin(index, node.into()) | |
74 | } |
|
74 | } | |
75 |
|
75 | |||
76 | /// Find the unique Revision whose `Node` starts with a given binary prefix |
|
76 | /// Find the unique Revision whose `Node` starts with a given binary prefix | |
77 | /// |
|
77 | /// | |
78 | /// If no Revision matches the given prefix, `Ok(None)` is returned. |
|
78 | /// If no Revision matches the given prefix, `Ok(None)` is returned. | |
79 | /// |
|
79 | /// | |
80 | /// If several Revisions match the given prefix, a [`MultipleResults`] |
|
80 | /// If several Revisions match the given prefix, a [`MultipleResults`] | |
81 | /// error is returned. |
|
81 | /// error is returned. | |
82 | fn find_bin<'a>( |
|
82 | fn find_bin<'a>( | |
83 | &self, |
|
83 | &self, | |
84 | idx: &impl RevlogIndex, |
|
84 | idx: &impl RevlogIndex, | |
85 | prefix: NodePrefixRef<'a>, |
|
85 | prefix: NodePrefixRef<'a>, | |
86 | ) -> Result<Option<Revision>, NodeMapError>; |
|
86 | ) -> Result<Option<Revision>, NodeMapError>; | |
87 |
|
87 | |||
88 | /// Find the unique Revision whose `Node` hexadecimal string representation |
|
88 | /// Find the unique Revision whose `Node` hexadecimal string representation | |
89 | /// starts with a given prefix |
|
89 | /// starts with a given prefix | |
90 | /// |
|
90 | /// | |
91 | /// If no Revision matches the given prefix, `Ok(None)` is returned. |
|
91 | /// If no Revision matches the given prefix, `Ok(None)` is returned. | |
92 | /// |
|
92 | /// | |
93 | /// If several Revisions match the given prefix, a [`MultipleResults`] |
|
93 | /// If several Revisions match the given prefix, a [`MultipleResults`] | |
94 | /// error is returned. |
|
94 | /// error is returned. | |
95 | fn find_hex( |
|
95 | fn find_hex( | |
96 | &self, |
|
96 | &self, | |
97 | idx: &impl RevlogIndex, |
|
97 | idx: &impl RevlogIndex, | |
98 | prefix: &str, |
|
98 | prefix: &str, | |
99 | ) -> Result<Option<Revision>, NodeMapError> { |
|
99 | ) -> Result<Option<Revision>, NodeMapError> { | |
100 | self.find_bin(idx, NodePrefix::from_hex(prefix)?.borrow()) |
|
100 | self.find_bin(idx, NodePrefix::from_hex(prefix)?.borrow()) | |
101 | } |
|
101 | } | |
102 |
|
102 | |||
103 | /// Give the size of the shortest node prefix that determines |
|
103 | /// Give the size of the shortest node prefix that determines | |
104 | /// the revision uniquely. |
|
104 | /// the revision uniquely. | |
105 | /// |
|
105 | /// | |
106 | /// From a binary node prefix, if it is matched in the node map, this |
|
106 | /// From a binary node prefix, if it is matched in the node map, this | |
107 | /// returns the number of hexadecimal digits that would had sufficed |
|
107 | /// returns the number of hexadecimal digits that would had sufficed | |
108 | /// to find the revision uniquely. |
|
108 | /// to find the revision uniquely. | |
109 | /// |
|
109 | /// | |
110 | /// Returns `None` if no `Revision` could be found for the prefix. |
|
110 | /// Returns `None` if no `Revision` could be found for the prefix. | |
111 | /// |
|
111 | /// | |
112 | /// If several Revisions match the given prefix, a [`MultipleResults`] |
|
112 | /// If several Revisions match the given prefix, a [`MultipleResults`] | |
113 | /// error is returned. |
|
113 | /// error is returned. | |
114 | fn unique_prefix_len_bin<'a>( |
|
114 | fn unique_prefix_len_bin<'a>( | |
115 | &self, |
|
115 | &self, | |
116 | idx: &impl RevlogIndex, |
|
116 | idx: &impl RevlogIndex, | |
117 | node_prefix: NodePrefixRef<'a>, |
|
117 | node_prefix: NodePrefixRef<'a>, | |
118 | ) -> Result<Option<usize>, NodeMapError>; |
|
118 | ) -> Result<Option<usize>, NodeMapError>; | |
119 |
|
119 | |||
120 | /// Same as `unique_prefix_len_bin`, with the hexadecimal representation |
|
120 | /// Same as `unique_prefix_len_bin`, with the hexadecimal representation | |
121 | /// of the prefix as input. |
|
121 | /// of the prefix as input. | |
122 | fn unique_prefix_len_hex( |
|
122 | fn unique_prefix_len_hex( | |
123 | &self, |
|
123 | &self, | |
124 | idx: &impl RevlogIndex, |
|
124 | idx: &impl RevlogIndex, | |
125 | prefix: &str, |
|
125 | prefix: &str, | |
126 | ) -> Result<Option<usize>, NodeMapError> { |
|
126 | ) -> Result<Option<usize>, NodeMapError> { | |
127 | self.unique_prefix_len_bin(idx, NodePrefix::from_hex(prefix)?.borrow()) |
|
127 | self.unique_prefix_len_bin(idx, NodePrefix::from_hex(prefix)?.borrow()) | |
128 | } |
|
128 | } | |
129 |
|
129 | |||
130 | /// Same as `unique_prefix_len_bin`, with a full `Node` as input |
|
130 | /// Same as `unique_prefix_len_bin`, with a full `Node` as input | |
131 | fn unique_prefix_len_node( |
|
131 | fn unique_prefix_len_node( | |
132 | &self, |
|
132 | &self, | |
133 | idx: &impl RevlogIndex, |
|
133 | idx: &impl RevlogIndex, | |
134 | node: &Node, |
|
134 | node: &Node, | |
135 | ) -> Result<Option<usize>, NodeMapError> { |
|
135 | ) -> Result<Option<usize>, NodeMapError> { | |
136 | self.unique_prefix_len_bin(idx, node.into()) |
|
136 | self.unique_prefix_len_bin(idx, node.into()) | |
137 | } |
|
137 | } | |
138 | } |
|
138 | } | |
139 |
|
139 | |||
140 | pub trait MutableNodeMap: NodeMap { |
|
140 | pub trait MutableNodeMap: NodeMap { | |
141 | fn insert<I: RevlogIndex>( |
|
141 | fn insert<I: RevlogIndex>( | |
142 | &mut self, |
|
142 | &mut self, | |
143 | index: &I, |
|
143 | index: &I, | |
144 | node: &Node, |
|
144 | node: &Node, | |
145 | rev: Revision, |
|
145 | rev: Revision, | |
146 | ) -> Result<(), NodeMapError>; |
|
146 | ) -> Result<(), NodeMapError>; | |
147 | } |
|
147 | } | |
148 |
|
148 | |||
149 | /// Low level NodeTree [`Blocks`] elements |
|
149 | /// Low level NodeTree [`Blocks`] elements | |
150 | /// |
|
150 | /// | |
151 | /// These are exactly as for instance on persistent storage. |
|
151 | /// These are exactly as for instance on persistent storage. | |
152 | type RawElement = unaligned::I32Be; |
|
152 | type RawElement = unaligned::I32Be; | |
153 |
|
153 | |||
154 | /// High level representation of values in NodeTree |
|
154 | /// High level representation of values in NodeTree | |
155 | /// [`Blocks`](struct.Block.html) |
|
155 | /// [`Blocks`](struct.Block.html) | |
156 | /// |
|
156 | /// | |
157 | /// This is the high level representation that most algorithms should |
|
157 | /// This is the high level representation that most algorithms should | |
158 | /// use. |
|
158 | /// use. | |
159 | #[derive(Clone, Debug, Eq, PartialEq)] |
|
159 | #[derive(Clone, Debug, Eq, PartialEq)] | |
160 | enum Element { |
|
160 | enum Element { | |
161 | Rev(Revision), |
|
161 | Rev(Revision), | |
162 | Block(usize), |
|
162 | Block(usize), | |
163 | None, |
|
163 | None, | |
164 | } |
|
164 | } | |
165 |
|
165 | |||
166 | impl From<RawElement> for Element { |
|
166 | impl From<RawElement> for Element { | |
167 | /// Conversion from low level representation, after endianness conversion. |
|
167 | /// Conversion from low level representation, after endianness conversion. | |
168 | /// |
|
168 | /// | |
169 | /// See [`Block`](struct.Block.html) for explanation about the encoding. |
|
169 | /// See [`Block`](struct.Block.html) for explanation about the encoding. | |
170 | fn from(raw: RawElement) -> Element { |
|
170 | fn from(raw: RawElement) -> Element { | |
171 | let int = raw.get(); |
|
171 | let int = raw.get(); | |
172 | if int >= 0 { |
|
172 | if int >= 0 { | |
173 | Element::Block(int as usize) |
|
173 | Element::Block(int as usize) | |
174 | } else if int == -1 { |
|
174 | } else if int == -1 { | |
175 | Element::None |
|
175 | Element::None | |
176 | } else { |
|
176 | } else { | |
177 | Element::Rev(-int - 2) |
|
177 | Element::Rev(-int - 2) | |
178 | } |
|
178 | } | |
179 | } |
|
179 | } | |
180 | } |
|
180 | } | |
181 |
|
181 | |||
182 | impl From<Element> for RawElement { |
|
182 | impl From<Element> for RawElement { | |
183 | fn from(element: Element) -> RawElement { |
|
183 | fn from(element: Element) -> RawElement { | |
184 | RawElement::from(match element { |
|
184 | RawElement::from(match element { | |
185 | Element::None => 0, |
|
185 | Element::None => 0, | |
186 | Element::Block(i) => i as i32, |
|
186 | Element::Block(i) => i as i32, | |
187 | Element::Rev(rev) => -rev - 2, |
|
187 | Element::Rev(rev) => -rev - 2, | |
188 | }) |
|
188 | }) | |
189 | } |
|
189 | } | |
190 | } |
|
190 | } | |
191 |
|
191 | |||
192 | /// A logical block of the `NodeTree`, packed with a fixed size. |
|
192 | /// A logical block of the `NodeTree`, packed with a fixed size. | |
193 | /// |
|
193 | /// | |
194 | /// These are always used in container types implementing `Index<Block>`, |
|
194 | /// These are always used in container types implementing `Index<Block>`, | |
195 | /// such as `&Block` |
|
195 | /// such as `&Block` | |
196 | /// |
|
196 | /// | |
197 | /// As an array of integers, its ith element encodes that the |
|
197 | /// As an array of integers, its ith element encodes that the | |
198 | /// ith potential edge from the block, representing the ith hexadecimal digit |
|
198 | /// ith potential edge from the block, representing the ith hexadecimal digit | |
199 | /// (nybble) `i` is either: |
|
199 | /// (nybble) `i` is either: | |
200 | /// |
|
200 | /// | |
201 | /// - absent (value -1) |
|
201 | /// - absent (value -1) | |
202 | /// - another `Block` in the same indexable container (value ≥ 0) |
|
202 | /// - another `Block` in the same indexable container (value ≥ 0) | |
203 | /// - a `Revision` leaf (value ≤ -2) |
|
203 | /// - a `Revision` leaf (value ≤ -2) | |
204 | /// |
|
204 | /// | |
205 | /// Endianness has to be fixed for consistency on shared storage across |
|
205 | /// Endianness has to be fixed for consistency on shared storage across | |
206 | /// different architectures. |
|
206 | /// different architectures. | |
207 | /// |
|
207 | /// | |
208 | /// A key difference with the C `nodetree` is that we need to be |
|
208 | /// A key difference with the C `nodetree` is that we need to be | |
209 | /// able to represent the [`Block`] at index 0, hence -1 is the empty marker |
|
209 | /// able to represent the [`Block`] at index 0, hence -1 is the empty marker | |
210 | /// rather than 0 and the `Revision` range upper limit of -2 instead of -1. |
|
210 | /// rather than 0 and the `Revision` range upper limit of -2 instead of -1. | |
211 | /// |
|
211 | /// | |
212 | /// Another related difference is that `NULL_REVISION` (-1) is not |
|
212 | /// Another related difference is that `NULL_REVISION` (-1) is not | |
213 | /// represented at all, because we want an immutable empty nodetree |
|
213 | /// represented at all, because we want an immutable empty nodetree | |
214 | /// to be valid. |
|
214 | /// to be valid. | |
215 |
|
215 | |||
216 | const ELEMENTS_PER_BLOCK: usize = 16; // number of different values in a nybble |
|
216 | const ELEMENTS_PER_BLOCK: usize = 16; // number of different values in a nybble | |
217 |
|
217 | |||
218 | #[derive(Copy, Clone, BytesCast, PartialEq)] |
|
218 | #[derive(Copy, Clone, BytesCast, PartialEq)] | |
219 | #[repr(transparent)] |
|
219 | #[repr(transparent)] | |
220 | pub struct Block([RawElement; ELEMENTS_PER_BLOCK]); |
|
220 | pub struct Block([RawElement; ELEMENTS_PER_BLOCK]); | |
221 |
|
221 | |||
222 | impl Block { |
|
222 | impl Block { | |
223 | fn new() -> Self { |
|
223 | fn new() -> Self { | |
224 | let absent_node = RawElement::from(-1); |
|
224 | let absent_node = RawElement::from(-1); | |
225 | Block([absent_node; ELEMENTS_PER_BLOCK]) |
|
225 | Block([absent_node; ELEMENTS_PER_BLOCK]) | |
226 | } |
|
226 | } | |
227 |
|
227 | |||
228 | fn get(&self, nybble: u8) -> Element { |
|
228 | fn get(&self, nybble: u8) -> Element { | |
229 | self.0[nybble as usize].into() |
|
229 | self.0[nybble as usize].into() | |
230 | } |
|
230 | } | |
231 |
|
231 | |||
232 | fn set(&mut self, nybble: u8, element: Element) { |
|
232 | fn set(&mut self, nybble: u8, element: Element) { | |
233 | self.0[nybble as usize] = element.into() |
|
233 | self.0[nybble as usize] = element.into() | |
234 | } |
|
234 | } | |
235 | } |
|
235 | } | |
236 |
|
236 | |||
237 | impl fmt::Debug for Block { |
|
237 | impl fmt::Debug for Block { | |
238 | /// sparse representation for testing and debugging purposes |
|
238 | /// sparse representation for testing and debugging purposes | |
239 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { |
|
239 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { | |
240 | f.debug_map() |
|
240 | f.debug_map() | |
241 | .entries((0..16).filter_map(|i| match self.get(i) { |
|
241 | .entries((0..16).filter_map(|i| match self.get(i) { | |
242 | Element::None => None, |
|
242 | Element::None => None, | |
243 | element => Some((i, element)), |
|
243 | element => Some((i, element)), | |
244 | })) |
|
244 | })) | |
245 | .finish() |
|
245 | .finish() | |
246 | } |
|
246 | } | |
247 | } |
|
247 | } | |
248 |
|
248 | |||
249 | /// A mutable 16-radix tree with the root block logically at the end |
|
249 | /// A mutable 16-radix tree with the root block logically at the end | |
250 | /// |
|
250 | /// | |
251 | /// Because of the append only nature of our node trees, we need to |
|
251 | /// Because of the append only nature of our node trees, we need to | |
252 | /// keep the original untouched and store new blocks separately. |
|
252 | /// keep the original untouched and store new blocks separately. | |
253 | /// |
|
253 | /// | |
254 | /// The mutable root `Block` is kept apart so that we don't have to rebump |
|
254 | /// The mutable root `Block` is kept apart so that we don't have to rebump | |
255 | /// it on each insertion. |
|
255 | /// it on each insertion. | |
256 | pub struct NodeTree { |
|
256 | pub struct NodeTree { | |
257 | readonly: Box<dyn Deref<Target = [Block]> + Send>, |
|
257 | readonly: Box<dyn Deref<Target = [Block]> + Send>, | |
258 | growable: Vec<Block>, |
|
258 | growable: Vec<Block>, | |
259 | root: Block, |
|
259 | root: Block, | |
260 | masked_inner_blocks: usize, |
|
260 | masked_inner_blocks: usize, | |
261 | } |
|
261 | } | |
262 |
|
262 | |||
263 | impl Index<usize> for NodeTree { |
|
263 | impl Index<usize> for NodeTree { | |
264 | type Output = Block; |
|
264 | type Output = Block; | |
265 |
|
265 | |||
266 | fn index(&self, i: usize) -> &Block { |
|
266 | fn index(&self, i: usize) -> &Block { | |
267 | let ro_len = self.readonly.len(); |
|
267 | let ro_len = self.readonly.len(); | |
268 | if i < ro_len { |
|
268 | if i < ro_len { | |
269 | &self.readonly[i] |
|
269 | &self.readonly[i] | |
270 | } else if i == ro_len + self.growable.len() { |
|
270 | } else if i == ro_len + self.growable.len() { | |
271 | &self.root |
|
271 | &self.root | |
272 | } else { |
|
272 | } else { | |
273 | &self.growable[i - ro_len] |
|
273 | &self.growable[i - ro_len] | |
274 | } |
|
274 | } | |
275 | } |
|
275 | } | |
276 | } |
|
276 | } | |
277 |
|
277 | |||
278 | /// Return `None` unless the `Node` for `rev` has given prefix in `index`. |
|
278 | /// Return `None` unless the `Node` for `rev` has given prefix in `index`. | |
279 | fn has_prefix_or_none( |
|
279 | fn has_prefix_or_none( | |
280 | idx: &impl RevlogIndex, |
|
280 | idx: &impl RevlogIndex, | |
281 | prefix: NodePrefixRef, |
|
281 | prefix: NodePrefixRef, | |
282 | rev: Revision, |
|
282 | rev: Revision, | |
283 | ) -> Result<Option<Revision>, NodeMapError> { |
|
283 | ) -> Result<Option<Revision>, NodeMapError> { | |
284 | idx.node(rev) |
|
284 | idx.node(rev) | |
285 | .ok_or_else(|| NodeMapError::RevisionNotInIndex(rev)) |
|
285 | .ok_or_else(|| NodeMapError::RevisionNotInIndex(rev)) | |
286 | .map(|node| { |
|
286 | .map(|node| { | |
287 | if prefix.is_prefix_of(node) { |
|
287 | if prefix.is_prefix_of(node) { | |
288 | Some(rev) |
|
288 | Some(rev) | |
289 | } else { |
|
289 | } else { | |
290 | None |
|
290 | None | |
291 | } |
|
291 | } | |
292 | }) |
|
292 | }) | |
293 | } |
|
293 | } | |
294 |
|
294 | |||
295 | /// validate that the candidate's node starts indeed with given prefix, |
|
295 | /// validate that the candidate's node starts indeed with given prefix, | |
296 | /// and treat ambiguities related to `NULL_REVISION`. |
|
296 | /// and treat ambiguities related to `NULL_REVISION`. | |
297 | /// |
|
297 | /// | |
298 | /// From the data in the NodeTree, one can only conclude that some |
|
298 | /// From the data in the NodeTree, one can only conclude that some | |
299 | /// revision is the only one for a *subprefix* of the one being looked up. |
|
299 | /// revision is the only one for a *subprefix* of the one being looked up. | |
300 | fn validate_candidate( |
|
300 | fn validate_candidate( | |
301 | idx: &impl RevlogIndex, |
|
301 | idx: &impl RevlogIndex, | |
302 | prefix: NodePrefixRef, |
|
302 | prefix: NodePrefixRef, | |
303 | candidate: (Option<Revision>, usize), |
|
303 | candidate: (Option<Revision>, usize), | |
304 | ) -> Result<(Option<Revision>, usize), NodeMapError> { |
|
304 | ) -> Result<(Option<Revision>, usize), NodeMapError> { | |
305 | let (rev, steps) = candidate; |
|
305 | let (rev, steps) = candidate; | |
306 | if let Some(nz_nybble) = prefix.first_different_nybble(&NULL_NODE) { |
|
306 | if let Some(nz_nybble) = prefix.first_different_nybble(&NULL_NODE) { | |
307 | rev.map_or(Ok((None, steps)), |r| { |
|
307 | rev.map_or(Ok((None, steps)), |r| { | |
308 | has_prefix_or_none(idx, prefix, r) |
|
308 | has_prefix_or_none(idx, prefix, r) | |
309 | .map(|opt| (opt, max(steps, nz_nybble + 1))) |
|
309 | .map(|opt| (opt, max(steps, nz_nybble + 1))) | |
310 | }) |
|
310 | }) | |
311 | } else { |
|
311 | } else { | |
312 | // the prefix is only made of zeros; NULL_REVISION always matches it |
|
312 | // the prefix is only made of zeros; NULL_REVISION always matches it | |
313 | // and any other *valid* result is an ambiguity |
|
313 | // and any other *valid* result is an ambiguity | |
314 | match rev { |
|
314 | match rev { | |
315 | None => Ok((Some(NULL_REVISION), steps + 1)), |
|
315 | None => Ok((Some(NULL_REVISION), steps + 1)), | |
316 | Some(r) => match has_prefix_or_none(idx, prefix, r)? { |
|
316 | Some(r) => match has_prefix_or_none(idx, prefix, r)? { | |
317 | None => Ok((Some(NULL_REVISION), steps + 1)), |
|
317 | None => Ok((Some(NULL_REVISION), steps + 1)), | |
318 | _ => Err(NodeMapError::MultipleResults), |
|
318 | _ => Err(NodeMapError::MultipleResults), | |
319 | }, |
|
319 | }, | |
320 | } |
|
320 | } | |
321 | } |
|
321 | } | |
322 | } |
|
322 | } | |
323 |
|
323 | |||
324 | impl NodeTree { |
|
324 | impl NodeTree { | |
325 | /// Initiate a NodeTree from an immutable slice-like of `Block` |
|
325 | /// Initiate a NodeTree from an immutable slice-like of `Block` | |
326 | /// |
|
326 | /// | |
327 | /// We keep `readonly` and clone its root block if it isn't empty. |
|
327 | /// We keep `readonly` and clone its root block if it isn't empty. | |
328 | fn new(readonly: Box<dyn Deref<Target = [Block]> + Send>) -> Self { |
|
328 | fn new(readonly: Box<dyn Deref<Target = [Block]> + Send>) -> Self { | |
329 | let root = readonly.last().cloned().unwrap_or_else(Block::new); |
|
329 | let root = readonly.last().cloned().unwrap_or_else(Block::new); | |
330 | NodeTree { |
|
330 | NodeTree { | |
331 | readonly, |
|
331 | readonly, | |
332 | growable: Vec::new(), |
|
332 | growable: Vec::new(), | |
333 | root, |
|
333 | root, | |
334 | masked_inner_blocks: 0, |
|
334 | masked_inner_blocks: 0, | |
335 | } |
|
335 | } | |
336 | } |
|
336 | } | |
337 |
|
337 | |||
338 | /// Create from an opaque bunch of bytes |
|
338 | /// Create from an opaque bunch of bytes | |
339 | /// |
|
339 | /// | |
340 | /// The created `NodeTreeBytes` from `buffer`, |
|
340 | /// The created `NodeTreeBytes` from `buffer`, | |
341 | /// of which exactly `amount` bytes are used. |
|
341 | /// of which exactly `amount` bytes are used. | |
342 | /// |
|
342 | /// | |
343 | /// - `buffer` could be derived from `PyBuffer` and `Mmap` objects. |
|
343 | /// - `buffer` could be derived from `PyBuffer` and `Mmap` objects. | |
344 | /// - `offset` allows for the final file format to include fixed data |
|
344 | /// - `offset` allows for the final file format to include fixed data | |
345 | /// (generation number, behavioural flags) |
|
345 | /// (generation number, behavioural flags) | |
346 | /// - `amount` is expressed in bytes, and is not automatically derived from |
|
346 | /// - `amount` is expressed in bytes, and is not automatically derived from | |
347 | /// `bytes`, so that a caller that manages them atomically can perform |
|
347 | /// `bytes`, so that a caller that manages them atomically can perform | |
348 | /// temporary disk serializations and still rollback easily if needed. |
|
348 | /// temporary disk serializations and still rollback easily if needed. | |
349 | /// First use-case for this would be to support Mercurial shell hooks. |
|
349 | /// First use-case for this would be to support Mercurial shell hooks. | |
350 | /// |
|
350 | /// | |
351 | /// panics if `buffer` is smaller than `amount` |
|
351 | /// panics if `buffer` is smaller than `amount` | |
352 | pub fn load_bytes( |
|
352 | pub fn load_bytes( | |
353 | bytes: Box<dyn Deref<Target = [u8]> + Send>, |
|
353 | bytes: Box<dyn Deref<Target = [u8]> + Send>, | |
354 | amount: usize, |
|
354 | amount: usize, | |
355 | ) -> Self { |
|
355 | ) -> Self { | |
356 | NodeTree::new(Box::new(NodeTreeBytes::new(bytes, amount))) |
|
356 | NodeTree::new(Box::new(NodeTreeBytes::new(bytes, amount))) | |
357 | } |
|
357 | } | |
358 |
|
358 | |||
359 | /// Retrieve added `Block` and the original immutable data |
|
359 | /// Retrieve added `Block` and the original immutable data | |
360 | pub fn into_readonly_and_added( |
|
360 | pub fn into_readonly_and_added( | |
361 | self, |
|
361 | self, | |
362 | ) -> (Box<dyn Deref<Target = [Block]> + Send>, Vec<Block>) { |
|
362 | ) -> (Box<dyn Deref<Target = [Block]> + Send>, Vec<Block>) { | |
363 | let mut vec = self.growable; |
|
363 | let mut vec = self.growable; | |
364 | let readonly = self.readonly; |
|
364 | let readonly = self.readonly; | |
365 | if readonly.last() != Some(&self.root) { |
|
365 | if readonly.last() != Some(&self.root) { | |
366 | vec.push(self.root); |
|
366 | vec.push(self.root); | |
367 | } |
|
367 | } | |
368 | (readonly, vec) |
|
368 | (readonly, vec) | |
369 | } |
|
369 | } | |
370 |
|
370 | |||
371 | /// Retrieve added `Blocks` as bytes, ready to be written to persistent |
|
371 | /// Retrieve added `Blocks` as bytes, ready to be written to persistent | |
372 | /// storage |
|
372 | /// storage | |
373 | pub fn into_readonly_and_added_bytes( |
|
373 | pub fn into_readonly_and_added_bytes( | |
374 | self, |
|
374 | self, | |
375 | ) -> (Box<dyn Deref<Target = [Block]> + Send>, Vec<u8>) { |
|
375 | ) -> (Box<dyn Deref<Target = [Block]> + Send>, Vec<u8>) { | |
376 | let (readonly, vec) = self.into_readonly_and_added(); |
|
376 | let (readonly, vec) = self.into_readonly_and_added(); | |
377 | // Prevent running `v`'s destructor so we are in complete control |
|
377 | // Prevent running `v`'s destructor so we are in complete control | |
378 | // of the allocation. |
|
378 | // of the allocation. | |
379 | let vec = mem::ManuallyDrop::new(vec); |
|
379 | let vec = mem::ManuallyDrop::new(vec); | |
380 |
|
380 | |||
381 | // Transmute the `Vec<Block>` to a `Vec<u8>`. Blocks are contiguous |
|
381 | // Transmute the `Vec<Block>` to a `Vec<u8>`. Blocks are contiguous | |
382 | // bytes, so this is perfectly safe. |
|
382 | // bytes, so this is perfectly safe. | |
383 | let bytes = unsafe { |
|
383 | let bytes = unsafe { | |
384 | // Check for compatible allocation layout. |
|
384 | // Check for compatible allocation layout. | |
385 | // (Optimized away by constant-folding + dead code elimination.) |
|
385 | // (Optimized away by constant-folding + dead code elimination.) | |
386 | assert_eq!(size_of::<Block>(), 64); |
|
386 | assert_eq!(size_of::<Block>(), 64); | |
387 | assert_eq!(align_of::<Block>(), 1); |
|
387 | assert_eq!(align_of::<Block>(), 1); | |
388 |
|
388 | |||
389 | // /!\ Any use of `vec` after this is use-after-free. |
|
389 | // /!\ Any use of `vec` after this is use-after-free. | |
390 | // TODO: use `into_raw_parts` once stabilized |
|
390 | // TODO: use `into_raw_parts` once stabilized | |
391 | Vec::from_raw_parts( |
|
391 | Vec::from_raw_parts( | |
392 | vec.as_ptr() as *mut u8, |
|
392 | vec.as_ptr() as *mut u8, | |
393 | vec.len() * size_of::<Block>(), |
|
393 | vec.len() * size_of::<Block>(), | |
394 | vec.capacity() * size_of::<Block>(), |
|
394 | vec.capacity() * size_of::<Block>(), | |
395 | ) |
|
395 | ) | |
396 | }; |
|
396 | }; | |
397 | (readonly, bytes) |
|
397 | (readonly, bytes) | |
398 | } |
|
398 | } | |
399 |
|
399 | |||
400 | /// Total number of blocks |
|
400 | /// Total number of blocks | |
401 | fn len(&self) -> usize { |
|
401 | fn len(&self) -> usize { | |
402 | self.readonly.len() + self.growable.len() + 1 |
|
402 | self.readonly.len() + self.growable.len() + 1 | |
403 | } |
|
403 | } | |
404 |
|
404 | |||
405 | /// Implemented for completeness |
|
405 | /// Implemented for completeness | |
406 | /// |
|
406 | /// | |
407 | /// A `NodeTree` always has at least the mutable root block. |
|
407 | /// A `NodeTree` always has at least the mutable root block. | |
408 | #[allow(dead_code)] |
|
408 | #[allow(dead_code)] | |
409 | fn is_empty(&self) -> bool { |
|
409 | fn is_empty(&self) -> bool { | |
410 | false |
|
410 | false | |
411 | } |
|
411 | } | |
412 |
|
412 | |||
413 | /// Main working method for `NodeTree` searches |
|
413 | /// Main working method for `NodeTree` searches | |
414 | /// |
|
414 | /// | |
415 | /// The first returned value is the result of analysing `NodeTree` data |
|
415 | /// The first returned value is the result of analysing `NodeTree` data | |
416 | /// *alone*: whereas `None` guarantees that the given prefix is absent |
|
416 | /// *alone*: whereas `None` guarantees that the given prefix is absent | |
417 | /// from the `NodeTree` data (but still could match `NULL_NODE`), with |
|
417 | /// from the `NodeTree` data (but still could match `NULL_NODE`), with | |
418 | /// `Some(rev)`, it is to be understood that `rev` is the unique `Revision` |
|
418 | /// `Some(rev)`, it is to be understood that `rev` is the unique `Revision` | |
419 | /// that could match the prefix. Actually, all that can be inferred from |
|
419 | /// that could match the prefix. Actually, all that can be inferred from | |
420 | /// the `NodeTree` data is that `rev` is the revision with the longest |
|
420 | /// the `NodeTree` data is that `rev` is the revision with the longest | |
421 | /// common node prefix with the given prefix. |
|
421 | /// common node prefix with the given prefix. | |
422 | /// |
|
422 | /// | |
423 | /// The second returned value is the size of the smallest subprefix |
|
423 | /// The second returned value is the size of the smallest subprefix | |
424 | /// of `prefix` that would give the same result, i.e. not the |
|
424 | /// of `prefix` that would give the same result, i.e. not the | |
425 | /// `MultipleResults` error variant (again, using only the data of the |
|
425 | /// `MultipleResults` error variant (again, using only the data of the | |
426 | /// `NodeTree`). |
|
426 | /// `NodeTree`). | |
427 | fn lookup( |
|
427 | fn lookup( | |
428 | &self, |
|
428 | &self, | |
429 | prefix: NodePrefixRef, |
|
429 | prefix: NodePrefixRef, | |
430 | ) -> Result<(Option<Revision>, usize), NodeMapError> { |
|
430 | ) -> Result<(Option<Revision>, usize), NodeMapError> { | |
431 | for (i, visit_item) in self.visit(prefix).enumerate() { |
|
431 | for (i, visit_item) in self.visit(prefix).enumerate() { | |
432 | if let Some(opt) = visit_item.final_revision() { |
|
432 | if let Some(opt) = visit_item.final_revision() { | |
433 | return Ok((opt, i + 1)); |
|
433 | return Ok((opt, i + 1)); | |
434 | } |
|
434 | } | |
435 | } |
|
435 | } | |
436 | Err(NodeMapError::MultipleResults) |
|
436 | Err(NodeMapError::MultipleResults) | |
437 | } |
|
437 | } | |
438 |
|
438 | |||
439 | fn visit<'n, 'p>( |
|
439 | fn visit<'n, 'p>( | |
440 | &'n self, |
|
440 | &'n self, | |
441 | prefix: NodePrefixRef<'p>, |
|
441 | prefix: NodePrefixRef<'p>, | |
442 | ) -> NodeTreeVisitor<'n, 'p> { |
|
442 | ) -> NodeTreeVisitor<'n, 'p> { | |
443 | NodeTreeVisitor { |
|
443 | NodeTreeVisitor { | |
444 | nt: self, |
|
444 | nt: self, | |
445 | prefix, |
|
445 | prefix, | |
446 | visit: self.len() - 1, |
|
446 | visit: self.len() - 1, | |
447 | nybble_idx: 0, |
|
447 | nybble_idx: 0, | |
448 | done: false, |
|
448 | done: false, | |
449 | } |
|
449 | } | |
450 | } |
|
450 | } | |
451 | /// Return a mutable reference for `Block` at index `idx`. |
|
451 | /// Return a mutable reference for `Block` at index `idx`. | |
452 | /// |
|
452 | /// | |
453 | /// If `idx` lies in the immutable area, then the reference is to |
|
453 | /// If `idx` lies in the immutable area, then the reference is to | |
454 | /// a newly appended copy. |
|
454 | /// a newly appended copy. | |
455 | /// |
|
455 | /// | |
456 | /// Returns (new_idx, glen, mut_ref) where |
|
456 | /// Returns (new_idx, glen, mut_ref) where | |
457 | /// |
|
457 | /// | |
458 | /// - `new_idx` is the index of the mutable `Block` |
|
458 | /// - `new_idx` is the index of the mutable `Block` | |
459 | /// - `mut_ref` is a mutable reference to the mutable Block. |
|
459 | /// - `mut_ref` is a mutable reference to the mutable Block. | |
460 | /// - `glen` is the new length of `self.growable` |
|
460 | /// - `glen` is the new length of `self.growable` | |
461 | /// |
|
461 | /// | |
462 | /// Note: the caller wouldn't be allowed to query `self.growable.len()` |
|
462 | /// Note: the caller wouldn't be allowed to query `self.growable.len()` | |
463 | /// itself because of the mutable borrow taken with the returned `Block` |
|
463 | /// itself because of the mutable borrow taken with the returned `Block` | |
464 | fn mutable_block(&mut self, idx: usize) -> (usize, &mut Block, usize) { |
|
464 | fn mutable_block(&mut self, idx: usize) -> (usize, &mut Block, usize) { | |
465 | let ro_blocks = &self.readonly; |
|
465 | let ro_blocks = &self.readonly; | |
466 | let ro_len = ro_blocks.len(); |
|
466 | let ro_len = ro_blocks.len(); | |
467 | let glen = self.growable.len(); |
|
467 | let glen = self.growable.len(); | |
468 | if idx < ro_len { |
|
468 | if idx < ro_len { | |
469 | self.masked_inner_blocks += 1; |
|
469 | self.masked_inner_blocks += 1; | |
470 | self.growable.push(ro_blocks[idx]); |
|
470 | self.growable.push(ro_blocks[idx]); | |
471 | (glen + ro_len, &mut self.growable[glen], glen + 1) |
|
471 | (glen + ro_len, &mut self.growable[glen], glen + 1) | |
472 | } else if glen + ro_len == idx { |
|
472 | } else if glen + ro_len == idx { | |
473 | (idx, &mut self.root, glen) |
|
473 | (idx, &mut self.root, glen) | |
474 | } else { |
|
474 | } else { | |
475 | (idx, &mut self.growable[idx - ro_len], glen) |
|
475 | (idx, &mut self.growable[idx - ro_len], glen) | |
476 | } |
|
476 | } | |
477 | } |
|
477 | } | |
478 |
|
478 | |||
479 | /// Main insertion method |
|
479 | /// Main insertion method | |
480 | /// |
|
480 | /// | |
481 | /// This will dive in the node tree to find the deepest `Block` for |
|
481 | /// This will dive in the node tree to find the deepest `Block` for | |
482 | /// `node`, split it as much as needed and record `node` in there. |
|
482 | /// `node`, split it as much as needed and record `node` in there. | |
483 | /// The method then backtracks, updating references in all the visited |
|
483 | /// The method then backtracks, updating references in all the visited | |
484 | /// blocks from the root. |
|
484 | /// blocks from the root. | |
485 | /// |
|
485 | /// | |
486 | /// All the mutated `Block` are copied first to the growable part if |
|
486 | /// All the mutated `Block` are copied first to the growable part if | |
487 | /// needed. That happens for those in the immutable part except the root. |
|
487 | /// needed. That happens for those in the immutable part except the root. | |
488 | pub fn insert<I: RevlogIndex>( |
|
488 | pub fn insert<I: RevlogIndex>( | |
489 | &mut self, |
|
489 | &mut self, | |
490 | index: &I, |
|
490 | index: &I, | |
491 | node: &Node, |
|
491 | node: &Node, | |
492 | rev: Revision, |
|
492 | rev: Revision, | |
493 | ) -> Result<(), NodeMapError> { |
|
493 | ) -> Result<(), NodeMapError> { | |
494 | let ro_len = &self.readonly.len(); |
|
494 | let ro_len = &self.readonly.len(); | |
495 |
|
495 | |||
496 | let mut visit_steps: Vec<_> = self.visit(node.into()).collect(); |
|
496 | let mut visit_steps: Vec<_> = self.visit(node.into()).collect(); | |
497 | let read_nybbles = visit_steps.len(); |
|
497 | let read_nybbles = visit_steps.len(); | |
498 | // visit_steps cannot be empty, since we always visit the root block |
|
498 | // visit_steps cannot be empty, since we always visit the root block | |
499 | let deepest = visit_steps.pop().unwrap(); |
|
499 | let deepest = visit_steps.pop().unwrap(); | |
500 |
|
500 | |||
501 | let (mut block_idx, mut block, mut glen) = |
|
501 | let (mut block_idx, mut block, mut glen) = | |
502 | self.mutable_block(deepest.block_idx); |
|
502 | self.mutable_block(deepest.block_idx); | |
503 |
|
503 | |||
504 | if let Element::Rev(old_rev) = deepest.element { |
|
504 | if let Element::Rev(old_rev) = deepest.element { | |
505 | let old_node = index |
|
505 | let old_node = index | |
506 | .node(old_rev) |
|
506 | .node(old_rev) | |
507 | .ok_or_else(|| NodeMapError::RevisionNotInIndex(old_rev))?; |
|
507 | .ok_or_else(|| NodeMapError::RevisionNotInIndex(old_rev))?; | |
508 | if old_node == node { |
|
508 | if old_node == node { | |
509 | return Ok(()); // avoid creating lots of useless blocks |
|
509 | return Ok(()); // avoid creating lots of useless blocks | |
510 | } |
|
510 | } | |
511 |
|
511 | |||
512 | // Looping over the tail of nybbles in both nodes, creating |
|
512 | // Looping over the tail of nybbles in both nodes, creating | |
513 | // new blocks until we find the difference |
|
513 | // new blocks until we find the difference | |
514 | let mut new_block_idx = ro_len + glen; |
|
514 | let mut new_block_idx = ro_len + glen; | |
515 | let mut nybble = deepest.nybble; |
|
515 | let mut nybble = deepest.nybble; | |
516 | for nybble_pos in read_nybbles..node.nybbles_len() { |
|
516 | for nybble_pos in read_nybbles..node.nybbles_len() { | |
517 | block.set(nybble, Element::Block(new_block_idx)); |
|
517 | block.set(nybble, Element::Block(new_block_idx)); | |
518 |
|
518 | |||
519 | let new_nybble = node.get_nybble(nybble_pos); |
|
519 | let new_nybble = node.get_nybble(nybble_pos); | |
520 | let old_nybble = old_node.get_nybble(nybble_pos); |
|
520 | let old_nybble = old_node.get_nybble(nybble_pos); | |
521 |
|
521 | |||
522 | if old_nybble == new_nybble { |
|
522 | if old_nybble == new_nybble { | |
523 | self.growable.push(Block::new()); |
|
523 | self.growable.push(Block::new()); | |
524 | block = &mut self.growable[glen]; |
|
524 | block = &mut self.growable[glen]; | |
525 | glen += 1; |
|
525 | glen += 1; | |
526 | new_block_idx += 1; |
|
526 | new_block_idx += 1; | |
527 | nybble = new_nybble; |
|
527 | nybble = new_nybble; | |
528 | } else { |
|
528 | } else { | |
529 | let mut new_block = Block::new(); |
|
529 | let mut new_block = Block::new(); | |
530 | new_block.set(old_nybble, Element::Rev(old_rev)); |
|
530 | new_block.set(old_nybble, Element::Rev(old_rev)); | |
531 | new_block.set(new_nybble, Element::Rev(rev)); |
|
531 | new_block.set(new_nybble, Element::Rev(rev)); | |
532 | self.growable.push(new_block); |
|
532 | self.growable.push(new_block); | |
533 | break; |
|
533 | break; | |
534 | } |
|
534 | } | |
535 | } |
|
535 | } | |
536 | } else { |
|
536 | } else { | |
537 | // Free slot in the deepest block: no splitting has to be done |
|
537 | // Free slot in the deepest block: no splitting has to be done | |
538 | block.set(deepest.nybble, Element::Rev(rev)); |
|
538 | block.set(deepest.nybble, Element::Rev(rev)); | |
539 | } |
|
539 | } | |
540 |
|
540 | |||
541 | // Backtrack over visit steps to update references |
|
541 | // Backtrack over visit steps to update references | |
542 | while let Some(visited) = visit_steps.pop() { |
|
542 | while let Some(visited) = visit_steps.pop() { | |
543 | let to_write = Element::Block(block_idx); |
|
543 | let to_write = Element::Block(block_idx); | |
544 | if visit_steps.is_empty() { |
|
544 | if visit_steps.is_empty() { | |
545 | self.root.set(visited.nybble, to_write); |
|
545 | self.root.set(visited.nybble, to_write); | |
546 | break; |
|
546 | break; | |
547 | } |
|
547 | } | |
548 | let (new_idx, block, _) = self.mutable_block(visited.block_idx); |
|
548 | let (new_idx, block, _) = self.mutable_block(visited.block_idx); | |
549 | if block.get(visited.nybble) == to_write { |
|
549 | if block.get(visited.nybble) == to_write { | |
550 | break; |
|
550 | break; | |
551 | } |
|
551 | } | |
552 | block.set(visited.nybble, to_write); |
|
552 | block.set(visited.nybble, to_write); | |
553 | block_idx = new_idx; |
|
553 | block_idx = new_idx; | |
554 | } |
|
554 | } | |
555 | Ok(()) |
|
555 | Ok(()) | |
556 | } |
|
556 | } | |
557 |
|
557 | |||
558 | /// Make the whole `NodeTree` logically empty, without touching the |
|
558 | /// Make the whole `NodeTree` logically empty, without touching the | |
559 | /// immutable part. |
|
559 | /// immutable part. | |
560 | pub fn invalidate_all(&mut self) { |
|
560 | pub fn invalidate_all(&mut self) { | |
561 | self.root = Block::new(); |
|
561 | self.root = Block::new(); | |
562 | self.growable = Vec::new(); |
|
562 | self.growable = Vec::new(); | |
563 | self.masked_inner_blocks = self.readonly.len(); |
|
563 | self.masked_inner_blocks = self.readonly.len(); | |
564 | } |
|
564 | } | |
565 |
|
565 | |||
566 | /// Return the number of blocks in the readonly part that are currently |
|
566 | /// Return the number of blocks in the readonly part that are currently | |
567 | /// masked in the mutable part. |
|
567 | /// masked in the mutable part. | |
568 | /// |
|
568 | /// | |
569 | /// The `NodeTree` structure has no efficient way to know how many blocks |
|
569 | /// The `NodeTree` structure has no efficient way to know how many blocks | |
570 | /// are already unreachable in the readonly part. |
|
570 | /// are already unreachable in the readonly part. | |
571 | /// |
|
571 | /// | |
572 | /// After a call to `invalidate_all()`, the returned number can be actually |
|
572 | /// After a call to `invalidate_all()`, the returned number can be actually | |
573 | /// bigger than the whole readonly part, a conventional way to mean that |
|
573 | /// bigger than the whole readonly part, a conventional way to mean that | |
574 | /// all the readonly blocks have been masked. This is what is really |
|
574 | /// all the readonly blocks have been masked. This is what is really | |
575 | /// useful to the caller and does not require to know how many were |
|
575 | /// useful to the caller and does not require to know how many were | |
576 | /// actually unreachable to begin with. |
|
576 | /// actually unreachable to begin with. | |
577 | pub fn masked_readonly_blocks(&self) -> usize { |
|
577 | pub fn masked_readonly_blocks(&self) -> usize { | |
578 | if let Some(readonly_root) = self.readonly.last() { |
|
578 | if let Some(readonly_root) = self.readonly.last() { | |
579 | if readonly_root == &self.root { |
|
579 | if readonly_root == &self.root { | |
580 | return 0; |
|
580 | return 0; | |
581 | } |
|
581 | } | |
582 | } else { |
|
582 | } else { | |
583 | return 0; |
|
583 | return 0; | |
584 | } |
|
584 | } | |
585 | self.masked_inner_blocks + 1 |
|
585 | self.masked_inner_blocks + 1 | |
586 | } |
|
586 | } | |
587 | } |
|
587 | } | |
588 |
|
588 | |||
589 | pub struct NodeTreeBytes { |
|
589 | pub struct NodeTreeBytes { | |
590 | buffer: Box<dyn Deref<Target = [u8]> + Send>, |
|
590 | buffer: Box<dyn Deref<Target = [u8]> + Send>, | |
591 | len_in_blocks: usize, |
|
591 | len_in_blocks: usize, | |
592 | } |
|
592 | } | |
593 |
|
593 | |||
594 | impl NodeTreeBytes { |
|
594 | impl NodeTreeBytes { | |
595 | fn new( |
|
595 | fn new( | |
596 | buffer: Box<dyn Deref<Target = [u8]> + Send>, |
|
596 | buffer: Box<dyn Deref<Target = [u8]> + Send>, | |
597 | amount: usize, |
|
597 | amount: usize, | |
598 | ) -> Self { |
|
598 | ) -> Self { | |
599 | assert!(buffer.len() >= amount); |
|
599 | assert!(buffer.len() >= amount); | |
600 | let len_in_blocks = amount / size_of::<Block>(); |
|
600 | let len_in_blocks = amount / size_of::<Block>(); | |
601 | NodeTreeBytes { |
|
601 | NodeTreeBytes { | |
602 | buffer, |
|
602 | buffer, | |
603 | len_in_blocks, |
|
603 | len_in_blocks, | |
604 | } |
|
604 | } | |
605 | } |
|
605 | } | |
606 | } |
|
606 | } | |
607 |
|
607 | |||
608 | impl Deref for NodeTreeBytes { |
|
608 | impl Deref for NodeTreeBytes { | |
609 | type Target = [Block]; |
|
609 | type Target = [Block]; | |
610 |
|
610 | |||
611 | fn deref(&self) -> &[Block] { |
|
611 | fn deref(&self) -> &[Block] { | |
612 | Block::slice_from_bytes(&self.buffer, self.len_in_blocks) |
|
612 | Block::slice_from_bytes(&self.buffer, self.len_in_blocks) | |
613 | // `NodeTreeBytes::new` already asserted that `self.buffer` is |
|
613 | // `NodeTreeBytes::new` already asserted that `self.buffer` is | |
614 | // large enough. |
|
614 | // large enough. | |
615 | .unwrap() |
|
615 | .unwrap() | |
616 | .0 |
|
616 | .0 | |
617 | } |
|
617 | } | |
618 | } |
|
618 | } | |
619 |
|
619 | |||
620 | struct NodeTreeVisitor<'n, 'p> { |
|
620 | struct NodeTreeVisitor<'n, 'p> { | |
621 | nt: &'n NodeTree, |
|
621 | nt: &'n NodeTree, | |
622 | prefix: NodePrefixRef<'p>, |
|
622 | prefix: NodePrefixRef<'p>, | |
623 | visit: usize, |
|
623 | visit: usize, | |
624 | nybble_idx: usize, |
|
624 | nybble_idx: usize, | |
625 | done: bool, |
|
625 | done: bool, | |
626 | } |
|
626 | } | |
627 |
|
627 | |||
628 | #[derive(Debug, PartialEq, Clone)] |
|
628 | #[derive(Debug, PartialEq, Clone)] | |
629 | struct NodeTreeVisitItem { |
|
629 | struct NodeTreeVisitItem { | |
630 | block_idx: usize, |
|
630 | block_idx: usize, | |
631 | nybble: u8, |
|
631 | nybble: u8, | |
632 | element: Element, |
|
632 | element: Element, | |
633 | } |
|
633 | } | |
634 |
|
634 | |||
635 | impl<'n, 'p> Iterator for NodeTreeVisitor<'n, 'p> { |
|
635 | impl<'n, 'p> Iterator for NodeTreeVisitor<'n, 'p> { | |
636 | type Item = NodeTreeVisitItem; |
|
636 | type Item = NodeTreeVisitItem; | |
637 |
|
637 | |||
638 | fn next(&mut self) -> Option<Self::Item> { |
|
638 | fn next(&mut self) -> Option<Self::Item> { | |
639 | if self.done || self.nybble_idx >= self.prefix.len() { |
|
639 | if self.done || self.nybble_idx >= self.prefix.len() { | |
640 | return None; |
|
640 | return None; | |
641 | } |
|
641 | } | |
642 |
|
642 | |||
643 | let nybble = self.prefix.get_nybble(self.nybble_idx); |
|
643 | let nybble = self.prefix.get_nybble(self.nybble_idx); | |
644 | self.nybble_idx += 1; |
|
644 | self.nybble_idx += 1; | |
645 |
|
645 | |||
646 | let visit = self.visit; |
|
646 | let visit = self.visit; | |
647 | let element = self.nt[visit].get(nybble); |
|
647 | let element = self.nt[visit].get(nybble); | |
648 | if let Element::Block(idx) = element { |
|
648 | if let Element::Block(idx) = element { | |
649 | self.visit = idx; |
|
649 | self.visit = idx; | |
650 | } else { |
|
650 | } else { | |
651 | self.done = true; |
|
651 | self.done = true; | |
652 | } |
|
652 | } | |
653 |
|
653 | |||
654 | Some(NodeTreeVisitItem { |
|
654 | Some(NodeTreeVisitItem { | |
655 | block_idx: visit, |
|
655 | block_idx: visit, | |
656 | nybble, |
|
656 | nybble, | |
657 | element, |
|
657 | element, | |
658 | }) |
|
658 | }) | |
659 | } |
|
659 | } | |
660 | } |
|
660 | } | |
661 |
|
661 | |||
662 | impl NodeTreeVisitItem { |
|
662 | impl NodeTreeVisitItem { | |
663 | // Return `Some(opt)` if this item is final, with `opt` being the |
|
663 | // Return `Some(opt)` if this item is final, with `opt` being the | |
664 | // `Revision` that it may represent. |
|
664 | // `Revision` that it may represent. | |
665 | // |
|
665 | // | |
666 | // If the item is not terminal, return `None` |
|
666 | // If the item is not terminal, return `None` | |
667 | fn final_revision(&self) -> Option<Option<Revision>> { |
|
667 | fn final_revision(&self) -> Option<Option<Revision>> { | |
668 | match self.element { |
|
668 | match self.element { | |
669 | Element::Block(_) => None, |
|
669 | Element::Block(_) => None, | |
670 | Element::Rev(r) => Some(Some(r)), |
|
670 | Element::Rev(r) => Some(Some(r)), | |
671 | Element::None => Some(None), |
|
671 | Element::None => Some(None), | |
672 | } |
|
672 | } | |
673 | } |
|
673 | } | |
674 | } |
|
674 | } | |
675 |
|
675 | |||
676 | impl From<Vec<Block>> for NodeTree { |
|
676 | impl From<Vec<Block>> for NodeTree { | |
677 | fn from(vec: Vec<Block>) -> Self { |
|
677 | fn from(vec: Vec<Block>) -> Self { | |
678 | Self::new(Box::new(vec)) |
|
678 | Self::new(Box::new(vec)) | |
679 | } |
|
679 | } | |
680 | } |
|
680 | } | |
681 |
|
681 | |||
682 | impl fmt::Debug for NodeTree { |
|
682 | impl fmt::Debug for NodeTree { | |
683 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
|
683 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
684 | let readonly: &[Block] = &*self.readonly; |
|
684 | let readonly: &[Block] = &*self.readonly; | |
685 | write!( |
|
685 | write!( | |
686 | f, |
|
686 | f, | |
687 | "readonly: {:?}, growable: {:?}, root: {:?}", |
|
687 | "readonly: {:?}, growable: {:?}, root: {:?}", | |
688 | readonly, self.growable, self.root |
|
688 | readonly, self.growable, self.root | |
689 | ) |
|
689 | ) | |
690 | } |
|
690 | } | |
691 | } |
|
691 | } | |
692 |
|
692 | |||
693 | impl Default for NodeTree { |
|
693 | impl Default for NodeTree { | |
694 | /// Create a fully mutable empty NodeTree |
|
694 | /// Create a fully mutable empty NodeTree | |
695 | fn default() -> Self { |
|
695 | fn default() -> Self { | |
696 | NodeTree::new(Box::new(Vec::new())) |
|
696 | NodeTree::new(Box::new(Vec::new())) | |
697 | } |
|
697 | } | |
698 | } |
|
698 | } | |
699 |
|
699 | |||
700 | impl NodeMap for NodeTree { |
|
700 | impl NodeMap for NodeTree { | |
701 | fn find_bin<'a>( |
|
701 | fn find_bin<'a>( | |
702 | &self, |
|
702 | &self, | |
703 | idx: &impl RevlogIndex, |
|
703 | idx: &impl RevlogIndex, | |
704 | prefix: NodePrefixRef<'a>, |
|
704 | prefix: NodePrefixRef<'a>, | |
705 | ) -> Result<Option<Revision>, NodeMapError> { |
|
705 | ) -> Result<Option<Revision>, NodeMapError> { | |
706 | validate_candidate(idx, prefix.clone(), self.lookup(prefix)?) |
|
706 | validate_candidate(idx, prefix.clone(), self.lookup(prefix)?) | |
707 | .map(|(opt, _shortest)| opt) |
|
707 | .map(|(opt, _shortest)| opt) | |
708 | } |
|
708 | } | |
709 |
|
709 | |||
710 | fn unique_prefix_len_bin<'a>( |
|
710 | fn unique_prefix_len_bin<'a>( | |
711 | &self, |
|
711 | &self, | |
712 | idx: &impl RevlogIndex, |
|
712 | idx: &impl RevlogIndex, | |
713 | prefix: NodePrefixRef<'a>, |
|
713 | prefix: NodePrefixRef<'a>, | |
714 | ) -> Result<Option<usize>, NodeMapError> { |
|
714 | ) -> Result<Option<usize>, NodeMapError> { | |
715 | validate_candidate(idx, prefix.clone(), self.lookup(prefix)?) |
|
715 | validate_candidate(idx, prefix.clone(), self.lookup(prefix)?) | |
716 | .map(|(opt, shortest)| opt.map(|_rev| shortest)) |
|
716 | .map(|(opt, shortest)| opt.map(|_rev| shortest)) | |
717 | } |
|
717 | } | |
718 | } |
|
718 | } | |
719 |
|
719 | |||
720 | #[cfg(test)] |
|
720 | #[cfg(test)] | |
721 | mod tests { |
|
721 | mod tests { | |
722 | use super::NodeMapError::*; |
|
722 | use super::NodeMapError::*; | |
723 | use super::*; |
|
723 | use super::*; | |
724 | use crate::revlog::node::{hex_pad_right, Node}; |
|
724 | use crate::revlog::node::{hex_pad_right, Node}; | |
725 | use std::collections::HashMap; |
|
725 | use std::collections::HashMap; | |
726 |
|
726 | |||
727 | /// Creates a `Block` using a syntax close to the `Debug` output |
|
727 | /// Creates a `Block` using a syntax close to the `Debug` output | |
728 | macro_rules! block { |
|
728 | macro_rules! block { | |
729 | {$($nybble:tt : $variant:ident($val:tt)),*} => ( |
|
729 | {$($nybble:tt : $variant:ident($val:tt)),*} => ( | |
730 | { |
|
730 | { | |
731 | let mut block = Block::new(); |
|
731 | let mut block = Block::new(); | |
732 | $(block.set($nybble, Element::$variant($val)));*; |
|
732 | $(block.set($nybble, Element::$variant($val)));*; | |
733 | block |
|
733 | block | |
734 | } |
|
734 | } | |
735 | ) |
|
735 | ) | |
736 | } |
|
736 | } | |
737 |
|
737 | |||
738 | #[test] |
|
738 | #[test] | |
739 | fn test_block_debug() { |
|
739 | fn test_block_debug() { | |
740 | let mut block = Block::new(); |
|
740 | let mut block = Block::new(); | |
741 | block.set(1, Element::Rev(3)); |
|
741 | block.set(1, Element::Rev(3)); | |
742 | block.set(10, Element::Block(0)); |
|
742 | block.set(10, Element::Block(0)); | |
743 | assert_eq!(format!("{:?}", block), "{1: Rev(3), 10: Block(0)}"); |
|
743 | assert_eq!(format!("{:?}", block), "{1: Rev(3), 10: Block(0)}"); | |
744 | } |
|
744 | } | |
745 |
|
745 | |||
746 | #[test] |
|
746 | #[test] | |
747 | fn test_block_macro() { |
|
747 | fn test_block_macro() { | |
748 | let block = block! {5: Block(2)}; |
|
748 | let block = block! {5: Block(2)}; | |
749 | assert_eq!(format!("{:?}", block), "{5: Block(2)}"); |
|
749 | assert_eq!(format!("{:?}", block), "{5: Block(2)}"); | |
750 |
|
750 | |||
751 | let block = block! {13: Rev(15), 5: Block(2)}; |
|
751 | let block = block! {13: Rev(15), 5: Block(2)}; | |
752 | assert_eq!(format!("{:?}", block), "{5: Block(2), 13: Rev(15)}"); |
|
752 | assert_eq!(format!("{:?}", block), "{5: Block(2), 13: Rev(15)}"); | |
753 | } |
|
753 | } | |
754 |
|
754 | |||
755 | #[test] |
|
755 | #[test] | |
756 | fn test_raw_block() { |
|
756 | fn test_raw_block() { | |
757 | let mut raw = [255u8; 64]; |
|
757 | let mut raw = [255u8; 64]; | |
758 |
|
758 | |||
759 | let mut counter = 0; |
|
759 | let mut counter = 0; | |
760 | for val in [0_i32, 15, -2, -1, -3].iter() { |
|
760 | for val in [0_i32, 15, -2, -1, -3].iter() { | |
761 | for byte in val.to_be_bytes().iter() { |
|
761 | for byte in val.to_be_bytes().iter() { | |
762 | raw[counter] = *byte; |
|
762 | raw[counter] = *byte; | |
763 | counter += 1; |
|
763 | counter += 1; | |
764 | } |
|
764 | } | |
765 | } |
|
765 | } | |
766 | let (block, _) = Block::from_bytes(&raw).unwrap(); |
|
766 | let (block, _) = Block::from_bytes(&raw).unwrap(); | |
767 | assert_eq!(block.get(0), Element::Block(0)); |
|
767 | assert_eq!(block.get(0), Element::Block(0)); | |
768 | assert_eq!(block.get(1), Element::Block(15)); |
|
768 | assert_eq!(block.get(1), Element::Block(15)); | |
769 | assert_eq!(block.get(3), Element::None); |
|
769 | assert_eq!(block.get(3), Element::None); | |
770 | assert_eq!(block.get(2), Element::Rev(0)); |
|
770 | assert_eq!(block.get(2), Element::Rev(0)); | |
771 | assert_eq!(block.get(4), Element::Rev(1)); |
|
771 | assert_eq!(block.get(4), Element::Rev(1)); | |
772 | } |
|
772 | } | |
773 |
|
773 | |||
774 | type TestIndex = HashMap<Revision, Node>; |
|
774 | type TestIndex = HashMap<Revision, Node>; | |
775 |
|
775 | |||
776 | impl RevlogIndex for TestIndex { |
|
776 | impl RevlogIndex for TestIndex { | |
777 | fn node(&self, rev: Revision) -> Option<&Node> { |
|
777 | fn node(&self, rev: Revision) -> Option<&Node> { | |
778 | self.get(&rev) |
|
778 | self.get(&rev) | |
779 | } |
|
779 | } | |
780 |
|
780 | |||
781 | fn len(&self) -> usize { |
|
781 | fn len(&self) -> usize { | |
782 | self.len() |
|
782 | self.len() | |
783 | } |
|
783 | } | |
784 | } |
|
784 | } | |
785 |
|
785 | |||
786 | /// Pad hexadecimal Node prefix with zeros on the right |
|
786 | /// Pad hexadecimal Node prefix with zeros on the right | |
787 | /// |
|
787 | /// | |
788 | /// This avoids having to repeatedly write very long hexadecimal |
|
788 | /// This avoids having to repeatedly write very long hexadecimal | |
789 | /// strings for test data, and brings actual hash size independency. |
|
789 | /// strings for test data, and brings actual hash size independency. | |
790 | #[cfg(test)] |
|
790 | #[cfg(test)] | |
791 | fn pad_node(hex: &str) -> Node { |
|
791 | fn pad_node(hex: &str) -> Node { | |
792 | Node::from_hex(&hex_pad_right(hex)).unwrap() |
|
792 | Node::from_hex(&hex_pad_right(hex)).unwrap() | |
793 | } |
|
793 | } | |
794 |
|
794 | |||
795 | /// Pad hexadecimal Node prefix with zeros on the right, then insert |
|
795 | /// Pad hexadecimal Node prefix with zeros on the right, then insert | |
796 | fn pad_insert(idx: &mut TestIndex, rev: Revision, hex: &str) { |
|
796 | fn pad_insert(idx: &mut TestIndex, rev: Revision, hex: &str) { | |
797 | idx.insert(rev, pad_node(hex)); |
|
797 | idx.insert(rev, pad_node(hex)); | |
798 | } |
|
798 | } | |
799 |
|
799 | |||
800 | fn sample_nodetree() -> NodeTree { |
|
800 | fn sample_nodetree() -> NodeTree { | |
801 | NodeTree::from(vec![ |
|
801 | NodeTree::from(vec![ | |
802 | block![0: Rev(9)], |
|
802 | block![0: Rev(9)], | |
803 | block![0: Rev(0), 1: Rev(9)], |
|
803 | block![0: Rev(0), 1: Rev(9)], | |
804 | block![0: Block(1), 1:Rev(1)], |
|
804 | block![0: Block(1), 1:Rev(1)], | |
805 | ]) |
|
805 | ]) | |
806 | } |
|
806 | } | |
807 |
|
807 | |||
808 | #[test] |
|
808 | #[test] | |
809 | fn test_nt_debug() { |
|
809 | fn test_nt_debug() { | |
810 | let nt = sample_nodetree(); |
|
810 | let nt = sample_nodetree(); | |
811 | assert_eq!( |
|
811 | assert_eq!( | |
812 | format!("{:?}", nt), |
|
812 | format!("{:?}", nt), | |
813 | "readonly: \ |
|
813 | "readonly: \ | |
814 | [{0: Rev(9)}, {0: Rev(0), 1: Rev(9)}, {0: Block(1), 1: Rev(1)}], \ |
|
814 | [{0: Rev(9)}, {0: Rev(0), 1: Rev(9)}, {0: Block(1), 1: Rev(1)}], \ | |
815 | growable: [], \ |
|
815 | growable: [], \ | |
816 | root: {0: Block(1), 1: Rev(1)}", |
|
816 | root: {0: Block(1), 1: Rev(1)}", | |
817 | ); |
|
817 | ); | |
818 | } |
|
818 | } | |
819 |
|
819 | |||
820 | #[test] |
|
820 | #[test] | |
821 | fn test_immutable_find_simplest() -> Result<(), NodeMapError> { |
|
821 | fn test_immutable_find_simplest() -> Result<(), NodeMapError> { | |
822 | let mut idx: TestIndex = HashMap::new(); |
|
822 | let mut idx: TestIndex = HashMap::new(); | |
823 | pad_insert(&mut idx, 1, "1234deadcafe"); |
|
823 | pad_insert(&mut idx, 1, "1234deadcafe"); | |
824 |
|
824 | |||
825 | let nt = NodeTree::from(vec![block! {1: Rev(1)}]); |
|
825 | let nt = NodeTree::from(vec![block! {1: Rev(1)}]); | |
826 | assert_eq!(nt.find_hex(&idx, "1")?, Some(1)); |
|
826 | assert_eq!(nt.find_hex(&idx, "1")?, Some(1)); | |
827 | assert_eq!(nt.find_hex(&idx, "12")?, Some(1)); |
|
827 | assert_eq!(nt.find_hex(&idx, "12")?, Some(1)); | |
828 | assert_eq!(nt.find_hex(&idx, "1234de")?, Some(1)); |
|
828 | assert_eq!(nt.find_hex(&idx, "1234de")?, Some(1)); | |
829 | assert_eq!(nt.find_hex(&idx, "1a")?, None); |
|
829 | assert_eq!(nt.find_hex(&idx, "1a")?, None); | |
830 | assert_eq!(nt.find_hex(&idx, "ab")?, None); |
|
830 | assert_eq!(nt.find_hex(&idx, "ab")?, None); | |
831 |
|
831 | |||
832 | // and with full binary Nodes |
|
832 | // and with full binary Nodes | |
833 | assert_eq!(nt.find_node(&idx, idx.get(&1).unwrap())?, Some(1)); |
|
833 | assert_eq!(nt.find_node(&idx, idx.get(&1).unwrap())?, Some(1)); | |
834 | let unknown = Node::from_hex(&hex_pad_right("3d")).unwrap(); |
|
834 | let unknown = Node::from_hex(&hex_pad_right("3d")).unwrap(); | |
835 | assert_eq!(nt.find_node(&idx, &unknown)?, None); |
|
835 | assert_eq!(nt.find_node(&idx, &unknown)?, None); | |
836 | Ok(()) |
|
836 | Ok(()) | |
837 | } |
|
837 | } | |
838 |
|
838 | |||
839 | #[test] |
|
839 | #[test] | |
840 | fn test_immutable_find_one_jump() { |
|
840 | fn test_immutable_find_one_jump() { | |
841 | let mut idx = TestIndex::new(); |
|
841 | let mut idx = TestIndex::new(); | |
842 | pad_insert(&mut idx, 9, "012"); |
|
842 | pad_insert(&mut idx, 9, "012"); | |
843 | pad_insert(&mut idx, 0, "00a"); |
|
843 | pad_insert(&mut idx, 0, "00a"); | |
844 |
|
844 | |||
845 | let nt = sample_nodetree(); |
|
845 | let nt = sample_nodetree(); | |
846 |
|
846 | |||
847 | assert_eq!(nt.find_hex(&idx, "0"), Err(MultipleResults)); |
|
847 | assert_eq!(nt.find_hex(&idx, "0"), Err(MultipleResults)); | |
848 | assert_eq!(nt.find_hex(&idx, "01"), Ok(Some(9))); |
|
848 | assert_eq!(nt.find_hex(&idx, "01"), Ok(Some(9))); | |
849 | assert_eq!(nt.find_hex(&idx, "00"), Err(MultipleResults)); |
|
849 | assert_eq!(nt.find_hex(&idx, "00"), Err(MultipleResults)); | |
850 | assert_eq!(nt.find_hex(&idx, "00a"), Ok(Some(0))); |
|
850 | assert_eq!(nt.find_hex(&idx, "00a"), Ok(Some(0))); | |
851 | assert_eq!(nt.unique_prefix_len_hex(&idx, "00a"), Ok(Some(3))); |
|
851 | assert_eq!(nt.unique_prefix_len_hex(&idx, "00a"), Ok(Some(3))); | |
852 | assert_eq!(nt.find_hex(&idx, "000"), Ok(Some(NULL_REVISION))); |
|
852 | assert_eq!(nt.find_hex(&idx, "000"), Ok(Some(NULL_REVISION))); | |
853 | } |
|
853 | } | |
854 |
|
854 | |||
855 | #[test] |
|
855 | #[test] | |
856 | fn test_mutated_find() -> Result<(), NodeMapError> { |
|
856 | fn test_mutated_find() -> Result<(), NodeMapError> { | |
857 | let mut idx = TestIndex::new(); |
|
857 | let mut idx = TestIndex::new(); | |
858 | pad_insert(&mut idx, 9, "012"); |
|
858 | pad_insert(&mut idx, 9, "012"); | |
859 | pad_insert(&mut idx, 0, "00a"); |
|
859 | pad_insert(&mut idx, 0, "00a"); | |
860 | pad_insert(&mut idx, 2, "cafe"); |
|
860 | pad_insert(&mut idx, 2, "cafe"); | |
861 | pad_insert(&mut idx, 3, "15"); |
|
861 | pad_insert(&mut idx, 3, "15"); | |
862 | pad_insert(&mut idx, 1, "10"); |
|
862 | pad_insert(&mut idx, 1, "10"); | |
863 |
|
863 | |||
864 | let nt = NodeTree { |
|
864 | let nt = NodeTree { | |
865 | readonly: sample_nodetree().readonly, |
|
865 | readonly: sample_nodetree().readonly, | |
866 | growable: vec![block![0: Rev(1), 5: Rev(3)]], |
|
866 | growable: vec![block![0: Rev(1), 5: Rev(3)]], | |
867 | root: block![0: Block(1), 1:Block(3), 12: Rev(2)], |
|
867 | root: block![0: Block(1), 1:Block(3), 12: Rev(2)], | |
868 | masked_inner_blocks: 1, |
|
868 | masked_inner_blocks: 1, | |
869 | }; |
|
869 | }; | |
870 | assert_eq!(nt.find_hex(&idx, "10")?, Some(1)); |
|
870 | assert_eq!(nt.find_hex(&idx, "10")?, Some(1)); | |
871 | assert_eq!(nt.find_hex(&idx, "c")?, Some(2)); |
|
871 | assert_eq!(nt.find_hex(&idx, "c")?, Some(2)); | |
872 | assert_eq!(nt.unique_prefix_len_hex(&idx, "c")?, Some(1)); |
|
872 | assert_eq!(nt.unique_prefix_len_hex(&idx, "c")?, Some(1)); | |
873 | assert_eq!(nt.find_hex(&idx, "00"), Err(MultipleResults)); |
|
873 | assert_eq!(nt.find_hex(&idx, "00"), Err(MultipleResults)); | |
874 | assert_eq!(nt.find_hex(&idx, "000")?, Some(NULL_REVISION)); |
|
874 | assert_eq!(nt.find_hex(&idx, "000")?, Some(NULL_REVISION)); | |
875 | assert_eq!(nt.unique_prefix_len_hex(&idx, "000")?, Some(3)); |
|
875 | assert_eq!(nt.unique_prefix_len_hex(&idx, "000")?, Some(3)); | |
876 | assert_eq!(nt.find_hex(&idx, "01")?, Some(9)); |
|
876 | assert_eq!(nt.find_hex(&idx, "01")?, Some(9)); | |
877 | assert_eq!(nt.masked_readonly_blocks(), 2); |
|
877 | assert_eq!(nt.masked_readonly_blocks(), 2); | |
878 | Ok(()) |
|
878 | Ok(()) | |
879 | } |
|
879 | } | |
880 |
|
880 | |||
881 | struct TestNtIndex { |
|
881 | struct TestNtIndex { | |
882 | index: TestIndex, |
|
882 | index: TestIndex, | |
883 | nt: NodeTree, |
|
883 | nt: NodeTree, | |
884 | } |
|
884 | } | |
885 |
|
885 | |||
886 | impl TestNtIndex { |
|
886 | impl TestNtIndex { | |
887 | fn new() -> Self { |
|
887 | fn new() -> Self { | |
888 | TestNtIndex { |
|
888 | TestNtIndex { | |
889 | index: HashMap::new(), |
|
889 | index: HashMap::new(), | |
890 | nt: NodeTree::default(), |
|
890 | nt: NodeTree::default(), | |
891 | } |
|
891 | } | |
892 | } |
|
892 | } | |
893 |
|
893 | |||
894 | fn insert( |
|
894 | fn insert( | |
895 | &mut self, |
|
895 | &mut self, | |
896 | rev: Revision, |
|
896 | rev: Revision, | |
897 | hex: &str, |
|
897 | hex: &str, | |
898 | ) -> Result<(), NodeMapError> { |
|
898 | ) -> Result<(), NodeMapError> { | |
899 | let node = pad_node(hex); |
|
899 | let node = pad_node(hex); | |
900 | self.index.insert(rev, node.clone()); |
|
900 | self.index.insert(rev, node.clone()); | |
901 | self.nt.insert(&self.index, &node, rev)?; |
|
901 | self.nt.insert(&self.index, &node, rev)?; | |
902 | Ok(()) |
|
902 | Ok(()) | |
903 | } |
|
903 | } | |
904 |
|
904 | |||
905 | fn find_hex( |
|
905 | fn find_hex( | |
906 | &self, |
|
906 | &self, | |
907 | prefix: &str, |
|
907 | prefix: &str, | |
908 | ) -> Result<Option<Revision>, NodeMapError> { |
|
908 | ) -> Result<Option<Revision>, NodeMapError> { | |
909 | self.nt.find_hex(&self.index, prefix) |
|
909 | self.nt.find_hex(&self.index, prefix) | |
910 | } |
|
910 | } | |
911 |
|
911 | |||
912 | fn unique_prefix_len_hex( |
|
912 | fn unique_prefix_len_hex( | |
913 | &self, |
|
913 | &self, | |
914 | prefix: &str, |
|
914 | prefix: &str, | |
915 | ) -> Result<Option<usize>, NodeMapError> { |
|
915 | ) -> Result<Option<usize>, NodeMapError> { | |
916 | self.nt.unique_prefix_len_hex(&self.index, prefix) |
|
916 | self.nt.unique_prefix_len_hex(&self.index, prefix) | |
917 | } |
|
917 | } | |
918 |
|
918 | |||
919 | /// Drain `added` and restart a new one |
|
919 | /// Drain `added` and restart a new one | |
920 | fn commit(self) -> Self { |
|
920 | fn commit(self) -> Self { | |
921 | let mut as_vec: Vec<Block> = |
|
921 | let mut as_vec: Vec<Block> = | |
922 | self.nt.readonly.iter().map(|block| block.clone()).collect(); |
|
922 | self.nt.readonly.iter().map(|block| block.clone()).collect(); | |
923 | as_vec.extend(self.nt.growable); |
|
923 | as_vec.extend(self.nt.growable); | |
924 | as_vec.push(self.nt.root); |
|
924 | as_vec.push(self.nt.root); | |
925 |
|
925 | |||
926 | Self { |
|
926 | Self { | |
927 | index: self.index, |
|
927 | index: self.index, | |
928 | nt: NodeTree::from(as_vec).into(), |
|
928 | nt: NodeTree::from(as_vec).into(), | |
929 | } |
|
929 | } | |
930 | } |
|
930 | } | |
931 | } |
|
931 | } | |
932 |
|
932 | |||
933 | #[test] |
|
933 | #[test] | |
934 | fn test_insert_full_mutable() -> Result<(), NodeMapError> { |
|
934 | fn test_insert_full_mutable() -> Result<(), NodeMapError> { | |
935 | let mut idx = TestNtIndex::new(); |
|
935 | let mut idx = TestNtIndex::new(); | |
936 | idx.insert(0, "1234")?; |
|
936 | idx.insert(0, "1234")?; | |
937 | assert_eq!(idx.find_hex("1")?, Some(0)); |
|
937 | assert_eq!(idx.find_hex("1")?, Some(0)); | |
938 | assert_eq!(idx.find_hex("12")?, Some(0)); |
|
938 | assert_eq!(idx.find_hex("12")?, Some(0)); | |
939 |
|
939 | |||
940 | // let's trigger a simple split |
|
940 | // let's trigger a simple split | |
941 | idx.insert(1, "1a34")?; |
|
941 | idx.insert(1, "1a34")?; | |
942 | assert_eq!(idx.nt.growable.len(), 1); |
|
942 | assert_eq!(idx.nt.growable.len(), 1); | |
943 | assert_eq!(idx.find_hex("12")?, Some(0)); |
|
943 | assert_eq!(idx.find_hex("12")?, Some(0)); | |
944 | assert_eq!(idx.find_hex("1a")?, Some(1)); |
|
944 | assert_eq!(idx.find_hex("1a")?, Some(1)); | |
945 |
|
945 | |||
946 | // reinserting is a no_op |
|
946 | // reinserting is a no_op | |
947 | idx.insert(1, "1a34")?; |
|
947 | idx.insert(1, "1a34")?; | |
948 | assert_eq!(idx.nt.growable.len(), 1); |
|
948 | assert_eq!(idx.nt.growable.len(), 1); | |
949 | assert_eq!(idx.find_hex("12")?, Some(0)); |
|
949 | assert_eq!(idx.find_hex("12")?, Some(0)); | |
950 | assert_eq!(idx.find_hex("1a")?, Some(1)); |
|
950 | assert_eq!(idx.find_hex("1a")?, Some(1)); | |
951 |
|
951 | |||
952 | idx.insert(2, "1a01")?; |
|
952 | idx.insert(2, "1a01")?; | |
953 | assert_eq!(idx.nt.growable.len(), 2); |
|
953 | assert_eq!(idx.nt.growable.len(), 2); | |
954 | assert_eq!(idx.find_hex("1a"), Err(NodeMapError::MultipleResults)); |
|
954 | assert_eq!(idx.find_hex("1a"), Err(NodeMapError::MultipleResults)); | |
955 | assert_eq!(idx.find_hex("12")?, Some(0)); |
|
955 | assert_eq!(idx.find_hex("12")?, Some(0)); | |
956 | assert_eq!(idx.find_hex("1a3")?, Some(1)); |
|
956 | assert_eq!(idx.find_hex("1a3")?, Some(1)); | |
957 | assert_eq!(idx.find_hex("1a0")?, Some(2)); |
|
957 | assert_eq!(idx.find_hex("1a0")?, Some(2)); | |
958 | assert_eq!(idx.find_hex("1a12")?, None); |
|
958 | assert_eq!(idx.find_hex("1a12")?, None); | |
959 |
|
959 | |||
960 | // now let's make it split and create more than one additional block |
|
960 | // now let's make it split and create more than one additional block | |
961 | idx.insert(3, "1a345")?; |
|
961 | idx.insert(3, "1a345")?; | |
962 | assert_eq!(idx.nt.growable.len(), 4); |
|
962 | assert_eq!(idx.nt.growable.len(), 4); | |
963 | assert_eq!(idx.find_hex("1a340")?, Some(1)); |
|
963 | assert_eq!(idx.find_hex("1a340")?, Some(1)); | |
964 | assert_eq!(idx.find_hex("1a345")?, Some(3)); |
|
964 | assert_eq!(idx.find_hex("1a345")?, Some(3)); | |
965 | assert_eq!(idx.find_hex("1a341")?, None); |
|
965 | assert_eq!(idx.find_hex("1a341")?, None); | |
966 |
|
966 | |||
967 | // there's no readonly block to mask |
|
967 | // there's no readonly block to mask | |
968 | assert_eq!(idx.nt.masked_readonly_blocks(), 0); |
|
968 | assert_eq!(idx.nt.masked_readonly_blocks(), 0); | |
969 | Ok(()) |
|
969 | Ok(()) | |
970 | } |
|
970 | } | |
971 |
|
971 | |||
972 | #[test] |
|
972 | #[test] | |
973 | fn test_unique_prefix_len_zero_prefix() { |
|
973 | fn test_unique_prefix_len_zero_prefix() { | |
974 | let mut idx = TestNtIndex::new(); |
|
974 | let mut idx = TestNtIndex::new(); | |
975 | idx.insert(0, "00000abcd").unwrap(); |
|
975 | idx.insert(0, "00000abcd").unwrap(); | |
976 |
|
976 | |||
977 | assert_eq!(idx.find_hex("000"), Err(NodeMapError::MultipleResults)); |
|
977 | assert_eq!(idx.find_hex("000"), Err(NodeMapError::MultipleResults)); | |
978 | // in the nodetree proper, this will be found at the first nybble |
|
978 | // in the nodetree proper, this will be found at the first nybble | |
979 | // yet the correct answer for unique_prefix_len is not 1, nor 1+1, |
|
979 | // yet the correct answer for unique_prefix_len is not 1, nor 1+1, | |
980 | // but the first difference with `NULL_NODE` |
|
980 | // but the first difference with `NULL_NODE` | |
981 | assert_eq!(idx.unique_prefix_len_hex("00000a"), Ok(Some(6))); |
|
981 | assert_eq!(idx.unique_prefix_len_hex("00000a"), Ok(Some(6))); | |
982 | assert_eq!(idx.unique_prefix_len_hex("00000ab"), Ok(Some(6))); |
|
982 | assert_eq!(idx.unique_prefix_len_hex("00000ab"), Ok(Some(6))); | |
983 |
|
983 | |||
984 | // same with odd result |
|
984 | // same with odd result | |
985 | idx.insert(1, "00123").unwrap(); |
|
985 | idx.insert(1, "00123").unwrap(); | |
986 | assert_eq!(idx.unique_prefix_len_hex("001"), Ok(Some(3))); |
|
986 | assert_eq!(idx.unique_prefix_len_hex("001"), Ok(Some(3))); | |
987 | assert_eq!(idx.unique_prefix_len_hex("0012"), Ok(Some(3))); |
|
987 | assert_eq!(idx.unique_prefix_len_hex("0012"), Ok(Some(3))); | |
988 |
|
988 | |||
989 | // these are unchanged of course |
|
989 | // these are unchanged of course | |
990 | assert_eq!(idx.unique_prefix_len_hex("00000a"), Ok(Some(6))); |
|
990 | assert_eq!(idx.unique_prefix_len_hex("00000a"), Ok(Some(6))); | |
991 | assert_eq!(idx.unique_prefix_len_hex("00000ab"), Ok(Some(6))); |
|
991 | assert_eq!(idx.unique_prefix_len_hex("00000ab"), Ok(Some(6))); | |
992 | } |
|
992 | } | |
993 |
|
993 | |||
994 | #[test] |
|
994 | #[test] | |
995 | fn test_insert_extreme_splitting() -> Result<(), NodeMapError> { |
|
995 | fn test_insert_extreme_splitting() -> Result<(), NodeMapError> { | |
996 | // check that the splitting loop is long enough |
|
996 | // check that the splitting loop is long enough | |
997 | let mut nt_idx = TestNtIndex::new(); |
|
997 | let mut nt_idx = TestNtIndex::new(); | |
998 | let nt = &mut nt_idx.nt; |
|
998 | let nt = &mut nt_idx.nt; | |
999 | let idx = &mut nt_idx.index; |
|
999 | let idx = &mut nt_idx.index; | |
1000 |
|
1000 | |||
1001 | let node0_hex = hex_pad_right("444444"); |
|
1001 | let node0_hex = hex_pad_right("444444"); | |
1002 | let mut node1_hex = hex_pad_right("444444").clone(); |
|
1002 | let mut node1_hex = hex_pad_right("444444").clone(); | |
1003 | node1_hex.pop(); |
|
1003 | node1_hex.pop(); | |
1004 | node1_hex.push('5'); |
|
1004 | node1_hex.push('5'); | |
1005 | let node0 = Node::from_hex(&node0_hex).unwrap(); |
|
1005 | let node0 = Node::from_hex(&node0_hex).unwrap(); | |
1006 | let node1 = Node::from_hex(&node1_hex).unwrap(); |
|
1006 | let node1 = Node::from_hex(&node1_hex).unwrap(); | |
1007 |
|
1007 | |||
1008 | idx.insert(0, node0.clone()); |
|
1008 | idx.insert(0, node0.clone()); | |
1009 | nt.insert(idx, &node0, 0)?; |
|
1009 | nt.insert(idx, &node0, 0)?; | |
1010 | idx.insert(1, node1.clone()); |
|
1010 | idx.insert(1, node1.clone()); | |
1011 | nt.insert(idx, &node1, 1)?; |
|
1011 | nt.insert(idx, &node1, 1)?; | |
1012 |
|
1012 | |||
1013 | assert_eq!(nt.find_bin(idx, (&node0).into())?, Some(0)); |
|
1013 | assert_eq!(nt.find_bin(idx, (&node0).into())?, Some(0)); | |
1014 | assert_eq!(nt.find_bin(idx, (&node1).into())?, Some(1)); |
|
1014 | assert_eq!(nt.find_bin(idx, (&node1).into())?, Some(1)); | |
1015 | Ok(()) |
|
1015 | Ok(()) | |
1016 | } |
|
1016 | } | |
1017 |
|
1017 | |||
1018 | #[test] |
|
1018 | #[test] | |
1019 | fn test_insert_partly_immutable() -> Result<(), NodeMapError> { |
|
1019 | fn test_insert_partly_immutable() -> Result<(), NodeMapError> { | |
1020 | let mut idx = TestNtIndex::new(); |
|
1020 | let mut idx = TestNtIndex::new(); | |
1021 | idx.insert(0, "1234")?; |
|
1021 | idx.insert(0, "1234")?; | |
1022 | idx.insert(1, "1235")?; |
|
1022 | idx.insert(1, "1235")?; | |
1023 | idx.insert(2, "131")?; |
|
1023 | idx.insert(2, "131")?; | |
1024 | idx.insert(3, "cafe")?; |
|
1024 | idx.insert(3, "cafe")?; | |
1025 | let mut idx = idx.commit(); |
|
1025 | let mut idx = idx.commit(); | |
1026 | assert_eq!(idx.find_hex("1234")?, Some(0)); |
|
1026 | assert_eq!(idx.find_hex("1234")?, Some(0)); | |
1027 | assert_eq!(idx.find_hex("1235")?, Some(1)); |
|
1027 | assert_eq!(idx.find_hex("1235")?, Some(1)); | |
1028 | assert_eq!(idx.find_hex("131")?, Some(2)); |
|
1028 | assert_eq!(idx.find_hex("131")?, Some(2)); | |
1029 | assert_eq!(idx.find_hex("cafe")?, Some(3)); |
|
1029 | assert_eq!(idx.find_hex("cafe")?, Some(3)); | |
1030 | // we did not add anything since init from readonly |
|
1030 | // we did not add anything since init from readonly | |
1031 | assert_eq!(idx.nt.masked_readonly_blocks(), 0); |
|
1031 | assert_eq!(idx.nt.masked_readonly_blocks(), 0); | |
1032 |
|
1032 | |||
1033 | idx.insert(4, "123A")?; |
|
1033 | idx.insert(4, "123A")?; | |
1034 | assert_eq!(idx.find_hex("1234")?, Some(0)); |
|
1034 | assert_eq!(idx.find_hex("1234")?, Some(0)); | |
1035 | assert_eq!(idx.find_hex("1235")?, Some(1)); |
|
1035 | assert_eq!(idx.find_hex("1235")?, Some(1)); | |
1036 | assert_eq!(idx.find_hex("131")?, Some(2)); |
|
1036 | assert_eq!(idx.find_hex("131")?, Some(2)); | |
1037 | assert_eq!(idx.find_hex("cafe")?, Some(3)); |
|
1037 | assert_eq!(idx.find_hex("cafe")?, Some(3)); | |
1038 | assert_eq!(idx.find_hex("123A")?, Some(4)); |
|
1038 | assert_eq!(idx.find_hex("123A")?, Some(4)); | |
1039 | // we masked blocks for all prefixes of "123", including the root |
|
1039 | // we masked blocks for all prefixes of "123", including the root | |
1040 | assert_eq!(idx.nt.masked_readonly_blocks(), 4); |
|
1040 | assert_eq!(idx.nt.masked_readonly_blocks(), 4); | |
1041 |
|
1041 | |||
1042 | eprintln!("{:?}", idx.nt); |
|
1042 | eprintln!("{:?}", idx.nt); | |
1043 | idx.insert(5, "c0")?; |
|
1043 | idx.insert(5, "c0")?; | |
1044 | assert_eq!(idx.find_hex("cafe")?, Some(3)); |
|
1044 | assert_eq!(idx.find_hex("cafe")?, Some(3)); | |
1045 | assert_eq!(idx.find_hex("c0")?, Some(5)); |
|
1045 | assert_eq!(idx.find_hex("c0")?, Some(5)); | |
1046 | assert_eq!(idx.find_hex("c1")?, None); |
|
1046 | assert_eq!(idx.find_hex("c1")?, None); | |
1047 | assert_eq!(idx.find_hex("1234")?, Some(0)); |
|
1047 | assert_eq!(idx.find_hex("1234")?, Some(0)); | |
1048 | // inserting "c0" is just splitting the 'c' slot of the mutable root, |
|
1048 | // inserting "c0" is just splitting the 'c' slot of the mutable root, | |
1049 | // it doesn't mask anything |
|
1049 | // it doesn't mask anything | |
1050 | assert_eq!(idx.nt.masked_readonly_blocks(), 4); |
|
1050 | assert_eq!(idx.nt.masked_readonly_blocks(), 4); | |
1051 |
|
1051 | |||
1052 | Ok(()) |
|
1052 | Ok(()) | |
1053 | } |
|
1053 | } | |
1054 |
|
1054 | |||
1055 | #[test] |
|
1055 | #[test] | |
1056 | fn test_invalidate_all() -> Result<(), NodeMapError> { |
|
1056 | fn test_invalidate_all() -> Result<(), NodeMapError> { | |
1057 | let mut idx = TestNtIndex::new(); |
|
1057 | let mut idx = TestNtIndex::new(); | |
1058 | idx.insert(0, "1234")?; |
|
1058 | idx.insert(0, "1234")?; | |
1059 | idx.insert(1, "1235")?; |
|
1059 | idx.insert(1, "1235")?; | |
1060 | idx.insert(2, "131")?; |
|
1060 | idx.insert(2, "131")?; | |
1061 | idx.insert(3, "cafe")?; |
|
1061 | idx.insert(3, "cafe")?; | |
1062 | let mut idx = idx.commit(); |
|
1062 | let mut idx = idx.commit(); | |
1063 |
|
1063 | |||
1064 | idx.nt.invalidate_all(); |
|
1064 | idx.nt.invalidate_all(); | |
1065 |
|
1065 | |||
1066 | assert_eq!(idx.find_hex("1234")?, None); |
|
1066 | assert_eq!(idx.find_hex("1234")?, None); | |
1067 | assert_eq!(idx.find_hex("1235")?, None); |
|
1067 | assert_eq!(idx.find_hex("1235")?, None); | |
1068 | assert_eq!(idx.find_hex("131")?, None); |
|
1068 | assert_eq!(idx.find_hex("131")?, None); | |
1069 | assert_eq!(idx.find_hex("cafe")?, None); |
|
1069 | assert_eq!(idx.find_hex("cafe")?, None); | |
1070 | // all the readonly blocks have been masked, this is the |
|
1070 | // all the readonly blocks have been masked, this is the | |
1071 | // conventional expected response |
|
1071 | // conventional expected response | |
1072 | assert_eq!(idx.nt.masked_readonly_blocks(), idx.nt.readonly.len() + 1); |
|
1072 | assert_eq!(idx.nt.masked_readonly_blocks(), idx.nt.readonly.len() + 1); | |
1073 | Ok(()) |
|
1073 | Ok(()) | |
1074 | } |
|
1074 | } | |
1075 |
|
1075 | |||
1076 | #[test] |
|
1076 | #[test] | |
1077 | fn test_into_added_empty() { |
|
1077 | fn test_into_added_empty() { | |
1078 | assert!(sample_nodetree().into_readonly_and_added().1.is_empty()); |
|
1078 | assert!(sample_nodetree().into_readonly_and_added().1.is_empty()); | |
1079 | assert!(sample_nodetree() |
|
1079 | assert!(sample_nodetree() | |
1080 | .into_readonly_and_added_bytes() |
|
1080 | .into_readonly_and_added_bytes() | |
1081 | .1 |
|
1081 | .1 | |
1082 | .is_empty()); |
|
1082 | .is_empty()); | |
1083 | } |
|
1083 | } | |
1084 |
|
1084 | |||
1085 | #[test] |
|
1085 | #[test] | |
1086 | fn test_into_added_bytes() -> Result<(), NodeMapError> { |
|
1086 | fn test_into_added_bytes() -> Result<(), NodeMapError> { | |
1087 | let mut idx = TestNtIndex::new(); |
|
1087 | let mut idx = TestNtIndex::new(); | |
1088 | idx.insert(0, "1234")?; |
|
1088 | idx.insert(0, "1234")?; | |
1089 | let mut idx = idx.commit(); |
|
1089 | let mut idx = idx.commit(); | |
1090 | idx.insert(4, "cafe")?; |
|
1090 | idx.insert(4, "cafe")?; | |
1091 | let (_, bytes) = idx.nt.into_readonly_and_added_bytes(); |
|
1091 | let (_, bytes) = idx.nt.into_readonly_and_added_bytes(); | |
1092 |
|
1092 | |||
1093 | // only the root block has been changed |
|
1093 | // only the root block has been changed | |
1094 | assert_eq!(bytes.len(), size_of::<Block>()); |
|
1094 | assert_eq!(bytes.len(), size_of::<Block>()); | |
1095 | // big endian for -2 |
|
1095 | // big endian for -2 | |
1096 | assert_eq!(&bytes[4..2 * 4], [255, 255, 255, 254]); |
|
1096 | assert_eq!(&bytes[4..2 * 4], [255, 255, 255, 254]); | |
1097 | // big endian for -6 |
|
1097 | // big endian for -6 | |
1098 | assert_eq!(&bytes[12 * 4..13 * 4], [255, 255, 255, 250]); |
|
1098 | assert_eq!(&bytes[12 * 4..13 * 4], [255, 255, 255, 250]); | |
1099 | Ok(()) |
|
1099 | Ok(()) | |
1100 | } |
|
1100 | } | |
1101 | } |
|
1101 | } |
@@ -1,496 +1,491 b'' | |||||
1 | // revlog.rs |
|
1 | // revlog.rs | |
2 | // |
|
2 | // | |
3 | // Copyright 2019-2020 Georges Racinet <georges.racinet@octobus.net> |
|
3 | // Copyright 2019-2020 Georges Racinet <georges.racinet@octobus.net> | |
4 | // |
|
4 | // | |
5 | // This software may be used and distributed according to the terms of the |
|
5 | // This software may be used and distributed according to the terms of the | |
6 | // GNU General Public License version 2 or any later version. |
|
6 | // GNU General Public License version 2 or any later version. | |
7 |
|
7 | |||
8 | use crate::{ |
|
8 | use crate::{ | |
9 | cindex, |
|
9 | cindex, | |
10 | utils::{node_from_py_bytes, node_from_py_object}, |
|
10 | utils::{node_from_py_bytes, node_from_py_object}, | |
11 | }; |
|
11 | }; | |
12 | use cpython::{ |
|
12 | use cpython::{ | |
13 | buffer::{Element, PyBuffer}, |
|
13 | buffer::{Element, PyBuffer}, | |
14 | exc::{IndexError, ValueError}, |
|
14 | exc::{IndexError, ValueError}, | |
15 | ObjectProtocol, PyBytes, PyClone, PyDict, PyErr, PyModule, PyObject, |
|
15 | ObjectProtocol, PyBytes, PyClone, PyDict, PyErr, PyModule, PyObject, | |
16 | PyResult, PyString, PyTuple, Python, PythonObject, ToPyObject, |
|
16 | PyResult, PyString, PyTuple, Python, PythonObject, ToPyObject, | |
17 | }; |
|
17 | }; | |
18 | use hg::{ |
|
18 | use hg::{ | |
19 | nodemap::{Block, NodeMapError, NodeTree}, |
|
19 | nodemap::{Block, NodeMapError, NodeTree}, | |
20 | revlog::{nodemap::NodeMap, RevlogIndex}, |
|
20 | revlog::{nodemap::NodeMap, RevlogIndex}, | |
21 |
|
|
21 | Revision, | |
22 | }; |
|
22 | }; | |
23 | use std::cell::RefCell; |
|
23 | use std::cell::RefCell; | |
24 |
|
24 | |||
25 | /// Return a Struct implementing the Graph trait |
|
25 | /// Return a Struct implementing the Graph trait | |
26 | pub(crate) fn pyindex_to_graph( |
|
26 | pub(crate) fn pyindex_to_graph( | |
27 | py: Python, |
|
27 | py: Python, | |
28 | index: PyObject, |
|
28 | index: PyObject, | |
29 | ) -> PyResult<cindex::Index> { |
|
29 | ) -> PyResult<cindex::Index> { | |
30 | match index.extract::<MixedIndex>(py) { |
|
30 | match index.extract::<MixedIndex>(py) { | |
31 | Ok(midx) => Ok(midx.clone_cindex(py)), |
|
31 | Ok(midx) => Ok(midx.clone_cindex(py)), | |
32 | Err(_) => cindex::Index::new(py, index), |
|
32 | Err(_) => cindex::Index::new(py, index), | |
33 | } |
|
33 | } | |
34 | } |
|
34 | } | |
35 |
|
35 | |||
36 | py_class!(pub class MixedIndex |py| { |
|
36 | py_class!(pub class MixedIndex |py| { | |
37 | data cindex: RefCell<cindex::Index>; |
|
37 | data cindex: RefCell<cindex::Index>; | |
38 | data nt: RefCell<Option<NodeTree>>; |
|
38 | data nt: RefCell<Option<NodeTree>>; | |
39 | data docket: RefCell<Option<PyObject>>; |
|
39 | data docket: RefCell<Option<PyObject>>; | |
40 | // Holds a reference to the mmap'ed persistent nodemap data |
|
40 | // Holds a reference to the mmap'ed persistent nodemap data | |
41 | data mmap: RefCell<Option<PyBuffer>>; |
|
41 | data mmap: RefCell<Option<PyBuffer>>; | |
42 |
|
42 | |||
43 | def __new__(_cls, cindex: PyObject) -> PyResult<MixedIndex> { |
|
43 | def __new__(_cls, cindex: PyObject) -> PyResult<MixedIndex> { | |
44 | Self::new(py, cindex) |
|
44 | Self::new(py, cindex) | |
45 | } |
|
45 | } | |
46 |
|
46 | |||
47 | /// Compatibility layer used for Python consumers needing access to the C index |
|
47 | /// Compatibility layer used for Python consumers needing access to the C index | |
48 | /// |
|
48 | /// | |
49 | /// Only use case so far is `scmutil.shortesthexnodeidprefix`, |
|
49 | /// Only use case so far is `scmutil.shortesthexnodeidprefix`, | |
50 | /// that may need to build a custom `nodetree`, based on a specified revset. |
|
50 | /// that may need to build a custom `nodetree`, based on a specified revset. | |
51 | /// With a Rust implementation of the nodemap, we will be able to get rid of |
|
51 | /// With a Rust implementation of the nodemap, we will be able to get rid of | |
52 | /// this, by exposing our own standalone nodemap class, |
|
52 | /// this, by exposing our own standalone nodemap class, | |
53 | /// ready to accept `MixedIndex`. |
|
53 | /// ready to accept `MixedIndex`. | |
54 | def get_cindex(&self) -> PyResult<PyObject> { |
|
54 | def get_cindex(&self) -> PyResult<PyObject> { | |
55 | Ok(self.cindex(py).borrow().inner().clone_ref(py)) |
|
55 | Ok(self.cindex(py).borrow().inner().clone_ref(py)) | |
56 | } |
|
56 | } | |
57 |
|
57 | |||
58 | // Index API involving nodemap, as defined in mercurial/pure/parsers.py |
|
58 | // Index API involving nodemap, as defined in mercurial/pure/parsers.py | |
59 |
|
59 | |||
60 | /// Return Revision if found, raises a bare `error.RevlogError` |
|
60 | /// Return Revision if found, raises a bare `error.RevlogError` | |
61 | /// in case of ambiguity, same as C version does |
|
61 | /// in case of ambiguity, same as C version does | |
62 | def get_rev(&self, node: PyBytes) -> PyResult<Option<Revision>> { |
|
62 | def get_rev(&self, node: PyBytes) -> PyResult<Option<Revision>> { | |
63 | let opt = self.get_nodetree(py)?.borrow(); |
|
63 | let opt = self.get_nodetree(py)?.borrow(); | |
64 | let nt = opt.as_ref().unwrap(); |
|
64 | let nt = opt.as_ref().unwrap(); | |
65 | let idx = &*self.cindex(py).borrow(); |
|
65 | let idx = &*self.cindex(py).borrow(); | |
66 | let node = node_from_py_bytes(py, &node)?; |
|
66 | let node = node_from_py_bytes(py, &node)?; | |
67 | nt.find_bin(idx, (&node).into()).map_err(|e| nodemap_error(py, e)) |
|
67 | nt.find_bin(idx, (&node).into()).map_err(|e| nodemap_error(py, e)) | |
68 | } |
|
68 | } | |
69 |
|
69 | |||
70 | /// same as `get_rev()` but raises a bare `error.RevlogError` if node |
|
70 | /// same as `get_rev()` but raises a bare `error.RevlogError` if node | |
71 | /// is not found. |
|
71 | /// is not found. | |
72 | /// |
|
72 | /// | |
73 | /// No need to repeat `node` in the exception, `mercurial/revlog.py` |
|
73 | /// No need to repeat `node` in the exception, `mercurial/revlog.py` | |
74 | /// will catch and rewrap with it |
|
74 | /// will catch and rewrap with it | |
75 | def rev(&self, node: PyBytes) -> PyResult<Revision> { |
|
75 | def rev(&self, node: PyBytes) -> PyResult<Revision> { | |
76 | self.get_rev(py, node)?.ok_or_else(|| revlog_error(py)) |
|
76 | self.get_rev(py, node)?.ok_or_else(|| revlog_error(py)) | |
77 | } |
|
77 | } | |
78 |
|
78 | |||
79 | /// return True if the node exist in the index |
|
79 | /// return True if the node exist in the index | |
80 | def has_node(&self, node: PyBytes) -> PyResult<bool> { |
|
80 | def has_node(&self, node: PyBytes) -> PyResult<bool> { | |
81 | self.get_rev(py, node).map(|opt| opt.is_some()) |
|
81 | self.get_rev(py, node).map(|opt| opt.is_some()) | |
82 | } |
|
82 | } | |
83 |
|
83 | |||
84 | /// find length of shortest hex nodeid of a binary ID |
|
84 | /// find length of shortest hex nodeid of a binary ID | |
85 | def shortest(&self, node: PyBytes) -> PyResult<usize> { |
|
85 | def shortest(&self, node: PyBytes) -> PyResult<usize> { | |
86 | let opt = self.get_nodetree(py)?.borrow(); |
|
86 | let opt = self.get_nodetree(py)?.borrow(); | |
87 | let nt = opt.as_ref().unwrap(); |
|
87 | let nt = opt.as_ref().unwrap(); | |
88 | let idx = &*self.cindex(py).borrow(); |
|
88 | let idx = &*self.cindex(py).borrow(); | |
89 | match nt.unique_prefix_len_node(idx, &node_from_py_bytes(py, &node)?) |
|
89 | match nt.unique_prefix_len_node(idx, &node_from_py_bytes(py, &node)?) | |
90 | { |
|
90 | { | |
91 | Ok(Some(l)) => Ok(l), |
|
91 | Ok(Some(l)) => Ok(l), | |
92 | Ok(None) => Err(revlog_error(py)), |
|
92 | Ok(None) => Err(revlog_error(py)), | |
93 | Err(e) => Err(nodemap_error(py, e)), |
|
93 | Err(e) => Err(nodemap_error(py, e)), | |
94 | } |
|
94 | } | |
95 | } |
|
95 | } | |
96 |
|
96 | |||
97 | def partialmatch(&self, node: PyObject) -> PyResult<Option<PyBytes>> { |
|
97 | def partialmatch(&self, node: PyObject) -> PyResult<Option<PyBytes>> { | |
98 | let opt = self.get_nodetree(py)?.borrow(); |
|
98 | let opt = self.get_nodetree(py)?.borrow(); | |
99 | let nt = opt.as_ref().unwrap(); |
|
99 | let nt = opt.as_ref().unwrap(); | |
100 | let idx = &*self.cindex(py).borrow(); |
|
100 | let idx = &*self.cindex(py).borrow(); | |
101 |
|
101 | |||
102 | let node_as_string = if cfg!(feature = "python3-sys") { |
|
102 | let node_as_string = if cfg!(feature = "python3-sys") { | |
103 | node.cast_as::<PyString>(py)?.to_string(py)?.to_string() |
|
103 | node.cast_as::<PyString>(py)?.to_string(py)?.to_string() | |
104 | } |
|
104 | } | |
105 | else { |
|
105 | else { | |
106 | let node = node.extract::<PyBytes>(py)?; |
|
106 | let node = node.extract::<PyBytes>(py)?; | |
107 | String::from_utf8_lossy(node.data(py)).to_string() |
|
107 | String::from_utf8_lossy(node.data(py)).to_string() | |
108 | }; |
|
108 | }; | |
109 |
|
109 | |||
110 | nt.find_hex(idx, &node_as_string) |
|
110 | nt.find_hex(idx, &node_as_string) | |
111 | // TODO make an inner API returning the node directly |
|
111 | // TODO make an inner API returning the node directly | |
112 | .map(|opt| opt.map( |
|
112 | .map(|opt| opt.map( | |
113 | |rev| PyBytes::new(py, idx.node(rev).unwrap().as_bytes()))) |
|
113 | |rev| PyBytes::new(py, idx.node(rev).unwrap().as_bytes()))) | |
114 | .map_err(|e| nodemap_error(py, e)) |
|
114 | .map_err(|e| nodemap_error(py, e)) | |
115 |
|
115 | |||
116 | } |
|
116 | } | |
117 |
|
117 | |||
118 | /// append an index entry |
|
118 | /// append an index entry | |
119 | def append(&self, tup: PyTuple) -> PyResult<PyObject> { |
|
119 | def append(&self, tup: PyTuple) -> PyResult<PyObject> { | |
120 | if tup.len(py) < 8 { |
|
120 | if tup.len(py) < 8 { | |
121 | // this is better than the panic promised by tup.get_item() |
|
121 | // this is better than the panic promised by tup.get_item() | |
122 | return Err( |
|
122 | return Err( | |
123 | PyErr::new::<IndexError, _>(py, "tuple index out of range")) |
|
123 | PyErr::new::<IndexError, _>(py, "tuple index out of range")) | |
124 | } |
|
124 | } | |
125 | let node_bytes = tup.get_item(py, 7).extract(py)?; |
|
125 | let node_bytes = tup.get_item(py, 7).extract(py)?; | |
126 | let node = node_from_py_object(py, &node_bytes)?; |
|
126 | let node = node_from_py_object(py, &node_bytes)?; | |
127 |
|
127 | |||
128 | let mut idx = self.cindex(py).borrow_mut(); |
|
128 | let mut idx = self.cindex(py).borrow_mut(); | |
129 | let rev = idx.len() as Revision; |
|
129 | let rev = idx.len() as Revision; | |
130 |
|
130 | |||
131 | idx.append(py, tup)?; |
|
131 | idx.append(py, tup)?; | |
132 | self.get_nodetree(py)?.borrow_mut().as_mut().unwrap() |
|
132 | self.get_nodetree(py)?.borrow_mut().as_mut().unwrap() | |
133 | .insert(&*idx, &node, rev) |
|
133 | .insert(&*idx, &node, rev) | |
134 | .map_err(|e| nodemap_error(py, e))?; |
|
134 | .map_err(|e| nodemap_error(py, e))?; | |
135 | Ok(py.None()) |
|
135 | Ok(py.None()) | |
136 | } |
|
136 | } | |
137 |
|
137 | |||
138 | def __delitem__(&self, key: PyObject) -> PyResult<()> { |
|
138 | def __delitem__(&self, key: PyObject) -> PyResult<()> { | |
139 | // __delitem__ is both for `del idx[r]` and `del idx[r1:r2]` |
|
139 | // __delitem__ is both for `del idx[r]` and `del idx[r1:r2]` | |
140 | self.cindex(py).borrow().inner().del_item(py, key)?; |
|
140 | self.cindex(py).borrow().inner().del_item(py, key)?; | |
141 | let mut opt = self.get_nodetree(py)?.borrow_mut(); |
|
141 | let mut opt = self.get_nodetree(py)?.borrow_mut(); | |
142 | let mut nt = opt.as_mut().unwrap(); |
|
142 | let mut nt = opt.as_mut().unwrap(); | |
143 | nt.invalidate_all(); |
|
143 | nt.invalidate_all(); | |
144 | self.fill_nodemap(py, &mut nt)?; |
|
144 | self.fill_nodemap(py, &mut nt)?; | |
145 | Ok(()) |
|
145 | Ok(()) | |
146 | } |
|
146 | } | |
147 |
|
147 | |||
148 | // |
|
148 | // | |
149 | // Reforwarded C index API |
|
149 | // Reforwarded C index API | |
150 | // |
|
150 | // | |
151 |
|
151 | |||
152 | // index_methods (tp_methods). Same ordering as in revlog.c |
|
152 | // index_methods (tp_methods). Same ordering as in revlog.c | |
153 |
|
153 | |||
154 | /// return the gca set of the given revs |
|
154 | /// return the gca set of the given revs | |
155 | def ancestors(&self, *args, **kw) -> PyResult<PyObject> { |
|
155 | def ancestors(&self, *args, **kw) -> PyResult<PyObject> { | |
156 | self.call_cindex(py, "ancestors", args, kw) |
|
156 | self.call_cindex(py, "ancestors", args, kw) | |
157 | } |
|
157 | } | |
158 |
|
158 | |||
159 | /// return the heads of the common ancestors of the given revs |
|
159 | /// return the heads of the common ancestors of the given revs | |
160 | def commonancestorsheads(&self, *args, **kw) -> PyResult<PyObject> { |
|
160 | def commonancestorsheads(&self, *args, **kw) -> PyResult<PyObject> { | |
161 | self.call_cindex(py, "commonancestorsheads", args, kw) |
|
161 | self.call_cindex(py, "commonancestorsheads", args, kw) | |
162 | } |
|
162 | } | |
163 |
|
163 | |||
164 | /// Clear the index caches and inner py_class data. |
|
164 | /// Clear the index caches and inner py_class data. | |
165 | /// It is Python's responsibility to call `update_nodemap_data` again. |
|
165 | /// It is Python's responsibility to call `update_nodemap_data` again. | |
166 | def clearcaches(&self, *args, **kw) -> PyResult<PyObject> { |
|
166 | def clearcaches(&self, *args, **kw) -> PyResult<PyObject> { | |
167 | self.nt(py).borrow_mut().take(); |
|
167 | self.nt(py).borrow_mut().take(); | |
168 | self.docket(py).borrow_mut().take(); |
|
168 | self.docket(py).borrow_mut().take(); | |
169 | self.mmap(py).borrow_mut().take(); |
|
169 | self.mmap(py).borrow_mut().take(); | |
170 | self.call_cindex(py, "clearcaches", args, kw) |
|
170 | self.call_cindex(py, "clearcaches", args, kw) | |
171 | } |
|
171 | } | |
172 |
|
172 | |||
173 | /// get an index entry |
|
173 | /// get an index entry | |
174 | def get(&self, *args, **kw) -> PyResult<PyObject> { |
|
174 | def get(&self, *args, **kw) -> PyResult<PyObject> { | |
175 | self.call_cindex(py, "get", args, kw) |
|
175 | self.call_cindex(py, "get", args, kw) | |
176 | } |
|
176 | } | |
177 |
|
177 | |||
178 | /// compute phases |
|
178 | /// compute phases | |
179 | def computephasesmapsets(&self, *args, **kw) -> PyResult<PyObject> { |
|
179 | def computephasesmapsets(&self, *args, **kw) -> PyResult<PyObject> { | |
180 | self.call_cindex(py, "computephasesmapsets", args, kw) |
|
180 | self.call_cindex(py, "computephasesmapsets", args, kw) | |
181 | } |
|
181 | } | |
182 |
|
182 | |||
183 | /// reachableroots |
|
183 | /// reachableroots | |
184 | def reachableroots2(&self, *args, **kw) -> PyResult<PyObject> { |
|
184 | def reachableroots2(&self, *args, **kw) -> PyResult<PyObject> { | |
185 | self.call_cindex(py, "reachableroots2", args, kw) |
|
185 | self.call_cindex(py, "reachableroots2", args, kw) | |
186 | } |
|
186 | } | |
187 |
|
187 | |||
188 | /// get head revisions |
|
188 | /// get head revisions | |
189 | def headrevs(&self, *args, **kw) -> PyResult<PyObject> { |
|
189 | def headrevs(&self, *args, **kw) -> PyResult<PyObject> { | |
190 | self.call_cindex(py, "headrevs", args, kw) |
|
190 | self.call_cindex(py, "headrevs", args, kw) | |
191 | } |
|
191 | } | |
192 |
|
192 | |||
193 | /// get filtered head revisions |
|
193 | /// get filtered head revisions | |
194 | def headrevsfiltered(&self, *args, **kw) -> PyResult<PyObject> { |
|
194 | def headrevsfiltered(&self, *args, **kw) -> PyResult<PyObject> { | |
195 | self.call_cindex(py, "headrevsfiltered", args, kw) |
|
195 | self.call_cindex(py, "headrevsfiltered", args, kw) | |
196 | } |
|
196 | } | |
197 |
|
197 | |||
198 | /// True if the object is a snapshot |
|
198 | /// True if the object is a snapshot | |
199 | def issnapshot(&self, *args, **kw) -> PyResult<PyObject> { |
|
199 | def issnapshot(&self, *args, **kw) -> PyResult<PyObject> { | |
200 | self.call_cindex(py, "issnapshot", args, kw) |
|
200 | self.call_cindex(py, "issnapshot", args, kw) | |
201 | } |
|
201 | } | |
202 |
|
202 | |||
203 | /// Gather snapshot data in a cache dict |
|
203 | /// Gather snapshot data in a cache dict | |
204 | def findsnapshots(&self, *args, **kw) -> PyResult<PyObject> { |
|
204 | def findsnapshots(&self, *args, **kw) -> PyResult<PyObject> { | |
205 | self.call_cindex(py, "findsnapshots", args, kw) |
|
205 | self.call_cindex(py, "findsnapshots", args, kw) | |
206 | } |
|
206 | } | |
207 |
|
207 | |||
208 | /// determine revisions with deltas to reconstruct fulltext |
|
208 | /// determine revisions with deltas to reconstruct fulltext | |
209 | def deltachain(&self, *args, **kw) -> PyResult<PyObject> { |
|
209 | def deltachain(&self, *args, **kw) -> PyResult<PyObject> { | |
210 | self.call_cindex(py, "deltachain", args, kw) |
|
210 | self.call_cindex(py, "deltachain", args, kw) | |
211 | } |
|
211 | } | |
212 |
|
212 | |||
213 | /// slice planned chunk read to reach a density threshold |
|
213 | /// slice planned chunk read to reach a density threshold | |
214 | def slicechunktodensity(&self, *args, **kw) -> PyResult<PyObject> { |
|
214 | def slicechunktodensity(&self, *args, **kw) -> PyResult<PyObject> { | |
215 | self.call_cindex(py, "slicechunktodensity", args, kw) |
|
215 | self.call_cindex(py, "slicechunktodensity", args, kw) | |
216 | } |
|
216 | } | |
217 |
|
217 | |||
218 | /// stats for the index |
|
218 | /// stats for the index | |
219 | def stats(&self, *args, **kw) -> PyResult<PyObject> { |
|
219 | def stats(&self, *args, **kw) -> PyResult<PyObject> { | |
220 | self.call_cindex(py, "stats", args, kw) |
|
220 | self.call_cindex(py, "stats", args, kw) | |
221 | } |
|
221 | } | |
222 |
|
222 | |||
223 | // index_sequence_methods and index_mapping_methods. |
|
223 | // index_sequence_methods and index_mapping_methods. | |
224 | // |
|
224 | // | |
225 | // Since we call back through the high level Python API, |
|
225 | // Since we call back through the high level Python API, | |
226 | // there's no point making a distinction between index_get |
|
226 | // there's no point making a distinction between index_get | |
227 | // and index_getitem. |
|
227 | // and index_getitem. | |
228 |
|
228 | |||
229 | def __len__(&self) -> PyResult<usize> { |
|
229 | def __len__(&self) -> PyResult<usize> { | |
230 | self.cindex(py).borrow().inner().len(py) |
|
230 | self.cindex(py).borrow().inner().len(py) | |
231 | } |
|
231 | } | |
232 |
|
232 | |||
233 | def __getitem__(&self, key: PyObject) -> PyResult<PyObject> { |
|
233 | def __getitem__(&self, key: PyObject) -> PyResult<PyObject> { | |
234 | // this conversion seems needless, but that's actually because |
|
234 | // this conversion seems needless, but that's actually because | |
235 | // `index_getitem` does not handle conversion from PyLong, |
|
235 | // `index_getitem` does not handle conversion from PyLong, | |
236 | // which expressions such as [e for e in index] internally use. |
|
236 | // which expressions such as [e for e in index] internally use. | |
237 | // Note that we don't seem to have a direct way to call |
|
237 | // Note that we don't seem to have a direct way to call | |
238 | // PySequence_GetItem (does the job), which would possibly be better |
|
238 | // PySequence_GetItem (does the job), which would possibly be better | |
239 | // for performance |
|
239 | // for performance | |
240 | let key = match key.extract::<Revision>(py) { |
|
240 | let key = match key.extract::<Revision>(py) { | |
241 | Ok(rev) => rev.to_py_object(py).into_object(), |
|
241 | Ok(rev) => rev.to_py_object(py).into_object(), | |
242 | Err(_) => key, |
|
242 | Err(_) => key, | |
243 | }; |
|
243 | }; | |
244 | self.cindex(py).borrow().inner().get_item(py, key) |
|
244 | self.cindex(py).borrow().inner().get_item(py, key) | |
245 | } |
|
245 | } | |
246 |
|
246 | |||
247 | def __setitem__(&self, key: PyObject, value: PyObject) -> PyResult<()> { |
|
247 | def __setitem__(&self, key: PyObject, value: PyObject) -> PyResult<()> { | |
248 | self.cindex(py).borrow().inner().set_item(py, key, value) |
|
248 | self.cindex(py).borrow().inner().set_item(py, key, value) | |
249 | } |
|
249 | } | |
250 |
|
250 | |||
251 | def __contains__(&self, item: PyObject) -> PyResult<bool> { |
|
251 | def __contains__(&self, item: PyObject) -> PyResult<bool> { | |
252 | // ObjectProtocol does not seem to provide contains(), so |
|
252 | // ObjectProtocol does not seem to provide contains(), so | |
253 | // this is an equivalent implementation of the index_contains() |
|
253 | // this is an equivalent implementation of the index_contains() | |
254 | // defined in revlog.c |
|
254 | // defined in revlog.c | |
255 | let cindex = self.cindex(py).borrow(); |
|
255 | let cindex = self.cindex(py).borrow(); | |
256 | match item.extract::<Revision>(py) { |
|
256 | match item.extract::<Revision>(py) { | |
257 | Ok(rev) => { |
|
257 | Ok(rev) => { | |
258 | Ok(rev >= -1 && rev < cindex.inner().len(py)? as Revision) |
|
258 | Ok(rev >= -1 && rev < cindex.inner().len(py)? as Revision) | |
259 | } |
|
259 | } | |
260 | Err(_) => { |
|
260 | Err(_) => { | |
261 | cindex.inner().call_method( |
|
261 | cindex.inner().call_method( | |
262 | py, |
|
262 | py, | |
263 | "has_node", |
|
263 | "has_node", | |
264 | PyTuple::new(py, &[item]), |
|
264 | PyTuple::new(py, &[item]), | |
265 | None)? |
|
265 | None)? | |
266 | .extract(py) |
|
266 | .extract(py) | |
267 | } |
|
267 | } | |
268 | } |
|
268 | } | |
269 | } |
|
269 | } | |
270 |
|
270 | |||
271 | def nodemap_data_all(&self) -> PyResult<PyBytes> { |
|
271 | def nodemap_data_all(&self) -> PyResult<PyBytes> { | |
272 | self.inner_nodemap_data_all(py) |
|
272 | self.inner_nodemap_data_all(py) | |
273 | } |
|
273 | } | |
274 |
|
274 | |||
275 | def nodemap_data_incremental(&self) -> PyResult<PyObject> { |
|
275 | def nodemap_data_incremental(&self) -> PyResult<PyObject> { | |
276 | self.inner_nodemap_data_incremental(py) |
|
276 | self.inner_nodemap_data_incremental(py) | |
277 | } |
|
277 | } | |
278 | def update_nodemap_data( |
|
278 | def update_nodemap_data( | |
279 | &self, |
|
279 | &self, | |
280 | docket: PyObject, |
|
280 | docket: PyObject, | |
281 | nm_data: PyObject |
|
281 | nm_data: PyObject | |
282 | ) -> PyResult<PyObject> { |
|
282 | ) -> PyResult<PyObject> { | |
283 | self.inner_update_nodemap_data(py, docket, nm_data) |
|
283 | self.inner_update_nodemap_data(py, docket, nm_data) | |
284 | } |
|
284 | } | |
285 |
|
285 | |||
286 |
|
286 | |||
287 | }); |
|
287 | }); | |
288 |
|
288 | |||
289 | impl MixedIndex { |
|
289 | impl MixedIndex { | |
290 | fn new(py: Python, cindex: PyObject) -> PyResult<MixedIndex> { |
|
290 | fn new(py: Python, cindex: PyObject) -> PyResult<MixedIndex> { | |
291 | Self::create_instance( |
|
291 | Self::create_instance( | |
292 | py, |
|
292 | py, | |
293 | RefCell::new(cindex::Index::new(py, cindex)?), |
|
293 | RefCell::new(cindex::Index::new(py, cindex)?), | |
294 | RefCell::new(None), |
|
294 | RefCell::new(None), | |
295 | RefCell::new(None), |
|
295 | RefCell::new(None), | |
296 | RefCell::new(None), |
|
296 | RefCell::new(None), | |
297 | ) |
|
297 | ) | |
298 | } |
|
298 | } | |
299 |
|
299 | |||
300 | /// This is scaffolding at this point, but it could also become |
|
300 | /// This is scaffolding at this point, but it could also become | |
301 | /// a way to start a persistent nodemap or perform a |
|
301 | /// a way to start a persistent nodemap or perform a | |
302 | /// vacuum / repack operation |
|
302 | /// vacuum / repack operation | |
303 | fn fill_nodemap( |
|
303 | fn fill_nodemap( | |
304 | &self, |
|
304 | &self, | |
305 | py: Python, |
|
305 | py: Python, | |
306 | nt: &mut NodeTree, |
|
306 | nt: &mut NodeTree, | |
307 | ) -> PyResult<PyObject> { |
|
307 | ) -> PyResult<PyObject> { | |
308 | let index = self.cindex(py).borrow(); |
|
308 | let index = self.cindex(py).borrow(); | |
309 | for r in 0..index.len() { |
|
309 | for r in 0..index.len() { | |
310 | let rev = r as Revision; |
|
310 | let rev = r as Revision; | |
311 | // in this case node() won't ever return None |
|
311 | // in this case node() won't ever return None | |
312 | nt.insert(&*index, index.node(rev).unwrap(), rev) |
|
312 | nt.insert(&*index, index.node(rev).unwrap(), rev) | |
313 | .map_err(|e| nodemap_error(py, e))? |
|
313 | .map_err(|e| nodemap_error(py, e))? | |
314 | } |
|
314 | } | |
315 | Ok(py.None()) |
|
315 | Ok(py.None()) | |
316 | } |
|
316 | } | |
317 |
|
317 | |||
318 | fn get_nodetree<'a>( |
|
318 | fn get_nodetree<'a>( | |
319 | &'a self, |
|
319 | &'a self, | |
320 | py: Python<'a>, |
|
320 | py: Python<'a>, | |
321 | ) -> PyResult<&'a RefCell<Option<NodeTree>>> { |
|
321 | ) -> PyResult<&'a RefCell<Option<NodeTree>>> { | |
322 | if self.nt(py).borrow().is_none() { |
|
322 | if self.nt(py).borrow().is_none() { | |
323 | let readonly = Box::new(Vec::new()); |
|
323 | let readonly = Box::new(Vec::new()); | |
324 | let mut nt = NodeTree::load_bytes(readonly, 0); |
|
324 | let mut nt = NodeTree::load_bytes(readonly, 0); | |
325 | self.fill_nodemap(py, &mut nt)?; |
|
325 | self.fill_nodemap(py, &mut nt)?; | |
326 | self.nt(py).borrow_mut().replace(nt); |
|
326 | self.nt(py).borrow_mut().replace(nt); | |
327 | } |
|
327 | } | |
328 | Ok(self.nt(py)) |
|
328 | Ok(self.nt(py)) | |
329 | } |
|
329 | } | |
330 |
|
330 | |||
331 | /// forward a method call to the underlying C index |
|
331 | /// forward a method call to the underlying C index | |
332 | fn call_cindex( |
|
332 | fn call_cindex( | |
333 | &self, |
|
333 | &self, | |
334 | py: Python, |
|
334 | py: Python, | |
335 | name: &str, |
|
335 | name: &str, | |
336 | args: &PyTuple, |
|
336 | args: &PyTuple, | |
337 | kwargs: Option<&PyDict>, |
|
337 | kwargs: Option<&PyDict>, | |
338 | ) -> PyResult<PyObject> { |
|
338 | ) -> PyResult<PyObject> { | |
339 | self.cindex(py) |
|
339 | self.cindex(py) | |
340 | .borrow() |
|
340 | .borrow() | |
341 | .inner() |
|
341 | .inner() | |
342 | .call_method(py, name, args, kwargs) |
|
342 | .call_method(py, name, args, kwargs) | |
343 | } |
|
343 | } | |
344 |
|
344 | |||
345 | pub fn clone_cindex(&self, py: Python) -> cindex::Index { |
|
345 | pub fn clone_cindex(&self, py: Python) -> cindex::Index { | |
346 | self.cindex(py).borrow().clone_ref(py) |
|
346 | self.cindex(py).borrow().clone_ref(py) | |
347 | } |
|
347 | } | |
348 |
|
348 | |||
349 | /// Returns the full nodemap bytes to be written as-is to disk |
|
349 | /// Returns the full nodemap bytes to be written as-is to disk | |
350 | fn inner_nodemap_data_all(&self, py: Python) -> PyResult<PyBytes> { |
|
350 | fn inner_nodemap_data_all(&self, py: Python) -> PyResult<PyBytes> { | |
351 | let nodemap = self.get_nodetree(py)?.borrow_mut().take().unwrap(); |
|
351 | let nodemap = self.get_nodetree(py)?.borrow_mut().take().unwrap(); | |
352 | let (readonly, bytes) = nodemap.into_readonly_and_added_bytes(); |
|
352 | let (readonly, bytes) = nodemap.into_readonly_and_added_bytes(); | |
353 |
|
353 | |||
354 | // If there's anything readonly, we need to build the data again from |
|
354 | // If there's anything readonly, we need to build the data again from | |
355 | // scratch |
|
355 | // scratch | |
356 | let bytes = if readonly.len() > 0 { |
|
356 | let bytes = if readonly.len() > 0 { | |
357 | let mut nt = NodeTree::load_bytes(Box::new(vec![]), 0); |
|
357 | let mut nt = NodeTree::load_bytes(Box::new(vec![]), 0); | |
358 | self.fill_nodemap(py, &mut nt)?; |
|
358 | self.fill_nodemap(py, &mut nt)?; | |
359 |
|
359 | |||
360 | let (readonly, bytes) = nt.into_readonly_and_added_bytes(); |
|
360 | let (readonly, bytes) = nt.into_readonly_and_added_bytes(); | |
361 | assert_eq!(readonly.len(), 0); |
|
361 | assert_eq!(readonly.len(), 0); | |
362 |
|
362 | |||
363 | bytes |
|
363 | bytes | |
364 | } else { |
|
364 | } else { | |
365 | bytes |
|
365 | bytes | |
366 | }; |
|
366 | }; | |
367 |
|
367 | |||
368 | let bytes = PyBytes::new(py, &bytes); |
|
368 | let bytes = PyBytes::new(py, &bytes); | |
369 | Ok(bytes) |
|
369 | Ok(bytes) | |
370 | } |
|
370 | } | |
371 |
|
371 | |||
372 | /// Returns the last saved docket along with the size of any changed data |
|
372 | /// Returns the last saved docket along with the size of any changed data | |
373 | /// (in number of blocks), and said data as bytes. |
|
373 | /// (in number of blocks), and said data as bytes. | |
374 | fn inner_nodemap_data_incremental( |
|
374 | fn inner_nodemap_data_incremental( | |
375 | &self, |
|
375 | &self, | |
376 | py: Python, |
|
376 | py: Python, | |
377 | ) -> PyResult<PyObject> { |
|
377 | ) -> PyResult<PyObject> { | |
378 | let docket = self.docket(py).borrow(); |
|
378 | let docket = self.docket(py).borrow(); | |
379 | let docket = match docket.as_ref() { |
|
379 | let docket = match docket.as_ref() { | |
380 | Some(d) => d, |
|
380 | Some(d) => d, | |
381 | None => return Ok(py.None()), |
|
381 | None => return Ok(py.None()), | |
382 | }; |
|
382 | }; | |
383 |
|
383 | |||
384 | let node_tree = self.get_nodetree(py)?.borrow_mut().take().unwrap(); |
|
384 | let node_tree = self.get_nodetree(py)?.borrow_mut().take().unwrap(); | |
385 | let masked_blocks = node_tree.masked_readonly_blocks(); |
|
385 | let masked_blocks = node_tree.masked_readonly_blocks(); | |
386 | let (_, data) = node_tree.into_readonly_and_added_bytes(); |
|
386 | let (_, data) = node_tree.into_readonly_and_added_bytes(); | |
387 | let changed = masked_blocks * std::mem::size_of::<Block>(); |
|
387 | let changed = masked_blocks * std::mem::size_of::<Block>(); | |
388 |
|
388 | |||
389 | Ok((docket, changed, PyBytes::new(py, &data)) |
|
389 | Ok((docket, changed, PyBytes::new(py, &data)) | |
390 | .to_py_object(py) |
|
390 | .to_py_object(py) | |
391 | .into_object()) |
|
391 | .into_object()) | |
392 | } |
|
392 | } | |
393 |
|
393 | |||
394 | /// Update the nodemap from the new (mmaped) data. |
|
394 | /// Update the nodemap from the new (mmaped) data. | |
395 | /// The docket is kept as a reference for later incremental calls. |
|
395 | /// The docket is kept as a reference for later incremental calls. | |
396 | fn inner_update_nodemap_data( |
|
396 | fn inner_update_nodemap_data( | |
397 | &self, |
|
397 | &self, | |
398 | py: Python, |
|
398 | py: Python, | |
399 | docket: PyObject, |
|
399 | docket: PyObject, | |
400 | nm_data: PyObject, |
|
400 | nm_data: PyObject, | |
401 | ) -> PyResult<PyObject> { |
|
401 | ) -> PyResult<PyObject> { | |
402 | let buf = PyBuffer::get(py, &nm_data)?; |
|
402 | let buf = PyBuffer::get(py, &nm_data)?; | |
403 | let len = buf.item_count(); |
|
403 | let len = buf.item_count(); | |
404 |
|
404 | |||
405 | // Build a slice from the mmap'ed buffer data |
|
405 | // Build a slice from the mmap'ed buffer data | |
406 | let cbuf = buf.buf_ptr(); |
|
406 | let cbuf = buf.buf_ptr(); | |
407 | let bytes = if std::mem::size_of::<u8>() == buf.item_size() |
|
407 | let bytes = if std::mem::size_of::<u8>() == buf.item_size() | |
408 | && buf.is_c_contiguous() |
|
408 | && buf.is_c_contiguous() | |
409 | && u8::is_compatible_format(buf.format()) |
|
409 | && u8::is_compatible_format(buf.format()) | |
410 | { |
|
410 | { | |
411 | unsafe { std::slice::from_raw_parts(cbuf as *const u8, len) } |
|
411 | unsafe { std::slice::from_raw_parts(cbuf as *const u8, len) } | |
412 | } else { |
|
412 | } else { | |
413 | return Err(PyErr::new::<ValueError, _>( |
|
413 | return Err(PyErr::new::<ValueError, _>( | |
414 | py, |
|
414 | py, | |
415 | "Nodemap data buffer has an invalid memory representation" |
|
415 | "Nodemap data buffer has an invalid memory representation" | |
416 | .to_string(), |
|
416 | .to_string(), | |
417 | )); |
|
417 | )); | |
418 | }; |
|
418 | }; | |
419 |
|
419 | |||
420 | // Keep a reference to the mmap'ed buffer, otherwise we get a dangling |
|
420 | // Keep a reference to the mmap'ed buffer, otherwise we get a dangling | |
421 | // pointer. |
|
421 | // pointer. | |
422 | self.mmap(py).borrow_mut().replace(buf); |
|
422 | self.mmap(py).borrow_mut().replace(buf); | |
423 |
|
423 | |||
424 | let mut nt = NodeTree::load_bytes(Box::new(bytes), len); |
|
424 | let mut nt = NodeTree::load_bytes(Box::new(bytes), len); | |
425 |
|
425 | |||
426 | let data_tip = |
|
426 | let data_tip = | |
427 | docket.getattr(py, "tip_rev")?.extract::<Revision>(py)?; |
|
427 | docket.getattr(py, "tip_rev")?.extract::<Revision>(py)?; | |
428 | self.docket(py).borrow_mut().replace(docket.clone_ref(py)); |
|
428 | self.docket(py).borrow_mut().replace(docket.clone_ref(py)); | |
429 | let idx = self.cindex(py).borrow(); |
|
429 | let idx = self.cindex(py).borrow(); | |
430 | let current_tip = idx.len(); |
|
430 | let current_tip = idx.len(); | |
431 |
|
431 | |||
432 | for r in (data_tip + 1)..current_tip as Revision { |
|
432 | for r in (data_tip + 1)..current_tip as Revision { | |
433 | let rev = r as Revision; |
|
433 | let rev = r as Revision; | |
434 | // in this case node() won't ever return None |
|
434 | // in this case node() won't ever return None | |
435 | nt.insert(&*idx, idx.node(rev).unwrap(), rev) |
|
435 | nt.insert(&*idx, idx.node(rev).unwrap(), rev) | |
436 | .map_err(|e| nodemap_error(py, e))? |
|
436 | .map_err(|e| nodemap_error(py, e))? | |
437 | } |
|
437 | } | |
438 |
|
438 | |||
439 | *self.nt(py).borrow_mut() = Some(nt); |
|
439 | *self.nt(py).borrow_mut() = Some(nt); | |
440 |
|
440 | |||
441 | Ok(py.None()) |
|
441 | Ok(py.None()) | |
442 | } |
|
442 | } | |
443 | } |
|
443 | } | |
444 |
|
444 | |||
445 | fn revlog_error(py: Python) -> PyErr { |
|
445 | fn revlog_error(py: Python) -> PyErr { | |
446 | match py |
|
446 | match py | |
447 | .import("mercurial.error") |
|
447 | .import("mercurial.error") | |
448 | .and_then(|m| m.get(py, "RevlogError")) |
|
448 | .and_then(|m| m.get(py, "RevlogError")) | |
449 | { |
|
449 | { | |
450 | Err(e) => e, |
|
450 | Err(e) => e, | |
451 | Ok(cls) => PyErr::from_instance(py, cls), |
|
451 | Ok(cls) => PyErr::from_instance(py, cls), | |
452 | } |
|
452 | } | |
453 | } |
|
453 | } | |
454 |
|
454 | |||
455 | fn rev_not_in_index(py: Python, rev: Revision) -> PyErr { |
|
455 | fn rev_not_in_index(py: Python, rev: Revision) -> PyErr { | |
456 | PyErr::new::<ValueError, _>( |
|
456 | PyErr::new::<ValueError, _>( | |
457 | py, |
|
457 | py, | |
458 | format!( |
|
458 | format!( | |
459 | "Inconsistency: Revision {} found in nodemap \ |
|
459 | "Inconsistency: Revision {} found in nodemap \ | |
460 | is not in revlog index", |
|
460 | is not in revlog index", | |
461 | rev |
|
461 | rev | |
462 | ), |
|
462 | ), | |
463 | ) |
|
463 | ) | |
464 | } |
|
464 | } | |
465 |
|
465 | |||
466 | /// Standard treatment of NodeMapError |
|
466 | /// Standard treatment of NodeMapError | |
467 | fn nodemap_error(py: Python, err: NodeMapError) -> PyErr { |
|
467 | fn nodemap_error(py: Python, err: NodeMapError) -> PyErr { | |
468 | match err { |
|
468 | match err { | |
469 | NodeMapError::MultipleResults => revlog_error(py), |
|
469 | NodeMapError::MultipleResults => revlog_error(py), | |
470 | NodeMapError::RevisionNotInIndex(r) => rev_not_in_index(py, r), |
|
470 | NodeMapError::RevisionNotInIndex(r) => rev_not_in_index(py, r), | |
471 |
NodeMapError::InvalidNodePrefix |
|
471 | NodeMapError::InvalidNodePrefix => { | |
|
472 | PyErr::new::<ValueError, _>(py, "Invalid node or prefix") | |||
|
473 | } | |||
472 | } |
|
474 | } | |
473 | } |
|
475 | } | |
474 |
|
476 | |||
475 | fn invalid_node_prefix(py: Python, ne: &NodeError) -> PyErr { |
|
|||
476 | PyErr::new::<ValueError, _>( |
|
|||
477 | py, |
|
|||
478 | format!("Invalid node or prefix: {:?}", ne), |
|
|||
479 | ) |
|
|||
480 | } |
|
|||
481 |
|
||||
482 | /// Create the module, with __package__ given from parent |
|
477 | /// Create the module, with __package__ given from parent | |
483 | pub fn init_module(py: Python, package: &str) -> PyResult<PyModule> { |
|
478 | pub fn init_module(py: Python, package: &str) -> PyResult<PyModule> { | |
484 | let dotted_name = &format!("{}.revlog", package); |
|
479 | let dotted_name = &format!("{}.revlog", package); | |
485 | let m = PyModule::new(py, dotted_name)?; |
|
480 | let m = PyModule::new(py, dotted_name)?; | |
486 | m.add(py, "__package__", package)?; |
|
481 | m.add(py, "__package__", package)?; | |
487 | m.add(py, "__doc__", "RevLog - Rust implementations")?; |
|
482 | m.add(py, "__doc__", "RevLog - Rust implementations")?; | |
488 |
|
483 | |||
489 | m.add_class::<MixedIndex>(py)?; |
|
484 | m.add_class::<MixedIndex>(py)?; | |
490 |
|
485 | |||
491 | let sys = PyModule::import(py, "sys")?; |
|
486 | let sys = PyModule::import(py, "sys")?; | |
492 | let sys_modules: PyDict = sys.get(py, "modules")?.extract(py)?; |
|
487 | let sys_modules: PyDict = sys.get(py, "modules")?.extract(py)?; | |
493 | sys_modules.set_item(py, dotted_name, &m)?; |
|
488 | sys_modules.set_item(py, dotted_name, &m)?; | |
494 |
|
489 | |||
495 | Ok(m) |
|
490 | Ok(m) | |
496 | } |
|
491 | } |
General Comments 0
You need to be logged in to leave comments.
Login now