D3499: revlog: use node tree (native code) for shortest() calculation
martinvonz (Martin von Zweigbergk)
phabricator at mercurial-scm.org
Thu May 10 12:02:14 EDT 2018
martinvonz updated this revision to Diff 8624.
REPOSITORY
rHG Mercurial
CHANGES SINCE LAST UPDATE
https://phab.mercurial-scm.org/D3499?vs=8552&id=8624
REVISION DETAIL
https://phab.mercurial-scm.org/D3499
AFFECTED FILES
mercurial/cext/parsers.c
mercurial/cext/revlog.c
mercurial/policy.py
mercurial/revlog.py
CHANGE DETAILS
diff --git a/mercurial/revlog.py b/mercurial/revlog.py
--- a/mercurial/revlog.py
+++ b/mercurial/revlog.py
@@ -1526,7 +1526,33 @@
raise LookupError(node, self.indexfile, _('no node'))
return not isrev(prefix)
+ def maybewdir(prefix):
+ return all(c == 'f' for c in prefix)
+
hexnode = hex(node)
+
+ def disambiguate(hexnode, minlength):
+ for length in range(minlength, 41):
+ prefix = hexnode[:length]
+ if not isrev(prefix) and not maybewdir(prefix):
+ return prefix
+
+ if not getattr(self, 'filteredrevs', None):
+ try:
+ length = max(self.index.shortest(node), minlength)
+ return disambiguate(hexnode, length)
+ except RevlogError:
+ if node == wdirid:
+ for length in range(minlength, 41):
+ prefix = hexnode[:length]
+ if isvalid(prefix):
+ return prefix
+ else:
+ raise LookupError(node, self.indexfile, _('no node'))
+ except AttributeError:
+ # Fall through to pure code
+ pass
+
shortest = hexnode
startlength = max(6, minlength)
length = startlength
diff --git a/mercurial/policy.py b/mercurial/policy.py
--- a/mercurial/policy.py
+++ b/mercurial/policy.py
@@ -69,7 +69,7 @@
(r'cext', r'bdiff'): 3,
(r'cext', r'mpatch'): 1,
(r'cext', r'osutil'): 4,
- (r'cext', r'parsers'): 4,
+ (r'cext', r'parsers'): 5,
}
# map import request to other package or module
diff --git a/mercurial/cext/revlog.c b/mercurial/cext/revlog.c
--- a/mercurial/cext/revlog.c
+++ b/mercurial/cext/revlog.c
@@ -1259,6 +1259,54 @@
return nt_find(self, node, nodelen, 1);
}
+/*
+ * Find the length of the shortest unique prefix of node.
+ *
+ * Return values:
+ *
+ * -3: error (exception set)
+ * -2: not found (no exception set)
+ * rest: length of shortest prefix
+ */
+static int nt_shortest(indexObject *self, const char *node)
+{
+ int level, off;
+
+ if (nt_init(self) == -1)
+ return -3;
+ if (nt_populate(self) == -1)
+ return -3;
+
+ for (level = off = 0; level < 40; level++) {
+ int k, v;
+ nodetree *n = &self->nt[off];
+ k = nt_level(node, level);
+ v = n->children[k];
+ if (v < 0) {
+ v = -(v + 1);
+ const char *n = index_node(self, v);
+ if (memcmp(node, n, 20) != 0)
+ /*
+ * Found a unique prefix, but it wasn't for the
+ * requested node (i.e the requested node does
+ * not exist).
+ */
+ return -2;
+ return level + 1;
+ }
+ if (v == 0)
+ return -2;
+ off = v;
+ }
+ /*
+ * The node was still not unique after 40 hex digits, so this won't
+ * happen. Also, if we get here, then there's a programming error in
+ * this file that made us insert a node longer than 40 hex digits.
+ */
+ PyErr_SetString(PyExc_Exception, "broken node tree");
+ return -3;
+}
+
static PyObject *index_partialmatch(indexObject *self, PyObject *args)
{
const char *fullnode;
@@ -1307,6 +1355,29 @@
return PyBytes_FromStringAndSize(fullnode, 20);
}
+static PyObject *index_shortest(indexObject *self, PyObject *args)
+{
+ Py_ssize_t nodelen;
+ PyObject *val;
+ char *node;
+ int length;
+
+ if (!PyArg_ParseTuple(args, "O", &val))
+ return NULL;
+ if (node_check(val, &node, &nodelen) == -1)
+ return NULL;
+
+ self->ntlookups++;
+ length = nt_shortest(self, node);
+ if (length == -3)
+ return NULL;
+ if (length == -2) {
+ raise_revlog_error();
+ return NULL;
+ }
+ return PyInt_FromLong(length);
+}
+
static PyObject *index_m_get(indexObject *self, PyObject *args)
{
Py_ssize_t nodelen;
@@ -1995,6 +2066,8 @@
"insert an index entry"},
{"partialmatch", (PyCFunction)index_partialmatch, METH_VARARGS,
"match a potentially ambiguous node ID"},
+ {"shortest", (PyCFunction)index_shortest, METH_VARARGS,
+ "find length of shortest hex nodeid of a binary ID"},
{"stats", (PyCFunction)index_stats, METH_NOARGS,
"stats for the index"},
{NULL} /* Sentinel */
diff --git a/mercurial/cext/parsers.c b/mercurial/cext/parsers.c
--- a/mercurial/cext/parsers.c
+++ b/mercurial/cext/parsers.c
@@ -713,7 +713,7 @@
void manifest_module_init(PyObject *mod);
void revlog_module_init(PyObject *mod);
-static const int version = 4;
+static const int version = 5;
static void module_init(PyObject *mod)
{
To: martinvonz, indygreg, #hg-reviewers
Cc: yuja, mercurial-devel
More information about the Mercurial-devel
mailing list