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