← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_graph.py

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2007-06-18 21:07:10 UTC
  • mfrom: (2490.2.27 graphwalker)
  • Revision ID: pqm@pqm.ubuntu.com-20070618210710-6y8wzcqiw2kvxdiy
Better merge base selection and graph API

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_graph.py
 
1
# Copyright (C) 2007 Canonical Ltd
 
2
#
 
3
# This program is free software; you can redistribute it and/or modify
 
4
# it under the terms of the GNU General Public License as published by
 
5
# the Free Software Foundation; either version 2 of the License, or
 
6
# (at your option) any later version.
 
7
#
 
8
# This program is distributed in the hope that it will be useful,
 
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
 
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
11
# GNU General Public License for more details.
 
12
#
 
13
# You should have received a copy of the GNU General Public License
 
14
# along with this program; if not, write to the Free Software
 
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
16
 
 
17
from bzrlib import graph
 
18
from bzrlib.revision import NULL_REVISION
 
19
from bzrlib.tests import TestCaseWithMemoryTransport
 
20
 
 
21
 
 
22
# Ancestry 1:
 
23
#
 
24
#  NULL_REVISION
 
25
#       |
 
26
#     rev1
 
27
#      /\
 
28
#  rev2a rev2b
 
29
#     |    |
 
30
#   rev3  /
 
31
#     |  /
 
32
#   rev4
 
33
ancestry_1 = {'rev1': [NULL_REVISION], 'rev2a': ['rev1'], 'rev2b': ['rev1'],
 
34
              'rev3': ['rev2a'], 'rev4': ['rev3', 'rev2b']}
 
35
 
 
36
 
 
37
# Ancestry 2:
 
38
#
 
39
#  NULL_REVISION
 
40
#    /    \
 
41
# rev1a  rev1b
 
42
#   |
 
43
# rev2a
 
44
#   |
 
45
# rev3a
 
46
#   |
 
47
# rev4a
 
48
ancestry_2 = {'rev1a': [NULL_REVISION], 'rev2a': ['rev1a'],
 
49
              'rev1b': [NULL_REVISION], 'rev3a': ['rev2a'], 'rev4a': ['rev3a']}
 
50
 
 
51
 
 
52
# Criss cross ancestry
 
53
#
 
54
#     NULL_REVISION
 
55
#         |
 
56
#        rev1
 
57
#        /  \
 
58
#    rev2a  rev2b
 
59
#       |\  /|
 
60
#       |  X |
 
61
#       |/  \|
 
62
#    rev3a  rev3b
 
63
criss_cross = {'rev1': [NULL_REVISION], 'rev2a': ['rev1'], 'rev2b': ['rev1'],
 
64
               'rev3a': ['rev2a', 'rev2b'], 'rev3b': ['rev2b', 'rev2a']}
 
65
 
 
66
 
 
67
# Criss-cross 2
 
68
#
 
69
#  NULL_REVISION
 
70
#    /   \
 
71
# rev1a  rev1b
 
72
#   |\   /|
 
73
#   | \ / |
 
74
#   |  X  |
 
75
#   | / \ |
 
76
#   |/   \|
 
77
# rev2a  rev2b
 
78
criss_cross2 = {'rev1a': [NULL_REVISION], 'rev1b': [NULL_REVISION],
 
79
                'rev2a': ['rev1a', 'rev1b'], 'rev2b': ['rev1b', 'rev1a']}
 
80
 
 
81
 
 
82
# Mainline:
 
83
#
 
84
#  NULL_REVISION
 
85
#       |
 
86
#      rev1
 
87
#      /  \
 
88
#      | rev2b
 
89
#      |  /
 
90
#     rev2a
 
91
mainline = {'rev1': [NULL_REVISION], 'rev2a': ['rev1', 'rev2b'],
 
92
            'rev2b': ['rev1']}
 
93
 
 
94
 
 
95
# feature branch:
 
96
#
 
97
#  NULL_REVISION
 
98
#       |
 
99
#      rev1
 
100
#       |
 
101
#     rev2b
 
102
#       |
 
103
#     rev3b
 
104
feature_branch = {'rev1': [NULL_REVISION],
 
105
                  'rev2b': ['rev1'], 'rev3b': ['rev2b']}
 
106
 
 
107
 
 
108
# History shortcut
 
109
#  NULL_REVISION
 
110
#       |
 
111
#     rev1------
 
112
#     /  \      \
 
113
#  rev2a rev2b rev2c
 
114
#    |  /   \   /
 
115
#  rev3a    reveb
 
