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