##// END OF EJS Templates
rust: use the bytes-cast crate to parse persistent nodemaps...
Simon Sapin -
r47107:1eb72345 default draft
parent child Browse files
Show More
@@ -1,1012 +1,1033 b''
1 1 # This file is automatically @generated by Cargo.
2 2 # It is not intended for manual editing.
3 3 [[package]]
4 4 name = "adler"
5 5 version = "0.2.3"
6 6 source = "registry+https://github.com/rust-lang/crates.io-index"
7 7
8 8 [[package]]
9 9 name = "aho-corasick"
10 10 version = "0.7.15"
11 11 source = "registry+https://github.com/rust-lang/crates.io-index"
12 12 dependencies = [
13 13 "memchr 2.3.4 (registry+https://github.com/rust-lang/crates.io-index)",
14 14 ]
15 15
16 16 [[package]]
17 17 name = "ansi_term"
18 18 version = "0.11.0"
19 19 source = "registry+https://github.com/rust-lang/crates.io-index"
20 20 dependencies = [
21 21 "winapi 0.3.9 (registry+https://github.com/rust-lang/crates.io-index)",
22 22 ]
23 23
24 24 [[package]]
25 25 name = "atty"
26 26 version = "0.2.14"
27 27 source = "registry+https://github.com/rust-lang/crates.io-index"
28 28 dependencies = [
29 29 "hermit-abi 0.1.17 (registry+https://github.com/rust-lang/crates.io-index)",
30 30 "libc 0.2.81 (registry+https://github.com/rust-lang/crates.io-index)",
31 31 "winapi 0.3.9 (registry+https://github.com/rust-lang/crates.io-index)",
32 32 ]
33 33
34 34 [[package]]
35 35 name = "autocfg"
36 36 version = "1.0.1"
37 37 source = "registry+https://github.com/rust-lang/crates.io-index"
38 38
39 39 [[package]]
40 40 name = "bitflags"
41 41 version = "1.2.1"
42 42 source = "registry+https://github.com/rust-lang/crates.io-index"
43 43
44 44 [[package]]
45 45 name = "bitmaps"
46 46 version = "2.1.0"
47 47 source = "registry+https://github.com/rust-lang/crates.io-index"
48 48 dependencies = [
49 49 "typenum 1.12.0 (registry+https://github.com/rust-lang/crates.io-index)",
50 50 ]
51 51
52 52 [[package]]
53 53 name = "byteorder"
54 54 version = "1.3.4"
55 55 source = "registry+https://github.com/rust-lang/crates.io-index"
56 56
57 57 [[package]]
58 name = "bytes-cast"
59 version = "0.1.0"
60 source = "registry+https://github.com/rust-lang/crates.io-index"
61 dependencies = [
62 "bytes-cast-derive 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)",
63 ]
64
65 [[package]]
66 name = "bytes-cast-derive"
67 version = "0.1.0"
68 source = "registry+https://github.com/rust-lang/crates.io-index"
69 dependencies = [
70 "proc-macro2 1.0.24 (registry+https://github.com/rust-lang/crates.io-index)",
71 "quote 1.0.7 (registry+https://github.com/rust-lang/crates.io-index)",
72 "syn 1.0.54 (registry+https://github.com/rust-lang/crates.io-index)",
73 ]
74
75 [[package]]
58 76 name = "cc"
59 77 version = "1.0.66"
60 78 source = "registry+https://github.com/rust-lang/crates.io-index"
61 79 dependencies = [
62 80 "jobserver 0.1.21 (registry+https://github.com/rust-lang/crates.io-index)",
63 81 ]
64 82
65 83 [[package]]
66 84 name = "cfg-if"
67 85 version = "0.1.10"
68 86 source = "registry+https://github.com/rust-lang/crates.io-index"
69 87
70 88 [[package]]
71 89 name = "cfg-if"
72 90 version = "1.0.0"
73 91 source = "registry+https://github.com/rust-lang/crates.io-index"
74 92
75 93 [[package]]
76 94 name = "clap"
77 95 version = "2.33.3"
78 96 source = "registry+https://github.com/rust-lang/crates.io-index"
79 97 dependencies = [
80 98 "ansi_term 0.11.0 (registry+https://github.com/rust-lang/crates.io-index)",
81 99 "atty 0.2.14 (registry+https://github.com/rust-lang/crates.io-index)",
82 100 "bitflags 1.2.1 (registry+https://github.com/rust-lang/crates.io-index)",
83 101 "strsim 0.8.0 (registry+https://github.com/rust-lang/crates.io-index)",
84 102 "textwrap 0.11.0 (registry+https://github.com/rust-lang/crates.io-index)",
85 103 "unicode-width 0.1.8 (registry+https://github.com/rust-lang/crates.io-index)",
86 104 "vec_map 0.8.2 (registry+https://github.com/rust-lang/crates.io-index)",
87 105 ]
88 106
89 107 [[package]]
90 108 name = "const_fn"
91 109 version = "0.4.4"
92 110 source = "registry+https://github.com/rust-lang/crates.io-index"
93 111
94 112 [[package]]
95 113 name = "cpython"
96 114 version = "0.4.1"
97 115 source = "registry+https://github.com/rust-lang/crates.io-index"
98 116 dependencies = [
99 117 "libc 0.2.81 (registry+https://github.com/rust-lang/crates.io-index)",
100 118 "num-traits 0.2.14 (registry+https://github.com/rust-lang/crates.io-index)",
101 119 "python27-sys 0.4.1 (registry+https://github.com/rust-lang/crates.io-index)",
102 120 "python3-sys 0.4.1 (registry+https://github.com/rust-lang/crates.io-index)",
103 121 ]
104 122
105 123 [[package]]
106 124 name = "crc32fast"
107 125 version = "1.2.1"
108 126 source = "registry+https://github.com/rust-lang/crates.io-index"
109 127 dependencies = [
110 128 "cfg-if 1.0.0 (registry+https://github.com/rust-lang/crates.io-index)",
111 129 ]
112 130
113 131 [[package]]
114 132 name = "crossbeam-channel"
115 133 version = "0.4.4"
116 134 source = "registry+https://github.com/rust-lang/crates.io-index"
117 135 dependencies = [
118 136 "crossbeam-utils 0.7.2 (registry+https://github.com/rust-lang/crates.io-index)",
119 137 "maybe-uninit 2.0.0 (registry+https://github.com/rust-lang/crates.io-index)",
120 138 ]
121 139
122 140 [[package]]
123 141 name = "crossbeam-channel"
124 142 version = "0.5.0"
125 143 source = "registry+https://github.com/rust-lang/crates.io-index"
126 144 dependencies = [
127 145 "cfg-if 1.0.0 (registry+https://github.com/rust-lang/crates.io-index)",
128 146 "crossbeam-utils 0.8.1 (registry+https://github.com/rust-lang/crates.io-index)",
129 147 ]
130 148
131 149 [[package]]
132 150 name = "crossbeam-deque"
133 151 version = "0.8.0"
134 152 source = "registry+https://github.com/rust-lang/crates.io-index"
135 153 dependencies = [
136 154 "cfg-if 1.0.0 (registry+https://github.com/rust-lang/crates.io-index)",
137 155 "crossbeam-epoch 0.9.1 (registry+https://github.com/rust-lang/crates.io-index)",
138 156 "crossbeam-utils 0.8.1 (registry+https://github.com/rust-lang/crates.io-index)",
139 157 ]
140 158
141 159 [[package]]
142 160 name = "crossbeam-epoch"
143 161 version = "0.9.1"
144 162 source = "registry+https://github.com/rust-lang/crates.io-index"
145 163 dependencies = [
146 164 "cfg-if 1.0.0 (registry+https://github.com/rust-lang/crates.io-index)",
147 165 "const_fn 0.4.4 (registry+https://github.com/rust-lang/crates.io-index)",
148 166 "crossbeam-utils 0.8.1 (registry+https://github.com/rust-lang/crates.io-index)",
149 167 "lazy_static 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)",
150 168 "memoffset 0.6.1 (registry+https://github.com/rust-lang/crates.io-index)",
151 169 "scopeguard 1.1.0 (registry+https://github.com/rust-lang/crates.io-index)",
152 170 ]
153 171
154 172 [[package]]
155 173 name = "crossbeam-utils"
156 174 version = "0.7.2"
157 175 source = "registry+https://github.com/rust-lang/crates.io-index"
158 176 dependencies = [
159 177 "autocfg 1.0.1 (registry+https://github.com/rust-lang/crates.io-index)",
160 178 "cfg-if 0.1.10 (registry+https://github.com/rust-lang/crates.io-index)",
161 179 "lazy_static 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)",
162 180 ]
163 181
164 182 [[package]]
165 183 name = "crossbeam-utils"
166 184 version = "0.8.1"
167 185 source = "registry+https://github.com/rust-lang/crates.io-index"
168 186 dependencies = [
169 187 "autocfg 1.0.1 (registry+https://github.com/rust-lang/crates.io-index)",
170 188 "cfg-if 1.0.0 (registry+https://github.com/rust-lang/crates.io-index)",
171 189 "lazy_static 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)",
172 190 ]
173 191
174 192 [[package]]
175 193 name = "ctor"
176 194 version = "0.1.16"
177 195 source = "registry+https://github.com/rust-lang/crates.io-index"
178 196 dependencies = [
179 197 "quote 1.0.7 (registry+https://github.com/rust-lang/crates.io-index)",
180 198 "syn 1.0.54 (registry+https://github.com/rust-lang/crates.io-index)",
181 199 ]
182 200
183 201 [[package]]
184 202 name = "difference"
185 203 version = "2.0.0"
186 204 source = "registry+https://github.com/rust-lang/crates.io-index"
187 205
188 206 [[package]]
189 207 name = "either"
190 208 version = "1.6.1"
191 209 source = "registry+https://github.com/rust-lang/crates.io-index"
192 210
193 211 [[package]]
194 212 name = "env_logger"
195 213 version = "0.7.1"
196 214 source = "registry+https://github.com/rust-lang/crates.io-index"
197 215 dependencies = [
198 216 "atty 0.2.14 (registry+https://github.com/rust-lang/crates.io-index)",
199 217 "humantime 1.3.0 (registry+https://github.com/rust-lang/crates.io-index)",
200 218 "log 0.4.11 (registry+https://github.com/rust-lang/crates.io-index)",
201 219 "regex 1.4.2 (registry+https://github.com/rust-lang/crates.io-index)",
202 220 "termcolor 1.1.2 (registry+https://github.com/rust-lang/crates.io-index)",
203 221 ]
204 222
205 223 [[package]]
206 224 name = "flate2"
207 225 version = "1.0.19"
208 226 source = "registry+https://github.com/rust-lang/crates.io-index"
209 227 dependencies = [
210 228 "cfg-if 1.0.0 (registry+https://github.com/rust-lang/crates.io-index)",
211 229 "crc32fast 1.2.1 (registry+https://github.com/rust-lang/crates.io-index)",
212 230 "libc 0.2.81 (registry+https://github.com/rust-lang/crates.io-index)",
213 231 "libz-sys 1.1.2 (registry+https://github.com/rust-lang/crates.io-index)",
214 232 "miniz_oxide 0.4.3 (registry+https://github.com/rust-lang/crates.io-index)",
215 233 ]
216 234
217 235 [[package]]
218 236 name = "format-bytes"
219 237 version = "0.1.3"
220 238 source = "registry+https://github.com/rust-lang/crates.io-index"
221 239 dependencies = [
222 240 "format-bytes-macros 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)",
223 241 "proc-macro-hack 0.5.19 (registry+https://github.com/rust-lang/crates.io-index)",
224 242 ]
225 243
226 244 [[package]]
227 245 name = "format-bytes-macros"
228 246 version = "0.1.2"
229 247 source = "registry+https://github.com/rust-lang/crates.io-index"
230 248 dependencies = [
231 249 "proc-macro-hack 0.5.19 (registry+https://github.com/rust-lang/crates.io-index)",
232 250 "proc-macro2 1.0.24 (registry+https://github.com/rust-lang/crates.io-index)",
233 251 "quote 1.0.7 (registry+https://github.com/rust-lang/crates.io-index)",
234 252 "syn 1.0.54 (registry+https://github.com/rust-lang/crates.io-index)",
235 253 ]
236 254
237 255 [[package]]
238 256 name = "fuchsia-cprng"
239 257 version = "0.1.1"
240 258 source = "registry+https://github.com/rust-lang/crates.io-index"
241 259
242 260 [[package]]
243 261 name = "gcc"
244 262 version = "0.3.55"
245 263 source = "registry+https://github.com/rust-lang/crates.io-index"
246 264
247 265 [[package]]
248 266 name = "getrandom"
249 267 version = "0.1.15"
250 268 source = "registry+https://github.com/rust-lang/crates.io-index"
251 269 dependencies = [
252 270 "cfg-if 0.1.10 (registry+https://github.com/rust-lang/crates.io-index)",
253 271 "libc 0.2.81 (registry+https://github.com/rust-lang/crates.io-index)",
254 272 "wasi 0.9.0+wasi-snapshot-preview1 (registry+https://github.com/rust-lang/crates.io-index)",
255 273 ]
256 274
257 275 [[package]]
258 276 name = "glob"
259 277 version = "0.3.0"
260 278 source = "registry+https://github.com/rust-lang/crates.io-index"
261 279
262 280 [[package]]
263 281 name = "hermit-abi"
264 282 version = "0.1.17"
265 283 source = "registry+https://github.com/rust-lang/crates.io-index"
266 284 dependencies = [
267 285 "libc 0.2.81 (registry+https://github.com/rust-lang/crates.io-index)",
268 286 ]
269 287
270 288 [[package]]
271 289 name = "hex"
272 290 version = "0.4.2"
273 291 source = "registry+https://github.com/rust-lang/crates.io-index"
274 292
275 293 [[package]]
276 294 name = "hg-core"
277 295 version = "0.1.0"
278 296 dependencies = [
279 297 "byteorder 1.3.4 (registry+https://github.com/rust-lang/crates.io-index)",
298 "bytes-cast 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)",
280 299 "clap 2.33.3 (registry+https://github.com/rust-lang/crates.io-index)",
281 300 "crossbeam-channel 0.4.4 (registry+https://github.com/rust-lang/crates.io-index)",
282 301 "flate2 1.0.19 (registry+https://github.com/rust-lang/crates.io-index)",
283 302 "format-bytes 0.1.3 (registry+https://github.com/rust-lang/crates.io-index)",
284 303 "hex 0.4.2 (registry+https://github.com/rust-lang/crates.io-index)",
285 304 "im-rc 15.0.0 (registry+https://github.com/rust-lang/crates.io-index)",
286 305 "lazy_static 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)",
287 306 "log 0.4.11 (registry+https://github.com/rust-lang/crates.io-index)",
288 307 "memchr 2.3.4 (registry+https://github.com/rust-lang/crates.io-index)",
289 308 "memmap 0.7.0 (registry+https://github.com/rust-lang/crates.io-index)",
290 309 "micro-timer 0.3.1 (registry+https://github.com/rust-lang/crates.io-index)",
291 310 "pretty_assertions 0.6.1 (registry+https://github.com/rust-lang/crates.io-index)",
292 311 "rand 0.7.3 (registry+https://github.com/rust-lang/crates.io-index)",
293 312 "rand_distr 0.2.2 (registry+https://github.com/rust-lang/crates.io-index)",
294 313 "rand_pcg 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)",
295 314 "rayon 1.5.0 (registry+https://github.com/rust-lang/crates.io-index)",
296 315 "regex 1.4.2 (registry+https://github.com/rust-lang/crates.io-index)",
297 316 "rust-crypto 0.2.36 (registry+https://github.com/rust-lang/crates.io-index)",
298 317 "same-file 1.0.6 (registry+https://github.com/rust-lang/crates.io-index)",
299 318 "tempfile 3.1.0 (registry+https://github.com/rust-lang/crates.io-index)",
300 319 "twox-hash 1.6.0 (registry+https://github.com/rust-lang/crates.io-index)",
301 320 "zstd 0.5.3+zstd.1.4.5 (registry+https://github.com/rust-lang/crates.io-index)",
302 321 ]
303 322
304 323 [[package]]
305 324 name = "hg-cpython"
306 325 version = "0.1.0"
307 326 dependencies = [
308 327 "cpython 0.4.1 (registry+https://github.com/rust-lang/crates.io-index)",
309 328 "env_logger 0.7.1 (registry+https://github.com/rust-lang/crates.io-index)",
310 329 "hg-core 0.1.0",
311 330 "libc 0.2.81 (registry+https://github.com/rust-lang/crates.io-index)",
312 331 "log 0.4.11 (registry+https://github.com/rust-lang/crates.io-index)",
313 332 ]
314 333
315 334 [[package]]
316 335 name = "humantime"
317 336 version = "1.3.0"
318 337 source = "registry+https://github.com/rust-lang/crates.io-index"
319 338 dependencies = [
320 339 "quick-error 1.2.3 (registry+https://github.com/rust-lang/crates.io-index)",
321 340 ]
322 341
323 342 [[package]]
324 343 name = "im-rc"
325 344 version = "15.0.0"
326 345 source = "registry+https://github.com/rust-lang/crates.io-index"
327 346 dependencies = [
328 347 "bitmaps 2.1.0 (registry+https://github.com/rust-lang/crates.io-index)",
329 348 "rand_core 0.5.1 (registry+https://github.com/rust-lang/crates.io-index)",
330 349 "rand_xoshiro 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)",
331 350 "sized-chunks 0.6.2 (registry+https://github.com/rust-lang/crates.io-index)",
332 351 "typenum 1.12.0 (registry+https://github.com/rust-lang/crates.io-index)",
333 352 "version_check 0.9.2 (registry+https://github.com/rust-lang/crates.io-index)",
334 353 ]
335 354
336 355 [[package]]
337 356 name = "itertools"
338 357 version = "0.9.0"
339 358 source = "registry+https://github.com/rust-lang/crates.io-index"
340 359 dependencies = [
341 360 "either 1.6.1 (registry+https://github.com/rust-lang/crates.io-index)",
342 361 ]
343 362
344 363 [[package]]
345 364 name = "jobserver"
346 365 version = "0.1.21"
347 366 source = "registry+https://github.com/rust-lang/crates.io-index"
348 367 dependencies = [
349 368 "libc 0.2.81 (registry+https://github.com/rust-lang/crates.io-index)",
350 369 ]
351 370
352 371 [[package]]
353 372 name = "lazy_static"
354 373 version = "1.4.0"
355 374 source = "registry+https://github.com/rust-lang/crates.io-index"
356 375
357 376 [[package]]
358 377 name = "libc"
359 378 version = "0.2.81"
360 379 source = "registry+https://github.com/rust-lang/crates.io-index"
361 380
362 381 [[package]]
363 382 name = "libz-sys"
364 383 version = "1.1.2"
365 384 source = "registry+https://github.com/rust-lang/crates.io-index"
366 385 dependencies = [
367 386 "cc 1.0.66 (registry+https://github.com/rust-lang/crates.io-index)",
368 387 "pkg-config 0.3.19 (registry+https://github.com/rust-lang/crates.io-index)",
369 388 "vcpkg 0.2.11 (registry+https://github.com/rust-lang/crates.io-index)",
370 389 ]
371 390
372 391 [[package]]
373 392 name = "log"
374 393 version = "0.4.11"
375 394 source = "registry+https://github.com/rust-lang/crates.io-index"
376 395 dependencies = [
377 396 "cfg-if 0.1.10 (registry+https://github.com/rust-lang/crates.io-index)",
378 397 ]
379 398
380 399 [[package]]
381 400 name = "maybe-uninit"
382 401 version = "2.0.0"
383 402 source = "registry+https://github.com/rust-lang/crates.io-index"
384 403
385 404 [[package]]
386 405 name = "memchr"
387 406 version = "2.3.4"
388 407 source = "registry+https://github.com/rust-lang/crates.io-index"
389 408
390 409 [[package]]
391 410 name = "memmap"
392 411 version = "0.7.0"
393 412 source = "registry+https://github.com/rust-lang/crates.io-index"
394 413 dependencies = [
395 414 "libc 0.2.81 (registry+https://github.com/rust-lang/crates.io-index)",
396 415 "winapi 0.3.9 (registry+https://github.com/rust-lang/crates.io-index)",
397 416 ]
398 417
399 418 [[package]]
400 419 name = "memoffset"
401 420 version = "0.6.1"
402 421 source = "registry+https://github.com/rust-lang/crates.io-index"
403 422 dependencies = [
404 423 "autocfg 1.0.1 (registry+https://github.com/rust-lang/crates.io-index)",
405 424 ]
406 425
407 426 [[package]]
408 427 name = "micro-timer"
409 428 version = "0.3.1"
410 429 source = "registry+https://github.com/rust-lang/crates.io-index"
411 430 dependencies = [
412 431 "micro-timer-macros 0.3.1 (registry+https://github.com/rust-lang/crates.io-index)",
413 432 "scopeguard 1.1.0 (registry+https://github.com/rust-lang/crates.io-index)",
414 433 ]
415 434
416 435 [[package]]
417 436 name = "micro-timer-macros"
418 437 version = "0.3.1"
419 438 source = "registry+https://github.com/rust-lang/crates.io-index"
420 439 dependencies = [
421 440 "proc-macro2 1.0.24 (registry+https://github.com/rust-lang/crates.io-index)",
422 441 "quote 1.0.7 (registry+https://github.com/rust-lang/crates.io-index)",
423 442 "scopeguard 1.1.0 (registry+https://github.com/rust-lang/crates.io-index)",
424 443 "syn 1.0.54 (registry+https://github.com/rust-lang/crates.io-index)",
425 444 ]
426 445
427 446 [[package]]
428 447 name = "miniz_oxide"
429 448 version = "0.4.3"
430 449 source = "registry+https://github.com/rust-lang/crates.io-index"
431 450 dependencies = [
432 451 "adler 0.2.3 (registry+https://github.com/rust-lang/crates.io-index)",
433 452 "autocfg 1.0.1 (registry+https://github.com/rust-lang/crates.io-index)",
434 453 ]
435 454
436 455 [[package]]
437 456 name = "num-traits"
438 457 version = "0.2.14"
439 458 source = "registry+https://github.com/rust-lang/crates.io-index"
440 459 dependencies = [
441 460 "autocfg 1.0.1 (registry+https://github.com/rust-lang/crates.io-index)",
442 461 ]
443 462
444 463 [[package]]
445 464 name = "num_cpus"
446 465 version = "1.13.0"
447 466 source = "registry+https://github.com/rust-lang/crates.io-index"
448 467 dependencies = [
449 468 "hermit-abi 0.1.17 (registry+https://github.com/rust-lang/crates.io-index)",
450 469 "libc 0.2.81 (registry+https://github.com/rust-lang/crates.io-index)",
451 470 ]
452 471
453 472 [[package]]
454 473 name = "output_vt100"
455 474 version = "0.1.2"
456 475 source = "registry+https://github.com/rust-lang/crates.io-index"
457 476 dependencies = [
458 477 "winapi 0.3.9 (registry+https://github.com/rust-lang/crates.io-index)",
459 478 ]
460 479
461 480 [[package]]
462 481 name = "pkg-config"
463 482 version = "0.3.19"
464 483 source = "registry+https://github.com/rust-lang/crates.io-index"
465 484
466 485 [[package]]
467 486 name = "ppv-lite86"
468 487 version = "0.2.10"
469 488 source = "registry+https://github.com/rust-lang/crates.io-index"
470 489
471 490 [[package]]
472 491 name = "pretty_assertions"
473 492 version = "0.6.1"
474 493 source = "registry+https://github.com/rust-lang/crates.io-index"
475 494 dependencies = [
476 495 "ansi_term 0.11.0 (registry+https://github.com/rust-lang/crates.io-index)",
477 496 "ctor 0.1.16 (registry+https://github.com/rust-lang/crates.io-index)",
478 497 "difference 2.0.0 (registry+https://github.com/rust-lang/crates.io-index)",
479 498 "output_vt100 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)",
480 499 ]
481 500
482 501 [[package]]
483 502 name = "proc-macro-hack"
484 503 version = "0.5.19"
485 504 source = "registry+https://github.com/rust-lang/crates.io-index"
486 505
487 506 [[package]]
488 507 name = "proc-macro2"
489 508 version = "1.0.24"
490 509 source = "registry+https://github.com/rust-lang/crates.io-index"
491 510 dependencies = [
492 511 "unicode-xid 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)",
493 512 ]
494 513
495 514 [[package]]
496 515 name = "python27-sys"
497 516 version = "0.4.1"
498 517 source = "registry+https://github.com/rust-lang/crates.io-index"
499 518 dependencies = [
500 519 "libc 0.2.81 (registry+https://github.com/rust-lang/crates.io-index)",
501 520 "regex 1.4.2 (registry+https://github.com/rust-lang/crates.io-index)",
502 521 ]
503 522
504 523 [[package]]
505 524 name = "python3-sys"
506 525 version = "0.4.1"
507 526 source = "registry+https://github.com/rust-lang/crates.io-index"
508 527 dependencies = [
509 528 "libc 0.2.81 (registry+https://github.com/rust-lang/crates.io-index)",
510 529 "regex 1.4.2 (registry+https://github.com/rust-lang/crates.io-index)",
511 530 ]
512 531
513 532 [[package]]
514 533 name = "quick-error"
515 534 version = "1.2.3"
516 535 source = "registry+https://github.com/rust-lang/crates.io-index"
517 536
518 537 [[package]]
519 538 name = "quote"
520 539 version = "1.0.7"
521 540 source = "registry+https://github.com/rust-lang/crates.io-index"
522 541 dependencies = [
523 542 "proc-macro2 1.0.24 (registry+https://github.com/rust-lang/crates.io-index)",
524 543 ]
525 544
526 545 [[package]]
527 546 name = "rand"
528 547 version = "0.3.23"
529 548 source = "registry+https://github.com/rust-lang/crates.io-index"
530 549 dependencies = [
531 550 "libc 0.2.81 (registry+https://github.com/rust-lang/crates.io-index)",
532 551 "rand 0.4.6 (registry+https://github.com/rust-lang/crates.io-index)",
533 552 ]
534 553
535 554 [[package]]
536 555 name = "rand"
537 556 version = "0.4.6"
538 557 source = "registry+https://github.com/rust-lang/crates.io-index"
539 558 dependencies = [
540 559 "fuchsia-cprng 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)",
541 560 "libc 0.2.81 (registry+https://github.com/rust-lang/crates.io-index)",
542 561 "rand_core 0.3.1 (registry+https://github.com/rust-lang/crates.io-index)",
543 562 "rdrand 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)",
544 563 "winapi 0.3.9 (registry+https://github.com/rust-lang/crates.io-index)",
545 564 ]
546 565
547 566 [[package]]
548 567 name = "rand"
549 568 version = "0.7.3"
550 569 source = "registry+https://github.com/rust-lang/crates.io-index"
551 570 dependencies = [
552 571 "getrandom 0.1.15 (registry+https://github.com/rust-lang/crates.io-index)",
553 572 "libc 0.2.81 (registry+https://github.com/rust-lang/crates.io-index)",
554 573 "rand_chacha 0.2.2 (registry+https://github.com/rust-lang/crates.io-index)",
555 574 "rand_core 0.5.1 (registry+https://github.com/rust-lang/crates.io-index)",
556 575 "rand_hc 0.2.0 (registry+https://github.com/rust-lang/crates.io-index)",
557 576 ]
558 577
559 578 [[package]]
560 579 name = "rand_chacha"
561 580 version = "0.2.2"
562 581 source = "registry+https://github.com/rust-lang/crates.io-index"
563 582 dependencies = [
564 583 "ppv-lite86 0.2.10 (registry+https://github.com/rust-lang/crates.io-index)",
565 584 "rand_core 0.5.1 (registry+https://github.com/rust-lang/crates.io-index)",
566 585 ]
567 586
568 587 [[package]]
569 588 name = "rand_core"
570 589 version = "0.3.1"
571 590 source = "registry+https://github.com/rust-lang/crates.io-index"
572 591 dependencies = [
573 592 "rand_core 0.4.2 (registry+https://github.com/rust-lang/crates.io-index)",
574 593 ]
575 594
576 595 [[package]]
577 596 name = "rand_core"
578 597 version = "0.4.2"
579 598 source = "registry+https://github.com/rust-lang/crates.io-index"
580 599
581 600 [[package]]
582 601 name = "rand_core"
583 602 version = "0.5.1"
584 603 source = "registry+https://github.com/rust-lang/crates.io-index"
585 604 dependencies = [
586 605 "getrandom 0.1.15 (registry+https://github.com/rust-lang/crates.io-index)",
587 606 ]
588 607
589 608 [[package]]
590 609 name = "rand_distr"
591 610 version = "0.2.2"
592 611 source = "registry+https://github.com/rust-lang/crates.io-index"
593 612 dependencies = [
594 613 "rand 0.7.3 (registry+https://github.com/rust-lang/crates.io-index)",
595 614 ]
596 615
597 616 [[package]]
598 617 name = "rand_hc"
599 618 version = "0.2.0"
600 619 source = "registry+https://github.com/rust-lang/crates.io-index"
601 620 dependencies = [
602 621 "rand_core 0.5.1 (registry+https://github.com/rust-lang/crates.io-index)",
603 622 ]
604 623
605 624 [[package]]
606 625 name = "rand_pcg"
607 626 version = "0.2.1"
608 627 source = "registry+https://github.com/rust-lang/crates.io-index"
609 628 dependencies = [
610 629 "rand_core 0.5.1 (registry+https://github.com/rust-lang/crates.io-index)",
611 630 ]
612 631
613 632 [[package]]
614 633 name = "rand_xoshiro"
615 634 version = "0.4.0"
616 635 source = "registry+https://github.com/rust-lang/crates.io-index"
617 636 dependencies = [
618 637 "rand_core 0.5.1 (registry+https://github.com/rust-lang/crates.io-index)",
619 638 ]
620 639
621 640 [[package]]
622 641 name = "rayon"
623 642 version = "1.5.0"
624 643 source = "registry+https://github.com/rust-lang/crates.io-index"
625 644 dependencies = [
626 645 "autocfg 1.0.1 (registry+https://github.com/rust-lang/crates.io-index)",
627 646 "crossbeam-deque 0.8.0 (registry+https://github.com/rust-lang/crates.io-index)",
628 647 "either 1.6.1 (registry+https://github.com/rust-lang/crates.io-index)",
629 648 "rayon-core 1.9.0 (registry+https://github.com/rust-lang/crates.io-index)",
630 649 ]
631 650
632 651 [[package]]
633 652 name = "rayon-core"
634 653 version = "1.9.0"
635 654 source = "registry+https://github.com/rust-lang/crates.io-index"
636 655 dependencies = [
637 656 "crossbeam-channel 0.5.0 (registry+https://github.com/rust-lang/crates.io-index)",
638 657 "crossbeam-deque 0.8.0 (registry+https://github.com/rust-lang/crates.io-index)",
639 658 "crossbeam-utils 0.8.1 (registry+https://github.com/rust-lang/crates.io-index)",
640 659 "lazy_static 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)",
641 660 "num_cpus 1.13.0 (registry+https://github.com/rust-lang/crates.io-index)",
642 661 ]
643 662
644 663 [[package]]
645 664 name = "rdrand"
646 665 version = "0.4.0"
647 666 source = "registry+https://github.com/rust-lang/crates.io-index"
648 667 dependencies = [
649 668 "rand_core 0.3.1 (registry+https://github.com/rust-lang/crates.io-index)",
650 669 ]
651 670
652 671 [[package]]
653 672 name = "redox_syscall"
654 673 version = "0.1.57"
655 674 source = "registry+https://github.com/rust-lang/crates.io-index"
656 675
657 676 [[package]]
658 677 name = "regex"
659 678 version = "1.4.2"
660 679 source = "registry+https://github.com/rust-lang/crates.io-index"
661 680 dependencies = [
662 681 "aho-corasick 0.7.15 (registry+https://github.com/rust-lang/crates.io-index)",
663 682 "memchr 2.3.4 (registry+https://github.com/rust-lang/crates.io-index)",
664 683 "regex-syntax 0.6.21 (registry+https://github.com/rust-lang/crates.io-index)",
665 684 "thread_local 1.0.1 (registry+https://github.com/rust-lang/crates.io-index)",
666 685 ]
667 686
668 687 [[package]]
669 688 name = "regex-syntax"
670 689 version = "0.6.21"
671 690 source = "registry+https://github.com/rust-lang/crates.io-index"
672 691
673 692 [[package]]
674 693 name = "remove_dir_all"
675 694 version = "0.5.3"
676 695 source = "registry+https://github.com/rust-lang/crates.io-index"
677 696 dependencies = [
678 697 "winapi 0.3.9 (registry+https://github.com/rust-lang/crates.io-index)",
679 698 ]
680 699
681 700 [[package]]
682 701 name = "rhg"
683 702 version = "0.1.0"
684 703 dependencies = [
685 704 "clap 2.33.3 (registry+https://github.com/rust-lang/crates.io-index)",
686 705 "env_logger 0.7.1 (registry+https://github.com/rust-lang/crates.io-index)",
687 706 "format-bytes 0.1.3 (registry+https://github.com/rust-lang/crates.io-index)",
688 707 "hg-core 0.1.0",
689 708 "log 0.4.11 (registry+https://github.com/rust-lang/crates.io-index)",
690 709 "micro-timer 0.3.1 (registry+https://github.com/rust-lang/crates.io-index)",
691 710 ]
692 711
693 712 [[package]]
694 713 name = "rust-crypto"
695 714 version = "0.2.36"
696 715 source = "registry+https://github.com/rust-lang/crates.io-index"
697 716 dependencies = [
698 717 "gcc 0.3.55 (registry+https://github.com/rust-lang/crates.io-index)",
699 718 "libc 0.2.81 (registry+https://github.com/rust-lang/crates.io-index)",
700 719 "rand 0.3.23 (registry+https://github.com/rust-lang/crates.io-index)",
701 720 "rustc-serialize 0.3.24 (registry+https://github.com/rust-lang/crates.io-index)",
702 721 "time 0.1.44 (registry+https://github.com/rust-lang/crates.io-index)",
703 722 ]
704 723
705 724 [[package]]
706 725 name = "rustc-serialize"
707 726 version = "0.3.24"
708 727 source = "registry+https://github.com/rust-lang/crates.io-index"
709 728
710 729 [[package]]
711 730 name = "same-file"
712 731 version = "1.0.6"
713 732 source = "registry+https://github.com/rust-lang/crates.io-index"
714 733 dependencies = [
715 734 "winapi-util 0.1.5 (registry+https://github.com/rust-lang/crates.io-index)",
716 735 ]
717 736
718 737 [[package]]
719 738 name = "scopeguard"
720 739 version = "1.1.0"
721 740 source = "registry+https://github.com/rust-lang/crates.io-index"
722 741
723 742 [[package]]
724 743 name = "sized-chunks"
725 744 version = "0.6.2"
726 745 source = "registry+https://github.com/rust-lang/crates.io-index"
727 746 dependencies = [
728 747 "bitmaps 2.1.0 (registry+https://github.com/rust-lang/crates.io-index)",
729 748 "typenum 1.12.0 (registry+https://github.com/rust-lang/crates.io-index)",
730 749 ]
731 750
732 751 [[package]]
733 752 name = "static_assertions"
734 753 version = "1.1.0"
735 754 source = "registry+https://github.com/rust-lang/crates.io-index"
736 755
737 756 [[package]]
738 757 name = "strsim"
739 758 version = "0.8.0"
740 759 source = "registry+https://github.com/rust-lang/crates.io-index"
741 760
742 761 [[package]]
743 762 name = "syn"
744 763 version = "1.0.54"
745 764 source = "registry+https://github.com/rust-lang/crates.io-index"
746 765 dependencies = [
747 766 "proc-macro2 1.0.24 (registry+https://github.com/rust-lang/crates.io-index)",
748 767 "quote 1.0.7 (registry+https://github.com/rust-lang/crates.io-index)",
749 768 "unicode-xid 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)",
750 769 ]
751 770
752 771 [[package]]
753 772 name = "tempfile"
754 773 version = "3.1.0"
755 774 source = "registry+https://github.com/rust-lang/crates.io-index"
756 775 dependencies = [
757 776 "cfg-if 0.1.10 (registry+https://github.com/rust-lang/crates.io-index)",
758 777 "libc 0.2.81 (registry+https://github.com/rust-lang/crates.io-index)",
759 778 "rand 0.7.3 (registry+https://github.com/rust-lang/crates.io-index)",
760 779 "redox_syscall 0.1.57 (registry+https://github.com/rust-lang/crates.io-index)",
761 780 "remove_dir_all 0.5.3 (registry+https://github.com/rust-lang/crates.io-index)",
762 781 "winapi 0.3.9 (registry+https://github.com/rust-lang/crates.io-index)",
763 782 ]
764 783
765 784 [[package]]
766 785 name = "termcolor"
767 786 version = "1.1.2"
768 787 source = "registry+https://github.com/rust-lang/crates.io-index"
769 788 dependencies = [
770 789 "winapi-util 0.1.5 (registry+https://github.com/rust-lang/crates.io-index)",
771 790 ]
772 791
773 792 [[package]]
774 793 name = "textwrap"
775 794 version = "0.11.0"
776 795 source = "registry+https://github.com/rust-lang/crates.io-index"
777 796 dependencies = [
778 797 "unicode-width 0.1.8 (registry+https://github.com/rust-lang/crates.io-index)",
779 798 ]
780 799
781 800 [[package]]
782 801 name = "thread_local"
783 802 version = "1.0.1"
784 803 source = "registry+https://github.com/rust-lang/crates.io-index"
785 804 dependencies = [
786 805 "lazy_static 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)",
787 806 ]
788 807
789 808 [[package]]
790 809 name = "time"
791 810 version = "0.1.44"
792 811 source = "registry+https://github.com/rust-lang/crates.io-index"
793 812 dependencies = [
794 813 "libc 0.2.81 (registry+https://github.com/rust-lang/crates.io-index)",
795 814 "wasi 0.10.0+wasi-snapshot-preview1 (registry+https://github.com/rust-lang/crates.io-index)",
796 815 "winapi 0.3.9 (registry+https://github.com/rust-lang/crates.io-index)",
797 816 ]
798 817
799 818 [[package]]
800 819 name = "twox-hash"
801 820 version = "1.6.0"
802 821 source = "registry+https://github.com/rust-lang/crates.io-index"
803 822 dependencies = [
804 823 "cfg-if 0.1.10 (registry+https://github.com/rust-lang/crates.io-index)",
805 824 "rand 0.7.3 (registry+https://github.com/rust-lang/crates.io-index)",
806 825 "static_assertions 1.1.0 (registry+https://github.com/rust-lang/crates.io-index)",
807 826 ]
808 827
809 828 [[package]]
810 829 name = "typenum"
811 830 version = "1.12.0"
812 831 source = "registry+https://github.com/rust-lang/crates.io-index"
813 832
814 833 [[package]]
815 834 name = "unicode-width"
816 835 version = "0.1.8"
817 836 source = "registry+https://github.com/rust-lang/crates.io-index"
818 837
819 838 [[package]]
820 839 name = "unicode-xid"
821 840 version = "0.2.1"
822 841 source = "registry+https://github.com/rust-lang/crates.io-index"
823 842
824 843 [[package]]
825 844 name = "vcpkg"
826 845 version = "0.2.11"
827 846 source = "registry+https://github.com/rust-lang/crates.io-index"
828 847
829 848 [[package]]
830 849 name = "vec_map"
831 850 version = "0.8.2"
832 851 source = "registry+https://github.com/rust-lang/crates.io-index"
833 852
834 853 [[package]]
835 854 name = "version_check"
836 855 version = "0.9.2"
837 856 source = "registry+https://github.com/rust-lang/crates.io-index"
838 857
839 858 [[package]]
840 859 name = "wasi"
841 860 version = "0.9.0+wasi-snapshot-preview1"
842 861 source = "registry+https://github.com/rust-lang/crates.io-index"
843 862
844 863 [[package]]
845 864 name = "wasi"
846 865 version = "0.10.0+wasi-snapshot-preview1"
847 866 source = "registry+https://github.com/rust-lang/crates.io-index"
848 867
849 868 [[package]]
850 869 name = "winapi"
851 870 version = "0.3.9"
852 871 source = "registry+https://github.com/rust-lang/crates.io-index"
853 872 dependencies = [
854 873 "winapi-i686-pc-windows-gnu 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)",
855 874 "winapi-x86_64-pc-windows-gnu 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)",
856 875 ]
857 876
858 877 [[package]]
859 878 name = "winapi-i686-pc-windows-gnu"
860 879 version = "0.4.0"
861 880 source = "registry+https://github.com/rust-lang/crates.io-index"
862 881
863 882 [[package]]
864 883 name = "winapi-util"
865 884 version = "0.1.5"
866 885 source = "registry+https://github.com/rust-lang/crates.io-index"
867 886 dependencies = [
868 887 "winapi 0.3.9 (registry+https://github.com/rust-lang/crates.io-index)",
869 888 ]
870 889
871 890 [[package]]
872 891 name = "winapi-x86_64-pc-windows-gnu"
873 892 version = "0.4.0"
874 893 source = "registry+https://github.com/rust-lang/crates.io-index"
875 894
876 895 [[package]]
877 896 name = "zstd"
878 897 version = "0.5.3+zstd.1.4.5"
879 898 source = "registry+https://github.com/rust-lang/crates.io-index"
880 899 dependencies = [
881 900 "zstd-safe 2.0.5+zstd.1.4.5 (registry+https://github.com/rust-lang/crates.io-index)",
882 901 ]
883 902
884 903 [[package]]
885 904 name = "zstd-safe"
886 905 version = "2.0.5+zstd.1.4.5"
887 906 source = "registry+https://github.com/rust-lang/crates.io-index"
888 907 dependencies = [
889 908 "libc 0.2.81 (registry+https://github.com/rust-lang/crates.io-index)",
890 909 "zstd-sys 1.4.17+zstd.1.4.5 (registry+https://github.com/rust-lang/crates.io-index)",
891 910 ]
892 911
893 912 [[package]]
894 913 name = "zstd-sys"
895 914 version = "1.4.17+zstd.1.4.5"
896 915 source = "registry+https://github.com/rust-lang/crates.io-index"
897 916 dependencies = [
898 917 "cc 1.0.66 (registry+https://github.com/rust-lang/crates.io-index)",
899 918 "glob 0.3.0 (registry+https://github.com/rust-lang/crates.io-index)",
900 919 "itertools 0.9.0 (registry+https://github.com/rust-lang/crates.io-index)",
901 920 "libc 0.2.81 (registry+https://github.com/rust-lang/crates.io-index)",
902 921 ]
903 922
904 923 [metadata]
905 924 "checksum adler 0.2.3 (registry+https://github.com/rust-lang/crates.io-index)" = "ee2a4ec343196209d6594e19543ae87a39f96d5534d7174822a3ad825dd6ed7e"
906 925 "checksum aho-corasick 0.7.15 (registry+https://github.com/rust-lang/crates.io-index)" = "7404febffaa47dac81aa44dba71523c9d069b1bdc50a77db41195149e17f68e5"
907 926 "checksum ansi_term 0.11.0 (registry+https://github.com/rust-lang/crates.io-index)" = "ee49baf6cb617b853aa8d93bf420db2383fab46d314482ca2803b40d5fde979b"
908 927 "checksum atty 0.2.14 (registry+https://github.com/rust-lang/crates.io-index)" = "d9b39be18770d11421cdb1b9947a45dd3f37e93092cbf377614828a319d5fee8"
909 928 "checksum autocfg 1.0.1 (registry+https://github.com/rust-lang/crates.io-index)" = "cdb031dd78e28731d87d56cc8ffef4a8f36ca26c38fe2de700543e627f8a464a"
910 929 "checksum bitflags 1.2.1 (registry+https://github.com/rust-lang/crates.io-index)" = "cf1de2fe8c75bc145a2f577add951f8134889b4795d47466a54a5c846d691693"
911 930 "checksum bitmaps 2.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "031043d04099746d8db04daf1fa424b2bc8bd69d92b25962dcde24da39ab64a2"
912 931 "checksum byteorder 1.3.4 (registry+https://github.com/rust-lang/crates.io-index)" = "08c48aae112d48ed9f069b33538ea9e3e90aa263cfa3d1c24309612b1f7472de"
932 "checksum bytes-cast 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "3196ba300c7bc9282a4331e878496cb3e9603a898a8f1446601317163e16ca52"
933 "checksum bytes-cast-derive 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "cb936af9de38476664d6b58e529aff30d482e4ce1c5e150293d00730b0d81fdb"
913 934 "checksum cc 1.0.66 (registry+https://github.com/rust-lang/crates.io-index)" = "4c0496836a84f8d0495758516b8621a622beb77c0fed418570e50764093ced48"
914 935 "checksum cfg-if 0.1.10 (registry+https://github.com/rust-lang/crates.io-index)" = "4785bdd1c96b2a846b2bd7cc02e86b6b3dbf14e7e53446c4f54c92a361040822"
915 936 "checksum cfg-if 1.0.0 (registry+https://github.com/rust-lang/crates.io-index)" = "baf1de4339761588bc0619e3cbc0120ee582ebb74b53b4efbf79117bd2da40fd"
916 937 "checksum clap 2.33.3 (registry+https://github.com/rust-lang/crates.io-index)" = "37e58ac78573c40708d45522f0d80fa2f01cc4f9b4e2bf749807255454312002"
917 938 "checksum const_fn 0.4.4 (registry+https://github.com/rust-lang/crates.io-index)" = "cd51eab21ab4fd6a3bf889e2d0958c0a6e3a61ad04260325e919e652a2a62826"
918 939 "checksum cpython 0.4.1 (registry+https://github.com/rust-lang/crates.io-index)" = "bfaf3847ab963e40c4f6dd8d6be279bdf74007ae2413786a0dcbb28c52139a95"
919 940 "checksum crc32fast 1.2.1 (registry+https://github.com/rust-lang/crates.io-index)" = "81156fece84ab6a9f2afdb109ce3ae577e42b1228441eded99bd77f627953b1a"
920 941 "checksum crossbeam-channel 0.4.4 (registry+https://github.com/rust-lang/crates.io-index)" = "b153fe7cbef478c567df0f972e02e6d736db11affe43dfc9c56a9374d1adfb87"
921 942 "checksum crossbeam-channel 0.5.0 (registry+https://github.com/rust-lang/crates.io-index)" = "dca26ee1f8d361640700bde38b2c37d8c22b3ce2d360e1fc1c74ea4b0aa7d775"
922 943 "checksum crossbeam-deque 0.8.0 (registry+https://github.com/rust-lang/crates.io-index)" = "94af6efb46fef72616855b036a624cf27ba656ffc9be1b9a3c931cfc7749a9a9"
923 944 "checksum crossbeam-epoch 0.9.1 (registry+https://github.com/rust-lang/crates.io-index)" = "a1aaa739f95311c2c7887a76863f500026092fb1dce0161dab577e559ef3569d"
924 945 "checksum crossbeam-utils 0.7.2 (registry+https://github.com/rust-lang/crates.io-index)" = "c3c7c73a2d1e9fc0886a08b93e98eb643461230d5f1925e4036204d5f2e261a8"
925 946 "checksum crossbeam-utils 0.8.1 (registry+https://github.com/rust-lang/crates.io-index)" = "02d96d1e189ef58269ebe5b97953da3274d83a93af647c2ddd6f9dab28cedb8d"
926 947 "checksum ctor 0.1.16 (registry+https://github.com/rust-lang/crates.io-index)" = "7fbaabec2c953050352311293be5c6aba8e141ba19d6811862b232d6fd020484"
927 948 "checksum difference 2.0.0 (registry+https://github.com/rust-lang/crates.io-index)" = "524cbf6897b527295dff137cec09ecf3a05f4fddffd7dfcd1585403449e74198"
928 949 "checksum either 1.6.1 (registry+https://github.com/rust-lang/crates.io-index)" = "e78d4f1cc4ae33bbfc157ed5d5a5ef3bc29227303d595861deb238fcec4e9457"
929 950 "checksum env_logger 0.7.1 (registry+https://github.com/rust-lang/crates.io-index)" = "44533bbbb3bb3c1fa17d9f2e4e38bbbaf8396ba82193c4cb1b6445d711445d36"
930 951 "checksum flate2 1.0.19 (registry+https://github.com/rust-lang/crates.io-index)" = "7411863d55df97a419aa64cb4d2f167103ea9d767e2c54a1868b7ac3f6b47129"
931 952 "checksum format-bytes 0.1.3 (registry+https://github.com/rust-lang/crates.io-index)" = "1a7374eb574cd29ae45878554298091c554c3286a17b3afa440a3e2710ae0790"
932 953 "checksum format-bytes-macros 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)" = "4edcc04201cea17a0e6b937adebd46b93fba09924c7e6ed8c515a35ce8432cbc"
933 954 "checksum fuchsia-cprng 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "a06f77d526c1a601b7c4cdd98f54b5eaabffc14d5f2f0296febdc7f357c6d3ba"
934 955 "checksum gcc 0.3.55 (registry+https://github.com/rust-lang/crates.io-index)" = "8f5f3913fa0bfe7ee1fd8248b6b9f42a5af4b9d65ec2dd2c3c26132b950ecfc2"
935 956 "checksum getrandom 0.1.15 (registry+https://github.com/rust-lang/crates.io-index)" = "fc587bc0ec293155d5bfa6b9891ec18a1e330c234f896ea47fbada4cadbe47e6"
936 957 "checksum glob 0.3.0 (registry+https://github.com/rust-lang/crates.io-index)" = "9b919933a397b79c37e33b77bb2aa3dc8eb6e165ad809e58ff75bc7db2e34574"
937 958 "checksum hermit-abi 0.1.17 (registry+https://github.com/rust-lang/crates.io-index)" = "5aca5565f760fb5b220e499d72710ed156fdb74e631659e99377d9ebfbd13ae8"
938 959 "checksum hex 0.4.2 (registry+https://github.com/rust-lang/crates.io-index)" = "644f9158b2f133fd50f5fb3242878846d9eb792e445c893805ff0e3824006e35"
939 960 "checksum humantime 1.3.0 (registry+https://github.com/rust-lang/crates.io-index)" = "df004cfca50ef23c36850aaaa59ad52cc70d0e90243c3c7737a4dd32dc7a3c4f"
940 961 "checksum im-rc 15.0.0 (registry+https://github.com/rust-lang/crates.io-index)" = "3ca8957e71f04a205cb162508f9326aea04676c8dfd0711220190d6b83664f3f"
941 962 "checksum itertools 0.9.0 (registry+https://github.com/rust-lang/crates.io-index)" = "284f18f85651fe11e8a991b2adb42cb078325c996ed026d994719efcfca1d54b"
942 963 "checksum jobserver 0.1.21 (registry+https://github.com/rust-lang/crates.io-index)" = "5c71313ebb9439f74b00d9d2dcec36440beaf57a6aa0623068441dd7cd81a7f2"
943 964 "checksum lazy_static 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "e2abad23fbc42b3700f2f279844dc832adb2b2eb069b2df918f455c4e18cc646"
944 965 "checksum libc 0.2.81 (registry+https://github.com/rust-lang/crates.io-index)" = "1482821306169ec4d07f6aca392a4681f66c75c9918aa49641a2595db64053cb"
945 966 "checksum libz-sys 1.1.2 (registry+https://github.com/rust-lang/crates.io-index)" = "602113192b08db8f38796c4e85c39e960c145965140e918018bcde1952429655"
946 967 "checksum log 0.4.11 (registry+https://github.com/rust-lang/crates.io-index)" = "4fabed175da42fed1fa0746b0ea71f412aa9d35e76e95e59b192c64b9dc2bf8b"
947 968 "checksum maybe-uninit 2.0.0 (registry+https://github.com/rust-lang/crates.io-index)" = "60302e4db3a61da70c0cb7991976248362f30319e88850c487b9b95bbf059e00"
948 969 "checksum memchr 2.3.4 (registry+https://github.com/rust-lang/crates.io-index)" = "0ee1c47aaa256ecabcaea351eae4a9b01ef39ed810004e298d2511ed284b1525"
949 970 "checksum memmap 0.7.0 (registry+https://github.com/rust-lang/crates.io-index)" = "6585fd95e7bb50d6cc31e20d4cf9afb4e2ba16c5846fc76793f11218da9c475b"
950 971 "checksum memoffset 0.6.1 (registry+https://github.com/rust-lang/crates.io-index)" = "157b4208e3059a8f9e78d559edc658e13df41410cb3ae03979c83130067fdd87"
951 972 "checksum micro-timer 0.3.1 (registry+https://github.com/rust-lang/crates.io-index)" = "2620153e1d903d26b72b89f0e9c48d8c4756cba941c185461dddc234980c298c"
952 973 "checksum micro-timer-macros 0.3.1 (registry+https://github.com/rust-lang/crates.io-index)" = "e28a3473e6abd6e9aab36aaeef32ad22ae0bd34e79f376643594c2b152ec1c5d"
953 974 "checksum miniz_oxide 0.4.3 (registry+https://github.com/rust-lang/crates.io-index)" = "0f2d26ec3309788e423cfbf68ad1800f061638098d76a83681af979dc4eda19d"
954 975 "checksum num-traits 0.2.14 (registry+https://github.com/rust-lang/crates.io-index)" = "9a64b1ec5cda2586e284722486d802acf1f7dbdc623e2bfc57e65ca1cd099290"
955 976 "checksum num_cpus 1.13.0 (registry+https://github.com/rust-lang/crates.io-index)" = "05499f3756671c15885fee9034446956fff3f243d6077b91e5767df161f766b3"
956 977 "checksum output_vt100 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)" = "53cdc5b785b7a58c5aad8216b3dfa114df64b0b06ae6e1501cef91df2fbdf8f9"
957 978 "checksum pkg-config 0.3.19 (registry+https://github.com/rust-lang/crates.io-index)" = "3831453b3449ceb48b6d9c7ad7c96d5ea673e9b470a1dc578c2ce6521230884c"
958 979 "checksum ppv-lite86 0.2.10 (registry+https://github.com/rust-lang/crates.io-index)" = "ac74c624d6b2d21f425f752262f42188365d7b8ff1aff74c82e45136510a4857"
959 980 "checksum pretty_assertions 0.6.1 (registry+https://github.com/rust-lang/crates.io-index)" = "3f81e1644e1b54f5a68959a29aa86cde704219254669da328ecfdf6a1f09d427"
960 981 "checksum proc-macro-hack 0.5.19 (registry+https://github.com/rust-lang/crates.io-index)" = "dbf0c48bc1d91375ae5c3cd81e3722dff1abcf81a30960240640d223f59fe0e5"
961 982 "checksum proc-macro2 1.0.24 (registry+https://github.com/rust-lang/crates.io-index)" = "1e0704ee1a7e00d7bb417d0770ea303c1bccbabf0ef1667dae92b5967f5f8a71"
962 983 "checksum python27-sys 0.4.1 (registry+https://github.com/rust-lang/crates.io-index)" = "67cb041de8615111bf224dd75667af5f25c6e032118251426fed7f1b70ce4c8c"
963 984 "checksum python3-sys 0.4.1 (registry+https://github.com/rust-lang/crates.io-index)" = "90af11779515a1e530af60782d273b59ac79d33b0e253c071a728563957c76d4"
964 985 "checksum quick-error 1.2.3 (registry+https://github.com/rust-lang/crates.io-index)" = "a1d01941d82fa2ab50be1e79e6714289dd7cde78eba4c074bc5a4374f650dfe0"
965 986 "checksum quote 1.0.7 (registry+https://github.com/rust-lang/crates.io-index)" = "aa563d17ecb180e500da1cfd2b028310ac758de548efdd203e18f283af693f37"
966 987 "checksum rand 0.3.23 (registry+https://github.com/rust-lang/crates.io-index)" = "64ac302d8f83c0c1974bf758f6b041c6c8ada916fbb44a609158ca8b064cc76c"
967 988 "checksum rand 0.4.6 (registry+https://github.com/rust-lang/crates.io-index)" = "552840b97013b1a26992c11eac34bdd778e464601a4c2054b5f0bff7c6761293"
968 989 "checksum rand 0.7.3 (registry+https://github.com/rust-lang/crates.io-index)" = "6a6b1679d49b24bbfe0c803429aa1874472f50d9b363131f0e89fc356b544d03"
969 990 "checksum rand_chacha 0.2.2 (registry+https://github.com/rust-lang/crates.io-index)" = "f4c8ed856279c9737206bf725bf36935d8666ead7aa69b52be55af369d193402"
970 991 "checksum rand_core 0.3.1 (registry+https://github.com/rust-lang/crates.io-index)" = "7a6fdeb83b075e8266dcc8762c22776f6877a63111121f5f8c7411e5be7eed4b"
971 992 "checksum rand_core 0.4.2 (registry+https://github.com/rust-lang/crates.io-index)" = "9c33a3c44ca05fa6f1807d8e6743f3824e8509beca625669633be0acbdf509dc"
972 993 "checksum rand_core 0.5.1 (registry+https://github.com/rust-lang/crates.io-index)" = "90bde5296fc891b0cef12a6d03ddccc162ce7b2aff54160af9338f8d40df6d19"
973 994 "checksum rand_distr 0.2.2 (registry+https://github.com/rust-lang/crates.io-index)" = "96977acbdd3a6576fb1d27391900035bf3863d4a16422973a409b488cf29ffb2"
974 995 "checksum rand_hc 0.2.0 (registry+https://github.com/rust-lang/crates.io-index)" = "ca3129af7b92a17112d59ad498c6f81eaf463253766b90396d39ea7a39d6613c"
975 996 "checksum rand_pcg 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)" = "16abd0c1b639e9eb4d7c50c0b8100b0d0f849be2349829c740fe8e6eb4816429"
976 997 "checksum rand_xoshiro 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "a9fcdd2e881d02f1d9390ae47ad8e5696a9e4be7b547a1da2afbc61973217004"
977 998 "checksum rayon 1.5.0 (registry+https://github.com/rust-lang/crates.io-index)" = "8b0d8e0819fadc20c74ea8373106ead0600e3a67ef1fe8da56e39b9ae7275674"
978 999 "checksum rayon-core 1.9.0 (registry+https://github.com/rust-lang/crates.io-index)" = "9ab346ac5921dc62ffa9f89b7a773907511cdfa5490c572ae9be1be33e8afa4a"
979 1000 "checksum rdrand 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "678054eb77286b51581ba43620cc911abf02758c91f93f479767aed0f90458b2"
980 1001 "checksum redox_syscall 0.1.57 (registry+https://github.com/rust-lang/crates.io-index)" = "41cc0f7e4d5d4544e8861606a285bb08d3e70712ccc7d2b84d7c0ccfaf4b05ce"
981 1002 "checksum regex 1.4.2 (registry+https://github.com/rust-lang/crates.io-index)" = "38cf2c13ed4745de91a5eb834e11c00bcc3709e773173b2ce4c56c9fbde04b9c"
982 1003 "checksum regex-syntax 0.6.21 (registry+https://github.com/rust-lang/crates.io-index)" = "3b181ba2dcf07aaccad5448e8ead58db5b742cf85dfe035e2227f137a539a189"
983 1004 "checksum remove_dir_all 0.5.3 (registry+https://github.com/rust-lang/crates.io-index)" = "3acd125665422973a33ac9d3dd2df85edad0f4ae9b00dafb1a05e43a9f5ef8e7"
984 1005 "checksum rust-crypto 0.2.36 (registry+https://github.com/rust-lang/crates.io-index)" = "f76d05d3993fd5f4af9434e8e436db163a12a9d40e1a58a726f27a01dfd12a2a"
985 1006 "checksum rustc-serialize 0.3.24 (registry+https://github.com/rust-lang/crates.io-index)" = "dcf128d1287d2ea9d80910b5f1120d0b8eede3fbf1abe91c40d39ea7d51e6fda"
986 1007 "checksum same-file 1.0.6 (registry+https://github.com/rust-lang/crates.io-index)" = "93fc1dc3aaa9bfed95e02e6eadabb4baf7e3078b0bd1b4d7b6b0b68378900502"
987 1008 "checksum scopeguard 1.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "d29ab0c6d3fc0ee92fe66e2d99f700eab17a8d57d1c1d3b748380fb20baa78cd"
988 1009 "checksum sized-chunks 0.6.2 (registry+https://github.com/rust-lang/crates.io-index)" = "1ec31ceca5644fa6d444cc77548b88b67f46db6f7c71683b0f9336e671830d2f"
989 1010 "checksum static_assertions 1.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "a2eb9349b6444b326872e140eb1cf5e7c522154d69e7a0ffb0fb81c06b37543f"
990 1011 "checksum strsim 0.8.0 (registry+https://github.com/rust-lang/crates.io-index)" = "8ea5119cdb4c55b55d432abb513a0429384878c15dde60cc77b1c99de1a95a6a"
991 1012 "checksum syn 1.0.54 (registry+https://github.com/rust-lang/crates.io-index)" = "9a2af957a63d6bd42255c359c93d9bfdb97076bd3b820897ce55ffbfbf107f44"
992 1013 "checksum tempfile 3.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "7a6e24d9338a0a5be79593e2fa15a648add6138caa803e2d5bc782c371732ca9"
993 1014 "checksum termcolor 1.1.2 (registry+https://github.com/rust-lang/crates.io-index)" = "2dfed899f0eb03f32ee8c6a0aabdb8a7949659e3466561fc0adf54e26d88c5f4"
994 1015 "checksum textwrap 0.11.0 (registry+https://github.com/rust-lang/crates.io-index)" = "d326610f408c7a4eb6f51c37c330e496b08506c9457c9d34287ecc38809fb060"
995 1016 "checksum thread_local 1.0.1 (registry+https://github.com/rust-lang/crates.io-index)" = "d40c6d1b69745a6ec6fb1ca717914848da4b44ae29d9b3080cbee91d72a69b14"
996 1017 "checksum time 0.1.44 (registry+https://github.com/rust-lang/crates.io-index)" = "6db9e6914ab8b1ae1c260a4ae7a49b6c5611b40328a735b21862567685e73255"
997 1018 "checksum twox-hash 1.6.0 (registry+https://github.com/rust-lang/crates.io-index)" = "04f8ab788026715fa63b31960869617cba39117e520eb415b0139543e325ab59"
998 1019 "checksum typenum 1.12.0 (registry+https://github.com/rust-lang/crates.io-index)" = "373c8a200f9e67a0c95e62a4f52fbf80c23b4381c05a17845531982fa99e6b33"
999 1020 "checksum unicode-width 0.1.8 (registry+https://github.com/rust-lang/crates.io-index)" = "9337591893a19b88d8d87f2cec1e73fad5cdfd10e5a6f349f498ad6ea2ffb1e3"
1000 1021 "checksum unicode-xid 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)" = "f7fe0bb3479651439c9112f72b6c505038574c9fbb575ed1bf3b797fa39dd564"
1001 1022 "checksum vcpkg 0.2.11 (registry+https://github.com/rust-lang/crates.io-index)" = "b00bca6106a5e23f3eee943593759b7fcddb00554332e856d990c893966879fb"
1002 1023 "checksum vec_map 0.8.2 (registry+https://github.com/rust-lang/crates.io-index)" = "f1bddf1187be692e79c5ffeab891132dfb0f236ed36a43c7ed39f1165ee20191"
1003 1024 "checksum version_check 0.9.2 (registry+https://github.com/rust-lang/crates.io-index)" = "b5a972e5669d67ba988ce3dc826706fb0a8b01471c088cb0b6110b805cc36aed"
1004 1025 "checksum wasi 0.10.0+wasi-snapshot-preview1 (registry+https://github.com/rust-lang/crates.io-index)" = "1a143597ca7c7793eff794def352d41792a93c481eb1042423ff7ff72ba2c31f"
1005 1026 "checksum wasi 0.9.0+wasi-snapshot-preview1 (registry+https://github.com/rust-lang/crates.io-index)" = "cccddf32554fecc6acb585f82a32a72e28b48f8c4c1883ddfeeeaa96f7d8e519"
1006 1027 "checksum winapi 0.3.9 (registry+https://github.com/rust-lang/crates.io-index)" = "5c839a674fcd7a98952e593242ea400abe93992746761e38641405d28b00f419"
1007 1028 "checksum winapi-i686-pc-windows-gnu 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "ac3b87c63620426dd9b991e5ce0329eff545bccbbb34f3be09ff6fb6ab51b7b6"
1008 1029 "checksum winapi-util 0.1.5 (registry+https://github.com/rust-lang/crates.io-index)" = "70ec6ce85bb158151cae5e5c87f95a8e97d2c0c4b001223f33a334e3ce5de178"
1009 1030 "checksum winapi-x86_64-pc-windows-gnu 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "712e227841d057c1ee1cd2fb22fa7e5a5461ae8e48fa2ca79ec42cfc1931183f"
1010 1031 "checksum zstd 0.5.3+zstd.1.4.5 (registry+https://github.com/rust-lang/crates.io-index)" = "01b32eaf771efa709e8308605bbf9319bf485dc1503179ec0469b611937c0cd8"
1011 1032 "checksum zstd-safe 2.0.5+zstd.1.4.5 (registry+https://github.com/rust-lang/crates.io-index)" = "1cfb642e0d27f64729a639c52db457e0ae906e7bc6f5fe8f5c453230400f1055"
1012 1033 "checksum zstd-sys 1.4.17+zstd.1.4.5 (registry+https://github.com/rust-lang/crates.io-index)" = "b89249644df056b522696b1bb9e7c18c87e8ffa3e2f0dc3b0155875d6498f01b"
@@ -1,48 +1,49 b''
1 1 [package]
2 2 name = "hg-core"
3 3 version = "0.1.0"
4 4 authors = ["Georges Racinet <gracinet@anybox.fr>"]
5 5 description = "Mercurial pure Rust core library, with no assumption on Python bindings (FFI)"
6 6 edition = "2018"
7 7
8 8 [lib]
9 9 name = "hg"
10 10
11 11 [dependencies]
12 bytes-cast = "0.1"
12 13 byteorder = "1.3.4"
13 14 hex = "0.4.2"
14 15 im-rc = "15.0.*"
15 16 lazy_static = "1.4.0"
16 17 memchr = "2.3.3"
17 18 rand = "0.7.3"
18 19 rand_pcg = "0.2.1"
19 20 rand_distr = "0.2.2"
20 21 rayon = "1.3.0"
21 22 regex = "1.3.9"
22 23 twox-hash = "1.5.0"
23 24 same-file = "1.0.6"
24 25 crossbeam-channel = "0.4"
25 26 micro-timer = "0.3.0"
26 27 log = "0.4.8"
27 28 memmap = "0.7.0"
28 29 zstd = "0.5.3"
29 30 rust-crypto = "0.2.36"
30 31 format-bytes = "0.1.2"
31 32
32 33 # We don't use the `miniz-oxide` backend to not change rhg benchmarks and until
33 34 # we have a clearer view of which backend is the fastest.
34 35 [dependencies.flate2]
35 36 version = "1.0.16"
36 37 features = ["zlib"]
37 38 default-features = false
38 39
39 40 [dev-dependencies]
40 41 clap = "*"
41 42 pretty_assertions = "0.6.1"
42 43 tempfile = "3.1.0"
43 44
44 45 [features]
45 46 # Use a (still unoptimized) tree for the dirstate instead of the current flat
46 47 # dirstate. This is not yet recommended for performance reasons. A future
47 48 # version might make it the default, or make it a runtime option.
48 49 dirstate-tree = []
@@ -1,1118 +1,1101 b''
1 1 // Copyright 2018-2020 Georges Racinet <georges.racinet@octobus.net>
2 2 // and Mercurial contributors
3 3 //
4 4 // This software may be used and distributed according to the terms of the
5 5 // GNU General Public License version 2 or any later version.
6 6 //! Indexing facilities for fast retrieval of `Revision` from `Node`
7 7 //!
8 8 //! This provides a variation on the 16-ary radix tree that is
9 9 //! provided as "nodetree" in revlog.c, ready for append-only persistence
10 10 //! on disk.
11 11 //!
12 12 //! Following existing implicit conventions, the "nodemap" terminology
13 13 //! is used in a more abstract context.
14 14
15 15 use super::{
16 16 node::NULL_NODE, Node, NodeError, NodePrefix, NodePrefixRef, Revision,
17 17 RevlogIndex, NULL_REVISION,
18 18 };
19 19
20 use bytes_cast::{unaligned, BytesCast};
20 21 use std::cmp::max;
21 22 use std::fmt;
22 use std::mem;
23 use std::mem::{self, align_of, size_of};
23 24 use std::ops::Deref;
24 25 use std::ops::Index;
25 use std::slice;
26 26
27 27 #[derive(Debug, PartialEq)]
28 28 pub enum NodeMapError {
29 29 MultipleResults,
30 30 InvalidNodePrefix(NodeError),
31 31 /// A `Revision` stored in the nodemap could not be found in the index
32 32 RevisionNotInIndex(Revision),
33 33 }
34 34
35 35 impl From<NodeError> for NodeMapError {
36 36 fn from(err: NodeError) -> Self {
37 37 NodeMapError::InvalidNodePrefix(err)
38 38 }
39 39 }
40 40
41 41 /// Mapping system from Mercurial nodes to revision numbers.
42 42 ///
43 43 /// ## `RevlogIndex` and `NodeMap`
44 44 ///
45 45 /// One way to think about their relationship is that
46 46 /// the `NodeMap` is a prefix-oriented reverse index of the `Node` information
47 47 /// carried by a [`RevlogIndex`].
48 48 ///
49 49 /// Many of the methods in this trait take a `RevlogIndex` argument
50 50 /// which is used for validation of their results. This index must naturally
51 51 /// be the one the `NodeMap` is about, and it must be consistent.
52 52 ///
53 53 /// Notably, the `NodeMap` must not store
54 54 /// information about more `Revision` values than there are in the index.
55 55 /// In these methods, an encountered `Revision` is not in the index, a
56 56 /// [`RevisionNotInIndex`] error is returned.
57 57 ///
58 58 /// In insert operations, the rule is thus that the `NodeMap` must always
59 59 /// be updated after the `RevlogIndex`
60 60 /// be updated first, and the `NodeMap` second.
61 61 ///
62 62 /// [`RevisionNotInIndex`]: enum.NodeMapError.html#variant.RevisionNotInIndex
63 63 /// [`RevlogIndex`]: ../trait.RevlogIndex.html
64 64 pub trait NodeMap {
65 65 /// Find the unique `Revision` having the given `Node`
66 66 ///
67 67 /// If no Revision matches the given `Node`, `Ok(None)` is returned.
68 68 fn find_node(
69 69 &self,
70 70 index: &impl RevlogIndex,
71 71 node: &Node,
72 72 ) -> Result<Option<Revision>, NodeMapError> {
73 73 self.find_bin(index, node.into())
74 74 }
75 75
76 76 /// Find the unique Revision whose `Node` starts with a given binary prefix
77 77 ///
78 78 /// If no Revision matches the given prefix, `Ok(None)` is returned.
79 79 ///
80 80 /// If several Revisions match the given prefix, a [`MultipleResults`]
81 81 /// error is returned.
82 82 fn find_bin<'a>(
83 83 &self,
84 84 idx: &impl RevlogIndex,
85 85 prefix: NodePrefixRef<'a>,
86 86 ) -> Result<Option<Revision>, NodeMapError>;
87 87
88 88 /// Find the unique Revision whose `Node` hexadecimal string representation
89 89 /// starts with a given prefix
90 90 ///
91 91 /// If no Revision matches the given prefix, `Ok(None)` is returned.
92 92 ///
93 93 /// If several Revisions match the given prefix, a [`MultipleResults`]
94 94 /// error is returned.
95 95 fn find_hex(
96 96 &self,
97 97 idx: &impl RevlogIndex,
98 98 prefix: &str,
99 99 ) -> Result<Option<Revision>, NodeMapError> {
100 100 self.find_bin(idx, NodePrefix::from_hex(prefix)?.borrow())
101 101 }
102 102
103 103 /// Give the size of the shortest node prefix that determines
104 104 /// the revision uniquely.
105 105 ///
106 106 /// From a binary node prefix, if it is matched in the node map, this
107 107 /// returns the number of hexadecimal digits that would had sufficed
108 108 /// to find the revision uniquely.
109 109 ///
110 110 /// Returns `None` if no `Revision` could be found for the prefix.
111 111 ///
112 112 /// If several Revisions match the given prefix, a [`MultipleResults`]
113 113 /// error is returned.
114 114 fn unique_prefix_len_bin<'a>(
115 115 &self,
116 116 idx: &impl RevlogIndex,
117 117 node_prefix: NodePrefixRef<'a>,
118 118 ) -> Result<Option<usize>, NodeMapError>;
119 119
120 120 /// Same as `unique_prefix_len_bin`, with the hexadecimal representation
121 121 /// of the prefix as input.
122 122 fn unique_prefix_len_hex(
123 123 &self,
124 124 idx: &impl RevlogIndex,
125 125 prefix: &str,
126 126 ) -> Result<Option<usize>, NodeMapError> {
127 127 self.unique_prefix_len_bin(idx, NodePrefix::from_hex(prefix)?.borrow())
128 128 }
129 129
130 130 /// Same as `unique_prefix_len_bin`, with a full `Node` as input
131 131 fn unique_prefix_len_node(
132 132 &self,
133 133 idx: &impl RevlogIndex,
134 134 node: &Node,
135 135 ) -> Result<Option<usize>, NodeMapError> {
136 136 self.unique_prefix_len_bin(idx, node.into())
137 137 }
138 138 }
139 139
140 140 pub trait MutableNodeMap: NodeMap {
141 141 fn insert<I: RevlogIndex>(
142 142 &mut self,
143 143 index: &I,
144 144 node: &Node,
145 145 rev: Revision,
146 146 ) -> Result<(), NodeMapError>;
147 147 }
148 148
149 149 /// Low level NodeTree [`Blocks`] elements
150 150 ///
151 151 /// These are exactly as for instance on persistent storage.
152 type RawElement = i32;
152 type RawElement = unaligned::I32Be;
153 153
154 154 /// High level representation of values in NodeTree
155 155 /// [`Blocks`](struct.Block.html)
156 156 ///
157 157 /// This is the high level representation that most algorithms should
158 158 /// use.
159 159 #[derive(Clone, Debug, Eq, PartialEq)]
160 160 enum Element {
161 161 Rev(Revision),
162 162 Block(usize),
163 163 None,
164 164 }
165 165
166 166 impl From<RawElement> for Element {
167 167 /// Conversion from low level representation, after endianness conversion.
168 168 ///
169 169 /// See [`Block`](struct.Block.html) for explanation about the encoding.
170 170 fn from(raw: RawElement) -> Element {
171 if raw >= 0 {
172 Element::Block(raw as usize)
173 } else if raw == -1 {
171 let int = raw.get();
172 if int >= 0 {
173 Element::Block(int as usize)
174 } else if int == -1 {
174 175 Element::None
175 176 } else {
176 Element::Rev(-raw - 2)
177 Element::Rev(-int - 2)
177 178 }
178 179 }
179 180 }
180 181
181 182 impl From<Element> for RawElement {
182 183 fn from(element: Element) -> RawElement {
183 match element {
184 RawElement::from(match element {
184 185 Element::None => 0,
185 Element::Block(i) => i as RawElement,
186 Element::Block(i) => i as i32,
186 187 Element::Rev(rev) => -rev - 2,
187 }
188 })
188 189 }
189 190 }
190 191
191 192 /// A logical block of the `NodeTree`, packed with a fixed size.
192 193 ///
193 194 /// These are always used in container types implementing `Index<Block>`,
194 195 /// such as `&Block`
195 196 ///
196 197 /// As an array of integers, its ith element encodes that the
197 198 /// ith potential edge from the block, representing the ith hexadecimal digit
198 199 /// (nybble) `i` is either:
199 200 ///
200 201 /// - absent (value -1)
201 202 /// - another `Block` in the same indexable container (value β‰₯ 0)
202 203 /// - a `Revision` leaf (value ≀ -2)
203 204 ///
204 205 /// Endianness has to be fixed for consistency on shared storage across
205 206 /// different architectures.
206 207 ///
207 208 /// A key difference with the C `nodetree` is that we need to be
208 209 /// able to represent the [`Block`] at index 0, hence -1 is the empty marker
209 210 /// rather than 0 and the `Revision` range upper limit of -2 instead of -1.
210 211 ///
211 212 /// Another related difference is that `NULL_REVISION` (-1) is not
212 213 /// represented at all, because we want an immutable empty nodetree
213 214 /// to be valid.
214 215
215 #[derive(Copy, Clone)]
216 pub struct Block([u8; BLOCK_SIZE]);
216 const ELEMENTS_PER_BLOCK: usize = 16; // number of different values in a nybble
217 217
218 /// Not derivable for arrays of length >32 until const generics are stable
219 impl PartialEq for Block {
220 fn eq(&self, other: &Self) -> bool {
221 self.0[..] == other.0[..]
222 }
223 }
224
225 pub const BLOCK_SIZE: usize = 64;
218 #[derive(Copy, Clone, BytesCast, PartialEq)]
219 #[repr(transparent)]
220 pub struct Block([RawElement; ELEMENTS_PER_BLOCK]);
226 221
227 222 impl Block {
228 223 fn new() -> Self {
229 // -1 in 2's complement to create an absent node
230 let byte: u8 = 255;
231 Block([byte; BLOCK_SIZE])
224 let absent_node = RawElement::from(-1);
225 Block([absent_node; ELEMENTS_PER_BLOCK])
232 226 }
233 227
234 228 fn get(&self, nybble: u8) -> Element {
235 let index = nybble as usize * mem::size_of::<RawElement>();
236 Element::from(RawElement::from_be_bytes([
237 self.0[index],
238 self.0[index + 1],
239 self.0[index + 2],
240 self.0[index + 3],
241 ]))
229 self.0[nybble as usize].into()
242 230 }
243 231
244 232 fn set(&mut self, nybble: u8, element: Element) {
245 let values = RawElement::to_be_bytes(element.into());
246 let index = nybble as usize * mem::size_of::<RawElement>();
247 self.0[index] = values[0];
248 self.0[index + 1] = values[1];
249 self.0[index + 2] = values[2];
250 self.0[index + 3] = values[3];
233 self.0[nybble as usize] = element.into()
251 234 }
252 235 }
253 236
254 237 impl fmt::Debug for Block {
255 238 /// sparse representation for testing and debugging purposes
256 239 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
257 240 f.debug_map()
258 241 .entries((0..16).filter_map(|i| match self.get(i) {
259 242 Element::None => None,
260 243 element => Some((i, element)),
261 244 }))
262 245 .finish()
263 246 }
264 247 }
265 248
266 249 /// A mutable 16-radix tree with the root block logically at the end
267 250 ///
268 251 /// Because of the append only nature of our node trees, we need to
269 252 /// keep the original untouched and store new blocks separately.
270 253 ///
271 254 /// The mutable root `Block` is kept apart so that we don't have to rebump
272 255 /// it on each insertion.
273 256 pub struct NodeTree {
274 257 readonly: Box<dyn Deref<Target = [Block]> + Send>,
275 258 growable: Vec<Block>,
276 259 root: Block,
277 260 masked_inner_blocks: usize,
278 261 }
279 262
280 263 impl Index<usize> for NodeTree {
281 264 type Output = Block;
282 265
283 266 fn index(&self, i: usize) -> &Block {
284 267 let ro_len = self.readonly.len();
285 268 if i < ro_len {
286 269 &self.readonly[i]
287 270 } else if i == ro_len + self.growable.len() {
288 271 &self.root
289 272 } else {
290 273 &self.growable[i - ro_len]
291 274 }
292 275 }
293 276 }
294 277
295 278 /// Return `None` unless the `Node` for `rev` has given prefix in `index`.
296 279 fn has_prefix_or_none(
297 280 idx: &impl RevlogIndex,
298 281 prefix: NodePrefixRef,
299 282 rev: Revision,
300 283 ) -> Result<Option<Revision>, NodeMapError> {
301 284 idx.node(rev)
302 285 .ok_or_else(|| NodeMapError::RevisionNotInIndex(rev))
303 286 .map(|node| {
304 287 if prefix.is_prefix_of(node) {
305 288 Some(rev)
306 289 } else {
307 290 None
308 291 }
309 292 })
310 293 }
311 294
312 295 /// validate that the candidate's node starts indeed with given prefix,
313 296 /// and treat ambiguities related to `NULL_REVISION`.
314 297 ///
315 298 /// From the data in the NodeTree, one can only conclude that some
316 299 /// revision is the only one for a *subprefix* of the one being looked up.
317 300 fn validate_candidate(
318 301 idx: &impl RevlogIndex,
319 302 prefix: NodePrefixRef,
320 303 candidate: (Option<Revision>, usize),
321 304 ) -> Result<(Option<Revision>, usize), NodeMapError> {
322 305 let (rev, steps) = candidate;
323 306 if let Some(nz_nybble) = prefix.first_different_nybble(&NULL_NODE) {
324 307 rev.map_or(Ok((None, steps)), |r| {
325 308 has_prefix_or_none(idx, prefix, r)
326 309 .map(|opt| (opt, max(steps, nz_nybble + 1)))
327 310 })
328 311 } else {
329 312 // the prefix is only made of zeros; NULL_REVISION always matches it
330 313 // and any other *valid* result is an ambiguity
331 314 match rev {
332 315 None => Ok((Some(NULL_REVISION), steps + 1)),
333 316 Some(r) => match has_prefix_or_none(idx, prefix, r)? {
334 317 None => Ok((Some(NULL_REVISION), steps + 1)),
335 318 _ => Err(NodeMapError::MultipleResults),
336 319 },
337 320 }
338 321 }
339 322 }
340 323
341 324 impl NodeTree {
342 325 /// Initiate a NodeTree from an immutable slice-like of `Block`
343 326 ///
344 327 /// We keep `readonly` and clone its root block if it isn't empty.
345 328 fn new(readonly: Box<dyn Deref<Target = [Block]> + Send>) -> Self {
346 329 let root = readonly.last().cloned().unwrap_or_else(Block::new);
347 330 NodeTree {
348 331 readonly,
349 332 growable: Vec::new(),
350 333 root,
351 334 masked_inner_blocks: 0,
352 335 }
353 336 }
354 337
355 338 /// Create from an opaque bunch of bytes
356 339 ///
357 340 /// The created `NodeTreeBytes` from `buffer`,
358 341 /// of which exactly `amount` bytes are used.
359 342 ///
360 343 /// - `buffer` could be derived from `PyBuffer` and `Mmap` objects.
361 344 /// - `offset` allows for the final file format to include fixed data
362 345 /// (generation number, behavioural flags)
363 346 /// - `amount` is expressed in bytes, and is not automatically derived from
364 347 /// `bytes`, so that a caller that manages them atomically can perform
365 348 /// temporary disk serializations and still rollback easily if needed.
366 349 /// First use-case for this would be to support Mercurial shell hooks.
367 350 ///
368 351 /// panics if `buffer` is smaller than `amount`
369 352 pub fn load_bytes(
370 353 bytes: Box<dyn Deref<Target = [u8]> + Send>,
371 354 amount: usize,
372 355 ) -> Self {
373 356 NodeTree::new(Box::new(NodeTreeBytes::new(bytes, amount)))
374 357 }
375 358
376 359 /// Retrieve added `Block` and the original immutable data
377 360 pub fn into_readonly_and_added(
378 361 self,
379 362 ) -> (Box<dyn Deref<Target = [Block]> + Send>, Vec<Block>) {
380 363 let mut vec = self.growable;
381 364 let readonly = self.readonly;
382 365 if readonly.last() != Some(&self.root) {
383 366 vec.push(self.root);
384 367 }
385 368 (readonly, vec)
386 369 }
387 370
388 371 /// Retrieve added `Blocks` as bytes, ready to be written to persistent
389 372 /// storage
390 373 pub fn into_readonly_and_added_bytes(
391 374 self,
392 375 ) -> (Box<dyn Deref<Target = [Block]> + Send>, Vec<u8>) {
393 376 let (readonly, vec) = self.into_readonly_and_added();
394 377 // Prevent running `v`'s destructor so we are in complete control
395 378 // of the allocation.
396 379 let vec = mem::ManuallyDrop::new(vec);
397 380
398 381 // Transmute the `Vec<Block>` to a `Vec<u8>`. Blocks are contiguous
399 382 // bytes, so this is perfectly safe.
400 383 let bytes = unsafe {
401 // Assert that `Block` hasn't been changed and has no padding
402 let _: [u8; 4 * BLOCK_SIZE] =
403 std::mem::transmute([Block::new(); 4]);
384 // Check for compatible allocation layout.
385 // (Optimized away by constant-folding + dead code elimination.)
386 assert_eq!(size_of::<Block>(), 64);
387 assert_eq!(align_of::<Block>(), 1);
404 388
405 389 // /!\ Any use of `vec` after this is use-after-free.
406 390 // TODO: use `into_raw_parts` once stabilized
407 391 Vec::from_raw_parts(
408 392 vec.as_ptr() as *mut u8,
409 vec.len() * BLOCK_SIZE,
410 vec.capacity() * BLOCK_SIZE,
393 vec.len() * size_of::<Block>(),
394 vec.capacity() * size_of::<Block>(),
411 395 )
412 396 };
413 397 (readonly, bytes)
414 398 }
415 399
416 400 /// Total number of blocks
417 401 fn len(&self) -> usize {
418 402 self.readonly.len() + self.growable.len() + 1
419 403 }
420 404
421 405 /// Implemented for completeness
422 406 ///
423 407 /// A `NodeTree` always has at least the mutable root block.
424 408 #[allow(dead_code)]
425 409 fn is_empty(&self) -> bool {
426 410 false
427 411 }
428 412
429 413 /// Main working method for `NodeTree` searches
430 414 ///
431 415 /// The first returned value is the result of analysing `NodeTree` data
432 416 /// *alone*: whereas `None` guarantees that the given prefix is absent
433 417 /// from the `NodeTree` data (but still could match `NULL_NODE`), with
434 418 /// `Some(rev)`, it is to be understood that `rev` is the unique `Revision`
435 419 /// that could match the prefix. Actually, all that can be inferred from
436 420 /// the `NodeTree` data is that `rev` is the revision with the longest
437 421 /// common node prefix with the given prefix.
438 422 ///
439 423 /// The second returned value is the size of the smallest subprefix
440 424 /// of `prefix` that would give the same result, i.e. not the
441 425 /// `MultipleResults` error variant (again, using only the data of the
442 426 /// `NodeTree`).
443 427 fn lookup(
444 428 &self,
445 429 prefix: NodePrefixRef,
446 430 ) -> Result<(Option<Revision>, usize), NodeMapError> {
447 431 for (i, visit_item) in self.visit(prefix).enumerate() {
448 432 if let Some(opt) = visit_item.final_revision() {
449 433 return Ok((opt, i + 1));
450 434 }
451 435 }
452 436 Err(NodeMapError::MultipleResults)
453 437 }
454 438
455 439 fn visit<'n, 'p>(
456 440 &'n self,
457 441 prefix: NodePrefixRef<'p>,
458 442 ) -> NodeTreeVisitor<'n, 'p> {
459 443 NodeTreeVisitor {
460 444 nt: self,
461 445 prefix,
462 446 visit: self.len() - 1,
463 447 nybble_idx: 0,
464 448 done: false,
465 449 }
466 450 }
467 451 /// Return a mutable reference for `Block` at index `idx`.
468 452 ///
469 453 /// If `idx` lies in the immutable area, then the reference is to
470 454 /// a newly appended copy.
471 455 ///
472 456 /// Returns (new_idx, glen, mut_ref) where
473 457 ///
474 458 /// - `new_idx` is the index of the mutable `Block`
475 459 /// - `mut_ref` is a mutable reference to the mutable Block.
476 460 /// - `glen` is the new length of `self.growable`
477 461 ///
478 462 /// Note: the caller wouldn't be allowed to query `self.growable.len()`
479 463 /// itself because of the mutable borrow taken with the returned `Block`
480 464 fn mutable_block(&mut self, idx: usize) -> (usize, &mut Block, usize) {
481 465 let ro_blocks = &self.readonly;
482 466 let ro_len = ro_blocks.len();
483 467 let glen = self.growable.len();
484 468 if idx < ro_len {
485 469 self.masked_inner_blocks += 1;
486 470 self.growable.push(ro_blocks[idx]);
487 471 (glen + ro_len, &mut self.growable[glen], glen + 1)
488 472 } else if glen + ro_len == idx {
489 473 (idx, &mut self.root, glen)
490 474 } else {
491 475 (idx, &mut self.growable[idx - ro_len], glen)
492 476 }
493 477 }
494 478
495 479 /// Main insertion method
496 480 ///
497 481 /// This will dive in the node tree to find the deepest `Block` for
498 482 /// `node`, split it as much as needed and record `node` in there.
499 483 /// The method then backtracks, updating references in all the visited
500 484 /// blocks from the root.
501 485 ///
502 486 /// All the mutated `Block` are copied first to the growable part if
503 487 /// needed. That happens for those in the immutable part except the root.
504 488 pub fn insert<I: RevlogIndex>(
505 489 &mut self,
506 490 index: &I,
507 491 node: &Node,
508 492 rev: Revision,
509 493 ) -> Result<(), NodeMapError> {
510 494 let ro_len = &self.readonly.len();
511 495
512 496 let mut visit_steps: Vec<_> = self.visit(node.into()).collect();
513 497 let read_nybbles = visit_steps.len();
514 498 // visit_steps cannot be empty, since we always visit the root block
515 499 let deepest = visit_steps.pop().unwrap();
516 500
517 501 let (mut block_idx, mut block, mut glen) =
518 502 self.mutable_block(deepest.block_idx);
519 503
520 504 if let Element::Rev(old_rev) = deepest.element {
521 505 let old_node = index
522 506 .node(old_rev)
523 507 .ok_or_else(|| NodeMapError::RevisionNotInIndex(old_rev))?;
524 508 if old_node == node {
525 509 return Ok(()); // avoid creating lots of useless blocks
526 510 }
527 511
528 512 // Looping over the tail of nybbles in both nodes, creating
529 513 // new blocks until we find the difference
530 514 let mut new_block_idx = ro_len + glen;
531 515 let mut nybble = deepest.nybble;
532 516 for nybble_pos in read_nybbles..node.nybbles_len() {
533 517 block.set(nybble, Element::Block(new_block_idx));
534 518
535 519 let new_nybble = node.get_nybble(nybble_pos);
536 520 let old_nybble = old_node.get_nybble(nybble_pos);
537 521
538 522 if old_nybble == new_nybble {
539 523 self.growable.push(Block::new());
540 524 block = &mut self.growable[glen];
541 525 glen += 1;
542 526 new_block_idx += 1;
543 527 nybble = new_nybble;
544 528 } else {
545 529 let mut new_block = Block::new();
546 530 new_block.set(old_nybble, Element::Rev(old_rev));
547 531 new_block.set(new_nybble, Element::Rev(rev));
548 532 self.growable.push(new_block);
549 533 break;
550 534 }
551 535 }
552 536 } else {
553 537 // Free slot in the deepest block: no splitting has to be done
554 538 block.set(deepest.nybble, Element::Rev(rev));
555 539 }
556 540
557 541 // Backtrack over visit steps to update references
558 542 while let Some(visited) = visit_steps.pop() {
559 543 let to_write = Element::Block(block_idx);
560 544 if visit_steps.is_empty() {
561 545 self.root.set(visited.nybble, to_write);
562 546 break;
563 547 }
564 548 let (new_idx, block, _) = self.mutable_block(visited.block_idx);
565 549 if block.get(visited.nybble) == to_write {
566 550 break;
567 551 }
568 552 block.set(visited.nybble, to_write);
569 553 block_idx = new_idx;
570 554 }
571 555 Ok(())
572 556 }
573 557
574 558 /// Make the whole `NodeTree` logically empty, without touching the
575 559 /// immutable part.
576 560 pub fn invalidate_all(&mut self) {
577 561 self.root = Block::new();
578 562 self.growable = Vec::new();
579 563 self.masked_inner_blocks = self.readonly.len();
580 564 }
581 565
582 566 /// Return the number of blocks in the readonly part that are currently
583 567 /// masked in the mutable part.
584 568 ///
585 569 /// The `NodeTree` structure has no efficient way to know how many blocks
586 570 /// are already unreachable in the readonly part.
587 571 ///
588 572 /// After a call to `invalidate_all()`, the returned number can be actually
589 573 /// bigger than the whole readonly part, a conventional way to mean that
590 574 /// all the readonly blocks have been masked. This is what is really
591 575 /// useful to the caller and does not require to know how many were
592 576 /// actually unreachable to begin with.
593 577 pub fn masked_readonly_blocks(&self) -> usize {
594 578 if let Some(readonly_root) = self.readonly.last() {
595 579 if readonly_root == &self.root {
596 580 return 0;
597 581 }
598 582 } else {
599 583 return 0;
600 584 }
601 585 self.masked_inner_blocks + 1
602 586 }
603 587 }
604 588
605 589 pub struct NodeTreeBytes {
606 590 buffer: Box<dyn Deref<Target = [u8]> + Send>,
607 591 len_in_blocks: usize,
608 592 }
609 593
610 594 impl NodeTreeBytes {
611 595 fn new(
612 596 buffer: Box<dyn Deref<Target = [u8]> + Send>,
613 597 amount: usize,
614 598 ) -> Self {
615 599 assert!(buffer.len() >= amount);
616 let len_in_blocks = amount / BLOCK_SIZE;
600 let len_in_blocks = amount / size_of::<Block>();
617 601 NodeTreeBytes {
618 602 buffer,
619 603 len_in_blocks,
620 604 }
621 605 }
622 606 }
623 607
624 608 impl Deref for NodeTreeBytes {
625 609 type Target = [Block];
626 610
627 611 fn deref(&self) -> &[Block] {
628 unsafe {
629 slice::from_raw_parts(
630 (&self.buffer).as_ptr() as *const Block,
631 self.len_in_blocks,
632 )
633 }
612 Block::slice_from_bytes(&self.buffer, self.len_in_blocks)
613 // `NodeTreeBytes::new` already asserted that `self.buffer` is
614 // large enough.
615 .unwrap()
616 .0
634 617 }
635 618 }
636 619
637 620 struct NodeTreeVisitor<'n, 'p> {
638 621 nt: &'n NodeTree,
639 622 prefix: NodePrefixRef<'p>,
640 623 visit: usize,
641 624 nybble_idx: usize,
642 625 done: bool,
643 626 }
644 627
645 628 #[derive(Debug, PartialEq, Clone)]
646 629 struct NodeTreeVisitItem {
647 630 block_idx: usize,
648 631 nybble: u8,
649 632 element: Element,
650 633 }
651 634
652 635 impl<'n, 'p> Iterator for NodeTreeVisitor<'n, 'p> {
653 636 type Item = NodeTreeVisitItem;
654 637
655 638 fn next(&mut self) -> Option<Self::Item> {
656 639 if self.done || self.nybble_idx >= self.prefix.len() {
657 640 return None;
658 641 }
659 642
660 643 let nybble = self.prefix.get_nybble(self.nybble_idx);
661 644 self.nybble_idx += 1;
662 645
663 646 let visit = self.visit;
664 647 let element = self.nt[visit].get(nybble);
665 648 if let Element::Block(idx) = element {
666 649 self.visit = idx;
667 650 } else {
668 651 self.done = true;
669 652 }
670 653
671 654 Some(NodeTreeVisitItem {
672 655 block_idx: visit,
673 656 nybble,
674 657 element,
675 658 })
676 659 }
677 660 }
678 661
679 662 impl NodeTreeVisitItem {
680 663 // Return `Some(opt)` if this item is final, with `opt` being the
681 664 // `Revision` that it may represent.
682 665 //
683 666 // If the item is not terminal, return `None`
684 667 fn final_revision(&self) -> Option<Option<Revision>> {
685 668 match self.element {
686 669 Element::Block(_) => None,
687 670 Element::Rev(r) => Some(Some(r)),
688 671 Element::None => Some(None),
689 672 }
690 673 }
691 674 }
692 675
693 676 impl From<Vec<Block>> for NodeTree {
694 677 fn from(vec: Vec<Block>) -> Self {
695 678 Self::new(Box::new(vec))
696 679 }
697 680 }
698 681
699 682 impl fmt::Debug for NodeTree {
700 683 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
701 684 let readonly: &[Block] = &*self.readonly;
702 685 write!(
703 686 f,
704 687 "readonly: {:?}, growable: {:?}, root: {:?}",
705 688 readonly, self.growable, self.root
706 689 )
707 690 }
708 691 }
709 692
710 693 impl Default for NodeTree {
711 694 /// Create a fully mutable empty NodeTree
712 695 fn default() -> Self {
713 696 NodeTree::new(Box::new(Vec::new()))
714 697 }
715 698 }
716 699
717 700 impl NodeMap for NodeTree {
718 701 fn find_bin<'a>(
719 702 &self,
720 703 idx: &impl RevlogIndex,
721 704 prefix: NodePrefixRef<'a>,
722 705 ) -> Result<Option<Revision>, NodeMapError> {
723 706 validate_candidate(idx, prefix.clone(), self.lookup(prefix)?)
724 707 .map(|(opt, _shortest)| opt)
725 708 }
726 709
727 710 fn unique_prefix_len_bin<'a>(
728 711 &self,
729 712 idx: &impl RevlogIndex,
730 713 prefix: NodePrefixRef<'a>,
731 714 ) -> Result<Option<usize>, NodeMapError> {
732 715 validate_candidate(idx, prefix.clone(), self.lookup(prefix)?)
733 716 .map(|(opt, shortest)| opt.map(|_rev| shortest))
734 717 }
735 718 }
736 719
737 720 #[cfg(test)]
738 721 mod tests {
739 722 use super::NodeMapError::*;
740 723 use super::*;
741 724 use crate::revlog::node::{hex_pad_right, Node};
742 725 use std::collections::HashMap;
743 726
744 727 /// Creates a `Block` using a syntax close to the `Debug` output
745 728 macro_rules! block {
746 729 {$($nybble:tt : $variant:ident($val:tt)),*} => (
747 730 {
748 731 let mut block = Block::new();
749 732 $(block.set($nybble, Element::$variant($val)));*;
750 733 block
751 734 }
752 735 )
753 736 }
754 737
755 738 #[test]
756 739 fn test_block_debug() {
757 740 let mut block = Block::new();
758 741 block.set(1, Element::Rev(3));
759 742 block.set(10, Element::Block(0));
760 743 assert_eq!(format!("{:?}", block), "{1: Rev(3), 10: Block(0)}");
761 744 }
762 745
763 746 #[test]
764 747 fn test_block_macro() {
765 748 let block = block! {5: Block(2)};
766 749 assert_eq!(format!("{:?}", block), "{5: Block(2)}");
767 750
768 751 let block = block! {13: Rev(15), 5: Block(2)};
769 752 assert_eq!(format!("{:?}", block), "{5: Block(2), 13: Rev(15)}");
770 753 }
771 754
772 755 #[test]
773 756 fn test_raw_block() {
774 757 let mut raw = [255u8; 64];
775 758
776 759 let mut counter = 0;
777 for val in [0, 15, -2, -1, -3].iter() {
778 for byte in RawElement::to_be_bytes(*val).iter() {
760 for val in [0_i32, 15, -2, -1, -3].iter() {
761 for byte in val.to_be_bytes().iter() {
779 762 raw[counter] = *byte;
780 763 counter += 1;
781 764 }
782 765 }
783 let block = Block(raw);
766 let (block, _) = Block::from_bytes(&raw).unwrap();
784 767 assert_eq!(block.get(0), Element::Block(0));
785 768 assert_eq!(block.get(1), Element::Block(15));
786 769 assert_eq!(block.get(3), Element::None);
787 770 assert_eq!(block.get(2), Element::Rev(0));
788 771 assert_eq!(block.get(4), Element::Rev(1));
789 772 }
790 773
791 774 type TestIndex = HashMap<Revision, Node>;
792 775
793 776 impl RevlogIndex for TestIndex {
794 777 fn node(&self, rev: Revision) -> Option<&Node> {
795 778 self.get(&rev)
796 779 }
797 780
798 781 fn len(&self) -> usize {
799 782 self.len()
800 783 }
801 784 }
802 785
803 786 /// Pad hexadecimal Node prefix with zeros on the right
804 787 ///
805 788 /// This avoids having to repeatedly write very long hexadecimal
806 789 /// strings for test data, and brings actual hash size independency.
807 790 #[cfg(test)]
808 791 fn pad_node(hex: &str) -> Node {
809 792 Node::from_hex(&hex_pad_right(hex)).unwrap()
810 793 }
811 794
812 795 /// Pad hexadecimal Node prefix with zeros on the right, then insert
813 796 fn pad_insert(idx: &mut TestIndex, rev: Revision, hex: &str) {
814 797 idx.insert(rev, pad_node(hex));
815 798 }
816 799
817 800 fn sample_nodetree() -> NodeTree {
818 801 NodeTree::from(vec![
819 802 block![0: Rev(9)],
820 803 block![0: Rev(0), 1: Rev(9)],
821 804 block![0: Block(1), 1:Rev(1)],
822 805 ])
823 806 }
824 807
825 808 #[test]
826 809 fn test_nt_debug() {
827 810 let nt = sample_nodetree();
828 811 assert_eq!(
829 812 format!("{:?}", nt),
830 813 "readonly: \
831 814 [{0: Rev(9)}, {0: Rev(0), 1: Rev(9)}, {0: Block(1), 1: Rev(1)}], \
832 815 growable: [], \
833 816 root: {0: Block(1), 1: Rev(1)}",
834 817 );
835 818 }
836 819
837 820 #[test]
838 821 fn test_immutable_find_simplest() -> Result<(), NodeMapError> {
839 822 let mut idx: TestIndex = HashMap::new();
840 823 pad_insert(&mut idx, 1, "1234deadcafe");
841 824
842 825 let nt = NodeTree::from(vec![block! {1: Rev(1)}]);
843 826 assert_eq!(nt.find_hex(&idx, "1")?, Some(1));
844 827 assert_eq!(nt.find_hex(&idx, "12")?, Some(1));
845 828 assert_eq!(nt.find_hex(&idx, "1234de")?, Some(1));
846 829 assert_eq!(nt.find_hex(&idx, "1a")?, None);
847 830 assert_eq!(nt.find_hex(&idx, "ab")?, None);
848 831
849 832 // and with full binary Nodes
850 833 assert_eq!(nt.find_node(&idx, idx.get(&1).unwrap())?, Some(1));
851 834 let unknown = Node::from_hex(&hex_pad_right("3d")).unwrap();
852 835 assert_eq!(nt.find_node(&idx, &unknown)?, None);
853 836 Ok(())
854 837 }
855 838
856 839 #[test]
857 840 fn test_immutable_find_one_jump() {
858 841 let mut idx = TestIndex::new();
859 842 pad_insert(&mut idx, 9, "012");
860 843 pad_insert(&mut idx, 0, "00a");
861 844
862 845 let nt = sample_nodetree();
863 846
864 847 assert_eq!(nt.find_hex(&idx, "0"), Err(MultipleResults));
865 848 assert_eq!(nt.find_hex(&idx, "01"), Ok(Some(9)));
866 849 assert_eq!(nt.find_hex(&idx, "00"), Err(MultipleResults));
867 850 assert_eq!(nt.find_hex(&idx, "00a"), Ok(Some(0)));
868 851 assert_eq!(nt.unique_prefix_len_hex(&idx, "00a"), Ok(Some(3)));
869 852 assert_eq!(nt.find_hex(&idx, "000"), Ok(Some(NULL_REVISION)));
870 853 }
871 854
872 855 #[test]
873 856 fn test_mutated_find() -> Result<(), NodeMapError> {
874 857 let mut idx = TestIndex::new();
875 858 pad_insert(&mut idx, 9, "012");
876 859 pad_insert(&mut idx, 0, "00a");
877 860 pad_insert(&mut idx, 2, "cafe");
878 861 pad_insert(&mut idx, 3, "15");
879 862 pad_insert(&mut idx, 1, "10");
880 863
881 864 let nt = NodeTree {
882 865 readonly: sample_nodetree().readonly,
883 866 growable: vec![block![0: Rev(1), 5: Rev(3)]],
884 867 root: block![0: Block(1), 1:Block(3), 12: Rev(2)],
885 868 masked_inner_blocks: 1,
886 869 };
887 870 assert_eq!(nt.find_hex(&idx, "10")?, Some(1));
888 871 assert_eq!(nt.find_hex(&idx, "c")?, Some(2));
889 872 assert_eq!(nt.unique_prefix_len_hex(&idx, "c")?, Some(1));
890 873 assert_eq!(nt.find_hex(&idx, "00"), Err(MultipleResults));
891 874 assert_eq!(nt.find_hex(&idx, "000")?, Some(NULL_REVISION));
892 875 assert_eq!(nt.unique_prefix_len_hex(&idx, "000")?, Some(3));
893 876 assert_eq!(nt.find_hex(&idx, "01")?, Some(9));
894 877 assert_eq!(nt.masked_readonly_blocks(), 2);
895 878 Ok(())
896 879 }
897 880
898 881 struct TestNtIndex {
899 882 index: TestIndex,
900 883 nt: NodeTree,
901 884 }
902 885
903 886 impl TestNtIndex {
904 887 fn new() -> Self {
905 888 TestNtIndex {
906 889 index: HashMap::new(),
907 890 nt: NodeTree::default(),
908 891 }
909 892 }
910 893
911 894 fn insert(
912 895 &mut self,
913 896 rev: Revision,
914 897 hex: &str,
915 898 ) -> Result<(), NodeMapError> {
916 899 let node = pad_node(hex);
917 900 self.index.insert(rev, node.clone());
918 901 self.nt.insert(&self.index, &node, rev)?;
919 902 Ok(())
920 903 }
921 904
922 905 fn find_hex(
923 906 &self,
924 907 prefix: &str,
925 908 ) -> Result<Option<Revision>, NodeMapError> {
926 909 self.nt.find_hex(&self.index, prefix)
927 910 }
928 911
929 912 fn unique_prefix_len_hex(
930 913 &self,
931 914 prefix: &str,
932 915 ) -> Result<Option<usize>, NodeMapError> {
933 916 self.nt.unique_prefix_len_hex(&self.index, prefix)
934 917 }
935 918
936 919 /// Drain `added` and restart a new one
937 920 fn commit(self) -> Self {
938 921 let mut as_vec: Vec<Block> =
939 922 self.nt.readonly.iter().map(|block| block.clone()).collect();
940 923 as_vec.extend(self.nt.growable);
941 924 as_vec.push(self.nt.root);
942 925
943 926 Self {
944 927 index: self.index,
945 928 nt: NodeTree::from(as_vec).into(),
946 929 }
947 930 }
948 931 }
949 932
950 933 #[test]
951 934 fn test_insert_full_mutable() -> Result<(), NodeMapError> {
952 935 let mut idx = TestNtIndex::new();
953 936 idx.insert(0, "1234")?;
954 937 assert_eq!(idx.find_hex("1")?, Some(0));
955 938 assert_eq!(idx.find_hex("12")?, Some(0));
956 939
957 940 // let's trigger a simple split
958 941 idx.insert(1, "1a34")?;
959 942 assert_eq!(idx.nt.growable.len(), 1);
960 943 assert_eq!(idx.find_hex("12")?, Some(0));
961 944 assert_eq!(idx.find_hex("1a")?, Some(1));
962 945
963 946 // reinserting is a no_op
964 947 idx.insert(1, "1a34")?;
965 948 assert_eq!(idx.nt.growable.len(), 1);
966 949 assert_eq!(idx.find_hex("12")?, Some(0));
967 950 assert_eq!(idx.find_hex("1a")?, Some(1));
968 951
969 952 idx.insert(2, "1a01")?;
970 953 assert_eq!(idx.nt.growable.len(), 2);
971 954 assert_eq!(idx.find_hex("1a"), Err(NodeMapError::MultipleResults));
972 955 assert_eq!(idx.find_hex("12")?, Some(0));
973 956 assert_eq!(idx.find_hex("1a3")?, Some(1));
974 957 assert_eq!(idx.find_hex("1a0")?, Some(2));
975 958 assert_eq!(idx.find_hex("1a12")?, None);
976 959
977 960 // now let's make it split and create more than one additional block
978 961 idx.insert(3, "1a345")?;
979 962 assert_eq!(idx.nt.growable.len(), 4);
980 963 assert_eq!(idx.find_hex("1a340")?, Some(1));
981 964 assert_eq!(idx.find_hex("1a345")?, Some(3));
982 965 assert_eq!(idx.find_hex("1a341")?, None);
983 966
984 967 // there's no readonly block to mask
985 968 assert_eq!(idx.nt.masked_readonly_blocks(), 0);
986 969 Ok(())
987 970 }
988 971
989 972 #[test]
990 973 fn test_unique_prefix_len_zero_prefix() {
991 974 let mut idx = TestNtIndex::new();
992 975 idx.insert(0, "00000abcd").unwrap();
993 976
994 977 assert_eq!(idx.find_hex("000"), Err(NodeMapError::MultipleResults));
995 978 // in the nodetree proper, this will be found at the first nybble
996 979 // yet the correct answer for unique_prefix_len is not 1, nor 1+1,
997 980 // but the first difference with `NULL_NODE`
998 981 assert_eq!(idx.unique_prefix_len_hex("00000a"), Ok(Some(6)));
999 982 assert_eq!(idx.unique_prefix_len_hex("00000ab"), Ok(Some(6)));
1000 983
1001 984 // same with odd result
1002 985 idx.insert(1, "00123").unwrap();
1003 986 assert_eq!(idx.unique_prefix_len_hex("001"), Ok(Some(3)));
1004 987 assert_eq!(idx.unique_prefix_len_hex("0012"), Ok(Some(3)));
1005 988
1006 989 // these are unchanged of course
1007 990 assert_eq!(idx.unique_prefix_len_hex("00000a"), Ok(Some(6)));
1008 991 assert_eq!(idx.unique_prefix_len_hex("00000ab"), Ok(Some(6)));
1009 992 }
1010 993
1011 994 #[test]
1012 995 fn test_insert_extreme_splitting() -> Result<(), NodeMapError> {
1013 996 // check that the splitting loop is long enough
1014 997 let mut nt_idx = TestNtIndex::new();
1015 998 let nt = &mut nt_idx.nt;
1016 999 let idx = &mut nt_idx.index;
1017 1000
1018 1001 let node0_hex = hex_pad_right("444444");
1019 1002 let mut node1_hex = hex_pad_right("444444").clone();
1020 1003 node1_hex.pop();
1021 1004 node1_hex.push('5');
1022 1005 let node0 = Node::from_hex(&node0_hex).unwrap();
1023 1006 let node1 = Node::from_hex(&node1_hex).unwrap();
1024 1007
1025 1008 idx.insert(0, node0.clone());
1026 1009 nt.insert(idx, &node0, 0)?;
1027 1010 idx.insert(1, node1.clone());
1028 1011 nt.insert(idx, &node1, 1)?;
1029 1012
1030 1013 assert_eq!(nt.find_bin(idx, (&node0).into())?, Some(0));
1031 1014 assert_eq!(nt.find_bin(idx, (&node1).into())?, Some(1));
1032 1015 Ok(())
1033 1016 }
1034 1017
1035 1018 #[test]
1036 1019 fn test_insert_partly_immutable() -> Result<(), NodeMapError> {
1037 1020 let mut idx = TestNtIndex::new();
1038 1021 idx.insert(0, "1234")?;
1039 1022 idx.insert(1, "1235")?;
1040 1023 idx.insert(2, "131")?;
1041 1024 idx.insert(3, "cafe")?;
1042 1025 let mut idx = idx.commit();
1043 1026 assert_eq!(idx.find_hex("1234")?, Some(0));
1044 1027 assert_eq!(idx.find_hex("1235")?, Some(1));
1045 1028 assert_eq!(idx.find_hex("131")?, Some(2));
1046 1029 assert_eq!(idx.find_hex("cafe")?, Some(3));
1047 1030 // we did not add anything since init from readonly
1048 1031 assert_eq!(idx.nt.masked_readonly_blocks(), 0);
1049 1032
1050 1033 idx.insert(4, "123A")?;
1051 1034 assert_eq!(idx.find_hex("1234")?, Some(0));
1052 1035 assert_eq!(idx.find_hex("1235")?, Some(1));
1053 1036 assert_eq!(idx.find_hex("131")?, Some(2));
1054 1037 assert_eq!(idx.find_hex("cafe")?, Some(3));
1055 1038 assert_eq!(idx.find_hex("123A")?, Some(4));
1056 1039 // we masked blocks for all prefixes of "123", including the root
1057 1040 assert_eq!(idx.nt.masked_readonly_blocks(), 4);
1058 1041
1059 1042 eprintln!("{:?}", idx.nt);
1060 1043 idx.insert(5, "c0")?;
1061 1044 assert_eq!(idx.find_hex("cafe")?, Some(3));
1062 1045 assert_eq!(idx.find_hex("c0")?, Some(5));
1063 1046 assert_eq!(idx.find_hex("c1")?, None);
1064 1047 assert_eq!(idx.find_hex("1234")?, Some(0));
1065 1048 // inserting "c0" is just splitting the 'c' slot of the mutable root,
1066 1049 // it doesn't mask anything
1067 1050 assert_eq!(idx.nt.masked_readonly_blocks(), 4);
1068 1051
1069 1052 Ok(())
1070 1053 }
1071 1054
1072 1055 #[test]
1073 1056 fn test_invalidate_all() -> Result<(), NodeMapError> {
1074 1057 let mut idx = TestNtIndex::new();
1075 1058 idx.insert(0, "1234")?;
1076 1059 idx.insert(1, "1235")?;
1077 1060 idx.insert(2, "131")?;
1078 1061 idx.insert(3, "cafe")?;
1079 1062 let mut idx = idx.commit();
1080 1063
1081 1064 idx.nt.invalidate_all();
1082 1065
1083 1066 assert_eq!(idx.find_hex("1234")?, None);
1084 1067 assert_eq!(idx.find_hex("1235")?, None);
1085 1068 assert_eq!(idx.find_hex("131")?, None);
1086 1069 assert_eq!(idx.find_hex("cafe")?, None);
1087 1070 // all the readonly blocks have been masked, this is the
1088 1071 // conventional expected response
1089 1072 assert_eq!(idx.nt.masked_readonly_blocks(), idx.nt.readonly.len() + 1);
1090 1073 Ok(())
1091 1074 }
1092 1075
1093 1076 #[test]
1094 1077 fn test_into_added_empty() {
1095 1078 assert!(sample_nodetree().into_readonly_and_added().1.is_empty());
1096 1079 assert!(sample_nodetree()
1097 1080 .into_readonly_and_added_bytes()
1098 1081 .1
1099 1082 .is_empty());
1100 1083 }
1101 1084
1102 1085 #[test]
1103 1086 fn test_into_added_bytes() -> Result<(), NodeMapError> {
1104 1087 let mut idx = TestNtIndex::new();
1105 1088 idx.insert(0, "1234")?;
1106 1089 let mut idx = idx.commit();
1107 1090 idx.insert(4, "cafe")?;
1108 1091 let (_, bytes) = idx.nt.into_readonly_and_added_bytes();
1109 1092
1110 1093 // only the root block has been changed
1111 assert_eq!(bytes.len(), BLOCK_SIZE);
1094 assert_eq!(bytes.len(), size_of::<Block>());
1112 1095 // big endian for -2
1113 1096 assert_eq!(&bytes[4..2 * 4], [255, 255, 255, 254]);
1114 1097 // big endian for -6
1115 1098 assert_eq!(&bytes[12 * 4..13 * 4], [255, 255, 255, 250]);
1116 1099 Ok(())
1117 1100 }
1118 1101 }
@@ -1,121 +1,105 b''
1 use bytes_cast::{unaligned, BytesCast};
1 2 use memmap::Mmap;
2 use std::convert::TryInto;
3 3 use std::path::{Path, PathBuf};
4 4
5 5 use super::revlog::RevlogError;
6 6 use crate::repo::Repo;
7 7 use crate::utils::strip_suffix;
8 8
9 9 const ONDISK_VERSION: u8 = 1;
10 10
11 11 pub(super) struct NodeMapDocket {
12 12 pub data_length: usize,
13 13 // TODO: keep here more of the data from `parse()` when we need it
14 14 }
15 15
16 #[derive(BytesCast)]
17 #[repr(C)]
18 struct DocketHeader {
19 uid_size: u8,
20 _tip_rev: unaligned::U64Be,
21 data_length: unaligned::U64Be,
22 _data_unused: unaligned::U64Be,
23 tip_node_size: unaligned::U64Be,
24 }
25
16 26 impl NodeMapDocket {
17 27 /// Return `Ok(None)` when the caller should proceed without a persistent
18 28 /// nodemap:
19 29 ///
20 30 /// * This revlog does not have a `.n` docket file (it is not generated for
21 31 /// small revlogs), or
22 32 /// * The docket has an unsupported version number (repositories created by
23 33 /// later hg, maybe that should be a requirement instead?), or
24 34 /// * The docket file points to a missing (likely deleted) data file (this
25 35 /// can happen in a rare race condition).
26 36 pub fn read_from_file(
27 37 repo: &Repo,
28 38 index_path: &Path,
29 39 ) -> Result<Option<(Self, Mmap)>, RevlogError> {
30 40 let docket_path = index_path.with_extension("n");
31 41 let docket_bytes = match repo.store_vfs().read(&docket_path) {
32 42 Err(e) if e.kind() == std::io::ErrorKind::NotFound => {
33 43 return Ok(None)
34 44 }
35 45 Err(e) => return Err(RevlogError::IoError(e)),
36 46 Ok(bytes) => bytes,
37 47 };
38 48
39 let mut input = if let Some((&ONDISK_VERSION, rest)) =
49 let input = if let Some((&ONDISK_VERSION, rest)) =
40 50 docket_bytes.split_first()
41 51 {
42 52 rest
43 53 } else {
44 54 return Ok(None);
45 55 };
46 let input = &mut input;
47 56
48 let uid_size = read_u8(input)? as usize;
49 let _tip_rev = read_be_u64(input)?;
57 let (header, rest) = DocketHeader::from_bytes(input)?;
58 let uid_size = header.uid_size as usize;
50 59 // TODO: do we care about overflow for 4 GB+ nodemap files on 32-bit
51 60 // systems?
52 let data_length = read_be_u64(input)? as usize;
53 let _data_unused = read_be_u64(input)?;
54 let tip_node_size = read_be_u64(input)? as usize;
55 let uid = read_bytes(input, uid_size)?;
56 let _tip_node = read_bytes(input, tip_node_size)?;
57
61 let tip_node_size = header.tip_node_size.get() as usize;
62 let data_length = header.data_length.get() as usize;
63 let (uid, rest) = u8::slice_from_bytes(rest, uid_size)?;
64 let (_tip_node, _rest) = u8::slice_from_bytes(rest, tip_node_size)?;
58 65 let uid =
59 66 std::str::from_utf8(uid).map_err(|_| RevlogError::Corrupted)?;
60 67 let docket = NodeMapDocket { data_length };
61 68
62 69 let data_path = rawdata_path(&docket_path, uid);
63 70 // TODO: use `std::fs::read` here when the `persistent-nodemap.mmap`
64 71 // config is false?
65 72 match repo.store_vfs().mmap_open(&data_path) {
66 73 Ok(mmap) => {
67 74 if mmap.len() >= data_length {
68 75 Ok(Some((docket, mmap)))
69 76 } else {
70 77 Err(RevlogError::Corrupted)
71 78 }
72 79 }
73 80 Err(error) => {
74 81 if error.kind() == std::io::ErrorKind::NotFound {
75 82 Ok(None)
76 83 } else {
77 84 Err(RevlogError::IoError(error))
78 85 }
79 86 }
80 87 }
81 88 }
82 89 }
83 90
84 fn read_bytes<'a>(
85 input: &mut &'a [u8],
86 count: usize,
87 ) -> Result<&'a [u8], RevlogError> {
88 if let Some(start) = input.get(..count) {
89 *input = &input[count..];
90 Ok(start)
91 } else {
92 Err(RevlogError::Corrupted)
93 }
94 }
95
96 fn read_u8<'a>(input: &mut &[u8]) -> Result<u8, RevlogError> {
97 Ok(read_bytes(input, 1)?[0])
98 }
99
100 fn read_be_u64<'a>(input: &mut &[u8]) -> Result<u64, RevlogError> {
101 let array = read_bytes(input, std::mem::size_of::<u64>())?
102 .try_into()
103 .unwrap();
104 Ok(u64::from_be_bytes(array))
105 }
106
107 91 fn rawdata_path(docket_path: &Path, uid: &str) -> PathBuf {
108 92 let docket_name = docket_path
109 93 .file_name()
110 94 .expect("expected a base name")
111 95 .to_str()
112 96 .expect("expected an ASCII file name in the store");
113 97 let prefix = strip_suffix(docket_name, ".n.a")
114 98 .or_else(|| strip_suffix(docket_name, ".n"))
115 99 .expect("expected docket path in .n or .n.a");
116 100 let name = format!("{}-{}.nd", prefix, uid);
117 101 docket_path
118 102 .parent()
119 103 .expect("expected a non-root path")
120 104 .join(name)
121 105 }
@@ -1,376 +1,382 b''
1 1 use std::borrow::Cow;
2 2 use std::io::Read;
3 3 use std::ops::Deref;
4 4 use std::path::Path;
5 5
6 6 use byteorder::{BigEndian, ByteOrder};
7 7 use crypto::digest::Digest;
8 8 use crypto::sha1::Sha1;
9 9 use flate2::read::ZlibDecoder;
10 10 use micro_timer::timed;
11 11 use zstd;
12 12
13 13 use super::index::Index;
14 14 use super::node::{NodePrefixRef, NODE_BYTES_LENGTH, NULL_NODE};
15 15 use super::nodemap;
16 16 use super::nodemap::NodeMap;
17 17 use super::nodemap_docket::NodeMapDocket;
18 18 use super::patch;
19 19 use crate::repo::Repo;
20 20 use crate::revlog::Revision;
21 21
22 22 pub enum RevlogError {
23 23 IoError(std::io::Error),
24 24 UnsuportedVersion(u16),
25 25 InvalidRevision,
26 26 /// Found more than one entry whose ID match the requested prefix
27 27 AmbiguousPrefix,
28 28 Corrupted,
29 29 UnknowDataFormat(u8),
30 30 }
31 31
32 impl From<bytes_cast::FromBytesError> for RevlogError {
33 fn from(_: bytes_cast::FromBytesError) -> Self {
34 RevlogError::Corrupted
35 }
36 }
37
32 38 /// Read only implementation of revlog.
33 39 pub struct Revlog {
34 40 /// When index and data are not interleaved: bytes of the revlog index.
35 41 /// When index and data are interleaved: bytes of the revlog index and
36 42 /// data.
37 43 index: Index,
38 44 /// When index and data are not interleaved: bytes of the revlog data
39 45 data_bytes: Option<Box<dyn Deref<Target = [u8]> + Send>>,
40 46 /// When present on disk: the persistent nodemap for this revlog
41 47 nodemap: Option<nodemap::NodeTree>,
42 48 }
43 49
44 50 impl Revlog {
45 51 /// Open a revlog index file.
46 52 ///
47 53 /// It will also open the associated data file if index and data are not
48 54 /// interleaved.
49 55 #[timed]
50 56 pub fn open(
51 57 repo: &Repo,
52 58 index_path: impl AsRef<Path>,
53 59 data_path: Option<&Path>,
54 60 ) -> Result<Self, RevlogError> {
55 61 let index_path = index_path.as_ref();
56 62 let index_mmap = repo
57 63 .store_vfs()
58 64 .mmap_open(&index_path)
59 65 .map_err(RevlogError::IoError)?;
60 66
61 67 let version = get_version(&index_mmap);
62 68 if version != 1 {
63 69 return Err(RevlogError::UnsuportedVersion(version));
64 70 }
65 71
66 72 let index = Index::new(Box::new(index_mmap))?;
67 73
68 74 let default_data_path = index_path.with_extension("d");
69 75
70 76 // type annotation required
71 77 // won't recognize Mmap as Deref<Target = [u8]>
72 78 let data_bytes: Option<Box<dyn Deref<Target = [u8]> + Send>> =
73 79 if index.is_inline() {
74 80 None
75 81 } else {
76 82 let data_path = data_path.unwrap_or(&default_data_path);
77 83 let data_mmap = repo
78 84 .store_vfs()
79 85 .mmap_open(data_path)
80 86 .map_err(RevlogError::IoError)?;
81 87 Some(Box::new(data_mmap))
82 88 };
83 89
84 90 let nodemap = NodeMapDocket::read_from_file(repo, index_path)?.map(
85 91 |(docket, data)| {
86 92 nodemap::NodeTree::load_bytes(
87 93 Box::new(data),
88 94 docket.data_length,
89 95 )
90 96 },
91 97 );
92 98
93 99 Ok(Revlog {
94 100 index,
95 101 data_bytes,
96 102 nodemap,
97 103 })
98 104 }
99 105
100 106 /// Return number of entries of the `Revlog`.
101 107 pub fn len(&self) -> usize {
102 108 self.index.len()
103 109 }
104 110
105 111 /// Returns `true` if the `Revlog` has zero `entries`.
106 112 pub fn is_empty(&self) -> bool {
107 113 self.index.is_empty()
108 114 }
109 115
110 116 /// Return the full data associated to a node.
111 117 #[timed]
112 118 pub fn get_node_rev(
113 119 &self,
114 120 node: NodePrefixRef,
115 121 ) -> Result<Revision, RevlogError> {
116 122 if let Some(nodemap) = &self.nodemap {
117 123 return nodemap
118 124 .find_bin(&self.index, node)
119 125 // TODO: propagate details of this error:
120 126 .map_err(|_| RevlogError::Corrupted)?
121 127 .ok_or(RevlogError::InvalidRevision);
122 128 }
123 129
124 130 // Fallback to linear scan when a persistent nodemap is not present.
125 131 // This happens when the persistent-nodemap experimental feature is not
126 132 // enabled, or for small revlogs.
127 133 //
128 134 // TODO: consider building a non-persistent nodemap in memory to
129 135 // optimize these cases.
130 136 let mut found_by_prefix = None;
131 137 for rev in (0..self.len() as Revision).rev() {
132 138 let index_entry =
133 139 self.index.get_entry(rev).ok_or(RevlogError::Corrupted)?;
134 140 if node == *index_entry.hash() {
135 141 return Ok(rev);
136 142 }
137 143 if node.is_prefix_of(index_entry.hash()) {
138 144 if found_by_prefix.is_some() {
139 145 return Err(RevlogError::AmbiguousPrefix);
140 146 }
141 147 found_by_prefix = Some(rev)
142 148 }
143 149 }
144 150 found_by_prefix.ok_or(RevlogError::InvalidRevision)
145 151 }
146 152
147 153 /// Return the full data associated to a revision.
148 154 ///
149 155 /// All entries required to build the final data out of deltas will be
150 156 /// retrieved as needed, and the deltas will be applied to the inital
151 157 /// snapshot to rebuild the final data.
152 158 #[timed]
153 159 pub fn get_rev_data(&self, rev: Revision) -> Result<Vec<u8>, RevlogError> {
154 160 // Todo return -> Cow
155 161 let mut entry = self.get_entry(rev)?;
156 162 let mut delta_chain = vec![];
157 163 while let Some(base_rev) = entry.base_rev {
158 164 delta_chain.push(entry);
159 165 entry =
160 166 self.get_entry(base_rev).or(Err(RevlogError::Corrupted))?;
161 167 }
162 168
163 169 // TODO do not look twice in the index
164 170 let index_entry = self
165 171 .index
166 172 .get_entry(rev)
167 173 .ok_or(RevlogError::InvalidRevision)?;
168 174
169 175 let data: Vec<u8> = if delta_chain.is_empty() {
170 176 entry.data()?.into()
171 177 } else {
172 178 Revlog::build_data_from_deltas(entry, &delta_chain)?
173 179 };
174 180
175 181 if self.check_hash(
176 182 index_entry.p1(),
177 183 index_entry.p2(),
178 184 index_entry.hash().as_bytes(),
179 185 &data,
180 186 ) {
181 187 Ok(data)
182 188 } else {
183 189 Err(RevlogError::Corrupted)
184 190 }
185 191 }
186 192
187 193 /// Check the hash of some given data against the recorded hash.
188 194 pub fn check_hash(
189 195 &self,
190 196 p1: Revision,
191 197 p2: Revision,
192 198 expected: &[u8],
193 199 data: &[u8],
194 200 ) -> bool {
195 201 let e1 = self.index.get_entry(p1);
196 202 let h1 = match e1 {
197 203 Some(ref entry) => entry.hash(),
198 204 None => &NULL_NODE,
199 205 };
200 206 let e2 = self.index.get_entry(p2);
201 207 let h2 = match e2 {
202 208 Some(ref entry) => entry.hash(),
203 209 None => &NULL_NODE,
204 210 };
205 211
206 212 hash(data, h1.as_bytes(), h2.as_bytes()).as_slice() == expected
207 213 }
208 214
209 215 /// Build the full data of a revision out its snapshot
210 216 /// and its deltas.
211 217 #[timed]
212 218 fn build_data_from_deltas(
213 219 snapshot: RevlogEntry,
214 220 deltas: &[RevlogEntry],
215 221 ) -> Result<Vec<u8>, RevlogError> {
216 222 let snapshot = snapshot.data()?;
217 223 let deltas = deltas
218 224 .iter()
219 225 .rev()
220 226 .map(RevlogEntry::data)
221 227 .collect::<Result<Vec<Cow<'_, [u8]>>, RevlogError>>()?;
222 228 let patches: Vec<_> =
223 229 deltas.iter().map(|d| patch::PatchList::new(d)).collect();
224 230 let patch = patch::fold_patch_lists(&patches);
225 231 Ok(patch.apply(&snapshot))
226 232 }
227 233
228 234 /// Return the revlog data.
229 235 fn data(&self) -> &[u8] {
230 236 match self.data_bytes {
231 237 Some(ref data_bytes) => &data_bytes,
232 238 None => panic!(
233 239 "forgot to load the data or trying to access inline data"
234 240 ),
235 241 }
236 242 }
237 243
238 244 /// Get an entry of the revlog.
239 245 fn get_entry(&self, rev: Revision) -> Result<RevlogEntry, RevlogError> {
240 246 let index_entry = self
241 247 .index
242 248 .get_entry(rev)
243 249 .ok_or(RevlogError::InvalidRevision)?;
244 250 let start = index_entry.offset();
245 251 let end = start + index_entry.compressed_len();
246 252 let data = if self.index.is_inline() {
247 253 self.index.data(start, end)
248 254 } else {
249 255 &self.data()[start..end]
250 256 };
251 257 let entry = RevlogEntry {
252 258 rev,
253 259 bytes: data,
254 260 compressed_len: index_entry.compressed_len(),
255 261 uncompressed_len: index_entry.uncompressed_len(),
256 262 base_rev: if index_entry.base_revision() == rev {
257 263 None
258 264 } else {
259 265 Some(index_entry.base_revision())
260 266 },
261 267 };
262 268 Ok(entry)
263 269 }
264 270 }
265 271
266 272 /// The revlog entry's bytes and the necessary informations to extract
267 273 /// the entry's data.
268 274 #[derive(Debug)]
269 275 pub struct RevlogEntry<'a> {
270 276 rev: Revision,
271 277 bytes: &'a [u8],
272 278 compressed_len: usize,
273 279 uncompressed_len: usize,
274 280 base_rev: Option<Revision>,
275 281 }
276 282
277 283 impl<'a> RevlogEntry<'a> {
278 284 /// Extract the data contained in the entry.
279 285 pub fn data(&self) -> Result<Cow<'_, [u8]>, RevlogError> {
280 286 if self.bytes.is_empty() {
281 287 return Ok(Cow::Borrowed(&[]));
282 288 }
283 289 match self.bytes[0] {
284 290 // Revision data is the entirety of the entry, including this
285 291 // header.
286 292 b'\0' => Ok(Cow::Borrowed(self.bytes)),
287 293 // Raw revision data follows.
288 294 b'u' => Ok(Cow::Borrowed(&self.bytes[1..])),
289 295 // zlib (RFC 1950) data.
290 296 b'x' => Ok(Cow::Owned(self.uncompressed_zlib_data()?)),
291 297 // zstd data.
292 298 b'\x28' => Ok(Cow::Owned(self.uncompressed_zstd_data()?)),
293 299 format_type => Err(RevlogError::UnknowDataFormat(format_type)),
294 300 }
295 301 }
296 302
297 303 fn uncompressed_zlib_data(&self) -> Result<Vec<u8>, RevlogError> {
298 304 let mut decoder = ZlibDecoder::new(self.bytes);
299 305 if self.is_delta() {
300 306 let mut buf = Vec::with_capacity(self.compressed_len);
301 307 decoder
302 308 .read_to_end(&mut buf)
303 309 .or(Err(RevlogError::Corrupted))?;
304 310 Ok(buf)
305 311 } else {
306 312 let mut buf = vec![0; self.uncompressed_len];
307 313 decoder
308 314 .read_exact(&mut buf)
309 315 .or(Err(RevlogError::Corrupted))?;
310 316 Ok(buf)
311 317 }
312 318 }
313 319
314 320 fn uncompressed_zstd_data(&self) -> Result<Vec<u8>, RevlogError> {
315 321 if self.is_delta() {
316 322 let mut buf = Vec::with_capacity(self.compressed_len);
317 323 zstd::stream::copy_decode(self.bytes, &mut buf)
318 324 .or(Err(RevlogError::Corrupted))?;
319 325 Ok(buf)
320 326 } else {
321 327 let mut buf = vec![0; self.uncompressed_len];
322 328 let len = zstd::block::decompress_to_buffer(self.bytes, &mut buf)
323 329 .or(Err(RevlogError::Corrupted))?;
324 330 if len != self.uncompressed_len {
325 331 Err(RevlogError::Corrupted)
326 332 } else {
327 333 Ok(buf)
328 334 }
329 335 }
330 336 }
331 337
332 338 /// Tell if the entry is a snapshot or a delta
333 339 /// (influences on decompression).
334 340 fn is_delta(&self) -> bool {
335 341 self.base_rev.is_some()
336 342 }
337 343 }
338 344
339 345 /// Format version of the revlog.
340 346 pub fn get_version(index_bytes: &[u8]) -> u16 {
341 347 BigEndian::read_u16(&index_bytes[2..=3])
342 348 }
343 349
344 350 /// Calculate the hash of a revision given its data and its parents.
345 351 fn hash(data: &[u8], p1_hash: &[u8], p2_hash: &[u8]) -> Vec<u8> {
346 352 let mut hasher = Sha1::new();
347 353 let (a, b) = (p1_hash, p2_hash);
348 354 if a > b {
349 355 hasher.input(b);
350 356 hasher.input(a);
351 357 } else {
352 358 hasher.input(a);
353 359 hasher.input(b);
354 360 }
355 361 hasher.input(data);
356 362 let mut hash = vec![0; NODE_BYTES_LENGTH];
357 363 hasher.result(&mut hash);
358 364 hash
359 365 }
360 366
361 367 #[cfg(test)]
362 368 mod tests {
363 369 use super::*;
364 370
365 371 use super::super::index::IndexEntryBuilder;
366 372
367 373 #[test]
368 374 fn version_test() {
369 375 let bytes = IndexEntryBuilder::new()
370 376 .is_first(true)
371 377 .with_version(1)
372 378 .build();
373 379
374 380 assert_eq!(get_version(&bytes), 1)
375 381 }
376 382 }
General Comments 0
You need to be logged in to leave comments. Login now