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