[RFC] ParentsProvider returning a dictionary instead of a list

John Arbash Meinel john at arbash-meinel.com
Fri Dec 7 22:54:26 GMT 2007


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

At the moment our Graph code expects a parents_provider to return a list, where
each entry matches up with the requested revisions.

However, I'm noticing a pattern that I keep repeating:

for revision_id, parent_ids in izip(revs, get_parents(revs)):

Also, most of the implementations I've come across build up a dictionary and
then iterate over it to return it in the requested order. As a breakdown:

DictParentsProvider:
  already has them in a dict, so just does the iteration, depending on how
  get_parents was defined it could just return it (do we care if there are
  extra nodes?)

StackedParentsProvider:
  Has to build up a dict, because it doesn't know what it can get from what
  provider.

CachingParentsProvider: (new)
  Also needs a dict because some will come from the cache, and others will come
  from the wrapped provider

Repository: (generic impl)
  Iterates up a list, because it uses a get_revision() call for each node. This
  could be made a bit better if we provided a get_present_revisions() call, but
  it doesn't really matter because either is going to be slow.

_KnitParentsProvider:
  Iterates the list using KnitVersionedFile.get_parents_with_ghosts()
  Has a slight inefficiency that it has to catch an exception for any missing
  nodes, but that will generally be rare anyway. (Except for maybe when
  comparing the graph of a large remote versus an old local branch)

PackRepository:
  Builds up a dict because index.iter_entries() can return data in any order.
  (Also now uses CachingParentsProvider on top, so we are building up a dict,
  to linearize it, to build it back into a dict, to linearize it again)

CombinedGraphIndex:
  Builds up a dict because it has to get some keys from each of the graphs.


And to top it off, my new versions of Graph.heads() and _find_border_ancestors
would rather have a dict anyway. (And I would guess those aren't the only place).

I'm willing to call it "get_parent_map()" or some other function for
compatibility. But I thought it would be reasonable to bring it up for discussion.

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

iD8DBQFHWc8hJdeBCYSNAAMRAk83AKDPpEeWimmsDuuenaUzV8lqjW2qOgCgpN7Y
c2z+si0TZXTOP6W2GcHw3hk=
=HkKu
-----END PGP SIGNATURE-----



More information about the bazaar mailing list