[MERGE] introduce is_ancestor, avoid using get_ancestry

[John Arbash Meinel]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Aaron Bentley wrote:
> John Arbash Meinel wrote:
>> Anyway, it would be nice to have a tiny bit of benchmarking on this.
> 
> Why do you want that?  This isn't about making anything faster, it's
> about avoiding an API that's necessarily slow.
> 
>> I would
>> also argue that we might consider deprecating get_ancestry.
> 
> I would love to, but it has other users that we need to correct first.
> 
>> The only valid user
>> I know of is "bzr ancestry", which could potentially do it in a different way.
> 
> Yes.  It seems reasonable to support Graph.iter_ancestors, so when
> that's implemented, we could do:
> 
> graph.iter_topo(graph.iter_ancestors(revision))
> 
>> I'm trying to understand your 'is_ancestor' code. At a minimum, it needs a
>> docstring. And certainly it could use a bit of commenting to help understand
>> what you are trying to do.
> 
>> Some questions:
> 
>> 1) How does the overall search work?
> 
> So there are two possible outcomes: True and False, but there are three
> possible relationships:
> 
> a) candidate_ancestor is an ancestor of candidate_descendant
> b) candidate_ancestor is an descendant of candidate_descendant
> c) candidate_ancestor is an sibling of candidate_descendant
> 
> To check for a, we walk from candidate_descendant, looking for
> candidate_ancestor.
> 
> To check for b, we walk from candidate_ancestor, looking for
> candidate_descendant.
> 
> To make a and b more efficient, we can stop any searches that hit common
> ancestors.
> 
> If we exhaust our searches, but neither a or b is true, then c is true.
> 
> In order to find c efficiently, we must avoid searching from
> candidate_descendant or candidate_ancestor into common ancestors.  But
> if we don't search common ancestors at all, we won't know if we hit
> common ancestors.  So we have a walker for common ancestors.  Note that
> its searches are not required to terminate in order to determine c to be
> true.


^- This seems like a great bit of text to put in a python comment right before
the actual code.

Otherwise +1.

John
=:->
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.7 (Darwin)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFGqh7cJdeBCYSNAAMRAp8wAJ4vIdwcB+neLBNdCUxJ9mXmu9yzEQCgxan/
Z43KXwRFxrvl+5OnxHwCUrY=
=HHik
-----END PGP SIGNATURE-----