Rev 3460: (jam) Implement Graph.find_distance_to_null(), in file:///home/pqm/archives/thelove/bzr/%2Btrunk/
Canonical.com Patch Queue Manager
pqm at pqm.ubuntu.com
Thu May 29 22:00:14 BST 2008
At file:///home/pqm/archives/thelove/bzr/%2Btrunk/
------------------------------------------------------------
revno: 3460
revision-id:pqm at pqm.ubuntu.com-20080529210000-bycgfufmrqq63tki
parent: pqm at pqm.ubuntu.com-20080529203427-tp2iw6h86fd1sauh
parent: john at arbash-meinel.com-20080529201737-4y4md0w6u6cuvrpo
committer: Canonical.com Patch Queue Manager <pqm at pqm.ubuntu.com>
branch nick: +trunk
timestamp: Thu 2008-05-29 22:00:00 +0100
message:
(jam) Implement Graph.find_distance_to_null(),
use it to speed up finding the revno when we are setting a branch to
a random revision_id
modified:
NEWS NEWS-20050323055033-4e00b5db738777ff
bzrlib/branch.py branch.py-20050309040759-e4baf4e0d046576e
bzrlib/errors.py errors.py-20050309040759-20512168c4e14fbd
bzrlib/graph.py graph_walker.py-20070525030359-y852guab65d4wtn0-1
bzrlib/remote.py remote.py-20060720103555-yeeg2x51vn0rbtdp-1
bzrlib/tests/branch_implementations/test_update.py test_update.py-20060305010612-e68efbcbb1baa69f
bzrlib/tests/test_errors.py test_errors.py-20060210110251-41aba2deddf936a8
bzrlib/tests/test_graph.py test_graph_walker.py-20070525030405-enq4r60hhi9xrujc-1
------------------------------------------------------------
revno: 3445.1.8
revision-id:john at arbash-meinel.com-20080529201737-4y4md0w6u6cuvrpo
parent: john at arbash-meinel.com-20080528222817-pcl5rlms0k9pd1g2
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: graph_find_distance_to_null
timestamp: Thu 2008-05-29 15:17:37 -0500
message:
Clarity tweaks recommended by Ian
modified:
bzrlib/branch.py branch.py-20050309040759-e4baf4e0d046576e
bzrlib/graph.py graph_walker.py-20070525030359-y852guab65d4wtn0-1
bzrlib/remote.py remote.py-20060720103555-yeeg2x51vn0rbtdp-1
bzrlib/tests/branch_implementations/test_update.py test_update.py-20060305010612-e68efbcbb1baa69f
bzrlib/tests/test_graph.py test_graph_walker.py-20070525030405-enq4r60hhi9xrujc-1
------------------------------------------------------------
revno: 3445.1.7
revision-id:john at arbash-meinel.com-20080528222817-pcl5rlms0k9pd1g2
parent: john at arbash-meinel.com-20080522230502-dpz32ohckuidvwyw
parent: pqm at pqm.ubuntu.com-20080527013230-8qjaju10duxpy3e2
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: graph_find_distance_to_null
timestamp: Wed 2008-05-28 17:28:17 -0500
message:
merge in and resolve conflicts with bzr.dev
added:
bzrlib/tests/file_utils.py file_utils.py-20080506145406-a1h3ydg2lsh2iriy-1
modified:
NEWS NEWS-20050323055033-4e00b5db738777ff
bzrlib/branch.py branch.py-20050309040759-e4baf4e0d046576e
bzrlib/bzrdir.py bzrdir.py-20060131065624-156dfea39c4387cb
bzrlib/config.py config.py-20051011043216-070c74f4e9e338e8
bzrlib/lockable_files.py control_files.py-20051111201905-bb88546e799d669f
bzrlib/merge.py merge.py-20050513021216-953b65a438527106
bzrlib/osutils.py osutils.py-20050309040759-eeaff12fbf77ac86
bzrlib/remote.py remote.py-20060720103555-yeeg2x51vn0rbtdp-1
bzrlib/repofmt/pack_repo.py pack_repo.py-20070813041115-gjv5ma7ktfqwsjgn-1
bzrlib/repofmt/weaverepo.py presplitout.py-20070125045333-wfav3tsh73oxu3zk-1
bzrlib/repository.py rev_storage.py-20051111201905-119e9401e46257e3
bzrlib/smart/branch.py branch.py-20061124031907-mzh3pla28r83r97f-1
bzrlib/smart/protocol.py protocol.py-20061108035435-ot0lstk2590yqhzr-1
bzrlib/smart/repository.py repository.py-20061128022038-vr5wy5bubyb8xttk-1
bzrlib/tests/blackbox/test_branch.py test_branch.py-20060524161337-noms9gmcwqqrfi8y-1
bzrlib/tests/branch_implementations/test_branch.py testbranch.py-20050711070244-121d632bc37d7253
bzrlib/tests/branch_implementations/test_push.py test_push.py-20070130153159-fhfap8uoifevg30j-1
bzrlib/tests/repository_implementations/test_has_same_location.py test_has_same_locati-20070807074648-2i2ah82fbe83iys7-1
bzrlib/tests/test_config.py testconfig.py-20051011041908-742d0c15d8d8c8eb
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_core.py test_merge_core.py-20050824132511-eb99b23a0eec641b
bzrlib/tests/test_osutils.py test_osutils.py-20051201224856-e48ee24c12182989
bzrlib/tests/test_osutils_encodings.py test_osutils_encodin-20061226013130-kkp732tpt3lm91vv-1
bzrlib/tests/test_remote.py test_remote.py-20060720103555-yeeg2x51vn0rbtdp-2
bzrlib/tests/test_repository.py test_repository.py-20060131075918-65c555b881612f4d
bzrlib/tests/test_smart.py test_smart.py-20061122024551-ol0l0o0oofsu9b3t-2
bzrlib/tests/test_smart_transport.py test_ssh_transport.py-20060608202016-c25gvf1ob7ypbus6-2
bzrlib/tests/test_transform.py test_transaction.py-20060105172520-b3ffb3946550e6c4
bzrlib/tests/test_workingtree.py testworkingtree.py-20051004024258-b88d0fe8f101d468
bzrlib/tests/workingtree_implementations/test_basis_inventory.py test_basis_inventory.py-20051218151655-3650468941091309
bzrlib/tests/workingtree_implementations/test_workingtree.py test_workingtree.py-20060203003124-817757d3e31444fb
bzrlib/transform.py transform.py-20060105172343-dd99e54394d91687
bzrlib/transport/fakenfs.py fakenfs.py-20060402223312-0e29c7275aa384dd
bzrlib/transport/http/response.py _response.py-20060613154423-a2ci7hd4iw5c7fnt-1
bzrlib/workingtree.py workingtree.py-20050511021032-29b6ec0a681e02e3
bzrlib/workingtree_4.py workingtree_4.py-20070208044105-5fgpc5j3ljlh5q6c-1
doc/developers/tortoise-strategy.txt tortoisestrategy.txt-20080403024510-2ahdqrvnwqrb5p5t-1
------------------------------------------------------------
revno: 3445.1.6
revision-id:john at arbash-meinel.com-20080522230502-dpz32ohckuidvwyw
parent: john at arbash-meinel.com-20080522225634-bl5qfq1caf119hr2
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: graph_find_distance_to_null
timestamp: Thu 2008-05-22 18:05:02 -0500
message:
Start using the 'graph' parameter of update_revisions to bias push and pull checking
modified:
bzrlib/branch.py branch.py-20050309040759-e4baf4e0d046576e
------------------------------------------------------------
revno: 3445.1.5
revision-id:john at arbash-meinel.com-20080522225634-bl5qfq1caf119hr2
parent: john at arbash-meinel.com-20080522220257-z3cnrx690d6ue4oz
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: graph_find_distance_to_null
timestamp: Thu 2008-05-22 17:56:34 -0500
message:
allow passing a 'graph' object into Branch.update_revisions.
modified:
NEWS NEWS-20050323055033-4e00b5db738777ff
bzrlib/branch.py branch.py-20050309040759-e4baf4e0d046576e
bzrlib/remote.py remote.py-20060720103555-yeeg2x51vn0rbtdp-1
bzrlib/tests/branch_implementations/test_update.py test_update.py-20060305010612-e68efbcbb1baa69f
------------------------------------------------------------
revno: 3445.1.4
revision-id:john at arbash-meinel.com-20080522220257-z3cnrx690d6ue4oz
parent: john at arbash-meinel.com-20080521194145-scvr9j7u0dmz6wti
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: graph_find_distance_to_null
timestamp: Thu 2008-05-22 17:02:57 -0500
message:
Change the function to be called 'find_distance_to_null'
modified:
bzrlib/graph.py graph_walker.py-20070525030359-y852guab65d4wtn0-1
bzrlib/tests/test_graph.py test_graph_walker.py-20070525030405-enq4r60hhi9xrujc-1
------------------------------------------------------------
revno: 3445.1.3
revision-id:john at arbash-meinel.com-20080521194145-scvr9j7u0dmz6wti
parent: john at arbash-meinel.com-20080521191128-49dvcb18r8qiteq3
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: graph_find_revno
timestamp: Wed 2008-05-21 14:41:45 -0500
message:
Search from all of the known revisions.
This lets us build up the numbering for all the stuff we know, and
allows us to stop early if there is convergence from a known revision
to the one in question.
In 'easy' cases this will search more than it has to, but it prevents
the worst-case behavior of always searching to the NULL revision.
modified:
bzrlib/graph.py graph_walker.py-20070525030359-y852guab65d4wtn0-1
bzrlib/tests/test_graph.py test_graph_walker.py-20070525030405-enq4r60hhi9xrujc-1
------------------------------------------------------------
revno: 3445.1.2
revision-id:john at arbash-meinel.com-20080521191128-49dvcb18r8qiteq3
parent: john at arbash-meinel.com-20080521190234-oijes1jniav97axe
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: graph_find_revno
timestamp: Wed 2008-05-21 14:11:28 -0500
message:
Handle when a known revision is an ancestor.
modified:
bzrlib/graph.py graph_walker.py-20070525030359-y852guab65d4wtn0-1
bzrlib/tests/test_graph.py test_graph_walker.py-20070525030405-enq4r60hhi9xrujc-1
------------------------------------------------------------
revno: 3445.1.1
revision-id:john at arbash-meinel.com-20080521190234-oijes1jniav97axe
parent: pqm at pqm.ubuntu.com-20080521104134-beoquporep2cpghs
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: graph_find_revno
timestamp: Wed 2008-05-21 14:02:34 -0500
message:
Start working on a new Graph api to make finding revision numbers faster.
The current implementation traverses all ancestors. We'll do better by seeding the
information with known revisions.
modified:
bzrlib/errors.py errors.py-20050309040759-20512168c4e14fbd
bzrlib/graph.py graph_walker.py-20070525030359-y852guab65d4wtn0-1
bzrlib/tests/test_errors.py test_errors.py-20060210110251-41aba2deddf936a8
bzrlib/tests/test_graph.py test_graph_walker.py-20070525030405-enq4r60hhi9xrujc-1
=== modified file 'NEWS'
--- a/NEWS 2008-05-29 20:34:27 +0000
+++ b/NEWS 2008-05-29 21:00:00 +0000
@@ -41,6 +41,11 @@
``Graph.find_differences`` to determine missing revisions without having
to search the whole ancestry. (John Arbash Meinel, #174625)
+ * ``bzr branch/push/pull -r XXX`` now have a helper function for finding
+ the revno of the new revision (``Graph.find_distance_to_null``). This
+ should make something like ``bzr branch -r -100`` in a shared, no-trees
+ repository much snappier. (John Arbash Meinel)
+
BUGFIXES:
* ``bzr merge --lca`` should handle when two revisions have no common
@@ -115,6 +120,11 @@
* ``Branch.abspath`` is deprecated; use the Tree or Transport
instead. (Martin Pool)
+ * ``Branch.update_revisions`` now takes an optional ``Graph``
+ object. This can be used by ``update_revisions`` when it is
+ checking ancestry, and allows callers to prefer request to go to a
+ local branch. (John Arbash Meinel)
+
* Branch, Repository, Tree and BzrDir should expose a Transport as an
attribute if they have one, rather than having it indirectly accessible
as ``.control_files._transport``. This doesn't add a requirement
=== modified file 'bzrlib/branch.py'
--- a/bzrlib/branch.py 2008-05-23 07:17:40 +0000
+++ b/bzrlib/branch.py 2008-05-29 20:17:37 +0000
@@ -447,11 +447,16 @@
raise errors.NoSuchRevision(self, stop_revision)
return other_history[self_len:stop_revision]
- def update_revisions(self, other, stop_revision=None):
+ def update_revisions(self, other, stop_revision=None, overwrite=False,
+ graph=None):
"""Pull in new perfect-fit revisions.
:param other: Another Branch to pull from
:param stop_revision: Updated until the given revision
+ :param overwrite: Always set the branch pointer, rather than checking
+ to see if it is a proper descendant.
+ :param graph: A Graph object that can be used to query history
+ information. This can be None.
:return: None
"""
raise NotImplementedError(self.update_revisions)
@@ -1501,17 +1506,21 @@
last_rev, other_branch))
@needs_write_lock
- def update_revisions(self, other, stop_revision=None, overwrite=False):
+ def update_revisions(self, other, stop_revision=None, overwrite=False,
+ graph=None):
"""See Branch.update_revisions."""
other.lock_read()
try:
- other_last_revno, other_last_revision = other.last_revision_info()
+ other_revno, other_last_revision = other.last_revision_info()
+ stop_revno = None # unknown
if stop_revision is None:
stop_revision = other_last_revision
if _mod_revision.is_null(stop_revision):
# if there are no commits, we're done.
return
- # whats the current last revision, before we fetch [and change it
+ stop_revno = other_revno
+
+ # what's the current last revision, before we fetch [and change it
# possibly]
last_rev = _mod_revision.ensure_null(self.last_revision())
# we fetch here so that we don't process data twice in the common
@@ -1521,8 +1530,9 @@
self.fetch(other, stop_revision)
# Check to see if one is an ancestor of the other
if not overwrite:
- heads = self.repository.get_graph().heads([stop_revision,
- last_rev])
+ if graph is None:
+ graph = self.repository.get_graph()
+ heads = graph.heads([stop_revision, last_rev])
if heads == set([last_rev]):
# The current revision is a decendent of the target,
# nothing to do
@@ -1532,17 +1542,14 @@
raise errors.DivergedBranches(self, other)
elif heads != set([stop_revision]):
raise AssertionError("invalid heads: %r" % heads)
- if other_last_revision == stop_revision:
- self.set_last_revision_info(other_last_revno,
- other_last_revision)
- else:
- # TODO: jam 2007-11-29 Is there a way to determine the
- # revno without searching all of history??
- if overwrite:
- self.generate_revision_history(stop_revision)
- else:
- self.generate_revision_history(stop_revision,
- last_rev=last_rev, other_branch=other)
+ if stop_revno is None:
+ if graph is None:
+ graph = self.repository.get_graph()
+ this_revno, this_last_revision = self.last_revision_info()
+ stop_revno = graph.find_distance_to_null(stop_revision,
+ [(other_last_revision, other_revno),
+ (this_last_revision, this_revno)])
+ self.set_last_revision_info(stop_revno, stop_revision)
finally:
other.unlock()
@@ -1566,8 +1573,12 @@
result.target_branch = self
source.lock_read()
try:
+ # We assume that during 'pull' the local repository is closer than
+ # the remote one.
+ graph = self.repository.get_graph(source.repository)
result.old_revno, result.old_revid = self.last_revision_info()
- self.update_revisions(source, stop_revision, overwrite=overwrite)
+ self.update_revisions(source, stop_revision, overwrite=overwrite,
+ graph=graph)
result.tag_conflicts = source.tags.merge_to(self.tags, overwrite)
result.new_revno, result.new_revid = self.last_revision_info()
if _hook_master:
@@ -1670,7 +1681,12 @@
result.source_branch = self
result.target_branch = target
result.old_revno, result.old_revid = target.last_revision_info()
- target.update_revisions(self, stop_revision, overwrite)
+
+ # We assume that during 'push' this repository is closer than
+ # the target.
+ graph = self.repository.get_graph(target.repository)
+ target.update_revisions(self, stop_revision, overwrite=overwrite,
+ graph=graph)
result.tag_conflicts = self.tags.merge_to(target.tags, overwrite)
result.new_revno, result.new_revid = target.last_revision_info()
return result
=== modified file 'bzrlib/errors.py'
--- a/bzrlib/errors.py 2008-05-16 05:59:21 +0000
+++ b/bzrlib/errors.py 2008-05-21 19:02:34 +0000
@@ -2253,6 +2253,17 @@
" Please set BZR_SSH environment variable.")
+class GhostRevisionsHaveNoRevno(BzrError):
+ """When searching for revnos, if we encounter a ghost, we are stuck"""
+
+ _fmt = ("Could not determine revno for {%(revision_id)s} because"
+ " its ancestry shows a ghost at {%(ghost_revision_id)s}")
+
+ def __init__(self, revision_id, ghost_revision_id):
+ self.revision_id = revision_id
+ self.ghost_revision_id = ghost_revision_id
+
+
class GhostRevisionUnusableHere(BzrError):
_fmt = "Ghost revision {%(revision_id)s} cannot be used here."
=== modified file 'bzrlib/graph.py'
--- a/bzrlib/graph.py 2008-05-21 05:46:23 +0000
+++ b/bzrlib/graph.py 2008-05-29 20:17:37 +0000
@@ -212,6 +212,59 @@
right = searchers[1].seen
return (left.difference(right), right.difference(left))
+ def find_distance_to_null(self, target_revision_id, known_revision_ids):
+ """Find the left-hand distance to the NULL_REVISION.
+
+ (This can also be considered the revno of a branch at
+ target_revision_id.)
+
+ :param target_revision_id: A revision_id which we would like to know
+ the revno for.
+ :param known_revision_ids: [(revision_id, revno)] A list of known
+ revno, revision_id tuples. We'll use this to seed the search.
+ """
+ # Map from revision_ids to a known value for their revno
+ known_revnos = dict(known_revision_ids)
+ cur_tip = target_revision_id
+ num_steps = 0
+ NULL_REVISION = revision.NULL_REVISION
+ known_revnos[NULL_REVISION] = 0
+
+ searching_known_tips = list(known_revnos.keys())
+
+ unknown_searched = {}
+
+ while cur_tip not in known_revnos:
+ unknown_searched[cur_tip] = num_steps
+ num_steps += 1
+ to_search = set([cur_tip])
+ to_search.update(searching_known_tips)
+ parent_map = self.get_parent_map(to_search)
+ parents = parent_map.get(cur_tip, None)
+ if not parents: # An empty list or None is a ghost
+ raise errors.GhostRevisionsHaveNoRevno(target_revision_id,
+ cur_tip)
+ cur_tip = parents[0]
+ next_known_tips = []
+ for revision_id in searching_known_tips:
+ parents = parent_map.get(revision_id, None)
+ if not parents:
+ continue
+ next = parents[0]
+ next_revno = known_revnos[revision_id] - 1
+ if next in unknown_searched:
+ # We have enough information to return a value right now
+ return next_revno + unknown_searched[next]
+ if next in known_revnos:
+ continue
+ known_revnos[next] = next_revno
+ next_known_tips.append(next)
+ searching_known_tips = next_known_tips
+
+ # We reached a known revision, so just add in how many steps it took to
+ # get there.
+ return known_revnos[cur_tip] + num_steps
+
def find_unique_ancestors(self, unique_revision, common_revisions):
"""Find the unique ancestors for a revision versus others.
=== modified file 'bzrlib/remote.py'
--- a/bzrlib/remote.py 2008-05-22 05:48:22 +0000
+++ b/bzrlib/remote.py 2008-05-29 20:17:37 +0000
@@ -48,6 +48,7 @@
from bzrlib.revision import ensure_null, NULL_REVISION
from bzrlib.trace import mutter, note, warning
+
# Note: RemoteBzrDirFormat is in bzrdir.py
class RemoteBzrDir(BzrDir):
@@ -1564,10 +1565,12 @@
self._ensure_real()
return self._real_branch.set_push_location(location)
- def update_revisions(self, other, stop_revision=None, overwrite=False):
+ def update_revisions(self, other, stop_revision=None, overwrite=False,
+ graph=None):
self._ensure_real()
return self._real_branch.update_revisions(
- other, stop_revision=stop_revision, overwrite=overwrite)
+ other, stop_revision=stop_revision, overwrite=overwrite,
+ graph=graph)
def _extract_tar(tar, to_dir):
=== modified file 'bzrlib/tests/branch_implementations/test_update.py'
--- a/bzrlib/tests/branch_implementations/test_update.py 2007-07-11 19:44:51 +0000
+++ b/bzrlib/tests/branch_implementations/test_update.py 2008-05-29 20:17:37 +0000
@@ -67,3 +67,51 @@
master_tree.commit('bar', rev_id='bar', allow_pointless=True)
self.assertEqual('foo', child_tree.branch.update())
self.assertEqual(['bar'], child_tree.branch.revision_history())
+
+
+class TestUpdateRevisions(TestCaseWithBranch):
+
+ def test_accepts_graph(self):
+ # An implementation may not use it, but it should allow a 'graph' to be
+ # supplied
+ tree1 = self.make_branch_and_tree('tree1')
+ rev1 = tree1.commit('one')
+ tree2 = tree1.bzrdir.sprout('tree2').open_workingtree()
+ rev2 = tree2.commit('two')
+
+ tree1.lock_write()
+ self.addCleanup(tree1.unlock)
+ tree2.lock_read()
+ self.addCleanup(tree2.unlock)
+ graph = tree2.branch.repository.get_graph(tree1.branch.repository)
+
+ tree1.branch.update_revisions(tree2.branch, graph=graph)
+ self.assertEqual((2, rev2), tree1.branch.last_revision_info())
+
+ def test_overwrite_ignores_diverged(self):
+ tree1 = self.make_branch_and_tree('tree1')
+ rev1 = tree1.commit('one')
+ tree2 = tree1.bzrdir.sprout('tree2').open_workingtree()
+ rev2 = tree1.commit('two')
+ rev2b = tree2.commit('alt two')
+
+ self.assertRaises(errors.DivergedBranches,
+ tree1.branch.update_revisions,
+ tree2.branch, overwrite=False)
+ # However, the revision should be copied into the repository
+ self.assertTrue(tree1.branch.repository.has_revision(rev2b))
+
+ tree1.branch.update_revisions(tree2.branch, overwrite=True)
+ self.assertEqual((2, rev2b), tree1.branch.last_revision_info())
+
+ def test_ignores_older_unless_overwrite(self):
+ tree1 = self.make_branch_and_tree('tree1')
+ rev1 = tree1.commit('one')
+ tree2 = tree1.bzrdir.sprout('tree2').open_workingtree()
+ rev2 = tree1.commit('two')
+
+ tree1.branch.update_revisions(tree2.branch)
+ self.assertEqual((2, rev2), tree1.branch.last_revision_info())
+
+ tree1.branch.update_revisions(tree2.branch, overwrite=True)
+ self.assertEqual((1, rev1), tree1.branch.last_revision_info())
=== modified file 'bzrlib/tests/test_errors.py'
--- a/bzrlib/tests/test_errors.py 2008-05-11 23:49:50 +0000
+++ b/bzrlib/tests/test_errors.py 2008-05-21 19:02:34 +0000
@@ -52,6 +52,12 @@
self.assertEqualDiff('The prefix foo is in the help search path twice.',
str(error))
+ def test_ghost_revisions_have_no_revno(self):
+ error = errors.GhostRevisionsHaveNoRevno('target', 'ghost_rev')
+ self.assertEqualDiff("Could not determine revno for {target} because"
+ " its ancestry shows a ghost at {ghost_rev}",
+ str(error))
+
def test_incompatibleAPI(self):
error = errors.IncompatibleAPI("module", (1, 2, 3), (4, 5, 6), (7, 8, 9))
self.assertEqualDiff(
=== modified file 'bzrlib/tests/test_graph.py'
--- a/bzrlib/tests/test_graph.py 2008-05-06 20:54:31 +0000
+++ b/bzrlib/tests/test_graph.py 2008-05-29 20:17:37 +0000
@@ -396,6 +396,28 @@
with_ghost = {'a': ['b'], 'c': ['b', 'd'], 'b':['e'], 'd':['e', 'g'],
'e': ['f'], 'f':[NULL_REVISION], NULL_REVISION:()}
+# A graph that shows we can shortcut finding revnos when reaching them from the
+# side.
+# NULL_REVISION
+# |
+# a
+# |
+# b
+# |
+# c
+# |
+# d
+# |
+# e
+# / \
+# f g
+# |
+# h
+# |
+# i
+
+with_tail = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'], 'd':['c'], 'e':['d'],
+ 'f':['e'], 'g':['e'], 'h':['f'], 'i':['h']}
class InstrumentedParentsProvider(object):
@@ -409,6 +431,24 @@
return self._real_parents_provider.get_parent_map(nodes)
+class TestGraphBase(tests.TestCase):
+
+ def make_graph(self, ancestors):
+ return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))
+
+ def make_breaking_graph(self, ancestors, break_on):
+ """Make a Graph that raises an exception if we hit a node."""
+ g = self.make_graph(ancestors)
+ orig_parent_map = g.get_parent_map
+ def get_parent_map(keys):
+ bad_keys = set(keys).intersection(break_on)
+ if bad_keys:
+ self.fail('key(s) %s was accessed' % (sorted(bad_keys),))
+ return orig_parent_map(keys)
+ g.get_parent_map = get_parent_map
+ return g
+
+
class TestGraph(TestCaseWithMemoryTransport):
def make_graph(self, ancestors):
@@ -1138,22 +1178,7 @@
self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
-class TestFindUniqueAncestors(tests.TestCase):
-
- def make_graph(self, ancestors):
- return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))
-
- def make_breaking_graph(self, ancestors, break_on):
- """Make a Graph that raises an exception if we hit a node."""
- g = self.make_graph(ancestors)
- orig_parent_map = g.get_parent_map
- def get_parent_map(keys):
- bad_keys = set(keys).intersection(break_on)
- if bad_keys:
- self.fail('key(s) %s was accessed' % (sorted(bad_keys),))
- return orig_parent_map(keys)
- g.get_parent_map = get_parent_map
- return g
+class TestFindUniqueAncestors(TestGraphBase):
def assertFindUniqueAncestors(self, graph, expected, node, common):
actual = graph.find_unique_ancestors(node, common)
@@ -1228,6 +1253,65 @@
['h', 'i', 'j', 'y'], 'j', ['z'])
+class TestGraphFindDistanceToNull(TestGraphBase):
+ """Test an api that should be able to compute a revno"""
+
+ def assertFindDistance(self, revno, graph, target_id, known_ids):
+ """Assert the output of Graph.find_distance_to_null()"""
+ actual = graph.find_distance_to_null(target_id, known_ids)
+ self.assertEqual(revno, actual)
+
+ def test_nothing_known(self):
+ graph = self.make_graph(ancestry_1)
+ self.assertFindDistance(0, graph, NULL_REVISION, [])
+ self.assertFindDistance(1, graph, 'rev1', [])
+ self.assertFindDistance(2, graph, 'rev2a', [])
+ self.assertFindDistance(2, graph, 'rev2b', [])
+ self.assertFindDistance(3, graph, 'rev3', [])
+ self.assertFindDistance(4, graph, 'rev4', [])
+
+ def test_rev_is_ghost(self):
+ graph = self.make_graph(ancestry_1)
+ e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
+ graph.find_distance_to_null, 'rev_missing', [])
+ self.assertEqual('rev_missing', e.revision_id)
+ self.assertEqual('rev_missing', e.ghost_revision_id)
+
+ def test_ancestor_is_ghost(self):
+ graph = self.make_graph({'rev':['parent']})
+ e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
+ graph.find_distance_to_null, 'rev', [])
+ self.assertEqual('rev', e.revision_id)
+ self.assertEqual('parent', e.ghost_revision_id)
+
+ def test_known_in_ancestry(self):
+ graph = self.make_graph(ancestry_1)
+ self.assertFindDistance(2, graph, 'rev2a', [('rev1', 1)])
+ self.assertFindDistance(3, graph, 'rev3', [('rev2a', 2)])
+
+ def test_known_in_ancestry_limits(self):
+ graph = self.make_breaking_graph(ancestry_1, ['rev1'])
+ self.assertFindDistance(4, graph, 'rev4', [('rev3', 3)])
+
+ def test_target_is_ancestor(self):
+ graph = self.make_graph(ancestry_1)
+ self.assertFindDistance(2, graph, 'rev2a', [('rev3', 3)])
+
+ def test_target_is_ancestor_limits(self):
+ """We shouldn't search all history if we run into ourselves"""
+ graph = self.make_breaking_graph(ancestry_1, ['rev1'])
+ self.assertFindDistance(3, graph, 'rev3', [('rev4', 4)])
+
+ def test_target_parallel_to_known_limits(self):
+ # Even though the known revision isn't part of the other ancestry, they
+ # eventually converge
+ graph = self.make_breaking_graph(with_tail, ['a'])
+ self.assertFindDistance(6, graph, 'f', [('g', 6)])
+ self.assertFindDistance(7, graph, 'h', [('g', 6)])
+ self.assertFindDistance(8, graph, 'i', [('g', 6)])
+ self.assertFindDistance(6, graph, 'g', [('i', 8)])
+
+
class TestCachingParentsProvider(tests.TestCase):
def setUp(self):
More information about the bazaar-commits
mailing list