##// END OF EJS Templates
index: pass only nodetree to nt_new()...
Martin von Zweigbergk -
r38951:fff675df default
parent child Browse files
Show More
@@ -1,2180 +1,2179 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 #include <Python.h>
11 11 #include <assert.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_AS_LONG PyLong_AS_LONG
28 28 #define PyInt_AsLong PyLong_AsLong
29 29 #endif
30 30
31 31 typedef struct {
32 32 int children[16];
33 33 } nodetreenode;
34 34
35 35 /*
36 36 * A base-16 trie for fast node->rev mapping.
37 37 *
38 38 * Positive value is index of the next node in the trie
39 39 * Negative value is a leaf: -(rev + 2)
40 40 * Zero is empty
41 41 */
42 42 typedef struct {
43 43 nodetreenode *nodes;
44 44 unsigned length; /* # nodes in use */
45 45 unsigned capacity; /* # nodes allocated */
46 46 int depth; /* maximum depth of tree */
47 47 int splits; /* # splits performed */
48 48 } nodetree;
49 49
50 50 /*
51 51 * This class has two behaviors.
52 52 *
53 53 * When used in a list-like way (with integer keys), we decode an
54 54 * entry in a RevlogNG index file on demand. Our last entry is a
55 55 * sentinel, always a nullid. We have limited support for
56 56 * integer-keyed insert and delete, only at elements right before the
57 57 * sentinel.
58 58 *
59 59 * With string keys, we lazily perform a reverse mapping from node to
60 60 * rev, using a base-16 trie.
61 61 */
62 62 typedef struct {
63 63 PyObject_HEAD
64 64 /* Type-specific fields go here. */
65 65 PyObject *data; /* raw bytes of index */
66 66 Py_buffer buf; /* buffer of data */
67 67 PyObject **cache; /* cached tuples */
68 68 const char **offsets; /* populated on demand */
69 69 Py_ssize_t raw_length; /* original number of elements */
70 70 Py_ssize_t length; /* current number of elements */
71 71 PyObject *added; /* populated on demand */
72 72 PyObject *headrevs; /* cache, invalidated on changes */
73 73 PyObject *filteredrevs;/* filtered revs set */
74 74 nodetree *nt; /* base-16 trie */
75 75 int ntrev; /* last rev scanned */
76 76 int ntlookups; /* # lookups */
77 77 int ntmisses; /* # lookups that miss the cache */
78 78 int inlined;
79 79 } indexObject;
80 80
81 81 static Py_ssize_t index_length(const indexObject *self)
82 82 {
83 83 if (self->added == NULL)
84 84 return self->length - 1;
85 85 return self->length + PyList_GET_SIZE(self->added) - 1;
86 86 }
87 87
88 88 static PyObject *nullentry;
89 89 static const char nullid[20];
90 90
91 91 static Py_ssize_t inline_scan(indexObject *self, const char **offsets);
92 92
93 93 #if LONG_MAX == 0x7fffffffL
94 94 static const char *const tuple_format = PY23("Kiiiiiis#", "Kiiiiiiy#");
95 95 #else
96 96 static const char *const tuple_format = PY23("kiiiiiis#", "kiiiiiiy#");
97 97 #endif
98 98
99 99 /* A RevlogNG v1 index entry is 64 bytes long. */
100 100 static const long v1_hdrsize = 64;
101 101
102 102 /*
103 103 * Return a pointer to the beginning of a RevlogNG record.
104 104 */
105 105 static const char *index_deref(indexObject *self, Py_ssize_t pos)
106 106 {
107 107 if (self->inlined && pos > 0) {
108 108 if (self->offsets == NULL) {
109 109 self->offsets = PyMem_Malloc(self->raw_length *
110 110 sizeof(*self->offsets));
111 111 if (self->offsets == NULL)
112 112 return (const char *)PyErr_NoMemory();
113 113 inline_scan(self, self->offsets);
114 114 }
115 115 return self->offsets[pos];
116 116 }
117 117
118 118 return (const char *)(self->buf.buf) + pos * v1_hdrsize;
119 119 }
120 120
121 121 static inline int index_get_parents(indexObject *self, Py_ssize_t rev,
122 122 int *ps, int maxrev)
123 123 {
124 124 if (rev >= self->length - 1) {
125 125 PyObject *tuple = PyList_GET_ITEM(self->added,
126 126 rev - self->length + 1);
127 127 ps[0] = (int)PyInt_AS_LONG(PyTuple_GET_ITEM(tuple, 5));
128 128 ps[1] = (int)PyInt_AS_LONG(PyTuple_GET_ITEM(tuple, 6));
129 129 } else {
130 130 const char *data = index_deref(self, rev);
131 131 ps[0] = getbe32(data + 24);
132 132 ps[1] = getbe32(data + 28);
133 133 }
134 134 /* If index file is corrupted, ps[] may point to invalid revisions. So
135 135 * there is a risk of buffer overflow to trust them unconditionally. */
136 136 if (ps[0] > maxrev || ps[1] > maxrev) {
137 137 PyErr_SetString(PyExc_ValueError, "parent out of range");
138 138 return -1;
139 139 }
140 140 return 0;
141 141 }
142 142
143 143
144 144 /*
145 145 * RevlogNG format (all in big endian, data may be inlined):
146 146 * 6 bytes: offset
147 147 * 2 bytes: flags
148 148 * 4 bytes: compressed length
149 149 * 4 bytes: uncompressed length
150 150 * 4 bytes: base revision
151 151 * 4 bytes: link revision
152 152 * 4 bytes: parent 1 revision
153 153 * 4 bytes: parent 2 revision
154 154 * 32 bytes: nodeid (only 20 bytes used)
155 155 */
156 156 static PyObject *index_get(indexObject *self, Py_ssize_t pos)
157 157 {
158 158 uint64_t offset_flags;
159 159 int comp_len, uncomp_len, base_rev, link_rev, parent_1, parent_2;
160 160 const char *c_node_id;
161 161 const char *data;
162 162 Py_ssize_t length = index_length(self);
163 163 PyObject *entry;
164 164
165 165 if (pos == -1) {
166 166 Py_INCREF(nullentry);
167 167 return nullentry;
168 168 }
169 169
170 170 if (pos < 0 || pos >= length) {
171 171 PyErr_SetString(PyExc_IndexError, "revlog index out of range");
172 172 return NULL;
173 173 }
174 174
175 175 if (pos >= self->length - 1) {
176 176 PyObject *obj;
177 177 obj = PyList_GET_ITEM(self->added, pos - self->length + 1);
178 178 Py_INCREF(obj);
179 179 return obj;
180 180 }
181 181
182 182 if (self->cache) {
183 183 if (self->cache[pos]) {
184 184 Py_INCREF(self->cache[pos]);
185 185 return self->cache[pos];
186 186 }
187 187 } else {
188 188 self->cache = calloc(self->raw_length, sizeof(PyObject *));
189 189 if (self->cache == NULL)
190 190 return PyErr_NoMemory();
191 191 }
192 192
193 193 data = index_deref(self, pos);
194 194 if (data == NULL)
195 195 return NULL;
196 196
197 197 offset_flags = getbe32(data + 4);
198 198 if (pos == 0) /* mask out version number for the first entry */
199 199 offset_flags &= 0xFFFF;
200 200 else {
201 201 uint32_t offset_high = getbe32(data);
202 202 offset_flags |= ((uint64_t)offset_high) << 32;
203 203 }
204 204
205 205 comp_len = getbe32(data + 8);
206 206 uncomp_len = getbe32(data + 12);
207 207 base_rev = getbe32(data + 16);
208 208 link_rev = getbe32(data + 20);
209 209 parent_1 = getbe32(data + 24);
210 210 parent_2 = getbe32(data + 28);
211 211 c_node_id = data + 32;
212 212
213 213 entry = Py_BuildValue(tuple_format, offset_flags, comp_len,
214 214 uncomp_len, base_rev, link_rev,
215 215 parent_1, parent_2, c_node_id, 20);
216 216
217 217 if (entry) {
218 218 PyObject_GC_UnTrack(entry);
219 219 Py_INCREF(entry);
220 220 }
221 221
222 222 self->cache[pos] = entry;
223 223
224 224 return entry;
225 225 }
226 226
227 227 /*
228 228 * Return the 20-byte SHA of the node corresponding to the given rev.
229 229 */
230 230 static const char *index_node(indexObject *self, Py_ssize_t pos)
231 231 {
232 232 Py_ssize_t length = index_length(self);
233 233 const char *data;
234 234
235 235 if (pos == -1)
236 236 return nullid;
237 237
238 238 if (pos >= length)
239 239 return NULL;
240 240
241 241 if (pos >= self->length - 1) {
242 242 PyObject *tuple, *str;
243 243 tuple = PyList_GET_ITEM(self->added, pos - self->length + 1);
244 244 str = PyTuple_GetItem(tuple, 7);
245 245 return str ? PyBytes_AS_STRING(str) : NULL;
246 246 }
247 247
248 248 data = index_deref(self, pos);
249 249 return data ? data + 32 : NULL;
250 250 }
251 251
252 252 /*
253 253 * Return the 20-byte SHA of the node corresponding to the given rev. The
254 254 * rev is assumed to be existing. If not, an exception is set.
255 255 */
256 256 static const char *index_node_existing(indexObject *self, Py_ssize_t pos)
257 257 {
258 258 const char *node = index_node(self, pos);
259 259 if (node == NULL) {
260 260 PyErr_Format(PyExc_IndexError, "could not access rev %d",
261 261 (int)pos);
262 262 }
263 263 return node;
264 264 }
265 265
266 266 static int nt_insert(indexObject *self, const char *node, int rev);
267 267
268 268 static int node_check(PyObject *obj, char **node)
269 269 {
270 270 Py_ssize_t nodelen;
271 271 if (PyBytes_AsStringAndSize(obj, node, &nodelen) == -1)
272 272 return -1;
273 273 if (nodelen == 20)
274 274 return 0;
275 275 PyErr_SetString(PyExc_ValueError, "20-byte hash required");
276 276 return -1;
277 277 }
278 278
279 279 static PyObject *index_append(indexObject *self, PyObject *obj)
280 280 {
281 281 char *node;
282 282 Py_ssize_t len;
283 283
284 284 if (!PyTuple_Check(obj) || PyTuple_GET_SIZE(obj) != 8) {
285 285 PyErr_SetString(PyExc_TypeError, "8-tuple required");
286 286 return NULL;
287 287 }
288 288
289 289 if (node_check(PyTuple_GET_ITEM(obj, 7), &node) == -1)
290 290 return NULL;
291 291
292 292 len = index_length(self);
293 293
294 294 if (self->added == NULL) {
295 295 self->added = PyList_New(0);
296 296 if (self->added == NULL)
297 297 return NULL;
298 298 }
299 299
300 300 if (PyList_Append(self->added, obj) == -1)
301 301 return NULL;
302 302
303 303 if (self->nt)
304 304 nt_insert(self, node, len);
305 305
306 306 Py_CLEAR(self->headrevs);
307 307 Py_RETURN_NONE;
308 308 }
309 309
310 310 static void _index_clearcaches(indexObject *self)
311 311 {
312 312 if (self->cache) {
313 313 Py_ssize_t i;
314 314
315 315 for (i = 0; i < self->raw_length; i++)
316 316 Py_CLEAR(self->cache[i]);
317 317 free(self->cache);
318 318 self->cache = NULL;
319 319 }
320 320 if (self->offsets) {
321 321 PyMem_Free(self->offsets);
322 322 self->offsets = NULL;
323 323 }
324 324 if (self->nt != NULL) {
325 325 free(self->nt->nodes);
326 326 free(self->nt);
327 327 }
328 328 self->nt = NULL;
329 329 Py_CLEAR(self->headrevs);
330 330 }
331 331
332 332 static PyObject *index_clearcaches(indexObject *self)
333 333 {
334 334 _index_clearcaches(self);
335 335 self->ntrev = -1;
336 336 self->ntlookups = self->ntmisses = 0;
337 337 Py_RETURN_NONE;
338 338 }
339 339
340 340 static PyObject *index_stats(indexObject *self)
341 341 {
342 342 PyObject *obj = PyDict_New();
343 343 PyObject *t = NULL;
344 344
345 345 if (obj == NULL)
346 346 return NULL;
347 347
348 348 #define istat(__n, __d) \
349 349 do { \
350 350 t = PyInt_FromSsize_t(self->__n); \
351 351 if (!t) \
352 352 goto bail; \
353 353 if (PyDict_SetItemString(obj, __d, t) == -1) \
354 354 goto bail; \
355 355 Py_DECREF(t); \
356 356 } while (0)
357 357
358 358 if (self->added) {
359 359 Py_ssize_t len = PyList_GET_SIZE(self->added);
360 360 t = PyInt_FromSsize_t(len);
361 361 if (!t)
362 362 goto bail;
363 363 if (PyDict_SetItemString(obj, "index entries added", t) == -1)
364 364 goto bail;
365 365 Py_DECREF(t);
366 366 }
367 367
368 368 if (self->raw_length != self->length - 1)
369 369 istat(raw_length, "revs on disk");
370 370 istat(length, "revs in memory");
371 371 istat(ntlookups, "node trie lookups");
372 372 istat(ntmisses, "node trie misses");
373 373 istat(ntrev, "node trie last rev scanned");
374 374 if (self->nt) {
375 375 istat(nt->capacity, "node trie capacity");
376 376 istat(nt->depth, "node trie depth");
377 377 istat(nt->length, "node trie count");
378 378 istat(nt->splits, "node trie splits");
379 379 }
380 380
381 381 #undef istat
382 382
383 383 return obj;
384 384
385 385 bail:
386 386 Py_XDECREF(obj);
387 387 Py_XDECREF(t);
388 388 return NULL;
389 389 }
390 390
391 391 /*
392 392 * When we cache a list, we want to be sure the caller can't mutate
393 393 * the cached copy.
394 394 */
395 395 static PyObject *list_copy(PyObject *list)
396 396 {
397 397 Py_ssize_t len = PyList_GET_SIZE(list);
398 398 PyObject *newlist = PyList_New(len);
399 399 Py_ssize_t i;
400 400
401 401 if (newlist == NULL)
402 402 return NULL;
403 403
404 404 for (i = 0; i < len; i++) {
405 405 PyObject *obj = PyList_GET_ITEM(list, i);
406 406 Py_INCREF(obj);
407 407 PyList_SET_ITEM(newlist, i, obj);
408 408 }
409 409
410 410 return newlist;
411 411 }
412 412
413 413 static int check_filter(PyObject *filter, Py_ssize_t arg)
414 414 {
415 415 if (filter) {
416 416 PyObject *arglist, *result;
417 417 int isfiltered;
418 418
419 419 arglist = Py_BuildValue("(n)", arg);
420 420 if (!arglist) {
421 421 return -1;
422 422 }
423 423
424 424 result = PyEval_CallObject(filter, arglist);
425 425 Py_DECREF(arglist);
426 426 if (!result) {
427 427 return -1;
428 428 }
429 429
430 430 /* PyObject_IsTrue returns 1 if true, 0 if false, -1 if error,
431 431 * same as this function, so we can just return it directly.*/
432 432 isfiltered = PyObject_IsTrue(result);
433 433 Py_DECREF(result);
434 434 return isfiltered;
435 435 } else {
436 436 return 0;
437 437 }
438 438 }
439 439
440 440 static Py_ssize_t add_roots_get_min(indexObject *self, PyObject *list,
441 441 Py_ssize_t marker, char *phases)
442 442 {
443 443 PyObject *iter = NULL;
444 444 PyObject *iter_item = NULL;
445 445 Py_ssize_t min_idx = index_length(self) + 2;
446 446 long iter_item_long;
447 447
448 448 if (PyList_GET_SIZE(list) != 0) {
449 449 iter = PyObject_GetIter(list);
450 450 if (iter == NULL)
451 451 return -2;
452 452 while ((iter_item = PyIter_Next(iter))) {
453 453 iter_item_long = PyInt_AS_LONG(iter_item);
454 454 Py_DECREF(iter_item);
455 455 if (iter_item_long < min_idx)
456 456 min_idx = iter_item_long;
457 457 phases[iter_item_long] = marker;
458 458 }
459 459 Py_DECREF(iter);
460 460 }
461 461
462 462 return min_idx;
463 463 }
464 464
465 465 static inline void set_phase_from_parents(char *phases, int parent_1,
466 466 int parent_2, Py_ssize_t i)
467 467 {
468 468 if (parent_1 >= 0 && phases[parent_1] > phases[i])
469 469 phases[i] = phases[parent_1];
470 470 if (parent_2 >= 0 && phases[parent_2] > phases[i])
471 471 phases[i] = phases[parent_2];
472 472 }
473 473
474 474 static PyObject *reachableroots2(indexObject *self, PyObject *args)
475 475 {
476 476
477 477 /* Input */
478 478 long minroot;
479 479 PyObject *includepatharg = NULL;
480 480 int includepath = 0;
481 481 /* heads and roots are lists */
482 482 PyObject *heads = NULL;
483 483 PyObject *roots = NULL;
484 484 PyObject *reachable = NULL;
485 485
486 486 PyObject *val;
487 487 Py_ssize_t len = index_length(self);
488 488 long revnum;
489 489 Py_ssize_t k;
490 490 Py_ssize_t i;
491 491 Py_ssize_t l;
492 492 int r;
493 493 int parents[2];
494 494
495 495 /* Internal data structure:
496 496 * tovisit: array of length len+1 (all revs + nullrev), filled upto lentovisit
497 497 * revstates: array of length len+1 (all revs + nullrev) */
498 498 int *tovisit = NULL;
499 499 long lentovisit = 0;
500 500 enum { RS_SEEN = 1, RS_ROOT = 2, RS_REACHABLE = 4 };
501 501 char *revstates = NULL;
502 502
503 503 /* Get arguments */
504 504 if (!PyArg_ParseTuple(args, "lO!O!O!", &minroot, &PyList_Type, &heads,
505 505 &PyList_Type, &roots,
506 506 &PyBool_Type, &includepatharg))
507 507 goto bail;
508 508
509 509 if (includepatharg == Py_True)
510 510 includepath = 1;
511 511
512 512 /* Initialize return set */
513 513 reachable = PyList_New(0);
514 514 if (reachable == NULL)
515 515 goto bail;
516 516
517 517 /* Initialize internal datastructures */
518 518 tovisit = (int *)malloc((len + 1) * sizeof(int));
519 519 if (tovisit == NULL) {
520 520 PyErr_NoMemory();
521 521 goto bail;
522 522 }
523 523
524 524 revstates = (char *)calloc(len + 1, 1);
525 525 if (revstates == NULL) {
526 526 PyErr_NoMemory();
527 527 goto bail;
528 528 }
529 529
530 530 l = PyList_GET_SIZE(roots);
531 531 for (i = 0; i < l; i++) {
532 532 revnum = PyInt_AsLong(PyList_GET_ITEM(roots, i));
533 533 if (revnum == -1 && PyErr_Occurred())
534 534 goto bail;
535 535 /* If root is out of range, e.g. wdir(), it must be unreachable
536 536 * from heads. So we can just ignore it. */
537 537 if (revnum + 1 < 0 || revnum + 1 >= len + 1)
538 538 continue;
539 539 revstates[revnum + 1] |= RS_ROOT;
540 540 }
541 541
542 542 /* Populate tovisit with all the heads */
543 543 l = PyList_GET_SIZE(heads);
544 544 for (i = 0; i < l; i++) {
545 545 revnum = PyInt_AsLong(PyList_GET_ITEM(heads, i));
546 546 if (revnum == -1 && PyErr_Occurred())
547 547 goto bail;
548 548 if (revnum + 1 < 0 || revnum + 1 >= len + 1) {
549 549 PyErr_SetString(PyExc_IndexError, "head out of range");
550 550 goto bail;
551 551 }
552 552 if (!(revstates[revnum + 1] & RS_SEEN)) {
553 553 tovisit[lentovisit++] = (int)revnum;
554 554 revstates[revnum + 1] |= RS_SEEN;
555 555 }
556 556 }
557 557
558 558 /* Visit the tovisit list and find the reachable roots */
559 559 k = 0;
560 560 while (k < lentovisit) {
561 561 /* Add the node to reachable if it is a root*/
562 562 revnum = tovisit[k++];
563 563 if (revstates[revnum + 1] & RS_ROOT) {
564 564 revstates[revnum + 1] |= RS_REACHABLE;
565 565 val = PyInt_FromLong(revnum);
566 566 if (val == NULL)
567 567 goto bail;
568 568 r = PyList_Append(reachable, val);
569 569 Py_DECREF(val);
570 570 if (r < 0)
571 571 goto bail;
572 572 if (includepath == 0)
573 573 continue;
574 574 }
575 575
576 576 /* Add its parents to the list of nodes to visit */
577 577 if (revnum == -1)
578 578 continue;
579 579 r = index_get_parents(self, revnum, parents, (int)len - 1);
580 580 if (r < 0)
581 581 goto bail;
582 582 for (i = 0; i < 2; i++) {
583 583 if (!(revstates[parents[i] + 1] & RS_SEEN)
584 584 && parents[i] >= minroot) {
585 585 tovisit[lentovisit++] = parents[i];
586 586 revstates[parents[i] + 1] |= RS_SEEN;
587 587 }
588 588 }
589 589 }
590 590
591 591 /* Find all the nodes in between the roots we found and the heads
592 592 * and add them to the reachable set */
593 593 if (includepath == 1) {
594 594 long minidx = minroot;
595 595 if (minidx < 0)
596 596 minidx = 0;
597 597 for (i = minidx; i < len; i++) {
598 598 if (!(revstates[i + 1] & RS_SEEN))
599 599 continue;
600 600 r = index_get_parents(self, i, parents, (int)len - 1);
601 601 /* Corrupted index file, error is set from
602 602 * index_get_parents */
603 603 if (r < 0)
604 604 goto bail;
605 605 if (((revstates[parents[0] + 1] |
606 606 revstates[parents[1] + 1]) & RS_REACHABLE)
607 607 && !(revstates[i + 1] & RS_REACHABLE)) {
608 608 revstates[i + 1] |= RS_REACHABLE;
609 609 val = PyInt_FromLong(i);
610 610 if (val == NULL)
611 611 goto bail;
612 612 r = PyList_Append(reachable, val);
613 613 Py_DECREF(val);
614 614 if (r < 0)
615 615 goto bail;
616 616 }
617 617 }
618 618 }
619 619
620 620 free(revstates);
621 621 free(tovisit);
622 622 return reachable;
623 623 bail:
624 624 Py_XDECREF(reachable);
625 625 free(revstates);
626 626 free(tovisit);
627 627 return NULL;
628 628 }
629 629
630 630 static PyObject *compute_phases_map_sets(indexObject *self, PyObject *args)
631 631 {
632 632 PyObject *roots = Py_None;
633 633 PyObject *ret = NULL;
634 634 PyObject *phasessize = NULL;
635 635 PyObject *phaseroots = NULL;
636 636 PyObject *phaseset = NULL;
637 637 PyObject *phasessetlist = NULL;
638 638 PyObject *rev = NULL;
639 639 Py_ssize_t len = index_length(self);
640 640 Py_ssize_t numphase = 0;
641 641 Py_ssize_t minrevallphases = 0;
642 642 Py_ssize_t minrevphase = 0;
643 643 Py_ssize_t i = 0;
644 644 char *phases = NULL;
645 645 long phase;
646 646
647 647 if (!PyArg_ParseTuple(args, "O", &roots))
648 648 goto done;
649 649 if (roots == NULL || !PyList_Check(roots)) {
650 650 PyErr_SetString(PyExc_TypeError, "roots must be a list");
651 651 goto done;
652 652 }
653 653
654 654 phases = calloc(len, 1); /* phase per rev: {0: public, 1: draft, 2: secret} */
655 655 if (phases == NULL) {
656 656 PyErr_NoMemory();
657 657 goto done;
658 658 }
659 659 /* Put the phase information of all the roots in phases */
660 660 numphase = PyList_GET_SIZE(roots)+1;
661 661 minrevallphases = len + 1;
662 662 phasessetlist = PyList_New(numphase);
663 663 if (phasessetlist == NULL)
664 664 goto done;
665 665
666 666 PyList_SET_ITEM(phasessetlist, 0, Py_None);
667 667 Py_INCREF(Py_None);
668 668
669 669 for (i = 0; i < numphase-1; i++) {
670 670 phaseroots = PyList_GET_ITEM(roots, i);
671 671 phaseset = PySet_New(NULL);
672 672 if (phaseset == NULL)
673 673 goto release;
674 674 PyList_SET_ITEM(phasessetlist, i+1, phaseset);
675 675 if (!PyList_Check(phaseroots)) {
676 676 PyErr_SetString(PyExc_TypeError,
677 677 "roots item must be a list");
678 678 goto release;
679 679 }
680 680 minrevphase = add_roots_get_min(self, phaseroots, i+1, phases);
681 681 if (minrevphase == -2) /* Error from add_roots_get_min */
682 682 goto release;
683 683 minrevallphases = MIN(minrevallphases, minrevphase);
684 684 }
685 685 /* Propagate the phase information from the roots to the revs */
686 686 if (minrevallphases != -1) {
687 687 int parents[2];
688 688 for (i = minrevallphases; i < len; i++) {
689 689 if (index_get_parents(self, i, parents,
690 690 (int)len - 1) < 0)
691 691 goto release;
692 692 set_phase_from_parents(phases, parents[0], parents[1], i);
693 693 }
694 694 }
695 695 /* Transform phase list to a python list */
696 696 phasessize = PyInt_FromLong(len);
697 697 if (phasessize == NULL)
698 698 goto release;
699 699 for (i = 0; i < len; i++) {
700 700 phase = phases[i];
701 701 /* We only store the sets of phase for non public phase, the public phase
702 702 * is computed as a difference */
703 703 if (phase != 0) {
704 704 phaseset = PyList_GET_ITEM(phasessetlist, phase);
705 705 rev = PyInt_FromLong(i);
706 706 if (rev == NULL)
707 707 goto release;
708 708 PySet_Add(phaseset, rev);
709 709 Py_XDECREF(rev);
710 710 }
711 711 }
712 712 ret = PyTuple_Pack(2, phasessize, phasessetlist);
713 713
714 714 release:
715 715 Py_XDECREF(phasessize);
716 716 Py_XDECREF(phasessetlist);
717 717 done:
718 718 free(phases);
719 719 return ret;
720 720 }
721 721
722 722 static PyObject *index_headrevs(indexObject *self, PyObject *args)
723 723 {
724 724 Py_ssize_t i, j, len;
725 725 char *nothead = NULL;
726 726 PyObject *heads = NULL;
727 727 PyObject *filter = NULL;
728 728 PyObject *filteredrevs = Py_None;
729 729
730 730 if (!PyArg_ParseTuple(args, "|O", &filteredrevs)) {
731 731 return NULL;
732 732 }
733 733
734 734 if (self->headrevs && filteredrevs == self->filteredrevs)
735 735 return list_copy(self->headrevs);
736 736
737 737 Py_DECREF(self->filteredrevs);
738 738 self->filteredrevs = filteredrevs;
739 739 Py_INCREF(filteredrevs);
740 740
741 741 if (filteredrevs != Py_None) {
742 742 filter = PyObject_GetAttrString(filteredrevs, "__contains__");
743 743 if (!filter) {
744 744 PyErr_SetString(PyExc_TypeError,
745 745 "filteredrevs has no attribute __contains__");
746 746 goto bail;
747 747 }
748 748 }
749 749
750 750 len = index_length(self);
751 751 heads = PyList_New(0);
752 752 if (heads == NULL)
753 753 goto bail;
754 754 if (len == 0) {
755 755 PyObject *nullid = PyInt_FromLong(-1);
756 756 if (nullid == NULL || PyList_Append(heads, nullid) == -1) {
757 757 Py_XDECREF(nullid);
758 758 goto bail;
759 759 }
760 760 goto done;
761 761 }
762 762
763 763 nothead = calloc(len, 1);
764 764 if (nothead == NULL) {
765 765 PyErr_NoMemory();
766 766 goto bail;
767 767 }
768 768
769 769 for (i = len - 1; i >= 0; i--) {
770 770 int isfiltered;
771 771 int parents[2];
772 772
773 773 /* If nothead[i] == 1, it means we've seen an unfiltered child of this
774 774 * node already, and therefore this node is not filtered. So we can skip
775 775 * the expensive check_filter step.
776 776 */
777 777 if (nothead[i] != 1) {
778 778 isfiltered = check_filter(filter, i);
779 779 if (isfiltered == -1) {
780 780 PyErr_SetString(PyExc_TypeError,
781 781 "unable to check filter");
782 782 goto bail;
783 783 }
784 784
785 785 if (isfiltered) {
786 786 nothead[i] = 1;
787 787 continue;
788 788 }
789 789 }
790 790
791 791 if (index_get_parents(self, i, parents, (int)len - 1) < 0)
792 792 goto bail;
793 793 for (j = 0; j < 2; j++) {
794 794 if (parents[j] >= 0)
795 795 nothead[parents[j]] = 1;
796 796 }
797 797 }
798 798
799 799 for (i = 0; i < len; i++) {
800 800 PyObject *head;
801 801
802 802 if (nothead[i])
803 803 continue;
804 804 head = PyInt_FromSsize_t(i);
805 805 if (head == NULL || PyList_Append(heads, head) == -1) {
806 806 Py_XDECREF(head);
807 807 goto bail;
808 808 }
809 809 }
810 810
811 811 done:
812 812 self->headrevs = heads;
813 813 Py_XDECREF(filter);
814 814 free(nothead);
815 815 return list_copy(self->headrevs);
816 816 bail:
817 817 Py_XDECREF(filter);
818 818 Py_XDECREF(heads);
819 819 free(nothead);
820 820 return NULL;
821 821 }
822 822
823 823 /**
824 824 * Obtain the base revision index entry.
825 825 *
826 826 * Callers must ensure that rev >= 0 or illegal memory access may occur.
827 827 */
828 828 static inline int index_baserev(indexObject *self, int rev)
829 829 {
830 830 const char *data;
831 831
832 832 if (rev >= self->length - 1) {
833 833 PyObject *tuple = PyList_GET_ITEM(self->added,
834 834 rev - self->length + 1);
835 835 return (int)PyInt_AS_LONG(PyTuple_GET_ITEM(tuple, 3));
836 836 }
837 837 else {
838 838 data = index_deref(self, rev);
839 839 if (data == NULL) {
840 840 return -2;
841 841 }
842 842
843 843 return getbe32(data + 16);
844 844 }
845 845 }
846 846
847 847 static PyObject *index_deltachain(indexObject *self, PyObject *args)
848 848 {
849 849 int rev, generaldelta;
850 850 PyObject *stoparg;
851 851 int stoprev, iterrev, baserev = -1;
852 852 int stopped;
853 853 PyObject *chain = NULL, *result = NULL;
854 854 const Py_ssize_t length = index_length(self);
855 855
856 856 if (!PyArg_ParseTuple(args, "iOi", &rev, &stoparg, &generaldelta)) {
857 857 return NULL;
858 858 }
859 859
860 860 if (PyInt_Check(stoparg)) {
861 861 stoprev = (int)PyInt_AsLong(stoparg);
862 862 if (stoprev == -1 && PyErr_Occurred()) {
863 863 return NULL;
864 864 }
865 865 }
866 866 else if (stoparg == Py_None) {
867 867 stoprev = -2;
868 868 }
869 869 else {
870 870 PyErr_SetString(PyExc_ValueError,
871 871 "stoprev must be integer or None");
872 872 return NULL;
873 873 }
874 874
875 875 if (rev < 0 || rev >= length) {
876 876 PyErr_SetString(PyExc_ValueError, "revlog index out of range");
877 877 return NULL;
878 878 }
879 879
880 880 chain = PyList_New(0);
881 881 if (chain == NULL) {
882 882 return NULL;
883 883 }
884 884
885 885 baserev = index_baserev(self, rev);
886 886
887 887 /* This should never happen. */
888 888 if (baserev <= -2) {
889 889 /* Error should be set by index_deref() */
890 890 assert(PyErr_Occurred());
891 891 goto bail;
892 892 }
893 893
894 894 iterrev = rev;
895 895
896 896 while (iterrev != baserev && iterrev != stoprev) {
897 897 PyObject *value = PyInt_FromLong(iterrev);
898 898 if (value == NULL) {
899 899 goto bail;
900 900 }
901 901 if (PyList_Append(chain, value)) {
902 902 Py_DECREF(value);
903 903 goto bail;
904 904 }
905 905 Py_DECREF(value);
906 906
907 907 if (generaldelta) {
908 908 iterrev = baserev;
909 909 }
910 910 else {
911 911 iterrev--;
912 912 }
913 913
914 914 if (iterrev < 0) {
915 915 break;
916 916 }
917 917
918 918 if (iterrev >= length) {
919 919 PyErr_SetString(PyExc_IndexError, "revision outside index");
920 920 return NULL;
921 921 }
922 922
923 923 baserev = index_baserev(self, iterrev);
924 924
925 925 /* This should never happen. */
926 926 if (baserev <= -2) {
927 927 /* Error should be set by index_deref() */
928 928 assert(PyErr_Occurred());
929 929 goto bail;
930 930 }
931 931 }
932 932
933 933 if (iterrev == stoprev) {
934 934 stopped = 1;
935 935 }
936 936 else {
937 937 PyObject *value = PyInt_FromLong(iterrev);
938 938 if (value == NULL) {
939 939 goto bail;
940 940 }
941 941 if (PyList_Append(chain, value)) {
942 942 Py_DECREF(value);
943 943 goto bail;
944 944 }
945 945 Py_DECREF(value);
946 946
947 947 stopped = 0;
948 948 }
949 949
950 950 if (PyList_Reverse(chain)) {
951 951 goto bail;
952 952 }
953 953
954 954 result = Py_BuildValue("OO", chain, stopped ? Py_True : Py_False);
955 955 Py_DECREF(chain);
956 956 return result;
957 957
958 958 bail:
959 959 Py_DECREF(chain);
960 960 return NULL;
961 961 }
962 962
963 963 static inline int nt_level(const char *node, Py_ssize_t level)
964 964 {
965 965 int v = node[level>>1];
966 966 if (!(level & 1))
967 967 v >>= 4;
968 968 return v & 0xf;
969 969 }
970 970
971 971 /*
972 972 * Return values:
973 973 *
974 974 * -4: match is ambiguous (multiple candidates)
975 975 * -2: not found
976 976 * rest: valid rev
977 977 */
978 978 static int nt_find(indexObject *self, const char *node, Py_ssize_t nodelen,
979 979 int hex)
980 980 {
981 981 int (*getnybble)(const char *, Py_ssize_t) = hex ? hexdigit : nt_level;
982 982 int level, maxlevel, off;
983 983
984 984 if (nodelen == 20 && node[0] == '\0' && memcmp(node, nullid, 20) == 0)
985 985 return -1;
986 986
987 987 if (hex)
988 988 maxlevel = nodelen > 40 ? 40 : (int)nodelen;
989 989 else
990 990 maxlevel = nodelen > 20 ? 40 : ((int)nodelen * 2);
991 991
992 992 for (level = off = 0; level < maxlevel; level++) {
993 993 int k = getnybble(node, level);
994 994 nodetreenode *n = &self->nt->nodes[off];
995 995 int v = n->children[k];
996 996
997 997 if (v < 0) {
998 998 const char *n;
999 999 Py_ssize_t i;
1000 1000
1001 1001 v = -(v + 2);
1002 1002 n = index_node(self, v);
1003 1003 if (n == NULL)
1004 1004 return -2;
1005 1005 for (i = level; i < maxlevel; i++)
1006 1006 if (getnybble(node, i) != nt_level(n, i))
1007 1007 return -2;
1008 1008 return v;
1009 1009 }
1010 1010 if (v == 0)
1011 1011 return -2;
1012 1012 off = v;
1013 1013 }
1014 1014 /* multiple matches against an ambiguous prefix */
1015 1015 return -4;
1016 1016 }
1017 1017
1018 static int nt_new(indexObject *self)
1018 static int nt_new(nodetree *self)
1019 1019 {
1020 nodetree *nt = self->nt;
1021 if (nt->length == nt->capacity) {
1022 if (nt->capacity >= INT_MAX / (sizeof(nodetreenode) * 2)) {
1020 if (self->length == self->capacity) {
1021 if (self->capacity >= INT_MAX / (sizeof(nodetreenode) * 2)) {
1023 1022 PyErr_SetString(PyExc_MemoryError,
1024 1023 "overflow in nt_new");
1025 1024 return -1;
1026 1025 }
1027 nt->capacity *= 2;
1028 nt->nodes = realloc(nt->nodes,
1029 nt->capacity * sizeof(nodetreenode));
1030 if (nt->nodes == NULL) {
1026 self->capacity *= 2;
1027 self->nodes = realloc(self->nodes,
1028 self->capacity * sizeof(nodetreenode));
1029 if (self->nodes == NULL) {
1031 1030 PyErr_SetString(PyExc_MemoryError, "out of memory");
1032 1031 return -1;
1033 1032 }
1034 memset(&nt->nodes[nt->length], 0,
1035 sizeof(nodetreenode) * (nt->capacity - nt->length));
1033 memset(&self->nodes[self->length], 0,
1034 sizeof(nodetreenode) * (self->capacity - self->length));
1036 1035 }
1037 return nt->length++;
1036 return self->length++;
1038 1037 }
1039 1038
1040 1039 static int nt_insert(indexObject *self, const char *node, int rev)
1041 1040 {
1042 1041 int level = 0;
1043 1042 int off = 0;
1044 1043
1045 1044 while (level < 40) {
1046 1045 int k = nt_level(node, level);
1047 1046 nodetreenode *n;
1048 1047 int v;
1049 1048
1050 1049 n = &self->nt->nodes[off];
1051 1050 v = n->children[k];
1052 1051
1053 1052 if (v == 0) {
1054 1053 n->children[k] = -rev - 2;
1055 1054 return 0;
1056 1055 }
1057 1056 if (v < 0) {
1058 1057 const char *oldnode = index_node_existing(self, -(v + 2));
1059 1058 int noff;
1060 1059
1061 1060 if (oldnode == NULL)
1062 1061 return -1;
1063 1062 if (!memcmp(oldnode, node, 20)) {
1064 1063 n->children[k] = -rev - 2;
1065 1064 return 0;
1066 1065 }
1067 noff = nt_new(self);
1066 noff = nt_new(self->nt);
1068 1067 if (noff == -1)
1069 1068 return -1;
1070 1069 /* self->nt->nodes may have been changed by realloc */
1071 1070 self->nt->nodes[off].children[k] = noff;
1072 1071 off = noff;
1073 1072 n = &self->nt->nodes[off];
1074 1073 n->children[nt_level(oldnode, ++level)] = v;
1075 1074 if (level > self->nt->depth)
1076 1075 self->nt->depth = level;
1077 1076 self->nt->splits += 1;
1078 1077 } else {
1079 1078 level += 1;
1080 1079 off = v;
1081 1080 }
1082 1081 }
1083 1082
1084 1083 return -1;
1085 1084 }
1086 1085
1087 1086 static int nt_delete_node(indexObject *self, const char *node)
1088 1087 {
1089 1088 /* rev==-2 happens to get encoded as 0, which is interpreted as not set */
1090 1089 return nt_insert(self, node, -2);
1091 1090 }
1092 1091
1093 1092 static int nt_init(indexObject *self)
1094 1093 {
1095 1094 if (self->nt == NULL) {
1096 1095 self->nt = PyMem_Malloc(sizeof(nodetree));
1097 1096 if (self->nt == NULL) {
1098 1097 PyErr_NoMemory();
1099 1098 return -1;
1100 1099 }
1101 1100 if ((size_t)self->raw_length > INT_MAX / sizeof(nodetreenode)) {
1102 1101 PyErr_SetString(PyExc_ValueError, "overflow in nt_init");
1103 1102 return -1;
1104 1103 }
1105 1104 self->nt->capacity = self->raw_length < 4
1106 1105 ? 4 : (int)self->raw_length / 2;
1107 1106
1108 1107 self->nt->nodes = calloc(self->nt->capacity, sizeof(nodetreenode));
1109 1108 if (self->nt->nodes == NULL) {
1110 1109 free(self->nt);
1111 1110 self->nt = NULL;
1112 1111 PyErr_NoMemory();
1113 1112 return -1;
1114 1113 }
1115 1114 self->ntrev = (int)index_length(self);
1116 1115 self->ntlookups = 1;
1117 1116 self->ntmisses = 0;
1118 1117 self->nt->depth = 0;
1119 1118 self->nt->splits = 0;
1120 1119 self->nt->length = 1;
1121 1120 if (nt_insert(self, nullid, -1) == -1) {
1122 1121 free(self->nt->nodes);
1123 1122 free(self->nt);
1124 1123 self->nt = NULL;
1125 1124 return -1;
1126 1125 }
1127 1126 }
1128 1127 return 0;
1129 1128 }
1130 1129
1131 1130 /*
1132 1131 * Return values:
1133 1132 *
1134 1133 * -3: error (exception set)
1135 1134 * -2: not found (no exception set)
1136 1135 * rest: valid rev
1137 1136 */
1138 1137 static int index_find_node(indexObject *self,
1139 1138 const char *node, Py_ssize_t nodelen)
1140 1139 {
1141 1140 int rev;
1142 1141
1143 1142 if (nt_init(self) == -1)
1144 1143 return -3;
1145 1144
1146 1145 self->ntlookups++;
1147 1146 rev = nt_find(self, node, nodelen, 0);
1148 1147 if (rev >= -1)
1149 1148 return rev;
1150 1149
1151 1150 /*
1152 1151 * For the first handful of lookups, we scan the entire index,
1153 1152 * and cache only the matching nodes. This optimizes for cases
1154 1153 * like "hg tip", where only a few nodes are accessed.
1155 1154 *
1156 1155 * After that, we cache every node we visit, using a single
1157 1156 * scan amortized over multiple lookups. This gives the best
1158 1157 * bulk performance, e.g. for "hg log".
1159 1158 */
1160 1159 if (self->ntmisses++ < 4) {
1161 1160 for (rev = self->ntrev - 1; rev >= 0; rev--) {
1162 1161 const char *n = index_node_existing(self, rev);
1163 1162 if (n == NULL)
1164 1163 return -3;
1165 1164 if (memcmp(node, n, nodelen > 20 ? 20 : nodelen) == 0) {
1166 1165 if (nt_insert(self, n, rev) == -1)
1167 1166 return -3;
1168 1167 break;
1169 1168 }
1170 1169 }
1171 1170 } else {
1172 1171 for (rev = self->ntrev - 1; rev >= 0; rev--) {
1173 1172 const char *n = index_node_existing(self, rev);
1174 1173 if (n == NULL)
1175 1174 return -3;
1176 1175 if (nt_insert(self, n, rev) == -1) {
1177 1176 self->ntrev = rev + 1;
1178 1177 return -3;
1179 1178 }
1180 1179 if (memcmp(node, n, nodelen > 20 ? 20 : nodelen) == 0) {
1181 1180 break;
1182 1181 }
1183 1182 }
1184 1183 self->ntrev = rev;
1185 1184 }
1186 1185
1187 1186 if (rev >= 0)
1188 1187 return rev;
1189 1188 return -2;
1190 1189 }
1191 1190
1192 1191 static void raise_revlog_error(void)
1193 1192 {
1194 1193 PyObject *mod = NULL, *dict = NULL, *errclass = NULL;
1195 1194
1196 1195 mod = PyImport_ImportModule("mercurial.error");
1197 1196 if (mod == NULL) {
1198 1197 goto cleanup;
1199 1198 }
1200 1199
1201 1200 dict = PyModule_GetDict(mod);
1202 1201 if (dict == NULL) {
1203 1202 goto cleanup;
1204 1203 }
1205 1204 Py_INCREF(dict);
1206 1205
1207 1206 errclass = PyDict_GetItemString(dict, "RevlogError");
1208 1207 if (errclass == NULL) {
1209 1208 PyErr_SetString(PyExc_SystemError,
1210 1209 "could not find RevlogError");
1211 1210 goto cleanup;
1212 1211 }
1213 1212
1214 1213 /* value of exception is ignored by callers */
1215 1214 PyErr_SetString(errclass, "RevlogError");
1216 1215
1217 1216 cleanup:
1218 1217 Py_XDECREF(dict);
1219 1218 Py_XDECREF(mod);
1220 1219 }
1221 1220
1222 1221 static PyObject *index_getitem(indexObject *self, PyObject *value)
1223 1222 {
1224 1223 char *node;
1225 1224 int rev;
1226 1225
1227 1226 if (PyInt_Check(value))
1228 1227 return index_get(self, PyInt_AS_LONG(value));
1229 1228
1230 1229 if (node_check(value, &node) == -1)
1231 1230 return NULL;
1232 1231 rev = index_find_node(self, node, 20);
1233 1232 if (rev >= -1)
1234 1233 return PyInt_FromLong(rev);
1235 1234 if (rev == -2)
1236 1235 raise_revlog_error();
1237 1236 return NULL;
1238 1237 }
1239 1238
1240 1239 /*
1241 1240 * Fully populate the radix tree.
1242 1241 */
1243 1242 static int nt_populate(indexObject *self) {
1244 1243 int rev;
1245 1244 if (self->ntrev > 0) {
1246 1245 for (rev = self->ntrev - 1; rev >= 0; rev--) {
1247 1246 const char *n = index_node_existing(self, rev);
1248 1247 if (n == NULL)
1249 1248 return -1;
1250 1249 if (nt_insert(self, n, rev) == -1)
1251 1250 return -1;
1252 1251 }
1253 1252 self->ntrev = -1;
1254 1253 }
1255 1254 return 0;
1256 1255 }
1257 1256
1258 1257 static int nt_partialmatch(indexObject *self, const char *node,
1259 1258 Py_ssize_t nodelen)
1260 1259 {
1261 1260 return nt_find(self, node, nodelen, 1);
1262 1261 }
1263 1262
1264 1263 /*
1265 1264 * Find the length of the shortest unique prefix of node.
1266 1265 *
1267 1266 * Return values:
1268 1267 *
1269 1268 * -3: error (exception set)
1270 1269 * -2: not found (no exception set)
1271 1270 * rest: length of shortest prefix
1272 1271 */
1273 1272 static int nt_shortest(indexObject *self, const char *node)
1274 1273 {
1275 1274 int level, off;
1276 1275
1277 1276 for (level = off = 0; level < 40; level++) {
1278 1277 int k, v;
1279 1278 nodetreenode *n = &self->nt->nodes[off];
1280 1279 k = nt_level(node, level);
1281 1280 v = n->children[k];
1282 1281 if (v < 0) {
1283 1282 const char *n;
1284 1283 v = -(v + 2);
1285 1284 n = index_node_existing(self, v);
1286 1285 if (n == NULL)
1287 1286 return -3;
1288 1287 if (memcmp(node, n, 20) != 0)
1289 1288 /*
1290 1289 * Found a unique prefix, but it wasn't for the
1291 1290 * requested node (i.e the requested node does
1292 1291 * not exist).
1293 1292 */
1294 1293 return -2;
1295 1294 return level + 1;
1296 1295 }
1297 1296 if (v == 0)
1298 1297 return -2;
1299 1298 off = v;
1300 1299 }
1301 1300 /*
1302 1301 * The node was still not unique after 40 hex digits, so this won't
1303 1302 * happen. Also, if we get here, then there's a programming error in
1304 1303 * this file that made us insert a node longer than 40 hex digits.
1305 1304 */
1306 1305 PyErr_SetString(PyExc_Exception, "broken node tree");
1307 1306 return -3;
1308 1307 }
1309 1308
1310 1309 static PyObject *index_partialmatch(indexObject *self, PyObject *args)
1311 1310 {
1312 1311 const char *fullnode;
1313 1312 int nodelen;
1314 1313 char *node;
1315 1314 int rev, i;
1316 1315
1317 1316 if (!PyArg_ParseTuple(args, PY23("s#", "y#"), &node, &nodelen))
1318 1317 return NULL;
1319 1318
1320 1319 if (nodelen < 1) {
1321 1320 PyErr_SetString(PyExc_ValueError, "key too short");
1322 1321 return NULL;
1323 1322 }
1324 1323
1325 1324 if (nodelen > 40) {
1326 1325 PyErr_SetString(PyExc_ValueError, "key too long");
1327 1326 return NULL;
1328 1327 }
1329 1328
1330 1329 for (i = 0; i < nodelen; i++)
1331 1330 hexdigit(node, i);
1332 1331 if (PyErr_Occurred()) {
1333 1332 /* input contains non-hex characters */
1334 1333 PyErr_Clear();
1335 1334 Py_RETURN_NONE;
1336 1335 }
1337 1336
1338 1337 if (nt_init(self) == -1)
1339 1338 return NULL;
1340 1339 if (nt_populate(self) == -1)
1341 1340 return NULL;
1342 1341 rev = nt_partialmatch(self, node, nodelen);
1343 1342
1344 1343 switch (rev) {
1345 1344 case -4:
1346 1345 raise_revlog_error();
1347 1346 return NULL;
1348 1347 case -2:
1349 1348 Py_RETURN_NONE;
1350 1349 case -1:
1351 1350 return PyBytes_FromStringAndSize(nullid, 20);
1352 1351 }
1353 1352
1354 1353 fullnode = index_node_existing(self, rev);
1355 1354 if (fullnode == NULL) {
1356 1355 return NULL;
1357 1356 }
1358 1357 return PyBytes_FromStringAndSize(fullnode, 20);
1359 1358 }
1360 1359
1361 1360 static PyObject *index_shortest(indexObject *self, PyObject *args)
1362 1361 {
1363 1362 PyObject *val;
1364 1363 char *node;
1365 1364 int length;
1366 1365
1367 1366 if (!PyArg_ParseTuple(args, "O", &val))
1368 1367 return NULL;
1369 1368 if (node_check(val, &node) == -1)
1370 1369 return NULL;
1371 1370
1372 1371 self->ntlookups++;
1373 1372 if (nt_init(self) == -1)
1374 1373 return NULL;
1375 1374 if (nt_populate(self) == -1)
1376 1375 return NULL;
1377 1376 length = nt_shortest(self, node);
1378 1377 if (length == -3)
1379 1378 return NULL;
1380 1379 if (length == -2) {
1381 1380 raise_revlog_error();
1382 1381 return NULL;
1383 1382 }
1384 1383 return PyInt_FromLong(length);
1385 1384 }
1386 1385
1387 1386 static PyObject *index_m_get(indexObject *self, PyObject *args)
1388 1387 {
1389 1388 PyObject *val;
1390 1389 char *node;
1391 1390 int rev;
1392 1391
1393 1392 if (!PyArg_ParseTuple(args, "O", &val))
1394 1393 return NULL;
1395 1394 if (node_check(val, &node) == -1)
1396 1395 return NULL;
1397 1396 rev = index_find_node(self, node, 20);
1398 1397 if (rev == -3)
1399 1398 return NULL;
1400 1399 if (rev == -2)
1401 1400 Py_RETURN_NONE;
1402 1401 return PyInt_FromLong(rev);
1403 1402 }
1404 1403
1405 1404 static int index_contains(indexObject *self, PyObject *value)
1406 1405 {
1407 1406 char *node;
1408 1407
1409 1408 if (PyInt_Check(value)) {
1410 1409 long rev = PyInt_AS_LONG(value);
1411 1410 return rev >= -1 && rev < index_length(self);
1412 1411 }
1413 1412
1414 1413 if (node_check(value, &node) == -1)
1415 1414 return -1;
1416 1415
1417 1416 switch (index_find_node(self, node, 20)) {
1418 1417 case -3:
1419 1418 return -1;
1420 1419 case -2:
1421 1420 return 0;
1422 1421 default:
1423 1422 return 1;
1424 1423 }
1425 1424 }
1426 1425
1427 1426 typedef uint64_t bitmask;
1428 1427
1429 1428 /*
1430 1429 * Given a disjoint set of revs, return all candidates for the
1431 1430 * greatest common ancestor. In revset notation, this is the set
1432 1431 * "heads(::a and ::b and ...)"
1433 1432 */
1434 1433 static PyObject *find_gca_candidates(indexObject *self, const int *revs,
1435 1434 int revcount)
1436 1435 {
1437 1436 const bitmask allseen = (1ull << revcount) - 1;
1438 1437 const bitmask poison = 1ull << revcount;
1439 1438 PyObject *gca = PyList_New(0);
1440 1439 int i, v, interesting;
1441 1440 int maxrev = -1;
1442 1441 bitmask sp;
1443 1442 bitmask *seen;
1444 1443
1445 1444 if (gca == NULL)
1446 1445 return PyErr_NoMemory();
1447 1446
1448 1447 for (i = 0; i < revcount; i++) {
1449 1448 if (revs[i] > maxrev)
1450 1449 maxrev = revs[i];
1451 1450 }
1452 1451
1453 1452 seen = calloc(sizeof(*seen), maxrev + 1);
1454 1453 if (seen == NULL) {
1455 1454 Py_DECREF(gca);
1456 1455 return PyErr_NoMemory();
1457 1456 }
1458 1457
1459 1458 for (i = 0; i < revcount; i++)
1460 1459 seen[revs[i]] = 1ull << i;
1461 1460
1462 1461 interesting = revcount;
1463 1462
1464 1463 for (v = maxrev; v >= 0 && interesting; v--) {
1465 1464 bitmask sv = seen[v];
1466 1465 int parents[2];
1467 1466
1468 1467 if (!sv)
1469 1468 continue;
1470 1469
1471 1470 if (sv < poison) {
1472 1471 interesting -= 1;
1473 1472 if (sv == allseen) {
1474 1473 PyObject *obj = PyInt_FromLong(v);
1475 1474 if (obj == NULL)
1476 1475 goto bail;
1477 1476 if (PyList_Append(gca, obj) == -1) {
1478 1477 Py_DECREF(obj);
1479 1478 goto bail;
1480 1479 }
1481 1480 sv |= poison;
1482 1481 for (i = 0; i < revcount; i++) {
1483 1482 if (revs[i] == v)
1484 1483 goto done;
1485 1484 }
1486 1485 }
1487 1486 }
1488 1487 if (index_get_parents(self, v, parents, maxrev) < 0)
1489 1488 goto bail;
1490 1489
1491 1490 for (i = 0; i < 2; i++) {
1492 1491 int p = parents[i];
1493 1492 if (p == -1)
1494 1493 continue;
1495 1494 sp = seen[p];
1496 1495 if (sv < poison) {
1497 1496 if (sp == 0) {
1498 1497 seen[p] = sv;
1499 1498 interesting++;
1500 1499 }
1501 1500 else if (sp != sv)
1502 1501 seen[p] |= sv;
1503 1502 } else {
1504 1503 if (sp && sp < poison)
1505 1504 interesting--;
1506 1505 seen[p] = sv;
1507 1506 }
1508 1507 }
1509 1508 }
1510 1509
1511 1510 done:
1512 1511 free(seen);
1513 1512 return gca;
1514 1513 bail:
1515 1514 free(seen);
1516 1515 Py_XDECREF(gca);
1517 1516 return NULL;
1518 1517 }
1519 1518
1520 1519 /*
1521 1520 * Given a disjoint set of revs, return the subset with the longest
1522 1521 * path to the root.
1523 1522 */
1524 1523 static PyObject *find_deepest(indexObject *self, PyObject *revs)
1525 1524 {
1526 1525 const Py_ssize_t revcount = PyList_GET_SIZE(revs);
1527 1526 static const Py_ssize_t capacity = 24;
1528 1527 int *depth, *interesting = NULL;
1529 1528 int i, j, v, ninteresting;
1530 1529 PyObject *dict = NULL, *keys = NULL;
1531 1530 long *seen = NULL;
1532 1531 int maxrev = -1;
1533 1532 long final;
1534 1533
1535 1534 if (revcount > capacity) {
1536 1535 PyErr_Format(PyExc_OverflowError,
1537 1536 "bitset size (%ld) > capacity (%ld)",
1538 1537 (long)revcount, (long)capacity);
1539 1538 return NULL;
1540 1539 }
1541 1540
1542 1541 for (i = 0; i < revcount; i++) {
1543 1542 int n = (int)PyInt_AsLong(PyList_GET_ITEM(revs, i));
1544 1543 if (n > maxrev)
1545 1544 maxrev = n;
1546 1545 }
1547 1546
1548 1547 depth = calloc(sizeof(*depth), maxrev + 1);
1549 1548 if (depth == NULL)
1550 1549 return PyErr_NoMemory();
1551 1550
1552 1551 seen = calloc(sizeof(*seen), maxrev + 1);
1553 1552 if (seen == NULL) {
1554 1553 PyErr_NoMemory();
1555 1554 goto bail;
1556 1555 }
1557 1556
1558 1557 interesting = calloc(sizeof(*interesting), 1 << revcount);
1559 1558 if (interesting == NULL) {
1560 1559 PyErr_NoMemory();
1561 1560 goto bail;
1562 1561 }
1563 1562
1564 1563 if (PyList_Sort(revs) == -1)
1565 1564 goto bail;
1566 1565
1567 1566 for (i = 0; i < revcount; i++) {
1568 1567 int n = (int)PyInt_AsLong(PyList_GET_ITEM(revs, i));
1569 1568 long b = 1l << i;
1570 1569 depth[n] = 1;
1571 1570 seen[n] = b;
1572 1571 interesting[b] = 1;
1573 1572 }
1574 1573
1575 1574 /* invariant: ninteresting is the number of non-zero entries in
1576 1575 * interesting. */
1577 1576 ninteresting = (int)revcount;
1578 1577
1579 1578 for (v = maxrev; v >= 0 && ninteresting > 1; v--) {
1580 1579 int dv = depth[v];
1581 1580 int parents[2];
1582 1581 long sv;
1583 1582
1584 1583 if (dv == 0)
1585 1584 continue;
1586 1585
1587 1586 sv = seen[v];
1588 1587 if (index_get_parents(self, v, parents, maxrev) < 0)
1589 1588 goto bail;
1590 1589
1591 1590 for (i = 0; i < 2; i++) {
1592 1591 int p = parents[i];
1593 1592 long sp;
1594 1593 int dp;
1595 1594
1596 1595 if (p == -1)
1597 1596 continue;
1598 1597
1599 1598 dp = depth[p];
1600 1599 sp = seen[p];
1601 1600 if (dp <= dv) {
1602 1601 depth[p] = dv + 1;
1603 1602 if (sp != sv) {
1604 1603 interesting[sv] += 1;
1605 1604 seen[p] = sv;
1606 1605 if (sp) {
1607 1606 interesting[sp] -= 1;
1608 1607 if (interesting[sp] == 0)
1609 1608 ninteresting -= 1;
1610 1609 }
1611 1610 }
1612 1611 }
1613 1612 else if (dv == dp - 1) {
1614 1613 long nsp = sp | sv;
1615 1614 if (nsp == sp)
1616 1615 continue;
1617 1616 seen[p] = nsp;
1618 1617 interesting[sp] -= 1;
1619 1618 if (interesting[sp] == 0)
1620 1619 ninteresting -= 1;
1621 1620 if (interesting[nsp] == 0)
1622 1621 ninteresting += 1;
1623 1622 interesting[nsp] += 1;
1624 1623 }
1625 1624 }
1626 1625 interesting[sv] -= 1;
1627 1626 if (interesting[sv] == 0)
1628 1627 ninteresting -= 1;
1629 1628 }
1630 1629
1631 1630 final = 0;
1632 1631 j = ninteresting;
1633 1632 for (i = 0; i < (int)(2 << revcount) && j > 0; i++) {
1634 1633 if (interesting[i] == 0)
1635 1634 continue;
1636 1635 final |= i;
1637 1636 j -= 1;
1638 1637 }
1639 1638 if (final == 0) {
1640 1639 keys = PyList_New(0);
1641 1640 goto bail;
1642 1641 }
1643 1642
1644 1643 dict = PyDict_New();
1645 1644 if (dict == NULL)
1646 1645 goto bail;
1647 1646
1648 1647 for (i = 0; i < revcount; i++) {
1649 1648 PyObject *key;
1650 1649
1651 1650 if ((final & (1 << i)) == 0)
1652 1651 continue;
1653 1652
1654 1653 key = PyList_GET_ITEM(revs, i);
1655 1654 Py_INCREF(key);
1656 1655 Py_INCREF(Py_None);
1657 1656 if (PyDict_SetItem(dict, key, Py_None) == -1) {
1658 1657 Py_DECREF(key);
1659 1658 Py_DECREF(Py_None);
1660 1659 goto bail;
1661 1660 }
1662 1661 }
1663 1662
1664 1663 keys = PyDict_Keys(dict);
1665 1664
1666 1665 bail:
1667 1666 free(depth);
1668 1667 free(seen);
1669 1668 free(interesting);
1670 1669 Py_XDECREF(dict);
1671 1670
1672 1671 return keys;
1673 1672 }
1674 1673
1675 1674 /*
1676 1675 * Given a (possibly overlapping) set of revs, return all the
1677 1676 * common ancestors heads: heads(::args[0] and ::a[1] and ...)
1678 1677 */
1679 1678 static PyObject *index_commonancestorsheads(indexObject *self, PyObject *args)
1680 1679 {
1681 1680 PyObject *ret = NULL;
1682 1681 Py_ssize_t argcount, i, len;
1683 1682 bitmask repeat = 0;
1684 1683 int revcount = 0;
1685 1684 int *revs;
1686 1685
1687 1686 argcount = PySequence_Length(args);
1688 1687 revs = PyMem_Malloc(argcount * sizeof(*revs));
1689 1688 if (argcount > 0 && revs == NULL)
1690 1689 return PyErr_NoMemory();
1691 1690 len = index_length(self);
1692 1691
1693 1692 for (i = 0; i < argcount; i++) {
1694 1693 static const int capacity = 24;
1695 1694 PyObject *obj = PySequence_GetItem(args, i);
1696 1695 bitmask x;
1697 1696 long val;
1698 1697
1699 1698 if (!PyInt_Check(obj)) {
1700 1699 PyErr_SetString(PyExc_TypeError,
1701 1700 "arguments must all be ints");
1702 1701 Py_DECREF(obj);
1703 1702 goto bail;
1704 1703 }
1705 1704 val = PyInt_AsLong(obj);
1706 1705 Py_DECREF(obj);
1707 1706 if (val == -1) {
1708 1707 ret = PyList_New(0);
1709 1708 goto done;
1710 1709 }
1711 1710 if (val < 0 || val >= len) {
1712 1711 PyErr_SetString(PyExc_IndexError,
1713 1712 "index out of range");
1714 1713 goto bail;
1715 1714 }
1716 1715 /* this cheesy bloom filter lets us avoid some more
1717 1716 * expensive duplicate checks in the common set-is-disjoint
1718 1717 * case */
1719 1718 x = 1ull << (val & 0x3f);
1720 1719 if (repeat & x) {
1721 1720 int k;
1722 1721 for (k = 0; k < revcount; k++) {
1723 1722 if (val == revs[k])
1724 1723 goto duplicate;
1725 1724 }
1726 1725 }
1727 1726 else repeat |= x;
1728 1727 if (revcount >= capacity) {
1729 1728 PyErr_Format(PyExc_OverflowError,
1730 1729 "bitset size (%d) > capacity (%d)",
1731 1730 revcount, capacity);
1732 1731 goto bail;
1733 1732 }
1734 1733 revs[revcount++] = (int)val;
1735 1734 duplicate:;
1736 1735 }
1737 1736
1738 1737 if (revcount == 0) {
1739 1738 ret = PyList_New(0);
1740 1739 goto done;
1741 1740 }
1742 1741 if (revcount == 1) {
1743 1742 PyObject *obj;
1744 1743 ret = PyList_New(1);
1745 1744 if (ret == NULL)
1746 1745 goto bail;
1747 1746 obj = PyInt_FromLong(revs[0]);
1748 1747 if (obj == NULL)
1749 1748 goto bail;
1750 1749 PyList_SET_ITEM(ret, 0, obj);
1751 1750 goto done;
1752 1751 }
1753 1752
1754 1753 ret = find_gca_candidates(self, revs, revcount);
1755 1754 if (ret == NULL)
1756 1755 goto bail;
1757 1756
1758 1757 done:
1759 1758 PyMem_Free(revs);
1760 1759 return ret;
1761 1760
1762 1761 bail:
1763 1762 PyMem_Free(revs);
1764 1763 Py_XDECREF(ret);
1765 1764 return NULL;
1766 1765 }
1767 1766
1768 1767 /*
1769 1768 * Given a (possibly overlapping) set of revs, return the greatest
1770 1769 * common ancestors: those with the longest path to the root.
1771 1770 */
1772 1771 static PyObject *index_ancestors(indexObject *self, PyObject *args)
1773 1772 {
1774 1773 PyObject *ret;
1775 1774 PyObject *gca = index_commonancestorsheads(self, args);
1776 1775 if (gca == NULL)
1777 1776 return NULL;
1778 1777
1779 1778 if (PyList_GET_SIZE(gca) <= 1) {
1780 1779 return gca;
1781 1780 }
1782 1781
1783 1782 ret = find_deepest(self, gca);
1784 1783 Py_DECREF(gca);
1785 1784 return ret;
1786 1785 }
1787 1786
1788 1787 /*
1789 1788 * Invalidate any trie entries introduced by added revs.
1790 1789 */
1791 1790 static void nt_invalidate_added(indexObject *self, Py_ssize_t start)
1792 1791 {
1793 1792 Py_ssize_t i, len = PyList_GET_SIZE(self->added);
1794 1793
1795 1794 for (i = start; i < len; i++) {
1796 1795 PyObject *tuple = PyList_GET_ITEM(self->added, i);
1797 1796 PyObject *node = PyTuple_GET_ITEM(tuple, 7);
1798 1797
1799 1798 nt_delete_node(self, PyBytes_AS_STRING(node));
1800 1799 }
1801 1800
1802 1801 if (start == 0)
1803 1802 Py_CLEAR(self->added);
1804 1803 }
1805 1804
1806 1805 /*
1807 1806 * Delete a numeric range of revs, which must be at the end of the
1808 1807 * range, but exclude the sentinel nullid entry.
1809 1808 */
1810 1809 static int index_slice_del(indexObject *self, PyObject *item)
1811 1810 {
1812 1811 Py_ssize_t start, stop, step, slicelength;
1813 1812 Py_ssize_t length = index_length(self) + 1;
1814 1813 int ret = 0;
1815 1814
1816 1815 /* Argument changed from PySliceObject* to PyObject* in Python 3. */
1817 1816 #ifdef IS_PY3K
1818 1817 if (PySlice_GetIndicesEx(item, length,
1819 1818 #else
1820 1819 if (PySlice_GetIndicesEx((PySliceObject*)item, length,
1821 1820 #endif
1822 1821 &start, &stop, &step, &slicelength) < 0)
1823 1822 return -1;
1824 1823
1825 1824 if (slicelength <= 0)
1826 1825 return 0;
1827 1826
1828 1827 if ((step < 0 && start < stop) || (step > 0 && start > stop))
1829 1828 stop = start;
1830 1829
1831 1830 if (step < 0) {
1832 1831 stop = start + 1;
1833 1832 start = stop + step*(slicelength - 1) - 1;
1834 1833 step = -step;
1835 1834 }
1836 1835
1837 1836 if (step != 1) {
1838 1837 PyErr_SetString(PyExc_ValueError,
1839 1838 "revlog index delete requires step size of 1");
1840 1839 return -1;
1841 1840 }
1842 1841
1843 1842 if (stop != length - 1) {
1844 1843 PyErr_SetString(PyExc_IndexError,
1845 1844 "revlog index deletion indices are invalid");
1846 1845 return -1;
1847 1846 }
1848 1847
1849 1848 if (start < self->length - 1) {
1850 1849 if (self->nt) {
1851 1850 Py_ssize_t i;
1852 1851
1853 1852 for (i = start + 1; i < self->length - 1; i++) {
1854 1853 const char *node = index_node_existing(self, i);
1855 1854 if (node == NULL)
1856 1855 return -1;
1857 1856
1858 1857 nt_delete_node(self, node);
1859 1858 }
1860 1859 if (self->added)
1861 1860 nt_invalidate_added(self, 0);
1862 1861 if (self->ntrev > start)
1863 1862 self->ntrev = (int)start;
1864 1863 }
1865 1864 self->length = start + 1;
1866 1865 if (start < self->raw_length) {
1867 1866 if (self->cache) {
1868 1867 Py_ssize_t i;
1869 1868 for (i = start; i < self->raw_length; i++)
1870 1869 Py_CLEAR(self->cache[i]);
1871 1870 }
1872 1871 self->raw_length = start;
1873 1872 }
1874 1873 goto done;
1875 1874 }
1876 1875
1877 1876 if (self->nt) {
1878 1877 nt_invalidate_added(self, start - self->length + 1);
1879 1878 if (self->ntrev > start)
1880 1879 self->ntrev = (int)start;
1881 1880 }
1882 1881 if (self->added)
1883 1882 ret = PyList_SetSlice(self->added, start - self->length + 1,
1884 1883 PyList_GET_SIZE(self->added), NULL);
1885 1884 done:
1886 1885 Py_CLEAR(self->headrevs);
1887 1886 return ret;
1888 1887 }
1889 1888
1890 1889 /*
1891 1890 * Supported ops:
1892 1891 *
1893 1892 * slice deletion
1894 1893 * string assignment (extend node->rev mapping)
1895 1894 * string deletion (shrink node->rev mapping)
1896 1895 */
1897 1896 static int index_assign_subscript(indexObject *self, PyObject *item,
1898 1897 PyObject *value)
1899 1898 {
1900 1899 char *node;
1901 1900 long rev;
1902 1901
1903 1902 if (PySlice_Check(item) && value == NULL)
1904 1903 return index_slice_del(self, item);
1905 1904
1906 1905 if (node_check(item, &node) == -1)
1907 1906 return -1;
1908 1907
1909 1908 if (value == NULL)
1910 1909 return self->nt ? nt_delete_node(self, node) : 0;
1911 1910 rev = PyInt_AsLong(value);
1912 1911 if (rev > INT_MAX || rev < 0) {
1913 1912 if (!PyErr_Occurred())
1914 1913 PyErr_SetString(PyExc_ValueError, "rev out of range");
1915 1914 return -1;
1916 1915 }
1917 1916
1918 1917 if (nt_init(self) == -1)
1919 1918 return -1;
1920 1919 return nt_insert(self, node, (int)rev);
1921 1920 }
1922 1921
1923 1922 /*
1924 1923 * Find all RevlogNG entries in an index that has inline data. Update
1925 1924 * the optional "offsets" table with those entries.
1926 1925 */
1927 1926 static Py_ssize_t inline_scan(indexObject *self, const char **offsets)
1928 1927 {
1929 1928 const char *data = (const char *)self->buf.buf;
1930 1929 Py_ssize_t pos = 0;
1931 1930 Py_ssize_t end = self->buf.len;
1932 1931 long incr = v1_hdrsize;
1933 1932 Py_ssize_t len = 0;
1934 1933
1935 1934 while (pos + v1_hdrsize <= end && pos >= 0) {
1936 1935 uint32_t comp_len;
1937 1936 /* 3rd element of header is length of compressed inline data */
1938 1937 comp_len = getbe32(data + pos + 8);
1939 1938 incr = v1_hdrsize + comp_len;
1940 1939 if (offsets)
1941 1940 offsets[len] = data + pos;
1942 1941 len++;
1943 1942 pos += incr;
1944 1943 }
1945 1944
1946 1945 if (pos != end) {
1947 1946 if (!PyErr_Occurred())
1948 1947 PyErr_SetString(PyExc_ValueError, "corrupt index file");
1949 1948 return -1;
1950 1949 }
1951 1950
1952 1951 return len;
1953 1952 }
1954 1953
1955 1954 static int index_init(indexObject *self, PyObject *args)
1956 1955 {
1957 1956 PyObject *data_obj, *inlined_obj;
1958 1957 Py_ssize_t size;
1959 1958
1960 1959 /* Initialize before argument-checking to avoid index_dealloc() crash. */
1961 1960 self->raw_length = 0;
1962 1961 self->added = NULL;
1963 1962 self->cache = NULL;
1964 1963 self->data = NULL;
1965 1964 memset(&self->buf, 0, sizeof(self->buf));
1966 1965 self->headrevs = NULL;
1967 1966 self->filteredrevs = Py_None;
1968 1967 Py_INCREF(Py_None);
1969 1968 self->nt = NULL;
1970 1969 self->offsets = NULL;
1971 1970
1972 1971 if (!PyArg_ParseTuple(args, "OO", &data_obj, &inlined_obj))
1973 1972 return -1;
1974 1973 if (!PyObject_CheckBuffer(data_obj)) {
1975 1974 PyErr_SetString(PyExc_TypeError,
1976 1975 "data does not support buffer interface");
1977 1976 return -1;
1978 1977 }
1979 1978
1980 1979 if (PyObject_GetBuffer(data_obj, &self->buf, PyBUF_SIMPLE) == -1)
1981 1980 return -1;
1982 1981 size = self->buf.len;
1983 1982
1984 1983 self->inlined = inlined_obj && PyObject_IsTrue(inlined_obj);
1985 1984 self->data = data_obj;
1986 1985
1987 1986 self->ntlookups = self->ntmisses = 0;
1988 1987 self->ntrev = -1;
1989 1988 Py_INCREF(self->data);
1990 1989
1991 1990 if (self->inlined) {
1992 1991 Py_ssize_t len = inline_scan(self, NULL);
1993 1992 if (len == -1)
1994 1993 goto bail;
1995 1994 self->raw_length = len;
1996 1995 self->length = len + 1;
1997 1996 } else {
1998 1997 if (size % v1_hdrsize) {
1999 1998 PyErr_SetString(PyExc_ValueError, "corrupt index file");
2000 1999 goto bail;
2001 2000 }
2002 2001 self->raw_length = size / v1_hdrsize;
2003 2002 self->length = self->raw_length + 1;
2004 2003 }
2005 2004
2006 2005 return 0;
2007 2006 bail:
2008 2007 return -1;
2009 2008 }
2010 2009
2011 2010 static PyObject *index_nodemap(indexObject *self)
2012 2011 {
2013 2012 Py_INCREF(self);
2014 2013 return (PyObject *)self;
2015 2014 }
2016 2015
2017 2016 static void index_dealloc(indexObject *self)
2018 2017 {
2019 2018 _index_clearcaches(self);
2020 2019 Py_XDECREF(self->filteredrevs);
2021 2020 if (self->buf.buf) {
2022 2021 PyBuffer_Release(&self->buf);
2023 2022 memset(&self->buf, 0, sizeof(self->buf));
2024 2023 }
2025 2024 Py_XDECREF(self->data);
2026 2025 Py_XDECREF(self->added);
2027 2026 PyObject_Del(self);
2028 2027 }
2029 2028
2030 2029 static PySequenceMethods index_sequence_methods = {
2031 2030 (lenfunc)index_length, /* sq_length */
2032 2031 0, /* sq_concat */
2033 2032 0, /* sq_repeat */
2034 2033 (ssizeargfunc)index_get, /* sq_item */
2035 2034 0, /* sq_slice */
2036 2035 0, /* sq_ass_item */
2037 2036 0, /* sq_ass_slice */
2038 2037 (objobjproc)index_contains, /* sq_contains */
2039 2038 };
2040 2039
2041 2040 static PyMappingMethods index_mapping_methods = {
2042 2041 (lenfunc)index_length, /* mp_length */
2043 2042 (binaryfunc)index_getitem, /* mp_subscript */
2044 2043 (objobjargproc)index_assign_subscript, /* mp_ass_subscript */
2045 2044 };
2046 2045
2047 2046 static PyMethodDef index_methods[] = {
2048 2047 {"ancestors", (PyCFunction)index_ancestors, METH_VARARGS,
2049 2048 "return the gca set of the given revs"},
2050 2049 {"commonancestorsheads", (PyCFunction)index_commonancestorsheads,
2051 2050 METH_VARARGS,
2052 2051 "return the heads of the common ancestors of the given revs"},
2053 2052 {"clearcaches", (PyCFunction)index_clearcaches, METH_NOARGS,
2054 2053 "clear the index caches"},
2055 2054 {"get", (PyCFunction)index_m_get, METH_VARARGS,
2056 2055 "get an index entry"},
2057 2056 {"computephasesmapsets", (PyCFunction)compute_phases_map_sets,
2058 2057 METH_VARARGS, "compute phases"},
2059 2058 {"reachableroots2", (PyCFunction)reachableroots2, METH_VARARGS,
2060 2059 "reachableroots"},
2061 2060 {"headrevs", (PyCFunction)index_headrevs, METH_VARARGS,
2062 2061 "get head revisions"}, /* Can do filtering since 3.2 */
2063 2062 {"headrevsfiltered", (PyCFunction)index_headrevs, METH_VARARGS,
2064 2063 "get filtered head revisions"}, /* Can always do filtering */
2065 2064 {"deltachain", (PyCFunction)index_deltachain, METH_VARARGS,
2066 2065 "determine revisions with deltas to reconstruct fulltext"},
2067 2066 {"append", (PyCFunction)index_append, METH_O,
2068 2067 "append an index entry"},
2069 2068 {"partialmatch", (PyCFunction)index_partialmatch, METH_VARARGS,
2070 2069 "match a potentially ambiguous node ID"},
2071 2070 {"shortest", (PyCFunction)index_shortest, METH_VARARGS,
2072 2071 "find length of shortest hex nodeid of a binary ID"},
2073 2072 {"stats", (PyCFunction)index_stats, METH_NOARGS,
2074 2073 "stats for the index"},
2075 2074 {NULL} /* Sentinel */
2076 2075 };
2077 2076
2078 2077 static PyGetSetDef index_getset[] = {
2079 2078 {"nodemap", (getter)index_nodemap, NULL, "nodemap", NULL},
2080 2079 {NULL} /* Sentinel */
2081 2080 };
2082 2081
2083 2082 static PyTypeObject indexType = {
2084 2083 PyVarObject_HEAD_INIT(NULL, 0) /* header */
2085 2084 "parsers.index", /* tp_name */
2086 2085 sizeof(indexObject), /* tp_basicsize */
2087 2086 0, /* tp_itemsize */
2088 2087 (destructor)index_dealloc, /* tp_dealloc */
2089 2088 0, /* tp_print */
2090 2089 0, /* tp_getattr */
2091 2090 0, /* tp_setattr */
2092 2091 0, /* tp_compare */
2093 2092 0, /* tp_repr */
2094 2093 0, /* tp_as_number */
2095 2094 &index_sequence_methods, /* tp_as_sequence */
2096 2095 &index_mapping_methods, /* tp_as_mapping */
2097 2096 0, /* tp_hash */
2098 2097 0, /* tp_call */
2099 2098 0, /* tp_str */
2100 2099 0, /* tp_getattro */
2101 2100 0, /* tp_setattro */
2102 2101 0, /* tp_as_buffer */
2103 2102 Py_TPFLAGS_DEFAULT, /* tp_flags */
2104 2103 "revlog index", /* tp_doc */
2105 2104 0, /* tp_traverse */
2106 2105 0, /* tp_clear */
2107 2106 0, /* tp_richcompare */
2108 2107 0, /* tp_weaklistoffset */
2109 2108 0, /* tp_iter */
2110 2109 0, /* tp_iternext */
2111 2110 index_methods, /* tp_methods */
2112 2111 0, /* tp_members */
2113 2112 index_getset, /* tp_getset */
2114 2113 0, /* tp_base */
2115 2114 0, /* tp_dict */
2116 2115 0, /* tp_descr_get */
2117 2116 0, /* tp_descr_set */
2118 2117 0, /* tp_dictoffset */
2119 2118 (initproc)index_init, /* tp_init */
2120 2119 0, /* tp_alloc */
2121 2120 };
2122 2121
2123 2122 /*
2124 2123 * returns a tuple of the form (index, index, cache) with elements as
2125 2124 * follows:
2126 2125 *
2127 2126 * index: an index object that lazily parses RevlogNG records
2128 2127 * cache: if data is inlined, a tuple (0, index_file_content), else None
2129 2128 * index_file_content could be a string, or a buffer
2130 2129 *
2131 2130 * added complications are for backwards compatibility
2132 2131 */
2133 2132 PyObject *parse_index2(PyObject *self, PyObject *args)
2134 2133 {
2135 2134 PyObject *tuple = NULL, *cache = NULL;
2136 2135 indexObject *idx;
2137 2136 int ret;
2138 2137
2139 2138 idx = PyObject_New(indexObject, &indexType);
2140 2139 if (idx == NULL)
2141 2140 goto bail;
2142 2141
2143 2142 ret = index_init(idx, args);
2144 2143 if (ret == -1)
2145 2144 goto bail;
2146 2145
2147 2146 if (idx->inlined) {
2148 2147 cache = Py_BuildValue("iO", 0, idx->data);
2149 2148 if (cache == NULL)
2150 2149 goto bail;
2151 2150 } else {
2152 2151 cache = Py_None;
2153 2152 Py_INCREF(cache);
2154 2153 }
2155 2154
2156 2155 tuple = Py_BuildValue("NN", idx, cache);
2157 2156 if (!tuple)
2158 2157 goto bail;
2159 2158 return tuple;
2160 2159
2161 2160 bail:
2162 2161 Py_XDECREF(idx);
2163 2162 Py_XDECREF(cache);
2164 2163 Py_XDECREF(tuple);
2165 2164 return NULL;
2166 2165 }
2167 2166
2168 2167 void revlog_module_init(PyObject *mod)
2169 2168 {
2170 2169 indexType.tp_new = PyType_GenericNew;
2171 2170 if (PyType_Ready(&indexType) < 0)
2172 2171 return;
2173 2172 Py_INCREF(&indexType);
2174 2173 PyModule_AddObject(mod, "index", (PyObject *)&indexType);
2175 2174
2176 2175 nullentry = Py_BuildValue(PY23("iiiiiiis#", "iiiiiiiy#"), 0, 0, 0,
2177 2176 -1, -1, -1, -1, nullid, 20);
2178 2177 if (nullentry)
2179 2178 PyObject_GC_UnTrack(nullentry);
2180 2179 }
General Comments 0
You need to be logged in to leave comments. Login now