##// END OF EJS Templates
parsers: fix refcount bug on corrupt index...
Matt Mackall -
r16597:b767382a stable
parent child Browse files
Show More
@@ -1,1186 +1,1186 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 <string.h>
12 #include <string.h>
13
13
14 #include "util.h"
14 #include "util.h"
15
15
16 static int hexdigit(char c)
16 static int hexdigit(char c)
17 {
17 {
18 if (c >= '0' && c <= '9')
18 if (c >= '0' && c <= '9')
19 return c - '0';
19 return c - '0';
20 if (c >= 'a' && c <= 'f')
20 if (c >= 'a' && c <= 'f')
21 return c - 'a' + 10;
21 return c - 'a' + 10;
22 if (c >= 'A' && c <= 'F')
22 if (c >= 'A' && c <= 'F')
23 return c - 'A' + 10;
23 return c - 'A' + 10;
24
24
25 PyErr_SetString(PyExc_ValueError, "input contains non-hex character");
25 PyErr_SetString(PyExc_ValueError, "input contains non-hex character");
26 return 0;
26 return 0;
27 }
27 }
28
28
29 /*
29 /*
30 * Turn a hex-encoded string into binary.
30 * Turn a hex-encoded string into binary.
31 */
31 */
32 static PyObject *unhexlify(const char *str, int len)
32 static PyObject *unhexlify(const char *str, int len)
33 {
33 {
34 PyObject *ret;
34 PyObject *ret;
35 const char *c;
35 const char *c;
36 char *d;
36 char *d;
37
37
38 ret = PyBytes_FromStringAndSize(NULL, len / 2);
38 ret = PyBytes_FromStringAndSize(NULL, len / 2);
39
39
40 if (!ret)
40 if (!ret)
41 return NULL;
41 return NULL;
42
42
43 d = PyBytes_AsString(ret);
43 d = PyBytes_AsString(ret);
44
44
45 for (c = str; c < str + len;) {
45 for (c = str; c < str + len;) {
46 int hi = hexdigit(*c++);
46 int hi = hexdigit(*c++);
47 int lo = hexdigit(*c++);
47 int lo = hexdigit(*c++);
48 *d++ = (hi << 4) | lo;
48 *d++ = (hi << 4) | lo;
49 }
49 }
50
50
51 return ret;
51 return ret;
52 }
52 }
53
53
54 /*
54 /*
55 * This code assumes that a manifest is stitched together with newline
55 * This code assumes that a manifest is stitched together with newline
56 * ('\n') characters.
56 * ('\n') characters.
57 */
57 */
58 static PyObject *parse_manifest(PyObject *self, PyObject *args)
58 static PyObject *parse_manifest(PyObject *self, PyObject *args)
59 {
59 {
60 PyObject *mfdict, *fdict;
60 PyObject *mfdict, *fdict;
61 char *str, *cur, *start, *zero;
61 char *str, *cur, *start, *zero;
62 int len;
62 int len;
63
63
64 if (!PyArg_ParseTuple(args, "O!O!s#:parse_manifest",
64 if (!PyArg_ParseTuple(args, "O!O!s#:parse_manifest",
65 &PyDict_Type, &mfdict,
65 &PyDict_Type, &mfdict,
66 &PyDict_Type, &fdict,
66 &PyDict_Type, &fdict,
67 &str, &len))
67 &str, &len))
68 goto quit;
68 goto quit;
69
69
70 for (start = cur = str, zero = NULL; cur < str + len; cur++) {
70 for (start = cur = str, zero = NULL; cur < str + len; cur++) {
71 PyObject *file = NULL, *node = NULL;
71 PyObject *file = NULL, *node = NULL;
72 PyObject *flags = NULL;
72 PyObject *flags = NULL;
73 int nlen;
73 int nlen;
74
74
75 if (!*cur) {
75 if (!*cur) {
76 zero = cur;
76 zero = cur;
77 continue;
77 continue;
78 }
78 }
79 else if (*cur != '\n')
79 else if (*cur != '\n')
80 continue;
80 continue;
81
81
82 if (!zero) {
82 if (!zero) {
83 PyErr_SetString(PyExc_ValueError,
83 PyErr_SetString(PyExc_ValueError,
84 "manifest entry has no separator");
84 "manifest entry has no separator");
85 goto quit;
85 goto quit;
86 }
86 }
87
87
88 file = PyBytes_FromStringAndSize(start, zero - start);
88 file = PyBytes_FromStringAndSize(start, zero - start);
89
89
90 if (!file)
90 if (!file)
91 goto bail;
91 goto bail;
92
92
93 nlen = cur - zero - 1;
93 nlen = cur - zero - 1;
94
94
95 node = unhexlify(zero + 1, nlen > 40 ? 40 : nlen);
95 node = unhexlify(zero + 1, nlen > 40 ? 40 : nlen);
96 if (!node)
96 if (!node)
97 goto bail;
97 goto bail;
98
98
99 if (nlen > 40) {
99 if (nlen > 40) {
100 flags = PyBytes_FromStringAndSize(zero + 41,
100 flags = PyBytes_FromStringAndSize(zero + 41,
101 nlen - 40);
101 nlen - 40);
102 if (!flags)
102 if (!flags)
103 goto bail;
103 goto bail;
104
104
105 if (PyDict_SetItem(fdict, file, flags) == -1)
105 if (PyDict_SetItem(fdict, file, flags) == -1)
106 goto bail;
106 goto bail;
107 }
107 }
108
108
109 if (PyDict_SetItem(mfdict, file, node) == -1)
109 if (PyDict_SetItem(mfdict, file, node) == -1)
110 goto bail;
110 goto bail;
111
111
112 start = cur + 1;
112 start = cur + 1;
113 zero = NULL;
113 zero = NULL;
114
114
115 Py_XDECREF(flags);
115 Py_XDECREF(flags);
116 Py_XDECREF(node);
116 Py_XDECREF(node);
117 Py_XDECREF(file);
117 Py_XDECREF(file);
118 continue;
118 continue;
119 bail:
119 bail:
120 Py_XDECREF(flags);
120 Py_XDECREF(flags);
121 Py_XDECREF(node);
121 Py_XDECREF(node);
122 Py_XDECREF(file);
122 Py_XDECREF(file);
123 goto quit;
123 goto quit;
124 }
124 }
125
125
126 if (len > 0 && *(cur - 1) != '\n') {
126 if (len > 0 && *(cur - 1) != '\n') {
127 PyErr_SetString(PyExc_ValueError,
127 PyErr_SetString(PyExc_ValueError,
128 "manifest contains trailing garbage");
128 "manifest contains trailing garbage");
129 goto quit;
129 goto quit;
130 }
130 }
131
131
132 Py_INCREF(Py_None);
132 Py_INCREF(Py_None);
133 return Py_None;
133 return Py_None;
134 quit:
134 quit:
135 return NULL;
135 return NULL;
136 }
136 }
137
137
138 static PyObject *parse_dirstate(PyObject *self, PyObject *args)
138 static PyObject *parse_dirstate(PyObject *self, PyObject *args)
139 {
139 {
140 PyObject *dmap, *cmap, *parents = NULL, *ret = NULL;
140 PyObject *dmap, *cmap, *parents = NULL, *ret = NULL;
141 PyObject *fname = NULL, *cname = NULL, *entry = NULL;
141 PyObject *fname = NULL, *cname = NULL, *entry = NULL;
142 char *str, *cur, *end, *cpos;
142 char *str, *cur, *end, *cpos;
143 int state, mode, size, mtime;
143 int state, mode, size, mtime;
144 unsigned int flen;
144 unsigned int flen;
145 int len;
145 int len;
146
146
147 if (!PyArg_ParseTuple(args, "O!O!s#:parse_dirstate",
147 if (!PyArg_ParseTuple(args, "O!O!s#:parse_dirstate",
148 &PyDict_Type, &dmap,
148 &PyDict_Type, &dmap,
149 &PyDict_Type, &cmap,
149 &PyDict_Type, &cmap,
150 &str, &len))
150 &str, &len))
151 goto quit;
151 goto quit;
152
152
153 /* read parents */
153 /* read parents */
154 if (len < 40)
154 if (len < 40)
155 goto quit;
155 goto quit;
156
156
157 parents = Py_BuildValue("s#s#", str, 20, str + 20, 20);
157 parents = Py_BuildValue("s#s#", str, 20, str + 20, 20);
158 if (!parents)
158 if (!parents)
159 goto quit;
159 goto quit;
160
160
161 /* read filenames */
161 /* read filenames */
162 cur = str + 40;
162 cur = str + 40;
163 end = str + len;
163 end = str + len;
164
164
165 while (cur < end - 17) {
165 while (cur < end - 17) {
166 /* unpack header */
166 /* unpack header */
167 state = *cur;
167 state = *cur;
168 mode = getbe32(cur + 1);
168 mode = getbe32(cur + 1);
169 size = getbe32(cur + 5);
169 size = getbe32(cur + 5);
170 mtime = getbe32(cur + 9);
170 mtime = getbe32(cur + 9);
171 flen = getbe32(cur + 13);
171 flen = getbe32(cur + 13);
172 cur += 17;
172 cur += 17;
173 if (cur + flen > end || cur + flen < cur) {
173 if (cur + flen > end || cur + flen < cur) {
174 PyErr_SetString(PyExc_ValueError, "overflow in dirstate");
174 PyErr_SetString(PyExc_ValueError, "overflow in dirstate");
175 goto quit;
175 goto quit;
176 }
176 }
177
177
178 entry = Py_BuildValue("ciii", state, mode, size, mtime);
178 entry = Py_BuildValue("ciii", state, mode, size, mtime);
179 if (!entry)
179 if (!entry)
180 goto quit;
180 goto quit;
181 PyObject_GC_UnTrack(entry); /* don't waste time with this */
181 PyObject_GC_UnTrack(entry); /* don't waste time with this */
182
182
183 cpos = memchr(cur, 0, flen);
183 cpos = memchr(cur, 0, flen);
184 if (cpos) {
184 if (cpos) {
185 fname = PyBytes_FromStringAndSize(cur, cpos - cur);
185 fname = PyBytes_FromStringAndSize(cur, cpos - cur);
186 cname = PyBytes_FromStringAndSize(cpos + 1,
186 cname = PyBytes_FromStringAndSize(cpos + 1,
187 flen - (cpos - cur) - 1);
187 flen - (cpos - cur) - 1);
188 if (!fname || !cname ||
188 if (!fname || !cname ||
189 PyDict_SetItem(cmap, fname, cname) == -1 ||
189 PyDict_SetItem(cmap, fname, cname) == -1 ||
190 PyDict_SetItem(dmap, fname, entry) == -1)
190 PyDict_SetItem(dmap, fname, entry) == -1)
191 goto quit;
191 goto quit;
192 Py_DECREF(cname);
192 Py_DECREF(cname);
193 } else {
193 } else {
194 fname = PyBytes_FromStringAndSize(cur, flen);
194 fname = PyBytes_FromStringAndSize(cur, flen);
195 if (!fname ||
195 if (!fname ||
196 PyDict_SetItem(dmap, fname, entry) == -1)
196 PyDict_SetItem(dmap, fname, entry) == -1)
197 goto quit;
197 goto quit;
198 }
198 }
199 cur += flen;
199 cur += flen;
200 Py_DECREF(fname);
200 Py_DECREF(fname);
201 Py_DECREF(entry);
201 Py_DECREF(entry);
202 fname = cname = entry = NULL;
202 fname = cname = entry = NULL;
203 }
203 }
204
204
205 ret = parents;
205 ret = parents;
206 Py_INCREF(ret);
206 Py_INCREF(ret);
207 quit:
207 quit:
208 Py_XDECREF(fname);
208 Py_XDECREF(fname);
209 Py_XDECREF(cname);
209 Py_XDECREF(cname);
210 Py_XDECREF(entry);
210 Py_XDECREF(entry);
211 Py_XDECREF(parents);
211 Py_XDECREF(parents);
212 return ret;
212 return ret;
213 }
213 }
214
214
215 /*
215 /*
216 * A base-16 trie for fast node->rev mapping.
216 * A base-16 trie for fast node->rev mapping.
217 *
217 *
218 * Positive value is index of the next node in the trie
218 * Positive value is index of the next node in the trie
219 * Negative value is a leaf: -(rev + 1)
219 * Negative value is a leaf: -(rev + 1)
220 * Zero is empty
220 * Zero is empty
221 */
221 */
222 typedef struct {
222 typedef struct {
223 int children[16];
223 int children[16];
224 } nodetree;
224 } nodetree;
225
225
226 /*
226 /*
227 * This class has two behaviours.
227 * This class has two behaviours.
228 *
228 *
229 * When used in a list-like way (with integer keys), we decode an
229 * When used in a list-like way (with integer keys), we decode an
230 * entry in a RevlogNG index file on demand. Our last entry is a
230 * entry in a RevlogNG index file on demand. Our last entry is a
231 * sentinel, always a nullid. We have limited support for
231 * sentinel, always a nullid. We have limited support for
232 * integer-keyed insert and delete, only at elements right before the
232 * integer-keyed insert and delete, only at elements right before the
233 * sentinel.
233 * sentinel.
234 *
234 *
235 * With string keys, we lazily perform a reverse mapping from node to
235 * With string keys, we lazily perform a reverse mapping from node to
236 * rev, using a base-16 trie.
236 * rev, using a base-16 trie.
237 */
237 */
238 typedef struct {
238 typedef struct {
239 PyObject_HEAD
239 PyObject_HEAD
240 /* Type-specific fields go here. */
240 /* Type-specific fields go here. */
241 PyObject *data; /* raw bytes of index */
241 PyObject *data; /* raw bytes of index */
242 PyObject **cache; /* cached tuples */
242 PyObject **cache; /* cached tuples */
243 const char **offsets; /* populated on demand */
243 const char **offsets; /* populated on demand */
244 Py_ssize_t raw_length; /* original number of elements */
244 Py_ssize_t raw_length; /* original number of elements */
245 Py_ssize_t length; /* current number of elements */
245 Py_ssize_t length; /* current number of elements */
246 PyObject *added; /* populated on demand */
246 PyObject *added; /* populated on demand */
247 nodetree *nt; /* base-16 trie */
247 nodetree *nt; /* base-16 trie */
248 int ntlength; /* # nodes in use */
248 int ntlength; /* # nodes in use */
249 int ntcapacity; /* # nodes allocated */
249 int ntcapacity; /* # nodes allocated */
250 int ntdepth; /* maximum depth of tree */
250 int ntdepth; /* maximum depth of tree */
251 int ntsplits; /* # splits performed */
251 int ntsplits; /* # splits performed */
252 int ntrev; /* last rev scanned */
252 int ntrev; /* last rev scanned */
253 int ntlookups; /* # lookups */
253 int ntlookups; /* # lookups */
254 int ntmisses; /* # lookups that miss the cache */
254 int ntmisses; /* # lookups that miss the cache */
255 int inlined;
255 int inlined;
256 } indexObject;
256 } indexObject;
257
257
258 static Py_ssize_t index_length(const indexObject *self)
258 static Py_ssize_t index_length(const indexObject *self)
259 {
259 {
260 if (self->added == NULL)
260 if (self->added == NULL)
261 return self->length;
261 return self->length;
262 return self->length + PyList_GET_SIZE(self->added);
262 return self->length + PyList_GET_SIZE(self->added);
263 }
263 }
264
264
265 static PyObject *nullentry;
265 static PyObject *nullentry;
266 static const char nullid[20];
266 static const char nullid[20];
267
267
268 static long inline_scan(indexObject *self, const char **offsets);
268 static long inline_scan(indexObject *self, const char **offsets);
269
269
270 #if LONG_MAX == 0x7fffffffL
270 #if LONG_MAX == 0x7fffffffL
271 static char *tuple_format = "Kiiiiiis#";
271 static char *tuple_format = "Kiiiiiis#";
272 #else
272 #else
273 static char *tuple_format = "kiiiiiis#";
273 static char *tuple_format = "kiiiiiis#";
274 #endif
274 #endif
275
275
276 /*
276 /*
277 * Return a pointer to the beginning of a RevlogNG record.
277 * Return a pointer to the beginning of a RevlogNG record.
278 */
278 */
279 static const char *index_deref(indexObject *self, Py_ssize_t pos)
279 static const char *index_deref(indexObject *self, Py_ssize_t pos)
280 {
280 {
281 if (self->inlined && pos > 0) {
281 if (self->inlined && pos > 0) {
282 if (self->offsets == NULL) {
282 if (self->offsets == NULL) {
283 self->offsets = malloc(self->raw_length *
283 self->offsets = malloc(self->raw_length *
284 sizeof(*self->offsets));
284 sizeof(*self->offsets));
285 if (self->offsets == NULL)
285 if (self->offsets == NULL)
286 return (const char *)PyErr_NoMemory();
286 return (const char *)PyErr_NoMemory();
287 inline_scan(self, self->offsets);
287 inline_scan(self, self->offsets);
288 }
288 }
289 return self->offsets[pos];
289 return self->offsets[pos];
290 }
290 }
291
291
292 return PyString_AS_STRING(self->data) + pos * 64;
292 return PyString_AS_STRING(self->data) + pos * 64;
293 }
293 }
294
294
295 /*
295 /*
296 * RevlogNG format (all in big endian, data may be inlined):
296 * RevlogNG format (all in big endian, data may be inlined):
297 * 6 bytes: offset
297 * 6 bytes: offset
298 * 2 bytes: flags
298 * 2 bytes: flags
299 * 4 bytes: compressed length
299 * 4 bytes: compressed length
300 * 4 bytes: uncompressed length
300 * 4 bytes: uncompressed length
301 * 4 bytes: base revision
301 * 4 bytes: base revision
302 * 4 bytes: link revision
302 * 4 bytes: link revision
303 * 4 bytes: parent 1 revision
303 * 4 bytes: parent 1 revision
304 * 4 bytes: parent 2 revision
304 * 4 bytes: parent 2 revision
305 * 32 bytes: nodeid (only 20 bytes used)
305 * 32 bytes: nodeid (only 20 bytes used)
306 */
306 */
307 static PyObject *index_get(indexObject *self, Py_ssize_t pos)
307 static PyObject *index_get(indexObject *self, Py_ssize_t pos)
308 {
308 {
309 uint64_t offset_flags;
309 uint64_t offset_flags;
310 int comp_len, uncomp_len, base_rev, link_rev, parent_1, parent_2;
310 int comp_len, uncomp_len, base_rev, link_rev, parent_1, parent_2;
311 const char *c_node_id;
311 const char *c_node_id;
312 const char *data;
312 const char *data;
313 Py_ssize_t length = index_length(self);
313 Py_ssize_t length = index_length(self);
314 PyObject *entry;
314 PyObject *entry;
315
315
316 if (pos < 0)
316 if (pos < 0)
317 pos += length;
317 pos += length;
318
318
319 if (pos < 0 || pos >= length) {
319 if (pos < 0 || pos >= length) {
320 PyErr_SetString(PyExc_IndexError, "revlog index out of range");
320 PyErr_SetString(PyExc_IndexError, "revlog index out of range");
321 return NULL;
321 return NULL;
322 }
322 }
323
323
324 if (pos == length - 1) {
324 if (pos == length - 1) {
325 Py_INCREF(nullentry);
325 Py_INCREF(nullentry);
326 return nullentry;
326 return nullentry;
327 }
327 }
328
328
329 if (pos >= self->length - 1) {
329 if (pos >= self->length - 1) {
330 PyObject *obj;
330 PyObject *obj;
331 obj = PyList_GET_ITEM(self->added, pos - self->length + 1);
331 obj = PyList_GET_ITEM(self->added, pos - self->length + 1);
332 Py_INCREF(obj);
332 Py_INCREF(obj);
333 return obj;
333 return obj;
334 }
334 }
335
335
336 if (self->cache) {
336 if (self->cache) {
337 if (self->cache[pos]) {
337 if (self->cache[pos]) {
338 Py_INCREF(self->cache[pos]);
338 Py_INCREF(self->cache[pos]);
339 return self->cache[pos];
339 return self->cache[pos];
340 }
340 }
341 } else {
341 } else {
342 self->cache = calloc(self->raw_length, sizeof(PyObject *));
342 self->cache = calloc(self->raw_length, sizeof(PyObject *));
343 if (self->cache == NULL)
343 if (self->cache == NULL)
344 return PyErr_NoMemory();
344 return PyErr_NoMemory();
345 }
345 }
346
346
347 data = index_deref(self, pos);
347 data = index_deref(self, pos);
348 if (data == NULL)
348 if (data == NULL)
349 return NULL;
349 return NULL;
350
350
351 offset_flags = getbe32(data + 4);
351 offset_flags = getbe32(data + 4);
352 if (pos == 0) /* mask out version number for the first entry */
352 if (pos == 0) /* mask out version number for the first entry */
353 offset_flags &= 0xFFFF;
353 offset_flags &= 0xFFFF;
354 else {
354 else {
355 uint32_t offset_high = getbe32(data);
355 uint32_t offset_high = getbe32(data);
356 offset_flags |= ((uint64_t)offset_high) << 32;
356 offset_flags |= ((uint64_t)offset_high) << 32;
357 }
357 }
358
358
359 comp_len = getbe32(data + 8);
359 comp_len = getbe32(data + 8);
360 uncomp_len = getbe32(data + 12);
360 uncomp_len = getbe32(data + 12);
361 base_rev = getbe32(data + 16);
361 base_rev = getbe32(data + 16);
362 link_rev = getbe32(data + 20);
362 link_rev = getbe32(data + 20);
363 parent_1 = getbe32(data + 24);
363 parent_1 = getbe32(data + 24);
364 parent_2 = getbe32(data + 28);
364 parent_2 = getbe32(data + 28);
365 c_node_id = data + 32;
365 c_node_id = data + 32;
366
366
367 entry = Py_BuildValue(tuple_format, offset_flags, comp_len,
367 entry = Py_BuildValue(tuple_format, offset_flags, comp_len,
368 uncomp_len, base_rev, link_rev,
368 uncomp_len, base_rev, link_rev,
369 parent_1, parent_2, c_node_id, 20);
369 parent_1, parent_2, c_node_id, 20);
370
370
371 if (entry)
371 if (entry)
372 PyObject_GC_UnTrack(entry);
372 PyObject_GC_UnTrack(entry);
373
373
374 self->cache[pos] = entry;
374 self->cache[pos] = entry;
375 Py_INCREF(entry);
375 Py_INCREF(entry);
376
376
377 return entry;
377 return entry;
378 }
378 }
379
379
380 /*
380 /*
381 * Return the 20-byte SHA of the node corresponding to the given rev.
381 * Return the 20-byte SHA of the node corresponding to the given rev.
382 */
382 */
383 static const char *index_node(indexObject *self, Py_ssize_t pos)
383 static const char *index_node(indexObject *self, Py_ssize_t pos)
384 {
384 {
385 Py_ssize_t length = index_length(self);
385 Py_ssize_t length = index_length(self);
386 const char *data;
386 const char *data;
387
387
388 if (pos == length - 1)
388 if (pos == length - 1)
389 return nullid;
389 return nullid;
390
390
391 if (pos >= length)
391 if (pos >= length)
392 return NULL;
392 return NULL;
393
393
394 if (pos >= self->length - 1) {
394 if (pos >= self->length - 1) {
395 PyObject *tuple, *str;
395 PyObject *tuple, *str;
396 tuple = PyList_GET_ITEM(self->added, pos - self->length + 1);
396 tuple = PyList_GET_ITEM(self->added, pos - self->length + 1);
397 str = PyTuple_GetItem(tuple, 7);
397 str = PyTuple_GetItem(tuple, 7);
398 return str ? PyString_AS_STRING(str) : NULL;
398 return str ? PyString_AS_STRING(str) : NULL;
399 }
399 }
400
400
401 data = index_deref(self, pos);
401 data = index_deref(self, pos);
402 return data ? data + 32 : NULL;
402 return data ? data + 32 : NULL;
403 }
403 }
404
404
405 static int nt_insert(indexObject *self, const char *node, int rev);
405 static int nt_insert(indexObject *self, const char *node, int rev);
406
406
407 static int node_check(PyObject *obj, char **node, Py_ssize_t *nodelen)
407 static int node_check(PyObject *obj, char **node, Py_ssize_t *nodelen)
408 {
408 {
409 if (PyString_AsStringAndSize(obj, node, nodelen) == -1)
409 if (PyString_AsStringAndSize(obj, node, nodelen) == -1)
410 return -1;
410 return -1;
411 if (*nodelen == 20)
411 if (*nodelen == 20)
412 return 0;
412 return 0;
413 PyErr_SetString(PyExc_ValueError, "20-byte hash required");
413 PyErr_SetString(PyExc_ValueError, "20-byte hash required");
414 return -1;
414 return -1;
415 }
415 }
416
416
417 static PyObject *index_insert(indexObject *self, PyObject *args)
417 static PyObject *index_insert(indexObject *self, PyObject *args)
418 {
418 {
419 PyObject *obj;
419 PyObject *obj;
420 char *node;
420 char *node;
421 long offset;
421 long offset;
422 Py_ssize_t len, nodelen;
422 Py_ssize_t len, nodelen;
423
423
424 if (!PyArg_ParseTuple(args, "lO", &offset, &obj))
424 if (!PyArg_ParseTuple(args, "lO", &offset, &obj))
425 return NULL;
425 return NULL;
426
426
427 if (!PyTuple_Check(obj) || PyTuple_GET_SIZE(obj) != 8) {
427 if (!PyTuple_Check(obj) || PyTuple_GET_SIZE(obj) != 8) {
428 PyErr_SetString(PyExc_TypeError, "8-tuple required");
428 PyErr_SetString(PyExc_TypeError, "8-tuple required");
429 return NULL;
429 return NULL;
430 }
430 }
431
431
432 if (node_check(PyTuple_GET_ITEM(obj, 7), &node, &nodelen) == -1)
432 if (node_check(PyTuple_GET_ITEM(obj, 7), &node, &nodelen) == -1)
433 return NULL;
433 return NULL;
434
434
435 len = index_length(self);
435 len = index_length(self);
436
436
437 if (offset < 0)
437 if (offset < 0)
438 offset += len;
438 offset += len;
439
439
440 if (offset != len - 1) {
440 if (offset != len - 1) {
441 PyErr_SetString(PyExc_IndexError,
441 PyErr_SetString(PyExc_IndexError,
442 "insert only supported at index -1");
442 "insert only supported at index -1");
443 return NULL;
443 return NULL;
444 }
444 }
445
445
446 if (offset > INT_MAX) {
446 if (offset > INT_MAX) {
447 PyErr_SetString(PyExc_ValueError,
447 PyErr_SetString(PyExc_ValueError,
448 "currently only 2**31 revs supported");
448 "currently only 2**31 revs supported");
449 return NULL;
449 return NULL;
450 }
450 }
451
451
452 if (self->added == NULL) {
452 if (self->added == NULL) {
453 self->added = PyList_New(0);
453 self->added = PyList_New(0);
454 if (self->added == NULL)
454 if (self->added == NULL)
455 return NULL;
455 return NULL;
456 }
456 }
457
457
458 if (PyList_Append(self->added, obj) == -1)
458 if (PyList_Append(self->added, obj) == -1)
459 return NULL;
459 return NULL;
460
460
461 if (self->nt)
461 if (self->nt)
462 nt_insert(self, node, (int)offset);
462 nt_insert(self, node, (int)offset);
463
463
464 Py_RETURN_NONE;
464 Py_RETURN_NONE;
465 }
465 }
466
466
467 static void _index_clearcaches(indexObject *self)
467 static void _index_clearcaches(indexObject *self)
468 {
468 {
469 if (self->cache) {
469 if (self->cache) {
470 Py_ssize_t i;
470 Py_ssize_t i;
471
471
472 for (i = 0; i < self->raw_length; i++) {
472 for (i = 0; i < self->raw_length; i++) {
473 if (self->cache[i]) {
473 if (self->cache[i]) {
474 Py_DECREF(self->cache[i]);
474 Py_DECREF(self->cache[i]);
475 self->cache[i] = NULL;
475 self->cache[i] = NULL;
476 }
476 }
477 }
477 }
478 free(self->cache);
478 free(self->cache);
479 self->cache = NULL;
479 self->cache = NULL;
480 }
480 }
481 if (self->offsets) {
481 if (self->offsets) {
482 free(self->offsets);
482 free(self->offsets);
483 self->offsets = NULL;
483 self->offsets = NULL;
484 }
484 }
485 if (self->nt) {
485 if (self->nt) {
486 free(self->nt);
486 free(self->nt);
487 self->nt = NULL;
487 self->nt = NULL;
488 }
488 }
489 }
489 }
490
490
491 static PyObject *index_clearcaches(indexObject *self)
491 static PyObject *index_clearcaches(indexObject *self)
492 {
492 {
493 _index_clearcaches(self);
493 _index_clearcaches(self);
494 self->ntlength = self->ntcapacity = 0;
494 self->ntlength = self->ntcapacity = 0;
495 self->ntdepth = self->ntsplits = 0;
495 self->ntdepth = self->ntsplits = 0;
496 self->ntrev = -1;
496 self->ntrev = -1;
497 self->ntlookups = self->ntmisses = 0;
497 self->ntlookups = self->ntmisses = 0;
498 Py_RETURN_NONE;
498 Py_RETURN_NONE;
499 }
499 }
500
500
501 static PyObject *index_stats(indexObject *self)
501 static PyObject *index_stats(indexObject *self)
502 {
502 {
503 PyObject *obj = PyDict_New();
503 PyObject *obj = PyDict_New();
504
504
505 if (obj == NULL)
505 if (obj == NULL)
506 return NULL;
506 return NULL;
507
507
508 #define istat(__n, __d) \
508 #define istat(__n, __d) \
509 if (PyDict_SetItemString(obj, __d, PyInt_FromLong(self->__n)) == -1) \
509 if (PyDict_SetItemString(obj, __d, PyInt_FromLong(self->__n)) == -1) \
510 goto bail;
510 goto bail;
511
511
512 if (self->added) {
512 if (self->added) {
513 Py_ssize_t len = PyList_GET_SIZE(self->added);
513 Py_ssize_t len = PyList_GET_SIZE(self->added);
514 if (PyDict_SetItemString(obj, "index entries added",
514 if (PyDict_SetItemString(obj, "index entries added",
515 PyInt_FromLong(len)) == -1)
515 PyInt_FromLong(len)) == -1)
516 goto bail;
516 goto bail;
517 }
517 }
518
518
519 if (self->raw_length != self->length - 1)
519 if (self->raw_length != self->length - 1)
520 istat(raw_length, "revs on disk");
520 istat(raw_length, "revs on disk");
521 istat(length, "revs in memory");
521 istat(length, "revs in memory");
522 istat(ntcapacity, "node trie capacity");
522 istat(ntcapacity, "node trie capacity");
523 istat(ntdepth, "node trie depth");
523 istat(ntdepth, "node trie depth");
524 istat(ntlength, "node trie count");
524 istat(ntlength, "node trie count");
525 istat(ntlookups, "node trie lookups");
525 istat(ntlookups, "node trie lookups");
526 istat(ntmisses, "node trie misses");
526 istat(ntmisses, "node trie misses");
527 istat(ntrev, "node trie last rev scanned");
527 istat(ntrev, "node trie last rev scanned");
528 istat(ntsplits, "node trie splits");
528 istat(ntsplits, "node trie splits");
529
529
530 #undef istat
530 #undef istat
531
531
532 return obj;
532 return obj;
533
533
534 bail:
534 bail:
535 Py_XDECREF(obj);
535 Py_XDECREF(obj);
536 return NULL;
536 return NULL;
537 }
537 }
538
538
539 static inline int nt_level(const char *node, int level)
539 static inline int nt_level(const char *node, int level)
540 {
540 {
541 int v = node[level>>1];
541 int v = node[level>>1];
542 if (!(level & 1))
542 if (!(level & 1))
543 v >>= 4;
543 v >>= 4;
544 return v & 0xf;
544 return v & 0xf;
545 }
545 }
546
546
547 static int nt_find(indexObject *self, const char *node, Py_ssize_t nodelen)
547 static int nt_find(indexObject *self, const char *node, Py_ssize_t nodelen)
548 {
548 {
549 int level, off;
549 int level, off;
550
550
551 if (nodelen == 20 && node[0] == '\0' && memcmp(node, nullid, 20) == 0)
551 if (nodelen == 20 && node[0] == '\0' && memcmp(node, nullid, 20) == 0)
552 return -1;
552 return -1;
553
553
554 if (self->nt == NULL)
554 if (self->nt == NULL)
555 return -2;
555 return -2;
556
556
557 for (level = off = 0; level < nodelen; level++) {
557 for (level = off = 0; level < nodelen; level++) {
558 int k = nt_level(node, level);
558 int k = nt_level(node, level);
559 nodetree *n = &self->nt[off];
559 nodetree *n = &self->nt[off];
560 int v = n->children[k];
560 int v = n->children[k];
561
561
562 if (v < 0) {
562 if (v < 0) {
563 const char *n;
563 const char *n;
564 v = -v - 1;
564 v = -v - 1;
565 n = index_node(self, v);
565 n = index_node(self, v);
566 if (n == NULL)
566 if (n == NULL)
567 return -2;
567 return -2;
568 return memcmp(node, n, nodelen > 20 ? 20 : nodelen)
568 return memcmp(node, n, nodelen > 20 ? 20 : nodelen)
569 ? -2 : v;
569 ? -2 : v;
570 }
570 }
571 if (v == 0)
571 if (v == 0)
572 return -2;
572 return -2;
573 off = v;
573 off = v;
574 }
574 }
575 return -2;
575 return -2;
576 }
576 }
577
577
578 static int nt_new(indexObject *self)
578 static int nt_new(indexObject *self)
579 {
579 {
580 if (self->ntlength == self->ntcapacity) {
580 if (self->ntlength == self->ntcapacity) {
581 self->ntcapacity *= 2;
581 self->ntcapacity *= 2;
582 self->nt = realloc(self->nt,
582 self->nt = realloc(self->nt,
583 self->ntcapacity * sizeof(nodetree));
583 self->ntcapacity * sizeof(nodetree));
584 if (self->nt == NULL) {
584 if (self->nt == NULL) {
585 PyErr_SetString(PyExc_MemoryError, "out of memory");
585 PyErr_SetString(PyExc_MemoryError, "out of memory");
586 return -1;
586 return -1;
587 }
587 }
588 memset(&self->nt[self->ntlength], 0,
588 memset(&self->nt[self->ntlength], 0,
589 sizeof(nodetree) * (self->ntcapacity - self->ntlength));
589 sizeof(nodetree) * (self->ntcapacity - self->ntlength));
590 }
590 }
591 return self->ntlength++;
591 return self->ntlength++;
592 }
592 }
593
593
594 static int nt_insert(indexObject *self, const char *node, int rev)
594 static int nt_insert(indexObject *self, const char *node, int rev)
595 {
595 {
596 int level = 0;
596 int level = 0;
597 int off = 0;
597 int off = 0;
598
598
599 while (level < 20) {
599 while (level < 20) {
600 int k = nt_level(node, level);
600 int k = nt_level(node, level);
601 nodetree *n;
601 nodetree *n;
602 int v;
602 int v;
603
603
604 n = &self->nt[off];
604 n = &self->nt[off];
605 v = n->children[k];
605 v = n->children[k];
606
606
607 if (v == 0) {
607 if (v == 0) {
608 n->children[k] = -rev - 1;
608 n->children[k] = -rev - 1;
609 return 0;
609 return 0;
610 }
610 }
611 if (v < 0) {
611 if (v < 0) {
612 const char *oldnode = index_node(self, -v - 1);
612 const char *oldnode = index_node(self, -v - 1);
613 int noff;
613 int noff;
614
614
615 if (!oldnode || !memcmp(oldnode, node, 20)) {
615 if (!oldnode || !memcmp(oldnode, node, 20)) {
616 n->children[k] = -rev - 1;
616 n->children[k] = -rev - 1;
617 return 0;
617 return 0;
618 }
618 }
619 noff = nt_new(self);
619 noff = nt_new(self);
620 if (noff == -1)
620 if (noff == -1)
621 return -1;
621 return -1;
622 /* self->nt may have been changed by realloc */
622 /* self->nt may have been changed by realloc */
623 self->nt[off].children[k] = noff;
623 self->nt[off].children[k] = noff;
624 off = noff;
624 off = noff;
625 n = &self->nt[off];
625 n = &self->nt[off];
626 n->children[nt_level(oldnode, ++level)] = v;
626 n->children[nt_level(oldnode, ++level)] = v;
627 if (level > self->ntdepth)
627 if (level > self->ntdepth)
628 self->ntdepth = level;
628 self->ntdepth = level;
629 self->ntsplits += 1;
629 self->ntsplits += 1;
630 } else {
630 } else {
631 level += 1;
631 level += 1;
632 off = v;
632 off = v;
633 }
633 }
634 }
634 }
635
635
636 return -1;
636 return -1;
637 }
637 }
638
638
639 /*
639 /*
640 * Return values:
640 * Return values:
641 *
641 *
642 * -3: error (exception set)
642 * -3: error (exception set)
643 * -2: not found (no exception set)
643 * -2: not found (no exception set)
644 * rest: valid rev
644 * rest: valid rev
645 */
645 */
646 static int index_find_node(indexObject *self,
646 static int index_find_node(indexObject *self,
647 const char *node, Py_ssize_t nodelen)
647 const char *node, Py_ssize_t nodelen)
648 {
648 {
649 int rev;
649 int rev;
650
650
651 self->ntlookups++;
651 self->ntlookups++;
652 rev = nt_find(self, node, nodelen);
652 rev = nt_find(self, node, nodelen);
653 if (rev >= -1)
653 if (rev >= -1)
654 return rev;
654 return rev;
655
655
656 if (self->nt == NULL) {
656 if (self->nt == NULL) {
657 self->ntcapacity = self->raw_length < 4
657 self->ntcapacity = self->raw_length < 4
658 ? 4 : self->raw_length / 2;
658 ? 4 : self->raw_length / 2;
659 self->nt = calloc(self->ntcapacity, sizeof(nodetree));
659 self->nt = calloc(self->ntcapacity, sizeof(nodetree));
660 if (self->nt == NULL) {
660 if (self->nt == NULL) {
661 PyErr_SetString(PyExc_MemoryError, "out of memory");
661 PyErr_SetString(PyExc_MemoryError, "out of memory");
662 return -3;
662 return -3;
663 }
663 }
664 self->ntlength = 1;
664 self->ntlength = 1;
665 self->ntrev = (int)index_length(self) - 1;
665 self->ntrev = (int)index_length(self) - 1;
666 self->ntlookups = 1;
666 self->ntlookups = 1;
667 self->ntmisses = 0;
667 self->ntmisses = 0;
668 }
668 }
669
669
670 /*
670 /*
671 * For the first handful of lookups, we scan the entire index,
671 * For the first handful of lookups, we scan the entire index,
672 * and cache only the matching nodes. This optimizes for cases
672 * and cache only the matching nodes. This optimizes for cases
673 * like "hg tip", where only a few nodes are accessed.
673 * like "hg tip", where only a few nodes are accessed.
674 *
674 *
675 * After that, we cache every node we visit, using a single
675 * After that, we cache every node we visit, using a single
676 * scan amortized over multiple lookups. This gives the best
676 * scan amortized over multiple lookups. This gives the best
677 * bulk performance, e.g. for "hg log".
677 * bulk performance, e.g. for "hg log".
678 */
678 */
679 if (self->ntmisses++ < 4) {
679 if (self->ntmisses++ < 4) {
680 for (rev = self->ntrev - 1; rev >= 0; rev--) {
680 for (rev = self->ntrev - 1; rev >= 0; rev--) {
681 const char *n = index_node(self, rev);
681 const char *n = index_node(self, rev);
682 if (n == NULL)
682 if (n == NULL)
683 return -2;
683 return -2;
684 if (memcmp(node, n, nodelen > 20 ? 20 : nodelen) == 0) {
684 if (memcmp(node, n, nodelen > 20 ? 20 : nodelen) == 0) {
685 if (nt_insert(self, n, rev) == -1)
685 if (nt_insert(self, n, rev) == -1)
686 return -3;
686 return -3;
687 break;
687 break;
688 }
688 }
689 }
689 }
690 } else {
690 } else {
691 for (rev = self->ntrev - 1; rev >= 0; rev--) {
691 for (rev = self->ntrev - 1; rev >= 0; rev--) {
692 const char *n = index_node(self, rev);
692 const char *n = index_node(self, rev);
693 if (n == NULL)
693 if (n == NULL)
694 return -2;
694 return -2;
695 if (nt_insert(self, n, rev) == -1)
695 if (nt_insert(self, n, rev) == -1)
696 return -3;
696 return -3;
697 if (memcmp(node, n, nodelen > 20 ? 20 : nodelen) == 0) {
697 if (memcmp(node, n, nodelen > 20 ? 20 : nodelen) == 0) {
698 break;
698 break;
699 }
699 }
700 }
700 }
701 self->ntrev = rev;
701 self->ntrev = rev;
702 }
702 }
703
703
704 if (rev >= 0)
704 if (rev >= 0)
705 return rev;
705 return rev;
706 return -2;
706 return -2;
707 }
707 }
708
708
709 static PyObject *raise_revlog_error(void)
709 static PyObject *raise_revlog_error(void)
710 {
710 {
711 static PyObject *errclass;
711 static PyObject *errclass;
712 PyObject *mod = NULL, *errobj;
712 PyObject *mod = NULL, *errobj;
713
713
714 if (errclass == NULL) {
714 if (errclass == NULL) {
715 PyObject *dict;
715 PyObject *dict;
716
716
717 mod = PyImport_ImportModule("mercurial.error");
717 mod = PyImport_ImportModule("mercurial.error");
718 if (mod == NULL)
718 if (mod == NULL)
719 goto classfail;
719 goto classfail;
720
720
721 dict = PyModule_GetDict(mod);
721 dict = PyModule_GetDict(mod);
722 if (dict == NULL)
722 if (dict == NULL)
723 goto classfail;
723 goto classfail;
724
724
725 errclass = PyDict_GetItemString(dict, "RevlogError");
725 errclass = PyDict_GetItemString(dict, "RevlogError");
726 if (errclass == NULL) {
726 if (errclass == NULL) {
727 PyErr_SetString(PyExc_SystemError,
727 PyErr_SetString(PyExc_SystemError,
728 "could not find RevlogError");
728 "could not find RevlogError");
729 goto classfail;
729 goto classfail;
730 }
730 }
731 Py_INCREF(errclass);
731 Py_INCREF(errclass);
732 }
732 }
733
733
734 errobj = PyObject_CallFunction(errclass, NULL);
734 errobj = PyObject_CallFunction(errclass, NULL);
735 if (errobj == NULL)
735 if (errobj == NULL)
736 return NULL;
736 return NULL;
737 PyErr_SetObject(errclass, errobj);
737 PyErr_SetObject(errclass, errobj);
738 return errobj;
738 return errobj;
739
739
740 classfail:
740 classfail:
741 Py_XDECREF(mod);
741 Py_XDECREF(mod);
742 return NULL;
742 return NULL;
743 }
743 }
744
744
745 static PyObject *index_getitem(indexObject *self, PyObject *value)
745 static PyObject *index_getitem(indexObject *self, PyObject *value)
746 {
746 {
747 char *node;
747 char *node;
748 Py_ssize_t nodelen;
748 Py_ssize_t nodelen;
749 int rev;
749 int rev;
750
750
751 if (PyInt_Check(value))
751 if (PyInt_Check(value))
752 return index_get(self, PyInt_AS_LONG(value));
752 return index_get(self, PyInt_AS_LONG(value));
753
753
754 if (PyString_AsStringAndSize(value, &node, &nodelen) == -1)
754 if (PyString_AsStringAndSize(value, &node, &nodelen) == -1)
755 return NULL;
755 return NULL;
756 rev = index_find_node(self, node, nodelen);
756 rev = index_find_node(self, node, nodelen);
757 if (rev >= -1)
757 if (rev >= -1)
758 return PyInt_FromLong(rev);
758 return PyInt_FromLong(rev);
759 if (rev == -2)
759 if (rev == -2)
760 raise_revlog_error();
760 raise_revlog_error();
761 return NULL;
761 return NULL;
762 }
762 }
763
763
764 static PyObject *index_m_get(indexObject *self, PyObject *args)
764 static PyObject *index_m_get(indexObject *self, PyObject *args)
765 {
765 {
766 char *node;
766 char *node;
767 int nodelen, rev;
767 int nodelen, rev;
768
768
769 if (!PyArg_ParseTuple(args, "s#", &node, &nodelen))
769 if (!PyArg_ParseTuple(args, "s#", &node, &nodelen))
770 return NULL;
770 return NULL;
771
771
772 rev = index_find_node(self, node, nodelen);
772 rev = index_find_node(self, node, nodelen);
773 if (rev == -3)
773 if (rev == -3)
774 return NULL;
774 return NULL;
775 if (rev == -2)
775 if (rev == -2)
776 Py_RETURN_NONE;
776 Py_RETURN_NONE;
777 return PyInt_FromLong(rev);
777 return PyInt_FromLong(rev);
778 }
778 }
779
779
780 static int index_contains(indexObject *self, PyObject *value)
780 static int index_contains(indexObject *self, PyObject *value)
781 {
781 {
782 char *node;
782 char *node;
783 Py_ssize_t nodelen;
783 Py_ssize_t nodelen;
784
784
785 if (PyInt_Check(value)) {
785 if (PyInt_Check(value)) {
786 long rev = PyInt_AS_LONG(value);
786 long rev = PyInt_AS_LONG(value);
787 return rev >= -1 && rev < index_length(self);
787 return rev >= -1 && rev < index_length(self);
788 }
788 }
789
789
790 if (!PyString_Check(value))
790 if (!PyString_Check(value))
791 return 0;
791 return 0;
792
792
793 node = PyString_AS_STRING(value);
793 node = PyString_AS_STRING(value);
794 nodelen = PyString_GET_SIZE(value);
794 nodelen = PyString_GET_SIZE(value);
795
795
796 switch (index_find_node(self, node, nodelen)) {
796 switch (index_find_node(self, node, nodelen)) {
797 case -3:
797 case -3:
798 return -1;
798 return -1;
799 case -2:
799 case -2:
800 return 0;
800 return 0;
801 default:
801 default:
802 return 1;
802 return 1;
803 }
803 }
804 }
804 }
805
805
806 /*
806 /*
807 * Invalidate any trie entries introduced by added revs.
807 * Invalidate any trie entries introduced by added revs.
808 */
808 */
809 static void nt_invalidate_added(indexObject *self, Py_ssize_t start)
809 static void nt_invalidate_added(indexObject *self, Py_ssize_t start)
810 {
810 {
811 Py_ssize_t i, len = PyList_GET_SIZE(self->added);
811 Py_ssize_t i, len = PyList_GET_SIZE(self->added);
812
812
813 for (i = start; i < len; i++) {
813 for (i = start; i < len; i++) {
814 PyObject *tuple = PyList_GET_ITEM(self->added, i);
814 PyObject *tuple = PyList_GET_ITEM(self->added, i);
815 PyObject *node = PyTuple_GET_ITEM(tuple, 7);
815 PyObject *node = PyTuple_GET_ITEM(tuple, 7);
816
816
817 nt_insert(self, PyString_AS_STRING(node), -1);
817 nt_insert(self, PyString_AS_STRING(node), -1);
818 }
818 }
819
819
820 if (start == 0) {
820 if (start == 0) {
821 Py_DECREF(self->added);
821 Py_DECREF(self->added);
822 self->added = NULL;
822 self->added = NULL;
823 }
823 }
824 }
824 }
825
825
826 /*
826 /*
827 * Delete a numeric range of revs, which must be at the end of the
827 * Delete a numeric range of revs, which must be at the end of the
828 * range, but exclude the sentinel nullid entry.
828 * range, but exclude the sentinel nullid entry.
829 */
829 */
830 static int index_slice_del(indexObject *self, PyObject *item)
830 static int index_slice_del(indexObject *self, PyObject *item)
831 {
831 {
832 Py_ssize_t start, stop, step, slicelength;
832 Py_ssize_t start, stop, step, slicelength;
833 Py_ssize_t length = index_length(self);
833 Py_ssize_t length = index_length(self);
834
834
835 if (PySlice_GetIndicesEx((PySliceObject*)item, length,
835 if (PySlice_GetIndicesEx((PySliceObject*)item, length,
836 &start, &stop, &step, &slicelength) < 0)
836 &start, &stop, &step, &slicelength) < 0)
837 return -1;
837 return -1;
838
838
839 if (slicelength <= 0)
839 if (slicelength <= 0)
840 return 0;
840 return 0;
841
841
842 if ((step < 0 && start < stop) || (step > 0 && start > stop))
842 if ((step < 0 && start < stop) || (step > 0 && start > stop))
843 stop = start;
843 stop = start;
844
844
845 if (step < 0) {
845 if (step < 0) {
846 stop = start + 1;
846 stop = start + 1;
847 start = stop + step*(slicelength - 1) - 1;
847 start = stop + step*(slicelength - 1) - 1;
848 step = -step;
848 step = -step;
849 }
849 }
850
850
851 if (step != 1) {
851 if (step != 1) {
852 PyErr_SetString(PyExc_ValueError,
852 PyErr_SetString(PyExc_ValueError,
853 "revlog index delete requires step size of 1");
853 "revlog index delete requires step size of 1");
854 return -1;
854 return -1;
855 }
855 }
856
856
857 if (stop != length - 1) {
857 if (stop != length - 1) {
858 PyErr_SetString(PyExc_IndexError,
858 PyErr_SetString(PyExc_IndexError,
859 "revlog index deletion indices are invalid");
859 "revlog index deletion indices are invalid");
860 return -1;
860 return -1;
861 }
861 }
862
862
863 if (start < self->length - 1) {
863 if (start < self->length - 1) {
864 if (self->nt) {
864 if (self->nt) {
865 Py_ssize_t i;
865 Py_ssize_t i;
866
866
867 for (i = start + 1; i < self->length - 1; i++) {
867 for (i = start + 1; i < self->length - 1; i++) {
868 const char *node = index_node(self, i);
868 const char *node = index_node(self, i);
869
869
870 if (node)
870 if (node)
871 nt_insert(self, node, -1);
871 nt_insert(self, node, -1);
872 }
872 }
873 if (self->added)
873 if (self->added)
874 nt_invalidate_added(self, 0);
874 nt_invalidate_added(self, 0);
875 if (self->ntrev > start)
875 if (self->ntrev > start)
876 self->ntrev = (int)start;
876 self->ntrev = (int)start;
877 }
877 }
878 self->length = start + 1;
878 self->length = start + 1;
879 return 0;
879 return 0;
880 }
880 }
881
881
882 if (self->nt) {
882 if (self->nt) {
883 nt_invalidate_added(self, start - self->length + 1);
883 nt_invalidate_added(self, start - self->length + 1);
884 if (self->ntrev > start)
884 if (self->ntrev > start)
885 self->ntrev = (int)start;
885 self->ntrev = (int)start;
886 }
886 }
887 return self->added
887 return self->added
888 ? PyList_SetSlice(self->added, start - self->length + 1,
888 ? PyList_SetSlice(self->added, start - self->length + 1,
889 PyList_GET_SIZE(self->added), NULL)
889 PyList_GET_SIZE(self->added), NULL)
890 : 0;
890 : 0;
891 }
891 }
892
892
893 /*
893 /*
894 * Supported ops:
894 * Supported ops:
895 *
895 *
896 * slice deletion
896 * slice deletion
897 * string assignment (extend node->rev mapping)
897 * string assignment (extend node->rev mapping)
898 * string deletion (shrink node->rev mapping)
898 * string deletion (shrink node->rev mapping)
899 */
899 */
900 static int index_assign_subscript(indexObject *self, PyObject *item,
900 static int index_assign_subscript(indexObject *self, PyObject *item,
901 PyObject *value)
901 PyObject *value)
902 {
902 {
903 char *node;
903 char *node;
904 Py_ssize_t nodelen;
904 Py_ssize_t nodelen;
905 long rev;
905 long rev;
906
906
907 if (PySlice_Check(item) && value == NULL)
907 if (PySlice_Check(item) && value == NULL)
908 return index_slice_del(self, item);
908 return index_slice_del(self, item);
909
909
910 if (node_check(item, &node, &nodelen) == -1)
910 if (node_check(item, &node, &nodelen) == -1)
911 return -1;
911 return -1;
912
912
913 if (value == NULL)
913 if (value == NULL)
914 return self->nt ? nt_insert(self, node, -1) : 0;
914 return self->nt ? nt_insert(self, node, -1) : 0;
915 rev = PyInt_AsLong(value);
915 rev = PyInt_AsLong(value);
916 if (rev > INT_MAX || rev < 0) {
916 if (rev > INT_MAX || rev < 0) {
917 if (!PyErr_Occurred())
917 if (!PyErr_Occurred())
918 PyErr_SetString(PyExc_ValueError, "rev out of range");
918 PyErr_SetString(PyExc_ValueError, "rev out of range");
919 return -1;
919 return -1;
920 }
920 }
921 return nt_insert(self, node, (int)rev);
921 return nt_insert(self, node, (int)rev);
922 }
922 }
923
923
924 /*
924 /*
925 * Find all RevlogNG entries in an index that has inline data. Update
925 * Find all RevlogNG entries in an index that has inline data. Update
926 * the optional "offsets" table with those entries.
926 * the optional "offsets" table with those entries.
927 */
927 */
928 static long inline_scan(indexObject *self, const char **offsets)
928 static long inline_scan(indexObject *self, const char **offsets)
929 {
929 {
930 const char *data = PyString_AS_STRING(self->data);
930 const char *data = PyString_AS_STRING(self->data);
931 const char *end = data + PyString_GET_SIZE(self->data);
931 const char *end = data + PyString_GET_SIZE(self->data);
932 const long hdrsize = 64;
932 const long hdrsize = 64;
933 long incr = hdrsize;
933 long incr = hdrsize;
934 Py_ssize_t len = 0;
934 Py_ssize_t len = 0;
935
935
936 while (data + hdrsize <= end) {
936 while (data + hdrsize <= end) {
937 uint32_t comp_len;
937 uint32_t comp_len;
938 const char *old_data;
938 const char *old_data;
939 /* 3rd element of header is length of compressed inline data */
939 /* 3rd element of header is length of compressed inline data */
940 comp_len = getbe32(data + 8);
940 comp_len = getbe32(data + 8);
941 incr = hdrsize + comp_len;
941 incr = hdrsize + comp_len;
942 if (incr < hdrsize)
942 if (incr < hdrsize)
943 break;
943 break;
944 if (offsets)
944 if (offsets)
945 offsets[len] = data;
945 offsets[len] = data;
946 len++;
946 len++;
947 old_data = data;
947 old_data = data;
948 data += incr;
948 data += incr;
949 if (data <= old_data)
949 if (data <= old_data)
950 break;
950 break;
951 }
951 }
952
952
953 if (data != end && data + hdrsize != end) {
953 if (data != end && data + hdrsize != end) {
954 if (!PyErr_Occurred())
954 if (!PyErr_Occurred())
955 PyErr_SetString(PyExc_ValueError, "corrupt index file");
955 PyErr_SetString(PyExc_ValueError, "corrupt index file");
956 return -1;
956 return -1;
957 }
957 }
958
958
959 return len;
959 return len;
960 }
960 }
961
961
962 static int index_init(indexObject *self, PyObject *args)
962 static int index_init(indexObject *self, PyObject *args)
963 {
963 {
964 PyObject *data_obj, *inlined_obj;
964 PyObject *data_obj, *inlined_obj;
965 Py_ssize_t size;
965 Py_ssize_t size;
966
966
967 if (!PyArg_ParseTuple(args, "OO", &data_obj, &inlined_obj))
967 if (!PyArg_ParseTuple(args, "OO", &data_obj, &inlined_obj))
968 return -1;
968 return -1;
969 if (!PyString_Check(data_obj)) {
969 if (!PyString_Check(data_obj)) {
970 PyErr_SetString(PyExc_TypeError, "data is not a string");
970 PyErr_SetString(PyExc_TypeError, "data is not a string");
971 return -1;
971 return -1;
972 }
972 }
973 size = PyString_GET_SIZE(data_obj);
973 size = PyString_GET_SIZE(data_obj);
974
974
975 self->inlined = inlined_obj && PyObject_IsTrue(inlined_obj);
975 self->inlined = inlined_obj && PyObject_IsTrue(inlined_obj);
976 self->data = data_obj;
976 self->data = data_obj;
977 self->cache = NULL;
977 self->cache = NULL;
978
978
979 self->added = NULL;
979 self->added = NULL;
980 self->offsets = NULL;
980 self->offsets = NULL;
981 self->nt = NULL;
981 self->nt = NULL;
982 self->ntlength = self->ntcapacity = 0;
982 self->ntlength = self->ntcapacity = 0;
983 self->ntdepth = self->ntsplits = 0;
983 self->ntdepth = self->ntsplits = 0;
984 self->ntlookups = self->ntmisses = 0;
984 self->ntlookups = self->ntmisses = 0;
985 self->ntrev = -1;
985 self->ntrev = -1;
986 Py_INCREF(self->data);
986
987
987 if (self->inlined) {
988 if (self->inlined) {
988 long len = inline_scan(self, NULL);
989 long len = inline_scan(self, NULL);
989 if (len == -1)
990 if (len == -1)
990 goto bail;
991 goto bail;
991 self->raw_length = len;
992 self->raw_length = len;
992 self->length = len + 1;
993 self->length = len + 1;
993 } else {
994 } else {
994 if (size % 64) {
995 if (size % 64) {
995 PyErr_SetString(PyExc_ValueError, "corrupt index file");
996 PyErr_SetString(PyExc_ValueError, "corrupt index file");
996 goto bail;
997 goto bail;
997 }
998 }
998 self->raw_length = size / 64;
999 self->raw_length = size / 64;
999 self->length = self->raw_length + 1;
1000 self->length = self->raw_length + 1;
1000 }
1001 }
1001 Py_INCREF(self->data);
1002
1002
1003 return 0;
1003 return 0;
1004 bail:
1004 bail:
1005 return -1;
1005 return -1;
1006 }
1006 }
1007
1007
1008 static PyObject *index_nodemap(indexObject *self)
1008 static PyObject *index_nodemap(indexObject *self)
1009 {
1009 {
1010 Py_INCREF(self);
1010 Py_INCREF(self);
1011 return (PyObject *)self;
1011 return (PyObject *)self;
1012 }
1012 }
1013
1013
1014 static void index_dealloc(indexObject *self)
1014 static void index_dealloc(indexObject *self)
1015 {
1015 {
1016 _index_clearcaches(self);
1016 _index_clearcaches(self);
1017 Py_DECREF(self->data);
1017 Py_DECREF(self->data);
1018 Py_XDECREF(self->added);
1018 Py_XDECREF(self->added);
1019 PyObject_Del(self);
1019 PyObject_Del(self);
1020 }
1020 }
1021
1021
1022 static PySequenceMethods index_sequence_methods = {
1022 static PySequenceMethods index_sequence_methods = {
1023 (lenfunc)index_length, /* sq_length */
1023 (lenfunc)index_length, /* sq_length */
1024 0, /* sq_concat */
1024 0, /* sq_concat */
1025 0, /* sq_repeat */
1025 0, /* sq_repeat */
1026 (ssizeargfunc)index_get, /* sq_item */
1026 (ssizeargfunc)index_get, /* sq_item */
1027 0, /* sq_slice */
1027 0, /* sq_slice */
1028 0, /* sq_ass_item */
1028 0, /* sq_ass_item */
1029 0, /* sq_ass_slice */
1029 0, /* sq_ass_slice */
1030 (objobjproc)index_contains, /* sq_contains */
1030 (objobjproc)index_contains, /* sq_contains */
1031 };
1031 };
1032
1032
1033 static PyMappingMethods index_mapping_methods = {
1033 static PyMappingMethods index_mapping_methods = {
1034 (lenfunc)index_length, /* mp_length */
1034 (lenfunc)index_length, /* mp_length */
1035 (binaryfunc)index_getitem, /* mp_subscript */
1035 (binaryfunc)index_getitem, /* mp_subscript */
1036 (objobjargproc)index_assign_subscript, /* mp_ass_subscript */
1036 (objobjargproc)index_assign_subscript, /* mp_ass_subscript */
1037 };
1037 };
1038
1038
1039 static PyMethodDef index_methods[] = {
1039 static PyMethodDef index_methods[] = {
1040 {"clearcaches", (PyCFunction)index_clearcaches, METH_NOARGS,
1040 {"clearcaches", (PyCFunction)index_clearcaches, METH_NOARGS,
1041 "clear the index caches"},
1041 "clear the index caches"},
1042 {"get", (PyCFunction)index_m_get, METH_VARARGS,
1042 {"get", (PyCFunction)index_m_get, METH_VARARGS,
1043 "get an index entry"},
1043 "get an index entry"},
1044 {"insert", (PyCFunction)index_insert, METH_VARARGS,
1044 {"insert", (PyCFunction)index_insert, METH_VARARGS,
1045 "insert an index entry"},
1045 "insert an index entry"},
1046 {"stats", (PyCFunction)index_stats, METH_NOARGS,
1046 {"stats", (PyCFunction)index_stats, METH_NOARGS,
1047 "stats for the index"},
1047 "stats for the index"},
1048 {NULL} /* Sentinel */
1048 {NULL} /* Sentinel */
1049 };
1049 };
1050
1050
1051 static PyGetSetDef index_getset[] = {
1051 static PyGetSetDef index_getset[] = {
1052 {"nodemap", (getter)index_nodemap, NULL, "nodemap", NULL},
1052 {"nodemap", (getter)index_nodemap, NULL, "nodemap", NULL},
1053 {NULL} /* Sentinel */
1053 {NULL} /* Sentinel */
1054 };
1054 };
1055
1055
1056 static PyTypeObject indexType = {
1056 static PyTypeObject indexType = {
1057 PyObject_HEAD_INIT(NULL)
1057 PyObject_HEAD_INIT(NULL)
1058 0, /* ob_size */
1058 0, /* ob_size */
1059 "parsers.index", /* tp_name */
1059 "parsers.index", /* tp_name */
1060 sizeof(indexObject), /* tp_basicsize */
1060 sizeof(indexObject), /* tp_basicsize */
1061 0, /* tp_itemsize */
1061 0, /* tp_itemsize */
1062 (destructor)index_dealloc, /* tp_dealloc */
1062 (destructor)index_dealloc, /* tp_dealloc */
1063 0, /* tp_print */
1063 0, /* tp_print */
1064 0, /* tp_getattr */
1064 0, /* tp_getattr */
1065 0, /* tp_setattr */
1065 0, /* tp_setattr */
1066 0, /* tp_compare */
1066 0, /* tp_compare */
1067 0, /* tp_repr */
1067 0, /* tp_repr */
1068 0, /* tp_as_number */
1068 0, /* tp_as_number */
1069 &index_sequence_methods, /* tp_as_sequence */
1069 &index_sequence_methods, /* tp_as_sequence */
1070 &index_mapping_methods, /* tp_as_mapping */
1070 &index_mapping_methods, /* tp_as_mapping */
1071 0, /* tp_hash */
1071 0, /* tp_hash */
1072 0, /* tp_call */
1072 0, /* tp_call */
1073 0, /* tp_str */
1073 0, /* tp_str */
1074 0, /* tp_getattro */
1074 0, /* tp_getattro */
1075 0, /* tp_setattro */
1075 0, /* tp_setattro */
1076 0, /* tp_as_buffer */
1076 0, /* tp_as_buffer */
1077 Py_TPFLAGS_DEFAULT, /* tp_flags */
1077 Py_TPFLAGS_DEFAULT, /* tp_flags */
1078 "revlog index", /* tp_doc */
1078 "revlog index", /* tp_doc */
1079 0, /* tp_traverse */
1079 0, /* tp_traverse */
1080 0, /* tp_clear */
1080 0, /* tp_clear */
1081 0, /* tp_richcompare */
1081 0, /* tp_richcompare */
1082 0, /* tp_weaklistoffset */
1082 0, /* tp_weaklistoffset */
1083 0, /* tp_iter */
1083 0, /* tp_iter */
1084 0, /* tp_iternext */
1084 0, /* tp_iternext */
1085 index_methods, /* tp_methods */
1085 index_methods, /* tp_methods */
1086 0, /* tp_members */
1086 0, /* tp_members */
1087 index_getset, /* tp_getset */
1087 index_getset, /* tp_getset */
1088 0, /* tp_base */
1088 0, /* tp_base */
1089 0, /* tp_dict */
1089 0, /* tp_dict */
1090 0, /* tp_descr_get */
1090 0, /* tp_descr_get */
1091 0, /* tp_descr_set */
1091 0, /* tp_descr_set */
1092 0, /* tp_dictoffset */
1092 0, /* tp_dictoffset */
1093 (initproc)index_init, /* tp_init */
1093 (initproc)index_init, /* tp_init */
1094 0, /* tp_alloc */
1094 0, /* tp_alloc */
1095 PyType_GenericNew, /* tp_new */
1095 PyType_GenericNew, /* tp_new */
1096 };
1096 };
1097
1097
1098 /*
1098 /*
1099 * returns a tuple of the form (index, index, cache) with elements as
1099 * returns a tuple of the form (index, index, cache) with elements as
1100 * follows:
1100 * follows:
1101 *
1101 *
1102 * index: an index object that lazily parses RevlogNG records
1102 * index: an index object that lazily parses RevlogNG records
1103 * cache: if data is inlined, a tuple (index_file_content, 0), else None
1103 * cache: if data is inlined, a tuple (index_file_content, 0), else None
1104 *
1104 *
1105 * added complications are for backwards compatibility
1105 * added complications are for backwards compatibility
1106 */
1106 */
1107 static PyObject *parse_index2(PyObject *self, PyObject *args)
1107 static PyObject *parse_index2(PyObject *self, PyObject *args)
1108 {
1108 {
1109 PyObject *tuple = NULL, *cache = NULL;
1109 PyObject *tuple = NULL, *cache = NULL;
1110 indexObject *idx;
1110 indexObject *idx;
1111 int ret;
1111 int ret;
1112
1112
1113 idx = PyObject_New(indexObject, &indexType);
1113 idx = PyObject_New(indexObject, &indexType);
1114 if (idx == NULL)
1114 if (idx == NULL)
1115 goto bail;
1115 goto bail;
1116
1116
1117 ret = index_init(idx, args);
1117 ret = index_init(idx, args);
1118 if (ret == -1)
1118 if (ret == -1)
1119 goto bail;
1119 goto bail;
1120
1120
1121 if (idx->inlined) {
1121 if (idx->inlined) {
1122 cache = Py_BuildValue("iO", 0, idx->data);
1122 cache = Py_BuildValue("iO", 0, idx->data);
1123 if (cache == NULL)
1123 if (cache == NULL)
1124 goto bail;
1124 goto bail;
1125 } else {
1125 } else {
1126 cache = Py_None;
1126 cache = Py_None;
1127 Py_INCREF(cache);
1127 Py_INCREF(cache);
1128 }
1128 }
1129
1129
1130 tuple = Py_BuildValue("NN", idx, cache);
1130 tuple = Py_BuildValue("NN", idx, cache);
1131 if (!tuple)
1131 if (!tuple)
1132 goto bail;
1132 goto bail;
1133 return tuple;
1133 return tuple;
1134
1134
1135 bail:
1135 bail:
1136 Py_XDECREF(idx);
1136 Py_XDECREF(idx);
1137 Py_XDECREF(cache);
1137 Py_XDECREF(cache);
1138 Py_XDECREF(tuple);
1138 Py_XDECREF(tuple);
1139 return NULL;
1139 return NULL;
1140 }
1140 }
1141
1141
1142 static char parsers_doc[] = "Efficient content parsing.";
1142 static char parsers_doc[] = "Efficient content parsing.";
1143
1143
1144 static PyMethodDef methods[] = {
1144 static PyMethodDef methods[] = {
1145 {"parse_manifest", parse_manifest, METH_VARARGS, "parse a manifest\n"},
1145 {"parse_manifest", parse_manifest, METH_VARARGS, "parse a manifest\n"},
1146 {"parse_dirstate", parse_dirstate, METH_VARARGS, "parse a dirstate\n"},
1146 {"parse_dirstate", parse_dirstate, METH_VARARGS, "parse a dirstate\n"},
1147 {"parse_index2", parse_index2, METH_VARARGS, "parse a revlog index\n"},
1147 {"parse_index2", parse_index2, METH_VARARGS, "parse a revlog index\n"},
1148 {NULL, NULL}
1148 {NULL, NULL}
1149 };
1149 };
1150
1150
1151 static void module_init(PyObject *mod)
1151 static void module_init(PyObject *mod)
1152 {
1152 {
1153 if (PyType_Ready(&indexType) < 0)
1153 if (PyType_Ready(&indexType) < 0)
1154 return;
1154 return;
1155 Py_INCREF(&indexType);
1155 Py_INCREF(&indexType);
1156
1156
1157 PyModule_AddObject(mod, "index", (PyObject *)&indexType);
1157 PyModule_AddObject(mod, "index", (PyObject *)&indexType);
1158
1158
1159 nullentry = Py_BuildValue("iiiiiiis#", 0, 0, 0,
1159 nullentry = Py_BuildValue("iiiiiiis#", 0, 0, 0,
1160 -1, -1, -1, -1, nullid, 20);
1160 -1, -1, -1, -1, nullid, 20);
1161 if (nullentry)
1161 if (nullentry)
1162 PyObject_GC_UnTrack(nullentry);
1162 PyObject_GC_UnTrack(nullentry);
1163 }
1163 }
1164
1164
1165 #ifdef IS_PY3K
1165 #ifdef IS_PY3K
1166 static struct PyModuleDef parsers_module = {
1166 static struct PyModuleDef parsers_module = {
1167 PyModuleDef_HEAD_INIT,
1167 PyModuleDef_HEAD_INIT,
1168 "parsers",
1168 "parsers",
1169 parsers_doc,
1169 parsers_doc,
1170 -1,
1170 -1,
1171 methods
1171 methods
1172 };
1172 };
1173
1173
1174 PyMODINIT_FUNC PyInit_parsers(void)
1174 PyMODINIT_FUNC PyInit_parsers(void)
1175 {
1175 {
1176 PyObject *mod = PyModule_Create(&parsers_module);
1176 PyObject *mod = PyModule_Create(&parsers_module);
1177 module_init(mod);
1177 module_init(mod);
1178 return mod;
1178 return mod;
1179 }
1179 }
1180 #else
1180 #else
1181 PyMODINIT_FUNC initparsers(void)
1181 PyMODINIT_FUNC initparsers(void)
1182 {
1182 {
1183 PyObject *mod = Py_InitModule3("parsers", methods, parsers_doc);
1183 PyObject *mod = Py_InitModule3("parsers", methods, parsers_doc);
1184 module_init(mod);
1184 module_init(mod);
1185 }
1185 }
1186 #endif
1186 #endif
General Comments 0
You need to be logged in to leave comments. Login now