This is an archive of the discontinued Mercurial Phabricator instance.

Differential D5443

ancestor: uniformity of calling lazyancestors classes
AbandonedPublic

Authored by gracinet on Dec 15 2018, 6:42 AM.

Download Raw Diff

Details

Reviewers

indygreg

Group Reviewers

hg-reviewers

Summary

Up to now, the pure Python lazyancestors had been taking the parents
function in its constructor, whereas Rust-backed variants would have needed
a revlog index.

With this change, instantiation of all lazyancestors work uniformely with
an index. This requires only minor wrapping in test-ancestor.py.

It could be argued that this introduces a new duplication, and that
therefore, parentsfunc(index) should be provided in some utility module and
used both from revlog and ancestor modules.

Diff Detail

Repository

rHG Mercurial

Lint

Lint Skipped

Unit

Unit Tests Skipped

Event Timeline

gracinet created this revision.Dec 15 2018, 6:42 AM

Herald added a reviewer: indygreg. · View Herald TranscriptDec 15 2018, 6:42 AM

Herald added a reviewer: hg-reviewers. · View Herald Transcript

Herald added a subscriber: mercurial-devel. · View Herald Transcript

obviously, this one could be adapted for application before the rust-cpython bindings, and extended for the incrementalmissingancestors as well

+def parentsfunc(index):
+ def parentrevs(rev):
+ try:
+ entry = index[rev]
+ except IndexError:
+ if rev == wdirrev:
+ raise error.WdirUnsupported
+ raise
+
+ return entry[5], entry[6]
+ return parentrevs

It doesn't seem correct that the ancestor module handles the revlog's
internals. Instead, can't we add a factory function which takes both
index and pfunc?

@yuja I'm not sure by what you consider exactly to be internals here. If that's the [5] and [6], maybe a parents(revision)` method on the index would be better ? The obvious drawback would be to write more C code.

Given that my ultimate goal here is to delegate the whole ancestors module to policy.importmod, where would we have the factory function you're thinking of ? In some sense, that's the role revlog.py fulfills isn't it ? Maybe all access to ancestors logic should keep on going through it ?

@yuja I'm not sure by what you consider exactly to be internals here. If that's the `[5]` and [6]`, maybe a `parents(revision)` method on the index would be better ? The obvious drawback would be to write more C code.
Given that my ultimate goal here is to delegate the whole `ancestors` module to `policy.importmod`, where would we have the factory function you're thinking of ?

ancestor.lazyrevlogancestors(index, pfunc, revs, ...) -> lazyancestors

It allows us to select the implementation by the policy importer without
exposing the revlog internals too much. It doesn't look pretty, but IMHO
is less bad than moving revlog.parents() out of the revlog class.

In some sense, that's the role revlog.py fulfills isn't it ? Maybe all access to ancestors logic should keep on going through it ?

Strictly speaking, yes, it's the role of revlog.py. The pure ancestor.py
is agnostic on the graph implementation, whereas the Rust one isn't. So
I think we'll need some glue code for the time being.

Given this conversation, and its outcome as materialised with latest versions of D5441 and D5442, we can now simply abandon this one.

Revision Contents
Changeset List

			Path	Packages
M			mercurial/ancestor.py (23 lines)
M			mercurial/revlog.py (9 lines)
M			tests/test-ancestor.py (18 lines)

Commit	Parents	Author	Summary	Date
		Georges Racinet		Dec 14 2018, 7:16 AM

Status	Author	Revision
Abandoned	gracinet	D5443 ancestor: uniformity of calling lazyancestors classes
Closed	gracinet	D5442 rust-cpython: using the new bindings from Python
Closed	gracinet	D5441 rust-cpython: binding for LazyAncestors
Closed	gracinet	D5440 rust: core implementation for lazyancestors
Closed	gracinet	D5439 rust-cpython: binding for AncestorsIterator
Closed	gracinet	D5438 rust-cpython: implementing Graph using C parents function
Closed	gracinet	D5437 rust-cpython: testing the bindings from Python
Closed	gracinet	D5436 rust-cpython: build via HGWITHRUSTEXT=cpython
Closed	gracinet	D5435 rust: better treatment of cargo/rustc errors
Closed	gracinet	D5434 rust-cpython: started cpython crate bindings
Closed	gracinet	D5433 rust-cpython: excluded hgcli from workspace

