[RFC] merge - common_ancestor generation

[Robert Collins]

On Mon, 2006-03-06 at 21:15 -0500, Aaron Bentley wrote:


> |  * The descendants graph? I think this is not needed for most callers,
> | but we can have a single utility function to convert a graph that mayu
> | contain ghosts into a descendants graph.
> 
> I want a way to get the descendant graph.  A utility is okay.  It seems
> like it would be more expensive that way, though.

Its a single pass to produce the descendant graph we have for
revision.py's revision_graph, which is the same one produced by the
previous code - node[child][1]

> |  * a list of roots ? [which would be found by scanning for parentless
> | nodes]
> 
> The graph root should always be the NULL_REVISION, except in cases where
> the NULL_REVISION is unreachable due to ghosts, in which case we can fail.

I think we should not fail in that case, rather report all the ghosts as
roots (they are) and let the caller decide what they want to do -
whether to synthesis a common ancestor, or to work off the known graph.



> | I plan to put this on repository because its code varies with the
> | repository format.
> |
> | So, my ideal api is:
> | repository.revision_graph_with_ghosts(['A', 'B'])
> | ->
> |   {'A':['C'],
> |    'B':['D'],
> |    'D':['C'],
> |    },
> |   set(['C'])
> |
> | Meaning: A has parents ['C']
> |          B has parents ['D']
> |          D has parents ['C']
> |          C is a ghost
> |          no revisions are connected to null: directly. [in fact null: is
> | not reachable].
> 
> I would expect to throw in that circumstance.

mmmm, discussing this on IRC with you....

>>> graph = repository.revision_graph_with_ghosts(['A', 'B'])
>>> graph.roots
set([])
>>> graph.ghosts
set(['C'])
>>> graph.get_ancestors()
{'A':['C'],
 'B':['D'],
 'D':['C'],
 }
>>> graph.get_descendants()
{'C':{'D':1, 'A':1},
 'A':{},
 'B':{},
 'D':{'B':1},
 }


when roots are reachable - say for 
{'A':['aroot'],
 'aroot':[],
 }

you get
>>> graph.roots
set(['aroot'])
>>> graph.ghosts
set([])
>>> graph.get_ancestors()
{'A':['aroot']}
>>> graph.get_descendants()
{'aroot':{'A':1}}


we also discussed the ghost unaware api, and making this consistent with
this ghost aware api, so repository.revision_graph(['A', 'B']) using my
first example graph (A,B,D present, C is a ghost and the common root):
>>> graph = repository.revision_graph(['A', 'B'])
>>> graph.roots
set(['A', 'D'])
>>> graph.ghosts
set([])
>>> graph.get_ancestors()
{'A':[],
 'B':['D'],
 'D':[],
 }
>>> graph.get_descendants()
{'A':{},
 'B':{},
 'D':{'B':1},
 }


Both of these graphs are trivially convertable to null: containing
graphs by passing over graph.roots and optionally graph.ghosts.

Can you confirm this matches what we spoke about?

Rob

-- 
GPG key available at: <http://www.robertcollins.net/keys.txt>.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 191 bytes
Desc: This is a digitally signed message part
Url : https://lists.ubuntu.com/archives/bazaar/attachments/20060307/cd301b97/attachment.pgp