rank: add a "rank" value to the revlog-entry tuple

The rank of a revision is the size of sub-graph it defines as a head. In other
words, the rank of X is the size of `ancestors(X)` (X included).

This is a property that can help various algorithm and we intend to store it in
changelog-v2. We start with adding this new information to the "entry tuple",
with a default value. We will start to compute and persist the rank later.

Differential Revision: https://phab.mercurial-scm.org/D11936

mercurial/cext/revlog.c

@@ -120,9 +120,11 b' static Py_ssize_t inline_scan(indexObjec'
 static int index_find_node(indexObject *self, const char *node);
 
 #if LONG_MAX == 0x7fffffffL
-static const char *const tuple_format = PY23("Kiiiiiis#KiBB", "Kiiiiiiy#KiBB");
+static const char *const tuple_format =
+    PY23("Kiiiiiis#KiBBi", "Kiiiiiiy#KiBBi");
 #else
-static const char *const tuple_format = PY23("kiiiiiis#kiBB", "kiiiiiiy#kiBB");
+static const char *const tuple_format =
+    PY23("kiiiiiis#kiBBi", "kiiiiiiy#kiBBi");
 #endif
 
 /* A RevlogNG v1 index entry is 64 bytes long. */
@@ -135,6 +137,7 b' static const long format_v1 = 1; /* Inte'
 static const long format_v2 = 2; /* Internal only, could be any number */
 
 static const char comp_mode_inline = 2;
