( )⚙ D12139 rank: naive rank property computation and retrieval

This is an archive of the discontinued Mercurial Phabricator instance.

Differential D12139

rank: naive rank property computation and retrieval
ClosedPublic

Authored by pacien on Feb 7 2022, 12:25 PM.

Details

Reviewers
Alphare
Group Reviewers
hg-reviewers
Commits
rHG2e949ede7350: rank: naive rank property computation and retrieval
Summary

This stores the rank (size of the ancestor set of a revision, including itself)
in a changelog field and allows this property to be retrieved.

This new property is used as part of stable-range computations, which will be
introduced later on.

The value is computed in a naive way from the definition of the rank. This will
be replaced by a more efficient version subsequently.

Diff Detail

Repository
rHG Mercurial
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

pacien created this revision.Feb 7 2022, 12:25 PM
joerg.sonnenberger added a subscriber: joerg.sonnenberger.Feb 7 2022, 3:01 PM

Why do we want this variant of a rank? E.g. an alternative definition of rank is the length of the longest path to root. That definition is much easier to compute incrementally and just as useful for most algorithmic uses.

marmoute added a subscriber: marmoute.Feb 8 2022, 5:42 AM
In D12139#186190, @joerg.sonnenberger wrote:

Why do we want this variant of a rank? E.g. an alternative definition of rank is the length of the longest path to root. That definition is much easier to compute incrementally and just as useful for most algorithmic uses.

What you describe is what we¹ have been calling depth. It is a useful property too, but not the one that is useful for the various algorithm we have so far.

[1] people doing the research around stable-range stuff

Alphare added a subscriber: Alphare.Feb 8 2022, 8:56 AM

One thing that isn't clear is exactly what the rank is going to be used for (at least its currently foreseeable applications) to people not privy to the details, so probably adding a sentence to the commit message about this might be a good idea.

mercurial/revlog.py
862

Why is this called fast_rank? Are we expecting to have a (possibly slower) def rank somewhere down the line?

866

"the rank og X i sthe size of" => "the rank of X is the size of"

869

s/variant/variants/

Alphare requested changes to this revision.Feb 8 2022, 9:00 AM
This revision now requires changes to proceed.Feb 8 2022, 9:00 AM
marmoute added inline comments.Feb 8 2022, 9:19 AM
mercurial/revlog.py
862

It is a the fast_rank because it a cached value that can be retreived in O(N). Not a computed value that would be expensive to compute. Using the rank when available could help various algorithm (outside of the initial target) for example ancestors checking or discovery. However it is unlikely to be worth computing the rank of the fly for these usecases.

Alphare added inline comments.Feb 8 2022, 10:09 AM
mercurial/revlog.py
862

You mean O(1) right?

marmoute added inline comments.Feb 8 2022, 10:36 AM
mercurial/revlog.py
862

I do.

pacien edited the summary of this revision. (Show Details)Feb 14 2022, 12:06 PM
pacien updated this revision to Diff 32167.
pacien marked 6 inline comments as done.Feb 14 2022, 12:09 PM

Documentation and commit description updated with the required explanations.

Alphare accepted this revision.Feb 15 2022, 7:57 AM
This revision is now accepted and ready to land.Feb 15 2022, 7:57 AM
marmoute added a commit: rHG2e949ede7350: rank: naive rank property computation and retrieval.Feb 15 2022, 9:48 AM
Closed by commit rHG2e949ede7350: rank: naive rank property computation and retrieval (authored by marmoute). · Explain Why
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

PathPackages
Mmercurial/revlog.py (23 lines)

Diff 32200

mercurial/revlog.py

