##// END OF EJS Templates
cext: add support for revlogv2...
Raphaël Gomès -
r47442:358737ab default
parent child Browse files
Show More
@@ -1,762 +1,763 b''
1 1 /*
2 2 parsers.c - efficient content parsing
3 3
4 4 Copyright 2008 Matt Mackall <mpm@selenic.com> and others
5 5
6 6 This software may be used and distributed according to the terms of
7 7 the GNU General Public License, incorporated herein by reference.
8 8 */
9 9
10 10 #define PY_SSIZE_T_CLEAN
11 11 #include <Python.h>
12 12 #include <ctype.h>
13 13 #include <stddef.h>
14 14 #include <string.h>
15 15
16 16 #include "bitmanipulation.h"
17 17 #include "charencode.h"
18 18 #include "util.h"
19 19
20 20 #ifdef IS_PY3K
21 21 /* The mapping of Python types is meant to be temporary to get Python
22 22 * 3 to compile. We should remove this once Python 3 support is fully
23 23 * supported and proper types are used in the extensions themselves. */
24 24 #define PyInt_Check PyLong_Check
25 25 #define PyInt_FromLong PyLong_FromLong
26 26 #define PyInt_FromSsize_t PyLong_FromSsize_t
27 27 #define PyInt_AsLong PyLong_AsLong
28 28 #endif
29 29
30 30 static const char *const versionerrortext = "Python minor version mismatch";
31 31
32 32 static PyObject *dict_new_presized(PyObject *self, PyObject *args)
33 33 {
34 34 Py_ssize_t expected_size;
35 35
36 36 if (!PyArg_ParseTuple(args, "n:make_presized_dict", &expected_size)) {
37 37 return NULL;
38 38 }
39 39
40 40 return _dict_new_presized(expected_size);
41 41 }
42 42
43 43 static inline dirstateTupleObject *make_dirstate_tuple(char state, int mode,
44 44 int size, int mtime)
45 45 {
46 46 dirstateTupleObject *t =
47 47 PyObject_New(dirstateTupleObject, &dirstateTupleType);
48 48 if (!t) {
49 49 return NULL;
50 50 }
51 51 t->state = state;
52 52 t->mode = mode;
53 53 t->size = size;
54 54 t->mtime = mtime;
55 55 return t;
56 56 }
57 57
58 58 static PyObject *dirstate_tuple_new(PyTypeObject *subtype, PyObject *args,
59 59 PyObject *kwds)
60 60 {
61 61 /* We do all the initialization here and not a tp_init function because
62 62 * dirstate_tuple is immutable. */
63 63 dirstateTupleObject *t;
64 64 char state;
65 65 int size, mode, mtime;
66 66 if (!PyArg_ParseTuple(args, "ciii", &state, &mode, &size, &mtime)) {
67 67 return NULL;
68 68 }
69 69
70 70 t = (dirstateTupleObject *)subtype->tp_alloc(subtype, 1);
71 71 if (!t) {
72 72 return NULL;
73 73 }
74 74 t->state = state;
75 75 t->mode = mode;
76 76 t->size = size;
77 77 t->mtime = mtime;
78 78
79 79 return (PyObject *)t;
80 80 }
81 81
82 82 static void dirstate_tuple_dealloc(PyObject *o)
83 83 {
84 84 PyObject_Del(o);
85 85 }
86 86
87 87 static Py_ssize_t dirstate_tuple_length(PyObject *o)
88 88 {
89 89 return 4;
90 90 }
91 91
92 92 static PyObject *dirstate_tuple_item(PyObject *o, Py_ssize_t i)
93 93 {
94 94 dirstateTupleObject *t = (dirstateTupleObject *)o;
95 95 switch (i) {
96 96 case 0:
97 97 return PyBytes_FromStringAndSize(&t->state, 1);
98 98 case 1:
99 99 return PyInt_FromLong(t->mode);
100 100 case 2:
101 101 return PyInt_FromLong(t->size);
102 102 case 3:
103 103 return PyInt_FromLong(t->mtime);
104 104 default:
105 105 PyErr_SetString(PyExc_IndexError, "index out of range");
106 106 return NULL;
107 107 }
108 108 }
109 109
110 110 static PySequenceMethods dirstate_tuple_sq = {
111 111 dirstate_tuple_length, /* sq_length */
112 112 0, /* sq_concat */
113 113 0, /* sq_repeat */
114 114 dirstate_tuple_item, /* sq_item */
115 115 0, /* sq_ass_item */
116 116 0, /* sq_contains */
117 117 0, /* sq_inplace_concat */
118 118 0 /* sq_inplace_repeat */
119 119 };
120 120
121 121 PyTypeObject dirstateTupleType = {
122 122 PyVarObject_HEAD_INIT(NULL, 0) /* header */
123 123 "dirstate_tuple", /* tp_name */
124 124 sizeof(dirstateTupleObject), /* tp_basicsize */
125 125 0, /* tp_itemsize */
126 126 (destructor)dirstate_tuple_dealloc, /* tp_dealloc */
127 127 0, /* tp_print */
128 128 0, /* tp_getattr */
129 129 0, /* tp_setattr */
130 130 0, /* tp_compare */
131 131 0, /* tp_repr */
132 132 0, /* tp_as_number */
133 133 &dirstate_tuple_sq, /* tp_as_sequence */
134 134 0, /* tp_as_mapping */
135 135 0, /* tp_hash */
136 136 0, /* tp_call */
137 137 0, /* tp_str */
138 138 0, /* tp_getattro */
139 139 0, /* tp_setattro */
140 140 0, /* tp_as_buffer */
141 141 Py_TPFLAGS_DEFAULT, /* tp_flags */
142 142 "dirstate tuple", /* tp_doc */
143 143 0, /* tp_traverse */
144 144 0, /* tp_clear */
145 145 0, /* tp_richcompare */
146 146 0, /* tp_weaklistoffset */
147 147 0, /* tp_iter */
148 148 0, /* tp_iternext */
149 149 0, /* tp_methods */
150 150 0, /* tp_members */
151 151 0, /* tp_getset */
152 152 0, /* tp_base */
153 153 0, /* tp_dict */
154 154 0, /* tp_descr_get */
155 155 0, /* tp_descr_set */
156 156 0, /* tp_dictoffset */
157 157 0, /* tp_init */
158 158 0, /* tp_alloc */
159 159 dirstate_tuple_new, /* tp_new */
160 160 };
161 161
162 162 static PyObject *parse_dirstate(PyObject *self, PyObject *args)
163 163 {
164 164 PyObject *dmap, *cmap, *parents = NULL, *ret = NULL;
165 165 PyObject *fname = NULL, *cname = NULL, *entry = NULL;
166 166 char state, *cur, *str, *cpos;
167 167 int mode, size, mtime;
168 168 unsigned int flen, pos = 40;
169 169 Py_ssize_t len = 40;
170 170 Py_ssize_t readlen;
171 171
172 172 if (!PyArg_ParseTuple(
173 173 args, PY23("O!O!s#:parse_dirstate", "O!O!y#:parse_dirstate"),
174 174 &PyDict_Type, &dmap, &PyDict_Type, &cmap, &str, &readlen)) {
175 175 goto quit;
176 176 }
177 177
178 178 len = readlen;
179 179
180 180 /* read parents */
181 181 if (len < 40) {
182 182 PyErr_SetString(PyExc_ValueError,
183 183 "too little data for parents");
184 184 goto quit;
185 185 }
186 186
187 187 parents = Py_BuildValue(PY23("s#s#", "y#y#"), str, (Py_ssize_t)20,
188 188 str + 20, (Py_ssize_t)20);
189 189 if (!parents) {
190 190 goto quit;
191 191 }
192 192
193 193 /* read filenames */
194 194 while (pos >= 40 && pos < len) {
195 195 if (pos + 17 > len) {
196 196 PyErr_SetString(PyExc_ValueError,
197 197 "overflow in dirstate");
198 198 goto quit;
199 199 }
200 200 cur = str + pos;
201 201 /* unpack header */
202 202 state = *cur;
203 203 mode = getbe32(cur + 1);
204 204 size = getbe32(cur + 5);
205 205 mtime = getbe32(cur + 9);
206 206 flen = getbe32(cur + 13);
207 207 pos += 17;
208 208 cur += 17;
209 209 if (flen > len - pos) {
210 210 PyErr_SetString(PyExc_ValueError,
211 211 "overflow in dirstate");
212 212 goto quit;
213 213 }
214 214
215 215 entry =
216 216 (PyObject *)make_dirstate_tuple(state, mode, size, mtime);
217 217 cpos = memchr(cur, 0, flen);
218 218 if (cpos) {
219 219 fname = PyBytes_FromStringAndSize(cur, cpos - cur);
220 220 cname = PyBytes_FromStringAndSize(
221 221 cpos + 1, flen - (cpos - cur) - 1);
222 222 if (!fname || !cname ||
223 223 PyDict_SetItem(cmap, fname, cname) == -1 ||
224 224 PyDict_SetItem(dmap, fname, entry) == -1) {
225 225 goto quit;
226 226 }
227 227 Py_DECREF(cname);
228 228 } else {
229 229 fname = PyBytes_FromStringAndSize(cur, flen);
230 230 if (!fname ||
231 231 PyDict_SetItem(dmap, fname, entry) == -1) {
232 232 goto quit;
233 233 }
234 234 }
235 235 Py_DECREF(fname);
236 236 Py_DECREF(entry);
237 237 fname = cname = entry = NULL;
238 238 pos += flen;
239 239 }
240 240
241 241 ret = parents;
242 242 Py_INCREF(ret);
243 243 quit:
244 244 Py_XDECREF(fname);
245 245 Py_XDECREF(cname);
246 246 Py_XDECREF(entry);
247 247 Py_XDECREF(parents);
248 248 return ret;
249 249 }
250 250
251 251 /*
252 252 * Build a set of non-normal and other parent entries from the dirstate dmap
253 253 */
254 254 static PyObject *nonnormalotherparententries(PyObject *self, PyObject *args)
255 255 {
256 256 PyObject *dmap, *fname, *v;
257 257 PyObject *nonnset = NULL, *otherpset = NULL, *result = NULL;
258 258 Py_ssize_t pos;
259 259
260 260 if (!PyArg_ParseTuple(args, "O!:nonnormalentries", &PyDict_Type,
261 261 &dmap)) {
262 262 goto bail;
263 263 }
264 264
265 265 nonnset = PySet_New(NULL);
266 266 if (nonnset == NULL) {
267 267 goto bail;
268 268 }
269 269
270 270 otherpset = PySet_New(NULL);
271 271 if (otherpset == NULL) {
272 272 goto bail;
273 273 }
274 274
275 275 pos = 0;
276 276 while (PyDict_Next(dmap, &pos, &fname, &v)) {
277 277 dirstateTupleObject *t;
278 278 if (!dirstate_tuple_check(v)) {
279 279 PyErr_SetString(PyExc_TypeError,
280 280 "expected a dirstate tuple");
281 281 goto bail;
282 282 }
283 283 t = (dirstateTupleObject *)v;
284 284
285 285 if (t->state == 'n' && t->size == -2) {
286 286 if (PySet_Add(otherpset, fname) == -1) {
287 287 goto bail;
288 288 }
289 289 }
290 290
291 291 if (t->state == 'n' && t->mtime != -1) {
292 292 continue;
293 293 }
294 294 if (PySet_Add(nonnset, fname) == -1) {
295 295 goto bail;
296 296 }
297 297 }
298 298
299 299 result = Py_BuildValue("(OO)", nonnset, otherpset);
300 300 if (result == NULL) {
301 301 goto bail;
302 302 }
303 303 Py_DECREF(nonnset);
304 304 Py_DECREF(otherpset);
305 305 return result;
306 306 bail:
307 307 Py_XDECREF(nonnset);
308 308 Py_XDECREF(otherpset);
309 309 Py_XDECREF(result);
310 310 return NULL;
311 311 }
312 312
313 313 /*
314 314 * Efficiently pack a dirstate object into its on-disk format.
315 315 */
316 316 static PyObject *pack_dirstate(PyObject *self, PyObject *args)
317 317 {
318 318 PyObject *packobj = NULL;
319 319 PyObject *map, *copymap, *pl, *mtime_unset = NULL;
320 320 Py_ssize_t nbytes, pos, l;
321 321 PyObject *k, *v = NULL, *pn;
322 322 char *p, *s;
323 323 int now;
324 324
325 325 if (!PyArg_ParseTuple(args, "O!O!O!i:pack_dirstate", &PyDict_Type, &map,
326 326 &PyDict_Type, &copymap, &PyTuple_Type, &pl,
327 327 &now)) {
328 328 return NULL;
329 329 }
330 330
331 331 if (PyTuple_Size(pl) != 2) {
332 332 PyErr_SetString(PyExc_TypeError, "expected 2-element tuple");
333 333 return NULL;
334 334 }
335 335
336 336 /* Figure out how much we need to allocate. */
337 337 for (nbytes = 40, pos = 0; PyDict_Next(map, &pos, &k, &v);) {
338 338 PyObject *c;
339 339 if (!PyBytes_Check(k)) {
340 340 PyErr_SetString(PyExc_TypeError, "expected string key");
341 341 goto bail;
342 342 }
343 343 nbytes += PyBytes_GET_SIZE(k) + 17;
344 344 c = PyDict_GetItem(copymap, k);
345 345 if (c) {
346 346 if (!PyBytes_Check(c)) {
347 347 PyErr_SetString(PyExc_TypeError,
348 348 "expected string key");
349 349 goto bail;
350 350 }
351 351 nbytes += PyBytes_GET_SIZE(c) + 1;
352 352 }
353 353 }
354 354
355 355 packobj = PyBytes_FromStringAndSize(NULL, nbytes);
356 356 if (packobj == NULL) {
357 357 goto bail;
358 358 }
359 359
360 360 p = PyBytes_AS_STRING(packobj);
361 361
362 362 pn = PyTuple_GET_ITEM(pl, 0);
363 363 if (PyBytes_AsStringAndSize(pn, &s, &l) == -1 || l != 20) {
364 364 PyErr_SetString(PyExc_TypeError, "expected a 20-byte hash");
365 365 goto bail;
366 366 }
367 367 memcpy(p, s, l);
368 368 p += 20;
369 369 pn = PyTuple_GET_ITEM(pl, 1);
370 370 if (PyBytes_AsStringAndSize(pn, &s, &l) == -1 || l != 20) {
371 371 PyErr_SetString(PyExc_TypeError, "expected a 20-byte hash");
372 372 goto bail;
373 373 }
374 374 memcpy(p, s, l);
375 375 p += 20;
376 376
377 377 for (pos = 0; PyDict_Next(map, &pos, &k, &v);) {
378 378 dirstateTupleObject *tuple;
379 379 char state;
380 380 int mode, size, mtime;
381 381 Py_ssize_t len, l;
382 382 PyObject *o;
383 383 char *t;
384 384
385 385 if (!dirstate_tuple_check(v)) {
386 386 PyErr_SetString(PyExc_TypeError,
387 387 "expected a dirstate tuple");
388 388 goto bail;
389 389 }
390 390 tuple = (dirstateTupleObject *)v;
391 391
392 392 state = tuple->state;
393 393 mode = tuple->mode;
394 394 size = tuple->size;
395 395 mtime = tuple->mtime;
396 396 if (state == 'n' && mtime == now) {
397 397 /* See pure/parsers.py:pack_dirstate for why we do
398 398 * this. */
399 399 mtime = -1;
400 400 mtime_unset = (PyObject *)make_dirstate_tuple(
401 401 state, mode, size, mtime);
402 402 if (!mtime_unset) {
403 403 goto bail;
404 404 }
405 405 if (PyDict_SetItem(map, k, mtime_unset) == -1) {
406 406 goto bail;
407 407 }
408 408 Py_DECREF(mtime_unset);
409 409 mtime_unset = NULL;
410 410 }
411 411 *p++ = state;
412 412 putbe32((uint32_t)mode, p);
413 413 putbe32((uint32_t)size, p + 4);
414 414 putbe32((uint32_t)mtime, p + 8);
415 415 t = p + 12;
416 416 p += 16;
417 417 len = PyBytes_GET_SIZE(k);
418 418 memcpy(p, PyBytes_AS_STRING(k), len);
419 419 p += len;
420 420 o = PyDict_GetItem(copymap, k);
421 421 if (o) {
422 422 *p++ = '\0';
423 423 l = PyBytes_GET_SIZE(o);
424 424 memcpy(p, PyBytes_AS_STRING(o), l);
425 425 p += l;
426 426 len += l + 1;
427 427 }
428 428 putbe32((uint32_t)len, t);
429 429 }
430 430
431 431 pos = p - PyBytes_AS_STRING(packobj);
432 432 if (pos != nbytes) {
433 433 PyErr_Format(PyExc_SystemError, "bad dirstate size: %ld != %ld",
434 434 (long)pos, (long)nbytes);
435 435 goto bail;
436 436 }
437 437
438 438 return packobj;
439 439 bail:
440 440 Py_XDECREF(mtime_unset);
441 441 Py_XDECREF(packobj);
442 442 Py_XDECREF(v);
443 443 return NULL;
444 444 }
445 445
446 446 #define BUMPED_FIX 1
447 447 #define USING_SHA_256 2
448 448 #define FM1_HEADER_SIZE (4 + 8 + 2 + 2 + 1 + 1 + 1)
449 449
450 450 static PyObject *readshas(const char *source, unsigned char num,
451 451 Py_ssize_t hashwidth)
452 452 {
453 453 int i;
454 454 PyObject *list = PyTuple_New(num);
455 455 if (list == NULL) {
456 456 return NULL;
457 457 }
458 458 for (i = 0; i < num; i++) {
459 459 PyObject *hash = PyBytes_FromStringAndSize(source, hashwidth);
460 460 if (hash == NULL) {
461 461 Py_DECREF(list);
462 462 return NULL;
463 463 }
464 464 PyTuple_SET_ITEM(list, i, hash);
465 465 source += hashwidth;
466 466 }
467 467 return list;
468 468 }
469 469
470 470 static PyObject *fm1readmarker(const char *databegin, const char *dataend,
471 471 uint32_t *msize)
472 472 {
473 473 const char *data = databegin;
474 474 const char *meta;
475 475
476 476 double mtime;
477 477 int16_t tz;
478 478 uint16_t flags;
479 479 unsigned char nsuccs, nparents, nmetadata;
480 480 Py_ssize_t hashwidth = 20;
481 481
482 482 PyObject *prec = NULL, *parents = NULL, *succs = NULL;
483 483 PyObject *metadata = NULL, *ret = NULL;
484 484 int i;
485 485
486 486 if (data + FM1_HEADER_SIZE > dataend) {
487 487 goto overflow;
488 488 }
489 489
490 490 *msize = getbe32(data);
491 491 data += 4;
492 492 mtime = getbefloat64(data);
493 493 data += 8;
494 494 tz = getbeint16(data);
495 495 data += 2;
496 496 flags = getbeuint16(data);
497 497 data += 2;
498 498
499 499 if (flags & USING_SHA_256) {
500 500 hashwidth = 32;
501 501 }
502 502
503 503 nsuccs = (unsigned char)(*data++);
504 504 nparents = (unsigned char)(*data++);
505 505 nmetadata = (unsigned char)(*data++);
506 506
507 507 if (databegin + *msize > dataend) {
508 508 goto overflow;
509 509 }
510 510 dataend = databegin + *msize; /* narrow down to marker size */
511 511
512 512 if (data + hashwidth > dataend) {
513 513 goto overflow;
514 514 }
515 515 prec = PyBytes_FromStringAndSize(data, hashwidth);
516 516 data += hashwidth;
517 517 if (prec == NULL) {
518 518 goto bail;
519 519 }
520 520
521 521 if (data + nsuccs * hashwidth > dataend) {
522 522 goto overflow;
523 523 }
524 524 succs = readshas(data, nsuccs, hashwidth);
525 525 if (succs == NULL) {
526 526 goto bail;
527 527 }
528 528 data += nsuccs * hashwidth;
529 529
530 530 if (nparents == 1 || nparents == 2) {
531 531 if (data + nparents * hashwidth > dataend) {
532 532 goto overflow;
533 533 }
534 534 parents = readshas(data, nparents, hashwidth);
535 535 if (parents == NULL) {
536 536 goto bail;
537 537 }
538 538 data += nparents * hashwidth;
539 539 } else {
540 540 parents = Py_None;
541 541 Py_INCREF(parents);
542 542 }
543 543
544 544 if (data + 2 * nmetadata > dataend) {
545 545 goto overflow;
546 546 }
547 547 meta = data + (2 * nmetadata);
548 548 metadata = PyTuple_New(nmetadata);
549 549 if (metadata == NULL) {
550 550 goto bail;
551 551 }
552 552 for (i = 0; i < nmetadata; i++) {
553 553 PyObject *tmp, *left = NULL, *right = NULL;
554 554 Py_ssize_t leftsize = (unsigned char)(*data++);
555 555 Py_ssize_t rightsize = (unsigned char)(*data++);
556 556 if (meta + leftsize + rightsize > dataend) {
557 557 goto overflow;
558 558 }
559 559 left = PyBytes_FromStringAndSize(meta, leftsize);
560 560 meta += leftsize;
561 561 right = PyBytes_FromStringAndSize(meta, rightsize);
562 562 meta += rightsize;
563 563 tmp = PyTuple_New(2);
564 564 if (!left || !right || !tmp) {
565 565 Py_XDECREF(left);
566 566 Py_XDECREF(right);
567 567 Py_XDECREF(tmp);
568 568 goto bail;
569 569 }
570 570 PyTuple_SET_ITEM(tmp, 0, left);
571 571 PyTuple_SET_ITEM(tmp, 1, right);
572 572 PyTuple_SET_ITEM(metadata, i, tmp);
573 573 }
574 574 ret = Py_BuildValue("(OOHO(di)O)", prec, succs, flags, metadata, mtime,
575 575 (int)tz * 60, parents);
576 576 goto bail; /* return successfully */
577 577
578 578 overflow:
579 579 PyErr_SetString(PyExc_ValueError, "overflow in obsstore");
580 580 bail:
581 581 Py_XDECREF(prec);
582 582 Py_XDECREF(succs);
583 583 Py_XDECREF(metadata);
584 584 Py_XDECREF(parents);
585 585 return ret;
586 586 }
587 587
588 588 static PyObject *fm1readmarkers(PyObject *self, PyObject *args)
589 589 {
590 590 const char *data, *dataend;
591 591 Py_ssize_t datalen, offset, stop;
592 592 PyObject *markers = NULL;
593 593
594 594 if (!PyArg_ParseTuple(args, PY23("s#nn", "y#nn"), &data, &datalen,
595 595 &offset, &stop)) {
596 596 return NULL;
597 597 }
598 598 if (offset < 0) {
599 599 PyErr_SetString(PyExc_ValueError,
600 600 "invalid negative offset in fm1readmarkers");
601 601 return NULL;
602 602 }
603 603 if (stop > datalen) {
604 604 PyErr_SetString(
605 605 PyExc_ValueError,
606 606 "stop longer than data length in fm1readmarkers");
607 607 return NULL;
608 608 }
609 609 dataend = data + datalen;
610 610 data += offset;
611 611 markers = PyList_New(0);
612 612 if (!markers) {
613 613 return NULL;
614 614 }
615 615 while (offset < stop) {
616 616 uint32_t msize;
617 617 int error;
618 618 PyObject *record = fm1readmarker(data, dataend, &msize);
619 619 if (!record) {
620 620 goto bail;
621 621 }
622 622 error = PyList_Append(markers, record);
623 623 Py_DECREF(record);
624 624 if (error) {
625 625 goto bail;
626 626 }
627 627 data += msize;
628 628 offset += msize;
629 629 }
630 630 return markers;
631 631 bail:
632 632 Py_DECREF(markers);
633 633 return NULL;
634 634 }
635 635
636 636 static char parsers_doc[] = "Efficient content parsing.";
637 637
638 638 PyObject *encodedir(PyObject *self, PyObject *args);
639 639 PyObject *pathencode(PyObject *self, PyObject *args);
640 640 PyObject *lowerencode(PyObject *self, PyObject *args);
641 PyObject *parse_index2(PyObject *self, PyObject *args);
641 PyObject *parse_index2(PyObject *self, PyObject *args, PyObject *kwargs);
642 642
643 643 static PyMethodDef methods[] = {
644 644 {"pack_dirstate", pack_dirstate, METH_VARARGS, "pack a dirstate\n"},
645 645 {"nonnormalotherparententries", nonnormalotherparententries, METH_VARARGS,
646 646 "create a set containing non-normal and other parent entries of given "
647 647 "dirstate\n"},
648 648 {"parse_dirstate", parse_dirstate, METH_VARARGS, "parse a dirstate\n"},
649 {"parse_index2", parse_index2, METH_VARARGS, "parse a revlog index\n"},
649 {"parse_index2", (PyCFunction)parse_index2, METH_VARARGS | METH_KEYWORDS,
650 "parse a revlog index\n"},
650 651 {"isasciistr", isasciistr, METH_VARARGS, "check if an ASCII string\n"},
651 652 {"asciilower", asciilower, METH_VARARGS, "lowercase an ASCII string\n"},
652 653 {"asciiupper", asciiupper, METH_VARARGS, "uppercase an ASCII string\n"},
653 654 {"dict_new_presized", dict_new_presized, METH_VARARGS,
654 655 "construct a dict with an expected size\n"},
655 656 {"make_file_foldmap", make_file_foldmap, METH_VARARGS,
656 657 "make file foldmap\n"},
657 658 {"jsonescapeu8fast", jsonescapeu8fast, METH_VARARGS,
658 659 "escape a UTF-8 byte string to JSON (fast path)\n"},
659 660 {"encodedir", encodedir, METH_VARARGS, "encodedir a path\n"},
660 661 {"pathencode", pathencode, METH_VARARGS, "fncache-encode a path\n"},
661 662 {"lowerencode", lowerencode, METH_VARARGS, "lower-encode a path\n"},
662 663 {"fm1readmarkers", fm1readmarkers, METH_VARARGS,
663 664 "parse v1 obsolete markers\n"},
664 665 {NULL, NULL}};
665 666
666 667 void dirs_module_init(PyObject *mod);
667 668 void manifest_module_init(PyObject *mod);
668 669 void revlog_module_init(PyObject *mod);
669 670
670 671 static const int version = 17;
671 672
672 673 static void module_init(PyObject *mod)
673 674 {
674 675 PyObject *capsule = NULL;
675 676 PyModule_AddIntConstant(mod, "version", version);
676 677
677 678 /* This module constant has two purposes. First, it lets us unit test
678 679 * the ImportError raised without hard-coding any error text. This
679 680 * means we can change the text in the future without breaking tests,
680 681 * even across changesets without a recompile. Second, its presence
681 682 * can be used to determine whether the version-checking logic is
682 683 * present, which also helps in testing across changesets without a
683 684 * recompile. Note that this means the pure-Python version of parsers
684 685 * should not have this module constant. */
685 686 PyModule_AddStringConstant(mod, "versionerrortext", versionerrortext);
686 687
687 688 dirs_module_init(mod);
688 689 manifest_module_init(mod);
689 690 revlog_module_init(mod);
690 691
691 692 capsule = PyCapsule_New(
692 693 make_dirstate_tuple,
693 694 "mercurial.cext.parsers.make_dirstate_tuple_CAPI", NULL);
694 695 if (capsule != NULL)
695 696 PyModule_AddObject(mod, "make_dirstate_tuple_CAPI", capsule);
696 697
697 698 if (PyType_Ready(&dirstateTupleType) < 0) {
698 699 return;
699 700 }
700 701 Py_INCREF(&dirstateTupleType);
701 702 PyModule_AddObject(mod, "dirstatetuple",
702 703 (PyObject *)&dirstateTupleType);
703 704 }
704 705
705 706 static int check_python_version(void)
706 707 {
707 708 PyObject *sys = PyImport_ImportModule("sys"), *ver;
708 709 long hexversion;
709 710 if (!sys) {
710 711 return -1;
711 712 }
712 713 ver = PyObject_GetAttrString(sys, "hexversion");
713 714 Py_DECREF(sys);
714 715 if (!ver) {
715 716 return -1;
716 717 }
717 718 hexversion = PyInt_AsLong(ver);
718 719 Py_DECREF(ver);
719 720 /* sys.hexversion is a 32-bit number by default, so the -1 case
720 721 * should only occur in unusual circumstances (e.g. if sys.hexversion
721 722 * is manually set to an invalid value). */
722 723 if ((hexversion == -1) || (hexversion >> 16 != PY_VERSION_HEX >> 16)) {
723 724 PyErr_Format(PyExc_ImportError,
724 725 "%s: The Mercurial extension "
725 726 "modules were compiled with Python " PY_VERSION
726 727 ", but "
727 728 "Mercurial is currently using Python with "
728 729 "sys.hexversion=%ld: "
729 730 "Python %s\n at: %s",
730 731 versionerrortext, hexversion, Py_GetVersion(),
731 732 Py_GetProgramFullPath());
732 733 return -1;
733 734 }
734 735 return 0;
735 736 }
736 737
737 738 #ifdef IS_PY3K
738 739 static struct PyModuleDef parsers_module = {PyModuleDef_HEAD_INIT, "parsers",
739 740 parsers_doc, -1, methods};
740 741
741 742 PyMODINIT_FUNC PyInit_parsers(void)
742 743 {
743 744 PyObject *mod;
744 745
745 746 if (check_python_version() == -1)
746 747 return NULL;
747 748 mod = PyModule_Create(&parsers_module);
748 749 module_init(mod);
749 750 return mod;
750 751 }
751 752 #else
752 753 PyMODINIT_FUNC initparsers(void)
753 754 {
754 755 PyObject *mod;
755 756
756 757 if (check_python_version() == -1) {
757 758 return;
758 759 }
759 760 mod = Py_InitModule3("parsers", methods, parsers_doc);
760 761 module_init(mod);
761 762 }
762 763 #endif
@@ -1,2867 +1,2926 b''
1 1 /*
2 2 parsers.c - efficient content parsing
3 3
4 4 Copyright 2008 Matt Mackall <mpm@selenic.com> and others
5 5
6 6 This software may be used and distributed according to the terms of
7 7 the GNU General Public License, incorporated herein by reference.
8 8 */
9 9
10 10 #define PY_SSIZE_T_CLEAN
11 11 #include <Python.h>
12 12 #include <assert.h>
13 13 #include <ctype.h>
14 14 #include <limits.h>
15 15 #include <stddef.h>
16 16 #include <stdlib.h>
17 17 #include <string.h>
18 18
19 19 #include "bitmanipulation.h"
20 20 #include "charencode.h"
21 21 #include "compat.h"
22 22 #include "revlog.h"
23 23 #include "util.h"
24 24
25 25 #ifdef IS_PY3K
26 26 /* The mapping of Python types is meant to be temporary to get Python
27 27 * 3 to compile. We should remove this once Python 3 support is fully
28 28 * supported and proper types are used in the extensions themselves. */
29 29 #define PyInt_Check PyLong_Check
30 30 #define PyInt_FromLong PyLong_FromLong
31 31 #define PyInt_FromSsize_t PyLong_FromSsize_t
32 32 #define PyInt_AsLong PyLong_AsLong
33 33 #endif
34 34
35 35 typedef struct indexObjectStruct indexObject;
36 36
37 37 typedef struct {
38 38 int children[16];
39 39 } nodetreenode;
40 40
41 41 typedef struct {
42 42 int abi_version;
43 43 Py_ssize_t (*index_length)(const indexObject *);
44 44 const char *(*index_node)(indexObject *, Py_ssize_t);
45 45 int (*index_parents)(PyObject *, int, int *);
46 46 } Revlog_CAPI;
47 47
48 48 /*
49 49 * A base-16 trie for fast node->rev mapping.
50 50 *
51 51 * Positive value is index of the next node in the trie
52 52 * Negative value is a leaf: -(rev + 2)
53 53 * Zero is empty
54 54 */
55 55 typedef struct {
56 56 indexObject *index;
57 57 nodetreenode *nodes;
58 58 Py_ssize_t nodelen;
59 59 size_t length; /* # nodes in use */
60 60 size_t capacity; /* # nodes allocated */
61 61 int depth; /* maximum depth of tree */
62 62 int splits; /* # splits performed */
63 63 } nodetree;
64 64
65 65 typedef struct {
66 66 PyObject_HEAD /* ; */
67 67 nodetree nt;
68 68 } nodetreeObject;
69 69
70 70 /*
71 71 * This class has two behaviors.
72 72 *
73 73 * When used in a list-like way (with integer keys), we decode an
74 74 * entry in a RevlogNG index file on demand. We have limited support for
75 75 * integer-keyed insert and delete, only at elements right before the
76 76 * end.
77 77 *
78 78 * With string keys, we lazily perform a reverse mapping from node to
79 79 * rev, using a base-16 trie.
80 80 */
81 81 struct indexObjectStruct {
82 82 PyObject_HEAD
83 83 /* Type-specific fields go here. */
84 84 PyObject *data; /* raw bytes of index */
85 85 Py_ssize_t nodelen; /* digest size of the hash, 20 for SHA-1 */
86 86 PyObject *nullentry; /* fast path for references to null */
87 87 Py_buffer buf; /* buffer of data */
88 88 const char **offsets; /* populated on demand */
89 89 Py_ssize_t length; /* current on-disk number of elements */
90 90 unsigned new_length; /* number of added elements */
91 91 unsigned added_length; /* space reserved for added elements */
92 92 char *added; /* populated on demand */
93 93 PyObject *headrevs; /* cache, invalidated on changes */
94 94 PyObject *filteredrevs; /* filtered revs set */
95 95 nodetree nt; /* base-16 trie */
96 96 int ntinitialized; /* 0 or 1 */
97 97 int ntrev; /* last rev scanned */
98 98 int ntlookups; /* # lookups */
99 99 int ntmisses; /* # lookups that miss the cache */
100 100 int inlined;
101 long hdrsize; /* size of index headers. Differs in v1 v.s. v2 format */
101 102 };
102 103
103 104 static Py_ssize_t index_length(const indexObject *self)
104 105 {
105 106 return self->length + self->new_length;
106 107 }
107 108
108 109 static const char nullid[32] = {0};
109 110 static const Py_ssize_t nullrev = -1;
110 111
111 112 static Py_ssize_t inline_scan(indexObject *self, const char **offsets);
112 113
113 114 static int index_find_node(indexObject *self, const char *node);
114 115
115 116 #if LONG_MAX == 0x7fffffffL
116 static const char *const tuple_format = PY23("Kiiiiiis#", "Kiiiiiiy#");
117 static const char *const v1_tuple_format = PY23("Kiiiiiis#", "Kiiiiiiy#");
118 static const char *const v2_tuple_format =
119 PY23("Kiiiiiis#Ki", "Kiiiiiiy#Ki");
117 120 #else
118 static const char *const tuple_format = PY23("kiiiiiis#", "kiiiiiiy#");
121 static const char *const v1_tuple_format = PY23("kiiiiiis#", "kiiiiiiy#");
122 static const char *const v2_tuple_format =
123 PY23("kiiiiiis#ki", "kiiiiiiy#ki");
119 124 #endif
120 125
121 126 /* A RevlogNG v1 index entry is 64 bytes long. */
122 127 static const long v1_hdrsize = 64;
123 128
129 /* A Revlogv2 index entry is 96 bytes long. */
130 static const long v2_hdrsize = 96;
131
124 132 static void raise_revlog_error(void)
125 133 {
126 134 PyObject *mod = NULL, *dict = NULL, *errclass = NULL;
127 135
128 136 mod = PyImport_ImportModule("mercurial.error");
129 137 if (mod == NULL) {
130 138 goto cleanup;
131 139 }
132 140
133 141 dict = PyModule_GetDict(mod);
134 142 if (dict == NULL) {
135 143 goto cleanup;
136 144 }
137 145 Py_INCREF(dict);
138 146
139 147 errclass = PyDict_GetItemString(dict, "RevlogError");
140 148 if (errclass == NULL) {
141 149 PyErr_SetString(PyExc_SystemError,
142 150 "could not find RevlogError");
143 151 goto cleanup;
144 152 }
145 153
146 154 /* value of exception is ignored by callers */
147 155 PyErr_SetString(errclass, "RevlogError");
148 156
149 157 cleanup:
150 158 Py_XDECREF(dict);
151 159 Py_XDECREF(mod);
152 160 }
153 161
154 162 /*
155 163 * Return a pointer to the beginning of a RevlogNG record.
156 164 */
157 165 static const char *index_deref(indexObject *self, Py_ssize_t pos)
158 166 {
159 167 if (pos >= self->length)
160 return self->added + (pos - self->length) * v1_hdrsize;
168 return self->added + (pos - self->length) * self->hdrsize;
161 169
162 170 if (self->inlined && pos > 0) {
163 171 if (self->offsets == NULL) {
164 172 Py_ssize_t ret;
165 173 self->offsets =
166 174 PyMem_Malloc(self->length * sizeof(*self->offsets));
167 175 if (self->offsets == NULL)
168 176 return (const char *)PyErr_NoMemory();
169 177 ret = inline_scan(self, self->offsets);
170 178 if (ret == -1) {
171 179 return NULL;
172 180 };
173 181 }
174 182 return self->offsets[pos];
175 183 }
176 184
177 return (const char *)(self->buf.buf) + pos * v1_hdrsize;
185 return (const char *)(self->buf.buf) + pos * self->hdrsize;
178 186 }
179 187
180 188 /*
181 189 * Get parents of the given rev.
182 190 *
183 191 * The specified rev must be valid and must not be nullrev. A returned
184 192 * parent revision may be nullrev, but is guaranteed to be in valid range.
185 193 */
186 194 static inline int index_get_parents(indexObject *self, Py_ssize_t rev, int *ps,
187 195 int maxrev)
188 196 {
189 197 const char *data = index_deref(self, rev);
190 198
191 199 ps[0] = getbe32(data + 24);
192 200 ps[1] = getbe32(data + 28);
193 201
194 202 /* If index file is corrupted, ps[] may point to invalid revisions. So
195 203 * there is a risk of buffer overflow to trust them unconditionally. */
196 204 if (ps[0] < -1 || ps[0] > maxrev || ps[1] < -1 || ps[1] > maxrev) {
197 205 PyErr_SetString(PyExc_ValueError, "parent out of range");
198 206 return -1;
199 207 }
200 208 return 0;
201 209 }
202 210
203 211 /*
204 212 * Get parents of the given rev.
205 213 *
206 214 * If the specified rev is out of range, IndexError will be raised. If the
207 215 * revlog entry is corrupted, ValueError may be raised.
208 216 *
209 217 * Returns 0 on success or -1 on failure.
210 218 */
211 219 static int HgRevlogIndex_GetParents(PyObject *op, int rev, int *ps)
212 220 {
213 221 int tiprev;
214 222 if (!op || !HgRevlogIndex_Check(op) || !ps) {
215 223 PyErr_BadInternalCall();
216 224 return -1;
217 225 }
218 226 tiprev = (int)index_length((indexObject *)op) - 1;
219 227 if (rev < -1 || rev > tiprev) {
220 228 PyErr_Format(PyExc_IndexError, "rev out of range: %d", rev);
221 229 return -1;
222 230 } else if (rev == -1) {
223 231 ps[0] = ps[1] = -1;
224 232 return 0;
225 233 } else {
226 234 return index_get_parents((indexObject *)op, rev, ps, tiprev);
227 235 }
228 236 }
229 237
230 238 static inline int64_t index_get_start(indexObject *self, Py_ssize_t rev)
231 239 {
232 240 const char *data;
233 241 uint64_t offset;
234 242
235 243 if (rev == nullrev)
236 244 return 0;
237 245
238 246 data = index_deref(self, rev);
239 247 offset = getbe32(data + 4);
240 248 if (rev == 0) {
241 249 /* mask out version number for the first entry */
242 250 offset &= 0xFFFF;
243 251 } else {
244 252 uint32_t offset_high = getbe32(data);
245 253 offset |= ((uint64_t)offset_high) << 32;
246 254 }
247 255 return (int64_t)(offset >> 16);
248 256 }
249 257
250 258 static inline int index_get_length(indexObject *self, Py_ssize_t rev)
251 259 {
252 260 const char *data;
253 261 int tmp;
254 262
255 263 if (rev == nullrev)
256 264 return 0;
257 265
258 266 data = index_deref(self, rev);
259 267
260 268 tmp = (int)getbe32(data + 8);
261 269 if (tmp < 0) {
262 270 PyErr_Format(PyExc_OverflowError,
263 271 "revlog entry size out of bound (%d)", tmp);
264 272 return -1;
265 273 }
266 274 return tmp;
267 275 }
268 276
269 277 /*
270 278 * RevlogNG format (all in big endian, data may be inlined):
271 279 * 6 bytes: offset
272 280 * 2 bytes: flags
273 281 * 4 bytes: compressed length
274 282 * 4 bytes: uncompressed length
275 283 * 4 bytes: base revision
276 284 * 4 bytes: link revision
277 285 * 4 bytes: parent 1 revision
278 286 * 4 bytes: parent 2 revision
279 287 * 32 bytes: nodeid (only 20 bytes used with SHA-1)
280 288 */
281 289 static PyObject *index_get(indexObject *self, Py_ssize_t pos)
282 290 {
283 uint64_t offset_flags;
284 int comp_len, uncomp_len, base_rev, link_rev, parent_1, parent_2;
291 uint64_t offset_flags, sidedata_offset;
292 int comp_len, uncomp_len, base_rev, link_rev, parent_1, parent_2,
293 sidedata_comp_len;
285 294 const char *c_node_id;
286 295 const char *data;
287 296 Py_ssize_t length = index_length(self);
288 297
289 298 if (pos == nullrev) {
290 299 Py_INCREF(self->nullentry);
291 300 return self->nullentry;
292 301 }
293 302
294 303 if (pos < 0 || pos >= length) {
295 304 PyErr_SetString(PyExc_IndexError, "revlog index out of range");
296 305 return NULL;
297 306 }
298 307
299 308 data = index_deref(self, pos);
300 309 if (data == NULL)
301 310 return NULL;
302 311
303 312 offset_flags = getbe32(data + 4);
304 313 /*
305 314 * The first entry on-disk needs the version number masked out,
306 315 * but this doesn't apply if entries are added to an empty index.
307 316 */
308 317 if (self->length && pos == 0)
309 318 offset_flags &= 0xFFFF;
310 319 else {
311 320 uint32_t offset_high = getbe32(data);
312 321 offset_flags |= ((uint64_t)offset_high) << 32;
313 322 }
314 323
315 324 comp_len = getbe32(data + 8);
316 325 uncomp_len = getbe32(data + 12);
317 326 base_rev = getbe32(data + 16);
318 327 link_rev = getbe32(data + 20);
319 328 parent_1 = getbe32(data + 24);
320 329 parent_2 = getbe32(data + 28);
321 330 c_node_id = data + 32;
322 331
323 return Py_BuildValue(tuple_format, offset_flags, comp_len, uncomp_len,
324 base_rev, link_rev, parent_1, parent_2, c_node_id,
325 self->nodelen);
332 if (self->hdrsize == v1_hdrsize) {
333 return Py_BuildValue(v1_tuple_format, offset_flags, comp_len,
334 uncomp_len, base_rev, link_rev, parent_1,
335 parent_2, c_node_id, self->nodelen);
336 } else {
337 sidedata_offset = getbe64(data + 64);
338 sidedata_comp_len = getbe32(data + 72);
339
340 return Py_BuildValue(v2_tuple_format, offset_flags, comp_len,
341 uncomp_len, base_rev, link_rev, parent_1,
342 parent_2, c_node_id, self->nodelen,
343 sidedata_offset, sidedata_comp_len);
344 }
326 345 }
327 346
328 347 /*
329 348 * Return the hash of node corresponding to the given rev.
330 349 */
331 350 static const char *index_node(indexObject *self, Py_ssize_t pos)
332 351 {
333 352 Py_ssize_t length = index_length(self);
334 353 const char *data;
335 354
336 355 if (pos == nullrev)
337 356 return nullid;
338 357
339 358 if (pos >= length)
340 359 return NULL;
341 360
342 361 data = index_deref(self, pos);
343 362 return data ? data + 32 : NULL;
344 363 }
345 364
346 365 /*
347 366 * Return the hash of the node corresponding to the given rev. The
348 367 * rev is assumed to be existing. If not, an exception is set.
349 368 */
350 369 static const char *index_node_existing(indexObject *self, Py_ssize_t pos)
351 370 {
352 371 const char *node = index_node(self, pos);
353 372 if (node == NULL) {
354 373 PyErr_Format(PyExc_IndexError, "could not access rev %d",
355 374 (int)pos);
356 375 }
357 376 return node;
358 377 }
359 378
360 379 static int nt_insert(nodetree *self, const char *node, int rev);
361 380
362 381 static int node_check(Py_ssize_t nodelen, PyObject *obj, char **node)
363 382 {
364 383 Py_ssize_t thisnodelen;
365 384 if (PyBytes_AsStringAndSize(obj, node, &thisnodelen) == -1)
366 385 return -1;
367 386 if (nodelen == thisnodelen)
368 387 return 0;
369 388 PyErr_Format(PyExc_ValueError, "node len %zd != expected node len %zd",
370 389 thisnodelen, nodelen);
371 390 return -1;
372 391 }
373 392
374 393 static PyObject *index_append(indexObject *self, PyObject *obj)
375 394 {
376 uint64_t offset_flags;
395 uint64_t offset_flags, sidedata_offset;
377 396 int rev, comp_len, uncomp_len, base_rev, link_rev, parent_1, parent_2;
378 Py_ssize_t c_node_id_len;
397 Py_ssize_t c_node_id_len, sidedata_comp_len;
379 398 const char *c_node_id;
380 399 char *data;
381 400
382 if (!PyArg_ParseTuple(obj, tuple_format, &offset_flags, &comp_len,
383 &uncomp_len, &base_rev, &link_rev, &parent_1,
384 &parent_2, &c_node_id, &c_node_id_len)) {
385 PyErr_SetString(PyExc_TypeError, "8-tuple required");
386 return NULL;
401 if (self->hdrsize == v1_hdrsize) {
402 if (!PyArg_ParseTuple(obj, v1_tuple_format, &offset_flags,
403 &comp_len, &uncomp_len, &base_rev,
404 &link_rev, &parent_1, &parent_2,
405 &c_node_id, &c_node_id_len)) {
406 PyErr_SetString(PyExc_TypeError, "8-tuple required");
407 return NULL;
408 }
409 } else {
410 if (!PyArg_ParseTuple(
411 obj, v2_tuple_format, &offset_flags, &comp_len,
412 &uncomp_len, &base_rev, &link_rev, &parent_1, &parent_2,
413 &c_node_id, &c_node_id_len, &sidedata_offset, &sidedata_comp_len)) {
414 PyErr_SetString(PyExc_TypeError, "10-tuple required");
415 return NULL;
416 }
387 417 }
418
388 419 if (c_node_id_len != self->nodelen) {
389 420 PyErr_SetString(PyExc_TypeError, "invalid node");
390 421 return NULL;
391 422 }
392 423
393 424 if (self->new_length == self->added_length) {
394 425 size_t new_added_length =
395 426 self->added_length ? self->added_length * 2 : 4096;
396 void *new_added =
397 PyMem_Realloc(self->added, new_added_length * v1_hdrsize);
427 void *new_added = PyMem_Realloc(self->added, new_added_length *
428 self->hdrsize);
398 429 if (!new_added)
399 430 return PyErr_NoMemory();
400 431 self->added = new_added;
401 432 self->added_length = new_added_length;
402 433 }
403 434 rev = self->length + self->new_length;
404 data = self->added + v1_hdrsize * self->new_length++;
435 data = self->added + self->hdrsize * self->new_length++;
405 436 putbe32(offset_flags >> 32, data);
406 437 putbe32(offset_flags & 0xffffffffU, data + 4);
407 438 putbe32(comp_len, data + 8);
408 439 putbe32(uncomp_len, data + 12);
409 440 putbe32(base_rev, data + 16);
410 441 putbe32(link_rev, data + 20);
411 442 putbe32(parent_1, data + 24);
412 443 putbe32(parent_2, data + 28);
413 444 memcpy(data + 32, c_node_id, c_node_id_len);
445 /* Padding since SHA-1 is only 20 bytes for now */
414 446 memset(data + 32 + c_node_id_len, 0, 32 - c_node_id_len);
447 if (self->hdrsize != v1_hdrsize) {
448 putbe64(sidedata_offset, data + 64);
449 putbe32(sidedata_comp_len, data + 72);
450 /* Padding for 96 bytes alignment */
451 memset(data + 76, 0, self->hdrsize - 76);
452 }
415 453
416 454 if (self->ntinitialized)
417 455 nt_insert(&self->nt, c_node_id, rev);
418 456
419 457 Py_CLEAR(self->headrevs);
420 458 Py_RETURN_NONE;
421 459 }
422 460
423 461 static PyObject *index_stats(indexObject *self)
424 462 {
425 463 PyObject *obj = PyDict_New();
426 464 PyObject *s = NULL;
427 465 PyObject *t = NULL;
428 466
429 467 if (obj == NULL)
430 468 return NULL;
431 469
432 470 #define istat(__n, __d) \
433 471 do { \
434 472 s = PyBytes_FromString(__d); \
435 473 t = PyInt_FromSsize_t(self->__n); \
436 474 if (!s || !t) \
437 475 goto bail; \
438 476 if (PyDict_SetItem(obj, s, t) == -1) \
439 477 goto bail; \
440 478 Py_CLEAR(s); \
441 479 Py_CLEAR(t); \
442 480 } while (0)
443 481
444 482 if (self->added_length)
445 483 istat(new_length, "index entries added");
446 484 istat(length, "revs in memory");
447 485 istat(ntlookups, "node trie lookups");
448 486 istat(ntmisses, "node trie misses");
449 487 istat(ntrev, "node trie last rev scanned");
450 488 if (self->ntinitialized) {
451 489 istat(nt.capacity, "node trie capacity");
452 490 istat(nt.depth, "node trie depth");
453 491 istat(nt.length, "node trie count");
454 492 istat(nt.splits, "node trie splits");
455 493 }
456 494
457 495 #undef istat
458 496
459 497 return obj;
460 498
461 499 bail:
462 500 Py_XDECREF(obj);
463 501 Py_XDECREF(s);
464 502 Py_XDECREF(t);
465 503 return NULL;
466 504 }
467 505
468 506 /*
469 507 * When we cache a list, we want to be sure the caller can't mutate
470 508 * the cached copy.
471 509 */
472 510 static PyObject *list_copy(PyObject *list)
473 511 {
474 512 Py_ssize_t len = PyList_GET_SIZE(list);
475 513 PyObject *newlist = PyList_New(len);
476 514 Py_ssize_t i;
477 515
478 516 if (newlist == NULL)
479 517 return NULL;
480 518
481 519 for (i = 0; i < len; i++) {
482 520 PyObject *obj = PyList_GET_ITEM(list, i);
483 521 Py_INCREF(obj);
484 522 PyList_SET_ITEM(newlist, i, obj);
485 523 }
486 524
487 525 return newlist;
488 526 }
489 527
490 528 static int check_filter(PyObject *filter, Py_ssize_t arg)
491 529 {
492 530 if (filter) {
493 531 PyObject *arglist, *result;
494 532 int isfiltered;
495 533
496 534 arglist = Py_BuildValue("(n)", arg);
497 535 if (!arglist) {
498 536 return -1;
499 537 }
500 538
501 539 result = PyObject_Call(filter, arglist, NULL);
502 540 Py_DECREF(arglist);
503 541 if (!result) {
504 542 return -1;
505 543 }
506 544
507 545 /* PyObject_IsTrue returns 1 if true, 0 if false, -1 if error,
508 546 * same as this function, so we can just return it directly.*/
509 547 isfiltered = PyObject_IsTrue(result);
510 548 Py_DECREF(result);
511 549 return isfiltered;
512 550 } else {
513 551 return 0;
514 552 }
515 553 }
516 554
517 555 static inline void set_phase_from_parents(char *phases, int parent_1,
518 556 int parent_2, Py_ssize_t i)
519 557 {
520 558 if (parent_1 >= 0 && phases[parent_1] > phases[i])
521 559 phases[i] = phases[parent_1];
522 560 if (parent_2 >= 0 && phases[parent_2] > phases[i])
523 561 phases[i] = phases[parent_2];
524 562 }
525 563
526 564 static PyObject *reachableroots2(indexObject *self, PyObject *args)
527 565 {
528 566
529 567 /* Input */
530 568 long minroot;
531 569 PyObject *includepatharg = NULL;
532 570 int includepath = 0;
533 571 /* heads and roots are lists */
534 572 PyObject *heads = NULL;
535 573 PyObject *roots = NULL;
536 574 PyObject *reachable = NULL;
537 575
538 576 PyObject *val;
539 577 Py_ssize_t len = index_length(self);
540 578 long revnum;
541 579 Py_ssize_t k;
542 580 Py_ssize_t i;
543 581 Py_ssize_t l;
544 582 int r;
545 583 int parents[2];
546 584
547 585 /* Internal data structure:
548 586 * tovisit: array of length len+1 (all revs + nullrev), filled upto
549 587 * lentovisit
550 588 *
551 589 * revstates: array of length len+1 (all revs + nullrev) */
552 590 int *tovisit = NULL;
553 591 long lentovisit = 0;
554 592 enum { RS_SEEN = 1, RS_ROOT = 2, RS_REACHABLE = 4 };
555 593 char *revstates = NULL;
556 594
557 595 /* Get arguments */
558 596 if (!PyArg_ParseTuple(args, "lO!O!O!", &minroot, &PyList_Type, &heads,
559 597 &PyList_Type, &roots, &PyBool_Type,
560 598 &includepatharg))
561 599 goto bail;
562 600
563 601 if (includepatharg == Py_True)
564 602 includepath = 1;
565 603
566 604 /* Initialize return set */
567 605 reachable = PyList_New(0);
568 606 if (reachable == NULL)
569 607 goto bail;
570 608
571 609 /* Initialize internal datastructures */
572 610 tovisit = (int *)malloc((len + 1) * sizeof(int));
573 611 if (tovisit == NULL) {
574 612 PyErr_NoMemory();
575 613 goto bail;
576 614 }
577 615
578 616 revstates = (char *)calloc(len + 1, 1);
579 617 if (revstates == NULL) {
580 618 PyErr_NoMemory();
581 619 goto bail;
582 620 }
583 621
584 622 l = PyList_GET_SIZE(roots);
585 623 for (i = 0; i < l; i++) {
586 624 revnum = PyInt_AsLong(PyList_GET_ITEM(roots, i));
587 625 if (revnum == -1 && PyErr_Occurred())
588 626 goto bail;
589 627 /* If root is out of range, e.g. wdir(), it must be unreachable
590 628 * from heads. So we can just ignore it. */
591 629 if (revnum + 1 < 0 || revnum + 1 >= len + 1)
592 630 continue;
593 631 revstates[revnum + 1] |= RS_ROOT;
594 632 }
595 633
596 634 /* Populate tovisit with all the heads */
597 635 l = PyList_GET_SIZE(heads);
598 636 for (i = 0; i < l; i++) {
599 637 revnum = PyInt_AsLong(PyList_GET_ITEM(heads, i));
600 638 if (revnum == -1 && PyErr_Occurred())
601 639 goto bail;
602 640 if (revnum + 1 < 0 || revnum + 1 >= len + 1) {
603 641 PyErr_SetString(PyExc_IndexError, "head out of range");
604 642 goto bail;
605 643 }
606 644 if (!(revstates[revnum + 1] & RS_SEEN)) {
607 645 tovisit[lentovisit++] = (int)revnum;
608 646 revstates[revnum + 1] |= RS_SEEN;
609 647 }
610 648 }
611 649
612 650 /* Visit the tovisit list and find the reachable roots */
613 651 k = 0;
614 652 while (k < lentovisit) {
615 653 /* Add the node to reachable if it is a root*/
616 654 revnum = tovisit[k++];
617 655 if (revstates[revnum + 1] & RS_ROOT) {
618 656 revstates[revnum + 1] |= RS_REACHABLE;
619 657 val = PyInt_FromLong(revnum);
620 658 if (val == NULL)
621 659 goto bail;
622 660 r = PyList_Append(reachable, val);
623 661 Py_DECREF(val);
624 662 if (r < 0)
625 663 goto bail;
626 664 if (includepath == 0)
627 665 continue;
628 666 }
629 667
630 668 /* Add its parents to the list of nodes to visit */
631 669 if (revnum == nullrev)
632 670 continue;
633 671 r = index_get_parents(self, revnum, parents, (int)len - 1);
634 672 if (r < 0)
635 673 goto bail;
636 674 for (i = 0; i < 2; i++) {
637 675 if (!(revstates[parents[i] + 1] & RS_SEEN) &&
638 676 parents[i] >= minroot) {
639 677 tovisit[lentovisit++] = parents[i];
640 678 revstates[parents[i] + 1] |= RS_SEEN;
641 679 }
642 680 }
643 681 }
644 682
645 683 /* Find all the nodes in between the roots we found and the heads
646 684 * and add them to the reachable set */
647 685 if (includepath == 1) {
648 686 long minidx = minroot;
649 687 if (minidx < 0)
650 688 minidx = 0;
651 689 for (i = minidx; i < len; i++) {
652 690 if (!(revstates[i + 1] & RS_SEEN))
653 691 continue;
654 692 r = index_get_parents(self, i, parents, (int)len - 1);
655 693 /* Corrupted index file, error is set from
656 694 * index_get_parents */
657 695 if (r < 0)
658 696 goto bail;
659 697 if (((revstates[parents[0] + 1] |
660 698 revstates[parents[1] + 1]) &
661 699 RS_REACHABLE) &&
662 700 !(revstates[i + 1] & RS_REACHABLE)) {
663 701 revstates[i + 1] |= RS_REACHABLE;
664 702 val = PyInt_FromSsize_t(i);
665 703 if (val == NULL)
666 704 goto bail;
667 705 r = PyList_Append(reachable, val);
668 706 Py_DECREF(val);
669 707 if (r < 0)
670 708 goto bail;
671 709 }
672 710 }
673 711 }
674 712
675 713 free(revstates);
676 714 free(tovisit);
677 715 return reachable;
678 716 bail:
679 717 Py_XDECREF(reachable);
680 718 free(revstates);
681 719 free(tovisit);
682 720 return NULL;
683 721 }
684 722
685 723 static int add_roots_get_min(indexObject *self, PyObject *roots, char *phases,
686 724 char phase)
687 725 {
688 726 Py_ssize_t len = index_length(self);
689 727 PyObject *item;
690 728 PyObject *iterator;
691 729 int rev, minrev = -1;
692 730 char *node;
693 731
694 732 if (!PySet_Check(roots)) {
695 733 PyErr_SetString(PyExc_TypeError,
696 734 "roots must be a set of nodes");
697 735 return -2;
698 736 }
699 737 iterator = PyObject_GetIter(roots);
700 738 if (iterator == NULL)
701 739 return -2;
702 740 while ((item = PyIter_Next(iterator))) {
703 741 if (node_check(self->nodelen, item, &node) == -1)
704 742 goto failed;
705 743 rev = index_find_node(self, node);
706 744 /* null is implicitly public, so negative is invalid */
707 745 if (rev < 0 || rev >= len)
708 746 goto failed;
709 747 phases[rev] = phase;
710 748 if (minrev == -1 || minrev > rev)
711 749 minrev = rev;
712 750 Py_DECREF(item);
713 751 }
714 752 Py_DECREF(iterator);
715 753 return minrev;
716 754 failed:
717 755 Py_DECREF(iterator);
718 756 Py_DECREF(item);
719 757 return -2;
720 758 }
721 759
722 760 static PyObject *compute_phases_map_sets(indexObject *self, PyObject *args)
723 761 {
724 762 /* 0: public (untracked), 1: draft, 2: secret, 32: archive,
725 763 96: internal */
726 764 static const char trackedphases[] = {1, 2, 32, 96};
727 765 PyObject *roots = Py_None;
728 766 PyObject *phasesetsdict = NULL;
729 767 PyObject *phasesets[4] = {NULL, NULL, NULL, NULL};
730 768 Py_ssize_t len = index_length(self);
731 769 char *phases = NULL;
732 770 int minphaserev = -1, rev, i;
733 771 const int numphases = (int)(sizeof(phasesets) / sizeof(phasesets[0]));
734 772
735 773 if (!PyArg_ParseTuple(args, "O", &roots))
736 774 return NULL;
737 775 if (roots == NULL || !PyDict_Check(roots)) {
738 776 PyErr_SetString(PyExc_TypeError, "roots must be a dictionary");
739 777 return NULL;
740 778 }
741 779
742 780 phases = calloc(len, 1);
743 781 if (phases == NULL) {
744 782 PyErr_NoMemory();
745 783 return NULL;
746 784 }
747 785
748 786 for (i = 0; i < numphases; ++i) {
749 787 PyObject *pyphase = PyInt_FromLong(trackedphases[i]);
750 788 PyObject *phaseroots = NULL;
751 789 if (pyphase == NULL)
752 790 goto release;
753 791 phaseroots = PyDict_GetItem(roots, pyphase);
754 792 Py_DECREF(pyphase);
755 793 if (phaseroots == NULL)
756 794 continue;
757 795 rev = add_roots_get_min(self, phaseroots, phases,
758 796 trackedphases[i]);
759 797 if (rev == -2)
760 798 goto release;
761 799 if (rev != -1 && (minphaserev == -1 || rev < minphaserev))
762 800 minphaserev = rev;
763 801 }
764 802
765 803 for (i = 0; i < numphases; ++i) {
766 804 phasesets[i] = PySet_New(NULL);
767 805 if (phasesets[i] == NULL)
768 806 goto release;
769 807 }
770 808
771 809 if (minphaserev == -1)
772 810 minphaserev = len;
773 811 for (rev = minphaserev; rev < len; ++rev) {
774 812 PyObject *pyphase = NULL;
775 813 PyObject *pyrev = NULL;
776 814 int parents[2];
777 815 /*
778 816 * The parent lookup could be skipped for phaseroots, but
779 817 * phase --force would historically not recompute them
780 818 * correctly, leaving descendents with a lower phase around.
781 819 * As such, unconditionally recompute the phase.
782 820 */
783 821 if (index_get_parents(self, rev, parents, (int)len - 1) < 0)
784 822 goto release;
785 823 set_phase_from_parents(phases, parents[0], parents[1], rev);
786 824 switch (phases[rev]) {
787 825 case 0:
788 826 continue;
789 827 case 1:
790 828 pyphase = phasesets[0];
791 829 break;
792 830 case 2:
793 831 pyphase = phasesets[1];
794 832 break;
795 833 case 32:
796 834 pyphase = phasesets[2];
797 835 break;
798 836 case 96:
799 837 pyphase = phasesets[3];
800 838 break;
801 839 default:
802 840 /* this should never happen since the phase number is
803 841 * specified by this function. */
804 842 PyErr_SetString(PyExc_SystemError,
805 843 "bad phase number in internal list");
806 844 goto release;
807 845 }
808 846 pyrev = PyInt_FromLong(rev);
809 847 if (pyrev == NULL)
810 848 goto release;
811 849 if (PySet_Add(pyphase, pyrev) == -1) {
812 850 Py_DECREF(pyrev);
813 851 goto release;
814 852 }
815 853 Py_DECREF(pyrev);
816 854 }
817 855
818 856 phasesetsdict = _dict_new_presized(numphases);
819 857 if (phasesetsdict == NULL)
820 858 goto release;
821 859 for (i = 0; i < numphases; ++i) {
822 860 PyObject *pyphase = PyInt_FromLong(trackedphases[i]);
823 861 if (pyphase == NULL)
824 862 goto release;
825 863 if (PyDict_SetItem(phasesetsdict, pyphase, phasesets[i]) ==
826 864 -1) {
827 865 Py_DECREF(pyphase);
828 866 goto release;
829 867 }
830 868 Py_DECREF(phasesets[i]);
831 869 phasesets[i] = NULL;
832 870 }
833 871
834 872 return Py_BuildValue("nN", len, phasesetsdict);
835 873
836 874 release:
837 875 for (i = 0; i < numphases; ++i)
838 876 Py_XDECREF(phasesets[i]);
839 877 Py_XDECREF(phasesetsdict);
840 878
841 879 free(phases);
842 880 return NULL;
843 881 }
844 882
845 883 static PyObject *index_headrevs(indexObject *self, PyObject *args)
846 884 {
847 885 Py_ssize_t i, j, len;
848 886 char *nothead = NULL;
849 887 PyObject *heads = NULL;
850 888 PyObject *filter = NULL;
851 889 PyObject *filteredrevs = Py_None;
852 890
853 891 if (!PyArg_ParseTuple(args, "|O", &filteredrevs)) {
854 892 return NULL;
855 893 }
856 894
857 895 if (self->headrevs && filteredrevs == self->filteredrevs)
858 896 return list_copy(self->headrevs);
859 897
860 898 Py_DECREF(self->filteredrevs);
861 899 self->filteredrevs = filteredrevs;
862 900 Py_INCREF(filteredrevs);
863 901
864 902 if (filteredrevs != Py_None) {
865 903 filter = PyObject_GetAttrString(filteredrevs, "__contains__");
866 904 if (!filter) {
867 905 PyErr_SetString(
868 906 PyExc_TypeError,
869 907 "filteredrevs has no attribute __contains__");
870 908 goto bail;
871 909 }
872 910 }
873 911
874 912 len = index_length(self);
875 913 heads = PyList_New(0);
876 914 if (heads == NULL)
877 915 goto bail;
878 916 if (len == 0) {
879 917 PyObject *nullid = PyInt_FromLong(-1);
880 918 if (nullid == NULL || PyList_Append(heads, nullid) == -1) {
881 919 Py_XDECREF(nullid);
882 920 goto bail;
883 921 }
884 922 goto done;
885 923 }
886 924
887 925 nothead = calloc(len, 1);
888 926 if (nothead == NULL) {
889 927 PyErr_NoMemory();
890 928 goto bail;
891 929 }
892 930
893 931 for (i = len - 1; i >= 0; i--) {
894 932 int isfiltered;
895 933 int parents[2];
896 934
897 935 /* If nothead[i] == 1, it means we've seen an unfiltered child
898 936 * of this node already, and therefore this node is not
899 937 * filtered. So we can skip the expensive check_filter step.
900 938 */
901 939 if (nothead[i] != 1) {
902 940 isfiltered = check_filter(filter, i);
903 941 if (isfiltered == -1) {
904 942 PyErr_SetString(PyExc_TypeError,
905 943 "unable to check filter");
906 944 goto bail;
907 945 }
908 946
909 947 if (isfiltered) {
910 948 nothead[i] = 1;
911 949 continue;
912 950 }
913 951 }
914 952
915 953 if (index_get_parents(self, i, parents, (int)len - 1) < 0)
916 954 goto bail;
917 955 for (j = 0; j < 2; j++) {
918 956 if (parents[j] >= 0)
919 957 nothead[parents[j]] = 1;
920 958 }
921 959 }
922 960
923 961 for (i = 0; i < len; i++) {
924 962 PyObject *head;
925 963
926 964 if (nothead[i])
927 965 continue;
928 966 head = PyInt_FromSsize_t(i);
929 967 if (head == NULL || PyList_Append(heads, head) == -1) {
930 968 Py_XDECREF(head);
931 969 goto bail;
932 970 }
933 971 }
934 972
935 973 done:
936 974 self->headrevs = heads;
937 975 Py_XDECREF(filter);
938 976 free(nothead);
939 977 return list_copy(self->headrevs);
940 978 bail:
941 979 Py_XDECREF(filter);
942 980 Py_XDECREF(heads);
943 981 free(nothead);
944 982 return NULL;
945 983 }
946 984
947 985 /**
948 986 * Obtain the base revision index entry.
949 987 *
950 988 * Callers must ensure that rev >= 0 or illegal memory access may occur.
951 989 */
952 990 static inline int index_baserev(indexObject *self, int rev)
953 991 {
954 992 const char *data;
955 993 int result;
956 994
957 995 data = index_deref(self, rev);
958 996 if (data == NULL)
959 997 return -2;
960 998 result = getbe32(data + 16);
961 999
962 1000 if (result > rev) {
963 1001 PyErr_Format(
964 1002 PyExc_ValueError,
965 1003 "corrupted revlog, revision base above revision: %d, %d",
966 1004 rev, result);
967 1005 return -2;
968 1006 }
969 1007 if (result < -1) {
970 1008 PyErr_Format(
971 1009 PyExc_ValueError,
972 1010 "corrupted revlog, revision base out of range: %d, %d", rev,
973 1011 result);
974 1012 return -2;
975 1013 }
976 1014 return result;
977 1015 }
978 1016
979 1017 /**
980 1018 * Find if a revision is a snapshot or not
981 1019 *
982 1020 * Only relevant for sparse-revlog case.
983 1021 * Callers must ensure that rev is in a valid range.
984 1022 */
985 1023 static int index_issnapshotrev(indexObject *self, Py_ssize_t rev)
986 1024 {
987 1025 int ps[2];
988 1026 Py_ssize_t base;
989 1027 while (rev >= 0) {
990 1028 base = (Py_ssize_t)index_baserev(self, rev);
991 1029 if (base == rev) {
992 1030 base = -1;
993 1031 }
994 1032 if (base == -2) {
995 1033 assert(PyErr_Occurred());
996 1034 return -1;
997 1035 }
998 1036 if (base == -1) {
999 1037 return 1;
1000 1038 }
1001 1039 if (index_get_parents(self, rev, ps, (int)rev) < 0) {
1002 1040 assert(PyErr_Occurred());
1003 1041 return -1;
1004 1042 };
1005 1043 if (base == ps[0] || base == ps[1]) {
1006 1044 return 0;
1007 1045 }
1008 1046 rev = base;
1009 1047 }
1010 1048 return rev == -1;
1011 1049 }
1012 1050
1013 1051 static PyObject *index_issnapshot(indexObject *self, PyObject *value)
1014 1052 {
1015 1053 long rev;
1016 1054 int issnap;
1017 1055 Py_ssize_t length = index_length(self);
1018 1056
1019 1057 if (!pylong_to_long(value, &rev)) {
1020 1058 return NULL;
1021 1059 }
1022 1060 if (rev < -1 || rev >= length) {
1023 1061 PyErr_Format(PyExc_ValueError, "revlog index out of range: %ld",
1024 1062 rev);
1025 1063 return NULL;
1026 1064 };
1027 1065 issnap = index_issnapshotrev(self, (Py_ssize_t)rev);
1028 1066 if (issnap < 0) {
1029 1067 return NULL;
1030 1068 };
1031 1069 return PyBool_FromLong((long)issnap);
1032 1070 }
1033 1071
1034 1072 static PyObject *index_findsnapshots(indexObject *self, PyObject *args)
1035 1073 {
1036 1074 Py_ssize_t start_rev;
1037 1075 PyObject *cache;
1038 1076 Py_ssize_t base;
1039 1077 Py_ssize_t rev;
1040 1078 PyObject *key = NULL;
1041 1079 PyObject *value = NULL;
1042 1080 const Py_ssize_t length = index_length(self);
1043 1081 if (!PyArg_ParseTuple(args, "O!n", &PyDict_Type, &cache, &start_rev)) {
1044 1082 return NULL;
1045 1083 }
1046 1084 for (rev = start_rev; rev < length; rev++) {
1047 1085 int issnap;
1048 1086 PyObject *allvalues = NULL;
1049 1087 issnap = index_issnapshotrev(self, rev);
1050 1088 if (issnap < 0) {
1051 1089 goto bail;
1052 1090 }
1053 1091 if (issnap == 0) {
1054 1092 continue;
1055 1093 }
1056 1094 base = (Py_ssize_t)index_baserev(self, rev);
1057 1095 if (base == rev) {
1058 1096 base = -1;
1059 1097 }
1060 1098 if (base == -2) {
1061 1099 assert(PyErr_Occurred());
1062 1100 goto bail;
1063 1101 }
1064 1102 key = PyInt_FromSsize_t(base);
1065 1103 allvalues = PyDict_GetItem(cache, key);
1066 1104 if (allvalues == NULL && PyErr_Occurred()) {
1067 1105 goto bail;
1068 1106 }
1069 1107 if (allvalues == NULL) {
1070 1108 int r;
1071 1109 allvalues = PyList_New(0);
1072 1110 if (!allvalues) {
1073 1111 goto bail;
1074 1112 }
1075 1113 r = PyDict_SetItem(cache, key, allvalues);
1076 1114 Py_DECREF(allvalues);
1077 1115 if (r < 0) {
1078 1116 goto bail;
1079 1117 }
1080 1118 }
1081 1119 value = PyInt_FromSsize_t(rev);
1082 1120 if (PyList_Append(allvalues, value)) {
1083 1121 goto bail;
1084 1122 }
1085 1123 Py_CLEAR(key);
1086 1124 Py_CLEAR(value);
1087 1125 }
1088 1126 Py_RETURN_NONE;
1089 1127 bail:
1090 1128 Py_XDECREF(key);
1091 1129 Py_XDECREF(value);
1092 1130 return NULL;
1093 1131 }
1094 1132
1095 1133 static PyObject *index_deltachain(indexObject *self, PyObject *args)
1096 1134 {
1097 1135 int rev, generaldelta;
1098 1136 PyObject *stoparg;
1099 1137 int stoprev, iterrev, baserev = -1;
1100 1138 int stopped;
1101 1139 PyObject *chain = NULL, *result = NULL;
1102 1140 const Py_ssize_t length = index_length(self);
1103 1141
1104 1142 if (!PyArg_ParseTuple(args, "iOi", &rev, &stoparg, &generaldelta)) {
1105 1143 return NULL;
1106 1144 }
1107 1145
1108 1146 if (PyInt_Check(stoparg)) {
1109 1147 stoprev = (int)PyInt_AsLong(stoparg);
1110 1148 if (stoprev == -1 && PyErr_Occurred()) {
1111 1149 return NULL;
1112 1150 }
1113 1151 } else if (stoparg == Py_None) {
1114 1152 stoprev = -2;
1115 1153 } else {
1116 1154 PyErr_SetString(PyExc_ValueError,
1117 1155 "stoprev must be integer or None");
1118 1156 return NULL;
1119 1157 }
1120 1158
1121 1159 if (rev < 0 || rev >= length) {
1122 1160 PyErr_SetString(PyExc_ValueError, "revlog index out of range");
1123 1161 return NULL;
1124 1162 }
1125 1163
1126 1164 chain = PyList_New(0);
1127 1165 if (chain == NULL) {
1128 1166 return NULL;
1129 1167 }
1130 1168
1131 1169 baserev = index_baserev(self, rev);
1132 1170
1133 1171 /* This should never happen. */
1134 1172 if (baserev <= -2) {
1135 1173 /* Error should be set by index_deref() */
1136 1174 assert(PyErr_Occurred());
1137 1175 goto bail;
1138 1176 }
1139 1177
1140 1178 iterrev = rev;
1141 1179
1142 1180 while (iterrev != baserev && iterrev != stoprev) {
1143 1181 PyObject *value = PyInt_FromLong(iterrev);
1144 1182 if (value == NULL) {
1145 1183 goto bail;
1146 1184 }
1147 1185 if (PyList_Append(chain, value)) {
1148 1186 Py_DECREF(value);
1149 1187 goto bail;
1150 1188 }
1151 1189 Py_DECREF(value);
1152 1190
1153 1191 if (generaldelta) {
1154 1192 iterrev = baserev;
1155 1193 } else {
1156 1194 iterrev--;
1157 1195 }
1158 1196
1159 1197 if (iterrev < 0) {
1160 1198 break;
1161 1199 }
1162 1200
1163 1201 if (iterrev >= length) {
1164 1202 PyErr_SetString(PyExc_IndexError,
1165 1203 "revision outside index");
1166 1204 return NULL;
1167 1205 }
1168 1206
1169 1207 baserev = index_baserev(self, iterrev);
1170 1208
1171 1209 /* This should never happen. */
1172 1210 if (baserev <= -2) {
1173 1211 /* Error should be set by index_deref() */
1174 1212 assert(PyErr_Occurred());
1175 1213 goto bail;
1176 1214 }
1177 1215 }
1178 1216
1179 1217 if (iterrev == stoprev) {
1180 1218 stopped = 1;
1181 1219 } else {
1182 1220 PyObject *value = PyInt_FromLong(iterrev);
1183 1221 if (value == NULL) {
1184 1222 goto bail;
1185 1223 }
1186 1224 if (PyList_Append(chain, value)) {
1187 1225 Py_DECREF(value);
1188 1226 goto bail;
1189 1227 }
1190 1228 Py_DECREF(value);
1191 1229
1192 1230 stopped = 0;
1193 1231 }
1194 1232
1195 1233 if (PyList_Reverse(chain)) {
1196 1234 goto bail;
1197 1235 }
1198 1236
1199 1237 result = Py_BuildValue("OO", chain, stopped ? Py_True : Py_False);
1200 1238 Py_DECREF(chain);
1201 1239 return result;
1202 1240
1203 1241 bail:
1204 1242 Py_DECREF(chain);
1205 1243 return NULL;
1206 1244 }
1207 1245
1208 1246 static inline int64_t
1209 1247 index_segment_span(indexObject *self, Py_ssize_t start_rev, Py_ssize_t end_rev)
1210 1248 {
1211 1249 int64_t start_offset;
1212 1250 int64_t end_offset;
1213 1251 int end_size;
1214 1252 start_offset = index_get_start(self, start_rev);
1215 1253 if (start_offset < 0) {
1216 1254 return -1;
1217 1255 }
1218 1256 end_offset = index_get_start(self, end_rev);
1219 1257 if (end_offset < 0) {
1220 1258 return -1;
1221 1259 }
1222 1260 end_size = index_get_length(self, end_rev);
1223 1261 if (end_size < 0) {
1224 1262 return -1;
1225 1263 }
1226 1264 if (end_offset < start_offset) {
1227 1265 PyErr_Format(PyExc_ValueError,
1228 1266 "corrupted revlog index: inconsistent offset "
1229 1267 "between revisions (%zd) and (%zd)",
1230 1268 start_rev, end_rev);
1231 1269 return -1;
1232 1270 }
1233 1271 return (end_offset - start_offset) + (int64_t)end_size;
1234 1272 }
1235 1273
1236 1274 /* returns endidx so that revs[startidx:endidx] has no empty trailing revs */
1237 1275 static Py_ssize_t trim_endidx(indexObject *self, const Py_ssize_t *revs,
1238 1276 Py_ssize_t startidx, Py_ssize_t endidx)
1239 1277 {
1240 1278 int length;
1241 1279 while (endidx > 1 && endidx > startidx) {
1242 1280 length = index_get_length(self, revs[endidx - 1]);
1243 1281 if (length < 0) {
1244 1282 return -1;
1245 1283 }
1246 1284 if (length != 0) {
1247 1285 break;
1248 1286 }
1249 1287 endidx -= 1;
1250 1288 }
1251 1289 return endidx;
1252 1290 }
1253 1291
1254 1292 struct Gap {
1255 1293 int64_t size;
1256 1294 Py_ssize_t idx;
1257 1295 };
1258 1296
1259 1297 static int gap_compare(const void *left, const void *right)
1260 1298 {
1261 1299 const struct Gap *l_left = ((const struct Gap *)left);
1262 1300 const struct Gap *l_right = ((const struct Gap *)right);
1263 1301 if (l_left->size < l_right->size) {
1264 1302 return -1;
1265 1303 } else if (l_left->size > l_right->size) {
1266 1304 return 1;
1267 1305 }
1268 1306 return 0;
1269 1307 }
1270 1308 static int Py_ssize_t_compare(const void *left, const void *right)
1271 1309 {
1272 1310 const Py_ssize_t l_left = *(const Py_ssize_t *)left;
1273 1311 const Py_ssize_t l_right = *(const Py_ssize_t *)right;
1274 1312 if (l_left < l_right) {
1275 1313 return -1;
1276 1314 } else if (l_left > l_right) {
1277 1315 return 1;
1278 1316 }
1279 1317 return 0;
1280 1318 }
1281 1319
1282 1320 static PyObject *index_slicechunktodensity(indexObject *self, PyObject *args)
1283 1321 {
1284 1322 /* method arguments */
1285 1323 PyObject *list_revs = NULL; /* revisions in the chain */
1286 1324 double targetdensity = 0; /* min density to achieve */
1287 1325 Py_ssize_t mingapsize = 0; /* threshold to ignore gaps */
1288 1326
1289 1327 /* other core variables */
1290 1328 Py_ssize_t idxlen = index_length(self);
1291 1329 Py_ssize_t i; /* used for various iteration */
1292 1330 PyObject *result = NULL; /* the final return of the function */
1293 1331
1294 1332 /* generic information about the delta chain being slice */
1295 1333 Py_ssize_t num_revs = 0; /* size of the full delta chain */
1296 1334 Py_ssize_t *revs = NULL; /* native array of revision in the chain */
1297 1335 int64_t chainpayload = 0; /* sum of all delta in the chain */
1298 1336 int64_t deltachainspan = 0; /* distance from first byte to last byte */
1299 1337
1300 1338 /* variable used for slicing the delta chain */
1301 1339 int64_t readdata = 0; /* amount of data currently planned to be read */
1302 1340 double density = 0; /* ration of payload data compared to read ones */
1303 1341 int64_t previous_end;
1304 1342 struct Gap *gaps = NULL; /* array of notable gap in the chain */
1305 1343 Py_ssize_t num_gaps =
1306 1344 0; /* total number of notable gap recorded so far */
1307 1345 Py_ssize_t *selected_indices = NULL; /* indices of gap skipped over */
1308 1346 Py_ssize_t num_selected = 0; /* number of gaps skipped */
1309 1347 PyObject *chunk = NULL; /* individual slice */
1310 1348 PyObject *allchunks = NULL; /* all slices */
1311 1349 Py_ssize_t previdx;
1312 1350
1313 1351 /* parsing argument */
1314 1352 if (!PyArg_ParseTuple(args, "O!dn", &PyList_Type, &list_revs,
1315 1353 &targetdensity, &mingapsize)) {
1316 1354 goto bail;
1317 1355 }
1318 1356
1319 1357 /* If the delta chain contains a single element, we do not need slicing
1320 1358 */
1321 1359 num_revs = PyList_GET_SIZE(list_revs);
1322 1360 if (num_revs <= 1) {
1323 1361 result = PyTuple_Pack(1, list_revs);
1324 1362 goto done;
1325 1363 }
1326 1364
1327 1365 /* Turn the python list into a native integer array (for efficiency) */
1328 1366 revs = (Py_ssize_t *)calloc(num_revs, sizeof(Py_ssize_t));
1329 1367 if (revs == NULL) {
1330 1368 PyErr_NoMemory();
1331 1369 goto bail;
1332 1370 }
1333 1371 for (i = 0; i < num_revs; i++) {
1334 1372 Py_ssize_t revnum = PyInt_AsLong(PyList_GET_ITEM(list_revs, i));
1335 1373 if (revnum == -1 && PyErr_Occurred()) {
1336 1374 goto bail;
1337 1375 }
1338 1376 if (revnum < nullrev || revnum >= idxlen) {
1339 1377 PyErr_Format(PyExc_IndexError,
1340 1378 "index out of range: %zd", revnum);
1341 1379 goto bail;
1342 1380 }
1343 1381 revs[i] = revnum;
1344 1382 }
1345 1383
1346 1384 /* Compute and check various property of the unsliced delta chain */
1347 1385 deltachainspan = index_segment_span(self, revs[0], revs[num_revs - 1]);
1348 1386 if (deltachainspan < 0) {
1349 1387 goto bail;
1350 1388 }
1351 1389
1352 1390 if (deltachainspan <= mingapsize) {
1353 1391 result = PyTuple_Pack(1, list_revs);
1354 1392 goto done;
1355 1393 }
1356 1394 chainpayload = 0;
1357 1395 for (i = 0; i < num_revs; i++) {
1358 1396 int tmp = index_get_length(self, revs[i]);
1359 1397 if (tmp < 0) {
1360 1398 goto bail;
1361 1399 }
1362 1400 chainpayload += tmp;
1363 1401 }
1364 1402
1365 1403 readdata = deltachainspan;
1366 1404 density = 1.0;
1367 1405
1368 1406 if (0 < deltachainspan) {
1369 1407 density = (double)chainpayload / (double)deltachainspan;
1370 1408 }
1371 1409
1372 1410 if (density >= targetdensity) {
1373 1411 result = PyTuple_Pack(1, list_revs);
1374 1412 goto done;
1375 1413 }
1376 1414
1377 1415 /* if chain is too sparse, look for relevant gaps */
1378 1416 gaps = (struct Gap *)calloc(num_revs, sizeof(struct Gap));
1379 1417 if (gaps == NULL) {
1380 1418 PyErr_NoMemory();
1381 1419 goto bail;
1382 1420 }
1383 1421
1384 1422 previous_end = -1;
1385 1423 for (i = 0; i < num_revs; i++) {
1386 1424 int64_t revstart;
1387 1425 int revsize;
1388 1426 revstart = index_get_start(self, revs[i]);
1389 1427 if (revstart < 0) {
1390 1428 goto bail;
1391 1429 };
1392 1430 revsize = index_get_length(self, revs[i]);
1393 1431 if (revsize < 0) {
1394 1432 goto bail;
1395 1433 };
1396 1434 if (revsize == 0) {
1397 1435 continue;
1398 1436 }
1399 1437 if (previous_end >= 0) {
1400 1438 int64_t gapsize = revstart - previous_end;
1401 1439 if (gapsize > mingapsize) {
1402 1440 gaps[num_gaps].size = gapsize;
1403 1441 gaps[num_gaps].idx = i;
1404 1442 num_gaps += 1;
1405 1443 }
1406 1444 }
1407 1445 previous_end = revstart + revsize;
1408 1446 }
1409 1447 if (num_gaps == 0) {
1410 1448 result = PyTuple_Pack(1, list_revs);
1411 1449 goto done;
1412 1450 }
1413 1451 qsort(gaps, num_gaps, sizeof(struct Gap), &gap_compare);
1414 1452
1415 1453 /* Slice the largest gap first, they improve the density the most */
1416 1454 selected_indices =
1417 1455 (Py_ssize_t *)malloc((num_gaps + 1) * sizeof(Py_ssize_t));
1418 1456 if (selected_indices == NULL) {
1419 1457 PyErr_NoMemory();
1420 1458 goto bail;
1421 1459 }
1422 1460
1423 1461 for (i = num_gaps - 1; i >= 0; i--) {
1424 1462 selected_indices[num_selected] = gaps[i].idx;
1425 1463 readdata -= gaps[i].size;
1426 1464 num_selected += 1;
1427 1465 if (readdata <= 0) {
1428 1466 density = 1.0;
1429 1467 } else {
1430 1468 density = (double)chainpayload / (double)readdata;
1431 1469 }
1432 1470 if (density >= targetdensity) {
1433 1471 break;
1434 1472 }
1435 1473 }
1436 1474 qsort(selected_indices, num_selected, sizeof(Py_ssize_t),
1437 1475 &Py_ssize_t_compare);
1438 1476
1439 1477 /* create the resulting slice */
1440 1478 allchunks = PyList_New(0);
1441 1479 if (allchunks == NULL) {
1442 1480 goto bail;
1443 1481 }
1444 1482 previdx = 0;
1445 1483 selected_indices[num_selected] = num_revs;
1446 1484 for (i = 0; i <= num_selected; i++) {
1447 1485 Py_ssize_t idx = selected_indices[i];
1448 1486 Py_ssize_t endidx = trim_endidx(self, revs, previdx, idx);
1449 1487 if (endidx < 0) {
1450 1488 goto bail;
1451 1489 }
1452 1490 if (previdx < endidx) {
1453 1491 chunk = PyList_GetSlice(list_revs, previdx, endidx);
1454 1492 if (chunk == NULL) {
1455 1493 goto bail;
1456 1494 }
1457 1495 if (PyList_Append(allchunks, chunk) == -1) {
1458 1496 goto bail;
1459 1497 }
1460 1498 Py_DECREF(chunk);
1461 1499 chunk = NULL;
1462 1500 }
1463 1501 previdx = idx;
1464 1502 }
1465 1503 result = allchunks;
1466 1504 goto done;
1467 1505
1468 1506 bail:
1469 1507 Py_XDECREF(allchunks);
1470 1508 Py_XDECREF(chunk);
1471 1509 done:
1472 1510 free(revs);
1473 1511 free(gaps);
1474 1512 free(selected_indices);
1475 1513 return result;
1476 1514 }
1477 1515
1478 1516 static inline int nt_level(const char *node, Py_ssize_t level)
1479 1517 {
1480 1518 int v = node[level >> 1];
1481 1519 if (!(level & 1))
1482 1520 v >>= 4;
1483 1521 return v & 0xf;
1484 1522 }
1485 1523
1486 1524 /*
1487 1525 * Return values:
1488 1526 *
1489 1527 * -4: match is ambiguous (multiple candidates)
1490 1528 * -2: not found
1491 1529 * rest: valid rev
1492 1530 */
1493 1531 static int nt_find(nodetree *self, const char *node, Py_ssize_t nodelen,
1494 1532 int hex)
1495 1533 {
1496 1534 int (*getnybble)(const char *, Py_ssize_t) = hex ? hexdigit : nt_level;
1497 1535 int level, maxlevel, off;
1498 1536
1499 1537 /* If the input is binary, do a fast check for the nullid first. */
1500 1538 if (!hex && nodelen == self->nodelen && node[0] == '\0' &&
1501 1539 node[1] == '\0' && memcmp(node, nullid, self->nodelen) == 0)
1502 1540 return -1;
1503 1541
1504 1542 if (hex)
1505 1543 maxlevel = nodelen;
1506 1544 else
1507 1545 maxlevel = 2 * nodelen;
1508 1546 if (maxlevel > 2 * self->nodelen)
1509 1547 maxlevel = 2 * self->nodelen;
1510 1548
1511 1549 for (level = off = 0; level < maxlevel; level++) {
1512 1550 int k = getnybble(node, level);
1513 1551 nodetreenode *n = &self->nodes[off];
1514 1552 int v = n->children[k];
1515 1553
1516 1554 if (v < 0) {
1517 1555 const char *n;
1518 1556 Py_ssize_t i;
1519 1557
1520 1558 v = -(v + 2);
1521 1559 n = index_node(self->index, v);
1522 1560 if (n == NULL)
1523 1561 return -2;
1524 1562 for (i = level; i < maxlevel; i++)
1525 1563 if (getnybble(node, i) != nt_level(n, i))
1526 1564 return -2;
1527 1565 return v;
1528 1566 }
1529 1567 if (v == 0)
1530 1568 return -2;
1531 1569 off = v;
1532 1570 }
1533 1571 /* multiple matches against an ambiguous prefix */
1534 1572 return -4;
1535 1573 }
1536 1574
1537 1575 static int nt_new(nodetree *self)
1538 1576 {
1539 1577 if (self->length == self->capacity) {
1540 1578 size_t newcapacity;
1541 1579 nodetreenode *newnodes;
1542 1580 newcapacity = self->capacity * 2;
1543 1581 if (newcapacity >= SIZE_MAX / sizeof(nodetreenode)) {
1544 1582 PyErr_SetString(PyExc_MemoryError,
1545 1583 "overflow in nt_new");
1546 1584 return -1;
1547 1585 }
1548 1586 newnodes =
1549 1587 realloc(self->nodes, newcapacity * sizeof(nodetreenode));
1550 1588 if (newnodes == NULL) {
1551 1589 PyErr_SetString(PyExc_MemoryError, "out of memory");
1552 1590 return -1;
1553 1591 }
1554 1592 self->capacity = newcapacity;
1555 1593 self->nodes = newnodes;
1556 1594 memset(&self->nodes[self->length], 0,
1557 1595 sizeof(nodetreenode) * (self->capacity - self->length));
1558 1596 }
1559 1597 return self->length++;
1560 1598 }
1561 1599
1562 1600 static int nt_insert(nodetree *self, const char *node, int rev)
1563 1601 {
1564 1602 int level = 0;
1565 1603 int off = 0;
1566 1604
1567 1605 while (level < 2 * self->nodelen) {
1568 1606 int k = nt_level(node, level);
1569 1607 nodetreenode *n;
1570 1608 int v;
1571 1609
1572 1610 n = &self->nodes[off];
1573 1611 v = n->children[k];
1574 1612
1575 1613 if (v == 0) {
1576 1614 n->children[k] = -rev - 2;
1577 1615 return 0;
1578 1616 }
1579 1617 if (v < 0) {
1580 1618 const char *oldnode =
1581 1619 index_node_existing(self->index, -(v + 2));
1582 1620 int noff;
1583 1621
1584 1622 if (oldnode == NULL)
1585 1623 return -1;
1586 1624 if (!memcmp(oldnode, node, self->nodelen)) {
1587 1625 n->children[k] = -rev - 2;
1588 1626 return 0;
1589 1627 }
1590 1628 noff = nt_new(self);
1591 1629 if (noff == -1)
1592 1630 return -1;
1593 1631 /* self->nodes may have been changed by realloc */
1594 1632 self->nodes[off].children[k] = noff;
1595 1633 off = noff;
1596 1634 n = &self->nodes[off];
1597 1635 n->children[nt_level(oldnode, ++level)] = v;
1598 1636 if (level > self->depth)
1599 1637 self->depth = level;
1600 1638 self->splits += 1;
1601 1639 } else {
1602 1640 level += 1;
1603 1641 off = v;
1604 1642 }
1605 1643 }
1606 1644
1607 1645 return -1;
1608 1646 }
1609 1647
1610 1648 static PyObject *ntobj_insert(nodetreeObject *self, PyObject *args)
1611 1649 {
1612 1650 Py_ssize_t rev;
1613 1651 const char *node;
1614 1652 Py_ssize_t length;
1615 1653 if (!PyArg_ParseTuple(args, "n", &rev))
1616 1654 return NULL;
1617 1655 length = index_length(self->nt.index);
1618 1656 if (rev < 0 || rev >= length) {
1619 1657 PyErr_SetString(PyExc_ValueError, "revlog index out of range");
1620 1658 return NULL;
1621 1659 }
1622 1660 node = index_node_existing(self->nt.index, rev);
1623 1661 if (nt_insert(&self->nt, node, (int)rev) == -1)
1624 1662 return NULL;
1625 1663 Py_RETURN_NONE;
1626 1664 }
1627 1665
1628 1666 static int nt_delete_node(nodetree *self, const char *node)
1629 1667 {
1630 1668 /* rev==-2 happens to get encoded as 0, which is interpreted as not set
1631 1669 */
1632 1670 return nt_insert(self, node, -2);
1633 1671 }
1634 1672
1635 1673 static int nt_init(nodetree *self, indexObject *index, unsigned capacity)
1636 1674 {
1637 1675 /* Initialize before overflow-checking to avoid nt_dealloc() crash. */
1638 1676 self->nodes = NULL;
1639 1677
1640 1678 self->index = index;
1641 1679 /* The input capacity is in terms of revisions, while the field is in
1642 1680 * terms of nodetree nodes. */
1643 1681 self->capacity = (capacity < 4 ? 4 : capacity / 2);
1644 1682 self->nodelen = index->nodelen;
1645 1683 self->depth = 0;
1646 1684 self->splits = 0;
1647 1685 if (self->capacity > SIZE_MAX / sizeof(nodetreenode)) {
1648 1686 PyErr_SetString(PyExc_ValueError, "overflow in init_nt");
1649 1687 return -1;
1650 1688 }
1651 1689 self->nodes = calloc(self->capacity, sizeof(nodetreenode));
1652 1690 if (self->nodes == NULL) {
1653 1691 PyErr_NoMemory();
1654 1692 return -1;
1655 1693 }
1656 1694 self->length = 1;
1657 1695 return 0;
1658 1696 }
1659 1697
1660 1698 static int ntobj_init(nodetreeObject *self, PyObject *args)
1661 1699 {
1662 1700 PyObject *index;
1663 1701 unsigned capacity;
1664 1702 if (!PyArg_ParseTuple(args, "O!I", &HgRevlogIndex_Type, &index,
1665 1703 &capacity))
1666 1704 return -1;
1667 1705 Py_INCREF(index);
1668 1706 return nt_init(&self->nt, (indexObject *)index, capacity);
1669 1707 }
1670 1708
1671 1709 static int nt_partialmatch(nodetree *self, const char *node, Py_ssize_t nodelen)
1672 1710 {
1673 1711 return nt_find(self, node, nodelen, 1);
1674 1712 }
1675 1713
1676 1714 /*
1677 1715 * Find the length of the shortest unique prefix of node.
1678 1716 *
1679 1717 * Return values:
1680 1718 *
1681 1719 * -3: error (exception set)
1682 1720 * -2: not found (no exception set)
1683 1721 * rest: length of shortest prefix
1684 1722 */
1685 1723 static int nt_shortest(nodetree *self, const char *node)
1686 1724 {
1687 1725 int level, off;
1688 1726
1689 1727 for (level = off = 0; level < 2 * self->nodelen; level++) {
1690 1728 int k, v;
1691 1729 nodetreenode *n = &self->nodes[off];
1692 1730 k = nt_level(node, level);
1693 1731 v = n->children[k];
1694 1732 if (v < 0) {
1695 1733 const char *n;
1696 1734 v = -(v + 2);
1697 1735 n = index_node_existing(self->index, v);
1698 1736 if (n == NULL)
1699 1737 return -3;
1700 1738 if (memcmp(node, n, self->nodelen) != 0)
1701 1739 /*
1702 1740 * Found a unique prefix, but it wasn't for the
1703 1741 * requested node (i.e the requested node does
1704 1742 * not exist).
1705 1743 */
1706 1744 return -2;
1707 1745 return level + 1;
1708 1746 }
1709 1747 if (v == 0)
1710 1748 return -2;
1711 1749 off = v;
1712 1750 }
1713 1751 /*
1714 1752 * The node was still not unique after 40 hex digits, so this won't
1715 1753 * happen. Also, if we get here, then there's a programming error in
1716 1754 * this file that made us insert a node longer than 40 hex digits.
1717 1755 */
1718 1756 PyErr_SetString(PyExc_Exception, "broken node tree");
1719 1757 return -3;
1720 1758 }
1721 1759
1722 1760 static PyObject *ntobj_shortest(nodetreeObject *self, PyObject *args)
1723 1761 {
1724 1762 PyObject *val;
1725 1763 char *node;
1726 1764 int length;
1727 1765
1728 1766 if (!PyArg_ParseTuple(args, "O", &val))
1729 1767 return NULL;
1730 1768 if (node_check(self->nt.nodelen, val, &node) == -1)
1731 1769 return NULL;
1732 1770
1733 1771 length = nt_shortest(&self->nt, node);
1734 1772 if (length == -3)
1735 1773 return NULL;
1736 1774 if (length == -2) {
1737 1775 raise_revlog_error();
1738 1776 return NULL;
1739 1777 }
1740 1778 return PyInt_FromLong(length);
1741 1779 }
1742 1780
1743 1781 static void nt_dealloc(nodetree *self)
1744 1782 {
1745 1783 free(self->nodes);
1746 1784 self->nodes = NULL;
1747 1785 }
1748 1786
1749 1787 static void ntobj_dealloc(nodetreeObject *self)
1750 1788 {
1751 1789 Py_XDECREF(self->nt.index);
1752 1790 nt_dealloc(&self->nt);
1753 1791 PyObject_Del(self);
1754 1792 }
1755 1793
1756 1794 static PyMethodDef ntobj_methods[] = {
1757 1795 {"insert", (PyCFunction)ntobj_insert, METH_VARARGS,
1758 1796 "insert an index entry"},
1759 1797 {"shortest", (PyCFunction)ntobj_shortest, METH_VARARGS,
1760 1798 "find length of shortest hex nodeid of a binary ID"},
1761 1799 {NULL} /* Sentinel */
1762 1800 };
1763 1801
1764 1802 static PyTypeObject nodetreeType = {
1765 1803 PyVarObject_HEAD_INIT(NULL, 0) /* header */
1766 1804 "parsers.nodetree", /* tp_name */
1767 1805 sizeof(nodetreeObject), /* tp_basicsize */
1768 1806 0, /* tp_itemsize */
1769 1807 (destructor)ntobj_dealloc, /* tp_dealloc */
1770 1808 0, /* tp_print */
1771 1809 0, /* tp_getattr */
1772 1810 0, /* tp_setattr */
1773 1811 0, /* tp_compare */
1774 1812 0, /* tp_repr */
1775 1813 0, /* tp_as_number */
1776 1814 0, /* tp_as_sequence */
1777 1815 0, /* tp_as_mapping */
1778 1816 0, /* tp_hash */
1779 1817 0, /* tp_call */
1780 1818 0, /* tp_str */
1781 1819 0, /* tp_getattro */
1782 1820 0, /* tp_setattro */
1783 1821 0, /* tp_as_buffer */
1784 1822 Py_TPFLAGS_DEFAULT, /* tp_flags */
1785 1823 "nodetree", /* tp_doc */
1786 1824 0, /* tp_traverse */
1787 1825 0, /* tp_clear */
1788 1826 0, /* tp_richcompare */
1789 1827 0, /* tp_weaklistoffset */
1790 1828 0, /* tp_iter */
1791 1829 0, /* tp_iternext */
1792 1830 ntobj_methods, /* tp_methods */
1793 1831 0, /* tp_members */
1794 1832 0, /* tp_getset */
1795 1833 0, /* tp_base */
1796 1834 0, /* tp_dict */
1797 1835 0, /* tp_descr_get */
1798 1836 0, /* tp_descr_set */
1799 1837 0, /* tp_dictoffset */
1800 1838 (initproc)ntobj_init, /* tp_init */
1801 1839 0, /* tp_alloc */
1802 1840 };
1803 1841
1804 1842 static int index_init_nt(indexObject *self)
1805 1843 {
1806 1844 if (!self->ntinitialized) {
1807 1845 if (nt_init(&self->nt, self, (int)self->length) == -1) {
1808 1846 nt_dealloc(&self->nt);
1809 1847 return -1;
1810 1848 }
1811 1849 if (nt_insert(&self->nt, nullid, -1) == -1) {
1812 1850 nt_dealloc(&self->nt);
1813 1851 return -1;
1814 1852 }
1815 1853 self->ntinitialized = 1;
1816 1854 self->ntrev = (int)index_length(self);
1817 1855 self->ntlookups = 1;
1818 1856 self->ntmisses = 0;
1819 1857 }
1820 1858 return 0;
1821 1859 }
1822 1860
1823 1861 /*
1824 1862 * Return values:
1825 1863 *
1826 1864 * -3: error (exception set)
1827 1865 * -2: not found (no exception set)
1828 1866 * rest: valid rev
1829 1867 */
1830 1868 static int index_find_node(indexObject *self, const char *node)
1831 1869 {
1832 1870 int rev;
1833 1871
1834 1872 if (index_init_nt(self) == -1)
1835 1873 return -3;
1836 1874
1837 1875 self->ntlookups++;
1838 1876 rev = nt_find(&self->nt, node, self->nodelen, 0);
1839 1877 if (rev >= -1)
1840 1878 return rev;
1841 1879
1842 1880 /*
1843 1881 * For the first handful of lookups, we scan the entire index,
1844 1882 * and cache only the matching nodes. This optimizes for cases
1845 1883 * like "hg tip", where only a few nodes are accessed.
1846 1884 *
1847 1885 * After that, we cache every node we visit, using a single
1848 1886 * scan amortized over multiple lookups. This gives the best
1849 1887 * bulk performance, e.g. for "hg log".
1850 1888 */
1851 1889 if (self->ntmisses++ < 4) {
1852 1890 for (rev = self->ntrev - 1; rev >= 0; rev--) {
1853 1891 const char *n = index_node_existing(self, rev);
1854 1892 if (n == NULL)
1855 1893 return -3;
1856 1894 if (memcmp(node, n, self->nodelen) == 0) {
1857 1895 if (nt_insert(&self->nt, n, rev) == -1)
1858 1896 return -3;
1859 1897 break;
1860 1898 }
1861 1899 }
1862 1900 } else {
1863 1901 for (rev = self->ntrev - 1; rev >= 0; rev--) {
1864 1902 const char *n = index_node_existing(self, rev);
1865 1903 if (n == NULL)
1866 1904 return -3;
1867 1905 if (nt_insert(&self->nt, n, rev) == -1) {
1868 1906 self->ntrev = rev + 1;
1869 1907 return -3;
1870 1908 }
1871 1909 if (memcmp(node, n, self->nodelen) == 0) {
1872 1910 break;
1873 1911 }
1874 1912 }
1875 1913 self->ntrev = rev;
1876 1914 }
1877 1915
1878 1916 if (rev >= 0)
1879 1917 return rev;
1880 1918 return -2;
1881 1919 }
1882 1920
1883 1921 static PyObject *index_getitem(indexObject *self, PyObject *value)
1884 1922 {
1885 1923 char *node;
1886 1924 int rev;
1887 1925
1888 1926 if (PyInt_Check(value)) {
1889 1927 long idx;
1890 1928 if (!pylong_to_long(value, &idx)) {
1891 1929 return NULL;
1892 1930 }
1893 1931 return index_get(self, idx);
1894 1932 }
1895 1933
1896 1934 if (node_check(self->nodelen, value, &node) == -1)
1897 1935 return NULL;
1898 1936 rev = index_find_node(self, node);
1899 1937 if (rev >= -1)
1900 1938 return PyInt_FromLong(rev);
1901 1939 if (rev == -2)
1902 1940 raise_revlog_error();
1903 1941 return NULL;
1904 1942 }
1905 1943
1906 1944 /*
1907 1945 * Fully populate the radix tree.
1908 1946 */
1909 1947 static int index_populate_nt(indexObject *self)
1910 1948 {
1911 1949 int rev;
1912 1950 if (self->ntrev > 0) {
1913 1951 for (rev = self->ntrev - 1; rev >= 0; rev--) {
1914 1952 const char *n = index_node_existing(self, rev);
1915 1953 if (n == NULL)
1916 1954 return -1;
1917 1955 if (nt_insert(&self->nt, n, rev) == -1)
1918 1956 return -1;
1919 1957 }
1920 1958 self->ntrev = -1;
1921 1959 }
1922 1960 return 0;
1923 1961 }
1924 1962
1925 1963 static PyObject *index_partialmatch(indexObject *self, PyObject *args)
1926 1964 {
1927 1965 const char *fullnode;
1928 1966 Py_ssize_t nodelen;
1929 1967 char *node;
1930 1968 int rev, i;
1931 1969
1932 1970 if (!PyArg_ParseTuple(args, PY23("s#", "y#"), &node, &nodelen))
1933 1971 return NULL;
1934 1972
1935 1973 if (nodelen < 1) {
1936 1974 PyErr_SetString(PyExc_ValueError, "key too short");
1937 1975 return NULL;
1938 1976 }
1939 1977
1940 1978 if (nodelen > 2 * self->nodelen) {
1941 1979 PyErr_SetString(PyExc_ValueError, "key too long");
1942 1980 return NULL;
1943 1981 }
1944 1982
1945 1983 for (i = 0; i < nodelen; i++)
1946 1984 hexdigit(node, i);
1947 1985 if (PyErr_Occurred()) {
1948 1986 /* input contains non-hex characters */
1949 1987 PyErr_Clear();
1950 1988 Py_RETURN_NONE;
1951 1989 }
1952 1990
1953 1991 if (index_init_nt(self) == -1)
1954 1992 return NULL;
1955 1993 if (index_populate_nt(self) == -1)
1956 1994 return NULL;
1957 1995 rev = nt_partialmatch(&self->nt, node, nodelen);
1958 1996
1959 1997 switch (rev) {
1960 1998 case -4:
1961 1999 raise_revlog_error();
1962 2000 return NULL;
1963 2001 case -2:
1964 2002 Py_RETURN_NONE;
1965 2003 case -1:
1966 2004 return PyBytes_FromStringAndSize(nullid, self->nodelen);
1967 2005 }
1968 2006
1969 2007 fullnode = index_node_existing(self, rev);
1970 2008 if (fullnode == NULL) {
1971 2009 return NULL;
1972 2010 }
1973 2011 return PyBytes_FromStringAndSize(fullnode, self->nodelen);
1974 2012 }
1975 2013
1976 2014 static PyObject *index_shortest(indexObject *self, PyObject *args)
1977 2015 {
1978 2016 PyObject *val;
1979 2017 char *node;
1980 2018 int length;
1981 2019
1982 2020 if (!PyArg_ParseTuple(args, "O", &val))
1983 2021 return NULL;
1984 2022 if (node_check(self->nodelen, val, &node) == -1)
1985 2023 return NULL;
1986 2024
1987 2025 self->ntlookups++;
1988 2026 if (index_init_nt(self) == -1)
1989 2027 return NULL;
1990 2028 if (index_populate_nt(self) == -1)
1991 2029 return NULL;
1992 2030 length = nt_shortest(&self->nt, node);
1993 2031 if (length == -3)
1994 2032 return NULL;
1995 2033 if (length == -2) {
1996 2034 raise_revlog_error();
1997 2035 return NULL;
1998 2036 }
1999 2037 return PyInt_FromLong(length);
2000 2038 }
2001 2039
2002 2040 static PyObject *index_m_get(indexObject *self, PyObject *args)
2003 2041 {
2004 2042 PyObject *val;
2005 2043 char *node;
2006 2044 int rev;
2007 2045
2008 2046 if (!PyArg_ParseTuple(args, "O", &val))
2009 2047 return NULL;
2010 2048 if (node_check(self->nodelen, val, &node) == -1)
2011 2049 return NULL;
2012 2050 rev = index_find_node(self, node);
2013 2051 if (rev == -3)
2014 2052 return NULL;
2015 2053 if (rev == -2)
2016 2054 Py_RETURN_NONE;
2017 2055 return PyInt_FromLong(rev);
2018 2056 }
2019 2057
2020 2058 static int index_contains(indexObject *self, PyObject *value)
2021 2059 {
2022 2060 char *node;
2023 2061
2024 2062 if (PyInt_Check(value)) {
2025 2063 long rev;
2026 2064 if (!pylong_to_long(value, &rev)) {
2027 2065 return -1;
2028 2066 }
2029 2067 return rev >= -1 && rev < index_length(self);
2030 2068 }
2031 2069
2032 2070 if (node_check(self->nodelen, value, &node) == -1)
2033 2071 return -1;
2034 2072
2035 2073 switch (index_find_node(self, node)) {
2036 2074 case -3:
2037 2075 return -1;
2038 2076 case -2:
2039 2077 return 0;
2040 2078 default:
2041 2079 return 1;
2042 2080 }
2043 2081 }
2044 2082
2045 2083 static PyObject *index_m_has_node(indexObject *self, PyObject *args)
2046 2084 {
2047 2085 int ret = index_contains(self, args);
2048 2086 if (ret < 0)
2049 2087 return NULL;
2050 2088 return PyBool_FromLong((long)ret);
2051 2089 }
2052 2090
2053 2091 static PyObject *index_m_rev(indexObject *self, PyObject *val)
2054 2092 {
2055 2093 char *node;
2056 2094 int rev;
2057 2095
2058 2096 if (node_check(self->nodelen, val, &node) == -1)
2059 2097 return NULL;
2060 2098 rev = index_find_node(self, node);
2061 2099 if (rev >= -1)
2062 2100 return PyInt_FromLong(rev);
2063 2101 if (rev == -2)
2064 2102 raise_revlog_error();
2065 2103 return NULL;
2066 2104 }
2067 2105
2068 2106 typedef uint64_t bitmask;
2069 2107
2070 2108 /*
2071 2109 * Given a disjoint set of revs, return all candidates for the
2072 2110 * greatest common ancestor. In revset notation, this is the set
2073 2111 * "heads(::a and ::b and ...)"
2074 2112 */
2075 2113 static PyObject *find_gca_candidates(indexObject *self, const int *revs,
2076 2114 int revcount)
2077 2115 {
2078 2116 const bitmask allseen = (1ull << revcount) - 1;
2079 2117 const bitmask poison = 1ull << revcount;
2080 2118 PyObject *gca = PyList_New(0);
2081 2119 int i, v, interesting;
2082 2120 int maxrev = -1;
2083 2121 bitmask sp;
2084 2122 bitmask *seen;
2085 2123
2086 2124 if (gca == NULL)
2087 2125 return PyErr_NoMemory();
2088 2126
2089 2127 for (i = 0; i < revcount; i++) {
2090 2128 if (revs[i] > maxrev)
2091 2129 maxrev = revs[i];
2092 2130 }
2093 2131
2094 2132 seen = calloc(sizeof(*seen), maxrev + 1);
2095 2133 if (seen == NULL) {
2096 2134 Py_DECREF(gca);
2097 2135 return PyErr_NoMemory();
2098 2136 }
2099 2137
2100 2138 for (i = 0; i < revcount; i++)
2101 2139 seen[revs[i]] = 1ull << i;
2102 2140
2103 2141 interesting = revcount;
2104 2142
2105 2143 for (v = maxrev; v >= 0 && interesting; v--) {
2106 2144 bitmask sv = seen[v];
2107 2145 int parents[2];
2108 2146
2109 2147 if (!sv)
2110 2148 continue;
2111 2149
2112 2150 if (sv < poison) {
2113 2151 interesting -= 1;
2114 2152 if (sv == allseen) {
2115 2153 PyObject *obj = PyInt_FromLong(v);
2116 2154 if (obj == NULL)
2117 2155 goto bail;
2118 2156 if (PyList_Append(gca, obj) == -1) {
2119 2157 Py_DECREF(obj);
2120 2158 goto bail;
2121 2159 }
2122 2160 sv |= poison;
2123 2161 for (i = 0; i < revcount; i++) {
2124 2162 if (revs[i] == v)
2125 2163 goto done;
2126 2164 }
2127 2165 }
2128 2166 }
2129 2167 if (index_get_parents(self, v, parents, maxrev) < 0)
2130 2168 goto bail;
2131 2169
2132 2170 for (i = 0; i < 2; i++) {
2133 2171 int p = parents[i];
2134 2172 if (p == -1)
2135 2173 continue;
2136 2174 sp = seen[p];
2137 2175 if (sv < poison) {
2138 2176 if (sp == 0) {
2139 2177 seen[p] = sv;
2140 2178 interesting++;
2141 2179 } else if (sp != sv)
2142 2180 seen[p] |= sv;
2143 2181 } else {
2144 2182 if (sp && sp < poison)
2145 2183 interesting--;
2146 2184 seen[p] = sv;
2147 2185 }
2148 2186 }
2149 2187 }
2150 2188
2151 2189 done:
2152 2190 free(seen);
2153 2191 return gca;
2154 2192 bail:
2155 2193 free(seen);
2156 2194 Py_XDECREF(gca);
2157 2195 return NULL;
2158 2196 }
2159 2197
2160 2198 /*
2161 2199 * Given a disjoint set of revs, return the subset with the longest
2162 2200 * path to the root.
2163 2201 */
2164 2202 static PyObject *find_deepest(indexObject *self, PyObject *revs)
2165 2203 {
2166 2204 const Py_ssize_t revcount = PyList_GET_SIZE(revs);
2167 2205 static const Py_ssize_t capacity = 24;
2168 2206 int *depth, *interesting = NULL;
2169 2207 int i, j, v, ninteresting;
2170 2208 PyObject *dict = NULL, *keys = NULL;
2171 2209 long *seen = NULL;
2172 2210 int maxrev = -1;
2173 2211 long final;
2174 2212
2175 2213 if (revcount > capacity) {
2176 2214 PyErr_Format(PyExc_OverflowError,
2177 2215 "bitset size (%ld) > capacity (%ld)",
2178 2216 (long)revcount, (long)capacity);
2179 2217 return NULL;
2180 2218 }
2181 2219
2182 2220 for (i = 0; i < revcount; i++) {
2183 2221 int n = (int)PyInt_AsLong(PyList_GET_ITEM(revs, i));
2184 2222 if (n > maxrev)
2185 2223 maxrev = n;
2186 2224 }
2187 2225
2188 2226 depth = calloc(sizeof(*depth), maxrev + 1);
2189 2227 if (depth == NULL)
2190 2228 return PyErr_NoMemory();
2191 2229
2192 2230 seen = calloc(sizeof(*seen), maxrev + 1);
2193 2231 if (seen == NULL) {
2194 2232 PyErr_NoMemory();
2195 2233 goto bail;
2196 2234 }
2197 2235
2198 2236 interesting = calloc(sizeof(*interesting), ((size_t)1) << revcount);
2199 2237 if (interesting == NULL) {
2200 2238 PyErr_NoMemory();
2201 2239 goto bail;
2202 2240 }
2203 2241
2204 2242 if (PyList_Sort(revs) == -1)
2205 2243 goto bail;
2206 2244
2207 2245 for (i = 0; i < revcount; i++) {
2208 2246 int n = (int)PyInt_AsLong(PyList_GET_ITEM(revs, i));
2209 2247 long b = 1l << i;
2210 2248 depth[n] = 1;
2211 2249 seen[n] = b;
2212 2250 interesting[b] = 1;
2213 2251 }
2214 2252
2215 2253 /* invariant: ninteresting is the number of non-zero entries in
2216 2254 * interesting. */
2217 2255 ninteresting = (int)revcount;
2218 2256
2219 2257 for (v = maxrev; v >= 0 && ninteresting > 1; v--) {
2220 2258 int dv = depth[v];
2221 2259 int parents[2];
2222 2260 long sv;
2223 2261
2224 2262 if (dv == 0)
2225 2263 continue;
2226 2264
2227 2265 sv = seen[v];
2228 2266 if (index_get_parents(self, v, parents, maxrev) < 0)
2229 2267 goto bail;
2230 2268
2231 2269 for (i = 0; i < 2; i++) {
2232 2270 int p = parents[i];
2233 2271 long sp;
2234 2272 int dp;
2235 2273
2236 2274 if (p == -1)
2237 2275 continue;
2238 2276
2239 2277 dp = depth[p];
2240 2278 sp = seen[p];
2241 2279 if (dp <= dv) {
2242 2280 depth[p] = dv + 1;
2243 2281 if (sp != sv) {
2244 2282 interesting[sv] += 1;
2245 2283 seen[p] = sv;
2246 2284 if (sp) {
2247 2285 interesting[sp] -= 1;
2248 2286 if (interesting[sp] == 0)
2249 2287 ninteresting -= 1;
2250 2288 }
2251 2289 }
2252 2290 } else if (dv == dp - 1) {
2253 2291 long nsp = sp | sv;
2254 2292 if (nsp == sp)
2255 2293 continue;
2256 2294 seen[p] = nsp;
2257 2295 interesting[sp] -= 1;
2258 2296 if (interesting[sp] == 0)
2259 2297 ninteresting -= 1;
2260 2298 if (interesting[nsp] == 0)
2261 2299 ninteresting += 1;
2262 2300 interesting[nsp] += 1;
2263 2301 }
2264 2302 }
2265 2303 interesting[sv] -= 1;
2266 2304 if (interesting[sv] == 0)
2267 2305 ninteresting -= 1;
2268 2306 }
2269 2307
2270 2308 final = 0;
2271 2309 j = ninteresting;
2272 2310 for (i = 0; i < (int)(2 << revcount) && j > 0; i++) {
2273 2311 if (interesting[i] == 0)
2274 2312 continue;
2275 2313 final |= i;
2276 2314 j -= 1;
2277 2315 }
2278 2316 if (final == 0) {
2279 2317 keys = PyList_New(0);
2280 2318 goto bail;
2281 2319 }
2282 2320
2283 2321 dict = PyDict_New();
2284 2322 if (dict == NULL)
2285 2323 goto bail;
2286 2324
2287 2325 for (i = 0; i < revcount; i++) {
2288 2326 PyObject *key;
2289 2327
2290 2328 if ((final & (1 << i)) == 0)
2291 2329 continue;
2292 2330
2293 2331 key = PyList_GET_ITEM(revs, i);
2294 2332 Py_INCREF(key);
2295 2333 Py_INCREF(Py_None);
2296 2334 if (PyDict_SetItem(dict, key, Py_None) == -1) {
2297 2335 Py_DECREF(key);
2298 2336 Py_DECREF(Py_None);
2299 2337 goto bail;
2300 2338 }
2301 2339 }
2302 2340
2303 2341 keys = PyDict_Keys(dict);
2304 2342
2305 2343 bail:
2306 2344 free(depth);
2307 2345 free(seen);
2308 2346 free(interesting);
2309 2347 Py_XDECREF(dict);
2310 2348
2311 2349 return keys;
2312 2350 }
2313 2351
2314 2352 /*
2315 2353 * Given a (possibly overlapping) set of revs, return all the
2316 2354 * common ancestors heads: heads(::args[0] and ::a[1] and ...)
2317 2355 */
2318 2356 static PyObject *index_commonancestorsheads(indexObject *self, PyObject *args)
2319 2357 {
2320 2358 PyObject *ret = NULL;
2321 2359 Py_ssize_t argcount, i, len;
2322 2360 bitmask repeat = 0;
2323 2361 int revcount = 0;
2324 2362 int *revs;
2325 2363
2326 2364 argcount = PySequence_Length(args);
2327 2365 revs = PyMem_Malloc(argcount * sizeof(*revs));
2328 2366 if (argcount > 0 && revs == NULL)
2329 2367 return PyErr_NoMemory();
2330 2368 len = index_length(self);
2331 2369
2332 2370 for (i = 0; i < argcount; i++) {
2333 2371 static const int capacity = 24;
2334 2372 PyObject *obj = PySequence_GetItem(args, i);
2335 2373 bitmask x;
2336 2374 long val;
2337 2375
2338 2376 if (!PyInt_Check(obj)) {
2339 2377 PyErr_SetString(PyExc_TypeError,
2340 2378 "arguments must all be ints");
2341 2379 Py_DECREF(obj);
2342 2380 goto bail;
2343 2381 }
2344 2382 val = PyInt_AsLong(obj);
2345 2383 Py_DECREF(obj);
2346 2384 if (val == -1) {
2347 2385 ret = PyList_New(0);
2348 2386 goto done;
2349 2387 }
2350 2388 if (val < 0 || val >= len) {
2351 2389 PyErr_SetString(PyExc_IndexError, "index out of range");
2352 2390 goto bail;
2353 2391 }
2354 2392 /* this cheesy bloom filter lets us avoid some more
2355 2393 * expensive duplicate checks in the common set-is-disjoint
2356 2394 * case */
2357 2395 x = 1ull << (val & 0x3f);
2358 2396 if (repeat & x) {
2359 2397 int k;
2360 2398 for (k = 0; k < revcount; k++) {
2361 2399 if (val == revs[k])
2362 2400 goto duplicate;
2363 2401 }
2364 2402 } else
2365 2403 repeat |= x;
2366 2404 if (revcount >= capacity) {
2367 2405 PyErr_Format(PyExc_OverflowError,
2368 2406 "bitset size (%d) > capacity (%d)",
2369 2407 revcount, capacity);
2370 2408 goto bail;
2371 2409 }
2372 2410 revs[revcount++] = (int)val;
2373 2411 duplicate:;
2374 2412 }
2375 2413
2376 2414 if (revcount == 0) {
2377 2415 ret = PyList_New(0);
2378 2416 goto done;
2379 2417 }
2380 2418 if (revcount == 1) {
2381 2419 PyObject *obj;
2382 2420 ret = PyList_New(1);
2383 2421 if (ret == NULL)
2384 2422 goto bail;
2385 2423 obj = PyInt_FromLong(revs[0]);
2386 2424 if (obj == NULL)
2387 2425 goto bail;
2388 2426 PyList_SET_ITEM(ret, 0, obj);
2389 2427 goto done;
2390 2428 }
2391 2429
2392 2430 ret = find_gca_candidates(self, revs, revcount);
2393 2431 if (ret == NULL)
2394 2432 goto bail;
2395 2433
2396 2434 done:
2397 2435 PyMem_Free(revs);
2398 2436 return ret;
2399 2437
2400 2438 bail:
2401 2439 PyMem_Free(revs);
2402 2440 Py_XDECREF(ret);
2403 2441 return NULL;
2404 2442 }
2405 2443
2406 2444 /*
2407 2445 * Given a (possibly overlapping) set of revs, return the greatest
2408 2446 * common ancestors: those with the longest path to the root.
2409 2447 */
2410 2448 static PyObject *index_ancestors(indexObject *self, PyObject *args)
2411 2449 {
2412 2450 PyObject *ret;
2413 2451 PyObject *gca = index_commonancestorsheads(self, args);
2414 2452 if (gca == NULL)
2415 2453 return NULL;
2416 2454
2417 2455 if (PyList_GET_SIZE(gca) <= 1) {
2418 2456 return gca;
2419 2457 }
2420 2458
2421 2459 ret = find_deepest(self, gca);
2422 2460 Py_DECREF(gca);
2423 2461 return ret;
2424 2462 }
2425 2463
2426 2464 /*
2427 2465 * Invalidate any trie entries introduced by added revs.
2428 2466 */
2429 2467 static void index_invalidate_added(indexObject *self, Py_ssize_t start)
2430 2468 {
2431 2469 Py_ssize_t i, len;
2432 2470
2433 2471 len = self->length + self->new_length;
2434 2472 i = start - self->length;
2435 2473 if (i < 0)
2436 2474 return;
2437 2475
2438 2476 for (i = start; i < len; i++)
2439 2477 nt_delete_node(&self->nt, index_deref(self, i) + 32);
2440 2478
2441 2479 self->new_length = start - self->length;
2442 2480 }
2443 2481
2444 2482 /*
2445 2483 * Delete a numeric range of revs, which must be at the end of the
2446 2484 * range.
2447 2485 */
2448 2486 static int index_slice_del(indexObject *self, PyObject *item)
2449 2487 {
2450 2488 Py_ssize_t start, stop, step, slicelength;
2451 2489 Py_ssize_t length = index_length(self) + 1;
2452 2490 int ret = 0;
2453 2491
2454 2492 /* Argument changed from PySliceObject* to PyObject* in Python 3. */
2455 2493 #ifdef IS_PY3K
2456 2494 if (PySlice_GetIndicesEx(item, length, &start, &stop, &step,
2457 2495 &slicelength) < 0)
2458 2496 #else
2459 2497 if (PySlice_GetIndicesEx((PySliceObject *)item, length, &start, &stop,
2460 2498 &step, &slicelength) < 0)
2461 2499 #endif
2462 2500 return -1;
2463 2501
2464 2502 if (slicelength <= 0)
2465 2503 return 0;
2466 2504
2467 2505 if ((step < 0 && start < stop) || (step > 0 && start > stop))
2468 2506 stop = start;
2469 2507
2470 2508 if (step < 0) {
2471 2509 stop = start + 1;
2472 2510 start = stop + step * (slicelength - 1) - 1;
2473 2511 step = -step;
2474 2512 }
2475 2513
2476 2514 if (step != 1) {
2477 2515 PyErr_SetString(PyExc_ValueError,
2478 2516 "revlog index delete requires step size of 1");
2479 2517 return -1;
2480 2518 }
2481 2519
2482 2520 if (stop != length - 1) {
2483 2521 PyErr_SetString(PyExc_IndexError,
2484 2522 "revlog index deletion indices are invalid");
2485 2523 return -1;
2486 2524 }
2487 2525
2488 2526 if (start < self->length) {
2489 2527 if (self->ntinitialized) {
2490 2528 Py_ssize_t i;
2491 2529
2492 2530 for (i = start; i < self->length; i++) {
2493 2531 const char *node = index_node_existing(self, i);
2494 2532 if (node == NULL)
2495 2533 return -1;
2496 2534
2497 2535 nt_delete_node(&self->nt, node);
2498 2536 }
2499 2537 if (self->new_length)
2500 2538 index_invalidate_added(self, self->length);
2501 2539 if (self->ntrev > start)
2502 2540 self->ntrev = (int)start;
2503 2541 } else if (self->new_length) {
2504 2542 self->new_length = 0;
2505 2543 }
2506 2544
2507 2545 self->length = start;
2508 2546 goto done;
2509 2547 }
2510 2548
2511 2549 if (self->ntinitialized) {
2512 2550 index_invalidate_added(self, start);
2513 2551 if (self->ntrev > start)
2514 2552 self->ntrev = (int)start;
2515 2553 } else {
2516 2554 self->new_length = start - self->length;
2517 2555 }
2518 2556 done:
2519 2557 Py_CLEAR(self->headrevs);
2520 2558 return ret;
2521 2559 }
2522 2560
2523 2561 /*
2524 2562 * Supported ops:
2525 2563 *
2526 2564 * slice deletion
2527 2565 * string assignment (extend node->rev mapping)
2528 2566 * string deletion (shrink node->rev mapping)
2529 2567 */
2530 2568 static int index_assign_subscript(indexObject *self, PyObject *item,
2531 2569 PyObject *value)
2532 2570 {
2533 2571 char *node;
2534 2572 long rev;
2535 2573
2536 2574 if (PySlice_Check(item) && value == NULL)
2537 2575 return index_slice_del(self, item);
2538 2576
2539 2577 if (node_check(self->nodelen, item, &node) == -1)
2540 2578 return -1;
2541 2579
2542 2580 if (value == NULL)
2543 2581 return self->ntinitialized ? nt_delete_node(&self->nt, node)
2544 2582 : 0;
2545 2583 rev = PyInt_AsLong(value);
2546 2584 if (rev > INT_MAX || rev < 0) {
2547 2585 if (!PyErr_Occurred())
2548 2586 PyErr_SetString(PyExc_ValueError, "rev out of range");
2549 2587 return -1;
2550 2588 }
2551 2589
2552 2590 if (index_init_nt(self) == -1)
2553 2591 return -1;
2554 2592 return nt_insert(&self->nt, node, (int)rev);
2555 2593 }
2556 2594
2557 2595 /*
2558 2596 * Find all RevlogNG entries in an index that has inline data. Update
2559 2597 * the optional "offsets" table with those entries.
2560 2598 */
2561 2599 static Py_ssize_t inline_scan(indexObject *self, const char **offsets)
2562 2600 {
2563 2601 const char *data = (const char *)self->buf.buf;
2564 2602 Py_ssize_t pos = 0;
2565 2603 Py_ssize_t end = self->buf.len;
2566 long incr = v1_hdrsize;
2604 long incr = self->hdrsize;
2567 2605 Py_ssize_t len = 0;
2568 2606
2569 while (pos + v1_hdrsize <= end && pos >= 0) {
2570 uint32_t comp_len;
2607 while (pos + self->hdrsize <= end && pos >= 0) {
2608 uint32_t comp_len, sidedata_comp_len = 0;
2571 2609 /* 3rd element of header is length of compressed inline data */
2572 2610 comp_len = getbe32(data + pos + 8);
2573 incr = v1_hdrsize + comp_len;
2611 if (self->hdrsize == v2_hdrsize) {
2612 sidedata_comp_len = getbe32(data + pos + 72);
2613 }
2614 incr = self->hdrsize + comp_len + sidedata_comp_len;
2574 2615 if (offsets)
2575 2616 offsets[len] = data + pos;
2576 2617 len++;
2577 2618 pos += incr;
2578 2619 }
2579 2620
2580 2621 if (pos != end) {
2581 2622 if (!PyErr_Occurred())
2582 2623 PyErr_SetString(PyExc_ValueError, "corrupt index file");
2583 2624 return -1;
2584 2625 }
2585 2626
2586 2627 return len;
2587 2628 }
2588 2629
2589 static int index_init(indexObject *self, PyObject *args)
2630 static int index_init(indexObject *self, PyObject *args, PyObject *kwargs)
2590 2631 {
2591 PyObject *data_obj, *inlined_obj;
2632 PyObject *data_obj, *inlined_obj, *revlogv2;
2592 2633 Py_ssize_t size;
2593 2634
2635 static char *kwlist[] = {"data", "inlined", "revlogv2", NULL};
2636
2594 2637 /* Initialize before argument-checking to avoid index_dealloc() crash.
2595 2638 */
2596 2639 self->added = NULL;
2597 2640 self->new_length = 0;
2598 2641 self->added_length = 0;
2599 2642 self->data = NULL;
2600 2643 memset(&self->buf, 0, sizeof(self->buf));
2601 2644 self->headrevs = NULL;
2602 2645 self->filteredrevs = Py_None;
2603 2646 Py_INCREF(Py_None);
2604 2647 self->ntinitialized = 0;
2605 2648 self->offsets = NULL;
2606 2649 self->nodelen = 20;
2607 2650 self->nullentry = NULL;
2608 2651
2609 if (!PyArg_ParseTuple(args, "OO", &data_obj, &inlined_obj))
2652 revlogv2 = NULL;
2653 if (!PyArg_ParseTupleAndKeywords(args, kwargs, "OO|O", kwlist,
2654 &data_obj, &inlined_obj, &revlogv2))
2610 2655 return -1;
2611 2656 if (!PyObject_CheckBuffer(data_obj)) {
2612 2657 PyErr_SetString(PyExc_TypeError,
2613 2658 "data does not support buffer interface");
2614 2659 return -1;
2615 2660 }
2616 2661 if (self->nodelen < 20 || self->nodelen > (Py_ssize_t)sizeof(nullid)) {
2617 2662 PyErr_SetString(PyExc_RuntimeError, "unsupported node size");
2618 2663 return -1;
2619 2664 }
2620 2665
2621 self->nullentry = Py_BuildValue(PY23("iiiiiiis#", "iiiiiiiy#"), 0, 0, 0,
2622 -1, -1, -1, -1, nullid, self->nodelen);
2666 if (revlogv2 && PyObject_IsTrue(revlogv2)) {
2667 self->hdrsize = v2_hdrsize;
2668 } else {
2669 self->hdrsize = v1_hdrsize;
2670 }
2671
2672 if (self->hdrsize == v1_hdrsize) {
2673 self->nullentry =
2674 Py_BuildValue(PY23("iiiiiiis#", "iiiiiiiy#"), 0, 0, 0, -1,
2675 -1, -1, -1, nullid, self->nodelen);
2676 } else {
2677 self->nullentry = Py_BuildValue(
2678 PY23("iiiiiiis#ii", "iiiiiiiy#ii"), 0, 0, 0, -1, -1, -1,
2679 -1, nullid, self->nodelen, 0, 0);
2680 }
2681
2623 2682 if (!self->nullentry)
2624 2683 return -1;
2625 2684 PyObject_GC_UnTrack(self->nullentry);
2626 2685
2627 2686 if (PyObject_GetBuffer(data_obj, &self->buf, PyBUF_SIMPLE) == -1)
2628 2687 return -1;
2629 2688 size = self->buf.len;
2630 2689
2631 2690 self->inlined = inlined_obj && PyObject_IsTrue(inlined_obj);
2632 2691 self->data = data_obj;
2633 2692
2634 2693 self->ntlookups = self->ntmisses = 0;
2635 2694 self->ntrev = -1;
2636 2695 Py_INCREF(self->data);
2637 2696
2638 2697 if (self->inlined) {
2639 2698 Py_ssize_t len = inline_scan(self, NULL);
2640 2699 if (len == -1)
2641 2700 goto bail;
2642 2701 self->length = len;
2643 2702 } else {
2644 if (size % v1_hdrsize) {
2703 if (size % self->hdrsize) {
2645 2704 PyErr_SetString(PyExc_ValueError, "corrupt index file");
2646 2705 goto bail;
2647 2706 }
2648 self->length = size / v1_hdrsize;
2707 self->length = size / self->hdrsize;
2649 2708 }
2650 2709
2651 2710 return 0;
2652 2711 bail:
2653 2712 return -1;
2654 2713 }
2655 2714
2656 2715 static PyObject *index_nodemap(indexObject *self)
2657 2716 {
2658 2717 Py_INCREF(self);
2659 2718 return (PyObject *)self;
2660 2719 }
2661 2720
2662 2721 static void _index_clearcaches(indexObject *self)
2663 2722 {
2664 2723 if (self->offsets) {
2665 2724 PyMem_Free((void *)self->offsets);
2666 2725 self->offsets = NULL;
2667 2726 }
2668 2727 if (self->ntinitialized) {
2669 2728 nt_dealloc(&self->nt);
2670 2729 }
2671 2730 self->ntinitialized = 0;
2672 2731 Py_CLEAR(self->headrevs);
2673 2732 }
2674 2733
2675 2734 static PyObject *index_clearcaches(indexObject *self)
2676 2735 {
2677 2736 _index_clearcaches(self);
2678 2737 self->ntrev = -1;
2679 2738 self->ntlookups = self->ntmisses = 0;
2680 2739 Py_RETURN_NONE;
2681 2740 }
2682 2741
2683 2742 static void index_dealloc(indexObject *self)
2684 2743 {
2685 2744 _index_clearcaches(self);
2686 2745 Py_XDECREF(self->filteredrevs);
2687 2746 if (self->buf.buf) {
2688 2747 PyBuffer_Release(&self->buf);
2689 2748 memset(&self->buf, 0, sizeof(self->buf));
2690 2749 }
2691 2750 Py_XDECREF(self->data);
2692 2751 PyMem_Free(self->added);
2693 2752 Py_XDECREF(self->nullentry);
2694 2753 PyObject_Del(self);
2695 2754 }
2696 2755
2697 2756 static PySequenceMethods index_sequence_methods = {
2698 2757 (lenfunc)index_length, /* sq_length */
2699 2758 0, /* sq_concat */
2700 2759 0, /* sq_repeat */
2701 2760 (ssizeargfunc)index_get, /* sq_item */
2702 2761 0, /* sq_slice */
2703 2762 0, /* sq_ass_item */
2704 2763 0, /* sq_ass_slice */
2705 2764 (objobjproc)index_contains, /* sq_contains */
2706 2765 };
2707 2766
2708 2767 static PyMappingMethods index_mapping_methods = {
2709 2768 (lenfunc)index_length, /* mp_length */
2710 2769 (binaryfunc)index_getitem, /* mp_subscript */
2711 2770 (objobjargproc)index_assign_subscript, /* mp_ass_subscript */
2712 2771 };
2713 2772
2714 2773 static PyMethodDef index_methods[] = {
2715 2774 {"ancestors", (PyCFunction)index_ancestors, METH_VARARGS,
2716 2775 "return the gca set of the given revs"},
2717 2776 {"commonancestorsheads", (PyCFunction)index_commonancestorsheads,
2718 2777 METH_VARARGS,
2719 2778 "return the heads of the common ancestors of the given revs"},
2720 2779 {"clearcaches", (PyCFunction)index_clearcaches, METH_NOARGS,
2721 2780 "clear the index caches"},
2722 2781 {"get", (PyCFunction)index_m_get, METH_VARARGS, "get an index entry"},
2723 2782 {"get_rev", (PyCFunction)index_m_get, METH_VARARGS,
2724 2783 "return `rev` associated with a node or None"},
2725 2784 {"has_node", (PyCFunction)index_m_has_node, METH_O,
2726 2785 "return True if the node exist in the index"},
2727 2786 {"rev", (PyCFunction)index_m_rev, METH_O,
2728 2787 "return `rev` associated with a node or raise RevlogError"},
2729 2788 {"computephasesmapsets", (PyCFunction)compute_phases_map_sets, METH_VARARGS,
2730 2789 "compute phases"},
2731 2790 {"reachableroots2", (PyCFunction)reachableroots2, METH_VARARGS,
2732 2791 "reachableroots"},
2733 2792 {"headrevs", (PyCFunction)index_headrevs, METH_VARARGS,
2734 2793 "get head revisions"}, /* Can do filtering since 3.2 */
2735 2794 {"headrevsfiltered", (PyCFunction)index_headrevs, METH_VARARGS,
2736 2795 "get filtered head revisions"}, /* Can always do filtering */
2737 2796 {"issnapshot", (PyCFunction)index_issnapshot, METH_O,
2738 2797 "True if the object is a snapshot"},
2739 2798 {"findsnapshots", (PyCFunction)index_findsnapshots, METH_VARARGS,
2740 2799 "Gather snapshot data in a cache dict"},
2741 2800 {"deltachain", (PyCFunction)index_deltachain, METH_VARARGS,
2742 2801 "determine revisions with deltas to reconstruct fulltext"},
2743 2802 {"slicechunktodensity", (PyCFunction)index_slicechunktodensity,
2744 2803 METH_VARARGS, "determine revisions with deltas to reconstruct fulltext"},
2745 2804 {"append", (PyCFunction)index_append, METH_O, "append an index entry"},
2746 2805 {"partialmatch", (PyCFunction)index_partialmatch, METH_VARARGS,
2747 2806 "match a potentially ambiguous node ID"},
2748 2807 {"shortest", (PyCFunction)index_shortest, METH_VARARGS,
2749 2808 "find length of shortest hex nodeid of a binary ID"},
2750 2809 {"stats", (PyCFunction)index_stats, METH_NOARGS, "stats for the index"},
2751 2810 {NULL} /* Sentinel */
2752 2811 };
2753 2812
2754 2813 static PyGetSetDef index_getset[] = {
2755 2814 {"nodemap", (getter)index_nodemap, NULL, "nodemap", NULL},
2756 2815 {NULL} /* Sentinel */
2757 2816 };
2758 2817
2759 2818 PyTypeObject HgRevlogIndex_Type = {
2760 2819 PyVarObject_HEAD_INIT(NULL, 0) /* header */
2761 2820 "parsers.index", /* tp_name */
2762 2821 sizeof(indexObject), /* tp_basicsize */
2763 2822 0, /* tp_itemsize */
2764 2823 (destructor)index_dealloc, /* tp_dealloc */
2765 2824 0, /* tp_print */
2766 2825 0, /* tp_getattr */
2767 2826 0, /* tp_setattr */
2768 2827 0, /* tp_compare */
2769 2828 0, /* tp_repr */
2770 2829 0, /* tp_as_number */
2771 2830 &index_sequence_methods, /* tp_as_sequence */
2772 2831 &index_mapping_methods, /* tp_as_mapping */
2773 2832 0, /* tp_hash */
2774 2833 0, /* tp_call */
2775 2834 0, /* tp_str */
2776 2835 0, /* tp_getattro */
2777 2836 0, /* tp_setattro */
2778 2837 0, /* tp_as_buffer */
2779 2838 Py_TPFLAGS_DEFAULT, /* tp_flags */
2780 2839 "revlog index", /* tp_doc */
2781 2840 0, /* tp_traverse */
2782 2841 0, /* tp_clear */
2783 2842 0, /* tp_richcompare */
2784 2843 0, /* tp_weaklistoffset */
2785 2844 0, /* tp_iter */
2786 2845 0, /* tp_iternext */
2787 2846 index_methods, /* tp_methods */
2788 2847 0, /* tp_members */
2789 2848 index_getset, /* tp_getset */
2790 2849 0, /* tp_base */
2791 2850 0, /* tp_dict */
2792 2851 0, /* tp_descr_get */
2793 2852 0, /* tp_descr_set */
2794 2853 0, /* tp_dictoffset */
2795 2854 (initproc)index_init, /* tp_init */
2796 2855 0, /* tp_alloc */
2797 2856 };
2798 2857
2799 2858 /*
2800 * returns a tuple of the form (index, index, cache) with elements as
2859 * returns a tuple of the form (index, cache) with elements as
2801 2860 * follows:
2802 2861 *
2803 * index: an index object that lazily parses RevlogNG records
2862 * index: an index object that lazily parses Revlog (v1 or v2) records
2804 2863 * cache: if data is inlined, a tuple (0, index_file_content), else None
2805 2864 * index_file_content could be a string, or a buffer
2806 2865 *
2807 2866 * added complications are for backwards compatibility
2808 2867 */
2809 PyObject *parse_index2(PyObject *self, PyObject *args)
2868 PyObject *parse_index2(PyObject *self, PyObject *args, PyObject *kwargs)
2810 2869 {
2811 2870 PyObject *cache = NULL;
2812 2871 indexObject *idx;
2813 2872 int ret;
2814 2873
2815 2874 idx = PyObject_New(indexObject, &HgRevlogIndex_Type);
2816 2875 if (idx == NULL)
2817 2876 goto bail;
2818 2877
2819 ret = index_init(idx, args);
2878 ret = index_init(idx, args, kwargs);
2820 2879 if (ret == -1)
2821 2880 goto bail;
2822 2881
2823 2882 if (idx->inlined) {
2824 2883 cache = Py_BuildValue("iO", 0, idx->data);
2825 2884 if (cache == NULL)
2826 2885 goto bail;
2827 2886 } else {
2828 2887 cache = Py_None;
2829 2888 Py_INCREF(cache);
2830 2889 }
2831 2890
2832 2891 return Py_BuildValue("NN", idx, cache);
2833 2892
2834 2893 bail:
2835 2894 Py_XDECREF(idx);
2836 2895 Py_XDECREF(cache);
2837 2896 return NULL;
2838 2897 }
2839 2898
2840 2899 static Revlog_CAPI CAPI = {
2841 2900 /* increment the abi_version field upon each change in the Revlog_CAPI
2842 2901 struct or in the ABI of the listed functions */
2843 2902 2,
2844 2903 index_length,
2845 2904 index_node,
2846 2905 HgRevlogIndex_GetParents,
2847 2906 };
2848 2907
2849 2908 void revlog_module_init(PyObject *mod)
2850 2909 {
2851 2910 PyObject *caps = NULL;
2852 2911 HgRevlogIndex_Type.tp_new = PyType_GenericNew;
2853 2912 if (PyType_Ready(&HgRevlogIndex_Type) < 0)
2854 2913 return;
2855 2914 Py_INCREF(&HgRevlogIndex_Type);
2856 2915 PyModule_AddObject(mod, "index", (PyObject *)&HgRevlogIndex_Type);
2857 2916
2858 2917 nodetreeType.tp_new = PyType_GenericNew;
2859 2918 if (PyType_Ready(&nodetreeType) < 0)
2860 2919 return;
2861 2920 Py_INCREF(&nodetreeType);
2862 2921 PyModule_AddObject(mod, "nodetree", (PyObject *)&nodetreeType);
2863 2922
2864 2923 caps = PyCapsule_New(&CAPI, "mercurial.cext.parsers.revlog_CAPI", NULL);
2865 2924 if (caps != NULL)
2866 2925 PyModule_AddObject(mod, "revlog_CAPI", caps);
2867 2926 }
General Comments 0
You need to be logged in to leave comments. Login now