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