116
history_shortcut = {'rev1': [NULL_REVISION], 'rev2a': ['rev1'],
 
117
                    'rev2b': ['rev1'], 'rev2c': ['rev1'],
 
118
                    'rev3a': ['rev2a', 'rev2b'], 'rev3b': ['rev2b', 'rev2c']}
 
119
 
 
120
 
 
121
class TestGraphWalker(TestCaseWithMemoryTransport):
 
122
 
 
123
    def make_graph(self, ancestors):
 
124
        tree = self.prepare_memory_tree('.')
 
125
        self.build_ancestry(tree, ancestors)
 
126
        tree.unlock()
 
127
        return tree.branch.repository.get_graph()
 
128
 
 
129
    def prepare_memory_tree(self, location):
 
130
        tree = self.make_branch_and_memory_tree(location)
 
131
        tree.lock_write()
 
132
        tree.add('.')
 
133
        return tree
 
134
 
 
135
    def build_ancestry(self, tree, ancestors):
 
136
        """Create an ancestry as specified by a graph dict
 
137
 
 
138
        :param tree: A tree to use
 
139
        :param ancestors: a dict of {node: [node_parent, ...]}
 
140
        """
 
141
        pending = [NULL_REVISION]
 
142
        descendants = {}
 
143
        for descendant, parents in ancestors.iteritems():
 
144
            for parent in parents:
 
145
                descendants.setdefault(parent, []).append(descendant)
 
146
        while len(pending) > 0:
 
147
            cur_node = pending.pop()
 
148
            for descendant in descendants.get(cur_node, []):
 
149
                if tree.branch.repository.has_revision(descendant):
 
150
                    continue
 
151
                parents = [p for p in ancestors[descendant] if p is not
 
152
                           NULL_REVISION]
 
153
                if len([p for p in parents if not
 
154
                    tree.branch.repository.has_revision(p)]) > 0:
 
155
                    continue
 
156
                tree.set_parent_ids(parents)
 
157
                if len(parents) > 0:
 
158
                    left_parent = parents[0]
 
159
                else:
 
160
                    left_parent = NULL_REVISION
 
161
                tree.branch.set_last_revision_info(
 
162
                    len(tree.branch._lefthand_history(left_parent)),
 
163
                    left_parent)
 
164
                tree.commit(descendant, rev_id=descendant)
 
165
                pending.append(descendant)
 
166
 
 
167
    def test_lca(self):
 
168
        """Test finding least common ancestor.
 
169
 
 
170
        ancestry_1 should always have a single common ancestor
 
171
        """
 
172
        graph = self.make_graph(ancestry_1)
 
173
        self.assertEqual(set([NULL_REVISION]),
 
174
                         graph.find_lca(NULL_REVISION, NULL_REVISION))
 
175
        self.assertEqual(set([NULL_REVISION]),
 
176
                         graph.find_lca(NULL_REVISION, 'rev1'))
 
177
        self.assertEqual(set(['rev1']), graph.find_lca('rev1', 'rev1'))
 
178
        self.assertEqual(set(['rev1']), graph.find_lca('rev2a', 'rev2b'))
 
179
 
 
180
    def test_lca_criss_cross(self):
 
181
        """Test least-common-ancestor after a criss-cross merge."""
 
182
        graph = self.make_graph(criss_cross)
 
183
        self.assertEqual(set(['rev2a', 'rev2b']),
 
184
                         graph.find_lca('rev3a', 'rev3b'))
 
185
        self.assertEqual(set(['rev2b']),
 
186
                         graph.find_lca('rev3a', 'rev3b', 'rev2b'))
 
187
 
 
188
    def test_lca_shortcut(self):
 
189
        """Test least-common ancestor on this history shortcut"""
 
190
        graph = self.make_graph(history_shortcut)
 
191
        self.assertEqual(set(['rev2b']), graph.find_lca('rev3a', 'rev3b'))
 
192
 
 
193
    def test_recursive_unique_lca(self):
 
194
        """Test finding a unique least common ancestor.
 
195
 
 
196
        ancestry_1 should always have a single common ancestor
 
197
        """
 
198
        graph = self.make_graph(ancestry_1)
 
199
        self.assertEqual(NULL_REVISION,
 
200
                         graph.find_unique_lca(NULL_REVISION, NULL_REVISION))
 
201
        self.assertEqual(NULL_REVISION,
 
202
                         graph.find_unique_lca(NULL_REVISION, 'rev1'))
 
203
        self.assertEqual('rev1', graph.find_unique_lca('rev1', 'rev1'))
 
