net/tools/tld_cleanup/make_dafsa_unittest.py

   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()