( )⚙ D11936 rank: add a "rank" value to the revlog-entry tuple

This is an archive of the discontinued Mercurial Phabricator instance.

Differential D11936

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

Authored by marmoute on Dec 16 2021, 12:43 PM.

Details

Reviewers
Alphare
Group Reviewers
hg-reviewers
Commits
rHG52034c42c09d: rank: add a "rank" value to the revlog-entry tuple
Summary

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.

Diff Detail

Repository
rHG Mercurial
Branch
default
Lint
No Linters Available
Unit
No Unit Test Coverage

Event Timeline

marmoute created this revision.Dec 16 2021, 12:43 PM
Alphare accepted this revision.Dec 17 2021, 8:35 AM
This revision is now accepted and ready to land.Dec 17 2021, 8:35 AM
Alphare requested changes to this revision.Dec 17 2021, 8:45 AM

Writing it down so I can amend it later

mercurial/revlogutils/constants.py
112

s/fof/of

This revision now requires changes to proceed.Dec 17 2021, 8:45 AM
Alphare accepted this revision.Dec 17 2021, 8:45 AM
This revision is now accepted and ready to land.Dec 17 2021, 8:45 AM
marmoute added a commit: rHG52034c42c09d: rank: add a "rank" value to the revlog-entry tuple.Dec 17 2021, 9:00 AM
Closed by commit rHG52034c42c09d: rank: add a "rank" value to the revlog-entry tuple (authored by marmoute). · Explain Why
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

Diff 31502

mercurial/cext/revlog.c

