Rev 100: * Fixed O(history) access during plan creation (Robert Collins, lp:#249823). in http://people.ubuntu.com/~robertc/baz2.0/plugins/rebase/dev
Robert Collins
robertc at robertcollins.net
Sat Jul 19 09:09:05 BST 2008
At http://people.ubuntu.com/~robertc/baz2.0/plugins/rebase/dev
------------------------------------------------------------
revno: 100
revision-id: robertc at robertcollins.net-20080719080845-rnqcpp6jky1g3m7g
parent: robertc at robertcollins.net-20080718171813-wvgbhtgf1rwngtmn
committer: Robert Collins <robertc at robertcollins.net>
branch nick: dev
timestamp: Sat 2008-07-19 18:08:45 +1000
message:
* Fixed O(history) access during plan creation (Robert Collins, lp:#249823).
modified:
NEWS news-20070721005510-kbjm9yxqoeczq9fl-1
__init__.py __init__.py-20070626215909-fi0s39bkwxn4gcto-1
rebase.py rebase.py-20070626221123-ellanmf93nw8z9r1-1
test_blackbox.py test_blackbox.py-20070709202607-dyvt95dfu09tuv6a-1
test_rebase.py test_rebase.py-20070626221123-ellanmf93nw8z9r1-2
=== modified file 'NEWS'
--- a/NEWS 2008-06-23 02:04:28 +0000
+++ b/NEWS 2008-07-19 08:08:45 +0000
@@ -10,6 +10,8 @@
* Fixed overactive assertion. (#242245)
+ * Fixed O(history) access during plan creation (Robert Collins, lp:#249823).
+
ENHANCEMENTS
* Set author property to preserve committer and original author of the
=== modified file '__init__.py'
--- a/__init__.py 2008-07-18 11:43:56 +0000
+++ b/__init__.py 2008-07-19 08:08:45 +0000
@@ -58,20 +58,6 @@
check_bzrlib_version(min_compatible_bzr_version)
-def find_last_common_revid(revhistory1, revhistory2):
- """Find the last revision two revision histories have in common.
-
- :param revhistory1: First revision history (list of revids)
- :param revhistory2: First revision history (list of revids)
- :return: The last common revision id
- """
- for revid in reversed(revhistory1):
- if revid in revhistory2:
- return revid
-
- raise UnrelatedBranches()
-
-
class cmd_rebase(Command):
"""Re-base a branch.
@@ -111,7 +97,7 @@
help="Show what would be done, but don't actually do anything."),
Option('always-rebase-merges',
help="Don't skip revisions that merge already present revisions."),
- Option('pending-merges',
+ Option('pending-merges',
help="Rebase pending merges onto local branch"),
Option('onto', help='Different revision to replay onto.',
type=str)]
@@ -187,37 +173,31 @@
wt.branch.repository.fetch(upstream_repository, onto)
- if stop_revid is not None:
- revhistory = list(
- wt.branch.repository.iter_reverse_revision_history(
- stop_revid))
- revhistory.reverse()
- else:
- revhistory = wt.branch.revision_history()
+ if stop_revid is None:
+ stop_revid = wt.branch.last_revision()
+ elif not pending_merges:
+ stop_revid = wt.branch.repository.get_parent_map(
+ [stop_revid])[stop_revid][0]
+ repo_graph = wt.branch.repository.get_graph()
+ our_new, onto_unique = repo_graph.find_difference(stop_revid, onto)
if start_revid is None:
- common_revid = find_last_common_revid(revhistory,
- upstream.revision_history())
- if common_revid == upstream.last_revision():
+ if not onto_unique:
self.outf.write("No revisions to rebase.\n")
return
- if common_revid == revhistory[-1]:
+ if not our_new:
self.outf.write("Base branch is descendant of current "
"branch. Use 'bzr pull'.\n")
return
- try:
- start_revid = revhistory[revhistory.index(common_revid)+1]
- except NoSuchRevision:
- raise BzrCommandError(
- "No common revision, please specify --revision")
+ # else: include extra revisions needed to make start_revid mean
+ # something.
# Create plan
replace_map = generate_simple_plan(
- revhistory, start_revid, stop_revid, onto,
- wt.branch.repository.get_ancestry(onto),
- wt.branch.repository.get_graph(),
- lambda revid: regenerate_default_revid(wt.branch.repository,
- revid),
+ our_new, start_revid, stop_revid,
+ onto, repo_graph,
+ lambda revid: regenerate_default_revid(
+ wt.branch.repository, revid),
not always_rebase_merges
)
@@ -251,9 +231,7 @@
class cmd_rebase_abort(Command):
- """Abort an interrupted rebase
-
- """
+ """Abort an interrupted rebase."""
@display_command
def run(self):
@@ -274,9 +252,7 @@
class cmd_rebase_continue(Command):
- """Continue an interrupted rebase after resolving conflicts
-
- """
+ """Continue an interrupted rebase after resolving conflicts."""
takes_options = ['merge-type']
@display_command
=== modified file 'rebase.py'
--- a/rebase.py 2008-07-18 17:18:13 +0000
+++ b/rebase.py 2008-07-19 08:08:45 +0000
@@ -16,13 +16,15 @@
"""Rebase."""
from bzrlib.config import Config
-from bzrlib.errors import (BzrError, NoSuchFile, UnknownFormatError,
+from bzrlib.errors import (BzrError, NoSuchFile, UnknownFormatError,
NoCommonAncestor, UnrelatedBranches)
from bzrlib.generate_ids import gen_revision_id
+from bzrlib.graph import FrozenHeadsCache
from bzrlib.merge import Merger
from bzrlib import osutils
from bzrlib.revision import NULL_REVISION
from bzrlib.trace import mutter
+from bzrlib.tsort import topo_sort
import bzrlib.ui as ui
from maptree import MapTree, map_file_ids
@@ -125,17 +127,17 @@
return gen_revision_id(rev.committer, rev.timestamp)
-def generate_simple_plan(history, start_revid, stop_revid, onto_revid,
- onto_ancestry, graph, generate_revid,
- skip_full_merged=False):
+def generate_simple_plan(todo_set, start_revid, stop_revid, onto_revid, graph,
+ generate_revid, skip_full_merged=False):
"""Create a simple rebase plan that replays history based
on one revision being replayed on top of another.
- :param history: Revision history
+ :param todo_set: A set of revisions to rebase. Only the revisions from
+ stop_revid back through the left hand ancestry are rebased; other
+ revisions are ignored (and references to them are preserved).
:param start_revid: Id of revision at which to start replaying
:param stop_revid: Id of revision until which to stop replaying
:param onto_revid: Id of revision on top of which to replay
- :param onto_ancestry: Ancestry of onto_revid
:param graph: Graph object
:param generate_revid: Function for generating new revision ids
:param skip_full_merged: Skip revisions that merge already merged
@@ -143,28 +145,45 @@
:return: replace map
"""
- assert start_revid is None or start_revid in history, "invalid start revid"
- assert stop_revid is None or stop_revid in history, "invalid stop_revid"
+ assert start_revid is None or start_revid in todo_set, \
+ "invalid start revid(%r), todo_set(%r)" % (start_revid, todo_set)
+ assert stop_revid is None or stop_revid in todo_set, "invalid stop_revid"
replace_map = {}
- if start_revid is not None:
- start_revno = history.index(start_revid)
- else:
- start_revno = None
- if stop_revid is not None:
- stop_revno = history.index(stop_revid)+1
- else:
- stop_revno = None
+ parent_map = graph.get_parent_map(todo_set)
+ order = topo_sort(parent_map)
+ left_most_path = []
+ if stop_revid is None:
+ stop_revid = order[-1]
+ rev = stop_revid
+ while rev in parent_map:
+ left_most_path.append(rev)
+ if rev == start_revid:
+ # manual specified early-stop
+ break
+ rev = parent_map[rev][0]
+ left_most_path.reverse()
+ if start_revid is None:
+ # We need a common base.
+ lca = graph.find_lca(stop_revid, onto_revid)
+ if lca == set([NULL_REVISION]):
+ raise UnrelatedBranches()
new_parent = onto_revid
- todo = history[start_revno:stop_revno]
- parent_map = graph.get_parent_map(todo)
- for oldrevid in todo:
+ todo = left_most_path
+ heads_cache = FrozenHeadsCache(graph)
+ # XXX: The output replacemap'd parents should get looked up in some manner
+ # by the heads cache? RBC 20080719
+ for oldrevid in todo:
oldparents = parent_map[oldrevid]
assert isinstance(oldparents, tuple), "not tuple: %r" % oldparents
- assert oldparents == () or \
- oldparents[0] == history[history.index(oldrevid)-1], \
- "invalid old parents for %r" % oldrevid
if len(oldparents) > 1:
- parents = (new_parent,) + tuple(filter(lambda p: p not in onto_ancestry or p == onto_revid, oldparents[1:]))
+ additional_parents = heads_cache.heads(oldparents[1:])
+ parents = [new_parent]
+ for parent in parents:
+ if parent in additional_parents and parent not in parents:
+ # Use as a parent
+ parent = replace_map.get(parent, (parent,))[0]
+ parents.append(parent)
+ parents = tuple(parents)
if len(parents) == 1 and skip_full_merged:
continue
else:
@@ -301,10 +320,6 @@
finally:
pb.finished()
- #assert all(map(repository.has_revision,
- # [replace_map[r][0] for r in replace_map]))
-
-
def replay_snapshot(repository, oldrevid, newrevid, new_parents,
revid_renames, fix_revid=None):
=== modified file 'test_blackbox.py'
--- a/test_blackbox.py 2008-07-18 17:18:13 +0000
+++ b/test_blackbox.py 2008-07-19 08:08:45 +0000
@@ -13,6 +13,7 @@
# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+
"""Couple of blackbox tests for the rebase plugin."""
from bzrlib.branch import Branch
@@ -21,6 +22,7 @@
import os
class TestRebaseSimple(ExternalBase):
+
def make_file(self, name, contents):
f = open(name, 'wb')
try:
@@ -86,47 +88,70 @@
self.check_output('3\n', 'revno')
def test_range(self):
+ # commit mainline rev 2
self.make_file('hello', '42')
self.run_bzr('commit -m that')
+ # commit feature rev 2
os.chdir('../feature')
self.make_file('hoi', "my data")
self.run_bzr('add')
self.run_bzr('commit -m this')
+ # commit feature rev 3
self.make_file('hooi', "your data")
self.run_bzr('add')
self.run_bzr('commit -m that')
+ # commit feature rev 4
self.make_file('hoooi', "someone else's data")
self.run_bzr('add')
self.run_bzr('commit -m these')
+ # pick up just rev 2 and discard 3 & 4 from feature
self.check_output('', 'rebase -r2..3 ../main')
- self.check_output('4\n', 'revno')
+ # our rev 2 is now rev3:
+ self.check_output('3\n', 'revno')
+ # content added from our old revisions 3 and 4 should be gone.
+ self.failIfExists('hooi')
+ self.failIfExists('hoooi')
def test_range_open_end(self):
+ # commit mainline rev 2
self.make_file('hello', '42')
self.run_bzr('commit -m that')
+ # commit feature rev 2
os.chdir('../feature')
self.make_file('hoi', "my data")
self.run_bzr('add')
self.run_bzr('commit -m this')
+ # commit feature rev 3
self.make_file('hooi', "your data")
self.run_bzr('add')
self.run_bzr('commit -m that')
+ # commit feature rev 4
self.make_file('hoooi', "someone else's data")
self.run_bzr('add')
self.run_bzr('commit -m these')
+ # rebase only rev 4 onto main
self.check_output('', 'rebase -r4.. ../main')
+ # should only get rev 3 (our old 2 and 3 are gone)
self.check_output('3\n', 'revno')
+ self.failIfExists('hoi')
+ self.failIfExists('hooi')
branch = Branch.open(".")
- self.assertEquals("these",
+ self.assertEquals("these",
branch.repository.get_revision(branch.last_revision()).message)
+ self.failUnlessExists('hoooi')
def test_conflicting(self):
+ # commit mainline rev 2
self.make_file('hello', '42')
self.run_bzr('commit -m that')
+ # commit feature rev 2 changing hello differently
os.chdir('../feature')
self.make_file('hello', "other data")
self.run_bzr('commit -m this')
- self.run_bzr_error('Text conflict in hello\nbzr: ERROR: A conflict occurred replaying a commit. Resolve the conflict and run \'bzr rebase-continue\' or run \'bzr rebase-abort\'.\n', 'rebase ../main')
+ self.run_bzr_error([
+ 'Text conflict in hello',
+ 'bzr: ERROR: A conflict occurred replaying a commit. Resolve the conflict and run \'bzr rebase-continue\' or run \'bzr rebase-abort\'.',
+ ], 'rebase ../main')
def test_conflicting_abort(self):
self.make_file('hello', '42')
=== modified file 'test_rebase.py'
--- a/test_rebase.py 2008-07-18 17:18:13 +0000
+++ b/test_rebase.py 2008-07-19 08:08:45 +0000
@@ -86,6 +86,7 @@
class PlanCreatorTests(TestCaseWithTransport):
+
def test_simple_plan_creator(self):
wt = self.make_branch_and_tree('.')
b = wt.branch
@@ -100,12 +101,11 @@
wt.commit(message='change hello', rev_id="bla2")
b.repository.lock_read()
- self.assertEquals({'bla2': ('newbla2', ("bloe",))},
- generate_simple_plan(b.revision_history(), "bla2", None,
- "bloe",
- ("bloe", "bla"),
- b.repository.get_graph(),
- lambda y: "new"+y))
+ graph = b.repository.get_graph()
+ self.assertEquals({'bla2': ('newbla2', ("bloe",))},
+ generate_simple_plan(
+ graph.find_difference(b.last_revision(),"bla")[0],
+ "bla2", None, "bloe", graph, lambda y: "new"+y))
b.repository.unlock()
def test_simple_plan_creator_extra_history(self):
@@ -124,13 +124,14 @@
wt.commit(message='change hello again', rev_id="bla3")
b.repository.lock_read()
- self.assertEquals({'bla2': ('newbla2', ("bloe",)), 'bla3': ('newbla3', ('newbla2',))},
- generate_simple_plan(b.revision_history(), "bla2", None, "bloe",
- ("bloe", "bla"),
- b.repository.get_graph(),
- lambda y: "new"+y))
+ graph = b.repository.get_graph()
+ self.assertEquals(
+ {'bla2': ('newbla2', ("bloe",)), 'bla3': ('newbla3', ('newbla2',))},
+ generate_simple_plan(
+ graph.find_difference(b.last_revision(),"bloe")[0],
+ "bla2", None, "bloe",
+ graph, lambda y: "new"+y))
b.repository.unlock()
-
def test_generate_transpose_plan(self):
wt = self.make_branch_and_tree('.')
@@ -203,10 +204,9 @@
"E": ("D", "B")
}
graph = Graph(DictParentsProvider(parents_map))
- self.assertEquals({"D": ("D'", ("C",)), "E": ("E'", ("D'",))},
- generate_simple_plan(["A", "D", "E"],
- "D", None, "C", ["A", "B", "C"],
- graph, lambda y: y+"'"))
+ self.assertEquals({"D": ("D'", ("C",)), "E": ("E'", ("D'",))},
+ generate_simple_plan(["D", "E"], "D", None, "C",
+ graph, lambda y: y+"'"))
def test_plan_with_already_merged_skip_merges(self):
"""We need to use a merge base that makes sense.
@@ -233,9 +233,8 @@
"E": ("D", "B")
}
graph = Graph(DictParentsProvider(parents_map))
- self.assertEquals({"D": ("D'", ("C",))},
- generate_simple_plan(["A", "D", "E"],
- "D", None, "C", ["A", "B", "C"],
+ self.assertEquals({"D": ("D'", ("C",))},
+ generate_simple_plan(["D", "E"], "D", None, "C",
graph, lambda y: y+"'", True))
More information about the bazaar-commits
mailing list