from .i18n import _ from .i18n import _
from .pycompat import getattr from .pycompat import getattr
from .revlogutils.constants import ( from .revlogutils.constants import (
ALL_KINDS, ALL_KINDS,
CHANGELOGV2, CHANGELOGV2,
COMP_MODE_DEFAULT, COMP_MODE_DEFAULT,
COMP_MODE_INLINE, COMP_MODE_INLINE,
COMP_MODE_PLAIN, COMP_MODE_PLAIN,
ENTRY_RANK,
FEATURES_BY_VERSION, FEATURES_BY_VERSION,
FLAG_GENERALDELTA, FLAG_GENERALDELTA,
FLAG_INLINE_DATA, FLAG_INLINE_DATA,
INDEX_HEADER, INDEX_HEADER,
KIND_CHANGELOG, KIND_CHANGELOG,
RANK_UNKNOWN,
REVLOGV0, REVLOGV0,
REVLOGV1, REVLOGV1,
REVLOGV1_FLAGS, REVLOGV1_FLAGS,
REVLOGV2, REVLOGV2,
REVLOGV2_FLAGS, REVLOGV2_FLAGS,
REVLOG_DEFAULT_FLAGS, REVLOG_DEFAULT_FLAGS,
REVLOG_DEFAULT_FORMAT, REVLOG_DEFAULT_FORMAT,
REVLOG_DEFAULT_VERSION, REVLOG_DEFAULT_VERSION,
# fast path: if no "read" flag processor could change the content, # fast path: if no "read" flag processor could change the content,
# size is rawsize. note: ELLIPSIS is known to not change the content. # size is rawsize. note: ELLIPSIS is known to not change the content.
flags = self.flags(rev) flags = self.flags(rev)
if flags & (flagutil.REVIDX_KNOWN_FLAGS ^ REVIDX_ELLIPSIS) == 0: if flags & (flagutil.REVIDX_KNOWN_FLAGS ^ REVIDX_ELLIPSIS) == 0:
return self.rawsize(rev) return self.rawsize(rev)
return len(self.revision(rev)) return len(self.revision(rev))
def fast_rank(self, rev):
AlphareUnsubmitted
Done

Why is this called fast_rank? Are we expecting to have a (possibly slower) def rank somewhere down the line?

Alphare: Why is this called `fast_rank`? Are we expecting to have a (possibly slower) `def rank`…
marmouteUnsubmitted
Done

It is a the fast_rank because it a cached value that can be retreived in O(N). Not a computed value that would be expensive to compute. Using the rank when available could help various algorithm (outside of the initial target) for example ancestors checking or discovery. However it is unlikely to be worth computing the rank of the fly for these usecases.

marmoute: It is a the `fast_rank` because it a cached value that can be retreived in O(N). Not a computed…
AlphareUnsubmitted
Done

You mean O(1) right?

Alphare: You mean `O(1)` right?
marmouteUnsubmitted
Done

I do.

marmoute: I do.
"""Return the rank of a revision if already known, or None otherwise.
The rank of a revision is the size of the sub-graph it defines as a
head. Equivalently, the rank of a revision `r` is the size of the set
AlphareUnsubmitted
Done

"the rank og X i sthe size of" => "the rank of X is the size of"

Alphare: "the rank og X i sthe size of" => "the rank of X is the size of"
`ancestors(r)`, `r` included.
This method returns the rank retrieved from the revlog in constant
AlphareUnsubmitted
Done

s/variant/variants/

Alphare: s/variant/variants/
time. It makes no attempt at computing unknown values for versions of
the revlog which do not persist the rank.
"""
rank = self.index[rev][ENTRY_RANK]
if rank == RANK_UNKNOWN:
return None
return rank
def chainbase(self, rev): def chainbase(self, rev):
base = self._chainbasecache.get(rev) base = self._chainbasecache.get(rev)
if base is not None: if base is not None:
return base return base
index = self.index index = self.index
iterrev = rev iterrev = rev
base = index[iterrev][3] base = index[iterrev][3]
serialized_sidedata = comp_sidedata serialized_sidedata = comp_sidedata
else: else:
serialized_sidedata = b"" serialized_sidedata = b""
# Don't store the offset if the sidedata is empty, that way # Don't store the offset if the sidedata is empty, that way
# we can easily detect empty sidedata and they will be no different # we can easily detect empty sidedata and they will be no different
# than ones we manually add. # than ones we manually add.
sidedata_offset = 0 sidedata_offset = 0
rank = RANK_UNKNOWN
if self._format_version == CHANGELOGV2:
rank = len(list(self.ancestors([p1r, p2r], inclusive=True))) + 1
e = revlogutils.entry( e = revlogutils.entry(
flags=flags, flags=flags,
data_offset=offset, data_offset=offset,
data_compressed_length=deltainfo.deltalen, data_compressed_length=deltainfo.deltalen,
data_uncompressed_length=textlen, data_uncompressed_length=textlen,
data_compression_mode=compression_mode, data_compression_mode=compression_mode,
data_delta_base=deltainfo.base, data_delta_base=deltainfo.base,
link_rev=link, link_rev=link,
parent_rev_1=p1r, parent_rev_1=p1r,
parent_rev_2=p2r, parent_rev_2=p2r,
node_id=node, node_id=node,
sidedata_offset=sidedata_offset, sidedata_offset=sidedata_offset,
sidedata_compressed_length=len(serialized_sidedata), sidedata_compressed_length=len(serialized_sidedata),
sidedata_compression_mode=sidedata_compression_mode, sidedata_compression_mode=sidedata_compression_mode,
rank=rank,
) )
self.index.append(e) self.index.append(e)
entry = self.index.entry_binary(curr) entry = self.index.entry_binary(curr)
if curr == 0 and self._docket is None: if curr == 0 and self._docket is None:
header = self._format_flags | self._format_version header = self._format_flags | self._format_version
header = self.index.pack_header(header) header = self.index.pack_header(header)
entry = header + entry entry = header + entry