summaryrefslogtreecommitdiffstats
path: root/xpcom/ds/test
diff options
context:
space:
mode:
Diffstat (limited to 'xpcom/ds/test')
-rw-r--r--xpcom/ds/test/python.ini4
-rw-r--r--xpcom/ds/test/test_dafsa.py546
2 files changed, 550 insertions, 0 deletions
diff --git a/xpcom/ds/test/python.ini b/xpcom/ds/test/python.ini
new file mode 100644
index 0000000000..680185c496
--- /dev/null
+++ b/xpcom/ds/test/python.ini
@@ -0,0 +1,4 @@
+[DEFAULT]
+subsuite = xpcom
+
+[test_dafsa.py]
diff --git a/xpcom/ds/test/test_dafsa.py b/xpcom/ds/test/test_dafsa.py
new file mode 100644
index 0000000000..9becdd6c06
--- /dev/null
+++ b/xpcom/ds/test/test_dafsa.py
@@ -0,0 +1,546 @@
+# This Source Code Form is subject to the terms of the Mozilla Public
+# License, v. 2.0. If a copy of the MPL was not distributed with this
+# file, You can obtain one at http://mozilla.org/MPL/2.0/.
+
+import unittest
+from io import StringIO
+
+import mozunit
+from incremental_dafsa import Dafsa, Node
+
+
+def _node_to_string(node: Node, prefix, buffer, cache):
+ if not node.is_end_node:
+ prefix += (
+ str(ord(node.character)) if ord(node.character) < 10 else node.character
+ )
+ else:
+ prefix += "$"
+ cached = cache.get(id(node))
+ buffer.write("{}{}".format(prefix, "=" if cached else "").strip() + "\n")
+
+ if not cached:
+ cache[id(node)] = node
+ if node:
+ for node in sorted(node.children.values(), key=lambda n: n.character):
+ _node_to_string(node, prefix, buffer, cache)
+
+
+def _dafsa_to_string(dafsa: Dafsa):
+ """Encodes the dafsa into a string notation.
+
+ Each node is printed on its own line with all the nodes that precede it.
+ The end node is designated with the "$" character.
+ If it joins into an existing node, the end of the line is adorned with a "=".
+ Though this doesn't carry information about which other prefix it has joined with,
+ it has seemed to be precise enough for testing.
+
+ For example, with the input data of:
+ * a1
+ * ac1
+ * bc1
+
+ [root] --- a ---- 1 --- [end]
+ | | /
+ -- b -- c---
+
+ The output will be:
+ a
+ a1
+ a1$ <- end node was found
+ ac
+ ac1= <- joins with the "a1" prefix
+ b
+ bc= <- joins with the "ac" prefix
+ """
+ buffer = StringIO()
+ cache = {}
+
+ for node in sorted(dafsa.root_node.children.values(), key=lambda n: n.character):
+ _node_to_string(node, "", buffer, cache)
+ return buffer.getvalue().strip()
+
+
+def _to_words(data):
+ return [line.strip() for line in data.strip().split("\n")]
+
+
+def _assert_dafsa(data, expected):
+ words = _to_words(data)
+ dafsa = Dafsa.from_tld_data(words)
+
+ expected = expected.strip()
+ expected = "\n".join([line.strip() for line in expected.split("\n")])
+ as_string = _dafsa_to_string(dafsa)
+ assert as_string == expected
+
+
+class TestDafsa(unittest.TestCase):
+ def test_1(self):
+ _assert_dafsa(
+ """
+ a1
+ ac1
+ acc1
+ bd1
+ bc1
+ bcc1
+ """,
+ """
+ a
+ a1
+ a1$
+ ac
+ ac1=
+ acc
+ acc1=
+ b
+ bc=
+ bd
+ bd1=
+ """,
+ )
+
+ def test_2(self):
+ _assert_dafsa(
+ """
+ ab1
+ b1
+ bb1
+ bbb1
+ """,
+ """
+ a
+ ab
+ ab1
+ ab1$
+ b
+ b1=
+ bb
+ bb1=
+ bbb=
+ """,
+ )
+
+ def test_3(self):
+ _assert_dafsa(
+ """
+ a.ca1
+ a.com1
+ c.corg1
+ b.ca1
+ b.com1
+ b.corg1
+ """,
+ """
+ a
+ a.
+ a.c
+ a.ca
+ a.ca1
+ a.ca1$
+ a.co
+ a.com
+ a.com1=
+ b
+ b.
+ b.c
+ b.ca=
+ b.co
+ b.com=
+ b.cor
+ b.corg
+ b.corg1=
+ c
+ c.
+ c.c
+ c.co
+ c.cor=
+ """,
+ )
+
+ def test_4(self):
+ _assert_dafsa(
+ """
+ acom1
+ bcomcom1
+ acomcom1
+ """,
+ """
+ a
+ ac
+ aco
+ acom
+ acom1
+ acom1$
+ acomc
+ acomco
+ acomcom
+ acomcom1=
+ b
+ bc
+ bco
+ bcom
+ bcomc=
+ """,
+ )
+
+ def test_5(self):
+ _assert_dafsa(
+ """
+ a.d1
+ a.c.d1
+ b.d1
+ b.c.d1
+ """,
+ """
+ a
+ a.
+ a.c
+ a.c.
+ a.c.d
+ a.c.d1
+ a.c.d1$
+ a.d=
+ b
+ b.=
+ """,
+ )
+
+ def test_6(self):
+ _assert_dafsa(
+ """
+ a61
+ a661
+ b61
+ b661
+ """,
+ """
+ a
+ a6
+ a61
+ a61$
+ a66
+ a661=
+ b
+ b6=
+ """,
+ )
+
+ def test_7(self):
+ _assert_dafsa(
+ """
+ a61
+ a6661
+ b61
+ b6661
+ """,
+ """
+ a
+ a6
+ a61
+ a61$
+ a66
+ a666
+ a6661=
+ b
+ b6=
+ """,
+ )
+
+ def test_8(self):
+ _assert_dafsa(
+ """
+ acc1
+ bc1
+ bccc1
+ """,
+ """
+ a
+ ac
+ acc
+ acc1
+ acc1$
+ b
+ bc
+ bc1=
+ bcc=
+ """,
+ )
+
+ def test_9(self):
+ _assert_dafsa(
+ """
+ acc1
+ bc1
+ bcc1
+ """,
+ """
+ a
+ ac
+ acc
+ acc1
+ acc1$
+ b
+ bc
+ bc1=
+ bcc=
+ """,
+ )
+
+ def test_10(self):
+ _assert_dafsa(
+ """
+ acc1
+ cc1
+ cccc1
+ """,
+ """
+ a
+ ac
+ acc
+ acc1
+ acc1$
+ c
+ cc
+ cc1=
+ ccc=
+ """,
+ )
+
+ def test_11(self):
+ _assert_dafsa(
+ """
+ ac1
+ acc1
+ bc1
+ bcc1
+ """,
+ """
+ a
+ ac
+ ac1
+ ac1$
+ acc
+ acc1=
+ b
+ bc=
+ """,
+ )
+
+ def test_12(self):
+ _assert_dafsa(
+ """
+ acd1
+ bcd1
+ bcdd1
+ """,
+ """
+ a
+ ac
+ acd
+ acd1
+ acd1$
+ b
+ bc
+ bcd
+ bcd1=
+ bcdd=
+ """,
+ )
+
+ def test_13(self):
+ _assert_dafsa(
+ """
+ ac1
+ acc1
+ bc1
+ bcc1
+ bccc1
+ """,
+ """
+ a
+ ac
+ ac1
+ ac1$
+ acc
+ acc1=
+ b
+ bc
+ bc1=
+ bcc=
+ """,
+ )
+
+ def test_14(self):
+ _assert_dafsa(
+ """
+ acc1
+ acccc1
+ bcc1
+ bcccc1
+ bcccccc1
+ """,
+ """
+ a
+ ac
+ acc
+ acc1
+ acc1$
+ accc
+ acccc
+ acccc1=
+ b
+ bc
+ bcc
+ bcc1=
+ bccc=
+ """,
+ )
+
+ def test_15(self):
+ _assert_dafsa(
+ """
+ ac1
+ bc1
+ acac1
+ """,
+ """
+ a
+ ac
+ ac1
+ ac1$
+ aca
+ acac
+ acac1=
+ b
+ bc=
+ """,
+ )
+
+ def test_16(self):
+ _assert_dafsa(
+ """
+ bat1
+ t1
+ tbat1
+ """,
+ """
+ b
+ ba
+ bat
+ bat1
+ bat1$
+ t
+ t1=
+ tb=
+ """,
+ )
+
+ def test_17(self):
+ _assert_dafsa(
+ """
+ acow1
+ acat1
+ t1
+ tcat1
+ acatcat1
+ """,
+ """
+ a
+ ac
+ aca
+ acat
+ acat1
+ acat1$
+ acatc
+ acatca
+ acatcat
+ acatcat1=
+ aco
+ acow
+ acow1=
+ t=
+ """,
+ )
+
+ def test_18(self):
+ _assert_dafsa(
+ """
+ bc1
+ abc1
+ abcxyzc1
+ """,
+ """
+ a
+ ab
+ abc
+ abc1
+ abc1$
+ abcx
+ abcxy
+ abcxyz
+ abcxyzc
+ abcxyzc1=
+ b
+ bc=
+ """,
+ )
+
+ def test_19(self):
+ _assert_dafsa(
+ """
+ a.z1
+ a.y1
+ c.z1
+ d.z1
+ d.y1
+ """,
+ """
+ a
+ a.
+ a.y
+ a.y1
+ a.y1$
+ a.z
+ a.z1=
+ c
+ c.
+ c.z=
+ d
+ d.=
+ """,
+ )
+
+ def test_20(self):
+ _assert_dafsa(
+ """
+ acz1
+ acy1
+ accz1
+ acccz1
+ bcz1
+ bcy1
+ bccz1
+ bcccz1
+ """,
+ """
+ a
+ ac
+ acc
+ accc
+ acccz
+ acccz1
+ acccz1$
+ accz=
+ acy
+ acy1=
+ acz=
+ b
+ bc=
+ """,
+ )
+
+
+if __name__ == "__main__":
+ mozunit.main()