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