Mercurial > hg
comparison tests/test-linelog.py @ 38795:422d661056be
linelog: add a Python implementation of the linelog datastructure
This datastructure was originally developed by Jun Wu at Facebook,
inspired by SCCS weaves. It's useful as a cache for blame information,
but also is the magic that makes `hg absorb` easy to implement. In
service of importing the code to Mercurial, I wanted to actually
/understand/ it, and once I did I decided to take a run at
implementing it.
The help/internals/linelog.txt document is the README from Jun Wu's
implementaiton. It all applies to our linelog implementation.
Differential Revision: https://phab.mercurial-scm.org/D3990
author | Augie Fackler <augie@google.com> |
---|---|
date | Mon, 30 Jul 2018 10:42:37 -0400 |
parents | |
children | 57af5ee15b35 |
comparison
equal
deleted
inserted
replaced
38794:1d01cf0416a5 | 38795:422d661056be |
---|---|
1 from __future__ import absolute_import, print_function | |
2 | |
3 import difflib | |
4 import random | |
5 import unittest | |
6 | |
7 from mercurial import linelog | |
8 | |
9 maxlinenum = 0xffffff | |
10 maxb1 = 0xffffff | |
11 maxdeltaa = 10 | |
12 maxdeltab = 10 | |
13 | |
14 def _genedits(seed, endrev): | |
15 lines = [] | |
16 random.seed(seed) | |
17 rev = 0 | |
18 for rev in range(0, endrev): | |
19 n = len(lines) | |
20 a1 = random.randint(0, n) | |
21 a2 = random.randint(a1, min(n, a1 + maxdeltaa)) | |
22 b1 = random.randint(0, maxb1) | |
23 b2 = random.randint(b1, b1 + maxdeltab) | |
24 blines = [(rev, idx) for idx in range(b1, b2)] | |
25 lines[a1:a2] = blines | |
26 yield lines, rev, a1, a2, b1, b2 | |
27 | |
28 class linelogtests(unittest.TestCase): | |
29 def testlinelogencodedecode(self): | |
30 program = [linelog._eof(0, 0), | |
31 linelog._jge(41, 42), | |
32 linelog._jump(0, 43), | |
33 linelog._eof(0, 0), | |
34 linelog._jl(44, 45), | |
35 linelog._line(46, 47), | |
36 ] | |
37 ll = linelog.linelog(program, maxrev=100) | |
38 enc = ll.encode() | |
39 # round-trips okay | |
40 self.assertEqual(linelog.linelog.fromdata(enc)._program, ll._program) | |
41 self.assertEqual(linelog.linelog.fromdata(enc), ll) | |
42 # This encoding matches the encoding used by hg-experimental's | |
43 # linelog file, or is supposed to if it doesn't. | |
44 self.assertEqual(enc, ('\x00\x00\x01\x90\x00\x00\x00\x06' | |
45 '\x00\x00\x00\xa4\x00\x00\x00*' | |
46 '\x00\x00\x00\x00\x00\x00\x00+' | |
47 '\x00\x00\x00\x00\x00\x00\x00\x00' | |
48 '\x00\x00\x00\xb1\x00\x00\x00-' | |
49 '\x00\x00\x00\xba\x00\x00\x00/')) | |
50 | |
51 def testsimpleedits(self): | |
52 ll = linelog.linelog() | |
53 # Initial revision: add lines 0, 1, and 2 | |
54 ll.replacelines(1, 0, 0, 0, 3) | |
55 self.assertEqual([(l.rev, l.linenum) for l in ll.annotate(1)], | |
56 [(1, 0), | |
57 (1, 1), | |
58 (1, 2), | |
59 ]) | |
60 # Replace line 1 with a new line | |
61 ll.replacelines(2, 1, 2, 1, 2) | |
62 self.assertEqual([(l.rev, l.linenum) for l in ll.annotate(2)], | |
63 [(1, 0), | |
64 (2, 1), | |
65 (1, 2), | |
66 ]) | |
67 # delete a line out of 2 | |
68 ll.replacelines(3, 1, 2, 0, 0) | |
69 self.assertEqual([(l.rev, l.linenum) for l in ll.annotate(3)], | |
70 [(1, 0), | |
71 (1, 2), | |
72 ]) | |
73 # annotation of 1 is unchanged | |
74 self.assertEqual([(l.rev, l.linenum) for l in ll.annotate(1)], | |
75 [(1, 0), | |
76 (1, 1), | |
77 (1, 2), | |
78 ]) | |
79 ll.annotate(3) # set internal state to revision 3 | |
80 start = ll.getoffset(0) | |
81 end = ll.getoffset(1) | |
82 self.assertEqual(ll.getalllines(start, end), [ | |
83 (1, 0), | |
84 (2, 1), | |
85 (1, 1), | |
86 ]) | |
87 self.assertEqual(ll.getalllines(), [ | |
88 (1, 0), | |
89 (2, 1), | |
90 (1, 1), | |
91 (1, 2), | |
92 ]) | |
93 | |
94 def testparseclinelogfile(self): | |
95 # This data is what the replacements in testsimpleedits | |
96 # produce when fed to the original linelog.c implementation. | |
97 data = ('\x00\x00\x00\x0c\x00\x00\x00\x0f' | |
98 '\x00\x00\x00\x00\x00\x00\x00\x02' | |
99 '\x00\x00\x00\x05\x00\x00\x00\x06' | |
100 '\x00\x00\x00\x06\x00\x00\x00\x00' | |
101 '\x00\x00\x00\x00\x00\x00\x00\x07' | |
102 '\x00\x00\x00\x06\x00\x00\x00\x02' | |
103 '\x00\x00\x00\x00\x00\x00\x00\x00' | |
104 '\x00\x00\x00\t\x00\x00\x00\t' | |
105 '\x00\x00\x00\x00\x00\x00\x00\x0c' | |
106 '\x00\x00\x00\x08\x00\x00\x00\x05' | |
107 '\x00\x00\x00\x06\x00\x00\x00\x01' | |
108 '\x00\x00\x00\x00\x00\x00\x00\x05' | |
109 '\x00\x00\x00\x0c\x00\x00\x00\x05' | |
110 '\x00\x00\x00\n\x00\x00\x00\x01' | |
111 '\x00\x00\x00\x00\x00\x00\x00\t') | |
112 llc = linelog.linelog.fromdata(data) | |
113 self.assertEqual([(l.rev, l.linenum) for l in llc.annotate(1)], | |
114 [(1, 0), | |
115 (1, 1), | |
116 (1, 2), | |
117 ]) | |
118 self.assertEqual([(l.rev, l.linenum) for l in llc.annotate(2)], | |
119 [(1, 0), | |
120 (2, 1), | |
121 (1, 2), | |
122 ]) | |
123 self.assertEqual([(l.rev, l.linenum) for l in llc.annotate(3)], | |
124 [(1, 0), | |
125 (1, 2), | |
126 ]) | |
127 # Check we emit the same bytecode. | |
128 ll = linelog.linelog() | |
129 # Initial revision: add lines 0, 1, and 2 | |
130 ll.replacelines(1, 0, 0, 0, 3) | |
131 # Replace line 1 with a new line | |
132 ll.replacelines(2, 1, 2, 1, 2) | |
133 # delete a line out of 2 | |
134 ll.replacelines(3, 1, 2, 0, 0) | |
135 diff = '\n ' + '\n '.join(difflib.unified_diff( | |
136 ll.debugstr().splitlines(), llc.debugstr().splitlines(), | |
137 'python', 'c', lineterm='')) | |
138 self.assertEqual(ll._program, llc._program, 'Program mismatch: ' + diff) | |
139 # Done as a secondary step so we get a better result if the | |
140 # program is where the mismatch is. | |
141 self.assertEqual(ll, llc) | |
142 self.assertEqual(ll.encode(), data) | |
143 | |
144 def testanothersimplecase(self): | |
145 ll = linelog.linelog() | |
146 ll.replacelines(3, 0, 0, 0, 2) | |
147 ll.replacelines(4, 0, 2, 0, 0) | |
148 self.assertEqual([(l.rev, l.linenum) for l in ll.annotate(4)], | |
149 []) | |
150 self.assertEqual([(l.rev, l.linenum) for l in ll.annotate(3)], | |
151 [(3, 0), (3, 1)]) | |
152 # rev 2 is empty because contents were only ever introduced in rev 3 | |
153 self.assertEqual([(l.rev, l.linenum) for l in ll.annotate(2)], | |
154 []) | |
155 | |
156 def testrandomedits(self): | |
157 # Inspired by original linelog tests. | |
158 seed = random.random() | |
159 numrevs = 2000 | |
160 ll = linelog.linelog() | |
161 # Populate linelog | |
162 for lines, rev, a1, a2, b1, b2 in _genedits(seed, numrevs): | |
163 ll.replacelines(rev, a1, a2, b1, b2) | |
164 ar = ll.annotate(rev) | |
165 self.assertEqual(ll.annotateresult, lines) | |
166 # Verify we can get back these states by annotating each rev | |
167 for lines, rev, a1, a2, b1, b2 in _genedits(seed, numrevs): | |
168 ar = ll.annotate(rev) | |
169 self.assertEqual([(l.rev, l.linenum) for l in ar], lines) | |
170 | |
171 if __name__ == '__main__': | |
172 import silenttestrunner | |
173 silenttestrunner.main(__name__) |