← 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: Robert Collins
  • Date: 2007-07-04 08:08:13 UTC
  • mfrom: (2572 +trunk)
  • mto: This revision was merged to the branch mainline in revision 2587.
  • Revision ID: robertc@robertcollins.net-20070704080813-wzebx0r88fvwj5rq
Merge bzr.dev.

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 (
 
18
    errors,
 
19
    graph,
 
20
    )
 
21
from bzrlib.revision import NULL_REVISION
 
22
from bzrlib.tests import TestCaseWithMemoryTransport
 
23
 
 
24
 
 
25
# Ancestry 1:
 
26
#
 
27
#  NULL_REVISION
 
28
#       |
 
29
#     rev1
 
30
#      /\
 
31
#  rev2a rev2b
 
32
#     |    |
 
33
#   rev3  /
 
34
#     |  /
 
35
#   rev4
 
36
ancestry_1 = {'rev1': [NULL_REVISION], 'rev2a': ['rev1'], 'rev2b': ['rev1'],
 
37
              'rev3': ['rev2a'], 'rev4': ['rev3', 'rev2b']}
 
38
 
 
39
 
 
40
# Ancestry 2:
 
41
#
 
42
#  NULL_REVISION
 
43
#    /    \
 
44
# rev1a  rev1b
 
45
#   |
 
46
# rev2a
 
47
#   |
 
48
# rev3a
 
49
#   |
 
50
# rev4a
 
51
ancestry_2 = {'rev1a': [NULL_REVISION], 'rev2a': ['rev1a'],
 
52
              'rev1b': [NULL_REVISION], 'rev3a': ['rev2a'], 'rev4a': ['rev3a']}
 
53
 
 
54
 
 
55
# Criss cross ancestry
 
56
#
 
57
#     NULL_REVISION
 
58
#         |
 
59
#        rev1
 
60
#        /  \
 
61
#    rev2a  rev2b
 
62
#       |\  /|
 
63
#       |  X |
 
64
#       |/  \|
 
65
#    rev3a  rev3b
 
66
criss_cross = {'rev1': [NULL_REVISION], 'rev2a': ['rev1'], 'rev2b': ['rev1'],
 
67
               'rev3a': ['rev2a', 'rev2b'], 'rev3b': ['rev2b', 'rev2a']}
 
68
 
 
69
 
 
70
# Criss-cross 2
 
71
#
 
72
#  NULL_REVISION
 
73
#    /   \
 
74
# rev1a  rev1b
 
75
#   |\   /|
 
76
#   | \ / |
 
77
#   |  X  |
 
78
#   | / \ |
 
79
#   |/   \|
 
80
# rev2a  rev2b
 
81
criss_cross2 = {'rev1a': [NULL_REVISION], 'rev1b': [NULL_REVISION],
 
82
                'rev2a': ['rev1a', 'rev1b'], 'rev2b': ['rev1b', 'rev1a']}
 
83
 
 
84
 
 
85
# Mainline:
 
86
#
 
87
#  NULL_REVISION
 
88
#       |
 
89
#      rev1
 
90
#      /  \
 
91
#      | rev2b
 
92
#      |  /
 
93
#     rev2a
 
94
mainline = {'rev1': [NULL_REVISION], 'rev2a': ['rev1', 'rev2b'],
 
95
            'rev2b': ['rev1']}
 
96
 
 
97
 
 
98
# feature branch:
 
99
#
 
100
#  NULL_REVISION
 
101
#       |
 
102
#      rev1
 
103
#       |
 
104
#     rev2b
 
105
#       |
 
106
#     rev3b
 
107
feature_branch = {'rev1': [NULL_REVISION],
 
108
                  'rev2b': ['rev1'], 'rev3b': ['rev2b']}
 
109
 
 
110
 
 
111
# History shortcut
 
112
#  NULL_REVISION
 
113
#       |
 
114
#     rev1------
 
115
#     /  \      \
 
116
#  rev2a rev2b rev2c
 
117
#    |  /   \   /
 
118
#  rev3a    reveb
 
119
history_shortcut = {'rev1': [NULL_REVISION], 'rev2a': ['rev1'],
 
120
                    'rev2b': ['rev1'], 'rev2c': ['rev1'],
 
121
                    'rev3a': ['rev2a', 'rev2b'], 'rev3b': ['rev2b', 'rev2c']}
 
122
 
 
123
 
 
124
class TestGraph(TestCaseWithMemoryTransport):
 
125
 
 
126
    def make_graph(self, ancestors):
 
127
        tree = self.prepare_memory_tree('.')
 