Diff 12880

mercurial/ancestor.py

	# ancestor.py - generic DAG ancestor algorithm for mercurial			# ancestor.py - generic DAG ancestor algorithm for mercurial
	#			#
	# Copyright 2006 Matt Mackall <mpm@selenic.com>			# Copyright 2006 Matt Mackall <mpm@selenic.com>
	#			#
	# 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

	import heapq			import heapq

	from .node import nullrev			from .node import (
				nullrev,
				wdirrev,
				)
	from . import (			from . import (
				error,
	policy,			policy,
	pycompat,			pycompat,
	)			)

	parsers = policy.importmod(r'parsers')			parsers = policy.importmod(r'parsers')

	def commonancestorsheads(pfunc, *nodes):			def commonancestorsheads(pfunc, *nodes):
	"""Returns a set with the heads of all common ancestors of all nodes,			"""Returns a set with the heads of all common ancestors of all nodes,
	heapreplace(visit, -p1)			heapreplace(visit, -p1)
	see(p1)			see(p1)
	else:			else:
	heappop(visit)			heappop(visit)
	if p2 not in seen:			if p2 not in seen:
	heappush(visit, -p2)			heappush(visit, -p2)
	see(p2)			see(p2)

				def parentsfunc(index):
				def parentrevs(rev):
				try:
				entry = index[rev]
				except IndexError:
				if rev == wdirrev:
				raise error.WdirUnsupported
				raise

				return entry[5], entry[6]
				return parentrevs

	class lazyancestors(object):			class lazyancestors(object):
	def __init__(self, pfunc, revs, stoprev=0, inclusive=False):			def __init__(self, index, revs, stoprev=0, inclusive=False):
	"""Create a new object generating ancestors for the given revs. Does			"""Create a new object generating ancestors for the given revs. Does
	not generate revs lower than stoprev.			not generate revs lower than stoprev.

	This is computed lazily starting from revs. The object supports			This is computed lazily starting from revs. The object supports
	iteration and membership.			iteration and membership.

	cl should be a changelog and revs should be an iterable. inclusive is			cl should be a changelog and revs should be an iterable. inclusive is
	a boolean that indicates whether revs should be included. Revs lower			a boolean that indicates whether revs should be included. Revs lower
	than stoprev will not be generated.			than stoprev will not be generated.

	Result does not include the null revision."""			Result does not include the null revision."""
	self._parentrevs = pfunc			self._parentrevs = parentsfunc(index)
	self._initrevs = revs = [r for r in revs if r >= stoprev]			self._initrevs = revs = [r for r in revs if r >= stoprev]
	self._stoprev = stoprev			self._stoprev = stoprev
	self._inclusive = inclusive			self._inclusive = inclusive

	self._containsseen = set()			self._containsseen = set()
	self._containsiter = _lazyancestorsiter(self._parentrevs,			self._containsiter = _lazyancestorsiter(self._parentrevs,
	self._initrevs,			self._initrevs,
	self._stoprev,			self._stoprev,
	self._inclusive)			self._inclusive)


	def __nonzero__(self):			def __nonzero__(self):
	"""False if the set is empty, True otherwise."""			"""False if the set is empty, True otherwise."""
	try:			try:
	next(iter(self))			next(iter(self))
	return True			return True
	except StopIteration:			except StopIteration:
	return False			return False

