Show More
@@ -1,100 +1,99 b'' | |||||
1 | # Randomized torture test generation for bdiff |
|
1 | # Randomized torture test generation for bdiff | |
2 |
|
2 | |||
3 | from __future__ import absolute_import, print_function |
|
3 | from __future__ import absolute_import, print_function | |
4 | import random |
|
4 | import random | |
5 | import sys |
|
5 | import sys | |
6 |
|
6 | |||
7 | from mercurial import ( |
|
7 | from mercurial import ( | |
8 | mdiff, |
|
8 | mdiff, | |
9 | mpatch, |
|
|||
10 | ) |
|
9 | ) | |
11 |
|
10 | |||
12 | def reducetest(a, b): |
|
11 | def reducetest(a, b): | |
13 | tries = 0 |
|
12 | tries = 0 | |
14 | reductions = 0 |
|
13 | reductions = 0 | |
15 | print("reducing...") |
|
14 | print("reducing...") | |
16 | while tries < 1000: |
|
15 | while tries < 1000: | |
17 | a2 = "\n".join(l for l in a.splitlines() |
|
16 | a2 = "\n".join(l for l in a.splitlines() | |
18 | if random.randint(0, 100) > 0) + "\n" |
|
17 | if random.randint(0, 100) > 0) + "\n" | |
19 | b2 = "\n".join(l for l in b.splitlines() |
|
18 | b2 = "\n".join(l for l in b.splitlines() | |
20 | if random.randint(0, 100) > 0) + "\n" |
|
19 | if random.randint(0, 100) > 0) + "\n" | |
21 | if a2 == a and b2 == b: |
|
20 | if a2 == a and b2 == b: | |
22 | continue |
|
21 | continue | |
23 | if a2 == b2: |
|
22 | if a2 == b2: | |
24 | continue |
|
23 | continue | |
25 | tries += 1 |
|
24 | tries += 1 | |
26 |
|
25 | |||
27 | try: |
|
26 | try: | |
28 | test1(a, b) |
|
27 | test1(a, b) | |
29 | except Exception as inst: |
|
28 | except Exception as inst: | |
30 | reductions += 1 |
|
29 | reductions += 1 | |
31 | tries = 0 |
|
30 | tries = 0 | |
32 | a = a2 |
|
31 | a = a2 | |
33 | b = b2 |
|
32 | b = b2 | |
34 |
|
33 | |||
35 | print("reduced:", reductions, len(a) + len(b), |
|
34 | print("reduced:", reductions, len(a) + len(b), | |
36 | repr(a), repr(b)) |
|
35 | repr(a), repr(b)) | |
37 | try: |
|
36 | try: | |
38 | test1(a, b) |
|
37 | test1(a, b) | |
39 | except Exception as inst: |
|
38 | except Exception as inst: | |
40 | print("failed:", inst) |
|
39 | print("failed:", inst) | |
41 |
|
40 | |||
42 | sys.exit(0) |
|
41 | sys.exit(0) | |
43 |
|
42 | |||
44 | def test1(a, b): |
|
43 | def test1(a, b): | |
45 | d = mdiff.textdiff(a, b) |
|
44 | d = mdiff.textdiff(a, b) | |
46 | if not d: |
|
45 | if not d: | |
47 | raise ValueError("empty") |
|
46 | raise ValueError("empty") | |
48 |
c = m |
|
47 | c = mdiff.patches(a, [d]) | |
49 | if c != b: |
|
48 | if c != b: | |
50 | raise ValueError("bad") |
|
49 | raise ValueError("bad") | |
51 |
|
50 | |||
52 | def testwrap(a, b): |
|
51 | def testwrap(a, b): | |
53 | try: |
|
52 | try: | |
54 | test1(a, b) |
|
53 | test1(a, b) | |
55 | return |
|
54 | return | |
56 | except Exception as inst: |
|
55 | except Exception as inst: | |
57 | pass |
|
56 | pass | |
58 | print("exception:", inst) |
|
57 | print("exception:", inst) | |
59 | reducetest(a, b) |
|
58 | reducetest(a, b) | |
60 |
|
59 | |||
61 | def test(a, b): |
|
60 | def test(a, b): | |
62 | testwrap(a, b) |
|
61 | testwrap(a, b) | |
63 | testwrap(b, a) |
|
62 | testwrap(b, a) | |
64 |
|
63 | |||
65 | def rndtest(size, noise): |
|
64 | def rndtest(size, noise): | |
66 | a = [] |
|
65 | a = [] | |
67 | src = " aaaaaaaabbbbccd" |
|
66 | src = " aaaaaaaabbbbccd" | |
68 | for x in xrange(size): |
|
67 | for x in xrange(size): | |
69 | a.append(src[random.randint(0, len(src) - 1)]) |
|
68 | a.append(src[random.randint(0, len(src) - 1)]) | |
70 |
|
69 | |||
71 | while True: |
|
70 | while True: | |
72 | b = [c for c in a if random.randint(0, 99) > noise] |
|
71 | b = [c for c in a if random.randint(0, 99) > noise] | |
73 | b2 = [] |
|
72 | b2 = [] | |
74 | for c in b: |
|
73 | for c in b: | |
75 | b2.append(c) |
|
74 | b2.append(c) | |
76 | while random.randint(0, 99) < noise: |
|
75 | while random.randint(0, 99) < noise: | |
77 | b2.append(src[random.randint(0, len(src) - 1)]) |
|
76 | b2.append(src[random.randint(0, len(src) - 1)]) | |
78 | if b2 != a: |
|
77 | if b2 != a: | |
79 | break |
|
78 | break | |
80 |
|
79 | |||
81 | a = "\n".join(a) + "\n" |
|
80 | a = "\n".join(a) + "\n" | |
82 | b = "\n".join(b2) + "\n" |
|
81 | b = "\n".join(b2) + "\n" | |
83 |
|
82 | |||
84 | test(a, b) |
|
83 | test(a, b) | |
85 |
|
84 | |||
86 | maxvol = 10000 |
|
85 | maxvol = 10000 | |
87 | startsize = 2 |
|
86 | startsize = 2 | |
88 | while True: |
|
87 | while True: | |
89 | size = startsize |
|
88 | size = startsize | |
90 | count = 0 |
|
89 | count = 0 | |
91 | while size < maxvol: |
|
90 | while size < maxvol: | |
92 | print(size) |
|
91 | print(size) | |
93 | volume = 0 |
|
92 | volume = 0 | |
94 | while volume < maxvol: |
|
93 | while volume < maxvol: | |
95 | rndtest(size, 2) |
|
94 | rndtest(size, 2) | |
96 | volume += size |
|
95 | volume += size | |
97 | count += 2 |
|
96 | count += 2 | |
98 | size *= 2 |
|
97 | size *= 2 | |
99 | maxvol *= 4 |
|
98 | maxvol *= 4 | |
100 | startsize *= 4 |
|
99 | startsize *= 4 |
@@ -1,150 +1,149 b'' | |||||
1 | from __future__ import absolute_import, print_function |
|
1 | from __future__ import absolute_import, print_function | |
2 | import collections |
|
2 | import collections | |
3 | import struct |
|
3 | import struct | |
4 | import unittest |
|
4 | import unittest | |
5 |
|
5 | |||
6 | from mercurial import ( |
|
6 | from mercurial import ( | |
7 | mdiff, |
|
7 | mdiff, | |
8 | mpatch, |
|
|||
9 | ) |
|
8 | ) | |
10 |
|
9 | |||
11 | class diffreplace( |
|
10 | class diffreplace( | |
12 | collections.namedtuple('diffreplace', 'start end from_ to')): |
|
11 | collections.namedtuple('diffreplace', 'start end from_ to')): | |
13 | def __repr__(self): |
|
12 | def __repr__(self): | |
14 | return 'diffreplace(%r, %r, %r, %r)' % self |
|
13 | return 'diffreplace(%r, %r, %r, %r)' % self | |
15 |
|
14 | |||
16 | class BdiffTests(unittest.TestCase): |
|
15 | class BdiffTests(unittest.TestCase): | |
17 |
|
16 | |||
18 | def assert_bdiff_applies(self, a, b): |
|
17 | def assert_bdiff_applies(self, a, b): | |
19 | d = mdiff.textdiff(a, b) |
|
18 | d = mdiff.textdiff(a, b) | |
20 | c = a |
|
19 | c = a | |
21 | if d: |
|
20 | if d: | |
22 |
c = m |
|
21 | c = mdiff.patches(a, [d]) | |
23 | self.assertEqual( |
|
22 | self.assertEqual( | |
24 | c, b, ("bad diff+patch result from\n %r to\n " |
|
23 | c, b, ("bad diff+patch result from\n %r to\n " | |
25 | "%r: \nbdiff: %r\npatched: %r" % (a, b, d, c[:200]))) |
|
24 | "%r: \nbdiff: %r\npatched: %r" % (a, b, d, c[:200]))) | |
26 |
|
25 | |||
27 | def assert_bdiff(self, a, b): |
|
26 | def assert_bdiff(self, a, b): | |
28 | self.assert_bdiff_applies(a, b) |
|
27 | self.assert_bdiff_applies(a, b) | |
29 | self.assert_bdiff_applies(b, a) |
|
28 | self.assert_bdiff_applies(b, a) | |
30 |
|
29 | |||
31 | def test_bdiff_basic(self): |
|
30 | def test_bdiff_basic(self): | |
32 | cases = [ |
|
31 | cases = [ | |
33 | ("a\nc\n\n\n\n", "a\nb\n\n\n"), |
|
32 | ("a\nc\n\n\n\n", "a\nb\n\n\n"), | |
34 | ("a\nb\nc\n", "a\nc\n"), |
|
33 | ("a\nb\nc\n", "a\nc\n"), | |
35 | ("", ""), |
|
34 | ("", ""), | |
36 | ("a\nb\nc", "a\nb\nc"), |
|
35 | ("a\nb\nc", "a\nb\nc"), | |
37 | ("a\nb\nc\nd\n", "a\nd\n"), |
|
36 | ("a\nb\nc\nd\n", "a\nd\n"), | |
38 | ("a\nb\nc\nd\n", "a\nc\ne\n"), |
|
37 | ("a\nb\nc\nd\n", "a\nc\ne\n"), | |
39 | ("a\nb\nc\n", "a\nc\n"), |
|
38 | ("a\nb\nc\n", "a\nc\n"), | |
40 | ("a\n", "c\na\nb\n"), |
|
39 | ("a\n", "c\na\nb\n"), | |
41 | ("a\n", ""), |
|
40 | ("a\n", ""), | |
42 | ("a\n", "b\nc\n"), |
|
41 | ("a\n", "b\nc\n"), | |
43 | ("a\n", "c\na\n"), |
|
42 | ("a\n", "c\na\n"), | |
44 | ("", "adjfkjdjksdhfksj"), |
|
43 | ("", "adjfkjdjksdhfksj"), | |
45 | ("", "ab"), |
|
44 | ("", "ab"), | |
46 | ("", "abc"), |
|
45 | ("", "abc"), | |
47 | ("a", "a"), |
|
46 | ("a", "a"), | |
48 | ("ab", "ab"), |
|
47 | ("ab", "ab"), | |
49 | ("abc", "abc"), |
|
48 | ("abc", "abc"), | |
50 | ("a\n", "a\n"), |
|
49 | ("a\n", "a\n"), | |
51 | ("a\nb", "a\nb"), |
|
50 | ("a\nb", "a\nb"), | |
52 | ] |
|
51 | ] | |
53 | for a, b in cases: |
|
52 | for a, b in cases: | |
54 | self.assert_bdiff(a, b) |
|
53 | self.assert_bdiff(a, b) | |
55 |
|
54 | |||
56 | def showdiff(self, a, b): |
|
55 | def showdiff(self, a, b): | |
57 | bin = mdiff.textdiff(a, b) |
|
56 | bin = mdiff.textdiff(a, b) | |
58 | pos = 0 |
|
57 | pos = 0 | |
59 | q = 0 |
|
58 | q = 0 | |
60 | actions = [] |
|
59 | actions = [] | |
61 | while pos < len(bin): |
|
60 | while pos < len(bin): | |
62 | p1, p2, l = struct.unpack(">lll", bin[pos:pos + 12]) |
|
61 | p1, p2, l = struct.unpack(">lll", bin[pos:pos + 12]) | |
63 | pos += 12 |
|
62 | pos += 12 | |
64 | if p1: |
|
63 | if p1: | |
65 | actions.append(a[q:p1]) |
|
64 | actions.append(a[q:p1]) | |
66 | actions.append(diffreplace(p1, p2, a[p1:p2], bin[pos:pos + l])) |
|
65 | actions.append(diffreplace(p1, p2, a[p1:p2], bin[pos:pos + l])) | |
67 | pos += l |
|
66 | pos += l | |
68 | q = p2 |
|
67 | q = p2 | |
69 | if q < len(a): |
|
68 | if q < len(a): | |
70 | actions.append(a[q:]) |
|
69 | actions.append(a[q:]) | |
71 | return actions |
|
70 | return actions | |
72 |
|
71 | |||
73 | def test_issue1295(self): |
|
72 | def test_issue1295(self): | |
74 | cases = [ |
|
73 | cases = [ | |
75 | ("x\n\nx\n\nx\n\nx\n\nz\n", "x\n\nx\n\ny\n\nx\n\nx\n\nz\n", |
|
74 | ("x\n\nx\n\nx\n\nx\n\nz\n", "x\n\nx\n\ny\n\nx\n\nx\n\nz\n", | |
76 | ['x\n\nx\n\n', diffreplace(6, 6, '', 'y\n\n'), 'x\n\nx\n\nz\n']), |
|
75 | ['x\n\nx\n\n', diffreplace(6, 6, '', 'y\n\n'), 'x\n\nx\n\nz\n']), | |
77 | ("x\n\nx\n\nx\n\nx\n\nz\n", "x\n\nx\n\ny\n\nx\n\ny\n\nx\n\nz\n", |
|
76 | ("x\n\nx\n\nx\n\nx\n\nz\n", "x\n\nx\n\ny\n\nx\n\ny\n\nx\n\nz\n", | |
78 | ['x\n\nx\n\n', |
|
77 | ['x\n\nx\n\n', | |
79 | diffreplace(6, 6, '', 'y\n\n'), |
|
78 | diffreplace(6, 6, '', 'y\n\n'), | |
80 | 'x\n\n', |
|
79 | 'x\n\n', | |
81 | diffreplace(9, 9, '', 'y\n\n'), |
|
80 | diffreplace(9, 9, '', 'y\n\n'), | |
82 | 'x\n\nz\n']), |
|
81 | 'x\n\nz\n']), | |
83 | ] |
|
82 | ] | |
84 | for old, new, want in cases: |
|
83 | for old, new, want in cases: | |
85 | self.assertEqual(self.showdiff(old, new), want) |
|
84 | self.assertEqual(self.showdiff(old, new), want) | |
86 |
|
85 | |||
87 | def test_issue1295_varies_on_pure(self): |
|
86 | def test_issue1295_varies_on_pure(self): | |
88 | # we should pick up abbbc. rather than bc.de as the longest match |
|
87 | # we should pick up abbbc. rather than bc.de as the longest match | |
89 | got = self.showdiff("a\nb\nb\nb\nc\n.\nd\ne\n.\nf\n", |
|
88 | got = self.showdiff("a\nb\nb\nb\nc\n.\nd\ne\n.\nf\n", | |
90 | "a\nb\nb\na\nb\nb\nb\nc\n.\nb\nc\n.\nd\ne\nf\n") |
|
89 | "a\nb\nb\na\nb\nb\nb\nc\n.\nb\nc\n.\nd\ne\nf\n") | |
91 | want_c = ['a\nb\nb\n', |
|
90 | want_c = ['a\nb\nb\n', | |
92 | diffreplace(6, 6, '', 'a\nb\nb\nb\nc\n.\n'), |
|
91 | diffreplace(6, 6, '', 'a\nb\nb\nb\nc\n.\n'), | |
93 | 'b\nc\n.\nd\ne\n', |
|
92 | 'b\nc\n.\nd\ne\n', | |
94 | diffreplace(16, 18, '.\n', ''), |
|
93 | diffreplace(16, 18, '.\n', ''), | |
95 | 'f\n'] |
|
94 | 'f\n'] | |
96 | want_pure = [diffreplace(0, 0, '', 'a\nb\nb\n'), |
|
95 | want_pure = [diffreplace(0, 0, '', 'a\nb\nb\n'), | |
97 | 'a\nb\nb\nb\nc\n.\n', |
|
96 | 'a\nb\nb\nb\nc\n.\n', | |
98 | diffreplace(12, 12, '', 'b\nc\n.\n'), |
|
97 | diffreplace(12, 12, '', 'b\nc\n.\n'), | |
99 | 'd\ne\n', |
|
98 | 'd\ne\n', | |
100 | diffreplace(16, 18, '.\n', ''), 'f\n'] |
|
99 | diffreplace(16, 18, '.\n', ''), 'f\n'] | |
101 | self.assert_(got in (want_c, want_pure), |
|
100 | self.assert_(got in (want_c, want_pure), | |
102 | 'got: %r, wanted either %r or %r' % ( |
|
101 | 'got: %r, wanted either %r or %r' % ( | |
103 | got, want_c, want_pure)) |
|
102 | got, want_c, want_pure)) | |
104 |
|
103 | |||
105 | def test_fixws(self): |
|
104 | def test_fixws(self): | |
106 | cases = [ |
|
105 | cases = [ | |
107 | (" \ta\r b\t\n", "ab\n", 1), |
|
106 | (" \ta\r b\t\n", "ab\n", 1), | |
108 | (" \ta\r b\t\n", " a b\n", 0), |
|
107 | (" \ta\r b\t\n", " a b\n", 0), | |
109 | ("", "", 1), |
|
108 | ("", "", 1), | |
110 | ("", "", 0), |
|
109 | ("", "", 0), | |
111 | ] |
|
110 | ] | |
112 | for a, b, allws in cases: |
|
111 | for a, b, allws in cases: | |
113 | c = mdiff.fixws(a, allws) |
|
112 | c = mdiff.fixws(a, allws) | |
114 | self.assertEqual( |
|
113 | self.assertEqual( | |
115 | c, b, 'fixws(%r) want %r got %r (allws=%r)' % (a, b, c, allws)) |
|
114 | c, b, 'fixws(%r) want %r got %r (allws=%r)' % (a, b, c, allws)) | |
116 |
|
115 | |||
117 | def test_nice_diff_for_trivial_change(self): |
|
116 | def test_nice_diff_for_trivial_change(self): | |
118 | self.assertEqual(self.showdiff( |
|
117 | self.assertEqual(self.showdiff( | |
119 | ''.join('<%s\n-\n' % i for i in range(5)), |
|
118 | ''.join('<%s\n-\n' % i for i in range(5)), | |
120 | ''.join('>%s\n-\n' % i for i in range(5))), |
|
119 | ''.join('>%s\n-\n' % i for i in range(5))), | |
121 | [diffreplace(0, 3, '<0\n', '>0\n'), |
|
120 | [diffreplace(0, 3, '<0\n', '>0\n'), | |
122 | '-\n', |
|
121 | '-\n', | |
123 | diffreplace(5, 8, '<1\n', '>1\n'), |
|
122 | diffreplace(5, 8, '<1\n', '>1\n'), | |
124 | '-\n', |
|
123 | '-\n', | |
125 | diffreplace(10, 13, '<2\n', '>2\n'), |
|
124 | diffreplace(10, 13, '<2\n', '>2\n'), | |
126 | '-\n', |
|
125 | '-\n', | |
127 | diffreplace(15, 18, '<3\n', '>3\n'), |
|
126 | diffreplace(15, 18, '<3\n', '>3\n'), | |
128 | '-\n', |
|
127 | '-\n', | |
129 | diffreplace(20, 23, '<4\n', '>4\n'), |
|
128 | diffreplace(20, 23, '<4\n', '>4\n'), | |
130 | '-\n']) |
|
129 | '-\n']) | |
131 |
|
130 | |||
132 | def test_prefer_appending(self): |
|
131 | def test_prefer_appending(self): | |
133 | # 1 line to 3 lines |
|
132 | # 1 line to 3 lines | |
134 | self.assertEqual(self.showdiff('a\n', 'a\n' * 3), |
|
133 | self.assertEqual(self.showdiff('a\n', 'a\n' * 3), | |
135 | ['a\n', diffreplace(2, 2, '', 'a\na\n')]) |
|
134 | ['a\n', diffreplace(2, 2, '', 'a\na\n')]) | |
136 | # 1 line to 5 lines |
|
135 | # 1 line to 5 lines | |
137 | self.assertEqual(self.showdiff('a\n', 'a\n' * 5), |
|
136 | self.assertEqual(self.showdiff('a\n', 'a\n' * 5), | |
138 | ['a\n', diffreplace(2, 2, '', 'a\na\na\na\n')]) |
|
137 | ['a\n', diffreplace(2, 2, '', 'a\na\na\na\n')]) | |
139 |
|
138 | |||
140 | def test_prefer_removing_trailing(self): |
|
139 | def test_prefer_removing_trailing(self): | |
141 | # 3 lines to 1 line |
|
140 | # 3 lines to 1 line | |
142 | self.assertEqual(self.showdiff('a\n' * 3, 'a\n'), |
|
141 | self.assertEqual(self.showdiff('a\n' * 3, 'a\n'), | |
143 | ['a\n', diffreplace(2, 6, 'a\na\n', '')]) |
|
142 | ['a\n', diffreplace(2, 6, 'a\na\n', '')]) | |
144 | # 5 lines to 1 line |
|
143 | # 5 lines to 1 line | |
145 | self.assertEqual(self.showdiff('a\n' * 5, 'a\n'), |
|
144 | self.assertEqual(self.showdiff('a\n' * 5, 'a\n'), | |
146 | ['a\n', diffreplace(2, 10, 'a\na\na\na\n', '')]) |
|
145 | ['a\n', diffreplace(2, 10, 'a\na\na\na\n', '')]) | |
147 |
|
146 | |||
148 | if __name__ == '__main__': |
|
147 | if __name__ == '__main__': | |
149 | import silenttestrunner |
|
148 | import silenttestrunner | |
150 | silenttestrunner.main(__name__) |
|
149 | silenttestrunner.main(__name__) |
General Comments 0
You need to be logged in to leave comments.
Login now