static const char nullid[32] = {0}; static const char nullid[32] = {0};
static const Py_ssize_t nullrev = -1; static const Py_ssize_t nullrev = -1;
static Py_ssize_t inline_scan(indexObject *self, const char **offsets); static Py_ssize_t inline_scan(indexObject *self, const char **offsets);
static int index_find_node(indexObject *self, const char *node); static int index_find_node(indexObject *self, const char *node);
#if LONG_MAX == 0x7fffffffL #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 #else
static const char *const tuple_format = PY23("kiiiiiis#kiBB", "kiiiiiiy#kiBB"); static const char *const tuple_format =
PY23("kiiiiiis#kiBBi", "kiiiiiiy#kiBBi");
#endif #endif
/* A RevlogNG v1 index entry is 64 bytes long. */ /* A RevlogNG v1 index entry is 64 bytes long. */
static const long v1_entry_size = 64; static const long v1_entry_size = 64;
/* A Revlogv2 index entry is 96 bytes long. */ /* A Revlogv2 index entry is 96 bytes long. */
static const long v2_entry_size = 96; static const long v2_entry_size = 96;
static const long format_v1 = 1; /* Internal only, could be any number */ static const long format_v1 = 1; /* Internal only, could be any number */
static const long format_v2 = 2; /* Internal only, could be any number */ static const long format_v2 = 2; /* Internal only, could be any number */
static const char comp_mode_inline = 2; static const char comp_mode_inline = 2;
static const char rank_unknown = -1;
static void raise_revlog_error(void) static void raise_revlog_error(void)
{ {
PyObject *mod = NULL, *dict = NULL, *errclass = NULL; PyObject *mod = NULL, *dict = NULL, *errclass = NULL;
mod = PyImport_ImportModule("mercurial.error"); mod = PyImport_ImportModule("mercurial.error");
if (mod == NULL) { if (mod == NULL) {
goto cleanup; goto cleanup;
sidedata_comp_len = getbe32(data + 72); sidedata_comp_len = getbe32(data + 72);
data_comp_mode = data[76] & 3; data_comp_mode = data[76] & 3;
sidedata_comp_mode = ((data[76] >> 2) & 3); sidedata_comp_mode = ((data[76] >> 2) & 3);
} }
return Py_BuildValue(tuple_format, offset_flags, comp_len, uncomp_len, return Py_BuildValue(tuple_format, offset_flags, comp_len, uncomp_len,
base_rev, link_rev, parent_1, parent_2, c_node_id, base_rev, link_rev, parent_1, parent_2, c_node_id,
self->nodelen, sidedata_offset, sidedata_comp_len, 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 * Pack header information in binary
*/ */
static PyObject *index_pack_header(indexObject *self, PyObject *args) static PyObject *index_pack_header(indexObject *self, PyObject *args)
{ {
int header; int header;
char out[4]; char out[4];
thisnodelen, nodelen); thisnodelen, nodelen);
return -1; return -1;
} }
static PyObject *index_append(indexObject *self, PyObject *obj) static PyObject *index_append(indexObject *self, PyObject *obj)
{ {
uint64_t offset_flags, sidedata_offset; uint64_t offset_flags, sidedata_offset;
int rev, comp_len, uncomp_len, base_rev, link_rev, parent_1, parent_2, 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; char data_comp_mode, sidedata_comp_mode;
Py_ssize_t c_node_id_len; Py_ssize_t c_node_id_len;
const char *c_node_id; const char *c_node_id;
char comp_field; char comp_field;
char *data; char *data;
if (!PyArg_ParseTuple(obj, tuple_format, &offset_flags, &comp_len, if (!PyArg_ParseTuple(obj, tuple_format, &offset_flags, &comp_len,
&uncomp_len, &base_rev, &link_rev, &parent_1, &uncomp_len, &base_rev, &link_rev, &parent_1,
&parent_2, &c_node_id, &c_node_id_len, &parent_2, &c_node_id, &c_node_id_len,
&sidedata_offset, &sidedata_comp_len, &sidedata_offset, &sidedata_comp_len,
&data_comp_mode, &sidedata_comp_mode)) { &data_comp_mode, &sidedata_comp_mode, &rank)) {
PyErr_SetString(PyExc_TypeError, "11-tuple required"); PyErr_SetString(PyExc_TypeError, "12-tuple required");
return NULL; return NULL;
} }
if (c_node_id_len != self->nodelen) { if (c_node_id_len != self->nodelen) {
PyErr_SetString(PyExc_TypeError, "invalid node"); PyErr_SetString(PyExc_TypeError, "invalid node");
return NULL; return NULL;
} }
if (self->format_version == format_v1) { if (self->format_version == format_v1) {
if (revlogv2 && PyObject_IsTrue(revlogv2)) { if (revlogv2 && PyObject_IsTrue(revlogv2)) {
self->format_version = format_v2; self->format_version = format_v2;
self->entry_size = v2_entry_size; self->entry_size = v2_entry_size;
} else { } else {
self->format_version = format_v1; self->format_version = format_v1;
self->entry_size = v1_entry_size; self->entry_size = v1_entry_size;
} }
self->nullentry = Py_BuildValue( self->nullentry =
PY23("iiiiiiis#iiBB", "iiiiiiiy#iiBB"), 0, 0, 0, -1, -1, -1, -1, Py_BuildValue(PY23("iiiiiiis#iiBBi", "iiiiiiiy#iiBBi"), 0, 0, 0, -1,
nullid, self->nodelen, 0, 0, comp_mode_inline, comp_mode_inline); -1, -1, -1, nullid, self->nodelen, 0, 0,
comp_mode_inline, comp_mode_inline, rank_unknown);
if (!self->nullentry) if (!self->nullentry)
return -1; return -1;
PyObject_GC_UnTrack(self->nullentry); PyObject_GC_UnTrack(self->nullentry);
if (PyObject_GetBuffer(data_obj, &self->buf, PyBUF_SIMPLE) == -1) if (PyObject_GetBuffer(data_obj, &self->buf, PyBUF_SIMPLE) == -1)
return -1; return -1;
size = self->buf.len; size = self->buf.len;

mercurial/pure/parsers.py

-1, -1,
-1, -1,
-1, -1,
sha1nodeconstants.nullid, sha1nodeconstants.nullid,
0, 0,
0, 0,
revlog_constants.COMP_MODE_INLINE, revlog_constants.COMP_MODE_INLINE,
revlog_constants.COMP_MODE_INLINE, revlog_constants.COMP_MODE_INLINE,
revlog_constants.RANK_UNKNOWN,
) )
@util.propertycache @util.propertycache
def entry_size(self): def entry_size(self):
return self.index_format.size return self.index_format.size
@property @property
def nodemap(self): def nodemap(self):
def _unpack_entry(self, rev, data): def _unpack_entry(self, rev, data):
r = self.index_format.unpack(data) r = self.index_format.unpack(data)
r = r + ( r = r + (
0, 0,
0, 0,
revlog_constants.COMP_MODE_INLINE, revlog_constants.COMP_MODE_INLINE,
revlog_constants.COMP_MODE_INLINE, revlog_constants.COMP_MODE_INLINE,
revlog_constants.RANK_UNKNOWN,
) )
return r return r
def pack_header(self, header): def pack_header(self, header):
"""pack header information as binary""" """pack header information as binary"""
v_fmt = revlog_constants.INDEX_HEADER v_fmt = revlog_constants.INDEX_HEADER
return v_fmt.pack(header) return v_fmt.pack(header)
new = self._pack_entry(rev, entry) new = self._pack_entry(rev, entry)
self._extra[rev - self._lgt] = new self._extra[rev - self._lgt] = new
def _unpack_entry(self, rev, data): def _unpack_entry(self, rev, data):
data = self.index_format.unpack(data) data = self.index_format.unpack(data)
entry = data[:10] entry = data[:10]
data_comp = data[10] & 3 data_comp = data[10] & 3
sidedata_comp = (data[10] & (3 << 2)) >> 2 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): def _pack_entry(self, rev, entry):
data = entry[:10] data = entry[:10]
data_comp = entry[10] & 3 data_comp = entry[10] & 3
sidedata_comp = (entry[11] & 3) << 2 sidedata_comp = (entry[11] & 3) << 2
data += (data_comp | sidedata_comp,) data += (data_comp | sidedata_comp,)
return self.index_format.pack(*data) return self.index_format.pack(*data)
items[revlog_constants.INDEX_ENTRY_V2_IDX_NODEID], items[revlog_constants.INDEX_ENTRY_V2_IDX_NODEID],
items[revlog_constants.INDEX_ENTRY_V2_IDX_SIDEDATA_OFFSET], items[revlog_constants.INDEX_ENTRY_V2_IDX_SIDEDATA_OFFSET],
items[ items[
revlog_constants.INDEX_ENTRY_V2_IDX_SIDEDATA_COMPRESSED_LENGTH revlog_constants.INDEX_ENTRY_V2_IDX_SIDEDATA_COMPRESSED_LENGTH
], ],
items[revlog_constants.INDEX_ENTRY_V2_IDX_COMPRESSION_MODE] & 3, items[revlog_constants.INDEX_ENTRY_V2_IDX_COMPRESSION_MODE] & 3,
(items[revlog_constants.INDEX_ENTRY_V2_IDX_COMPRESSION_MODE] >> 2) (items[revlog_constants.INDEX_ENTRY_V2_IDX_COMPRESSION_MODE] >> 2)
& 3, & 3,
revlog_constants.RANK_UNKNOWN,
) )
def _pack_entry(self, rev, entry): def _pack_entry(self, rev, entry):
base = entry[revlog_constants.ENTRY_DELTA_BASE] base = entry[revlog_constants.ENTRY_DELTA_BASE]
link_rev = entry[revlog_constants.ENTRY_LINK_REV] link_rev = entry[revlog_constants.ENTRY_LINK_REV]
assert base == rev, (base, rev) assert base == rev, (base, rev)
assert link_rev == rev, (link_rev, rev) assert link_rev == rev, (link_rev, rev)

mercurial/revlogutils/__init__.py

# mercurial.revlogutils -- basic utilities for revlog # mercurial.revlogutils -- basic utilities for revlog
# #
# Copyright 2019 Pierre-Yves David <pierre-yves.david@octobus.net> # Copyright 2019 Pierre-Yves David <pierre-yves.david@octobus.net>
# #
# This software may be used and distributed according to the terms of the # This software may be used and distributed according to the terms of the
# GNU General Public License version 2 or any later version. # GNU General Public License version 2 or any later version.
from __future__ import absolute_import from __future__ import absolute_import
from ..thirdparty import attr from ..thirdparty import attr
from ..interfaces import repository from ..interfaces import repository
# See mercurial.revlogutils.constants for doc # See mercurial.revlogutils.constants for doc
COMP_MODE_INLINE = 2 COMP_MODE_INLINE = 2
RANK_UNKNOWN = -1
def offset_type(offset, type): def offset_type(offset, type):
if (type & ~repository.REVISION_FLAGS_KNOWN) != 0: if (type & ~repository.REVISION_FLAGS_KNOWN) != 0:
raise ValueError(b'unknown revlog index flags: %d' % type) raise ValueError(b'unknown revlog index flags: %d' % type)
return int(int(offset) << 16 | type) return int(int(offset) << 16 | type)
def entry( def entry(
data_offset, data_offset,
data_compressed_length, data_compressed_length,
data_delta_base, data_delta_base,
link_rev, link_rev,
parent_rev_1, parent_rev_1,
parent_rev_2, parent_rev_2,
node_id, node_id,
flags=0, flags=0,
data_uncompressed_length=-1, data_uncompressed_length=-1,
data_compression_mode=COMP_MODE_INLINE, data_compression_mode=COMP_MODE_INLINE,
sidedata_offset=0, sidedata_offset=0,
sidedata_compressed_length=0, sidedata_compressed_length=0,
sidedata_compression_mode=COMP_MODE_INLINE, sidedata_compression_mode=COMP_MODE_INLINE,
rank=RANK_UNKNOWN,
): ):
"""Build one entry from symbolic name """Build one entry from symbolic name
This is useful to abstract the actual detail of how we build the entry This is useful to abstract the actual detail of how we build the entry
tuple for caller who don't care about it. tuple for caller who don't care about it.
This should always be called using keyword arguments. Some arguments have This should always be called using keyword arguments. Some arguments have
default value, this match the value used by index version that does not store such data. default value, this match the value used by index version that does not store such data.
""" """
return ( return (
offset_type(data_offset, flags), offset_type(data_offset, flags),
data_compressed_length, data_compressed_length,
data_uncompressed_length, data_uncompressed_length,
data_delta_base, data_delta_base,
link_rev, link_rev,
parent_rev_1, parent_rev_1,
parent_rev_2, parent_rev_2,
node_id, node_id,
sidedata_offset, sidedata_offset,
sidedata_compressed_length, sidedata_compressed_length,
data_compression_mode, data_compression_mode,
sidedata_compression_mode, sidedata_compression_mode,
rank,
) )
@attr.s(slots=True, frozen=True) @attr.s(slots=True, frozen=True)
class revisioninfo(object): class revisioninfo(object):
"""Information about a revision that allows building its fulltext """Information about a revision that allows building its fulltext
node: expected hash of the revision node: expected hash of the revision
p1, p2: parent revs of the revision p1, p2: parent revs of the revision

mercurial/revlogutils/constants.py

# 1 this will always be COMP_MODE_INLINE. # 1 this will always be COMP_MODE_INLINE.
ENTRY_DATA_COMPRESSION_MODE = 10 ENTRY_DATA_COMPRESSION_MODE = 10
# [11] side-data compression mode: # [11] side-data compression mode:
# two bits that detail the way the sidedata chunk is compressed on disk. # two bits that detail the way the sidedata chunk is compressed on disk.
# (see "COMP_MODE_*" constants for details) # (see "COMP_MODE_*" constants for details)
ENTRY_SIDEDATA_COMPRESSION_MODE = 11 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 fof 0.
AlphareUnsubmitted
Not Done

s/fof/of

Alphare: s/fof/of
ENTRY_RANK = 12
RANK_UNKNOWN = -1
### main revlog header ### main revlog header
# We cannot rely on Struct.format is inconsistent for python <=3.6 versus above # We cannot rely on Struct.format is inconsistent for python <=3.6 versus above
INDEX_HEADER_FMT = b">I" INDEX_HEADER_FMT = b">I"
INDEX_HEADER = struct.Struct(INDEX_HEADER_FMT) INDEX_HEADER = struct.Struct(INDEX_HEADER_FMT)
## revlog version ## revlog version
REVLOGV0 = 0 REVLOGV0 = 0

mercurial/unionrepo.py

linkrev, linkrev,
p1rev, p1rev,
p2rev, p2rev,
node, node,
_sdo, _sdo,
_sds, _sds,
_dcm, _dcm,
_sdcm, _sdcm,
rank,
) = rev ) = rev
flags = _start & 0xFFFF flags = _start & 0xFFFF
if linkmapper is None: # link is to same revlog if linkmapper is None: # link is to same revlog
assert linkrev == rev2 # we never link back assert linkrev == rev2 # we never link back
link = n link = n
else: # rev must be mapped from repo2 cl to unified cl by linkmapper else: # rev must be mapped from repo2 cl to unified cl by linkmapper
link = linkmapper(linkrev) link = linkmapper(linkrev)
link, link,
self.rev(p1node), self.rev(p1node),
self.rev(p2node), self.rev(p2node),
node, node,
0, # sidedata offset 0, # sidedata offset
0, # sidedata size 0, # sidedata size
revlog_constants.COMP_MODE_INLINE, revlog_constants.COMP_MODE_INLINE,
revlog_constants.COMP_MODE_INLINE, revlog_constants.COMP_MODE_INLINE,
rank,
) )
self.index.append(e) self.index.append(e)
self.bundlerevs.add(n) self.bundlerevs.add(n)
n += 1 n += 1
def _chunk(self, rev): def _chunk(self, rev):
if rev <= self.repotiprev: if rev <= self.repotiprev:
return revlog.revlog._chunk(self, rev) return revlog.revlog._chunk(self, rev)

