make_dafsa_unittest.py 23 KB

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