OLD | NEW |
| (Empty) |
1 #!/usr/bin/env python | |
2 # Copyright 2014 The Chromium Authors. All rights reserved. | |
3 # Use of this source code is governed by a BSD-style license that can be | |
4 # found in the LICENSE file. | |
5 | |
6 | |
7 import sys | |
8 import unittest | |
9 import make_dafsa | |
10 | |
11 | |
12 class ParseGperfTest(unittest.TestCase): | |
13 def testMalformedKey(self): | |
14 """Tests exception is thrown at bad format.""" | |
15 infile1 = [ '%%', '', '%%' ] | |
16 self.assertRaises(make_dafsa.InputError, make_dafsa.parse_gperf, infile1) | |
17 | |
18 infile2 = [ '%%', 'apa,1', '%%' ] | |
19 self.assertRaises(make_dafsa.InputError, make_dafsa.parse_gperf, infile2) | |
20 | |
21 infile3 = [ '%%', 'apa, 1', '%%' ] | |
22 self.assertRaises(make_dafsa.InputError, make_dafsa.parse_gperf, infile3) | |
23 | |
24 def testBadValues(self): | |
25 """Tests exception is thrown when value is out of range.""" | |
26 infile1 = [ '%%', 'a, -1', '%%' ] | |
27 self.assertRaises(make_dafsa.InputError, make_dafsa.parse_gperf, infile1) | |
28 | |
29 infile2 = [ '%%', 'a, x', '%%' ] | |
30 self.assertRaises(make_dafsa.InputError, make_dafsa.parse_gperf, infile2) | |
31 | |
32 infile3 = [ '%%', 'a, 3', '%%' ] | |
33 self.assertRaises(make_dafsa.InputError, make_dafsa.parse_gperf, infile3) | |
34 | |
35 infile4 = [ '%%', 'a, 6', '%%' ] | |
36 self.assertRaises(make_dafsa.InputError, make_dafsa.parse_gperf, infile4) | |
37 | |
38 infile5 = [ '%%', 'a, 12', '%%' ] | |
39 self.assertRaises(make_dafsa.InputError, make_dafsa.parse_gperf, infile5) | |
40 | |
41 def testValues(self): | |
42 """Tests legal values are accepted.""" | |
43 infile1 = [ '%%', 'a, 0', '%%' ] | |
44 words1 = [ 'a0' ] | |
45 self.assertEqual(make_dafsa.parse_gperf(infile1), words1) | |
46 | |
47 infile2 = [ '%%', 'a, 1', '%%' ] | |
48 words2 = [ 'a1' ] | |
49 self.assertEqual(make_dafsa.parse_gperf(infile2), words2) | |
50 | |
51 infile3 = [ '%%', 'a, 2', '%%' ] | |
52 words3 = [ 'a2' ] | |
53 self.assertEqual(make_dafsa.parse_gperf(infile3), words3) | |
54 | |
55 infile4 = [ '%%', 'a, 4', '%%' ] | |
56 words4 = [ 'a4' ] | |
57 self.assertEqual(make_dafsa.parse_gperf(infile4), words4) | |
58 | |
59 def testOneWord(self): | |
60 """Tests a single key can be parsed.""" | |
61 infile = [ '%%', 'apa, 1', '%%' ] | |
62 words = [ 'apa1' ] | |
63 self.assertEqual(make_dafsa.parse_gperf(infile), words) | |
64 | |
65 def testTwoWords(self): | |
66 """Tests a sequence of keys can be parsed.""" | |
67 infile = [ '%%', 'apa, 1', 'bepa.com, 2', '%%' ] | |
68 words = [ 'apa1', 'bepa.com2' ] | |
69 self.assertEqual(make_dafsa.parse_gperf(infile), words) | |
70 | |
71 | |
72 class ToDafsaTest(unittest.TestCase): | |
73 def testEmptyInput(self): | |
74 """Tests exception is thrown at empty input.""" | |
75 words = () | |
76 self.assertRaises(make_dafsa.InputError, make_dafsa.to_dafsa, words) | |
77 | |
78 def testNonASCII(self): | |
79 """Tests exception is thrown if illegal characters are used.""" | |
80 words1 = ( chr(0x1F) + 'a1', ) | |
81 self.assertRaises(make_dafsa.InputError, make_dafsa.to_dafsa, words1) | |
82 | |
83 words2 = ( 'a' + chr(0x1F) + '1', ) | |
84 self.assertRaises(make_dafsa.InputError, make_dafsa.to_dafsa, words2) | |
85 | |
86 words3 = ( chr(0x80) + 'a1', ) | |
87 self.assertRaises(make_dafsa.InputError, make_dafsa.to_dafsa, words3) | |
88 | |
89 words4 = ( 'a' + chr(0x80) + '1', ) | |
90 self.assertRaises(make_dafsa.InputError, make_dafsa.to_dafsa, words4) | |
91 | |
92 def testChar(self): | |
93 """Tests a DAFSA can be created from a single character domain name.""" | |
94 words = [ 'a0' ] | |
95 node2 = ( chr(0), [ None ] ) | |
96 node1 = ( 'a', [ node2 ] ) | |
97 source = [ node1 ] | |
98 self.assertEqual(make_dafsa.to_dafsa(words), source) | |
99 | |
100 def testChars(self): | |
101 """Tests a DAFSA can be created from a multi character domain name.""" | |
102 words = [ 'ab0' ] | |
103 node3 = ( chr(0), [ None ] ) | |
104 node2 = ( 'b', [ node3 ] ) | |
105 node1 = ( 'a', [ node2 ] ) | |
106 source = [ node1 ] | |
107 self.assertEqual(make_dafsa.to_dafsa(words), source) | |
108 | |
109 def testWords(self): | |
110 """Tests a DAFSA can be created from a sequence of domain names.""" | |
111 words = [ 'a0', 'b1' ] | |
112 node4 = ( chr(1), [ None ] ) | |
113 node3 = ( 'b', [ node4 ] ) | |
114 node2 = ( chr(0), [ None ] ) | |
115 node1 = ( 'a', [ node2 ] ) | |
116 source = [ node1, node3 ] | |
117 self.assertEqual(make_dafsa.to_dafsa(words), source) | |
118 | |
119 | |
120 class ToWordsTest(unittest.TestCase): | |
121 def testSink(self): | |
122 """Tests the sink is exapnded to a list with an empty string.""" | |
123 node1 = None | |
124 words = [ '' ] | |
125 self.assertEqual(make_dafsa.to_words(node1), words) | |
126 | |
127 def testSingleNode(self): | |
128 """Tests a single node is expanded to a list with the label string.""" | |
129 | |
130 # 'ab' -> [ 'ab' ] | |
131 | |
132 node1 = ( 'ab', [ None ] ) | |
133 words = [ 'ab' ] | |
134 self.assertEqual(make_dafsa.to_words(node1), words) | |
135 | |
136 def testChain(self): | |
137 """Tests a sequence of nodes are preoperly expanded.""" | |
138 | |
139 # 'ab' -> 'cd' => [ 'abcd' ] | |
140 | |
141 node2 = ( 'cd', [ None ] ) | |
142 node1 = ( 'ab', [ node2 ] ) | |
143 words = [ 'abcd' ] | |
144 self.assertEqual(make_dafsa.to_words(node1), words) | |
145 | |
146 def testInnerTerminator(self): | |
147 """Tests a sequence with an inner terminator is expanded to two strings.""" | |
148 | |
149 # 'a' -> 'b' | |
150 # \ => [ 'ab', 'a' ] | |
151 # {sink} | |
152 | |
153 node2 = ( 'b', [ None ] ) | |
154 node1 = ( 'a', [ node2, None ] ) | |
155 words = [ 'ab', 'a' ] | |
156 self.assertEqual(make_dafsa.to_words(node1), words) | |
157 | |
158 def testDiamond(self): | |
159 """Tests a diamond can be expanded to a word list.""" | |
160 | |
161 # 'cd' | |
162 # / \ | |
163 # 'ab' 'gh' | |
164 # \ / | |
165 # 'ef' | |
166 | |
167 node4 = ( 'gh', [ None ] ) | |
168 node3 = ( 'ef', [ node4 ] ) | |
169 node2 = ( 'cd', [ node4 ] ) | |
170 node1 = ( 'ab', [ node2, node3 ] ) | |
171 words = [ 'abcdgh', 'abefgh' ] | |
172 self.assertEqual(make_dafsa.to_words(node1), words) | |
173 | |
174 | |
175 class JoinLabelsTest(unittest.TestCase): | |
176 def testLabel(self): | |
177 """Tests a single label passes unchanged.""" | |
178 | |
179 # 'a' => 'a' | |
180 | |
181 node1 = ( 'a', [ None ] ) | |
182 source = [ node1 ] | |
183 self.assertEqual(make_dafsa.join_labels(source), source) | |
184 | |
185 def testInnerTerminator(self): | |
186 """Tests a sequence with an inner terminator passes unchanged.""" | |
187 | |
188 # 'a' -> 'b' 'a' -> 'b' | |
189 # \ => \ | |
190 # {sink} {sink} | |
191 | |
192 node2 = ( 'b', [ None ] ) | |
193 node1 = ( 'a', [ node2, None ] ) | |
194 source = [ node1 ] | |
195 self.assertEqual(make_dafsa.join_labels(source), source) | |
196 | |
197 def testLabels(self): | |
198 """Tests a sequence of labels can be joined.""" | |
199 | |
200 # 'a' -> 'b' => 'ab' | |
201 | |
202 node2 = ( 'b', [ None ] ) | |
203 node1 = ( 'a', [ node2 ] ) | |
204 source1 = [ node1 ] | |
205 node3 = ( 'ab', [ None ] ) | |
206 source2 = [ node3 ] | |
207 self.assertEqual(make_dafsa.join_labels(source1), source2) | |
208 | |
209 def testCompositeLabels(self): | |
210 """Tests a sequence of multi character labels can be joined.""" | |
211 | |
212 # 'ab' -> 'cd' => 'abcd' | |
213 | |
214 node2 = ( 'cd', [ None ] ) | |
215 node1 = ( 'ab', [ node2 ] ) | |
216 source1 = [ node1 ] | |
217 node3 = ( 'abcd', [ None ] ) | |
218 source2 = [ node3 ] | |
219 self.assertEqual(make_dafsa.join_labels(source1), source2) | |
220 | |
221 def testAtomicTrie(self): | |
222 """Tests a trie formed DAFSA with atomic labels passes unchanged.""" | |
223 | |
224 # 'b' 'b' | |
225 # / / | |
226 # 'a' => 'a' | |
227 # \ \ | |
228 # 'c' 'c' | |
229 | |
230 node3 = ( 'c', [ None ] ) | |
231 node2 = ( 'b', [ None ] ) | |
232 node1 = ( 'a', [ node2, node3 ] ) | |
233 source = [ node1 ] | |
234 self.assertEqual(make_dafsa.join_labels(source), source) | |
235 | |
236 def testReverseAtomicTrie(self): | |
237 """Tests a reverse trie formed DAFSA with atomic labels passes unchanged.""" | |
238 | |
239 # 'a' 'a' | |
240 # \ \ | |
241 # 'c' => 'c' | |
242 # / / | |
243 # 'b' 'b' | |
244 | |
245 node3 = ( 'c', [ None ] ) | |
246 node2 = ( 'b', [ node3 ] ) | |
247 node1 = ( 'a', [ node3 ] ) | |
248 source = [ node1, node2 ] | |
249 self.assertEqual(make_dafsa.join_labels(source), source) | |
250 | |
251 def testChainedTrie(self): | |
252 """Tests a trie formed DAFSA with chained labels can be joined.""" | |
253 | |
254 # 'c' -> 'd' 'cd' | |
255 # / / | |
256 # 'a' -> 'b' => 'ab' | |
257 # \ \ | |
258 # 'e' -> 'f' 'ef' | |
259 | |
260 node6 = ( 'f', [ None ] ) | |
261 node5 = ( 'e', [ node6 ] ) | |
262 node4 = ( 'd', [ None ] ) | |
263 node3 = ( 'c', [ node4 ] ) | |
264 node2 = ( 'b', [ node3, node5 ] ) | |
265 node1 = ( 'a', [ node2 ] ) | |
266 source1 = [ node1 ] | |
267 node9 = ( 'ef', [ None ] ) | |
268 node8 = ( 'cd', [ None ] ) | |
269 node7 = ( 'ab', [ node8, node9 ] ) | |
270 source2 = [ node7 ] | |
271 self.assertEqual(make_dafsa.join_labels(source1), source2) | |
272 | |
273 def testReverseChainedTrie(self): | |
274 """Tests a reverse trie formed DAFSA with chained labels can be joined.""" | |
275 | |
276 # 'a' -> 'b' 'ab' | |
277 # \ \ | |
278 # 'e' -> 'f' => 'ef' | |
279 # / / | |
280 # 'c' -> 'd' 'cd' | |
281 | |
282 node6 = ( 'f', [ None ] ) | |
283 node5 = ( 'e', [ node6 ] ) | |
284 node4 = ( 'd', [ node5 ] ) | |
285 node3 = ( 'c', [ node4 ] ) | |
286 node2 = ( 'b', [ node5 ] ) | |
287 node1 = ( 'a', [ node2 ] ) | |
288 source1 = [ node1, node3 ] | |
289 node9 = ( 'ef', [ None ] ) | |
290 node8 = ( 'cd', [ node9 ] ) | |
291 node7 = ( 'ab', [ node9 ] ) | |
292 source2 = [ node7, node8 ] | |
293 self.assertEqual(make_dafsa.join_labels(source1), source2) | |
294 | |
295 | |
296 class JoinSuffixesTest(unittest.TestCase): | |
297 def testSingleLabel(self): | |
298 """Tests a single label passes unchanged.""" | |
299 | |
300 # 'a' => 'a' | |
301 | |
302 node1 = ( 'a', [ None ] ) | |
303 source = [ node1 ] | |
304 self.assertEqual(make_dafsa.join_suffixes(source), source) | |
305 | |
306 def testInnerTerminator(self): | |
307 """Tests a sequence with an inner terminator passes unchanged.""" | |
308 | |
309 # 'a' -> 'b' 'a' -> 'b' | |
310 # \ => \ | |
311 # {sink} {sink} | |
312 | |
313 node2 = ( 'b', [ None ] ) | |
314 node1 = ( 'a', [ node2, None ] ) | |
315 source = [ node1 ] | |
316 self.assertEqual(make_dafsa.join_suffixes(source), source) | |
317 | |
318 def testDistinctTrie(self): | |
319 """Tests a trie formed DAFSA with distinct labels passes unchanged.""" | |
320 | |
321 # 'b' 'b' | |
322 # / / | |
323 # 'a' => 'a' | |
324 # \ \ | |
325 # 'c' 'c' | |
326 | |
327 node3 = ( 'c', [ None ] ) | |
328 node2 = ( 'b', [ None ] ) | |
329 node1 = ( 'a', [ node2, node3 ] ) | |
330 source = [ node1 ] | |
331 self.assertEqual(make_dafsa.join_suffixes(source), source) | |
332 | |
333 def testReverseDistinctTrie(self): | |
334 """Tests a reverse trie formed DAFSA with distinct labels passes unchanged. | |
335 """ | |
336 | |
337 # 'a' 'a' | |
338 # \ \ | |
339 # 'c' => 'c' | |
340 # / / | |
341 # 'b' 'b' | |
342 | |
343 node3 = ( 'c', [ None ] ) | |
344 node2 = ( 'b', [ node3 ] ) | |
345 node1 = ( 'a', [ node3 ] ) | |
346 source = [ node1, node2 ] | |
347 self.assertEqual(make_dafsa.join_suffixes(source), source) | |
348 | |
349 def testJoinTwoHeads(self): | |
350 """Tests two heads can be joined even if there is something else between.""" | |
351 | |
352 # 'a' ------'a' | |
353 # / | |
354 # 'b' => 'b' / | |
355 # / | |
356 # 'a' --- | |
357 # | |
358 # The picture above should shows that the new version should have just one | |
359 # instance of the node with label 'a'. | |
360 | |
361 node3 = ( 'a', [ None ] ) | |
362 node2 = ( 'b', [ None ] ) | |
363 node1 = ( 'a', [ None ] ) | |
364 source1 = [ node1, node2, node3 ] | |
365 source2 = make_dafsa.join_suffixes(source1) | |
366 | |
367 # Both versions should expand to the same content. | |
368 self.assertEqual(source1, source2) | |
369 # But the new version should have just one instance of 'a'. | |
370 self.assertIs(source2[0], source2[2]) | |
371 | |
372 def testJoinTails(self): | |
373 """Tests tails can be joined.""" | |
374 | |
375 # 'a' -> 'c' 'a' | |
376 # \ | |
377 # => 'c' | |
378 # / | |
379 # 'b' -> 'c' 'b' | |
380 | |
381 node4 = ( 'c', [ None ] ) | |
382 node3 = ( 'b', [ node4 ] ) | |
383 node2 = ( 'c', [ None ] ) | |
384 node1 = ( 'a', [ node2 ] ) | |
385 source1 = [ node1, node3 ] | |
386 source2 = make_dafsa.join_suffixes(source1) | |
387 | |
388 # Both versions should expand to the same content. | |
389 self.assertEqual(source1, source2) | |
390 # But the new version should have just one tail. | |
391 self.assertIs(source2[0][1][0], source2[1][1][0]) | |
392 | |
393 def testMakeRecursiveTrie(self): | |
394 """Tests recursive suffix join.""" | |
395 | |
396 # 'a' -> 'e' -> 'g' 'a' | |
397 # \ | |
398 # 'e' | |
399 # / \ | |
400 # 'b' -> 'e' -> 'g' 'b' \ | |
401 # \ | |
402 # => 'g' | |
403 # / | |
404 # 'c' -> 'f' -> 'g' 'c' / | |
405 # \ / | |
406 # 'f' | |
407 # / | |
408 # 'd' -> 'f' -> 'g' 'd' | |
409 | |
410 node7 = ( 'g', [ None ] ) | |
411 node6 = ( 'f', [ node7 ] ) | |
412 node5 = ( 'e', [ node7 ] ) | |
413 node4 = ( 'd', [ node6 ] ) | |
414 node3 = ( 'c', [ node6 ] ) | |
415 node2 = ( 'b', [ node5 ] ) | |
416 node1 = ( 'a', [ node5 ] ) | |
417 source1 = [ node1, node2, node3, node4 ] | |
418 source2 = make_dafsa.join_suffixes(source1) | |
419 | |
420 # Both versions should expand to the same content. | |
421 self.assertEqual(source1, source2) | |
422 # But the new version should have just one 'e'. | |
423 self.assertIs(source2[0][1][0], source2[1][1][0]) | |
424 # And one 'f'. | |
425 self.assertIs(source2[2][1][0], source2[3][1][0]) | |
426 # And one 'g'. | |
427 self.assertIs(source2[0][1][0][1][0], source2[2][1][0][1][0]) | |
428 | |
429 def testMakeDiamond(self): | |
430 """Test we can join suffixes of a trie.""" | |
431 | |
432 # 'b' -> 'd' 'b' | |
433 # / / \ | |
434 # 'a' => 'a' 'd' | |
435 # \ \ / | |
436 # 'c' -> 'd' 'c' | |
437 | |
438 node5 = ( 'd', [ None ] ) | |
439 node4 = ( 'c', [ node5 ] ) | |
440 node3 = ( 'd', [ None ] ) | |
441 node2 = ( 'b', [ node3 ] ) | |
442 node1 = ( 'a', [ node2, node4 ] ) | |
443 source1 = [ node1 ] | |
444 source2 = make_dafsa.join_suffixes(source1) | |
445 | |
446 # Both versions should expand to the same content. | |
447 self.assertEqual(source1, source2) | |
448 # But the new version should have just one 'd'. | |
449 self.assertIs(source2[0][1][0][1][0], source2[0][1][1][1][0]) | |
450 | |
451 def testJoinOneChild(self): | |
452 """Tests that we can join some children but not all.""" | |
453 | |
454 # 'c' ----'c' | |
455 # / / / | |
456 # 'a' 'a' / | |
457 # \ \ / | |
458 # 'd' 'd'/ | |
459 # => / | |
460 # 'c' / | |
461 # / / | |
462 # 'b' 'b' | |
463 # \ \ | |
464 # 'e' 'e' | |
465 | |
466 node6 = ( 'e', [ None ] ) | |
467 node5 = ( 'c', [ None ] ) | |
468 node4 = ( 'b', [ node5, node6 ] ) | |
469 node3 = ( 'd', [ None ] ) | |
470 node2 = ( 'c', [ None ] ) | |
471 node1 = ( 'a', [ node2, node3 ] ) | |
472 source1 = [ node1, node4 ] | |
473 source2 = make_dafsa.join_suffixes(source1) | |
474 | |
475 # Both versions should expand to the same content. | |
476 self.assertEqual(source1, source2) | |
477 # But the new version should have just one 'c'. | |
478 self.assertIs(source2[0][1][0], source2[1][1][0]) | |
479 | |
480 | |
481 class ReverseTest(unittest.TestCase): | |
482 def testAtomicLabel(self): | |
483 """Tests an atomic label passes unchanged.""" | |
484 | |
485 # 'a' => 'a' | |
486 | |
487 node1 = ( 'a', [ None ] ) | |
488 source = [ node1 ] | |
489 self.assertEqual(make_dafsa.reverse(source), source) | |
490 | |
491 def testLabel(self): | |
492 """Tests that labels are reversed.""" | |
493 | |
494 # 'ab' => 'ba' | |
495 | |
496 node1 = ( 'ab', [ None ] ) | |
497 source1 = [ node1 ] | |
498 node2 = ( 'ba', [ None ] ) | |
499 source2 = [ node2 ] | |
500 self.assertEqual(make_dafsa.reverse(source1), source2) | |
501 | |
502 def testChain(self): | |
503 """Tests that edges are reversed.""" | |
504 | |
505 # 'a' -> 'b' => 'b' -> 'a' | |
506 | |
507 node2 = ( 'b', [ None ] ) | |
508 node1 = ( 'a', [ node2 ] ) | |
509 source1 = [ node1 ] | |
510 node4 = ( 'a', [ None ] ) | |
511 node3 = ( 'b', [ node4 ] ) | |
512 source2 = [ node3 ] | |
513 self.assertEqual(make_dafsa.reverse(source1), source2) | |
514 | |
515 def testInnerTerminator(self): | |
516 """Tests a sequence with an inner terminator can be reversed.""" | |
517 | |
518 # 'a' -> 'b' 'b' -> 'a' | |
519 # \ => / | |
520 # {sink} ------ | |
521 | |
522 node2 = ( 'b', [ None ] ) | |
523 node1 = ( 'a', [ node2, None ] ) | |
524 source1 = [ node1 ] | |
525 node4 = ( 'a', [ None ] ) | |
526 node3 = ( 'b', [ node4 ] ) | |
527 source2 = [ node3, node4 ] | |
528 self.assertEqual(make_dafsa.reverse(source1), source2) | |
529 | |
530 def testAtomicTrie(self): | |
531 """Tests a trie formed DAFSA can be reversed.""" | |
532 | |
533 # 'b' 'b' | |
534 # / \ | |
535 # 'a' => 'a' | |
536 # \ / | |
537 # 'c' 'c' | |
538 | |
539 node3 = ( 'c', [ None ] ) | |
540 node2 = ( 'b', [ None ] ) | |
541 node1 = ( 'a', [ node2, node3 ] ) | |
542 source1 = [ node1 ] | |
543 node6 = ( 'a', [ None ] ) | |
544 node5 = ( 'c', [ node6 ] ) | |
545 node4 = ( 'b', [ node6 ] ) | |
546 source2 = [ node4, node5 ] | |
547 self.assertEqual(make_dafsa.reverse(source1), source2) | |
548 | |
549 def testReverseAtomicTrie(self): | |
550 """Tests a reverse trie formed DAFSA can be reversed.""" | |
551 | |
552 # 'a' 'a' | |
553 # \ / | |
554 # 'c' => 'c' | |
555 # / \ | |
556 # 'b' 'b' | |
557 | |
558 node3 = ( 'c', [ None ] ) | |
559 node2 = ( 'b', [ node3 ] ) | |
560 node1 = ( 'a', [ node3 ] ) | |
561 source1 = [ node1, node2 ] | |
562 node6 = ( 'b', [ None ] ) | |
563 node5 = ( 'a', [ None ] ) | |
564 node4 = ( 'c', [ node5, node6 ] ) | |
565 source2 = [ node4 ] | |
566 self.assertEqual(make_dafsa.reverse(source1), source2) | |
567 | |
568 def testDiamond(self): | |
569 """Tests we can reverse both edges and nodes in a diamond.""" | |
570 | |
571 # 'cd' 'dc' | |
572 # / \ / \ | |
573 # 'ab' 'gh' => 'hg' 'ba' | |
574 # \ / \ / | |
575 # 'ef' 'fe' | |
576 | |
577 node4 = ( 'gh', [ None ] ) | |
578 node3 = ( 'ef', [ node4 ] ) | |
579 node2 = ( 'cd', [ node4 ] ) | |
580 node1 = ( 'ab', [ node2, node3 ] ) | |
581 source1 = [ node1 ] | |
582 node8 = ( 'ba', [ None ] ) | |
583 node7 = ( 'fe', [ node8 ] ) | |
584 node6 = ( 'dc', [ node8 ] ) | |
585 node5 = ( 'hg', [ node6, node7 ] ) | |
586 source2 = [ node5 ] | |
587 self.assertEqual(make_dafsa.reverse(source1), source2) | |
588 | |
589 | |
590 class TopSortTest(unittest.TestCase): | |
591 def testNode(self): | |
592 """Tests a DAFSA with one node can be sorted.""" | |
593 | |
594 # 'a' => [ 'a' ] | |
595 | |
596 node1 = ( 'a', [ None ] ) | |
597 source = [ node1 ] | |
598 nodes = [ node1 ] | |
599 self.assertEqual(make_dafsa.top_sort(source), nodes) | |
600 | |
601 def testDiamond(self): | |
602 """Tests nodes in a diamond can be sorted.""" | |
603 | |
604 # 'b' | |
605 # / \ | |
606 # 'a' 'd' | |
607 # \ / | |
608 # 'c' | |
609 | |
610 node4 = ( 'd', [ None ] ) | |
611 node3 = ( 'c', [ node4 ] ) | |
612 node2 = ( 'b', [ node4 ] ) | |
613 node1 = ( 'a', [ node2, node3 ] ) | |
614 source = [ node1 ] | |
615 nodes = make_dafsa.top_sort(source) | |
616 self.assertLess(nodes.index(node1), nodes.index(node2)) | |
617 self.assertLess(nodes.index(node2), nodes.index(node4)) | |
618 self.assertLess(nodes.index(node3), nodes.index(node4)) | |
619 | |
620 | |
621 class EncodePrefixTest(unittest.TestCase): | |
622 def testChar(self): | |
623 """Tests to encode a single character prefix.""" | |
624 label = 'a' | |
625 bytes = [ ord('a') ] | |
626 self.assertEqual(make_dafsa.encode_prefix(label), bytes) | |
627 | |
628 def testChars(self): | |
629 """Tests to encode a multi character prefix.""" | |
630 label = 'ab' | |
631 bytes = [ ord('b'), ord('a') ] | |
632 self.assertEqual(make_dafsa.encode_prefix(label), bytes) | |
633 | |
634 | |
635 class EncodeLabelTest(unittest.TestCase): | |
636 def testChar(self): | |
637 """Tests to encode a single character label.""" | |
638 label = 'a' | |
639 bytes = [ ord('a') + 0x80 ] | |
640 self.assertEqual(make_dafsa.encode_label(label), bytes) | |
641 | |
642 def testChars(self): | |
643 """Tests to encode a multi character label.""" | |
644 label = 'ab' | |
645 bytes = [ ord('b') + 0x80, ord('a') ] | |
646 self.assertEqual(make_dafsa.encode_label(label), bytes) | |
647 | |
648 | |
649 class EncodeLinksTest(unittest.TestCase): | |
650 def testEndLabel(self): | |
651 """Tests to encode link to the sink.""" | |
652 children = [ None ] | |
653 offsets = {} | |
654 bytes = 0 | |
655 output = [] | |
656 self.assertEqual(make_dafsa.encode_links(children, offsets, bytes), | |
657 output) | |
658 | |
659 def testOneByteOffset(self): | |
660 """Tests to encode a single one byte offset.""" | |
661 node = ( '', [ None ] ) | |
662 children = [ node ] | |
663 offsets = { id(node) : 2 } | |
664 bytes = 5 | |
665 output = [ 132 ] | |
666 self.assertEqual(make_dafsa.encode_links(children, offsets, bytes), | |
667 output) | |
668 | |
669 def testOneByteOffsets(self): | |
670 """Tests to encode a sequence of one byte offsets.""" | |
671 node1 = ( '', [ None ] ) | |
672 node2 = ( '', [ None ] ) | |
673 children = [ node1, node2 ] | |
674 offsets = { id(node1) : 2, id(node2) : 1 } | |
675 bytes = 5 | |
676 output = [ 129, 5 ] | |
677 self.assertEqual(make_dafsa.encode_links(children, offsets, bytes), | |
678 output) | |
679 | |
680 def testTwoBytesOffset(self): | |
681 """Tests to encode a single two byte offset.""" | |
682 node = ( '', [ None ] ) | |
683 children = [ node ] | |
684 offsets = { id(node) : 2 } | |
685 bytes = 1005 | |
686 output = [ 237, 195] | |
687 self.assertEqual(make_dafsa.encode_links(children, offsets, bytes), | |
688 output) | |
689 | |
690 def testTwoBytesOffsets(self): | |
691 """Tests to encode a sequence of two byte offsets.""" | |
692 node1 = ( '', [ None ] ) | |
693 node2 = ( '', [ None ] ) | |
694 node3 = ( '', [ None ] ) | |
695 children = [ node1, node2, node3 ] | |
696 offsets = { id(node1) : 1002, id(node2) : 2, id(node3) : 2002 } | |
697 bytes = 3005 | |
698 output = [ 232, 195, 232, 67, 241, 67 ] | |
699 self.assertEqual(make_dafsa.encode_links(children, offsets, bytes), | |
700 output) | |
701 | |
702 def testThreeBytesOffset(self): | |
703 """Tests to encode a single three byte offset.""" | |
704 node = ( '', [ None ] ) | |
705 children = [ node ] | |
706 offsets = { id(node) : 2 } | |
707 bytes = 100005 | |
708 output = [ 166, 134, 225 ] | |
709 self.assertEqual(make_dafsa.encode_links(children, offsets, bytes), | |
710 output) | |
711 | |
712 def testThreeBytesOffsets(self): | |
713 """Tests to encode a sequence of three byte offsets.""" | |
714 node1 = ( '', [ None ] ) | |
715 node2 = ( '', [ None ] ) | |
716 node3 = ( '', [ None ] ) | |
717 children = [ node1, node2, node3 ] | |
718 offsets = { id(node1) : 100002, id(node2) : 2, id(node3) : 200002 } | |
719 bytes = 300005 | |
720 output = [ 160, 134, 225, 160, 134, 97, 172, 134, 97 ] | |
721 self.assertEqual(make_dafsa.encode_links(children, offsets, bytes), | |
722 output) | |
723 | |
724 def testOneTwoThreeBytesOffsets(self): | |
725 """Tests to encode offsets of different sizes.""" | |
726 node1 = ( '', [ None ] ) | |
727 node2 = ( '', [ None ] ) | |
728 node3 = ( '', [ None ] ) | |
729 children = [ node1, node2, node3 ] | |
730 offsets = { id(node1) : 10003, id(node2) : 10002, id(node3) : 100002 } | |
731 bytes = 300005 | |
732 output = [ 129, 143, 95, 97, 74, 13, 99 ] | |
733 self.assertEqual(make_dafsa.encode_links(children, offsets, bytes), | |
734 output) | |
735 | |
736 | |
737 class ExamplesTest(unittest.TestCase): | |
738 def testExample1(self): | |
739 """Tests Example 1 from make_dafsa.py.""" | |
740 infile = [ '%%', 'aa, 1', 'a, 2', '%%' ] | |
741 bytes = [ 0x81, 0xE1, 0x02, 0x81, 0x82, 0x61, 0x81 ] | |
742 outfile = make_dafsa.to_cxx(bytes) | |
743 self.assertEqual(make_dafsa.words_to_cxx(make_dafsa.parse_gperf(infile)), | |
744 outfile) | |
745 | |
746 def testExample2(self): | |
747 """Tests Example 2 from make_dafsa.py.""" | |
748 infile = [ '%%', 'aa, 1', 'bbb, 2', 'baa, 1', '%%' ] | |
749 bytes = [ 0x02, 0x83, 0xE2, 0x02, 0x83, 0x61, 0x61, 0x81, 0x62, 0x62, | |
750 0x82 ] | |
751 outfile = make_dafsa.to_cxx(bytes) | |
752 self.assertEqual(make_dafsa.words_to_cxx(make_dafsa.parse_gperf(infile)), | |
753 outfile) | |
754 | |
755 | |
756 if __name__ == '__main__': | |
757 unittest.main() | |
OLD | NEW |