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