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