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

This is an archive of the discontinued Mercurial Phabricator instance.

rank: naive rank property computation and retrieval
ClosedPublic

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

Details

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

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.

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
This revision was automatically updated to reflect the committed changes.