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