~ubuntu-branches/ubuntu/precise/dulwich/precise-security
» Revision
1.2.16
: dulwich/tests/test_walk.py
« back to all changes in this revision
Viewing changes to dulwich/tests/test_walk.py
- browse files at revision 1.2.16
- compare with another revision
- download diff
- download tarball
- view history from revision 1.2.16
- Committer: Bazaar Package Importer
- Author(s): Jelmer Vernooij
- Date: 2011-08-07 15:03:44 UTC
- mto: This revision was merged to the branch mainline in revision 25.
- Revision ID: james.westby@ubuntu.com-20110807150344-94xw3o3hnh47y1m8
Tags: upstream-0.8.0
Import upstream version 0.8.0
- files added:
- dulwich/tests/test_utils.py
- files modified:
- NEWS
added
removed
dulwich/tests/test_walk.py
1
# test_walk.py -- Tests for commit walking functionality.
2
# Copyright (C) 2010 Google, Inc.
3
#
4
# This program is free software; you can redistribute it and/or
5
# modify it under the terms of the GNU General Public License
6
# as published by the Free Software Foundation; version 2
7
# or (at your option) any later version of the License.
8
#
9
# This program is distributed in the hope that it will be useful,
10
# but WITHOUT ANY WARRANTY; without even the implied warranty of
11
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12
# GNU General Public License for more details.
13
#
14
# You should have received a copy of the GNU General Public License
15
# along with this program; if not, write to the Free Software
16
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
17
# MA 02110-1301, USA.
18
19
"""Tests for commit walking functionality."""
20
21
from dulwich._compat import (
22
permutations,
23
)
24
from dulwich.diff_tree import (
25
CHANGE_ADD,
26
CHANGE_MODIFY,
27
CHANGE_RENAME,
28
CHANGE_COPY,
29
TreeChange,
30
RenameDetector,
31
)
32
from dulwich.errors import (
33
MissingCommitError,
34
)
35
from dulwich.object_store import (
36
MemoryObjectStore,
37
)
38
from dulwich.objects import (
39
Commit,
40
Blob,
41
)
42
from dulwich.walk import (
43
ORDER_TOPO,
44
WalkEntry,
45
Walker,
46
_topo_reorder
47
)
48
from dulwich.tests import TestCase
49
from utils import (
50
F,
51
make_object,
52
build_commit_graph,
53
)
54
55
56
class TestWalkEntry(object):
57
58
def __init__(self, commit, changes):
59
self.commit = commit
60
self.changes = changes
61
62
def __repr__(self):
63
return '<TestWalkEntry commit=%s, changes=%r>' % (
64
self.commit.id, self.changes)
65
66
def __eq__(self, other):
67
if not isinstance(other, WalkEntry) or self.commit != other.commit:
68
return False
69
if self.changes is None:
70
return True
71
return self.changes == other.changes()
72
73
74
class WalkerTest(TestCase):
75
76
def setUp(self):
77
self.store = MemoryObjectStore()
78
79
def make_commits(self, commit_spec, **kwargs):
80
times = kwargs.pop('times', [])
81
attrs = kwargs.pop('attrs', {})
82
for i, t in enumerate(times):
83
attrs.setdefault(i + 1, {})['commit_time'] = t
84
return build_commit_graph(self.store, commit_spec, attrs=attrs,
85
**kwargs)
86
87
def make_linear_commits(self, num_commits, **kwargs):
88
commit_spec = []
89
for i in xrange(1, num_commits + 1):
90
c = [i]
91
if i > 1:
92
c.append(i - 1)
93
commit_spec.append(c)
94
return self.make_commits(commit_spec, **kwargs)
95
96
def assertWalkYields(self, expected, *args, **kwargs):
97
walker = Walker(self.store, *args, **kwargs)
98
expected = list(expected)
99
for i, entry in enumerate(expected):
100
if isinstance(entry, Commit):
101
expected[i] = TestWalkEntry(entry, None)
102
actual = list(walker)
103
self.assertEqual(expected, actual)
104
105
def test_linear(self):
106
c1, c2, c3 = self.make_linear_commits(3)
107
self.assertWalkYields([c1], [c1.id])
108
self.assertWalkYields([c2, c1], [c2.id])
109
self.assertWalkYields([c3, c2, c1], [c3.id])
110
self.assertWalkYields([c3, c2, c1], [c3.id, c1.id])
111
self.assertWalkYields([c3, c2], [c3.id], exclude=[c1.id])
112
self.assertWalkYields([c3, c2], [c3.id, c1.id], exclude=[c1.id])
113
self.assertWalkYields([c3], [c3.id, c1.id], exclude=[c2.id])
114
115
def test_missing(self):
116
cs = list(reversed(self.make_linear_commits(20)))
117
self.assertWalkYields(cs, [cs[0].id])
118
119
# Exactly how close we can get to a missing commit depends on our
120
# implementation (in particular the choice of _MAX_EXTRA_COMMITS), but
121
# we should at least be able to walk some history in a broken repo.
122
del self.store[cs[-1].id]
123
for i in xrange(1, 11):
124
self.assertWalkYields(cs[:i], [cs[0].id], max_entries=i)
125
self.assertRaises(MissingCommitError, Walker, self.store, cs[0].id)
126
127
def test_branch(self):
128
c1, x2, x3, y4 = self.make_commits([[1], [2, 1], [3, 2], [4, 1]])
129
self.assertWalkYields([x3, x2, c1], [x3.id])
130
self.assertWalkYields([y4, c1], [y4.id])
131
self.assertWalkYields([y4, x2, c1], [y4.id, x2.id])
132
self.assertWalkYields([y4, x2], [y4.id, x2.id], exclude=[c1.id])
133
self.assertWalkYields([y4, x3], [y4.id, x3.id], exclude=[x2.id])
134
self.assertWalkYields([y4], [y4.id], exclude=[x3.id])
135
self.assertWalkYields([x3, x2], [x3.id], exclude=[y4.id])
136
137
def test_merge(self):
138
c1, c2, c3, c4 = self.make_commits([[1], [2, 1], [3, 1], [4, 2, 3]])
139
self.assertWalkYields([c4, c3, c2, c1], [c4.id])
140
self.assertWalkYields([c3, c1], [c3.id])
141
self.assertWalkYields([c2, c1], [c2.id])
142
self.assertWalkYields([c4, c3], [c4.id], exclude=[c2.id])
143
self.assertWalkYields([c4, c2], [c4.id], exclude=[c3.id])
144
145
def test_reverse(self):
146
c1, c2, c3 = self.make_linear_commits(3)
147
self.assertWalkYields([c1, c2, c3], [c3.id], reverse=True)
148
149
def test_max_entries(self):
150
c1, c2, c3 = self.make_linear_commits(3)
151
self.assertWalkYields([c3, c2, c1], [c3.id], max_entries=3)
152
self.assertWalkYields([c3, c2], [c3.id], max_entries=2)
153
self.assertWalkYields([c3], [c3.id], max_entries=1)
154
155
def test_reverse_after_max_entries(self):
156
c1, c2, c3 = self.make_linear_commits(3)
157
self.assertWalkYields([c1, c2, c3], [c3.id], max_entries=3,
158
reverse=True)
159
self.assertWalkYields([c2, c3], [c3.id], max_entries=2, reverse=True)
160
self.assertWalkYields([c3], [c3.id], max_entries=1, reverse=True)
161
162
def test_changes_one_parent(self):
163
blob_a1 = make_object(Blob, data='a1')
164
blob_a2 = make_object(Blob, data='a2')
165
blob_b2 = make_object(Blob, data='b2')
166
c1, c2 = self.make_linear_commits(
167
2, trees={1: [('a', blob_a1)],
168
2: [('a', blob_a2), ('b', blob_b2)]})
169
e1 = TestWalkEntry(c1, [TreeChange.add(('a', F, blob_a1.id))])
170
e2 = TestWalkEntry(c2, [TreeChange(CHANGE_MODIFY, ('a', F, blob_a1.id),
171
('a', F, blob_a2.id)),
172
TreeChange.add(('b', F, blob_b2.id))])
173
self.assertWalkYields([e2, e1], [c2.id])
174
175
def test_changes_multiple_parents(self):
176
blob_a1 = make_object(Blob, data='a1')
177
blob_b2 = make_object(Blob, data='b2')
178
blob_a3 = make_object(Blob, data='a3')
179
c1, c2, c3 = self.make_commits(
180
[[1], [2], [3, 1, 2]],
181
trees={1: [('a', blob_a1)], 2: [('b', blob_b2)],
182
3: [('a', blob_a3), ('b', blob_b2)]})
183
# a is a modify/add conflict and b is not conflicted.
184
changes = [[
185
TreeChange(CHANGE_MODIFY, ('a', F, blob_a1.id), ('a', F, blob_a3.id)),
186
TreeChange.add(('a', F, blob_a3.id)),
187
]]
188
self.assertWalkYields([TestWalkEntry(c3, changes)], [c3.id],
189
exclude=[c1.id, c2.id])
190
191
def test_path_matches(self):
192
walker = Walker(None, [], paths=['foo', 'bar', 'baz/quux'])
193
self.assertTrue(walker._path_matches('foo'))
194
self.assertTrue(walker._path_matches('foo/a'))
195
self.assertTrue(walker._path_matches('foo/a/b'))
196
self.assertTrue(walker._path_matches('bar'))
197
self.assertTrue(walker._path_matches('baz/quux'))
198
self.assertTrue(walker._path_matches('baz/quux/a'))
199
200
self.assertFalse(walker._path_matches(None))
201
self.assertFalse(walker._path_matches('oops'))
202
self.assertFalse(walker._path_matches('fool'))
203
self.assertFalse(walker._path_matches('baz'))
204
self.assertFalse(walker._path_matches('baz/quu'))
205
206
def test_paths(self):
207
blob_a1 = make_object(Blob, data='a1')
208
blob_b2 = make_object(Blob, data='b2')
209
blob_a3 = make_object(Blob, data='a3')
210
blob_b3 = make_object(Blob, data='b3')
211
c1, c2, c3 = self.make_linear_commits(
212
3, trees={1: [('a', blob_a1)],
213
2: [('a', blob_a1), ('x/b', blob_b2)],
214
3: [('a', blob_a3), ('x/b', blob_b3)]})
215
216
self.assertWalkYields([c3, c2, c1], [c3.id])
217
self.assertWalkYields([c3, c1], [c3.id], paths=['a'])
218
self.assertWalkYields([c3, c2], [c3.id], paths=['x/b'])
219
220
# All changes are included, not just for requested paths.
221
changes = [
222
TreeChange(CHANGE_MODIFY, ('a', F, blob_a1.id),
223
('a', F, blob_a3.id)),
224
TreeChange(CHANGE_MODIFY, ('x/b', F, blob_b2.id),
225
('x/b', F, blob_b3.id)),
226
]
227
self.assertWalkYields([TestWalkEntry(c3, changes)], [c3.id],
228
max_entries=1, paths=['a'])
229
230
def test_paths_subtree(self):
231
blob_a = make_object(Blob, data='a')
232
blob_b = make_object(Blob, data='b')
233
c1, c2, c3 = self.make_linear_commits(
234
3, trees={1: [('x/a', blob_a)],
235
2: [('b', blob_b), ('x/a', blob_a)],
236
3: [('b', blob_b), ('x/a', blob_a), ('x/b', blob_b)]})
237
self.assertWalkYields([c2], [c3.id], paths=['b'])
238
self.assertWalkYields([c3, c1], [c3.id], paths=['x'])
239
240
def test_paths_max_entries(self):
241
blob_a = make_object(Blob, data='a')
242
blob_b = make_object(Blob, data='b')
243
c1, c2 = self.make_linear_commits(
244
2, trees={1: [('a', blob_a)],
245
2: [('a', blob_a), ('b', blob_b)]})
246
self.assertWalkYields([c2], [c2.id], paths=['b'], max_entries=1)
247
self.assertWalkYields([c1], [c1.id], paths=['a'], max_entries=1)
248
249
def test_paths_merge(self):
250
blob_a1 = make_object(Blob, data='a1')
251
blob_a2 = make_object(Blob, data='a2')
252
blob_a3 = make_object(Blob, data='a3')
253
x1, y2, m3, m4 = self.make_commits(
254
[[1], [2], [3, 1, 2], [4, 1, 2]],
255
trees={1: [('a', blob_a1)],
256
2: [('a', blob_a2)],
257
3: [('a', blob_a3)],
258
4: [('a', blob_a1)]}) # Non-conflicting
259
self.assertWalkYields([m3, y2, x1], [m3.id], paths=['a'])
260
self.assertWalkYields([y2, x1], [m4.id], paths=['a'])
261
262
def test_changes_with_renames(self):
263
blob = make_object(Blob, data='blob')
264
c1, c2 = self.make_linear_commits(
265
2, trees={1: [('a', blob)], 2: [('b', blob)]})
266
entry_a = ('a', F, blob.id)
267
entry_b = ('b', F, blob.id)
268
changes_without_renames = [TreeChange.delete(entry_a),
269
TreeChange.add(entry_b)]
270
changes_with_renames = [TreeChange(CHANGE_RENAME, entry_a, entry_b)]
271
self.assertWalkYields(
272
[TestWalkEntry(c2, changes_without_renames)], [c2.id], max_entries=1)
273
detector = RenameDetector(self.store)
274
self.assertWalkYields(
275
[TestWalkEntry(c2, changes_with_renames)], [c2.id], max_entries=1,
276
rename_detector=detector)
277
278
def test_follow_rename(self):
279
blob = make_object(Blob, data='blob')
280
names = ['a', 'a', 'b', 'b', 'c', 'c']
281
282
trees = dict((i + 1, [(n, blob, F)]) for i, n in enumerate(names))
283
c1, c2, c3, c4, c5, c6 = self.make_linear_commits(6, trees=trees)
284
self.assertWalkYields([c5], [c6.id], paths=['c'])
285
286
e = lambda n: (n, F, blob.id)
287
self.assertWalkYields(
288
[TestWalkEntry(c5, [TreeChange(CHANGE_RENAME, e('b'), e('c'))]),
289
TestWalkEntry(c3, [TreeChange(CHANGE_RENAME, e('a'), e('b'))]),
290
TestWalkEntry(c1, [TreeChange.add(e('a'))])],
291
[c6.id], paths=['c'], follow=True)
292
293
def test_follow_rename_remove_path(self):
294
blob = make_object(Blob, data='blob')
295
_, _, _, c4, c5, c6 = self.make_linear_commits(
296
6, trees={1: [('a', blob), ('c', blob)],
297
2: [],
298
3: [],
299
4: [('b', blob)],
300
5: [('a', blob)],
301
6: [('c', blob)]})
302
303
e = lambda n: (n, F, blob.id)
304
# Once the path changes to b, we aren't interested in a or c anymore.
305
self.assertWalkYields(
306
[TestWalkEntry(c6, [TreeChange(CHANGE_RENAME, e('a'), e('c'))]),
307
TestWalkEntry(c5, [TreeChange(CHANGE_RENAME, e('b'), e('a'))]),
308
TestWalkEntry(c4, [TreeChange.add(e('b'))])],
309
[c6.id], paths=['c'], follow=True)
310
311
def test_since(self):
312
c1, c2, c3 = self.make_linear_commits(3)
313
self.assertWalkYields([c3, c2, c1], [c3.id], since=-1)
314
self.assertWalkYields([c3, c2, c1], [c3.id], since=0)
315
self.assertWalkYields([c3, c2], [c3.id], since=1)
316
self.assertWalkYields([c3, c2], [c3.id], since=99)
317
self.assertWalkYields([c3, c2], [c3.id], since=100)
318
self.assertWalkYields([c3], [c3.id], since=101)
319
self.assertWalkYields([c3], [c3.id], since=199)
320
self.assertWalkYields([c3], [c3.id], since=200)
321
self.assertWalkYields([], [c3.id], since=201)
322
self.assertWalkYields([], [c3.id], since=300)
323
324
def test_until(self):
325
c1, c2, c3 = self.make_linear_commits(3)
326
self.assertWalkYields([], [c3.id], until=-1)
327
self.assertWalkYields([c1], [c3.id], until=0)
328
self.assertWalkYields([c1], [c3.id], until=1)
329
self.assertWalkYields([c1], [c3.id], until=99)
330
self.assertWalkYields([c2, c1], [c3.id], until=100)
331
self.assertWalkYields([c2, c1], [c3.id], until=101)
332
self.assertWalkYields([c2, c1], [c3.id], until=199)
333
self.assertWalkYields([c3, c2, c1], [c3.id], until=200)
334
self.assertWalkYields([c3, c2, c1], [c3.id], until=201)
335
self.assertWalkYields([c3, c2, c1], [c3.id], until=300)
336
337
def test_since_until(self):
338
c1, c2, c3 = self.make_linear_commits(3)
339
self.assertWalkYields([], [c3.id], since=100, until=99)
340
self.assertWalkYields([c3, c2, c1], [c3.id], since=-1, until=201)
341
self.assertWalkYields([c2], [c3.id], since=100, until=100)
342
self.assertWalkYields([c2], [c3.id], since=50, until=150)
343
344
def test_since_over_scan(self):
345
commits = self.make_linear_commits(
346
11, times=[9, 0, 1, 2, 3, 4, 5, 8, 6, 7, 9])
347
c8, _, c10, c11 = commits[-4:]
348
del self.store[commits[0].id]
349
# c9 is older than we want to walk, but is out of order with its parent,
350
# so we need to walk past it to get to c8.
351
# c1 would also match, but we've deleted it, and it should get pruned
352
# even with over-scanning.
353
self.assertWalkYields([c11, c10, c8], [c11.id], since=7)
354
355
def assertTopoOrderEqual(self, expected_commits, commits):
356
entries = [TestWalkEntry(c, None) for c in commits]
357
actual_ids = [e.commit.id for e in list(_topo_reorder(entries))]
358
self.assertEqual([c.id for c in expected_commits], actual_ids)
359
360
def test_topo_reorder_linear(self):
361
commits = self.make_linear_commits(5)
362
commits.reverse()
363
for perm in permutations(commits):
364
self.assertTopoOrderEqual(commits, perm)
365
366
def test_topo_reorder_multiple_parents(self):
367
c1, c2, c3 = self.make_commits([[1], [2], [3, 1, 2]])
368
# Already sorted, so totally FIFO.
369
self.assertTopoOrderEqual([c3, c2, c1], [c3, c2, c1])
370
self.assertTopoOrderEqual([c3, c1, c2], [c3, c1, c2])
371
372
# c3 causes one parent to be yielded.
373
self.assertTopoOrderEqual([c3, c2, c1], [c2, c3, c1])
374
self.assertTopoOrderEqual([c3, c1, c2], [c1, c3, c2])
375
376
# c3 causes both parents to be yielded.
377
self.assertTopoOrderEqual([c3, c2, c1], [c1, c2, c3])
378
self.assertTopoOrderEqual([c3, c2, c1], [c2, c1, c3])
379
380
def test_topo_reorder_multiple_children(self):
381
c1, c2, c3 = self.make_commits([[1], [2, 1], [3, 1]])
382
383
# c2 and c3 are FIFO but c1 moves to the end.
384
self.assertTopoOrderEqual([c3, c2, c1], [c3, c2, c1])
385
self.assertTopoOrderEqual([c3, c2, c1], [c3, c1, c2])
386
self.assertTopoOrderEqual([c3, c2, c1], [c1, c3, c2])
387
388
self.assertTopoOrderEqual([c2, c3, c1], [c2, c3, c1])
389
self.assertTopoOrderEqual([c2, c3, c1], [c2, c1, c3])
390
self.assertTopoOrderEqual([c2, c3, c1], [c1, c2, c3])
391
392
def test_out_of_order_children(self):
393
c1, c2, c3, c4, c5 = self.make_commits(
394
[[1], [2, 1], [3, 2], [4, 1], [5, 3, 4]],
395
times=[2, 1, 3, 4, 5])
396
self.assertWalkYields([c5, c4, c3, c1, c2], [c5.id])
397
self.assertWalkYields([c5, c4, c3, c2, c1], [c5.id], order=ORDER_TOPO)
398
399
def test_out_of_order_with_exclude(self):
400
# Create the following graph:
401
# c1-------x2---m6
402
# \ /
403
# \-y3--y4-/--y5
404
# Due to skew, y5 is the oldest commit.
405
c1, x2, y3, y4, y5, m6 = cs = self.make_commits(
406
[[1], [2, 1], [3, 1], [4, 3], [5, 4], [6, 2, 4]],
407
times=[2, 3, 4, 5, 1, 6])
408
self.assertWalkYields([m6, y4, y3, x2, c1], [m6.id])
409
# Ensure that c1..y4 get excluded even though they're popped from the
410
# priority queue long before y5.
411
self.assertWalkYields([m6, x2], [m6.id], exclude=[y5.id])
Loggerhead is a web-based interface for Breezy
Version: 2.0.1