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