mercurial/revlog.py

	entry = self.index[rev]			entry = self.index[rev]
	except IndexError:			except IndexError:
	if rev == wdirrev:			if rev == wdirrev:
	raise error.WdirUnsupported			raise error.WdirUnsupported
	raise			raise

	return entry[5], entry[6]			return entry[5], entry[6]

	# fast parentrevs(rev) where rev isn't filtered
	_uncheckedparentrevs = parentrevs

	def node(self, rev):			def node(self, rev):
	try:			try:
	return self.index[rev][7]			return self.index[rev][7]
	except IndexError:			except IndexError:
	if rev == wdirrev:			if rev == wdirrev:
	raise error.WdirUnsupported			raise error.WdirUnsupported
	raise			raise

	global rustext			global rustext
	if rustext is not None:			if rustext is not None:
	try:			try:
	rustext.__name__			rustext.__name__
	except ImportError:			except ImportError:
	rustext = None			rustext = None
	if rustext is not None:			if rustext is not None:
	lazyancestors = rustext.ancestor.lazyancestors			lazyancestors = rustext.ancestor.lazyancestors
	arg = self.index
	elif util.safehasattr(parsers, 'rustlazyancestors'):			elif util.safehasattr(parsers, 'rustlazyancestors'):
	lazyancestors = ancestor.rustlazyancestors			lazyancestors = ancestor.rustlazyancestors
	arg = self.index
	else:			else:
	lazyancestors = ancestor.lazyancestors			lazyancestors = ancestor.lazyancestors
	arg = self._uncheckedparentrevs			return lazyancestors(self.index, revs,
	return lazyancestors(arg, revs, stoprev=stoprev, inclusive=inclusive)			stoprev=stoprev, inclusive=inclusive)

	def descendants(self, revs):			def descendants(self, revs):
	return dagop.descendantrevs(revs, self.revs, self.parentrevs)			return dagop.descendantrevs(revs, self.revs, self.parentrevs)

	def findcommonmissing(self, common=None, heads=None):			def findcommonmissing(self, common=None, heads=None):
	"""Return a tuple of the ancestors of common and the ancestors of heads			"""Return a tuple of the ancestors of common and the ancestors of heads
	that are not ancestors of common. In revset terminology, we return the			that are not ancestors of common. In revset terminology, we return the
	tuple:			tuple:

tests/test-ancestor.py

	missanc = ancestor.incrementalmissingancestors(vecgraph.__getitem__, bases)			missanc = ancestor.incrementalmissingancestors(vecgraph.__getitem__, bases)
	revs = {4, 12, 41, 28, 68, 38, 1, 30, 56, 44}			revs = {4, 12, 41, 28, 68, 38, 1, 30, 56, 44}
	missanc.removeancestorsfrom(revs)			missanc.removeancestorsfrom(revs)
	if 28 in revs:			if 28 in revs:
	print("Failed!")			print("Failed!")
	else:			else:
	print("Ok")			print("Ok")

				class fakeindex(object):
				'''A pseudo index backed by a dict or list graph

				It's only meant for parents lookup, and
				all that matters is that self.graph[rev] is the pair of rev's parents.
				'''
				def __init__(self, graph):
				self.graph = graph
				def __getitem__(self, rev):
				res = [None] * 5
				try:
				res.extend(self.graph[rev])
				except KeyError:
				raise IndexError(rev)
				return res

	def genlazyancestors(revs, stoprev=0, inclusive=False):			def genlazyancestors(revs, stoprev=0, inclusive=False):
	print(("%% lazy ancestor set for %s, stoprev = %s, inclusive = %s" %			print(("%% lazy ancestor set for %s, stoprev = %s, inclusive = %s" %
	(revs, stoprev, inclusive)))			(revs, stoprev, inclusive)))
	return ancestor.lazyancestors(graph.get, revs, stoprev=stoprev,			return ancestor.lazyancestors(fakeindex(graph), revs, stoprev=stoprev,
	inclusive=inclusive)			inclusive=inclusive)

	def printlazyancestors(s, l):			def printlazyancestors(s, l):
	print('membership: %r' % [n for n in l if n in s])			print('membership: %r' % [n for n in l if n in s])
	print('iteration: %r' % list(s))			print('iteration: %r' % list(s))

	def test_lazyancestors():			def test_lazyancestors():
	# Empty revs			# Empty revs

Diff	ID	Base	Description	Created	Lint	Unit
Base			Base
Diff 1	12880			Dec 15 2018, 6:42 AM	★	★