• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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
7import sys
8import unittest
9import make_dafsa
10
11
12class 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
72class 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
120class 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
175class 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
296class 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
481class 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
590class 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
621class 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
635class 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
649class 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
737class 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
756if __name__ == '__main__':
757  unittest.main()
758