This is an archive of the discontinued Mercurial Phabricator instance.

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.

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

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
877	Why is this called `fast_rank`? Are we expecting to have a (possibly slower) `def rank` somewhere down the line?
881	"the rank og X i sthe size of" => "the rank of X is the size of"
884	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
877	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
877	You mean `O(1)` right?

marmoute added inline comments.Feb 8 2022, 10:36 AM

mercurial/revlog.py
877	I do.

pacien edited the summary of this revision. (Show Details)Feb 14 2022, 12:06 PM

pacien updated this revision to Diff 32167.

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

			Path	Packages
M			mercurial/revlog.py (23 lines)

Diff	ID	Description	Created	Lint	Unit
Base		Base
Diff 1	32086		Feb 7 2022, 12:25 PM	★	★
Diff 2	32167		Feb 14 2022, 12:06 PM	★	★
Diff 3	32200	rHG2e949ede7350d0d9ec654d0c709118c979eb5519	Jan 28 2022, 5:33 AM	★	★

Commit	Parents	Author	Summary	Date
f956ac5c9c5a	4afb9627dc77	Pierre-Yves David		Jan 28 2022, 5:33 AM

Status	Author	Revision
Closed	pacien	D12143 rank: compute property incrementally
Closed	pacien	D12142 rank: add test with golden values
Closed	pacien	D12141 rank: add minimal test
Closed	pacien	D12140 rank: add context and template keyword
Closed	pacien	D12139 rank: naive rank property computation and retrieval

Diff 32167

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, raw=False))			return len(self.revision(rev, raw=False))

				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

This is an archive of the discontinued Mercurial Phabricator instance.

rank: naive rank property computation and retrievalClosedPublic

Details

Diff Detail

Event Timeline

Revision ContentsChangeset List

Diff 32167

mercurial/revlog.py

rank: naive rank property computation and retrieval
ClosedPublic

Revision Contents
Changeset List