204
        self.assertEqual('rev1', graph.find_unique_lca('rev2a', 'rev2b'))
 
205
 
 
206
    def test_unique_lca_criss_cross(self):
 
207
        """Ensure we don't pick non-unique lcas in a criss-cross"""
 
208
        graph = self.make_graph(criss_cross)
 
209
        self.assertEqual('rev1', graph.find_unique_lca('rev3a', 'rev3b'))
 
210
 
 
211
    def test_unique_lca_null_revision(self):
 
212
        """Ensure we pick NULL_REVISION when necessary"""
 
213
        graph = self.make_graph(criss_cross2)
 
214
        self.assertEqual('rev1b', graph.find_unique_lca('rev2a', 'rev1b'))
 
215
        self.assertEqual(NULL_REVISION,
 
216
                         graph.find_unique_lca('rev2a', 'rev2b'))
 
217
 
 
218
    def test_unique_lca_null_revision2(self):
 
219
        """Ensure we pick NULL_REVISION when necessary"""
 
220
        graph = self.make_graph(ancestry_2)
 
221
        self.assertEqual(NULL_REVISION,
 
222
                         graph.find_unique_lca('rev4a', 'rev1b'))
 
223
 
 
224
    def test_common_ancestor_two_repos(self):
 
225
        """Ensure we do unique_lca using data from two repos"""
 
226
        mainline_tree = self.prepare_memory_tree('mainline')
 
227
        self.build_ancestry(mainline_tree, mainline)
 
228
        mainline_tree.unlock()
 
229
 
 
230
        # This is cheating, because the revisions in the graph are actually
 
231
        # different revisions, despite having the same revision-id.
 
232
        feature_tree = self.prepare_memory_tree('feature')
 
233
        self.build_ancestry(feature_tree, feature_branch)
 
234
        feature_tree.unlock()
 
235
        graph = mainline_tree.branch.repository.get_graph(
 
236
            feature_tree.branch.repository)
 
237
        self.assertEqual('rev2b', graph.find_unique_lca('rev2a', 'rev3b'))
 
238
 
 
239
    def test_graph_difference(self):
 
240
        graph = self.make_graph(ancestry_1)
 
241
        self.assertEqual((set(), set()), graph.find_difference('rev1', 'rev1'))
 
242
        self.assertEqual((set(), set(['rev1'])),
 
243
                         graph.find_difference(NULL_REVISION, 'rev1'))
 
244
        self.assertEqual((set(['rev1']), set()),
 
245
                         graph.find_difference('rev1', NULL_REVISION))
 
246
        self.assertEqual((set(['rev2a', 'rev3']), set(['rev2b'])),
 
247
                         graph.find_difference('rev3', 'rev2b'))
 
248
        self.assertEqual((set(['rev4', 'rev3', 'rev2a']), set()),
 
249
                         graph.find_difference('rev4', 'rev2b'))
 
250
 
 
251
    def test_graph_difference_criss_cross(self):
 
252
        graph = self.make_graph(criss_cross)
 
253
        self.assertEqual((set(['rev3a']), set(['rev3b'])),
 
254
                         graph.find_difference('rev3a', 'rev3b'))
 
255
        self.assertEqual((set([]), set(['rev3b', 'rev2b'])),
 
256
                         graph.find_difference('rev2a', 'rev3b'))
 
257
 
 
258
    def test_stacked_parents_provider(self):
 
259
 
 
260
        class ParentsProvider(object):
 
261
 
 
262
            def __init__(self, ancestry):
 
263
                self.ancestry = ancestry
 
264
 
 
265
            def get_parents(self, revisions):
 
266
                return [self.ancestry.get(r, None) for r in revisions]
 
267
 
 
268
        parents1 = ParentsProvider({'rev2': ['rev3']})
 
269
        parents2 = ParentsProvider({'rev1': ['rev4']})
 
270
        stacked = graph._StackedParentsProvider([parents1, parents2])
 
271
        self.assertEqual([['rev4',], ['rev3']],
 
272
                         stacked.get_parents(['rev1', 'rev2']))
 
273
        self.assertEqual([['rev3',], ['rev4']],
 
274
                         stacked.get_parents(['rev2', 'rev1']))
 
275
        self.assertEqual([['rev3',], ['rev3']],
 
276
                         stacked.get_parents(['rev2', 'rev2']))
 
277
        self.assertEqual([['rev4',], ['rev4']],
 
278
                         stacked.get_parents(['rev1', 'rev1']))