Mercurial > hg
view mercurial/parsers.c @ 24663:7d01371e6358
commands: add ui.statuscopies config knob
statuscopies enables viewing of copies and moves in 'hg status' by default.
| author | Mathias De Maré <mathias.demare@gmail.com> |
|---|---|
| date | Tue, 24 Mar 2015 21:25:57 +0100 |
| parents | 2262d7bc469e |
| children | f2fd087a75ef |
line wrap: on
line source
/* parsers.c - efficient content parsing Copyright 2008 Matt Mackall <mpm@selenic.com> and others This software may be used and distributed according to the terms of the GNU General Public License, incorporated herein by reference. */ #include <Python.h> #include <ctype.h> #include <stddef.h> #include <string.h> #include "util.h" static char *versionerrortext = "Python minor version mismatch"; static int8_t hextable[256] = { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, -1, -1, -1, -1, -1, -1, /* 0-9 */ -1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* A-F */ -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* a-f */ -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 }; static char lowertable[128] = { '\x00', '\x01', '\x02', '\x03', '\x04', '\x05', '\x06', '\x07', '\x08', '\x09', '\x0a', '\x0b', '\x0c', '\x0d', '\x0e', '\x0f', '\x10', '\x11', '\x12', '\x13', '\x14', '\x15', '\x16', '\x17', '\x18', '\x19', '\x1a', '\x1b', '\x1c', '\x1d', '\x1e', '\x1f', '\x20', '\x21', '\x22', '\x23', '\x24', '\x25', '\x26', '\x27', '\x28', '\x29', '\x2a', '\x2b', '\x2c', '\x2d', '\x2e', '\x2f', '\x30', '\x31', '\x32', '\x33', '\x34', '\x35', '\x36', '\x37', '\x38', '\x39', '\x3a', '\x3b', '\x3c', '\x3d', '\x3e', '\x3f', '\x40', '\x61', '\x62', '\x63', '\x64', '\x65', '\x66', '\x67', /* A-G */ '\x68', '\x69', '\x6a', '\x6b', '\x6c', '\x6d', '\x6e', '\x6f', /* H-O */ '\x70', '\x71', '\x72', '\x73', '\x74', '\x75', '\x76', '\x77', /* P-W */ '\x78', '\x79', '\x7a', /* X-Z */ '\x5b', '\x5c', '\x5d', '\x5e', '\x5f', '\x60', '\x61', '\x62', '\x63', '\x64', '\x65', '\x66', '\x67', '\x68', '\x69', '\x6a', '\x6b', '\x6c', '\x6d', '\x6e', '\x6f', '\x70', '\x71', '\x72', '\x73', '\x74', '\x75', '\x76', '\x77', '\x78', '\x79', '\x7a', '\x7b', '\x7c', '\x7d', '\x7e', '\x7f' }; static char uppertable[128] = { '\x00', '\x01', '\x02', '\x03', '\x04', '\x05', '\x06', '\x07', '\x08', '\x09', '\x0a', '\x0b', '\x0c', '\x0d', '\x0e', '\x0f', '\x10', '\x11', '\x12', '\x13', '\x14', '\x15', '\x16', '\x17', '\x18', '\x19', '\x1a', '\x1b', '\x1c', '\x1d', '\x1e', '\x1f', '\x20', '\x21', '\x22', '\x23', '\x24', '\x25', '\x26', '\x27', '\x28', '\x29', '\x2a', '\x2b', '\x2c', '\x2d', '\x2e', '\x2f', '\x30', '\x31', '\x32', '\x33', '\x34', '\x35', '\x36', '\x37', '\x38', '\x39', '\x3a', '\x3b', '\x3c', '\x3d', '\x3e', '\x3f', '\x40', '\x41', '\x42', '\x43', '\x44', '\x45', '\x46', '\x47', '\x48', '\x49', '\x4a', '\x4b', '\x4c', '\x4d', '\x4e', '\x4f', '\x50', '\x51', '\x52', '\x53', '\x54', '\x55', '\x56', '\x57', '\x58', '\x59', '\x5a', '\x5b', '\x5c', '\x5d', '\x5e', '\x5f', '\x60', '\x41', '\x42', '\x43', '\x44', '\x45', '\x46', '\x47', /* a-g */ '\x48', '\x49', '\x4a', '\x4b', '\x4c', '\x4d', '\x4e', '\x4f', /* h-o */ '\x50', '\x51', '\x52', '\x53', '\x54', '\x55', '\x56', '\x57', /* p-w */ '\x58', '\x59', '\x5a', /* x-z */ '\x7b', '\x7c', '\x7d', '\x7e', '\x7f' }; static inline int hexdigit(const char *p, Py_ssize_t off) { int8_t val = hextable[(unsigned char)p[off]]; if (val >= 0) { return val; } PyErr_SetString(PyExc_ValueError, "input contains non-hex character"); return 0; } /* * Turn a hex-encoded string into binary. */ PyObject *unhexlify(const char *str, int len) { PyObject *ret; char *d; int i; ret = PyBytes_FromStringAndSize(NULL, len / 2); if (!ret) return NULL; d = PyBytes_AsString(ret); for (i = 0; i < len;) { int hi = hexdigit(str, i++); int lo = hexdigit(str, i++); *d++ = (hi << 4) | lo; } return ret; } static inline PyObject *_asciitransform(PyObject *str_obj, const char table[128], PyObject *fallback_fn) { char *str, *newstr; Py_ssize_t i, len; PyObject *newobj = NULL; PyObject *ret = NULL; str = PyBytes_AS_STRING(str_obj); len = PyBytes_GET_SIZE(str_obj); newobj = PyBytes_FromStringAndSize(NULL, len); if (!newobj) goto quit; newstr = PyBytes_AS_STRING(newobj); for (i = 0; i < len; i++) { char c = str[i]; if (c & 0x80) { if (fallback_fn != NULL) { ret = PyObject_CallFunctionObjArgs(fallback_fn, str_obj, NULL); } else { PyObject *err = PyUnicodeDecodeError_Create( "ascii", str, len, i, (i + 1), "unexpected code byte"); PyErr_SetObject(PyExc_UnicodeDecodeError, err); Py_XDECREF(err); } goto quit; } newstr[i] = table[(unsigned char)c]; } ret = newobj; Py_INCREF(ret); quit: Py_XDECREF(newobj); return ret; } static PyObject *asciilower(PyObject *self, PyObject *args) { PyObject *str_obj; if (!PyArg_ParseTuple(args, "O!:asciilower", &PyBytes_Type, &str_obj)) return NULL; return _asciitransform(str_obj, lowertable, NULL); } static PyObject *asciiupper(PyObject *self, PyObject *args) { PyObject *str_obj; if (!PyArg_ParseTuple(args, "O!:asciiupper", &PyBytes_Type, &str_obj)) return NULL; return _asciitransform(str_obj, uppertable, NULL); } static PyObject *make_file_foldmap(PyObject *self, PyObject *args) { PyObject *dmap, *spec_obj, *normcase_fallback; PyObject *file_foldmap = NULL; enum normcase_spec spec; PyObject *k, *v; dirstateTupleObject *tuple; Py_ssize_t pos = 0; const char *table; if (!PyArg_ParseTuple(args, "O!O!O!:make_file_foldmap", &PyDict_Type, &dmap, &PyInt_Type, &spec_obj, &PyFunction_Type, &normcase_fallback)) goto quit; spec = (int)PyInt_AS_LONG(spec_obj); switch (spec) { case NORMCASE_LOWER: table = lowertable; break; case NORMCASE_UPPER: table = uppertable; break; case NORMCASE_OTHER: table = NULL; break; default: PyErr_SetString(PyExc_TypeError, "invalid normcasespec"); goto quit; } file_foldmap = PyDict_New(); if (file_foldmap == NULL) goto quit; while (PyDict_Next(dmap, &pos, &k, &v)) { if (!dirstate_tuple_check(v)) { PyErr_SetString(PyExc_TypeError, "expected a dirstate tuple"); goto quit; } tuple = (dirstateTupleObject *)v; if (tuple->state != 'r') { PyObject *normed; if (table != NULL) { normed = _asciitransform(k, table, normcase_fallback); } else { normed = PyObject_CallFunctionObjArgs( normcase_fallback, k, NULL); } if (normed == NULL) goto quit; if (PyDict_SetItem(file_foldmap, normed, k) == -1) goto quit; } } return file_foldmap; quit: Py_XDECREF(file_foldmap); return NULL; } /* * This code assumes that a manifest is stitched together with newline * ('\n') characters. */ static PyObject *parse_manifest(PyObject *self, PyObject *args) { PyObject *mfdict, *fdict; char *str, *start, *end; int len; if (!PyArg_ParseTuple(args, "O!O!s#:parse_manifest", &PyDict_Type, &mfdict, &PyDict_Type, &fdict, &str, &len)) goto quit; start = str; end = str + len; while (start < end) { PyObject *file = NULL, *node = NULL; PyObject *flags = NULL; char *zero = NULL, *newline = NULL; ptrdiff_t nlen; zero = memchr(start, '\0', end - start); if (!zero) { PyErr_SetString(PyExc_ValueError, "manifest entry has no separator"); goto quit; } newline = memchr(zero + 1, '\n', end - (zero + 1)); if (!newline) { PyErr_SetString(PyExc_ValueError, "manifest contains trailing garbage"); goto quit; } file = PyBytes_FromStringAndSize(start, zero - start); if (!file) goto bail; nlen = newline - zero - 1; node = unhexlify(zero + 1, nlen > 40 ? 40 : (int)nlen); if (!node) goto bail; if (nlen > 40) { flags = PyBytes_FromStringAndSize(zero + 41, nlen - 40); if (!flags) goto bail; if (PyDict_SetItem(fdict, file, flags) == -1) goto bail; } if (PyDict_SetItem(mfdict, file, node) == -1) goto bail; start = newline + 1; Py_XDECREF(flags); Py_XDECREF(node); Py_XDECREF(file); continue; bail: Py_XDECREF(flags); Py_XDECREF(node); Py_XDECREF(file); goto quit; } Py_INCREF(Py_None); return Py_None; quit: return NULL; } static inline dirstateTupleObject *make_dirstate_tuple(char state, int mode, int size, int mtime) { dirstateTupleObject *t = PyObject_New(dirstateTupleObject, &dirstateTupleType); if (!t) return NULL; t->state = state; t->mode = mode; t->size = size; t->mtime = mtime; return t; } static PyObject *dirstate_tuple_new(PyTypeObject *subtype, PyObject *args, PyObject *kwds) { /* We do all the initialization here and not a tp_init function because * dirstate_tuple is immutable. */ dirstateTupleObject *t; char state; int size, mode, mtime; if (!PyArg_ParseTuple(args, "ciii", &state, &mode, &size, &mtime)) return NULL; t = (dirstateTupleObject *)subtype->tp_alloc(subtype, 1); if (!t) return NULL; t->state = state; t->mode = mode; t->size = size; t->mtime = mtime; return (PyObject *)t; } static void dirstate_tuple_dealloc(PyObject *o) { PyObject_Del(o); } static Py_ssize_t dirstate_tuple_length(PyObject *o) { return 4; } static PyObject *dirstate_tuple_item(PyObject *o, Py_ssize_t i) { dirstateTupleObject *t = (dirstateTupleObject *)o; switch (i) { case 0: return PyBytes_FromStringAndSize(&t->state, 1); case 1: return PyInt_FromLong(t->mode); case 2: return PyInt_FromLong(t->size); case 3: return PyInt_FromLong(t->mtime); default: PyErr_SetString(PyExc_IndexError, "index out of range"); return NULL; } } static PySequenceMethods dirstate_tuple_sq = { dirstate_tuple_length, /* sq_length */ 0, /* sq_concat */ 0, /* sq_repeat */ dirstate_tuple_item, /* sq_item */ 0, /* sq_ass_item */ 0, /* sq_contains */ 0, /* sq_inplace_concat */ 0 /* sq_inplace_repeat */ }; PyTypeObject dirstateTupleType = { PyVarObject_HEAD_INIT(NULL, 0) "dirstate_tuple", /* tp_name */ sizeof(dirstateTupleObject),/* tp_basicsize */ 0, /* tp_itemsize */ (destructor)dirstate_tuple_dealloc, /* tp_dealloc */ 0, /* tp_print */ 0, /* tp_getattr */ 0, /* tp_setattr */ 0, /* tp_compare */ 0, /* tp_repr */ 0, /* tp_as_number */ &dirstate_tuple_sq, /* tp_as_sequence */ 0, /* tp_as_mapping */ 0, /* tp_hash */ 0, /* tp_call */ 0, /* tp_str */ 0, /* tp_getattro */ 0, /* tp_setattro */ 0, /* tp_as_buffer */ Py_TPFLAGS_DEFAULT, /* tp_flags */ "dirstate tuple", /* tp_doc */ 0, /* tp_traverse */ 0, /* tp_clear */ 0, /* tp_richcompare */ 0, /* tp_weaklistoffset */ 0, /* tp_iter */ 0, /* tp_iternext */ 0, /* tp_methods */ 0, /* tp_members */ 0, /* tp_getset */ 0, /* tp_base */ 0, /* tp_dict */ 0, /* tp_descr_get */ 0, /* tp_descr_set */ 0, /* tp_dictoffset */ 0, /* tp_init */ 0, /* tp_alloc */ dirstate_tuple_new, /* tp_new */ }; static PyObject *parse_dirstate(PyObject *self, PyObject *args) { PyObject *dmap, *cmap, *parents = NULL, *ret = NULL; PyObject *fname = NULL, *cname = NULL, *entry = NULL; char state, *cur, *str, *cpos; int mode, size, mtime; unsigned int flen, len, pos = 40; int readlen; if (!PyArg_ParseTuple(args, "O!O!s#:parse_dirstate", &PyDict_Type, &dmap, &PyDict_Type, &cmap, &str, &readlen)) goto quit; if (readlen < 0) goto quit; len = readlen; /* read parents */ if (len < 40) goto quit; parents = Py_BuildValue("s#s#", str, 20, str + 20, 20); if (!parents) goto quit; /* read filenames */ while (pos >= 40 && pos < len) { cur = str + pos; /* unpack header */ state = *cur; mode = getbe32(cur + 1); size = getbe32(cur + 5); mtime = getbe32(cur + 9); flen = getbe32(cur + 13); pos += 17; cur += 17; if (flen > len - pos) { PyErr_SetString(PyExc_ValueError, "overflow in dirstate"); goto quit; } entry = (PyObject *)make_dirstate_tuple(state, mode, size, mtime); cpos = memchr(cur, 0, flen); if (cpos) { fname = PyBytes_FromStringAndSize(cur, cpos - cur); cname = PyBytes_FromStringAndSize(cpos + 1, flen - (cpos - cur) - 1); if (!fname || !cname || PyDict_SetItem(cmap, fname, cname) == -1 || PyDict_SetItem(dmap, fname, entry) == -1) goto quit; Py_DECREF(cname); } else { fname = PyBytes_FromStringAndSize(cur, flen); if (!fname || PyDict_SetItem(dmap, fname, entry) == -1) goto quit; } Py_DECREF(fname); Py_DECREF(entry); fname = cname = entry = NULL; pos += flen; } ret = parents; Py_INCREF(ret); quit: Py_XDECREF(fname); Py_XDECREF(cname); Py_XDECREF(entry); Py_XDECREF(parents); return ret; } /* * Efficiently pack a dirstate object into its on-disk format. */ static PyObject *pack_dirstate(PyObject *self, PyObject *args) { PyObject *packobj = NULL; PyObject *map, *copymap, *pl, *mtime_unset = NULL; Py_ssize_t nbytes, pos, l; PyObject *k, *v = NULL, *pn; char *p, *s; double now; if (!PyArg_ParseTuple(args, "O!O!Od:pack_dirstate", &PyDict_Type, &map, &PyDict_Type, ©map, &pl, &now)) return NULL; if (!PySequence_Check(pl) || PySequence_Size(pl) != 2) { PyErr_SetString(PyExc_TypeError, "expected 2-element sequence"); return NULL; } /* Figure out how much we need to allocate. */ for (nbytes = 40, pos = 0; PyDict_Next(map, &pos, &k, &v);) { PyObject *c; if (!PyString_Check(k)) { PyErr_SetString(PyExc_TypeError, "expected string key"); goto bail; } nbytes += PyString_GET_SIZE(k) + 17; c = PyDict_GetItem(copymap, k); if (c) { if (!PyString_Check(c)) { PyErr_SetString(PyExc_TypeError, "expected string key"); goto bail; } nbytes += PyString_GET_SIZE(c) + 1; } } packobj = PyString_FromStringAndSize(NULL, nbytes); if (packobj == NULL) goto bail; p = PyString_AS_STRING(packobj); pn = PySequence_ITEM(pl, 0); if (PyString_AsStringAndSize(pn, &s, &l) == -1 || l != 20) { PyErr_SetString(PyExc_TypeError, "expected a 20-byte hash"); goto bail; } memcpy(p, s, l); p += 20; pn = PySequence_ITEM(pl, 1); if (PyString_AsStringAndSize(pn, &s, &l) == -1 || l != 20) { PyErr_SetString(PyExc_TypeError, "expected a 20-byte hash"); goto bail; } memcpy(p, s, l); p += 20; for (pos = 0; PyDict_Next(map, &pos, &k, &v); ) { dirstateTupleObject *tuple; char state; uint32_t mode, size, mtime; Py_ssize_t len, l; PyObject *o; char *t; if (!dirstate_tuple_check(v)) { PyErr_SetString(PyExc_TypeError, "expected a dirstate tuple"); goto bail; } tuple = (dirstateTupleObject *)v; state = tuple->state; mode = tuple->mode; size = tuple->size; mtime = tuple->mtime; if (state == 'n' && mtime == (uint32_t)now) { /* See pure/parsers.py:pack_dirstate for why we do * this. */ mtime = -1; mtime_unset = (PyObject *)make_dirstate_tuple( state, mode, size, mtime); if (!mtime_unset) goto bail; if (PyDict_SetItem(map, k, mtime_unset) == -1) goto bail; Py_DECREF(mtime_unset); mtime_unset = NULL; } *p++ = state; putbe32(mode, p); putbe32(size, p + 4); putbe32(mtime, p + 8); t = p + 12; p += 16; len = PyString_GET_SIZE(k); memcpy(p, PyString_AS_STRING(k), len); p += len; o = PyDict_GetItem(copymap, k); if (o) { *p++ = '\0'; l = PyString_GET_SIZE(o); memcpy(p, PyString_AS_STRING(o), l); p += l; len += l + 1; } putbe32((uint32_t)len, t); } pos = p - PyString_AS_STRING(packobj); if (pos != nbytes) { PyErr_Format(PyExc_SystemError, "bad dirstate size: %ld != %ld", (long)pos, (long)nbytes); goto bail; } return packobj; bail: Py_XDECREF(mtime_unset); Py_XDECREF(packobj); Py_XDECREF(v); return NULL; } /* * A base-16 trie for fast node->rev mapping. * * Positive value is index of the next node in the trie * Negative value is a leaf: -(rev + 1) * Zero is empty */ typedef struct { int children[16]; } nodetree; /* * This class has two behaviours. * * When used in a list-like way (with integer keys), we decode an * entry in a RevlogNG index file on demand. Our last entry is a * sentinel, always a nullid. We have limited support for * integer-keyed insert and delete, only at elements right before the * sentinel. * * With string keys, we lazily perform a reverse mapping from node to * rev, using a base-16 trie. */ typedef struct { PyObject_HEAD /* Type-specific fields go here. */ PyObject *data; /* raw bytes of index */ PyObject **cache; /* cached tuples */ const char **offsets; /* populated on demand */ Py_ssize_t raw_length; /* original number of elements */ Py_ssize_t length; /* current number of elements */ PyObject *added; /* populated on demand */ PyObject *headrevs; /* cache, invalidated on changes */ PyObject *filteredrevs;/* filtered revs set */ nodetree *nt; /* base-16 trie */ int ntlength; /* # nodes in use */ int ntcapacity; /* # nodes allocated */ int ntdepth; /* maximum depth of tree */ int ntsplits; /* # splits performed */ int ntrev; /* last rev scanned */ int ntlookups; /* # lookups */ int ntmisses; /* # lookups that miss the cache */ int inlined; } indexObject; static Py_ssize_t index_length(const indexObject *self) { if (self->added == NULL) return self->length; return self->length + PyList_GET_SIZE(self->added); } static PyObject *nullentry; static const char nullid[20]; static Py_ssize_t inline_scan(indexObject *self, const char **offsets); #if LONG_MAX == 0x7fffffffL static char *tuple_format = "Kiiiiiis#"; #else static char *tuple_format = "kiiiiiis#"; #endif /* A RevlogNG v1 index entry is 64 bytes long. */ static const long v1_hdrsize = 64; /* * Return a pointer to the beginning of a RevlogNG record. */ static const char *index_deref(indexObject *self, Py_ssize_t pos) { if (self->inlined && pos > 0) { if (self->offsets == NULL) { self->offsets = malloc(self->raw_length * sizeof(*self->offsets)); if (self->offsets == NULL) return (const char *)PyErr_NoMemory(); inline_scan(self, self->offsets); } return self->offsets[pos]; } return PyString_AS_STRING(self->data) + pos * v1_hdrsize; } /* * RevlogNG format (all in big endian, data may be inlined): * 6 bytes: offset * 2 bytes: flags * 4 bytes: compressed length * 4 bytes: uncompressed length * 4 bytes: base revision * 4 bytes: link revision * 4 bytes: parent 1 revision * 4 bytes: parent 2 revision * 32 bytes: nodeid (only 20 bytes used) */ static PyObject *index_get(indexObject *self, Py_ssize_t pos) { uint64_t offset_flags; int comp_len, uncomp_len, base_rev, link_rev, parent_1, parent_2; const char *c_node_id; const char *data; Py_ssize_t length = index_length(self); PyObject *entry; if (pos < 0) pos += length; if (pos < 0 || pos >= length) { PyErr_SetString(PyExc_IndexError, "revlog index out of range"); return NULL; } if (pos == length - 1) { Py_INCREF(nullentry); return nullentry; } if (pos >= self->length - 1) { PyObject *obj; obj = PyList_GET_ITEM(self->added, pos - self->length + 1); Py_INCREF(obj); return obj; } if (self->cache) { if (self->cache[pos]) { Py_INCREF(self->cache[pos]); return self->cache[pos]; } } else { self->cache = calloc(self->raw_length, sizeof(PyObject *)); if (self->cache == NULL) return PyErr_NoMemory(); } data = index_deref(self, pos); if (data == NULL) return NULL; offset_flags = getbe32(data + 4); if (pos == 0) /* mask out version number for the first entry */ offset_flags &= 0xFFFF; else { uint32_t offset_high = getbe32(data); offset_flags |= ((uint64_t)offset_high) << 32; } comp_len = getbe32(data + 8); uncomp_len = getbe32(data + 12); base_rev = getbe32(data + 16); link_rev = getbe32(data + 20); parent_1 = getbe32(data + 24); parent_2 = getbe32(data + 28); c_node_id = data + 32; entry = Py_BuildValue(tuple_format, offset_flags, comp_len, uncomp_len, base_rev, link_rev, parent_1, parent_2, c_node_id, 20); if (entry) { PyObject_GC_UnTrack(entry); Py_INCREF(entry); } self->cache[pos] = entry; return entry; } /* * Return the 20-byte SHA of the node corresponding to the given rev. */ static const char *index_node(indexObject *self, Py_ssize_t pos) { Py_ssize_t length = index_length(self); const char *data; if (pos == length - 1 || pos == INT_MAX) return nullid; if (pos >= length) return NULL; if (pos >= self->length - 1) { PyObject *tuple, *str; tuple = PyList_GET_ITEM(self->added, pos - self->length + 1); str = PyTuple_GetItem(tuple, 7); return str ? PyString_AS_STRING(str) : NULL; } data = index_deref(self, pos); return data ? data + 32 : NULL; } static int nt_insert(indexObject *self, const char *node, int rev); static int node_check(PyObject *obj, char **node, Py_ssize_t *nodelen) { if (PyString_AsStringAndSize(obj, node, nodelen) == -1) return -1; if (*nodelen == 20) return 0; PyErr_SetString(PyExc_ValueError, "20-byte hash required"); return -1; } static PyObject *index_insert(indexObject *self, PyObject *args) { PyObject *obj; char *node; int index; Py_ssize_t len, nodelen; if (!PyArg_ParseTuple(args, "iO", &index, &obj)) return NULL; if (!PyTuple_Check(obj) || PyTuple_GET_SIZE(obj) != 8) { PyErr_SetString(PyExc_TypeError, "8-tuple required"); return NULL; } if (node_check(PyTuple_GET_ITEM(obj, 7), &node, &nodelen) == -1) return NULL; len = index_length(self); if (index < 0) index += len; if (index != len - 1) { PyErr_SetString(PyExc_IndexError, "insert only supported at index -1"); return NULL; } if (self->added == NULL) { self->added = PyList_New(0); if (self->added == NULL) return NULL; } if (PyList_Append(self->added, obj) == -1) return NULL; if (self->nt) nt_insert(self, node, index); Py_CLEAR(self->headrevs); Py_RETURN_NONE; } static void _index_clearcaches(indexObject *self) { if (self->cache) { Py_ssize_t i; for (i = 0; i < self->raw_length; i++) Py_CLEAR(self->cache[i]); free(self->cache); self->cache = NULL; } if (self->offsets) { free(self->offsets); self->offsets = NULL; } if (self->nt) { free(self->nt); self->nt = NULL; } Py_CLEAR(self->headrevs); } static PyObject *index_clearcaches(indexObject *self) { _index_clearcaches(self); self->ntlength = self->ntcapacity = 0; self->ntdepth = self->ntsplits = 0; self->ntrev = -1; self->ntlookups = self->ntmisses = 0; Py_RETURN_NONE; } static PyObject *index_stats(indexObject *self) { PyObject *obj = PyDict_New(); PyObject *t = NULL; if (obj == NULL) return NULL; #define istat(__n, __d) \ t = PyInt_FromSsize_t(self->__n); \ if (!t) \ goto bail; \ if (PyDict_SetItemString(obj, __d, t) == -1) \ goto bail; \ Py_DECREF(t); if (self->added) { Py_ssize_t len = PyList_GET_SIZE(self->added); t = PyInt_FromSsize_t(len); if (!t) goto bail; if (PyDict_SetItemString(obj, "index entries added", t) == -1) goto bail; Py_DECREF(t); } if (self->raw_length != self->length - 1) istat(raw_length, "revs on disk"); istat(length, "revs in memory"); istat(ntcapacity, "node trie capacity"); istat(ntdepth, "node trie depth"); istat(ntlength, "node trie count"); istat(ntlookups, "node trie lookups"); istat(ntmisses, "node trie misses"); istat(ntrev, "node trie last rev scanned"); istat(ntsplits, "node trie splits"); #undef istat return obj; bail: Py_XDECREF(obj); Py_XDECREF(t); return NULL; } /* * When we cache a list, we want to be sure the caller can't mutate * the cached copy. */ static PyObject *list_copy(PyObject *list) { Py_ssize_t len = PyList_GET_SIZE(list); PyObject *newlist = PyList_New(len); Py_ssize_t i; if (newlist == NULL) return NULL; for (i = 0; i < len; i++) { PyObject *obj = PyList_GET_ITEM(list, i); Py_INCREF(obj); PyList_SET_ITEM(newlist, i, obj); } return newlist; } /* arg should be Py_ssize_t but Python 2.4 do not support the n format */ static int check_filter(PyObject *filter, unsigned long arg) { if (filter) { PyObject *arglist, *result; int isfiltered; arglist = Py_BuildValue("(k)", arg); if (!arglist) { return -1; } result = PyEval_CallObject(filter, arglist); Py_DECREF(arglist); if (!result) { return -1; } /* PyObject_IsTrue returns 1 if true, 0 if false, -1 if error, * same as this function, so we can just return it directly.*/ isfiltered = PyObject_IsTrue(result); Py_DECREF(result); return isfiltered; } else { return 0; } } static Py_ssize_t add_roots_get_min(indexObject *self, PyObject *list, Py_ssize_t marker, char *phases) { PyObject *iter = NULL; PyObject *iter_item = NULL; Py_ssize_t min_idx = index_length(self) + 1; long iter_item_long; if (PyList_GET_SIZE(list) != 0) { iter = PyObject_GetIter(list); if (iter == NULL) return -2; while ((iter_item = PyIter_Next(iter))) { iter_item_long = PyInt_AS_LONG(iter_item); Py_DECREF(iter_item); if (iter_item_long < min_idx) min_idx = iter_item_long; phases[iter_item_long] = marker; } Py_DECREF(iter); } return min_idx; } static inline void set_phase_from_parents(char *phases, int parent_1, int parent_2, Py_ssize_t i) { if (parent_1 >= 0 && phases[parent_1] > phases[i]) phases[i] = phases[parent_1]; if (parent_2 >= 0 && phases[parent_2] > phases[i]) phases[i] = phases[parent_2]; } static PyObject *compute_phases(indexObject *self, PyObject *args) { PyObject *roots = Py_None; PyObject *phaseslist = NULL; PyObject *phaseroots = NULL; PyObject *rev = NULL; PyObject *p1 = NULL; PyObject *p2 = NULL; Py_ssize_t addlen = self->added ? PyList_GET_SIZE(self->added) : 0; Py_ssize_t len = index_length(self) - 1; Py_ssize_t numphase = 0; Py_ssize_t minrevallphases = 0; Py_ssize_t minrevphase = 0; Py_ssize_t i = 0; int parent_1, parent_2; char *phases = NULL; const char *data; if (!PyArg_ParseTuple(args, "O", &roots)) goto release_none; if (roots == NULL || !PyList_Check(roots)) goto release_none; phases = calloc(len, 1); /* phase per rev: {0: public, 1: draft, 2: secret} */ if (phases == NULL) goto release_none; /* Put the phase information of all the roots in phases */ numphase = PyList_GET_SIZE(roots)+1; minrevallphases = len + 1; for (i = 0; i < numphase-1; i++) { phaseroots = PyList_GET_ITEM(roots, i); if (!PyList_Check(phaseroots)) goto release_phases; minrevphase = add_roots_get_min(self, phaseroots, i+1, phases); if (minrevphase == -2) /* Error from add_roots_get_min */ goto release_phases; minrevallphases = MIN(minrevallphases, minrevphase); } /* Propagate the phase information from the roots to the revs */ if (minrevallphases != -1) { for (i = minrevallphases; i < self->raw_length; i++) { data = index_deref(self, i); set_phase_from_parents(phases, getbe32(data+24), getbe32(data+28), i); } for (i = 0; i < addlen; i++) { rev = PyList_GET_ITEM(self->added, i); p1 = PyTuple_GET_ITEM(rev, 5); p2 = PyTuple_GET_ITEM(rev, 6); if (!PyInt_Check(p1) || !PyInt_Check(p2)) { PyErr_SetString(PyExc_TypeError, "revlog parents are invalid"); goto release_phases; } parent_1 = (int)PyInt_AS_LONG(p1); parent_2 = (int)PyInt_AS_LONG(p2); set_phase_from_parents(phases, parent_1, parent_2, i+self->raw_length); } } /* Transform phase list to a python list */ phaseslist = PyList_New(len); if (phaseslist == NULL) goto release_phases; for (i = 0; i < len; i++) PyList_SET_ITEM(phaseslist, i, PyInt_FromLong(phases[i])); release_phases: free(phases); release_none: return phaseslist; } static PyObject *index_headrevs(indexObject *self, PyObject *args) { Py_ssize_t i, len, addlen; char *nothead = NULL; PyObject *heads = NULL; PyObject *filter = NULL; PyObject *filteredrevs = Py_None; if (!PyArg_ParseTuple(args, "|O", &filteredrevs)) { return NULL; } if (self->headrevs && filteredrevs == self->filteredrevs) return list_copy(self->headrevs); Py_DECREF(self->filteredrevs); self->filteredrevs = filteredrevs; Py_INCREF(filteredrevs); if (filteredrevs != Py_None) { filter = PyObject_GetAttrString(filteredrevs, "__contains__"); if (!filter) { PyErr_SetString(PyExc_TypeError, "filteredrevs has no attribute __contains__"); goto bail; } } len = index_length(self) - 1; heads = PyList_New(0); if (heads == NULL) goto bail; if (len == 0) { PyObject *nullid = PyInt_FromLong(-1); if (nullid == NULL || PyList_Append(heads, nullid) == -1) { Py_XDECREF(nullid); goto bail; } goto done; } nothead = calloc(len, 1); if (nothead == NULL) goto bail; for (i = 0; i < self->raw_length; i++) { const char *data; int parent_1, parent_2, isfiltered; isfiltered = check_filter(filter, i); if (isfiltered == -1) { PyErr_SetString(PyExc_TypeError, "unable to check filter"); goto bail; } if (isfiltered) { nothead[i] = 1; continue; } data = index_deref(self, i); parent_1 = getbe32(data + 24); parent_2 = getbe32(data + 28); if (parent_1 >= 0) nothead[parent_1] = 1; if (parent_2 >= 0) nothead[parent_2] = 1; } addlen = self->added ? PyList_GET_SIZE(self->added) : 0; for (i = 0; i < addlen; i++) { PyObject *rev = PyList_GET_ITEM(self->added, i); PyObject *p1 = PyTuple_GET_ITEM(rev, 5); PyObject *p2 = PyTuple_GET_ITEM(rev, 6); long parent_1, parent_2; int isfiltered; if (!PyInt_Check(p1) || !PyInt_Check(p2)) { PyErr_SetString(PyExc_TypeError, "revlog parents are invalid"); goto bail; } isfiltered = check_filter(filter, i); if (isfiltered == -1) { PyErr_SetString(PyExc_TypeError, "unable to check filter"); goto bail; } if (isfiltered) { nothead[i] = 1; continue; } parent_1 = PyInt_AS_LONG(p1); parent_2 = PyInt_AS_LONG(p2); if (parent_1 >= 0) nothead[parent_1] = 1; if (parent_2 >= 0) nothead[parent_2] = 1; } for (i = 0; i < len; i++) { PyObject *head; if (nothead[i]) continue; head = PyInt_FromSsize_t(i); if (head == NULL || PyList_Append(heads, head) == -1) { Py_XDECREF(head); goto bail; } } done: self->headrevs = heads; Py_XDECREF(filter); free(nothead); return list_copy(self->headrevs); bail: Py_XDECREF(filter); Py_XDECREF(heads); free(nothead); return NULL; } static inline int nt_level(const char *node, Py_ssize_t level) { int v = node[level>>1]; if (!(level & 1)) v >>= 4; return v & 0xf; } /* * Return values: * * -4: match is ambiguous (multiple candidates) * -2: not found * rest: valid rev */ static int nt_find(indexObject *self, const char *node, Py_ssize_t nodelen, int hex) { int (*getnybble)(const char *, Py_ssize_t) = hex ? hexdigit : nt_level; int level, maxlevel, off; if (nodelen == 20 && node[0] == '\0' && memcmp(node, nullid, 20) == 0) return -1; if (self->nt == NULL) return -2; if (hex) maxlevel = nodelen > 40 ? 40 : (int)nodelen; else maxlevel = nodelen > 20 ? 40 : ((int)nodelen * 2); for (level = off = 0; level < maxlevel; level++) { int k = getnybble(node, level); nodetree *n = &self->nt[off]; int v = n->children[k]; if (v < 0) { const char *n; Py_ssize_t i; v = -v - 1; n = index_node(self, v); if (n == NULL) return -2; for (i = level; i < maxlevel; i++) if (getnybble(node, i) != nt_level(n, i)) return -2; return v; } if (v == 0) return -2; off = v; } /* multiple matches against an ambiguous prefix */ return -4; } static int nt_new(indexObject *self) { if (self->ntlength == self->ntcapacity) { if (self->ntcapacity >= INT_MAX / (sizeof(nodetree) * 2)) { PyErr_SetString(PyExc_MemoryError, "overflow in nt_new"); return -1; } self->ntcapacity *= 2; self->nt = realloc(self->nt, self->ntcapacity * sizeof(nodetree)); if (self->nt == NULL) { PyErr_SetString(PyExc_MemoryError, "out of memory"); return -1; } memset(&self->nt[self->ntlength], 0, sizeof(nodetree) * (self->ntcapacity - self->ntlength)); } return self->ntlength++; } static int nt_insert(indexObject *self, const char *node, int rev) { int level = 0; int off = 0; while (level < 40) { int k = nt_level(node, level); nodetree *n; int v; n = &self->nt[off]; v = n->children[k]; if (v == 0) { n->children[k] = -rev - 1; return 0; } if (v < 0) { const char *oldnode = index_node(self, -v - 1); int noff; if (!oldnode || !memcmp(oldnode, node, 20)) { n->children[k] = -rev - 1; return 0; } noff = nt_new(self); if (noff == -1) return -1; /* self->nt may have been changed by realloc */ self->nt[off].children[k] = noff; off = noff; n = &self->nt[off]; n->children[nt_level(oldnode, ++level)] = v; if (level > self->ntdepth) self->ntdepth = level; self->ntsplits += 1; } else { level += 1; off = v; } } return -1; } static int nt_init(indexObject *self) { if (self->nt == NULL) { if (self->raw_length > INT_MAX / sizeof(nodetree)) { PyErr_SetString(PyExc_ValueError, "overflow in nt_init"); return -1; } self->ntcapacity = self->raw_length < 4 ? 4 : (int)self->raw_length / 2; self->nt = calloc(self->ntcapacity, sizeof(nodetree)); if (self->nt == NULL) { PyErr_NoMemory(); return -1; } self->ntlength = 1; self->ntrev = (int)index_length(self) - 1; self->ntlookups = 1; self->ntmisses = 0; if (nt_insert(self, nullid, INT_MAX) == -1) return -1; } return 0; } /* * Return values: * * -3: error (exception set) * -2: not found (no exception set) * rest: valid rev */ static int index_find_node(indexObject *self, const char *node, Py_ssize_t nodelen) { int rev; self->ntlookups++; rev = nt_find(self, node, nodelen, 0); if (rev >= -1) return rev; if (nt_init(self) == -1) return -3; /* * For the first handful of lookups, we scan the entire index, * and cache only the matching nodes. This optimizes for cases * like "hg tip", where only a few nodes are accessed. * * After that, we cache every node we visit, using a single * scan amortized over multiple lookups. This gives the best * bulk performance, e.g. for "hg log". */ if (self->ntmisses++ < 4) { for (rev = self->ntrev - 1; rev >= 0; rev--) { const char *n = index_node(self, rev); if (n == NULL) return -2; if (memcmp(node, n, nodelen > 20 ? 20 : nodelen) == 0) { if (nt_insert(self, n, rev) == -1) return -3; break; } } } else { for (rev = self->ntrev - 1; rev >= 0; rev--) { const char *n = index_node(self, rev); if (n == NULL) { self->ntrev = rev + 1; return -2; } if (nt_insert(self, n, rev) == -1) { self->ntrev = rev + 1; return -3; } if (memcmp(node, n, nodelen > 20 ? 20 : nodelen) == 0) { break; } } self->ntrev = rev; } if (rev >= 0) return rev; return -2; } static PyObject *raise_revlog_error(void) { static PyObject *errclass; PyObject *mod = NULL, *errobj; if (errclass == NULL) { PyObject *dict; mod = PyImport_ImportModule("mercurial.error"); if (mod == NULL) goto classfail; dict = PyModule_GetDict(mod); if (dict == NULL) goto classfail; errclass = PyDict_GetItemString(dict, "RevlogError"); if (errclass == NULL) { PyErr_SetString(PyExc_SystemError, "could not find RevlogError"); goto classfail; } Py_INCREF(errclass); Py_DECREF(mod); } errobj = PyObject_CallFunction(errclass, NULL); if (errobj == NULL) return NULL; PyErr_SetObject(errclass, errobj); return errobj; classfail: Py_XDECREF(mod); return NULL; } static PyObject *index_getitem(indexObject *self, PyObject *value) { char *node; Py_ssize_t nodelen; int rev; if (PyInt_Check(value)) return index_get(self, PyInt_AS_LONG(value)); if (node_check(value, &node, &nodelen) == -1) return NULL; rev = index_find_node(self, node, nodelen); if (rev >= -1) return PyInt_FromLong(rev); if (rev == -2) raise_revlog_error(); return NULL; } static int nt_partialmatch(indexObject *self, const char *node, Py_ssize_t nodelen) { int rev; if (nt_init(self) == -1) return -3; if (self->ntrev > 0) { /* ensure that the radix tree is fully populated */ for (rev = self->ntrev - 1; rev >= 0; rev--) { const char *n = index_node(self, rev); if (n == NULL) return -2; if (nt_insert(self, n, rev) == -1) return -3; } self->ntrev = rev; } return nt_find(self, node, nodelen, 1); } static PyObject *index_partialmatch(indexObject *self, PyObject *args) { const char *fullnode; int nodelen; char *node; int rev, i; if (!PyArg_ParseTuple(args, "s#", &node, &nodelen)) return NULL; if (nodelen < 4) { PyErr_SetString(PyExc_ValueError, "key too short"); return NULL; } if (nodelen > 40) { PyErr_SetString(PyExc_ValueError, "key too long"); return NULL; } for (i = 0; i < nodelen; i++) hexdigit(node, i); if (PyErr_Occurred()) { /* input contains non-hex characters */ PyErr_Clear(); Py_RETURN_NONE; } rev = nt_partialmatch(self, node, nodelen); switch (rev) { case -4: raise_revlog_error(); case -3: return NULL; case -2: Py_RETURN_NONE; case -1: return PyString_FromStringAndSize(nullid, 20); } fullnode = index_node(self, rev); if (fullnode == NULL) { PyErr_Format(PyExc_IndexError, "could not access rev %d", rev); return NULL; } return PyString_FromStringAndSize(fullnode, 20); } static PyObject *index_m_get(indexObject *self, PyObject *args) { Py_ssize_t nodelen; PyObject *val; char *node; int rev; if (!PyArg_ParseTuple(args, "O", &val)) return NULL; if (node_check(val, &node, &nodelen) == -1) return NULL; rev = index_find_node(self, node, nodelen); if (rev == -3) return NULL; if (rev == -2) Py_RETURN_NONE; return PyInt_FromLong(rev); } static int index_contains(indexObject *self, PyObject *value) { char *node; Py_ssize_t nodelen; if (PyInt_Check(value)) { long rev = PyInt_AS_LONG(value); return rev >= -1 && rev < index_length(self); } if (node_check(value, &node, &nodelen) == -1) return -1; switch (index_find_node(self, node, nodelen)) { case -3: return -1; case -2: return 0; default: return 1; } } static inline void index_get_parents(indexObject *self, int rev, int *ps) { if (rev >= self->length - 1) { PyObject *tuple = PyList_GET_ITEM(self->added, rev - self->length + 1); ps[0] = (int)PyInt_AS_LONG(PyTuple_GET_ITEM(tuple, 5)); ps[1] = (int)PyInt_AS_LONG(PyTuple_GET_ITEM(tuple, 6)); } else { const char *data = index_deref(self, rev); ps[0] = getbe32(data + 24); ps[1] = getbe32(data + 28); } } typedef uint64_t bitmask; /* * Given a disjoint set of revs, return all candidates for the * greatest common ancestor. In revset notation, this is the set * "heads(::a and ::b and ...)" */ static PyObject *find_gca_candidates(indexObject *self, const int *revs, int revcount) { const bitmask allseen = (1ull << revcount) - 1; const bitmask poison = 1ull << revcount; PyObject *gca = PyList_New(0); int i, v, interesting; int maxrev = -1; bitmask sp; bitmask *seen; if (gca == NULL) return PyErr_NoMemory(); for (i = 0; i < revcount; i++) { if (revs[i] > maxrev) maxrev = revs[i]; } seen = calloc(sizeof(*seen), maxrev + 1); if (seen == NULL) { Py_DECREF(gca); return PyErr_NoMemory(); } for (i = 0; i < revcount; i++) seen[revs[i]] = 1ull << i; interesting = revcount; for (v = maxrev; v >= 0 && interesting; v--) { bitmask sv = seen[v]; int parents[2]; if (!sv) continue; if (sv < poison) { interesting -= 1; if (sv == allseen) { PyObject *obj = PyInt_FromLong(v); if (obj == NULL) goto bail; if (PyList_Append(gca, obj) == -1) { Py_DECREF(obj); goto bail; } sv |= poison; for (i = 0; i < revcount; i++) { if (revs[i] == v) goto done; } } } index_get_parents(self, v, parents); for (i = 0; i < 2; i++) { int p = parents[i]; if (p == -1) continue; sp = seen[p]; if (sv < poison) { if (sp == 0) { seen[p] = sv; interesting++; } else if (sp != sv) seen[p] |= sv; } else { if (sp && sp < poison) interesting--; seen[p] = sv; } } } done: free(seen); return gca; bail: free(seen); Py_XDECREF(gca); return NULL; } /* * Given a disjoint set of revs, return the subset with the longest * path to the root. */ static PyObject *find_deepest(indexObject *self, PyObject *revs) { const Py_ssize_t revcount = PyList_GET_SIZE(revs); static const Py_ssize_t capacity = 24; int *depth, *interesting = NULL; int i, j, v, ninteresting; PyObject *dict = NULL, *keys = NULL; long *seen = NULL; int maxrev = -1; long final; if (revcount > capacity) { PyErr_Format(PyExc_OverflowError, "bitset size (%ld) > capacity (%ld)", (long)revcount, (long)capacity); return NULL; } for (i = 0; i < revcount; i++) { int n = (int)PyInt_AsLong(PyList_GET_ITEM(revs, i)); if (n > maxrev) maxrev = n; } depth = calloc(sizeof(*depth), maxrev + 1); if (depth == NULL) return PyErr_NoMemory(); seen = calloc(sizeof(*seen), maxrev + 1); if (seen == NULL) { PyErr_NoMemory(); goto bail; } interesting = calloc(sizeof(*interesting), 2 << revcount); if (interesting == NULL) { PyErr_NoMemory(); goto bail; } if (PyList_Sort(revs) == -1) goto bail; for (i = 0; i < revcount; i++) { int n = (int)PyInt_AsLong(PyList_GET_ITEM(revs, i)); long b = 1l << i; depth[n] = 1; seen[n] = b; interesting[b] = 1; } ninteresting = (int)revcount; for (v = maxrev; v >= 0 && ninteresting > 1; v--) { int dv = depth[v]; int parents[2]; long sv; if (dv == 0) continue; sv = seen[v]; index_get_parents(self, v, parents); for (i = 0; i < 2; i++) { int p = parents[i]; long nsp, sp; int dp; if (p == -1) continue; dp = depth[p]; nsp = sp = seen[p]; if (dp <= dv) { depth[p] = dv + 1; if (sp != sv) { interesting[sv] += 1; nsp = seen[p] = sv; if (sp) { interesting[sp] -= 1; if (interesting[sp] == 0) ninteresting -= 1; } } } else if (dv == dp - 1) { nsp = sp | sv; if (nsp == sp) continue; seen[p] = nsp; interesting[sp] -= 1; if (interesting[sp] == 0 && interesting[nsp] > 0) ninteresting -= 1; interesting[nsp] += 1; } } interesting[sv] -= 1; if (interesting[sv] == 0) ninteresting -= 1; } final = 0; j = ninteresting; for (i = 0; i < (int)(2 << revcount) && j > 0; i++) { if (interesting[i] == 0) continue; final |= i; j -= 1; } if (final == 0) { keys = PyList_New(0); goto bail; } dict = PyDict_New(); if (dict == NULL) goto bail; for (i = 0; i < revcount; i++) { PyObject *key; if ((final & (1 << i)) == 0) continue; key = PyList_GET_ITEM(revs, i); Py_INCREF(key); Py_INCREF(Py_None); if (PyDict_SetItem(dict, key, Py_None) == -1) { Py_DECREF(key); Py_DECREF(Py_None); goto bail; } } keys = PyDict_Keys(dict); bail: free(depth); free(seen); free(interesting); Py_XDECREF(dict); return keys; } /* * Given a (possibly overlapping) set of revs, return all the * common ancestors heads: heads(::args[0] and ::a[1] and ...) */ static PyObject *index_commonancestorsheads(indexObject *self, PyObject *args) { PyObject *ret = NULL; Py_ssize_t argcount, i, len; bitmask repeat = 0; int revcount = 0; int *revs; argcount = PySequence_Length(args); revs = malloc(argcount * sizeof(*revs)); if (argcount > 0 && revs == NULL) return PyErr_NoMemory(); len = index_length(self) - 1; for (i = 0; i < argcount; i++) { static const int capacity = 24; PyObject *obj = PySequence_GetItem(args, i); bitmask x; long val; if (!PyInt_Check(obj)) { PyErr_SetString(PyExc_TypeError, "arguments must all be ints"); Py_DECREF(obj); goto bail; } val = PyInt_AsLong(obj); Py_DECREF(obj); if (val == -1) { ret = PyList_New(0); goto done; } if (val < 0 || val >= len) { PyErr_SetString(PyExc_IndexError, "index out of range"); goto bail; } /* this cheesy bloom filter lets us avoid some more * expensive duplicate checks in the common set-is-disjoint * case */ x = 1ull << (val & 0x3f); if (repeat & x) { int k; for (k = 0; k < revcount; k++) { if (val == revs[k]) goto duplicate; } } else repeat |= x; if (revcount >= capacity) { PyErr_Format(PyExc_OverflowError, "bitset size (%d) > capacity (%d)", revcount, capacity); goto bail; } revs[revcount++] = (int)val; duplicate:; } if (revcount == 0) { ret = PyList_New(0); goto done; } if (revcount == 1) { PyObject *obj; ret = PyList_New(1); if (ret == NULL) goto bail; obj = PyInt_FromLong(revs[0]); if (obj == NULL) goto bail; PyList_SET_ITEM(ret, 0, obj); goto done; } ret = find_gca_candidates(self, revs, revcount); if (ret == NULL) goto bail; done: free(revs); return ret; bail: free(revs); Py_XDECREF(ret); return NULL; } /* * Given a (possibly overlapping) set of revs, return the greatest * common ancestors: those with the longest path to the root. */ static PyObject *index_ancestors(indexObject *self, PyObject *args) { PyObject *gca = index_commonancestorsheads(self, args); if (gca == NULL) return NULL; if (PyList_GET_SIZE(gca) <= 1) { Py_INCREF(gca); return gca; } return find_deepest(self, gca); } /* * Invalidate any trie entries introduced by added revs. */ static void nt_invalidate_added(indexObject *self, Py_ssize_t start) { Py_ssize_t i, len = PyList_GET_SIZE(self->added); for (i = start; i < len; i++) { PyObject *tuple = PyList_GET_ITEM(self->added, i); PyObject *node = PyTuple_GET_ITEM(tuple, 7); nt_insert(self, PyString_AS_STRING(node), -1); } if (start == 0) Py_CLEAR(self->added); } /* * Delete a numeric range of revs, which must be at the end of the * range, but exclude the sentinel nullid entry. */ static int index_slice_del(indexObject *self, PyObject *item) { Py_ssize_t start, stop, step, slicelength; Py_ssize_t length = index_length(self); int ret = 0; if (PySlice_GetIndicesEx((PySliceObject*)item, length, &start, &stop, &step, &slicelength) < 0) return -1; if (slicelength <= 0) return 0; if ((step < 0 && start < stop) || (step > 0 && start > stop)) stop = start; if (step < 0) { stop = start + 1; start = stop + step*(slicelength - 1) - 1; step = -step; } if (step != 1) { PyErr_SetString(PyExc_ValueError, "revlog index delete requires step size of 1"); return -1; } if (stop != length - 1) { PyErr_SetString(PyExc_IndexError, "revlog index deletion indices are invalid"); return -1; } if (start < self->length - 1) { if (self->nt) { Py_ssize_t i; for (i = start + 1; i < self->length - 1; i++) { const char *node = index_node(self, i); if (node) nt_insert(self, node, -1); } if (self->added) nt_invalidate_added(self, 0); if (self->ntrev > start) self->ntrev = (int)start; } self->length = start + 1; if (start < self->raw_length) { if (self->cache) { Py_ssize_t i; for (i = start; i < self->raw_length; i++) Py_CLEAR(self->cache[i]); } self->raw_length = start; } goto done; } if (self->nt) { nt_invalidate_added(self, start - self->length + 1); if (self->ntrev > start) self->ntrev = (int)start; } if (self->added) ret = PyList_SetSlice(self->added, start - self->length + 1, PyList_GET_SIZE(self->added), NULL); done: Py_CLEAR(self->headrevs); return ret; } /* * Supported ops: * * slice deletion * string assignment (extend node->rev mapping) * string deletion (shrink node->rev mapping) */ static int index_assign_subscript(indexObject *self, PyObject *item, PyObject *value) { char *node; Py_ssize_t nodelen; long rev; if (PySlice_Check(item) && value == NULL) return index_slice_del(self, item); if (node_check(item, &node, &nodelen) == -1) return -1; if (value == NULL) return self->nt ? nt_insert(self, node, -1) : 0; rev = PyInt_AsLong(value); if (rev > INT_MAX || rev < 0) { if (!PyErr_Occurred()) PyErr_SetString(PyExc_ValueError, "rev out of range"); return -1; } if (nt_init(self) == -1) return -1; return nt_insert(self, node, (int)rev); } /* * Find all RevlogNG entries in an index that has inline data. Update * the optional "offsets" table with those entries. */ static Py_ssize_t inline_scan(indexObject *self, const char **offsets) { const char *data = PyString_AS_STRING(self->data); Py_ssize_t pos = 0; Py_ssize_t end = PyString_GET_SIZE(self->data); long incr = v1_hdrsize; Py_ssize_t len = 0; while (pos + v1_hdrsize <= end && pos >= 0) { uint32_t comp_len; /* 3rd element of header is length of compressed inline data */ comp_len = getbe32(data + pos + 8); incr = v1_hdrsize + comp_len; if (offsets) offsets[len] = data + pos; len++; pos += incr; } if (pos != end) { if (!PyErr_Occurred()) PyErr_SetString(PyExc_ValueError, "corrupt index file"); return -1; } return len; } static int index_init(indexObject *self, PyObject *args) { PyObject *data_obj, *inlined_obj; Py_ssize_t size; /* Initialize before argument-checking to avoid index_dealloc() crash. */ self->raw_length = 0; self->added = NULL; self->cache = NULL; self->data = NULL; self->headrevs = NULL; self->filteredrevs = Py_None; Py_INCREF(Py_None); self->nt = NULL; self->offsets = NULL; if (!PyArg_ParseTuple(args, "OO", &data_obj, &inlined_obj)) return -1; if (!PyString_Check(data_obj)) { PyErr_SetString(PyExc_TypeError, "data is not a string"); return -1; } size = PyString_GET_SIZE(data_obj); self->inlined = inlined_obj && PyObject_IsTrue(inlined_obj); self->data = data_obj; self->ntlength = self->ntcapacity = 0; self->ntdepth = self->ntsplits = 0; self->ntlookups = self->ntmisses = 0; self->ntrev = -1; Py_INCREF(self->data); if (self->inlined) { Py_ssize_t len = inline_scan(self, NULL); if (len == -1) goto bail; self->raw_length = len; self->length = len + 1; } else { if (size % v1_hdrsize) { PyErr_SetString(PyExc_ValueError, "corrupt index file"); goto bail; } self->raw_length = size / v1_hdrsize; self->length = self->raw_length + 1; } return 0; bail: return -1; } static PyObject *index_nodemap(indexObject *self) { Py_INCREF(self); return (PyObject *)self; } static void index_dealloc(indexObject *self) { _index_clearcaches(self); Py_XDECREF(self->filteredrevs); Py_XDECREF(self->data); Py_XDECREF(self->added); PyObject_Del(self); } static PySequenceMethods index_sequence_methods = { (lenfunc)index_length, /* sq_length */ 0, /* sq_concat */ 0, /* sq_repeat */ (ssizeargfunc)index_get, /* sq_item */ 0, /* sq_slice */ 0, /* sq_ass_item */ 0, /* sq_ass_slice */ (objobjproc)index_contains, /* sq_contains */ }; static PyMappingMethods index_mapping_methods = { (lenfunc)index_length, /* mp_length */ (binaryfunc)index_getitem, /* mp_subscript */ (objobjargproc)index_assign_subscript, /* mp_ass_subscript */ }; static PyMethodDef index_methods[] = { {"ancestors", (PyCFunction)index_ancestors, METH_VARARGS, "return the gca set of the given revs"}, {"commonancestorsheads", (PyCFunction)index_commonancestorsheads, METH_VARARGS, "return the heads of the common ancestors of the given revs"}, {"clearcaches", (PyCFunction)index_clearcaches, METH_NOARGS, "clear the index caches"}, {"get", (PyCFunction)index_m_get, METH_VARARGS, "get an index entry"}, {"computephases", (PyCFunction)compute_phases, METH_VARARGS, "compute phases"}, {"headrevs", (PyCFunction)index_headrevs, METH_VARARGS, "get head revisions"}, /* Can do filtering since 3.2 */ {"headrevsfiltered", (PyCFunction)index_headrevs, METH_VARARGS, "get filtered head revisions"}, /* Can always do filtering */ {"insert", (PyCFunction)index_insert, METH_VARARGS, "insert an index entry"}, {"partialmatch", (PyCFunction)index_partialmatch, METH_VARARGS, "match a potentially ambiguous node ID"}, {"stats", (PyCFunction)index_stats, METH_NOARGS, "stats for the index"}, {NULL} /* Sentinel */ }; static PyGetSetDef index_getset[] = { {"nodemap", (getter)index_nodemap, NULL, "nodemap", NULL}, {NULL} /* Sentinel */ }; static PyTypeObject indexType = { PyObject_HEAD_INIT(NULL) 0, /* ob_size */ "parsers.index", /* tp_name */ sizeof(indexObject), /* tp_basicsize */ 0, /* tp_itemsize */ (destructor)index_dealloc, /* tp_dealloc */ 0, /* tp_print */ 0, /* tp_getattr */ 0, /* tp_setattr */ 0, /* tp_compare */ 0, /* tp_repr */ 0, /* tp_as_number */ &index_sequence_methods, /* tp_as_sequence */ &index_mapping_methods, /* tp_as_mapping */ 0, /* tp_hash */ 0, /* tp_call */ 0, /* tp_str */ 0, /* tp_getattro */ 0, /* tp_setattro */ 0, /* tp_as_buffer */ Py_TPFLAGS_DEFAULT, /* tp_flags */ "revlog index", /* tp_doc */ 0, /* tp_traverse */ 0, /* tp_clear */ 0, /* tp_richcompare */ 0, /* tp_weaklistoffset */ 0, /* tp_iter */ 0, /* tp_iternext */ index_methods, /* tp_methods */ 0, /* tp_members */ index_getset, /* tp_getset */ 0, /* tp_base */ 0, /* tp_dict */ 0, /* tp_descr_get */ 0, /* tp_descr_set */ 0, /* tp_dictoffset */ (initproc)index_init, /* tp_init */ 0, /* tp_alloc */ }; /* * returns a tuple of the form (index, index, cache) with elements as * follows: * * index: an index object that lazily parses RevlogNG records * cache: if data is inlined, a tuple (index_file_content, 0), else None * * added complications are for backwards compatibility */ static PyObject *parse_index2(PyObject *self, PyObject *args) { PyObject *tuple = NULL, *cache = NULL; indexObject *idx; int ret; idx = PyObject_New(indexObject, &indexType); if (idx == NULL) goto bail; ret = index_init(idx, args); if (ret == -1) goto bail; if (idx->inlined) { cache = Py_BuildValue("iO", 0, idx->data); if (cache == NULL) goto bail; } else { cache = Py_None; Py_INCREF(cache); } tuple = Py_BuildValue("NN", idx, cache); if (!tuple) goto bail; return tuple; bail: Py_XDECREF(idx); Py_XDECREF(cache); Py_XDECREF(tuple); return NULL; } #define BUMPED_FIX 1 #define USING_SHA_256 2 static PyObject *readshas( const char *source, unsigned char num, Py_ssize_t hashwidth) { int i; PyObject *list = PyTuple_New(num); if (list == NULL) { return NULL; } for (i = 0; i < num; i++) { PyObject *hash = PyString_FromStringAndSize(source, hashwidth); if (hash == NULL) { Py_DECREF(list); return NULL; } PyTuple_SetItem(list, i, hash); source += hashwidth; } return list; } static PyObject *fm1readmarker(const char *data, uint32_t *msize) { const char *meta; double mtime; int16_t tz; uint16_t flags; unsigned char nsuccs, nparents, nmetadata; Py_ssize_t hashwidth = 20; PyObject *prec = NULL, *parents = NULL, *succs = NULL; PyObject *metadata = NULL, *ret = NULL; int i; *msize = getbe32(data); data += 4; mtime = getbefloat64(data); data += 8; tz = getbeint16(data); data += 2; flags = getbeuint16(data); data += 2; if (flags & USING_SHA_256) { hashwidth = 32; } nsuccs = (unsigned char)(*data++); nparents = (unsigned char)(*data++); nmetadata = (unsigned char)(*data++); prec = PyString_FromStringAndSize(data, hashwidth); data += hashwidth; if (prec == NULL) { goto bail; } succs = readshas(data, nsuccs, hashwidth); if (succs == NULL) { goto bail; } data += nsuccs * hashwidth; if (nparents == 1 || nparents == 2) { parents = readshas(data, nparents, hashwidth); if (parents == NULL) { goto bail; } data += nparents * hashwidth; } else { parents = Py_None; } meta = data + (2 * nmetadata); metadata = PyTuple_New(nmetadata); if (metadata == NULL) { goto bail; } for (i = 0; i < nmetadata; i++) { PyObject *tmp, *left = NULL, *right = NULL; Py_ssize_t metasize = (unsigned char)(*data++); left = PyString_FromStringAndSize(meta, metasize); meta += metasize; metasize = (unsigned char)(*data++); right = PyString_FromStringAndSize(meta, metasize); meta += metasize; if (!left || !right) { Py_XDECREF(left); Py_XDECREF(right); goto bail; } tmp = PyTuple_Pack(2, left, right); Py_DECREF(left); Py_DECREF(right); if (!tmp) { goto bail; } PyTuple_SetItem(metadata, i, tmp); } ret = Py_BuildValue("(OOHO(di)O)", prec, succs, flags, metadata, mtime, (int)tz * 60, parents); bail: Py_XDECREF(prec); Py_XDECREF(succs); Py_XDECREF(metadata); if (parents != Py_None) Py_XDECREF(parents); return ret; } static PyObject *fm1readmarkers(PyObject *self, PyObject *args) { const char *data; Py_ssize_t datalen; /* only unsigned long because python 2.4, should be Py_ssize_t */ unsigned long offset, stop; PyObject *markers = NULL; /* replace kk with nn when we drop Python 2.4 */ if (!PyArg_ParseTuple(args, "s#kk", &data, &datalen, &offset, &stop)) { return NULL; } data += offset; markers = PyList_New(0); if (!markers) { return NULL; } while (offset < stop) { uint32_t msize; int error; PyObject *record = fm1readmarker(data, &msize); if (!record) { goto bail; } error = PyList_Append(markers, record); Py_DECREF(record); if (error) { goto bail; } data += msize; offset += msize; } return markers; bail: Py_DECREF(markers); return NULL; } static char parsers_doc[] = "Efficient content parsing."; PyObject *encodedir(PyObject *self, PyObject *args); PyObject *pathencode(PyObject *self, PyObject *args); PyObject *lowerencode(PyObject *self, PyObject *args); static PyMethodDef methods[] = { {"pack_dirstate", pack_dirstate, METH_VARARGS, "pack a dirstate\n"}, {"parse_manifest", parse_manifest, METH_VARARGS, "parse a manifest\n"}, {"parse_dirstate", parse_dirstate, METH_VARARGS, "parse a dirstate\n"}, {"parse_index2", parse_index2, METH_VARARGS, "parse a revlog index\n"}, {"asciilower", asciilower, METH_VARARGS, "lowercase an ASCII string\n"}, {"asciiupper", asciiupper, METH_VARARGS, "uppercase an ASCII string\n"}, {"make_file_foldmap", make_file_foldmap, METH_VARARGS, "make file foldmap\n"}, {"encodedir", encodedir, METH_VARARGS, "encodedir a path\n"}, {"pathencode", pathencode, METH_VARARGS, "fncache-encode a path\n"}, {"lowerencode", lowerencode, METH_VARARGS, "lower-encode a path\n"}, {"fm1readmarkers", fm1readmarkers, METH_VARARGS, "parse v1 obsolete markers\n"}, {NULL, NULL} }; void dirs_module_init(PyObject *mod); void manifest_module_init(PyObject *mod); static void module_init(PyObject *mod) { /* This module constant has two purposes. First, it lets us unit test * the ImportError raised without hard-coding any error text. This * means we can change the text in the future without breaking tests, * even across changesets without a recompile. Second, its presence * can be used to determine whether the version-checking logic is * present, which also helps in testing across changesets without a * recompile. Note that this means the pure-Python version of parsers * should not have this module constant. */ PyModule_AddStringConstant(mod, "versionerrortext", versionerrortext); dirs_module_init(mod); manifest_module_init(mod); indexType.tp_new = PyType_GenericNew; if (PyType_Ready(&indexType) < 0 || PyType_Ready(&dirstateTupleType) < 0) return; Py_INCREF(&indexType); PyModule_AddObject(mod, "index", (PyObject *)&indexType); Py_INCREF(&dirstateTupleType); PyModule_AddObject(mod, "dirstatetuple", (PyObject *)&dirstateTupleType); nullentry = Py_BuildValue("iiiiiiis#", 0, 0, 0, -1, -1, -1, -1, nullid, 20); if (nullentry) PyObject_GC_UnTrack(nullentry); } static int check_python_version(void) { PyObject *sys = PyImport_ImportModule("sys"), *ver; long hexversion; if (!sys) return -1; ver = PyObject_GetAttrString(sys, "hexversion"); Py_DECREF(sys); if (!ver) return -1; hexversion = PyInt_AsLong(ver); Py_DECREF(ver); /* sys.hexversion is a 32-bit number by default, so the -1 case * should only occur in unusual circumstances (e.g. if sys.hexversion * is manually set to an invalid value). */ if ((hexversion == -1) || (hexversion >> 16 != PY_VERSION_HEX >> 16)) { PyErr_Format(PyExc_ImportError, "%s: The Mercurial extension " "modules were compiled with Python " PY_VERSION ", but " "Mercurial is currently using Python with sys.hexversion=%ld: " "Python %s\n at: %s", versionerrortext, hexversion, Py_GetVersion(), Py_GetProgramFullPath()); return -1; } return 0; } #ifdef IS_PY3K static struct PyModuleDef parsers_module = { PyModuleDef_HEAD_INIT, "parsers", parsers_doc, -1, methods }; PyMODINIT_FUNC PyInit_parsers(void) { PyObject *mod; if (check_python_version() == -1) return; mod = PyModule_Create(&parsers_module); module_init(mod); return mod; } #else PyMODINIT_FUNC initparsers(void) { PyObject *mod; if (check_python_version() == -1) return; mod = Py_InitModule3("parsers", methods, parsers_doc); module_init(mod); } #endif