##// END OF EJS Templates
parsers: fix refcount leak, simplify init of index (issue3417)...
Bryan O'Sullivan -
r16572:8d44b5a2 stable
parent child Browse files
Show More
@@ -1,1195 +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 Py_XDECREF(self->cache[i]);
473 if (self->cache[i]) {
474 Py_DECREF(self->cache[i]);
474 self->cache[i] = NULL;
475 self->cache[i] = NULL;
475 }
476 }
477 }
476 free(self->cache);
478 free(self->cache);
477 self->cache = NULL;
479 self->cache = NULL;
478 }
480 }
479 if (self->offsets) {
481 if (self->offsets) {
480 free(self->offsets);
482 free(self->offsets);
481 self->offsets = NULL;
483 self->offsets = NULL;
482 }
484 }
483 if (self->nt) {
485 if (self->nt) {
484 free(self->nt);
486 free(self->nt);
485 self->nt = NULL;
487 self->nt = NULL;
486 }
488 }
487 }
489 }
488
490
489 static PyObject *index_clearcaches(indexObject *self)
491 static PyObject *index_clearcaches(indexObject *self)
490 {
492 {
491 _index_clearcaches(self);
493 _index_clearcaches(self);
492 self->ntlength = self->ntcapacity = 0;
494 self->ntlength = self->ntcapacity = 0;
493 self->ntdepth = self->ntsplits = 0;
495 self->ntdepth = self->ntsplits = 0;
494 self->ntrev = -1;
496 self->ntrev = -1;
495 self->ntlookups = self->ntmisses = 0;
497 self->ntlookups = self->ntmisses = 0;
496 Py_RETURN_NONE;
498 Py_RETURN_NONE;
497 }
499 }
498
500
499 static PyObject *index_stats(indexObject *self)
501 static PyObject *index_stats(indexObject *self)
500 {
502 {
501 PyObject *obj = PyDict_New();
503 PyObject *obj = PyDict_New();
502
504
503 if (obj == NULL)
505 if (obj == NULL)
504 return NULL;
506 return NULL;
505
507
506 #define istat(__n, __d) \
508 #define istat(__n, __d) \
507 if (PyDict_SetItemString(obj, __d, PyInt_FromLong(self->__n)) == -1) \
509 if (PyDict_SetItemString(obj, __d, PyInt_FromLong(self->__n)) == -1) \
508 goto bail;
510 goto bail;
509
511
510 if (self->added) {
512 if (self->added) {
511 Py_ssize_t len = PyList_GET_SIZE(self->added);
513 Py_ssize_t len = PyList_GET_SIZE(self->added);
512 if (PyDict_SetItemString(obj, "index entries added",
514 if (PyDict_SetItemString(obj, "index entries added",
513 PyInt_FromLong(len)) == -1)
515 PyInt_FromLong(len)) == -1)
514 goto bail;
516 goto bail;
515 }
517 }
516
518
517 if (self->raw_length != self->length - 1)
519 if (self->raw_length != self->length - 1)
518 istat(raw_length, "revs on disk");
520 istat(raw_length, "revs on disk");
519 istat(length, "revs in memory");
521 istat(length, "revs in memory");
520 istat(ntcapacity, "node trie capacity");
522 istat(ntcapacity, "node trie capacity");
521 istat(ntdepth, "node trie depth");
523 istat(ntdepth, "node trie depth");
522 istat(ntlength, "node trie count");
524 istat(ntlength, "node trie count");
523 istat(ntlookups, "node trie lookups");
525 istat(ntlookups, "node trie lookups");
524 istat(ntmisses, "node trie misses");
526 istat(ntmisses, "node trie misses");
525 istat(ntrev, "node trie last rev scanned");
527 istat(ntrev, "node trie last rev scanned");
526 istat(ntsplits, "node trie splits");
528 istat(ntsplits, "node trie splits");
527
529
528 #undef istat
530 #undef istat
529
531
530 return obj;
532 return obj;
531
533
532 bail:
534 bail:
533 Py_XDECREF(obj);
535 Py_XDECREF(obj);
534 return NULL;
536 return NULL;
535 }
537 }
536
538
537 static inline int nt_level(const char *node, int level)
539 static inline int nt_level(const char *node, int level)
538 {
540 {
539 int v = node[level>>1];
541 int v = node[level>>1];
540 if (!(level & 1))
542 if (!(level & 1))
541 v >>= 4;
543 v >>= 4;
542 return v & 0xf;
544 return v & 0xf;
543 }
545 }
544
546
545 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)
546 {
548 {
547 int level, off;
549 int level, off;
548
550
549 if (nodelen == 20 && node[0] == '\0' && memcmp(node, nullid, 20) == 0)
551 if (nodelen == 20 && node[0] == '\0' && memcmp(node, nullid, 20) == 0)
550 return -1;
552 return -1;
551
553
552 if (self->nt == NULL)
554 if (self->nt == NULL)
553 return -2;
555 return -2;
554
556
555 for (level = off = 0; level < nodelen; level++) {
557 for (level = off = 0; level < nodelen; level++) {
556 int k = nt_level(node, level);
558 int k = nt_level(node, level);
557 nodetree *n = &self->nt[off];
559 nodetree *n = &self->nt[off];
558 int v = n->children[k];
560 int v = n->children[k];
559
561
560 if (v < 0) {
562 if (v < 0) {
561 const char *n;
563 const char *n;
562 v = -v - 1;
564 v = -v - 1;
563 n = index_node(self, v);
565 n = index_node(self, v);
564 if (n == NULL)
566 if (n == NULL)
565 return -2;
567 return -2;
566 return memcmp(node, n, nodelen > 20 ? 20 : nodelen)
568 return memcmp(node, n, nodelen > 20 ? 20 : nodelen)
567 ? -2 : v;
569 ? -2 : v;
568 }
570 }
569 if (v == 0)
571 if (v == 0)
570 return -2;
572 return -2;
571 off = v;
573 off = v;
572 }
574 }
573 return -2;
575 return -2;
574 }
576 }
575
577
576 static int nt_new(indexObject *self)
578 static int nt_new(indexObject *self)
577 {
579 {
578 if (self->ntlength == self->ntcapacity) {
580 if (self->ntlength == self->ntcapacity) {
579 self->ntcapacity *= 2;
581 self->ntcapacity *= 2;
580 self->nt = realloc(self->nt,
582 self->nt = realloc(self->nt,
581 self->ntcapacity * sizeof(nodetree));
583 self->ntcapacity * sizeof(nodetree));
582 if (self->nt == NULL) {
584 if (self->nt == NULL) {
583 PyErr_SetString(PyExc_MemoryError, "out of memory");
585 PyErr_SetString(PyExc_MemoryError, "out of memory");
584 return -1;
586 return -1;
585 }
587 }
586 memset(&self->nt[self->ntlength], 0,
588 memset(&self->nt[self->ntlength], 0,
587 sizeof(nodetree) * (self->ntcapacity - self->ntlength));
589 sizeof(nodetree) * (self->ntcapacity - self->ntlength));
588 }
590 }
589 return self->ntlength++;
591 return self->ntlength++;
590 }
592 }
591
593
592 static int nt_insert(indexObject *self, const char *node, int rev)
594 static int nt_insert(indexObject *self, const char *node, int rev)
593 {
595 {
594 int level = 0;
596 int level = 0;
595 int off = 0;
597 int off = 0;
596
598
597 while (level < 20) {
599 while (level < 20) {
598 int k = nt_level(node, level);
600 int k = nt_level(node, level);
599 nodetree *n;
601 nodetree *n;
600 int v;
602 int v;
601
603
602 n = &self->nt[off];
604 n = &self->nt[off];
603 v = n->children[k];
605 v = n->children[k];
604
606
605 if (v == 0) {
607 if (v == 0) {
606 n->children[k] = -rev - 1;
608 n->children[k] = -rev - 1;
607 return 0;
609 return 0;
608 }
610 }
609 if (v < 0) {
611 if (v < 0) {
610 const char *oldnode = index_node(self, -v - 1);
612 const char *oldnode = index_node(self, -v - 1);
611 int noff;
613 int noff;
612
614
613 if (!oldnode || !memcmp(oldnode, node, 20)) {
615 if (!oldnode || !memcmp(oldnode, node, 20)) {
614 n->children[k] = -rev - 1;
616 n->children[k] = -rev - 1;
615 return 0;
617 return 0;
616 }
618 }
617 noff = nt_new(self);
619 noff = nt_new(self);
618 if (noff == -1)
620 if (noff == -1)
619 return -1;
621 return -1;
620 /* self->nt may have been changed by realloc */
622 /* self->nt may have been changed by realloc */
621 self->nt[off].children[k] = noff;
623 self->nt[off].children[k] = noff;
622 off = noff;
624 off = noff;
623 n = &self->nt[off];
625 n = &self->nt[off];
624 n->children[nt_level(oldnode, ++level)] = v;
626 n->children[nt_level(oldnode, ++level)] = v;
625 if (level > self->ntdepth)
627 if (level > self->ntdepth)
626 self->ntdepth = level;
628 self->ntdepth = level;
627 self->ntsplits += 1;
629 self->ntsplits += 1;
628 } else {
630 } else {
629 level += 1;
631 level += 1;
630 off = v;
632 off = v;
631 }
633 }
632 }
634 }
633
635
634 return -1;
636 return -1;
635 }
637 }
636
638
637 /*
639 /*
638 * Return values:
640 * Return values:
639 *
641 *
640 * -3: error (exception set)
642 * -3: error (exception set)
641 * -2: not found (no exception set)
643 * -2: not found (no exception set)
642 * rest: valid rev
644 * rest: valid rev
643 */
645 */
644 static int index_find_node(indexObject *self,
646 static int index_find_node(indexObject *self,
645 const char *node, Py_ssize_t nodelen)
647 const char *node, Py_ssize_t nodelen)
646 {
648 {
647 int rev;
649 int rev;
648
650
649 self->ntlookups++;
651 self->ntlookups++;
650 rev = nt_find(self, node, nodelen);
652 rev = nt_find(self, node, nodelen);
651 if (rev >= -1)
653 if (rev >= -1)
652 return rev;
654 return rev;
653
655
654 if (self->nt == NULL) {
656 if (self->nt == NULL) {
655 self->ntcapacity = self->raw_length < 4
657 self->ntcapacity = self->raw_length < 4
656 ? 4 : self->raw_length / 2;
658 ? 4 : self->raw_length / 2;
657 self->nt = calloc(self->ntcapacity, sizeof(nodetree));
659 self->nt = calloc(self->ntcapacity, sizeof(nodetree));
658 if (self->nt == NULL) {
660 if (self->nt == NULL) {
659 PyErr_SetString(PyExc_MemoryError, "out of memory");
661 PyErr_SetString(PyExc_MemoryError, "out of memory");
660 return -3;
662 return -3;
661 }
663 }
662 self->ntlength = 1;
664 self->ntlength = 1;
663 self->ntrev = (int)index_length(self) - 1;
665 self->ntrev = (int)index_length(self) - 1;
664 self->ntlookups = 1;
666 self->ntlookups = 1;
665 self->ntmisses = 0;
667 self->ntmisses = 0;
666 }
668 }
667
669
668 /*
670 /*
669 * For the first handful of lookups, we scan the entire index,
671 * For the first handful of lookups, we scan the entire index,
670 * and cache only the matching nodes. This optimizes for cases
672 * and cache only the matching nodes. This optimizes for cases
671 * like "hg tip", where only a few nodes are accessed.
673 * like "hg tip", where only a few nodes are accessed.
672 *
674 *
673 * After that, we cache every node we visit, using a single
675 * After that, we cache every node we visit, using a single
674 * scan amortized over multiple lookups. This gives the best
676 * scan amortized over multiple lookups. This gives the best
675 * bulk performance, e.g. for "hg log".
677 * bulk performance, e.g. for "hg log".
676 */
678 */
677 if (self->ntmisses++ < 4) {
679 if (self->ntmisses++ < 4) {
678 for (rev = self->ntrev - 1; rev >= 0; rev--) {
680 for (rev = self->ntrev - 1; rev >= 0; rev--) {
679 const char *n = index_node(self, rev);
681 const char *n = index_node(self, rev);
680 if (n == NULL)
682 if (n == NULL)
681 return -2;
683 return -2;
682 if (memcmp(node, n, nodelen > 20 ? 20 : nodelen) == 0) {
684 if (memcmp(node, n, nodelen > 20 ? 20 : nodelen) == 0) {
683 if (nt_insert(self, n, rev) == -1)
685 if (nt_insert(self, n, rev) == -1)
684 return -3;
686 return -3;
685 break;
687 break;
686 }
688 }
687 }
689 }
688 } else {
690 } else {
689 for (rev = self->ntrev - 1; rev >= 0; rev--) {
691 for (rev = self->ntrev - 1; rev >= 0; rev--) {
690 const char *n = index_node(self, rev);
692 const char *n = index_node(self, rev);
691 if (n == NULL)
693 if (n == NULL)
692 return -2;
694 return -2;
693 if (nt_insert(self, n, rev) == -1)
695 if (nt_insert(self, n, rev) == -1)
694 return -3;
696 return -3;
695 if (memcmp(node, n, nodelen > 20 ? 20 : nodelen) == 0) {
697 if (memcmp(node, n, nodelen > 20 ? 20 : nodelen) == 0) {
696 break;
698 break;
697 }
699 }
698 }
700 }
699 self->ntrev = rev;
701 self->ntrev = rev;
700 }
702 }
701
703
702 if (rev >= 0)
704 if (rev >= 0)
703 return rev;
705 return rev;
704 return -2;
706 return -2;
705 }
707 }
706
708
707 static PyObject *raise_revlog_error(void)
709 static PyObject *raise_revlog_error(void)
708 {
710 {
709 static PyObject *errclass;
711 static PyObject *errclass;
710 PyObject *mod = NULL, *errobj;
712 PyObject *mod = NULL, *errobj;
711
713
712 if (errclass == NULL) {
714 if (errclass == NULL) {
713 PyObject *dict;
715 PyObject *dict;
714
716
715 mod = PyImport_ImportModule("mercurial.error");
717 mod = PyImport_ImportModule("mercurial.error");
716 if (mod == NULL)
718 if (mod == NULL)
717 goto classfail;
719 goto classfail;
718
720
719 dict = PyModule_GetDict(mod);
721 dict = PyModule_GetDict(mod);
720 if (dict == NULL)
722 if (dict == NULL)
721 goto classfail;
723 goto classfail;
722
724
723 errclass = PyDict_GetItemString(dict, "RevlogError");
725 errclass = PyDict_GetItemString(dict, "RevlogError");
724 if (errclass == NULL) {
726 if (errclass == NULL) {
725 PyErr_SetString(PyExc_SystemError,
727 PyErr_SetString(PyExc_SystemError,
726 "could not find RevlogError");
728 "could not find RevlogError");
727 goto classfail;
729 goto classfail;
728 }
730 }
729 Py_INCREF(errclass);
731 Py_INCREF(errclass);
730 }
732 }
731
733
732 errobj = PyObject_CallFunction(errclass, NULL);
734 errobj = PyObject_CallFunction(errclass, NULL);
733 if (errobj == NULL)
735 if (errobj == NULL)
734 return NULL;
736 return NULL;
735 PyErr_SetObject(errclass, errobj);
737 PyErr_SetObject(errclass, errobj);
736 return errobj;
738 return errobj;
737
739
738 classfail:
740 classfail:
739 Py_XDECREF(mod);
741 Py_XDECREF(mod);
740 return NULL;
742 return NULL;
741 }
743 }
742
744
743 static PyObject *index_getitem(indexObject *self, PyObject *value)
745 static PyObject *index_getitem(indexObject *self, PyObject *value)
744 {
746 {
745 char *node;
747 char *node;
746 Py_ssize_t nodelen;
748 Py_ssize_t nodelen;
747 int rev;
749 int rev;
748
750
749 if (PyInt_Check(value))
751 if (PyInt_Check(value))
750 return index_get(self, PyInt_AS_LONG(value));
752 return index_get(self, PyInt_AS_LONG(value));
751
753
752 if (PyString_AsStringAndSize(value, &node, &nodelen) == -1)
754 if (PyString_AsStringAndSize(value, &node, &nodelen) == -1)
753 return NULL;
755 return NULL;
754 rev = index_find_node(self, node, nodelen);
756 rev = index_find_node(self, node, nodelen);
755 if (rev >= -1)
757 if (rev >= -1)
756 return PyInt_FromLong(rev);
758 return PyInt_FromLong(rev);
757 if (rev == -2)
759 if (rev == -2)
758 raise_revlog_error();
760 raise_revlog_error();
759 return NULL;
761 return NULL;
760 }
762 }
761
763
762 static PyObject *index_m_get(indexObject *self, PyObject *args)
764 static PyObject *index_m_get(indexObject *self, PyObject *args)
763 {
765 {
764 char *node;
766 char *node;
765 int nodelen, rev;
767 int nodelen, rev;
766
768
767 if (!PyArg_ParseTuple(args, "s#", &node, &nodelen))
769 if (!PyArg_ParseTuple(args, "s#", &node, &nodelen))
768 return NULL;
770 return NULL;
769
771
770 rev = index_find_node(self, node, nodelen);
772 rev = index_find_node(self, node, nodelen);
771 if (rev == -3)
773 if (rev == -3)
772 return NULL;
774 return NULL;
773 if (rev == -2)
775 if (rev == -2)
774 Py_RETURN_NONE;
776 Py_RETURN_NONE;
775 return PyInt_FromLong(rev);
777 return PyInt_FromLong(rev);
776 }
778 }
777
779
778 static int index_contains(indexObject *self, PyObject *value)
780 static int index_contains(indexObject *self, PyObject *value)
779 {
781 {
780 char *node;
782 char *node;
781 Py_ssize_t nodelen;
783 Py_ssize_t nodelen;
782
784
783 if (PyInt_Check(value)) {
785 if (PyInt_Check(value)) {
784 long rev = PyInt_AS_LONG(value);
786 long rev = PyInt_AS_LONG(value);
785 return rev >= -1 && rev < index_length(self);
787 return rev >= -1 && rev < index_length(self);
786 }
788 }
787
789
788 if (!PyString_Check(value))
790 if (!PyString_Check(value))
789 return 0;
791 return 0;
790
792
791 node = PyString_AS_STRING(value);
793 node = PyString_AS_STRING(value);
792 nodelen = PyString_GET_SIZE(value);
794 nodelen = PyString_GET_SIZE(value);
793
795
794 switch (index_find_node(self, node, nodelen)) {
796 switch (index_find_node(self, node, nodelen)) {
795 case -3:
797 case -3:
796 return -1;
798 return -1;
797 case -2:
799 case -2:
798 return 0;
800 return 0;
799 default:
801 default:
800 return 1;
802 return 1;
801 }
803 }
802 }
804 }
803
805
804 /*
806 /*
805 * Invalidate any trie entries introduced by added revs.
807 * Invalidate any trie entries introduced by added revs.
806 */
808 */
807 static void nt_invalidate_added(indexObject *self, Py_ssize_t start)
809 static void nt_invalidate_added(indexObject *self, Py_ssize_t start)
808 {
810 {
809 Py_ssize_t i, len = PyList_GET_SIZE(self->added);
811 Py_ssize_t i, len = PyList_GET_SIZE(self->added);
810
812
811 for (i = start; i < len; i++) {
813 for (i = start; i < len; i++) {
812 PyObject *tuple = PyList_GET_ITEM(self->added, i);
814 PyObject *tuple = PyList_GET_ITEM(self->added, i);
813 PyObject *node = PyTuple_GET_ITEM(tuple, 7);
815 PyObject *node = PyTuple_GET_ITEM(tuple, 7);
814
816
815 nt_insert(self, PyString_AS_STRING(node), -1);
817 nt_insert(self, PyString_AS_STRING(node), -1);
816 }
818 }
817
819
818 if (start == 0) {
820 if (start == 0) {
819 Py_DECREF(self->added);
821 Py_DECREF(self->added);
820 self->added = NULL;
822 self->added = NULL;
821 }
823 }
822 }
824 }
823
825
824 /*
826 /*
825 * 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
826 * range, but exclude the sentinel nullid entry.
828 * range, but exclude the sentinel nullid entry.
827 */
829 */
828 static int index_slice_del(indexObject *self, PyObject *item)
830 static int index_slice_del(indexObject *self, PyObject *item)
829 {
831 {
830 Py_ssize_t start, stop, step, slicelength;
832 Py_ssize_t start, stop, step, slicelength;
831 Py_ssize_t length = index_length(self);
833 Py_ssize_t length = index_length(self);
832
834
833 if (PySlice_GetIndicesEx((PySliceObject*)item, length,
835 if (PySlice_GetIndicesEx((PySliceObject*)item, length,
834 &start, &stop, &step, &slicelength) < 0)
836 &start, &stop, &step, &slicelength) < 0)
835 return -1;
837 return -1;
836
838
837 if (slicelength <= 0)
839 if (slicelength <= 0)
838 return 0;
840 return 0;
839
841
840 if ((step < 0 && start < stop) || (step > 0 && start > stop))
842 if ((step < 0 && start < stop) || (step > 0 && start > stop))
841 stop = start;
843 stop = start;
842
844
843 if (step < 0) {
845 if (step < 0) {
844 stop = start + 1;
846 stop = start + 1;
845 start = stop + step*(slicelength - 1) - 1;
847 start = stop + step*(slicelength - 1) - 1;
846 step = -step;
848 step = -step;
847 }
849 }
848
850
849 if (step != 1) {
851 if (step != 1) {
850 PyErr_SetString(PyExc_ValueError,
852 PyErr_SetString(PyExc_ValueError,
851 "revlog index delete requires step size of 1");
853 "revlog index delete requires step size of 1");
852 return -1;
854 return -1;
853 }
855 }
854
856
855 if (stop != length - 1) {
857 if (stop != length - 1) {
856 PyErr_SetString(PyExc_IndexError,
858 PyErr_SetString(PyExc_IndexError,
857 "revlog index deletion indices are invalid");
859 "revlog index deletion indices are invalid");
858 return -1;
860 return -1;
859 }
861 }
860
862
861 if (start < self->length - 1) {
863 if (start < self->length - 1) {
862 if (self->nt) {
864 if (self->nt) {
863 Py_ssize_t i;
865 Py_ssize_t i;
864
866
865 for (i = start + 1; i < self->length - 1; i++) {
867 for (i = start + 1; i < self->length - 1; i++) {
866 const char *node = index_node(self, i);
868 const char *node = index_node(self, i);
867
869
868 if (node)
870 if (node)
869 nt_insert(self, node, -1);
871 nt_insert(self, node, -1);
870 }
872 }
871 if (self->added)
873 if (self->added)
872 nt_invalidate_added(self, 0);
874 nt_invalidate_added(self, 0);
873 if (self->ntrev > start)
875 if (self->ntrev > start)
874 self->ntrev = (int)start;
876 self->ntrev = (int)start;
875 }
877 }
876 self->length = start + 1;
878 self->length = start + 1;
877 return 0;
879 return 0;
878 }
880 }
879
881
880 if (self->nt) {
882 if (self->nt) {
881 nt_invalidate_added(self, start - self->length + 1);
883 nt_invalidate_added(self, start - self->length + 1);
882 if (self->ntrev > start)
884 if (self->ntrev > start)
883 self->ntrev = (int)start;
885 self->ntrev = (int)start;
884 }
886 }
885 return self->added
887 return self->added
886 ? PyList_SetSlice(self->added, start - self->length + 1,
888 ? PyList_SetSlice(self->added, start - self->length + 1,
887 PyList_GET_SIZE(self->added), NULL)
889 PyList_GET_SIZE(self->added), NULL)
888 : 0;
890 : 0;
889 }
891 }
890
892
891 /*
893 /*
892 * Supported ops:
894 * Supported ops:
893 *
895 *
894 * slice deletion
896 * slice deletion
895 * string assignment (extend node->rev mapping)
897 * string assignment (extend node->rev mapping)
896 * string deletion (shrink node->rev mapping)
898 * string deletion (shrink node->rev mapping)
897 */
899 */
898 static int index_assign_subscript(indexObject *self, PyObject *item,
900 static int index_assign_subscript(indexObject *self, PyObject *item,
899 PyObject *value)
901 PyObject *value)
900 {
902 {
901 char *node;
903 char *node;
902 Py_ssize_t nodelen;
904 Py_ssize_t nodelen;
903 long rev;
905 long rev;
904
906
905 if (PySlice_Check(item) && value == NULL)
907 if (PySlice_Check(item) && value == NULL)
906 return index_slice_del(self, item);
908 return index_slice_del(self, item);
907
909
908 if (node_check(item, &node, &nodelen) == -1)
910 if (node_check(item, &node, &nodelen) == -1)
909 return -1;
911 return -1;
910
912
911 if (value == NULL)
913 if (value == NULL)
912 return self->nt ? nt_insert(self, node, -1) : 0;
914 return self->nt ? nt_insert(self, node, -1) : 0;
913 rev = PyInt_AsLong(value);
915 rev = PyInt_AsLong(value);
914 if (rev > INT_MAX || rev < 0) {
916 if (rev > INT_MAX || rev < 0) {
915 if (!PyErr_Occurred())
917 if (!PyErr_Occurred())
916 PyErr_SetString(PyExc_ValueError, "rev out of range");
918 PyErr_SetString(PyExc_ValueError, "rev out of range");
917 return -1;
919 return -1;
918 }
920 }
919 return nt_insert(self, node, (int)rev);
921 return nt_insert(self, node, (int)rev);
920 }
922 }
921
923
922 /*
924 /*
923 * 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
924 * the optional "offsets" table with those entries.
926 * the optional "offsets" table with those entries.
925 */
927 */
926 static long inline_scan(indexObject *self, const char **offsets)
928 static long inline_scan(indexObject *self, const char **offsets)
927 {
929 {
928 const char *data = PyString_AS_STRING(self->data);
930 const char *data = PyString_AS_STRING(self->data);
929 const char *end = data + PyString_GET_SIZE(self->data);
931 const char *end = data + PyString_GET_SIZE(self->data);
930 const long hdrsize = 64;
932 const long hdrsize = 64;
931 long incr = hdrsize;
933 long incr = hdrsize;
932 Py_ssize_t len = 0;
934 Py_ssize_t len = 0;
933
935
934 while (data + hdrsize <= end) {
936 while (data + hdrsize <= end) {
935 uint32_t comp_len;
937 uint32_t comp_len;
936 const char *old_data;
938 const char *old_data;
937 /* 3rd element of header is length of compressed inline data */
939 /* 3rd element of header is length of compressed inline data */
938 comp_len = getbe32(data + 8);
940 comp_len = getbe32(data + 8);
939 incr = hdrsize + comp_len;
941 incr = hdrsize + comp_len;
940 if (incr < hdrsize)
942 if (incr < hdrsize)
941 break;
943 break;
942 if (offsets)
944 if (offsets)
943 offsets[len] = data;
945 offsets[len] = data;
944 len++;
946 len++;
945 old_data = data;
947 old_data = data;
946 data += incr;
948 data += incr;
947 if (data <= old_data)
949 if (data <= old_data)
948 break;
950 break;
949 }
951 }
950
952
951 if (data != end && data + hdrsize != end) {
953 if (data != end && data + hdrsize != end) {
952 if (!PyErr_Occurred())
954 if (!PyErr_Occurred())
953 PyErr_SetString(PyExc_ValueError, "corrupt index file");
955 PyErr_SetString(PyExc_ValueError, "corrupt index file");
954 return -1;
956 return -1;
955 }
957 }
956
958
957 return len;
959 return len;
958 }
960 }
959
961
960 static int index_real_init(indexObject *self, const char *data, int size,
962 static int index_init(indexObject *self, PyObject *args)
961 PyObject *inlined_obj, PyObject *data_obj)
962 {
963 {
964 PyObject *data_obj, *inlined_obj;
965 Py_ssize_t size;
966
967 if (!PyArg_ParseTuple(args, "OO", &data_obj, &inlined_obj))
968 return -1;
969 if (!PyString_Check(data_obj)) {
970 PyErr_SetString(PyExc_TypeError, "data is not a string");
971 return -1;
972 }
973 size = PyString_GET_SIZE(data_obj);
974
963 self->inlined = inlined_obj && PyObject_IsTrue(inlined_obj);
975 self->inlined = inlined_obj && PyObject_IsTrue(inlined_obj);
964 self->data = data_obj;
976 self->data = data_obj;
965 self->cache = NULL;
977 self->cache = NULL;
966
978
967 self->added = NULL;
979 self->added = NULL;
968 self->offsets = NULL;
980 self->offsets = NULL;
969 self->nt = NULL;
981 self->nt = NULL;
970 self->ntlength = self->ntcapacity = 0;
982 self->ntlength = self->ntcapacity = 0;
971 self->ntdepth = self->ntsplits = 0;
983 self->ntdepth = self->ntsplits = 0;
972 self->ntlookups = self->ntmisses = 0;
984 self->ntlookups = self->ntmisses = 0;
973 self->ntrev = -1;
985 self->ntrev = -1;
974 Py_INCREF(self->data);
975
986
976 if (self->inlined) {
987 if (self->inlined) {
977 long len = inline_scan(self, NULL);
988 long len = inline_scan(self, NULL);
978 if (len == -1)
989 if (len == -1)
979 goto bail;
990 goto bail;
980 self->raw_length = len;
991 self->raw_length = len;
981 self->length = len + 1;
992 self->length = len + 1;
982 } else {
993 } else {
983 if (size % 64) {
994 if (size % 64) {
984 PyErr_SetString(PyExc_ValueError, "corrupt index file");
995 PyErr_SetString(PyExc_ValueError, "corrupt index file");
985 goto bail;
996 goto bail;
986 }
997 }
987 self->raw_length = size / 64;
998 self->raw_length = size / 64;
988 self->length = self->raw_length + 1;
999 self->length = self->raw_length + 1;
989 }
1000 }
1001 Py_INCREF(self->data);
990
1002
991 return 0;
1003 return 0;
992 bail:
1004 bail:
993 return -1;
1005 return -1;
994 }
1006 }
995
1007
996 static int index_init(indexObject *self, PyObject *args, PyObject *kwds)
997 {
998 const char *data;
999 int size;
1000 PyObject *inlined_obj;
1001
1002 if (!PyArg_ParseTuple(args, "s#O", &data, &size, &inlined_obj))
1003 return -1;
1004
1005 return index_real_init(self, data, size, inlined_obj,
1006 PyTuple_GET_ITEM(args, 0));
1007 }
1008
1009 static PyObject *index_nodemap(indexObject *self)
1008 static PyObject *index_nodemap(indexObject *self)
1010 {
1009 {
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 const char *data;
1109 PyObject *tuple = NULL, *cache = NULL;
1110 int size, ret;
1111 PyObject *inlined_obj, *tuple = NULL, *cache = NULL;
1112 indexObject *idx;
1110 indexObject *idx;
1113
1111 int ret;
1114 if (!PyArg_ParseTuple(args, "s#O", &data, &size, &inlined_obj))
1115 return NULL;
1116
1112
1117 idx = PyObject_New(indexObject, &indexType);
1113 idx = PyObject_New(indexObject, &indexType);
1118
1119 if (idx == NULL)
1114 if (idx == NULL)
1120 goto bail;
1115 goto bail;
1121
1116
1122 ret = index_real_init(idx, data, size, inlined_obj,
1117 ret = index_init(idx, args);
1123 PyTuple_GET_ITEM(args, 0));
1118 if (ret == -1)
1124 if (ret)
1125 goto bail;
1119 goto bail;
1126
1120
1127 if (idx->inlined) {
1121 if (idx->inlined) {
1128 Py_INCREF(idx->data);
1129 cache = Py_BuildValue("iO", 0, idx->data);
1122 cache = Py_BuildValue("iO", 0, idx->data);
1130 if (cache == NULL)
1123 if (cache == NULL)
1131 goto bail;
1124 goto bail;
1132 } else {
1125 } else {
1133 cache = Py_None;
1126 cache = Py_None;
1134 Py_INCREF(cache);
1127 Py_INCREF(cache);
1135 }
1128 }
1136
1129
1137 Py_INCREF(idx);
1138
1139 tuple = Py_BuildValue("NN", idx, cache);
1130 tuple = Py_BuildValue("NN", idx, cache);
1140 if (!tuple)
1131 if (!tuple)
1141 goto bail;
1132 goto bail;
1142 return tuple;
1133 return tuple;
1143
1134
1144 bail:
1135 bail:
1145 Py_XDECREF(idx);
1136 Py_XDECREF(idx);
1146 Py_XDECREF(cache);
1137 Py_XDECREF(cache);
1147 Py_XDECREF(tuple);
1138 Py_XDECREF(tuple);
1148 return NULL;
1139 return NULL;
1149 }
1140 }
1150
1141
1151 static char parsers_doc[] = "Efficient content parsing.";
1142 static char parsers_doc[] = "Efficient content parsing.";
1152
1143
1153 static PyMethodDef methods[] = {
1144 static PyMethodDef methods[] = {
1154 {"parse_manifest", parse_manifest, METH_VARARGS, "parse a manifest\n"},
1145 {"parse_manifest", parse_manifest, METH_VARARGS, "parse a manifest\n"},
1155 {"parse_dirstate", parse_dirstate, METH_VARARGS, "parse a dirstate\n"},
1146 {"parse_dirstate", parse_dirstate, METH_VARARGS, "parse a dirstate\n"},
1156 {"parse_index2", parse_index2, METH_VARARGS, "parse a revlog index\n"},
1147 {"parse_index2", parse_index2, METH_VARARGS, "parse a revlog index\n"},
1157 {NULL, NULL}
1148 {NULL, NULL}
1158 };
1149 };
1159
1150
1160 static void module_init(PyObject *mod)
1151 static void module_init(PyObject *mod)
1161 {
1152 {
1162 if (PyType_Ready(&indexType) < 0)
1153 if (PyType_Ready(&indexType) < 0)
1163 return;
1154 return;
1164 Py_INCREF(&indexType);
1155 Py_INCREF(&indexType);
1165
1156
1166 PyModule_AddObject(mod, "index", (PyObject *)&indexType);
1157 PyModule_AddObject(mod, "index", (PyObject *)&indexType);
1167
1158
1168 nullentry = Py_BuildValue("iiiiiiis#", 0, 0, 0,
1159 nullentry = Py_BuildValue("iiiiiiis#", 0, 0, 0,
1169 -1, -1, -1, -1, nullid, 20);
1160 -1, -1, -1, -1, nullid, 20);
1170 if (nullentry)
1161 if (nullentry)
1171 PyObject_GC_UnTrack(nullentry);
1162 PyObject_GC_UnTrack(nullentry);
1172 }
1163 }
1173
1164
1174 #ifdef IS_PY3K
1165 #ifdef IS_PY3K
1175 static struct PyModuleDef parsers_module = {
1166 static struct PyModuleDef parsers_module = {
1176 PyModuleDef_HEAD_INIT,
1167 PyModuleDef_HEAD_INIT,
1177 "parsers",
1168 "parsers",
1178 parsers_doc,
1169 parsers_doc,
1179 -1,
1170 -1,
1180 methods
1171 methods
1181 };
1172 };
1182
1173
1183 PyMODINIT_FUNC PyInit_parsers(void)
1174 PyMODINIT_FUNC PyInit_parsers(void)
1184 {
1175 {
1185 PyObject *mod = PyModule_Create(&parsers_module);
1176 PyObject *mod = PyModule_Create(&parsers_module);
1186 module_init(mod);
1177 module_init(mod);
1187 return mod;
1178 return mod;
1188 }
1179 }
1189 #else
1180 #else
1190 PyMODINIT_FUNC initparsers(void)
1181 PyMODINIT_FUNC initparsers(void)
1191 {
1182 {
1192 PyObject *mod = Py_InitModule3("parsers", methods, parsers_doc);
1183 PyObject *mod = Py_InitModule3("parsers", methods, parsers_doc);
1193 module_init(mod);
1184 module_init(mod);
1194 }
1185 }
1195 #endif
1186 #endif
General Comments 0
You need to be logged in to leave comments. Login now