+static const char rank_unknown = -1;
 
 static void raise_revlog_error(void)
 {
@@ -352,7 +355,7 b' static PyObject *index_get(indexObject *'
 	return Py_BuildValue(tuple_format, offset_flags, comp_len, uncomp_len,
 	                     base_rev, link_rev, parent_1, parent_2, c_node_id,
 	                     self->nodelen, sidedata_offset, sidedata_comp_len,
-	                     data_comp_mode, sidedata_comp_mode);
+	                     data_comp_mode, sidedata_comp_mode, rank_unknown);
 }
 /*
  * Pack header information in binary
@@ -453,7 +456,7 b' static PyObject *index_append(indexObjec'
 {
 	uint64_t offset_flags, sidedata_offset;
 	int rev, comp_len, uncomp_len, base_rev, link_rev, parent_1, parent_2,
-	    sidedata_comp_len;
+	    sidedata_comp_len, rank;
 	char data_comp_mode, sidedata_comp_mode;
 	Py_ssize_t c_node_id_len;
 	const char *c_node_id;
@@ -464,8 +467,8 b' static PyObject *index_append(indexObjec'
 	                      &uncomp_len, &base_rev, &link_rev, &parent_1,
 	                      &parent_2, &c_node_id, &c_node_id_len,
 	                      &sidedata_offset, &sidedata_comp_len,
-	                      &data_comp_mode, &sidedata_comp_mode)) {
-		PyErr_SetString(PyExc_TypeError, "11-tuple required");
+	                      &data_comp_mode, &sidedata_comp_mode, &rank)) {
+		PyErr_SetString(PyExc_TypeError, "12-tuple required");
 		return NULL;
 	}
 
@@ -2797,9 +2800,10 b' static int index_init(indexObject *self,'
 		self->entry_size = v1_entry_size;
 	}
 
-	self->nullentry = Py_BuildValue(
-	    PY23("iiiiiiis#iiBB", "iiiiiiiy#iiBB"), 0, 0, 0, -1, -1, -1, -1,
-	    nullid, self->nodelen, 0, 0, comp_mode_inline, comp_mode_inline);
+	self->nullentry =
+	    Py_BuildValue(PY23("iiiiiiis#iiBBi", "iiiiiiiy#iiBBi"), 0, 0, 0, -1,
+	                  -1, -1, -1, nullid, self->nodelen, 0, 0,
+	                  comp_mode_inline, comp_mode_inline, rank_unknown);
 
 	if (!self->nullentry)
 		return -1;

mercurial/pure/parsers.py

@@ -584,6 +584,7 b' class BaseIndexObject(object):'
         0,
         revlog_constants.COMP_MODE_INLINE,
         revlog_constants.COMP_MODE_INLINE,
+        revlog_constants.RANK_UNKNOWN,
     )
 
     @util.propertycache
@@ -671,6 +672,7 b' class BaseIndexObject(object):'
             0,
             revlog_constants.COMP_MODE_INLINE,
             revlog_constants.COMP_MODE_INLINE,
+            revlog_constants.RANK_UNKNOWN,
         )
         return r
 
@@ -853,7 +855,7 b' class IndexObject2(IndexObject):'
         entry = data[:10]
         data_comp = data[10] & 3
         sidedata_comp = (data[10] & (3 << 2)) >> 2
-        return entry + (data_comp, sidedata_comp)
+        return entry + (data_comp, sidedata_comp, revlog_constants.RANK_UNKNOWN)
 
     def _pack_entry(self, rev, entry):
         data = entry[:10]
@@ -896,6 +898,7 b' class IndexChangelogV2(IndexObject2):'
             items[revlog_constants.INDEX_ENTRY_V2_IDX_COMPRESSION_MODE] & 3,
             (items[revlog_constants.INDEX_ENTRY_V2_IDX_COMPRESSION_MODE] >> 2)
             & 3,
+            revlog_constants.RANK_UNKNOWN,
         )
 
     def _pack_entry(self, rev, entry):

mercurial/revlogutils/__init__.py

@@ -12,6 +12,7 b' from ..interfaces import repository'
 
 # See mercurial.revlogutils.constants for doc
 COMP_MODE_INLINE = 2
+RANK_UNKNOWN = -1
 
 
 def offset_type(offset, type):
@@ -34,6 +35,7 b' def entry('
     sidedata_offset=0,
     sidedata_compressed_length=0,
     sidedata_compression_mode=COMP_MODE_INLINE,
+    rank=RANK_UNKNOWN,
 ):
     """Build one entry from symbolic name
 
@@ -56,6 +58,7 b' def entry('
         sidedata_compressed_length,
         data_compression_mode,
         sidedata_compression_mode,
+        rank,
     )
 
 

mercurial/revlogutils/constants.py

@@ -103,6 +103,17 b' ENTRY_DATA_COMPRESSION_MODE = 10'
 #            (see "COMP_MODE_*" constants for details)
 ENTRY_SIDEDATA_COMPRESSION_MODE = 11
 
+#    [12] Revision rank:
+#            The number of revision under this one.
+#
+#            Formally this is defined as : rank(X) = len(ancestors(X) + X)
+#
+#            If rank == -1; then we do not have this information available.
+#            Only `null` has a rank of 0.
+ENTRY_RANK = 12
+
+RANK_UNKNOWN = -1
+
 ### main revlog header
 
 # We cannot rely on  Struct.format is inconsistent for python <=3.6 versus above

mercurial/unionrepo.py

@@ -71,6 +71,7 b' class unionrevlog(revlog.revlog):'
                 _sds,
                 _dcm,
                 _sdcm,
+                rank,
             ) = rev
             flags = _start & 0xFFFF
 
@@ -107,6 +108,7 b' class unionrevlog(revlog.revlog):'
                 0,  # sidedata size
                 revlog_constants.COMP_MODE_INLINE,
                 revlog_constants.COMP_MODE_INLINE,
+                rank,
             )
             self.index.append(e)
             self.bundlerevs.add(n)

tests/test-parseindex2.py

@@ -57,6 +57,7 b' def py_parseindex(data, inline):'
                 0,
                 constants.COMP_MODE_INLINE,
                 constants.COMP_MODE_INLINE,
+                constants.RANK_UNKNOWN,
             )
             nodemap[e[7]] = n
             append(e)
@@ -72,6 +73,7 b' def py_parseindex(data, inline):'
                 0,
                 constants.COMP_MODE_INLINE,
                 constants.COMP_MODE_INLINE,
+                constants.RANK_UNKNOWN,
             )
             nodemap[e[7]] = n
             append(e)
@@ -268,6 +270,7 b' class parseindex2tests(unittest.TestCase'
             0,
             constants.COMP_MODE_INLINE,
             constants.COMP_MODE_INLINE,
+            constants.RANK_UNKNOWN,
         )
         index, junk = parsers.parse_index2(data_inlined, True)
         got = index[-1]
@@ -303,6 +306,7 b' class parseindex2tests(unittest.TestCase'
                 0,
                 constants.COMP_MODE_INLINE,
                 constants.COMP_MODE_INLINE,
+                constants.RANK_UNKNOWN,
             )
             index.append(e)