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