New public Graph.revision_relation method

John Arbash Meinel john at
Wed Dec 9 18:58:53 GMT 2009

Hash: SHA1

Martin von Gagern wrote:
> John Arbash Meinel wrote:
>> You may also want to look at the KnownGraph code.
> I had encountered KnownGraph before. Originally I had assumed that
> KnownGraph would be a specialization of Graph, so that any wrapper
> method added top Graph would become available to KnownGraph as well.
> It seems I was wrong; KnownGraph inherits directly from object in the
> pure python version, and a basic cdef class in the Pyrex version. So
> while it looks like its heads implementation already does all the
> optimization a proper find_relation would need, I'd either have to copy
> the implementation, come up with some clever inheritance scheme, or
> simply leave find_relation restricted to either graph implementation for
> the time being.
> I guess I'd favor a mltiple inheritance mechanism. Have some
> AbstractGraph to provide common wrapper functions, some RawKnownGraph to
> provide the Pyrex implementation, and then let Graph inherit from
> AbstractGraph and KnownGraph inherit from both RawKnownGraph and
> AbstractGraph. What do you think?
> Martin

The internals are pretty much 100% different. KnownGraph expects to be
passed the full parent_map of ancestry, while Graph expects to be passed
a 'parents_provider' which it can then query for more ancestry.

The internal layout of structures, etc, are also completely different.
So while if you implement your functionality strictly in terms of
'.heads()' then it could use either implementation, but if you implement
something that depends on internal state, then it won't work on the
other implementation.

It comes down to what can you expect to be part of the abstract base /

I'd be a bit cautious about inheriting from an abstract base in the
Pyrex code, (for performance reasons), but it has been done before. the
_annotator_pyx extension inherits from the pure-python version, and just
overrides a couple key functions with pyrex optimized functions.

However, a lot of the specific benefits for KnownGraph come from the
fact that it changes how the parent map is structured internally. (Being
able to walk a pointer to a parent, rather than getting a key and
looking it up in a dict is a significant performance improvement.)

A simpler fashion would be to implement abstract functionality in a
different class, and pass in either a KnownGraph instance or a Graph
instance. Something like:

def find_relation(graph, rev1, rev2):
  heads = graph.heads(rev1, rev2)
  if len(heads) == 2:
    return 'unrelated'
  else: # there can be only 1
    head = iter(heads).next()
    if head == rev1:
      return 'rev2-ancestor'
      return 'rev1-ancestor'



Version: GnuPG v1.4.9 (Cygwin)
Comment: Using GnuPG with Mozilla -


More information about the bazaar mailing list