Rev 3126: (jam) Implement ParentProviders.get_parent_map() and deprecate in file:///home/pqm/archives/thelove/bzr/%2Btrunk/
Canonical.com Patch Queue Manager
pqm at pqm.ubuntu.com
Tue Dec 18 23:41:40 GMT 2007
At file:///home/pqm/archives/thelove/bzr/%2Btrunk/
------------------------------------------------------------
revno: 3126
revision-id:pqm at pqm.ubuntu.com-20071218234130-061grgxsaf1g7bao
parent: pqm at pqm.ubuntu.com-20071218201613-83d41agovrry31lv
parent: john at arbash-meinel.com-20071218224058-fsihu8vgtmksb7vp
committer: Canonical.com Patch Queue Manager <pqm at pqm.ubuntu.com>
branch nick: +trunk
timestamp: Tue 2007-12-18 23:41:30 +0000
message:
(jam) Implement ParentProviders.get_parent_map() and deprecate
get_parents()
modified:
NEWS NEWS-20050323055033-4e00b5db738777ff
bzrlib/bundle/serializer/v4.py v10.py-20070611062757-5ggj7k18s9dej0fr-1
bzrlib/bzrdir.py bzrdir.py-20060131065624-156dfea39c4387cb
bzrlib/graph.py graph_walker.py-20070525030359-y852guab65d4wtn0-1
bzrlib/index.py index.py-20070712131115-lolkarso50vjr64s-1
bzrlib/repofmt/knitrepo.py knitrepo.py-20070206081537-pyy4a00xdas0j4pf-1
bzrlib/repofmt/pack_repo.py pack_repo.py-20070813041115-gjv5ma7ktfqwsjgn-1
bzrlib/repository.py rev_storage.py-20051111201905-119e9401e46257e3
bzrlib/tests/repository_implementations/test_repository.py test_repository.py-20060131092128-ad07f494f5c9d26c
bzrlib/tests/test_graph.py test_graph_walker.py-20070525030405-enq4r60hhi9xrujc-1
------------------------------------------------------------
revno: 3099.3.7
revision-id:john at arbash-meinel.com-20071218224058-fsihu8vgtmksb7vp
parent: john at arbash-meinel.com-20071218222126-323kuf097yi63ick
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: graph_optimization
timestamp: Tue 2007-12-18 16:40:58 -0600
message:
Another parent provider I didn't realize existed.
modified:
bzrlib/bzrdir.py bzrdir.py-20060131065624-156dfea39c4387cb
------------------------------------------------------------
revno: 3099.3.6
revision-id:john at arbash-meinel.com-20071218222126-323kuf097yi63ick
parent: john at arbash-meinel.com-20071218205734-khopeuh6xh1gcqbk
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: graph_optimization
timestamp: Tue 2007-12-18 16:21:26 -0600
message:
fix simple typo
modified:
bzrlib/repository.py rev_storage.py-20051111201905-119e9401e46257e3
------------------------------------------------------------
revno: 3099.3.5
revision-id:john at arbash-meinel.com-20071218205734-khopeuh6xh1gcqbk
parent: john at arbash-meinel.com-20071218194430-h9mlqul4vtacs9bf
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: graph_optimization
timestamp: Tue 2007-12-18 14:57:34 -0600
message:
Update the last couple of places that referred to Provider.get_parents() directly.
modified:
bzrlib/bundle/serializer/v4.py v10.py-20070611062757-5ggj7k18s9dej0fr-1
bzrlib/tests/repository_implementations/test_repository.py test_repository.py-20060131092128-ad07f494f5c9d26c
------------------------------------------------------------
revno: 3099.3.4
revision-id:john at arbash-meinel.com-20071218194430-h9mlqul4vtacs9bf
parent: john at arbash-meinel.com-20071218194210-hrciq0bscpg2ge3p
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: graph_optimization
timestamp: Tue 2007-12-18 13:44:30 -0600
message:
NEWS about the deprecation.
modified:
NEWS NEWS-20050323055033-4e00b5db738777ff
------------------------------------------------------------
revno: 3099.3.3
revision-id:john at arbash-meinel.com-20071218194210-hrciq0bscpg2ge3p
parent: john at arbash-meinel.com-20071218190438-sq0itdz00lu5cm5h
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: graph_optimization
timestamp: Tue 2007-12-18 13:42:10 -0600
message:
Deprecate get_parents() in favor of get_parent_map()
modified:
bzrlib/graph.py graph_walker.py-20070525030359-y852guab65d4wtn0-1
bzrlib/index.py index.py-20070712131115-lolkarso50vjr64s-1
bzrlib/repofmt/knitrepo.py knitrepo.py-20070206081537-pyy4a00xdas0j4pf-1
bzrlib/repofmt/pack_repo.py pack_repo.py-20070813041115-gjv5ma7ktfqwsjgn-1
bzrlib/repository.py rev_storage.py-20051111201905-119e9401e46257e3
bzrlib/tests/test_graph.py test_graph_walker.py-20070525030405-enq4r60hhi9xrujc-1
------------------------------------------------------------
revno: 3099.3.2
revision-id:john at arbash-meinel.com-20071218190438-sq0itdz00lu5cm5h
parent: john at arbash-meinel.com-20071218170642-nls9ory76cmh4r6y
parent: john at arbash-meinel.com-20071218182512-147g8dhwfd3gv7dh
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: graph_optimization
timestamp: Tue 2007-12-18 13:04:38 -0600
message:
Merge in bzr.dev and the one_one deprecation string.
added:
bzrlib/help_topics/ help_topics-20071211013603-qz0sojhgxhiujm6a-1
bzrlib/help_topics/en/ bzrlibhelp-20071209214431-xzg3moksichjwyts-1
bzrlib/version_info_formats/format_custom.py format_custom.py-20071029100350-ajovqhbpb5khf6gu-1
doc/en/user-guide/adv_merging.txt adv_merging.txt-20071213070245-d7u7150lb2hhnvby-1
doc/en/user-reference/readme.txt readme.txt-20071211133352-guencaey6fpesv4j-1
index.txt index.txt-20071121073725-0corxykv5irjal00-1
renamed:
bzrlib/help_topics.py => bzrlib/help_topics/__init__.py help_topics.py-20060920210027-rnim90q9e0bwxvy4-1
doc/en/user-guide/authentication_conf.txt => bzrlib/help_topics/en/authentication.txt authentication_conf.-20071104135035-glfv0ri355tyg1nf-1
doc/en/user-guide/configuration.txt => bzrlib/help_topics/en/configuration.txt configuration.txt-20060314161707-868350809502af01
doc/en/user-guide/conflicts.txt => bzrlib/help_topics/en/conflicts.txt conflicts.txt-20070723221841-ns3jvwxdb4okn6fk-1
doc/en/user-reference/hooks.txt => bzrlib/help_topics/en/hooks.txt hooks.txt-20070830033044-xxu2rced13f72dka-1
modified:
.bzrignore bzrignore-20050311232317-81f7b71efa2db11a
Makefile Makefile-20050805140406-d96e3498bb61c5bb
NEWS NEWS-20050323055033-4e00b5db738777ff
bzr bzr.py-20050313053754-5485f144c7006fa6
bzrlib/__init__.py __init__.py-20050309040759-33e65acf91bbcd5d
bzrlib/branch.py branch.py-20050309040759-e4baf4e0d046576e
bzrlib/bugtracker.py bugtracker.py-20070410073305-vu1vu1qosjurg8kb-1
bzrlib/builtins.py builtins.py-20050830033751-fc01482b9ca23183
bzrlib/cmd_version_info.py __init__.py-20051228204928-697d01fdca29c99b
bzrlib/diff.py diff.py-20050309040759-26944fbbf2ebbf36
bzrlib/errors.py errors.py-20050309040759-20512168c4e14fbd
bzrlib/inventory.py inventory.py-20050309040759-6648b84ca2005b37
bzrlib/lockable_files.py control_files.py-20051111201905-bb88546e799d669f
bzrlib/merge_directive.py merge_directive.py-20070228184838-ja62280spt1g7f4x-1
bzrlib/osutils.py osutils.py-20050309040759-eeaff12fbf77ac86
bzrlib/reconfigure.py reconfigure.py-20070908040425-6ykgo7escxhyrg9p-1
bzrlib/repofmt/pack_repo.py pack_repo.py-20070813041115-gjv5ma7ktfqwsjgn-1
bzrlib/revision.py revision.py-20050309040759-e77802c08f3999d5
bzrlib/symbol_versioning.py symbol_versioning.py-20060105104851-9ecf8af605d15a80
bzrlib/tests/__init__.py selftest.py-20050531073622-8d0e3c8845c97a64
bzrlib/tests/blackbox/test_bound_branches.py test_bound_branches.py-20051109215527-2373188ad566c205
bzrlib/tests/blackbox/test_commit.py test_commit.py-20060212094538-ae88fc861d969db0
bzrlib/tests/blackbox/test_diff.py test_diff.py-20060110203741-aa99ac93e633d971
bzrlib/tests/blackbox/test_info.py test_info.py-20060215045507-bbdd2d34efab9e0a
bzrlib/tests/blackbox/test_log.py test_log.py-20060112090212-78f6ea560c868e24
bzrlib/tests/blackbox/test_outside_wt.py test_outside_wt.py-20060116200058-98edd33e7db8bdde
bzrlib/tests/blackbox/test_send.py test_bundle.py-20060616222707-c21c8b7ea5ef57b1
bzrlib/tests/blackbox/test_uncommit.py test_uncommit.py-20051027212835-84944b63adae51be
bzrlib/tests/branch_implementations/test_branch.py testbranch.py-20050711070244-121d632bc37d7253
bzrlib/tests/test_ancestry.py test_ancestry.py-20050913023709-69768e94848312c6
bzrlib/tests/test_help.py test_help.py-20070419045354-6q6rq15j9e2n5fna-1
bzrlib/tests/test_http_response.py test_http_response.py-20060628233143-950b2a482a32505d
bzrlib/tests/test_lockable_files.py test_lockable_files.py-20051225183927-365c7fd99591caf1
bzrlib/tests/test_merge_directive.py test_merge_directive-20070228184838-ja62280spt1g7f4x-2
bzrlib/tests/test_osutils.py test_osutils.py-20051201224856-e48ee24c12182989
bzrlib/tests/test_reconfigure.py test_reconfigure.py-20070908040425-6ykgo7escxhyrg9p-2
bzrlib/tests/test_repository.py test_repository.py-20060131075918-65c555b881612f4d
bzrlib/tests/test_revision.py testrevision.py-20050804210559-46f5e1eb67b01289
bzrlib/tests/test_transform.py test_transaction.py-20060105172520-b3ffb3946550e6c4
bzrlib/tests/test_version_info.py test_version_info.py-20051228204928-2c364e30b702b41b
bzrlib/tests/tree_implementations/test_inv.py test_inv.py-20070312023226-0cdvk5uwhutis9vg-1
bzrlib/transform.py transform.py-20060105172343-dd99e54394d91687
bzrlib/transport/http/__init__.py http_transport.py-20050711212304-506c5fd1059ace96
bzrlib/transport/http/_urllib2_wrappers.py _urllib2_wrappers.py-20060913231729-ha9ugi48ktx481ao-1
bzrlib/version_info_formats/__init__.py generate_version_info.py-20051228204928-8358edabcddcd97e
doc/en/mini-tutorial/index.txt index.txt-20070813141352-2u64ooqzo0or4hss-2
doc/en/user-guide/browsing_history.txt browsing_history.txt-20071121073725-0corxykv5irjal00-2
doc/en/user-guide/bug_trackers.txt bug_trackers.txt-20070713223459-khxdlcudraii95uv-1
doc/en/user-guide/configuring_bazaar.txt configuring_bazaar.t-20071128000722-ncxiua259xwbdbg7-1
doc/en/user-guide/core_concepts.txt core_concepts.txt-20071114035000-q36a9h57ps06uvnl-2
doc/en/user-guide/hooks.txt hooks.txt-20070829200551-7nr6e5a1io6x78uf-1
doc/en/user-guide/http_smart_server.txt fastcgi.txt-20061005091552-rz8pva0olkxv0sd8-3
doc/en/user-guide/index.txt index.txt-20060622101119-tgwtdci8z769bjb9-2
doc/en/user-guide/installing_bazaar.txt installing_bazaar.tx-20071114035000-q36a9h57ps06uvnl-4
doc/en/user-guide/introducing_bazaar.txt introducing_bazaar.t-20071114035000-q36a9h57ps06uvnl-5
doc/en/user-guide/plugins.txt plugins.txt-20060314145616-525099a747f3ffdd
doc/en/user-guide/publishing_a_branch.txt publishing_a_branch.-20071123055134-k5x4ekduci2lbn36-2
doc/en/user-guide/reusing_a_checkout.txt reusing_a_checkout.t-20071123055134-k5x4ekduci2lbn36-3
doc/en/user-guide/sending_changes.txt sending_changes.txt-20071123154453-dk2mjhrg1vpjm5w2-4
doc/en/user-guide/server.txt server.txt-20060913044801-h939fvbwzz39gf7g-1
doc/en/user-guide/setting_up_email.txt setting_up_email.txt-20060314161707-fd242c8944346173
doc/en/user-guide/specifying_revisions.txt specifying_revisions.txt-20060314161707-19deb139101bea33
doc/en/user-guide/version_info.txt version_info.txt-20060921215543-gju6o5xdic8w25np-1
setup.py setup.py-20050314065409-02f8a0a6e3f9bc70
tools/doc_generate/autodoc_rstx.py autodoc_rstx.py-20060420024836-3e0d4a526452193c
tools/rst2html.py rst2html.py-20060817120932-gn177u8v0008txhu-1
bzrlib/help_topics/__init__.py help_topics.py-20060920210027-rnim90q9e0bwxvy4-1
bzrlib/help_topics/en/authentication.txt authentication_conf.-20071104135035-glfv0ri355tyg1nf-1
bzrlib/help_topics/en/configuration.txt configuration.txt-20060314161707-868350809502af01
bzrlib/help_topics/en/conflicts.txt conflicts.txt-20070723221841-ns3jvwxdb4okn6fk-1
bzrlib/help_topics/en/hooks.txt hooks.txt-20070830033044-xxu2rced13f72dka-1
------------------------------------------------------------
revno: 3099.3.1
revision-id:john at arbash-meinel.com-20071218170642-nls9ory76cmh4r6y
parent: pqm at pqm.ubuntu.com-20071210120611-a3j02d26cbzvlyju
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: graph_optimization
timestamp: Tue 2007-12-18 11:06:42 -0600
message:
Implement get_parent_map for ParentProviders
Add a CachingParentProvider for PackRepository to use.
Add some XFAIL tests for the find_difference algorithm.
modified:
bzrlib/graph.py graph_walker.py-20070525030359-y852guab65d4wtn0-1
bzrlib/index.py index.py-20070712131115-lolkarso50vjr64s-1
bzrlib/repofmt/knitrepo.py knitrepo.py-20070206081537-pyy4a00xdas0j4pf-1
bzrlib/repofmt/pack_repo.py pack_repo.py-20070813041115-gjv5ma7ktfqwsjgn-1
bzrlib/repository.py rev_storage.py-20051111201905-119e9401e46257e3
bzrlib/tests/test_graph.py test_graph_walker.py-20070525030405-enq4r60hhi9xrujc-1
=== modified file 'NEWS'
--- a/NEWS 2007-12-18 15:23:12 +0000
+++ b/NEWS 2007-12-18 23:41:30 +0000
@@ -71,6 +71,10 @@
* Help topics can now be loaded from files.
(Ian Clatworthy, Alexander Belchenko)
+ * Parent Providers should now implement ``get_parent_map`` returning a
+ dictionary instead of ``get_parents`` returning a list.
+ ``get_parents`` is now considered deprecated. (John Arbash Meinel)
+
API BREAKS:
TESTING:
=== modified file 'bzrlib/bundle/serializer/v4.py'
--- a/bzrlib/bundle/serializer/v4.py 2007-11-10 15:11:08 +0000
+++ b/bzrlib/bundle/serializer/v4.py 2007-12-18 20:57:34 +0000
@@ -343,8 +343,9 @@
revision_order.remove(self.target)
revision_order.append(self.target)
self.add_mp_records('inventory', None, inv_vf, revision_order)
- parents_list = self.repository.get_parents(revision_order)
- for parents, revision_id in zip(parents_list, revision_order):
+ parent_map = self.repository.get_parent_map(revision_order)
+ for revision_id in revision_order:
+ parents = parent_map.get(revision_id, None)
revision_text = self.repository.get_revision_xml(revision_id)
self.bundle.add_fulltext_record(revision_text, parents,
'revision', revision_id)
=== modified file 'bzrlib/bzrdir.py'
--- a/bzrlib/bzrdir.py 2007-11-30 01:26:17 +0000
+++ b/bzrlib/bzrdir.py 2007-12-18 22:40:58 +0000
@@ -1999,10 +1999,17 @@
del ie.text_id
assert getattr(ie, 'revision', None) is not None
+ @symbol_versioning.deprecated_method(symbol_versioning.one_one)
def get_parents(self, revision_ids):
for revision_id in revision_ids:
yield self.revisions[revision_id].parent_ids
+ def get_parent_map(self, revision_ids):
+ """See graph._StackedParentsProvider.get_parent_map"""
+ return dict((revision_id, self.revisions[revision_id])
+ for revision_id in revision_ids
+ if revision_id in self.revisions)
+
def snapshot_ie(self, previous_revisions, ie, w, rev_id):
# TODO: convert this logic, which is ~= snapshot to
# a call to:. This needs the path figured out. rather than a work_tree
=== modified file 'bzrlib/graph.py'
--- a/bzrlib/graph.py 2007-12-07 05:31:54 +0000
+++ b/bzrlib/graph.py 2007-12-18 19:42:10 +0000
@@ -17,6 +17,7 @@
from bzrlib import (
errors,
revision,
+ symbol_versioning,
tsort,
)
from bzrlib.deprecated_graph import (node_distances, select_farthest)
@@ -52,9 +53,15 @@
def __repr__(self):
return 'DictParentsProvider(%r)' % self.ancestry
+ @symbol_versioning.deprecated_method(symbol_versioning.one_one)
def get_parents(self, revisions):
return [self.ancestry.get(r, None) for r in revisions]
+ def get_parent_map(self, keys):
+ """See _StackedParentsProvider.get_parent_map"""
+ ancestry = self.ancestry
+ return dict((k, ancestry[k]) for k in keys if k in ancestry)
+
class _StackedParentsProvider(object):
@@ -64,6 +71,7 @@
def __repr__(self):
return "_StackedParentsProvider(%r)" % self._parent_providers
+ @symbol_versioning.deprecated_method(symbol_versioning.one_one)
def get_parents(self, revision_ids):
"""Find revision ids of the parents of a list of revisions
@@ -76,17 +84,77 @@
If the revision is not present (i.e. a ghost), None is used in place
of the list of parents.
"""
+ found = self.get_parent_map(revision_ids)
+ return [found.get(r, None) for r in revision_ids]
+
+ def get_parent_map(self, keys):
+ """Get a mapping of keys => parents
+
+ A dictionary is returned with an entry for each key present in this
+ source. If this source doesn't have information about a key, it should
+ not include an entry.
+
+ [NULL_REVISION] is used as the parent of the first user-committed
+ revision. Its parent list is empty.
+
+ :param keys: An iterable returning keys to check (eg revision_ids)
+ :return: A dictionary mapping each key to its parents
+ """
found = {}
+ remaining = set(keys)
for parents_provider in self._parent_providers:
- pending_revisions = [r for r in revision_ids if r not in found]
- parent_list = parents_provider.get_parents(pending_revisions)
- new_found = dict((k, v) for k, v in zip(pending_revisions,
- parent_list) if v is not None)
+ new_found = parents_provider.get_parent_map(remaining)
found.update(new_found)
- if len(found) == len(revision_ids):
+ remaining.difference_update(new_found)
+ if not remaining:
break
+ return found
+
+
+class CachingParentsProvider(object):
+ """A parents provider which will cache the revision => parents in a dict.
+
+ This is useful for providers that have an expensive lookup.
+ """
+
+ def __init__(self, parent_provider):
+ self._real_provider = parent_provider
+ # Theoretically we could use an LRUCache here
+ self._cache = {}
+
+ def __repr__(self):
+ return "%s(%r)" % (self.__class__.__name__, self._real_provider)
+
+ @symbol_versioning.deprecated_method(symbol_versioning.one_one)
+ def get_parents(self, revision_ids):
+ """See _StackedParentsProvider.get_parents"""
+ found = self.get_parent_map(revision_ids)
return [found.get(r, None) for r in revision_ids]
+ def get_parent_map(self, keys):
+ """See _StackedParentsProvider.get_parent_map"""
+ needed = set()
+ # If the _real_provider doesn't have a key, we cache a value of None,
+ # which we then later use to realize we cannot provide a value for that
+ # key.
+ parent_map = {}
+ cache = self._cache
+ for key in keys:
+ if key in cache:
+ value = cache[key]
+ if value is not None:
+ parent_map[key] = value
+ else:
+ needed.add(key)
+
+ if needed:
+ new_parents = self._real_provider.get_parent_map(needed)
+ cache.update(new_parents)
+ parent_map.update(new_parents)
+ needed.difference_update(new_parents)
+ cache.update(dict.fromkeys(needed, None))
+ return parent_map
+
class Graph(object):
"""Provide incremental access to revision graphs.
@@ -106,6 +174,7 @@
conforming to the behavior of StackedParentsProvider.get_parents
"""
self.get_parents = parents_provider.get_parents
+ self.get_parent_map = parents_provider.get_parent_map
self._parents_provider = parents_provider
def __repr__(self):
@@ -354,7 +423,7 @@
An ancestor may sort after a descendant if the relationship is not
visible in the supplied list of revisions.
"""
- sorter = tsort.TopoSorter(zip(revisions, self.get_parents(revisions)))
+ sorter = tsort.TopoSorter(self.get_parent_map(revisions))
return sorter.iter_topo_order()
def is_ancestor(self, candidate_ancestor, candidate_descendant):
@@ -432,11 +501,15 @@
self._start = set(revisions)
self._search_revisions = None
self.seen = set(revisions)
- self._parents_provider = parents_provider
+ self._parents_provider = parents_provider
def __repr__(self):
- return ('_BreadthFirstSearcher(self._search_revisions=%r,'
- ' self.seen=%r)' % (self._search_revisions, self.seen))
+ if self._search_revisions is not None:
+ search = 'searching=%r' % (list(self._search_revisions),)
+ else:
+ search = 'starting=%r' % (list(self._start),)
+ return ('_BreadthFirstSearcher(%s,'
+ ' seen=%r)' % (search, list(self.seen)))
def next(self):
"""Return the next ancestors of this revision.
@@ -448,10 +521,9 @@
self._search_revisions = self._start
else:
new_search_revisions = set()
- for parents in self._parents_provider.get_parents(
- self._search_revisions):
- if parents is None:
- continue
+ parent_map = self._parents_provider.get_parent_map(
+ self._search_revisions)
+ for parents in parent_map.itervalues():
new_search_revisions.update(p for p in parents if
p not in self.seen)
self._search_revisions = new_search_revisions
=== modified file 'bzrlib/index.py'
--- a/bzrlib/index.py 2007-11-28 00:59:30 +0000
+++ b/bzrlib/index.py 2007-12-18 19:42:10 +0000
@@ -35,7 +35,11 @@
from bzrlib.revision import NULL_REVISION
from bzrlib.trace import mutter
""")
-from bzrlib import debug, errors
+from bzrlib import (
+ debug,
+ errors,
+ symbol_versioning,
+ )
_HEADER_READV = (0, 200)
_OPTION_KEY_ELEMENTS = "key_elements="
@@ -995,8 +999,9 @@
self.__class__.__name__,
', '.join(map(repr, self._indices)))
+ @symbol_versioning.deprecated_method(symbol_versioning.one_one)
def get_parents(self, revision_ids):
- """See StackedParentsProvider.get_parents.
+ """See graph._StackedParentsProvider.get_parents.
This implementation thunks the graph.Graph.get_parents api across to
GraphIndex.
@@ -1008,21 +1013,23 @@
* (NULL_REVISION,) when the key has no parents.
* (parent_key, parent_key...) otherwise.
"""
- search_keys = set(revision_ids)
- search_keys.discard(NULL_REVISION)
- found_parents = {NULL_REVISION:[]}
+ parent_map = self.get_parent_map(revision_ids)
+ return [parent_map.get(r, None) for r in revision_ids]
+
+ def get_parent_map(self, keys):
+ """See graph._StackedParentsProvider.get_parent_map"""
+ search_keys = set(keys)
+ if NULL_REVISION in search_keys:
+ search_keys.discard(NULL_REVISION)
+ found_parents = {NULL_REVISION:[]}
+ else:
+ found_parents = {}
for index, key, value, refs in self.iter_entries(search_keys):
parents = refs[0]
if not parents:
parents = (NULL_REVISION,)
found_parents[key] = parents
- result = []
- for key in revision_ids:
- try:
- result.append(found_parents[key])
- except KeyError:
- result.append(None)
- return result
+ return found_parents
def insert_index(self, pos, index):
"""Insert a new index in the list of indices to query.
=== modified file 'bzrlib/repofmt/knitrepo.py'
--- a/bzrlib/repofmt/knitrepo.py 2007-11-18 18:42:17 +0000
+++ b/bzrlib/repofmt/knitrepo.py 2007-12-18 19:42:10 +0000
@@ -30,6 +30,7 @@
lockable_files,
lockdir,
osutils,
+ symbol_versioning,
transactions,
xml5,
xml6,
@@ -58,21 +59,28 @@
def __repr__(self):
return 'KnitParentsProvider(%r)' % self._knit
+ @symbol_versioning.deprecated_method(symbol_versioning.one_one)
def get_parents(self, revision_ids):
- parents_list = []
- for revision_id in revision_ids:
+ """See graph._StackedParentsProvider.get_parents"""
+ parent_map = self.get_parent_map(revision_ids)
+ return [parent_map.get(r, None) for r in revision_ids]
+
+ def get_parent_map(self, keys):
+ """See graph._StackedParentsProvider.get_parent_map"""
+ parent_map = {}
+ for revision_id in keys:
if revision_id == _mod_revision.NULL_REVISION:
- parents = []
+ parent_map[revision_id] = []
else:
try:
parents = self._knit.get_parents_with_ghosts(revision_id)
except errors.RevisionNotPresent:
- parents = None
+ pass
else:
if len(parents) == 0:
parents = [_mod_revision.NULL_REVISION]
- parents_list.append(parents)
- return parents_list
+ parent_map[revision_id] = parents
+ return parent_map
class KnitRepository(MetaDirRepository):
=== modified file 'bzrlib/repofmt/pack_repo.py'
--- a/bzrlib/repofmt/pack_repo.py 2007-12-14 07:35:49 +0000
+++ b/bzrlib/repofmt/pack_repo.py 2007-12-18 19:42:10 +0000
@@ -23,10 +23,10 @@
from bzrlib import (
debug,
+ graph,
pack,
ui,
)
-from bzrlib.graph import Graph
from bzrlib.index import (
GraphIndex,
GraphIndexBuilder,
@@ -48,6 +48,7 @@
lockable_files,
lockdir,
osutils,
+ symbol_versioning,
transactions,
xml5,
xml6,
@@ -81,7 +82,7 @@
CommitBuilder.__init__(self, repository, parents, config,
timestamp=timestamp, timezone=timezone, committer=committer,
revprops=revprops, revision_id=revision_id)
- self._file_graph = Graph(
+ self._file_graph = graph.Graph(
repository._pack_collection.text_index.combined_index)
def _add_text_to_weave(self, file_id, new_lines, parents, nostore_sha):
@@ -107,7 +108,7 @@
CommitBuilder.__init__(self, repository, parents, config,
timestamp=timestamp, timezone=timezone, committer=committer,
revprops=revprops, revision_id=revision_id)
- self._file_graph = Graph(
+ self._file_graph = graph.Graph(
repository._pack_collection.text_index.combined_index)
def _add_text_to_weave(self, file_id, new_lines, parents, nostore_sha):
@@ -1894,19 +1895,27 @@
pb.finished()
return result
+ @symbol_versioning.deprecated_method(symbol_versioning.one_one)
def get_parents(self, revision_ids):
- """See StackedParentsProvider.get_parents.
-
+ """See graph._StackedParentsProvider.get_parents."""
+ parent_map = self.get_parent_map(revision_ids)
+ return [parent_map.get(r, None) for r in revision_ids]
+
+ def get_parent_map(self, keys):
+ """See graph._StackedParentsProvider.get_parent_map
+
This implementation accesses the combined revision index to provide
answers.
"""
self._pack_collection.ensure_loaded()
index = self._pack_collection.revision_index.combined_index
- search_keys = set()
- for revision_id in revision_ids:
- if revision_id != _mod_revision.NULL_REVISION:
- search_keys.add((revision_id,))
- found_parents = {_mod_revision.NULL_REVISION:[]}
+ keys = set(keys)
+ if _mod_revision.NULL_REVISION in keys:
+ keys.discard(_mod_revision.NULL_REVISION)
+ found_parents = {_mod_revision.NULL_REVISION:[]}
+ else:
+ found_parents = {}
+ search_keys = set((revision_id,) for revision_id in keys)
for index, key, value, refs in index.iter_entries(search_keys):
parents = refs[0]
if not parents:
@@ -1914,16 +1923,10 @@
else:
parents = tuple(parent[0] for parent in parents)
found_parents[key[0]] = parents
- result = []
- for revision_id in revision_ids:
- try:
- result.append(found_parents[revision_id])
- except KeyError:
- result.append(None)
- return result
+ return found_parents
def _make_parents_provider(self):
- return self
+ return graph.CachingParentsProvider(self)
def _refresh_data(self):
if self._write_lock_count == 1 or (
=== modified file 'bzrlib/repository.py'
--- a/bzrlib/repository.py 2007-12-03 06:16:05 +0000
+++ b/bzrlib/repository.py 2007-12-18 22:21:26 +0000
@@ -1643,22 +1643,28 @@
def revision_parents(self, revision_id):
return self.get_inventory_weave().parent_names(revision_id)
+ @deprecated_method(symbol_versioning.one_one)
def get_parents(self, revision_ids):
"""See StackedParentsProvider.get_parents"""
- parents_list = []
- for revision_id in revision_ids:
+ parent_map = self.get_parent_map(revision_ids)
+ return [parent_map.get(r, None) for r in revision_ids]
+
+ def get_parent_map(self, keys):
+ """See graph._StackedParentsProvider.get_parent_map"""
+ parent_map = {}
+ for revision_id in keys:
if revision_id == _mod_revision.NULL_REVISION:
- parents = []
+ parent_map[revision_id] = []
else:
try:
- parents = self.get_revision(revision_id).parent_ids
+ parent_ids = self.get_revision(revision_id).parent_ids
except errors.NoSuchRevision:
- parents = None
+ pass
else:
- if len(parents) == 0:
- parents = [_mod_revision.NULL_REVISION]
- parents_list.append(parents)
- return parents_list
+ if len(parent_ids) == 0:
+ parent_ids = [_mod_revision.NULL_REVISION]
+ parent_map[revision_id] = parent_ids
+ return parent_map
def _make_parents_provider(self):
return self
=== modified file 'bzrlib/tests/repository_implementations/test_repository.py'
--- a/bzrlib/tests/repository_implementations/test_repository.py 2007-12-07 06:36:56 +0000
+++ b/bzrlib/tests/repository_implementations/test_repository.py 2007-12-18 20:57:34 +0000
@@ -631,10 +631,10 @@
def test__make_parents_provider(self):
"""Repositories must have a _make_parents_provider method that returns
- an object with a get_parents method.
+ an object with a get_parent_map method.
"""
repo = self.make_repository('repo')
- repo._make_parents_provider().get_parents
+ repo._make_parents_provider().get_parent_map
class TestRepositoryLocking(TestCaseWithRepository):
=== modified file 'bzrlib/tests/test_graph.py'
--- a/bzrlib/tests/test_graph.py 2007-12-04 00:34:34 +0000
+++ b/bzrlib/tests/test_graph.py 2007-12-18 19:42:10 +0000
@@ -17,6 +17,8 @@
from bzrlib import (
errors,
graph as _mod_graph,
+ symbol_versioning,
+ tests,
)
from bzrlib.revision import NULL_REVISION
from bzrlib.tests import TestCaseWithMemoryTransport
@@ -115,11 +117,113 @@
# / \ \
# rev2a rev2b rev2c
# | / \ /
-# rev3a reveb
+# rev3a rev3b
history_shortcut = {'rev1': [NULL_REVISION], 'rev2a': ['rev1'],
'rev2b': ['rev1'], 'rev2c': ['rev1'],
'rev3a': ['rev2a', 'rev2b'], 'rev3b': ['rev2b', 'rev2c']}
+# Extended history shortcut
+# NULL_REVISION
+# |
+# a
+# |\
+# b |
+# | |
+# c |
+# | |
+# d |
+# |\|
+# e f
+extended_history_shortcut = {'a': [NULL_REVISION],
+ 'b': ['a'],
+ 'c': ['b'],
+ 'd': ['c'],
+ 'e': ['d'],
+ 'f': ['a', 'd'],
+ }
+
+# Double shortcut
+# Both sides will see 'A' first, even though it is actually a decendent of a
+# different common revision.
+#
+# NULL_REVISION
+# |
+# a
+# /|\
+# / b \
+# / | \
+# | c |
+# | / \ |
+# | d e |
+# |/ \|
+# f g
+
+double_shortcut = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'],
+ 'd':['c'], 'e':['c'], 'f':['a', 'd'],
+ 'g':['a', 'e']}
+
+# Complex shortcut
+# This has a failure mode in that a shortcut will find some nodes in common,
+# but the common searcher won't have time to find that one branch is actually
+# in common. The extra nodes at the top are because we want to avoid
+# walking off the graph. Specifically, node G should be considered common, but
+# is likely to be seen by M long before the common searcher finds it.
+#
+# NULL_REVISION
+# |
+# a
+# |
+# b
+# |
+# c
+# |
+# d
+# |\
+# e f
+# | |\
+# i | h
+# |\| |
+# | g |
+# | | |
+# | j |
+# | | |
+# | k |
+# | | |
+# | l |
+# |/|/
+# m n
+complex_shortcut = {'d':[NULL_REVISION],
+ 'x':['d'], 'y':['x'],
+ 'e':['y'], 'f':['d'], 'g':['f', 'i'], 'h':['f'],
+ 'i':['e'], 'j':['g'], 'k':['j'],
+ 'l':['k'], 'm':['i', 's'], 'n':['s', 'h'],
+ 'o':['l'], 'p':['o'], 'q':['p'],
+ 'r':['q'], 's':['r'],
+ }
+
+# Shortcut with extra root
+# We have a long history shortcut, and an extra root, which is why we can't
+# stop searchers based on seeing NULL_REVISION
+# NULL_REVISION
+# | |
+# a |
+# |\ |
+# b | |
+# | | |
+# c | |
+# | | |
+# d | g
+# |\|/
+# e f
+shortcut_extra_root = {'a': [NULL_REVISION],
+ 'b': ['a'],
+ 'c': ['b'],
+ 'd': ['c'],
+ 'e': ['d'],
+ 'f': ['a', 'd', 'g'],
+ 'g': [NULL_REVISION],
+ }
+
# NULL_REVISION
# |
# f
@@ -144,10 +248,17 @@
self.calls.extend(nodes)
return self._real_parents_provider.get_parents(nodes)
+ def get_parent_map(self, nodes):
+ self.calls.extend(nodes)
+ return self._real_parents_provider.get_parent_map(nodes)
+
class TestGraph(TestCaseWithMemoryTransport):
def make_graph(self, ancestors):
+ # XXX: This seems valid, is there a reason to actually create a
+ # repository and put things in it?
+ return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))
tree = self.prepare_memory_tree('.')
self.build_ancestry(tree, ancestors)
self.addCleanup(tree.unlock)
@@ -261,6 +372,10 @@
self.assertEqual(NULL_REVISION,
graph.find_unique_lca('rev4a', 'rev1b'))
+ def test_lca_double_shortcut(self):
+ graph = self.make_graph(double_shortcut)
+ self.assertEqual('c', graph.find_unique_lca('f', 'g'))
+
def test_common_ancestor_two_repos(self):
"""Ensure we do unique_lca using data from two repos"""
mainline_tree = self.prepare_memory_tree('mainline')
@@ -289,6 +404,14 @@
self.assertEqual((set(['rev4', 'rev3', 'rev2a']), set()),
graph.find_difference('rev4', 'rev2b'))
+ def test_graph_difference_separate_ancestry(self):
+ graph = self.make_graph(ancestry_2)
+ self.assertEqual((set(['rev1a']), set(['rev1b'])),
+ graph.find_difference('rev1a', 'rev1b'))
+ self.assertEqual((set(['rev1a', 'rev2a', 'rev3a', 'rev4a']),
+ set(['rev1b'])),
+ graph.find_difference('rev4a', 'rev1b'))
+
def test_graph_difference_criss_cross(self):
graph = self.make_graph(criss_cross)
self.assertEqual((set(['rev3a']), set(['rev3b'])),
@@ -296,19 +419,66 @@
self.assertEqual((set([]), set(['rev3b', 'rev2b'])),
graph.find_difference('rev2a', 'rev3b'))
- def test_stacked_parents_provider(self):
-
+ def test_graph_difference_extended_history(self):
+ graph = self.make_graph(extended_history_shortcut)
+ self.expectFailure('find_difference cannot handle shortcuts',
+ self.assertEqual, (set(['e']), set(['f'])),
+ graph.find_difference('e', 'f'))
+ self.assertEqual((set(['e']), set(['f'])),
+ graph.find_difference('e', 'f'))
+ self.assertEqual((set(['f']), set(['e'])),
+ graph.find_difference('f', 'e'))
+
+ def test_graph_difference_double_shortcut(self):
+ graph = self.make_graph(double_shortcut)
+ self.assertEqual((set(['d', 'f']), set(['e', 'g'])),
+ graph.find_difference('f', 'g'))
+
+ def test_graph_difference_complex_shortcut(self):
+ graph = self.make_graph(complex_shortcut)
+ self.expectFailure('find_difference cannot handle shortcuts',
+ self.assertEqual, (set(['m']), set(['h', 'n'])),
+ graph.find_difference('m', 'n'))
+ self.assertEqual((set(['m']), set(['h', 'n'])),
+ graph.find_difference('m', 'n'))
+
+ def test_graph_difference_shortcut_extra_root(self):
+ graph = self.make_graph(shortcut_extra_root)
+ self.expectFailure('find_difference cannot handle shortcuts',
+ self.assertEqual, (set(['e']), set(['f', 'g'])),
+ graph.find_difference('e', 'f'))
+ self.assertEqual((set(['e']), set(['f', 'g'])),
+ graph.find_difference('e', 'f'))
+
+ def test_stacked_parents_provider_get_parents(self):
parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
stacked = _mod_graph._StackedParentsProvider([parents1, parents2])
self.assertEqual([['rev4',], ['rev3']],
- stacked.get_parents(['rev1', 'rev2']))
+ self.applyDeprecated(symbol_versioning.one_one,
+ stacked.get_parents, ['rev1', 'rev2']))
self.assertEqual([['rev3',], ['rev4']],
- stacked.get_parents(['rev2', 'rev1']))
+ self.applyDeprecated(symbol_versioning.one_one,
+ stacked.get_parents, ['rev2', 'rev1']))
self.assertEqual([['rev3',], ['rev3']],
- stacked.get_parents(['rev2', 'rev2']))
+ self.applyDeprecated(symbol_versioning.one_one,
+ stacked.get_parents, ['rev2', 'rev2']))
self.assertEqual([['rev4',], ['rev4']],
- stacked.get_parents(['rev1', 'rev1']))
+ self.applyDeprecated(symbol_versioning.one_one,
+ stacked.get_parents, ['rev1', 'rev1']))
+
+ def test_stacked_parents_provider(self):
+ parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
+ parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
+ stacked = _mod_graph._StackedParentsProvider([parents1, parents2])
+ self.assertEqual({'rev1':['rev4'], 'rev2':['rev3']},
+ stacked.get_parent_map(['rev1', 'rev2']))
+ self.assertEqual({'rev2':['rev3'], 'rev1':['rev4']},
+ stacked.get_parent_map(['rev2', 'rev1']))
+ self.assertEqual({'rev2':['rev3']},
+ stacked.get_parent_map(['rev2', 'rev2']))
+ self.assertEqual({'rev1':['rev4']},
+ stacked.get_parent_map(['rev1', 'rev1']))
def test_iter_topo_order(self):
graph = self.make_graph(ancestry_1)
@@ -463,8 +633,16 @@
self.fail('key deeper was accessed')
result.append(graph_dict[key])
return result
+ def get_parent_map(keys):
+ result = {}
+ for key in keys:
+ if key == 'deeper':
+ self.fail('key deeper was accessed')
+ result[key] = graph_dict[key]
+ return result
an_obj = stub()
an_obj.get_parents = get_parents
+ an_obj.get_parent_map = get_parent_map
graph = _mod_graph.Graph(an_obj)
return graph.heads(search)
@@ -502,3 +680,61 @@
}
self.assertEqual(set(['h1', 'h2']),
self._run_heads_break_deeper(graph_dict, ['h1', 'h2']))
+
+
+class TestCachingParentsProvider(tests.TestCase):
+
+ def setUp(self):
+ super(TestCachingParentsProvider, self).setUp()
+ dict_pp = _mod_graph.DictParentsProvider({'a':('b',)})
+ self.inst_pp = InstrumentedParentsProvider(dict_pp)
+ self.caching_pp = _mod_graph.CachingParentsProvider(self.inst_pp)
+
+ def test_get_parents(self):
+ """Requesting the same revision should be returned from cache"""
+ self.assertEqual({}, self.caching_pp._cache)
+ self.assertEqual([('b',)],
+ self.applyDeprecated(symbol_versioning.one_one,
+ self.caching_pp.get_parents, ['a']))
+ self.assertEqual(['a'], self.inst_pp.calls)
+ self.assertEqual([('b',)],
+ self.applyDeprecated(symbol_versioning.one_one,
+ self.caching_pp.get_parents, ['a']))
+ # No new call, as it should have been returned from the cache
+ self.assertEqual(['a'], self.inst_pp.calls)
+ self.assertEqual({'a':('b',)}, self.caching_pp._cache)
+
+ def test_get_parent_map(self):
+ """Requesting the same revision should be returned from cache"""
+ self.assertEqual({}, self.caching_pp._cache)
+ self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
+ self.assertEqual(['a'], self.inst_pp.calls)
+ self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
+ # No new call, as it should have been returned from the cache
+ self.assertEqual(['a'], self.inst_pp.calls)
+ self.assertEqual({'a':('b',)}, self.caching_pp._cache)
+
+ def test_get_parent_map_not_present(self):
+ """The cache should also track when a revision doesn't exist"""
+ self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
+ self.assertEqual(['b'], self.inst_pp.calls)
+ self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
+ # No new calls
+ self.assertEqual(['b'], self.inst_pp.calls)
+ self.assertEqual({'b':None}, self.caching_pp._cache)
+
+ def test_get_parent_map_mixed(self):
+ """Anything that can be returned from cache, should be"""
+ self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
+ self.assertEqual(['b'], self.inst_pp.calls)
+ self.assertEqual({'a':('b',)},
+ self.caching_pp.get_parent_map(['a', 'b']))
+ self.assertEqual(['b', 'a'], self.inst_pp.calls)
+
+ def test_get_parent_map_repeated(self):
+ """Asking for the same parent 2x will only forward 1 request."""
+ self.assertEqual({'a':('b',)},
+ self.caching_pp.get_parent_map(['b', 'a', 'b']))
+ # Use sorted because we don't care about the order, just that each is
+ # only present 1 time.
+ self.assertEqual(['a', 'b'], sorted(self.inst_pp.calls))
More information about the bazaar-commits
mailing list