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