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