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