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