[PATCH 2 of 2] revlog: do inclusive descendant testing (API)

Martin von Zweigbergk martinvonz at google.com
Wed Jun 27 13:42:35 EDT 2018


On Mon, Jun 25, 2018 at 9:54 AM Paul Morelle <paul.morelle at octobus.net>
wrote:

> On 21/06/18 18:30, Martin von Zweigbergk wrote:
>
> On Thu, Jun 21, 2018 at 7:24 AM Paul Morelle <paul.morelle at octobus.net>
> wrote:
>
>> # HG changeset patch
>> # User Boris Feld <boris.feld at octobus.net>
>> # Date 1529585081 -3600
>> #      Thu Jun 21 13:44:41 2018 +0100
>> # Node ID 59fea52e54e014722486f7c049e192fa505032d8
>> # Parent  8d20b1b4b6a0297e7f9640d285b15a5d6647369e
>> # EXP-Topic descendant
>> # Available At https://bitbucket.org/octobus/mercurial-devel/
>> #              hg pull https://bitbucket.org/octobus/mercurial-devel/ -r
>> 59fea52e54e0
>> revlog: do inclusive descendant testing (API)
>>
>> In many other places, a revision is considered a descendant of itself.
>> We update the behavior of `revlog.descendant()` to match this.
>>
>> No test breaks, so it seems safe to do so.
>>
>> diff -r 8d20b1b4b6a0 -r 59fea52e54e0 mercurial/revlog.py
>> --- a/mercurial/revlog.py       Thu Jun 21 13:32:07 2018 +0100
>> +++ b/mercurial/revlog.py       Thu Jun 21 13:44:41 2018 +0100
>> @@ -1378,7 +1378,7 @@
>>      def descendant(self, start, end):
>>          if start == nullrev:
>>              return True
>> -        return start in self.ancestors([end])
>> +        return start in self.ancestors([end], inclusive=True)
>>
>
> Is this now equivalent to self.isancestor(start, end)? That method relies
> on commonancestorsheads instead of lazyancestors. What are the performance
> trade-offs? Equivalent both when there are many ancestors and when there
> are many descendants?
>
> Hello Martin,
>
> Interestingly, it turns out that we have the following flock of functions:
>
>    - ancestors: commonancestorsheads(parent_func, *revs)
>       - uses revnum
>       - any number of arguments
>       - written in Python
>    - cext/revlog.c: revlog.index.commonancestorsheads(*revs)
>       - uses revnum
>       - any number of arguments
>       - written in C
>    - revlog: revlog.commonancestorsheads(node-a, node-b)
>       - uses nodes
>       - takes exactly two nodes
>       - Calls either self.index.c…a…heads  or ancestors.c…a…heads
>    - revlog: revlog.isancestor(anc, desc)
>       - uses nodes
>       - calls revlog.commonancestorsheads
>    - revlog: revlog.descendant(rev-a, rev-b)
>       - uses revs
>       - has it own very slow code
>    - revlog: revlog.descendant(rev-a, rev-b)
>       - uses revs
>       - has it own very slow code
>       - non-inclusive
>    - context: context.descendant(other)
>       - uses contexts
>       - calls revlog.descendant
>       - non-inclusive
>
> At the algorithm level, `anc in ancestors(desc)` will be faster when anc
> is not an ancestor of desc (or they are many gca), since it will finish
> sooner. However given `commonancestorheads` benefits from a C
> implementation, it is currently the fastest option.
>
> In short terms, I think the following actions would make sense:
>
>    1. Extract a lower level `revlog._commonancestorheads(*revs)` from
>    `revlog.commonancestorsheads`
>
> What would the new function do? commonancestorsheads is already pretty
short. Do you mean to just make it work on revnums instead of nodeids? Or
do you mean for making it optionally inclusive?

>
>    1. Use it in `revlog.descendant`
>    2. Make `revlog.isancestor` use `revlog.descendant`
>
> Why is that better than making descendant call isancestor?

Does this seems sensible to you?
>
> --
> Paul Morelle
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.mercurial-scm.org/pipermail/mercurial-devel/attachments/20180627/69d87d13/attachment.html>


More information about the Mercurial-devel mailing list