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