128
        self.build_ancestry(tree, ancestors)
 
129
        tree.unlock()
 
130
        return tree.branch.repository.get_graph()
 
131
 
 
132
    def prepare_memory_tree(self, location):
 
133
        tree = self.make_branch_and_memory_tree(location)
 
134
        tree.lock_write()
 
135
        tree.add('.')
 
136
        return tree
 
137
 
 
138
    def build_ancestry(self, tree, ancestors):
 
139
        """Create an ancestry as specified by a graph dict
 
140
 
 
141
        :param tree: A tree to use
 
142
        :param ancestors: a dict of {node: [node_parent, ...]}
 
143
        """
 
144
        pending = [NULL_REVISION]
 
145
        descendants = {}
 
146
        for descendant, parents in ancestors.iteritems():
 
147
            for parent in parents:
 
148
                descendants.setdefault(parent, []).append(descendant)
 
149
        while len(pending) > 0:
 
150
            cur_node = pending.pop()
 
151
            for descendant in descendants.get(cur_node, []):
 
152
                if tree.branch.repository.has_revision(descendant):
 
153
                    continue
 
154
                parents = [p for p in ancestors[descendant] if p is not
 
155
                           NULL_REVISION]
 
156
                if len([p for p in parents if not
 
157
                    tree.branch.repository.has_revision(p)]) > 0:
 
158
                    continue
 
159
                tree.set_parent_ids(parents)
 
160
                if len(parents) > 0:
 
161
                    left_parent = parents[0]
 
162
                else:
 
163
                    left_parent = NULL_REVISION
 
164
                tree.branch.set_last_revision_info(
 
165
                    len(tree.branch._lefthand_history(left_parent)),
 
166
                    left_parent)
 
167
                tree.commit(descendant, rev_id=descendant)
 
168
                pending.append(descendant)
 
169
 
 
170
    def test_lca(self):
 
171
        """Test finding least common ancestor.
 
172
 
 
173
        ancestry_1 should always have a single common ancestor
 
174
        """
 
175
        graph = self.make_graph(ancestry_1)
 
176
        self.assertRaises(errors.InvalidRevisionId, graph.find_lca, None)
 
177
        self.assertEqual(set([NULL_REVISION]),
 
178
                         graph.find_lca(NULL_REVISION, NULL_REVISION))
 
179
        self.assertEqual(set([NULL_REVISION]),
 
180
                         graph.find_lca(NULL_REVISION, 'rev1'))
 
181
        self.assertEqual(set(['rev1']), graph.find_lca('rev1', 'rev1'))
 
182
        self.assertEqual(set(['rev1']), graph.find_lca('rev2a', 'rev2b'))
 
183
 
 
184
    def test_lca_criss_cross(self):
 
185
        """Test least-common-ancestor after a criss-cross merge."""
 
186
        graph = self.make_graph(criss_cross)
 
187
        self.assertEqual(set(['rev2a', 'rev2b']),
 
188
                         graph.find_lca('rev3a', 'rev3b'))
 
189
        self.assertEqual(set(['rev2b']),
 
190
                         graph.find_lca('rev3a', 'rev3b', 'rev2b'))
 
191
 
 
192
    def test_lca_shortcut(self):
 
193
        """Test least-common ancestor on this history shortcut"""
 
194
        graph = self.make_graph(history_shortcut)
 
195
        self.assertEqual(set(['rev2b']), graph.find_lca('rev3a', 'rev3b'))
 
196
 
 
197
    def test_recursive_unique_lca(self):
 
198
        """Test finding a unique least common ancestor.
 
199
 
 
200
        ancestry_1 should always have a single common ancestor
 
201
        """
 
202
        graph = self.make_graph(ancestry_1)
 
203
        self.assertEqual(NULL_REVISION,
 
204
                         graph.find_unique_lca(NULL_REVISION, NULL_REVISION))
 
205
        self.assertEqual(NULL_REVISION,
 
206
                         graph.find_unique_lca(NULL_REVISION, 'rev1'))
 
207
        self.assertEqual('rev1', graph.find_unique_lca('rev1', 'rev1'))
 
208
        self.assertEqual('rev1', graph.find_unique_lca('rev2a', 'rev2b'))
 
209
 
 
210
    def test_unique_lca_criss_cross(self):
 
211
        """Ensure we don't pick non-unique lcas in a criss-cross"""
 
212
        graph = self.make_graph(criss_cross)
 
213
        self.assertEqual('rev1', graph.find_unique_lca('rev3a', 'rev3b'))
 