tests/test-parseindex2.py

cache = (0, data) cache = (0, data)
while off <= l: while off <= l:
e = struct.unpack(indexformatng, data[off : off + s]) e = struct.unpack(indexformatng, data[off : off + s])
e = e + ( e = e + (
0, 0,
0, 0,
constants.COMP_MODE_INLINE, constants.COMP_MODE_INLINE,
constants.COMP_MODE_INLINE, constants.COMP_MODE_INLINE,
constants.RANK_UNKNOWN,
) )
nodemap[e[7]] = n nodemap[e[7]] = n
append(e) append(e)
n += 1 n += 1
if e[1] < 0: if e[1] < 0:
break break
off += e[1] + s off += e[1] + s
else: else:
while off <= l: while off <= l:
e = struct.unpack(indexformatng, data[off : off + s]) e = struct.unpack(indexformatng, data[off : off + s])
e = e + ( e = e + (
0, 0,
0, 0,
constants.COMP_MODE_INLINE, constants.COMP_MODE_INLINE,
constants.COMP_MODE_INLINE, constants.COMP_MODE_INLINE,
constants.RANK_UNKNOWN,
) )
nodemap[e[7]] = n nodemap[e[7]] = n
append(e) append(e)
n += 1 n += 1
off += s off += s
e = list(index[0]) e = list(index[0])
type = gettype(e[0]) type = gettype(e[0])
-1, -1,
-1, -1,
-1, -1,
sha1nodeconstants.nullid, sha1nodeconstants.nullid,
0, 0,
0, 0,
constants.COMP_MODE_INLINE, constants.COMP_MODE_INLINE,
constants.COMP_MODE_INLINE, constants.COMP_MODE_INLINE,
constants.RANK_UNKNOWN,
) )
index, junk = parsers.parse_index2(data_inlined, True) index, junk = parsers.parse_index2(data_inlined, True)
got = index[-1] got = index[-1]
self.assertEqual(want, got) # inline data self.assertEqual(want, got) # inline data
index, junk = parsers.parse_index2(data_non_inlined, False) index, junk = parsers.parse_index2(data_non_inlined, False)
got = index[-1] got = index[-1]
self.assertEqual(want, got) # no inline data self.assertEqual(want, got) # no inline data
34, 34,
p1, p1,
p2, p2,
node, node,
0, 0,
0, 0,
constants.COMP_MODE_INLINE, constants.COMP_MODE_INLINE,
constants.COMP_MODE_INLINE, constants.COMP_MODE_INLINE,
constants.RANK_UNKNOWN,
) )
index.append(e) index.append(e)
appendrev(4) appendrev(4)
appendrev(5) appendrev(5)
appendrev(6) appendrev(6)
self.assertEqual(len(index), 7) self.assertEqual(len(index), 7)