make_dafsa_unittest.py 20 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706
  1. #!/usr/bin/env python3
  2. # Copyright 2017 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. import sys
  6. import unittest
  7. import make_dafsa
  8. class ToDafsaTest(unittest.TestCase):
  9. def testEmptyInput(self):
  10. """Tests exception is thrown at empty input."""
  11. words = ()
  12. self.assertRaises(make_dafsa.InputError, make_dafsa.to_dafsa, words)
  13. def testNonASCII(self):
  14. """Tests exception is thrown if illegal characters are used."""
  15. words1 = ( chr(0x1F) + 'a1', )
  16. self.assertRaises(make_dafsa.InputError, make_dafsa.to_dafsa, words1)
  17. words2 = ( 'a' + chr(0x1F) + '1', )
  18. self.assertRaises(make_dafsa.InputError, make_dafsa.to_dafsa, words2)
  19. words3 = ( chr(0x80) + 'a1', )
  20. self.assertRaises(make_dafsa.InputError, make_dafsa.to_dafsa, words3)
  21. words4 = ( 'a' + chr(0x80) + '1', )
  22. self.assertRaises(make_dafsa.InputError, make_dafsa.to_dafsa, words4)
  23. def testChar(self):
  24. """Tests a DAFSA can be created from a single character domain name."""
  25. words = [ 'a0' ]
  26. node2 = ( chr(0), [ None ] )
  27. node1 = ( 'a', [ node2 ] )
  28. source = [ node1 ]
  29. self.assertEqual(make_dafsa.to_dafsa(words), source)
  30. def testChars(self):
  31. """Tests a DAFSA can be created from a multi character domain name."""
  32. words = [ 'ab0' ]
  33. node3 = ( chr(0), [ None ] )
  34. node2 = ( 'b', [ node3 ] )
  35. node1 = ( 'a', [ node2 ] )
  36. source = [ node1 ]
  37. self.assertEqual(make_dafsa.to_dafsa(words), source)
  38. def testWords(self):
  39. """Tests a DAFSA can be created from a sequence of domain names."""
  40. words = [ 'a0', 'b1' ]
  41. node4 = ( chr(1), [ None ] )
  42. node3 = ( 'b', [ node4 ] )
  43. node2 = ( chr(0), [ None ] )
  44. node1 = ( 'a', [ node2 ] )
  45. source = [ node1, node3 ]
  46. self.assertEqual(make_dafsa.to_dafsa(words), source)
  47. class ToWordsTest(unittest.TestCase):
  48. def testSink(self):
  49. """Tests the sink is exapnded to a list with an empty string."""
  50. node1 = None
  51. words = [ '' ]
  52. self.assertEqual(make_dafsa.to_words(node1), words)
  53. def testSingleNode(self):
  54. """Tests a single node is expanded to a list with the label string."""
  55. # 'ab' -> [ 'ab' ]
  56. node1 = ( 'ab', [ None ] )
  57. words = [ 'ab' ]
  58. self.assertEqual(make_dafsa.to_words(node1), words)
  59. def testChain(self):
  60. """Tests a sequence of nodes are preoperly expanded."""
  61. # 'ab' -> 'cd' => [ 'abcd' ]
  62. node2 = ( 'cd', [ None ] )
  63. node1 = ( 'ab', [ node2 ] )
  64. words = [ 'abcd' ]
  65. self.assertEqual(make_dafsa.to_words(node1), words)
  66. def testInnerTerminator(self):
  67. """Tests a sequence with an inner terminator is expanded to two strings."""
  68. # 'a' -> 'b'
  69. # \ => [ 'ab', 'a' ]
  70. # {sink}
  71. node2 = ( 'b', [ None ] )
  72. node1 = ( 'a', [ node2, None ] )
  73. words = [ 'ab', 'a' ]
  74. self.assertEqual(make_dafsa.to_words(node1), words)
  75. def testDiamond(self):
  76. """Tests a diamond can be expanded to a word list."""
  77. # 'cd'
  78. # / \
  79. # 'ab' 'gh'
  80. # \ /
  81. # 'ef'
  82. node4 = ( 'gh', [ None ] )
  83. node3 = ( 'ef', [ node4 ] )
  84. node2 = ( 'cd', [ node4 ] )
  85. node1 = ( 'ab', [ node2, node3 ] )
  86. words = [ 'abcdgh', 'abefgh' ]
  87. self.assertEqual(make_dafsa.to_words(node1), words)
  88. class JoinLabelsTest(unittest.TestCase):
  89. def testLabel(self):
  90. """Tests a single label passes unchanged."""
  91. # 'a' => 'a'
  92. node1 = ( 'a', [ None ] )
  93. source = [ node1 ]
  94. self.assertEqual(make_dafsa.join_labels(source), source)
  95. def testInnerTerminator(self):
  96. """Tests a sequence with an inner terminator passes unchanged."""
  97. # 'a' -> 'b' 'a' -> 'b'
  98. # \ => \
  99. # {sink} {sink}
  100. node2 = ( 'b', [ None ] )
  101. node1 = ( 'a', [ node2, None ] )
  102. source = [ node1 ]
  103. self.assertEqual(make_dafsa.join_labels(source), source)
  104. def testLabels(self):
  105. """Tests a sequence of labels can be joined."""
  106. # 'a' -> 'b' => 'ab'
  107. node2 = ( 'b', [ None ] )
  108. node1 = ( 'a', [ node2 ] )
  109. source1 = [ node1 ]
  110. node3 = ( 'ab', [ None ] )
  111. source2 = [ node3 ]
  112. self.assertEqual(make_dafsa.join_labels(source1), source2)
  113. def testCompositeLabels(self):
  114. """Tests a sequence of multi character labels can be joined."""
  115. # 'ab' -> 'cd' => 'abcd'
  116. node2 = ( 'cd', [ None ] )
  117. node1 = ( 'ab', [ node2 ] )
  118. source1 = [ node1 ]
  119. node3 = ( 'abcd', [ None ] )
  120. source2 = [ node3 ]
  121. self.assertEqual(make_dafsa.join_labels(source1), source2)
  122. def testAtomicTrie(self):
  123. """Tests a trie formed DAFSA with atomic labels passes unchanged."""
  124. # 'b' 'b'
  125. # / /
  126. # 'a' => 'a'
  127. # \ \
  128. # 'c' 'c'
  129. node3 = ( 'c', [ None ] )
  130. node2 = ( 'b', [ None ] )
  131. node1 = ( 'a', [ node2, node3 ] )
  132. source = [ node1 ]
  133. self.assertEqual(make_dafsa.join_labels(source), source)
  134. def testReverseAtomicTrie(self):
  135. """Tests a reverse trie formed DAFSA with atomic labels passes unchanged."""
  136. # 'a' 'a'
  137. # \ \
  138. # 'c' => 'c'
  139. # / /
  140. # 'b' 'b'
  141. node3 = ( 'c', [ None ] )
  142. node2 = ( 'b', [ node3 ] )
  143. node1 = ( 'a', [ node3 ] )
  144. source = [ node1, node2 ]
  145. self.assertEqual(make_dafsa.join_labels(source), source)
  146. def testChainedTrie(self):
  147. """Tests a trie formed DAFSA with chained labels can be joined."""
  148. # 'c' -> 'd' 'cd'
  149. # / /
  150. # 'a' -> 'b' => 'ab'
  151. # \ \
  152. # 'e' -> 'f' 'ef'
  153. node6 = ( 'f', [ None ] )
  154. node5 = ( 'e', [ node6 ] )
  155. node4 = ( 'd', [ None ] )
  156. node3 = ( 'c', [ node4 ] )
  157. node2 = ( 'b', [ node3, node5 ] )
  158. node1 = ( 'a', [ node2 ] )
  159. source1 = [ node1 ]
  160. node9 = ( 'ef', [ None ] )
  161. node8 = ( 'cd', [ None ] )
  162. node7 = ( 'ab', [ node8, node9 ] )
  163. source2 = [ node7 ]
  164. self.assertEqual(make_dafsa.join_labels(source1), source2)
  165. def testReverseChainedTrie(self):
  166. """Tests a reverse trie formed DAFSA with chained labels can be joined."""
  167. # 'a' -> 'b' 'ab'
  168. # \ \
  169. # 'e' -> 'f' => 'ef'
  170. # / /
  171. # 'c' -> 'd' 'cd'
  172. node6 = ( 'f', [ None ] )
  173. node5 = ( 'e', [ node6 ] )
  174. node4 = ( 'd', [ node5 ] )
  175. node3 = ( 'c', [ node4 ] )
  176. node2 = ( 'b', [ node5 ] )
  177. node1 = ( 'a', [ node2 ] )
  178. source1 = [ node1, node3 ]
  179. node9 = ( 'ef', [ None ] )
  180. node8 = ( 'cd', [ node9 ] )
  181. node7 = ( 'ab', [ node9 ] )
  182. source2 = [ node7, node8 ]
  183. self.assertEqual(make_dafsa.join_labels(source1), source2)
  184. class JoinSuffixesTest(unittest.TestCase):
  185. def testSingleLabel(self):
  186. """Tests a single label passes unchanged."""
  187. # 'a' => 'a'
  188. node1 = ( 'a', [ None ] )
  189. source = [ node1 ]
  190. self.assertEqual(make_dafsa.join_suffixes(source), source)
  191. def testInnerTerminator(self):
  192. """Tests a sequence with an inner terminator passes unchanged."""
  193. # 'a' -> 'b' 'a' -> 'b'
  194. # \ => \
  195. # {sink} {sink}
  196. node2 = ( 'b', [ None ] )
  197. node1 = ( 'a', [ node2, None ] )
  198. source = [ node1 ]
  199. self.assertEqual(make_dafsa.join_suffixes(source), source)
  200. def testDistinctTrie(self):
  201. """Tests a trie formed DAFSA with distinct labels passes unchanged."""
  202. # 'b' 'b'
  203. # / /
  204. # 'a' => 'a'
  205. # \ \
  206. # 'c' 'c'
  207. node3 = ( 'c', [ None ] )
  208. node2 = ( 'b', [ None ] )
  209. node1 = ( 'a', [ node2, node3 ] )
  210. source = [ node1 ]
  211. self.assertEqual(make_dafsa.join_suffixes(source), source)
  212. def testReverseDistinctTrie(self):
  213. """Tests a reverse trie formed DAFSA with distinct labels passes unchanged.
  214. """
  215. # 'a' 'a'
  216. # \ \
  217. # 'c' => 'c'
  218. # / /
  219. # 'b' 'b'
  220. node3 = ( 'c', [ None ] )
  221. node2 = ( 'b', [ node3 ] )
  222. node1 = ( 'a', [ node3 ] )
  223. source = [ node1, node2 ]
  224. self.assertEqual(make_dafsa.join_suffixes(source), source)
  225. def testJoinTwoHeads(self):
  226. """Tests two heads can be joined even if there is something else between."""
  227. # 'a' ------'a'
  228. # /
  229. # 'b' => 'b' /
  230. # /
  231. # 'a' ---
  232. #
  233. # The picture above should shows that the new version should have just one
  234. # instance of the node with label 'a'.
  235. node3 = ( 'a', [ None ] )
  236. node2 = ( 'b', [ None ] )
  237. node1 = ( 'a', [ None ] )
  238. source1 = [ node1, node2, node3 ]
  239. source2 = make_dafsa.join_suffixes(source1)
  240. # Both versions should expand to the same content.
  241. self.assertEqual(source1, source2)
  242. # But the new version should have just one instance of 'a'.
  243. self.assertIs(source2[0], source2[2])
  244. def testJoinTails(self):
  245. """Tests tails can be joined."""
  246. # 'a' -> 'c' 'a'
  247. # \
  248. # => 'c'
  249. # /
  250. # 'b' -> 'c' 'b'
  251. node4 = ( 'c', [ None ] )
  252. node3 = ( 'b', [ node4 ] )
  253. node2 = ( 'c', [ None ] )
  254. node1 = ( 'a', [ node2 ] )
  255. source1 = [ node1, node3 ]
  256. source2 = make_dafsa.join_suffixes(source1)
  257. # Both versions should expand to the same content.
  258. self.assertEqual(source1, source2)
  259. # But the new version should have just one tail.
  260. self.assertIs(source2[0][1][0], source2[1][1][0])
  261. def testMakeRecursiveTrie(self):
  262. """Tests recursive suffix join."""
  263. # 'a' -> 'e' -> 'g' 'a'
  264. # \
  265. # 'e'
  266. # / \
  267. # 'b' -> 'e' -> 'g' 'b' \
  268. # \
  269. # => 'g'
  270. # /
  271. # 'c' -> 'f' -> 'g' 'c' /
  272. # \ /
  273. # 'f'
  274. # /
  275. # 'd' -> 'f' -> 'g' 'd'
  276. node7 = ( 'g', [ None ] )
  277. node6 = ( 'f', [ node7 ] )
  278. node5 = ( 'e', [ node7 ] )
  279. node4 = ( 'd', [ node6 ] )
  280. node3 = ( 'c', [ node6 ] )
  281. node2 = ( 'b', [ node5 ] )
  282. node1 = ( 'a', [ node5 ] )
  283. source1 = [ node1, node2, node3, node4 ]
  284. source2 = make_dafsa.join_suffixes(source1)
  285. # Both versions should expand to the same content.
  286. self.assertEqual(source1, source2)
  287. # But the new version should have just one 'e'.
  288. self.assertIs(source2[0][1][0], source2[1][1][0])
  289. # And one 'f'.
  290. self.assertIs(source2[2][1][0], source2[3][1][0])
  291. # And one 'g'.
  292. self.assertIs(source2[0][1][0][1][0], source2[2][1][0][1][0])
  293. def testMakeDiamond(self):
  294. """Test we can join suffixes of a trie."""
  295. # 'b' -> 'd' 'b'
  296. # / / \
  297. # 'a' => 'a' 'd'
  298. # \ \ /
  299. # 'c' -> 'd' 'c'
  300. node5 = ( 'd', [ None ] )
  301. node4 = ( 'c', [ node5 ] )
  302. node3 = ( 'd', [ None ] )
  303. node2 = ( 'b', [ node3 ] )
  304. node1 = ( 'a', [ node2, node4 ] )
  305. source1 = [ node1 ]
  306. source2 = make_dafsa.join_suffixes(source1)
  307. # Both versions should expand to the same content.
  308. self.assertEqual(source1, source2)
  309. # But the new version should have just one 'd'.
  310. self.assertIs(source2[0][1][0][1][0], source2[0][1][1][1][0])
  311. def testJoinOneChild(self):
  312. """Tests that we can join some children but not all."""
  313. # 'c' ----'c'
  314. # / / /
  315. # 'a' 'a' /
  316. # \ \ /
  317. # 'd' 'd'/
  318. # => /
  319. # 'c' /
  320. # / /
  321. # 'b' 'b'
  322. # \ \
  323. # 'e' 'e'
  324. node6 = ( 'e', [ None ] )
  325. node5 = ( 'c', [ None ] )
  326. node4 = ( 'b', [ node5, node6 ] )
  327. node3 = ( 'd', [ None ] )
  328. node2 = ( 'c', [ None ] )
  329. node1 = ( 'a', [ node2, node3 ] )
  330. source1 = [ node1, node4 ]
  331. source2 = make_dafsa.join_suffixes(source1)
  332. # Both versions should expand to the same content.
  333. self.assertEqual(source1, source2)
  334. # But the new version should have just one 'c'.
  335. self.assertIs(source2[0][1][0], source2[1][1][0])
  336. class ReverseTest(unittest.TestCase):
  337. def testAtomicLabel(self):
  338. """Tests an atomic label passes unchanged."""
  339. # 'a' => 'a'
  340. node1 = ( 'a', [ None ] )
  341. source = [ node1 ]
  342. self.assertEqual(make_dafsa.reverse(source), source)
  343. def testLabel(self):
  344. """Tests that labels are reversed."""
  345. # 'ab' => 'ba'
  346. node1 = ( 'ab', [ None ] )
  347. source1 = [ node1 ]
  348. node2 = ( 'ba', [ None ] )
  349. source2 = [ node2 ]
  350. self.assertEqual(make_dafsa.reverse(source1), source2)
  351. def testChain(self):
  352. """Tests that edges are reversed."""
  353. # 'a' -> 'b' => 'b' -> 'a'
  354. node2 = ( 'b', [ None ] )
  355. node1 = ( 'a', [ node2 ] )
  356. source1 = [ node1 ]
  357. node4 = ( 'a', [ None ] )
  358. node3 = ( 'b', [ node4 ] )
  359. source2 = [ node3 ]
  360. self.assertEqual(make_dafsa.reverse(source1), source2)
  361. def testInnerTerminator(self):
  362. """Tests a sequence with an inner terminator can be reversed."""
  363. # 'a' -> 'b' 'b' -> 'a'
  364. # \ => /
  365. # {sink} ------
  366. node2 = ( 'b', [ None ] )
  367. node1 = ( 'a', [ node2, None ] )
  368. source1 = [ node1 ]
  369. node4 = ( 'a', [ None ] )
  370. node3 = ( 'b', [ node4 ] )
  371. source2 = [ node3, node4 ]
  372. self.assertEqual(make_dafsa.reverse(source1), source2)
  373. def testAtomicTrie(self):
  374. """Tests a trie formed DAFSA can be reversed."""
  375. # 'b' 'b'
  376. # / \
  377. # 'a' => 'a'
  378. # \ /
  379. # 'c' 'c'
  380. node3 = ( 'c', [ None ] )
  381. node2 = ( 'b', [ None ] )
  382. node1 = ( 'a', [ node2, node3 ] )
  383. source1 = [ node1 ]
  384. node6 = ( 'a', [ None ] )
  385. node5 = ( 'c', [ node6 ] )
  386. node4 = ( 'b', [ node6 ] )
  387. source2 = [ node4, node5 ]
  388. self.assertEqual(make_dafsa.reverse(source1), source2)
  389. def testReverseAtomicTrie(self):
  390. """Tests a reverse trie formed DAFSA can be reversed."""
  391. # 'a' 'a'
  392. # \ /
  393. # 'c' => 'c'
  394. # / \
  395. # 'b' 'b'
  396. node3 = ( 'c', [ None ] )
  397. node2 = ( 'b', [ node3 ] )
  398. node1 = ( 'a', [ node3 ] )
  399. source1 = [ node1, node2 ]
  400. node6 = ( 'b', [ None ] )
  401. node5 = ( 'a', [ None ] )
  402. node4 = ( 'c', [ node5, node6 ] )
  403. source2 = [ node4 ]
  404. self.assertEqual(make_dafsa.reverse(source1), source2)
  405. def testDiamond(self):
  406. """Tests we can reverse both edges and nodes in a diamond."""
  407. # 'cd' 'dc'
  408. # / \ / \
  409. # 'ab' 'gh' => 'hg' 'ba'
  410. # \ / \ /
  411. # 'ef' 'fe'
  412. node4 = ( 'gh', [ None ] )
  413. node3 = ( 'ef', [ node4 ] )
  414. node2 = ( 'cd', [ node4 ] )
  415. node1 = ( 'ab', [ node2, node3 ] )
  416. source1 = [ node1 ]
  417. node8 = ( 'ba', [ None ] )
  418. node7 = ( 'fe', [ node8 ] )
  419. node6 = ( 'dc', [ node8 ] )
  420. node5 = ( 'hg', [ node6, node7 ] )
  421. source2 = [ node5 ]
  422. self.assertEqual(make_dafsa.reverse(source1), source2)
  423. class TopSortTest(unittest.TestCase):
  424. def testNode(self):
  425. """Tests a DAFSA with one node can be sorted."""
  426. # 'a' => [ 'a' ]
  427. node1 = ( 'a', [ None ] )
  428. source = [ node1 ]
  429. nodes = [ node1 ]
  430. self.assertEqual(make_dafsa.top_sort(source), nodes)
  431. def testDiamond(self):
  432. """Tests nodes in a diamond can be sorted."""
  433. # 'b'
  434. # / \
  435. # 'a' 'd'
  436. # \ /
  437. # 'c'
  438. node4 = ( 'd', [ None ] )
  439. node3 = ( 'c', [ node4 ] )
  440. node2 = ( 'b', [ node4 ] )
  441. node1 = ( 'a', [ node2, node3 ] )
  442. source = [ node1 ]
  443. nodes = make_dafsa.top_sort(source)
  444. self.assertLess(nodes.index(node1), nodes.index(node2))
  445. self.assertLess(nodes.index(node2), nodes.index(node4))
  446. self.assertLess(nodes.index(node3), nodes.index(node4))
  447. class EncodePrefixTest(unittest.TestCase):
  448. def testChar(self):
  449. """Tests to encode a single character prefix."""
  450. label = 'a'
  451. bytes = [ ord('a') ]
  452. self.assertEqual(make_dafsa.encode_prefix(label), bytes)
  453. def testChars(self):
  454. """Tests to encode a multi character prefix."""
  455. label = 'ab'
  456. bytes = [ ord('b'), ord('a') ]
  457. self.assertEqual(make_dafsa.encode_prefix(label), bytes)
  458. class EncodeLabelTest(unittest.TestCase):
  459. def testChar(self):
  460. """Tests to encode a single character label."""
  461. label = 'a'
  462. bytes = [ ord('a') + 0x80 ]
  463. self.assertEqual(make_dafsa.encode_label(label), bytes)
  464. def testChars(self):
  465. """Tests to encode a multi character label."""
  466. label = 'ab'
  467. bytes = [ ord('b') + 0x80, ord('a') ]
  468. self.assertEqual(make_dafsa.encode_label(label), bytes)
  469. class EncodeLinksTest(unittest.TestCase):
  470. def testEndLabel(self):
  471. """Tests to encode link to the sink."""
  472. children = [ None ]
  473. offsets = {}
  474. bytes = 0
  475. output = []
  476. self.assertEqual(make_dafsa.encode_links(children, offsets, bytes),
  477. output)
  478. def testOneByteOffset(self):
  479. """Tests to encode a single one byte offset."""
  480. node = ( '', [ None ] )
  481. children = [ node ]
  482. offsets = { id(node) : 2 }
  483. bytes = 5
  484. output = [ 132 ]
  485. self.assertEqual(make_dafsa.encode_links(children, offsets, bytes),
  486. output)
  487. def testOneByteOffsets(self):
  488. """Tests to encode a sequence of one byte offsets."""
  489. node1 = ( '', [ None ] )
  490. node2 = ( '', [ None ] )
  491. children = [ node1, node2 ]
  492. offsets = { id(node1) : 2, id(node2) : 1 }
  493. bytes = 5
  494. output = [ 129, 5 ]
  495. self.assertEqual(make_dafsa.encode_links(children, offsets, bytes),
  496. output)
  497. def testTwoBytesOffset(self):
  498. """Tests to encode a single two byte offset."""
  499. node = ( '', [ None ] )
  500. children = [ node ]
  501. offsets = { id(node) : 2 }
  502. bytes = 1005
  503. output = [ 237, 195]
  504. self.assertEqual(make_dafsa.encode_links(children, offsets, bytes),
  505. output)
  506. def testTwoBytesOffsets(self):
  507. """Tests to encode a sequence of two byte offsets."""
  508. node1 = ( '', [ None ] )
  509. node2 = ( '', [ None ] )
  510. node3 = ( '', [ None ] )
  511. children = [ node1, node2, node3 ]
  512. offsets = { id(node1) : 1002, id(node2) : 2, id(node3) : 2002 }
  513. bytes = 3005
  514. output = [ 232, 195, 232, 67, 241, 67 ]
  515. self.assertEqual(make_dafsa.encode_links(children, offsets, bytes),
  516. output)
  517. def testThreeBytesOffset(self):
  518. """Tests to encode a single three byte offset."""
  519. node = ( '', [ None ] )
  520. children = [ node ]
  521. offsets = { id(node) : 2 }
  522. bytes = 100005
  523. output = [ 166, 134, 225 ]
  524. self.assertEqual(make_dafsa.encode_links(children, offsets, bytes),
  525. output)
  526. def testThreeBytesOffsets(self):
  527. """Tests to encode a sequence of three byte offsets."""
  528. node1 = ( '', [ None ] )
  529. node2 = ( '', [ None ] )
  530. node3 = ( '', [ None ] )
  531. children = [ node1, node2, node3 ]
  532. offsets = { id(node1) : 100002, id(node2) : 2, id(node3) : 200002 }
  533. bytes = 300005
  534. output = [ 160, 134, 225, 160, 134, 97, 172, 134, 97 ]
  535. self.assertEqual(make_dafsa.encode_links(children, offsets, bytes),
  536. output)
  537. def testOneTwoThreeBytesOffsets(self):
  538. """Tests to encode offsets of different sizes."""
  539. node1 = ( '', [ None ] )
  540. node2 = ( '', [ None ] )
  541. node3 = ( '', [ None ] )
  542. children = [ node1, node2, node3 ]
  543. offsets = { id(node1) : 10003, id(node2) : 10002, id(node3) : 100002 }
  544. bytes = 300005
  545. output = [ 129, 143, 95, 97, 74, 13, 99 ]
  546. self.assertEqual(make_dafsa.encode_links(children, offsets, bytes),
  547. output)
  548. class ExamplesTest(unittest.TestCase):
  549. def testExample1(self):
  550. """Tests Example 1 from make_dafsa.py."""
  551. infile = '["https://www.example.com:8081", "http://www.example.org"]'
  552. outfile = b'\x81www.example\xae\x02\x84org\x81com:8081\x80'
  553. self.assertEqual(
  554. make_dafsa.words_to_encoded_dafsa(make_dafsa.parse_json(infile)),
  555. outfile)
  556. def testExample2(self):
  557. """Tests Example 2 from make_dafsa.py."""
  558. infile = '["https://www.example.org", "http://www.google.com"]'
  559. outfile = b'\x81www\xae\x02\x8bgoogle.com\x81example.org\x80'
  560. self.assertEqual(
  561. make_dafsa.words_to_encoded_dafsa(make_dafsa.parse_json(infile)),
  562. outfile)
  563. def testBadJSON(self):
  564. """Tests make_dafsa.py with bad JSON input."""
  565. self.assertRaises(make_dafsa.InputError, make_dafsa.parse_json, "badinput")
  566. def testInvalidProtocol(self):
  567. """Tests make_dafsa.py with an invalid protocol."""
  568. self.assertRaises(make_dafsa.InputError, make_dafsa.parse_json,
  569. '["ftp://www.example.com"]')
  570. if __name__ == '__main__':
  571. unittest.main()