214
 
 
215
    def test_unique_lca_null_revision(self):
 
216
        """Ensure we pick NULL_REVISION when necessary"""
 
217
        graph = self.make_graph(criss_cross2)
 
218
        self.assertEqual('rev1b', graph.find_unique_lca('rev2a', 'rev1b'))
 
219
        self.assertEqual(NULL_REVISION,
 
220
                         graph.find_unique_lca('rev2a', 'rev2b'))
 
221
 
 
222
    def test_unique_lca_null_revision2(self):
 
223
        """Ensure we pick NULL_REVISION when necessary"""
 
224
        graph = self.make_graph(ancestry_2)
 
225
        self.assertEqual(NULL_REVISION,
 
226
                         graph.find_unique_lca('rev4a', 'rev1b'))
 
227
 
 
228
    def test_common_ancestor_two_repos(self):
 
229
        """Ensure we do unique_lca using data from two repos"""
 
230
        mainline_tree = self.prepare_memory_tree('mainline')
 
231
        self.build_ancestry(mainline_tree, mainline)
 
232
        mainline_tree.unlock()
 
233
 
 
234
        # This is cheating, because the revisions in the graph are actually
 
235
        # different revisions, despite having the same revision-id.
 
236
        feature_tree = self.prepare_memory_tree('feature')
 
237
        self.build_ancestry(feature_tree, feature_branch)
 
238
        feature_tree.unlock()
 
239
        graph = mainline_tree.branch.repository.get_graph(
 
240
            feature_tree.branch.repository)
 
241
        self.assertEqual('rev2b', graph.find_unique_lca('rev2a', 'rev3b'))
 
242
 
 
243
    def test_graph_difference(self):
 
244
        graph = self.make_graph(ancestry_1)
 
245
        self.assertEqual((set(), set()), graph.find_difference('rev1', 'rev1'))
 
246
        self.assertEqual((set(), set(['rev1'])),
 
247
                         graph.find_difference(NULL_REVISION, 'rev1'))
 
248
        self.assertEqual((set(['rev1']), set()),
 
249
                         graph.find_difference('rev1', NULL_REVISION))
 
250
        self.assertEqual((set(['rev2a', 'rev3']), set(['rev2b'])),
 
251
                         graph.find_difference('rev3', 'rev2b'))
 
252
        self.assertEqual((set(['rev4', 'rev3', 'rev2a']), set()),
 
253
                         graph.find_difference('rev4', 'rev2b'))
 
254
 
 
255
    def test_graph_difference_criss_cross(self):
 
256
        graph = self.make_graph(criss_cross)
 
257
        self.assertEqual((set(['rev3a']), set(['rev3b'])),
 
258
                         graph.find_difference('rev3a', 'rev3b'))
 
259
        self.assertEqual((set([]), set(['rev3b', 'rev2b'])),
 
260
                         graph.find_difference('rev2a', 'rev3b'))
 
261
 
 
262
    def test_stacked_parents_provider(self):
 
263
 
 
264
        class ParentsProvider(object):
 
265
 
 
266
            def __init__(self, ancestry):
 
267
                self.ancestry = ancestry
 
268
 
 
269
            def get_parents(self, revisions):
 
270
                return [self.ancestry.get(r, None) for r in revisions]
 
271
 
 
272
        parents1 = ParentsProvider({'rev2': ['rev3']})
 
273
        parents2 = ParentsProvider({'rev1': ['rev4']})
 
274
        stacked = graph._StackedParentsProvider([parents1, parents2])
 
275
        self.assertEqual([['rev4',], ['rev3']],
 
276
                         stacked.get_parents(['rev1', 'rev2']))
 
277
        self.assertEqual([['rev3',], ['rev4']],
 
278
                         stacked.get_parents(['rev2', 'rev1']))
 
279
        self.assertEqual([['rev3',], ['rev3']],
 
280
                         stacked.get_parents(['rev2', 'rev2']))
 
281
        self.assertEqual([['rev4',], ['rev4']],
 
282
                         stacked.get_parents(['rev1', 'rev1']))
 
283
 
 
284
    def test_iter_topo_order(self):
 
285
        graph = self.make_graph(ancestry_1)
 
286
        args = ['rev2a', 'rev3', 'rev1']
 
287
        topo_args = list(graph.iter_topo_order(args))
 
288
        self.assertEqual(set(args), set(topo_args))
 
289
        self.assertTrue(topo_args.index('rev2a') > topo_args.index('rev1'))
 
290
        self.assertTrue(topo_args.index('rev2a') < topo_args.index('rev3'))