Repository: mhulden/pyfoma

Issue:
pyfoma's AT&T format is not understood by foma
pyfoma uses some shortcuts when outputting AT&T format which are not really part of the AT&T format, might not be accepted by OpenFST, and definitely aren't accepted by foma, namely:

- epsilon labels are just the empty string
- transitions without transduction only output one label (even if the machine is otherwise a transducer ... thus `fstcompile --acceptor` won't work)

Since there isn't any universal standard for what to call epsilon (OpenFST just uses index 0 in the symbol table, whatever it happens to correspond to, while foma seems to use `@0@`) probably there should be an actual method for outputting AT&T format along with symbol tables.

Hints from issue comments:
@dhdaines: (I will have a PR for this ... though the actual reason I want it is to use `foma2js.perl` so perhaps I'll reimplement that as well)@dhdaines: (reference for the format as understood by OpenFST: https://www.openfst.org/twiki/bin/view/FST/FstQuickTour#Creating%20FSTs%20Using%20Text%20Files%20f)

Solution patch:
diff --git a/src/pyfoma/fst.py b/src/pyfoma/fst.py
index 4aaa371..22547da 100644
--- a/src/pyfoma/fst.py
+++ b/src/pyfoma/fst.py
@@ -2,9 +2,11 @@
 
 """PyFoma Finite-State Tool."""
 
-import heapq, operator, itertools, re as pyre, functools
+import heapq, json, itertools, re as pyre
 from collections import deque, defaultdict
-from typing import Callable, Dict, Any, Iterable
+from typing import Callable, Dict, Any, Iterable, TextIO
+from os import PathLike
+from pathlib import Path
 from pyfoma.flag import FlagStringFilter, FlagOp
 import subprocess
 import pickle
@@ -201,6 +203,100 @@ class FST:
         with open(path, 'rb') as f:
             fst = pickle.load(f)
         return fst
+
+    def save_att(self, base: PathLike[str], state_symbols=False, epsilon="@0@"):
+        """Save to AT&T format files for use with other FST libraries
+        (Foma, OpenFST, RustFST, HFST, etc).
+
+        This will, in addition to saving the transitions in `base`,
+        also create separate files with the extensions `.isyms` and
+        `.osyms` containing the input and output symbol tables (so for
+        example if base is `test.fst`, it will create `test.isyms` and
+        `test.osyms`)
+
+        Note also that the AT&T format has no mechanism for
+        quoting or escaping characters (notably whitespace) in symbols
+        and state names, but only tabs are used as field separators by
+        default, so any other characters should be acceptable (though
+        not always recommended).  The symbol `@0@` is used by default
+        for epsilon (but can be changed with the `epsilon` parameter)
+        as this is Foma's default, and will always have symbol ID 0 as
+        this is required by OpenFST.
+
+        If `state_symbols` is true, the names of states will be
+        retained in the output file and a state symbol table created
+        with the extension `.ssyms`.  This option is disabled by
+        default since it is not compatible with Foma.
+        """
+        path = Path(base)
+        ssympath = path.with_suffix(".ssyms")
+        isympath = path.with_suffix(".isyms")
+        osympath = path.with_suffix(".osyms")
+        # Number all states and create state symbol table
+        if state_symbols:
+            ssyms = [self.initialstate.name]
+        else:
+            ssyms = ["0"]
+        ssymtab = {id(self.initialstate): ssyms[0]}
+        for s in self.states:
+            if s == self.initialstate:
+                continue
+            if s.name is None or not state_symbols:
+                name = str(len(ssyms))
+            else:
+                name = s.name
+            ssymtab[id(s)] = name
+            ssyms.append(name)
+        if state_symbols:
+            with open(ssympath, "wt") as outfh:
+                for idx, name in enumerate(ssyms):
+                    print(f"{name}\t{idx}", file=outfh)
+        # Do a second pass to output the FST itself (we will always have
+        # to do this because of the need to number states)
+        isyms = {epsilon: 0}
+        osyms = {epsilon: 0}
+
+        def output_state(s: State, outfh: TextIO):
+            name = ssymtab[id(s)]
+            for label, arcs in s.transitions.items():
+                if len(label) == 1:
+                    isym = osym = (label[0] or epsilon)
+                else:
+                    isym, osym = ((x or epsilon) for x in label)
+                if isym not in isyms:
+                    isyms[isym] = len(isyms)
+                if osym not in osyms:
+                    osyms[osym] = len(osyms)
+                for transition in arcs:
+                    dest = ssymtab[id(transition.targetstate)]
+                    fields = [
+                        name,
+                        dest,
+                        isym,
+                        osym,
+                    ]
+                    if transition.weight != 0.0:
+                        fields.append(transition.weight)
+                    print("\t".join(fields), file=outfh)
+            # NOTE: These are not required to be at the end of the file
+            if s in self.finalstates:
+                name = ssymtab[id(s)]
+                if s.finalweight != 0.0:
+                    print(f"{name}\t{s.finalweight}", file=outfh)
+                else:
+                    print(name, file=outfh)
+
+        with open(path, "wt") as outfh:
+            output_state(self.initialstate, outfh)
+            for s in self.states:
+                if s != self.initialstate:
+                    output_state(s, outfh)
+        with open(isympath, "wt") as outfh:
+            for name, idx in isyms.items():
+                print(f"{name}\t{idx}", file=outfh)
+        with open(osympath, "wt") as outfh:
+            for name, idx in osyms.items():
+                print(f"{name}\t{idx}", file=outfh)
     # endregion
 
 
@@ -224,9 +320,15 @@ class FST:
         for s in self.states:
             if len(s.transitions) > 0:
                 for label in s.transitions.keys():
+                    if len(label) == 1:
+                        att_label = (label[0], label[0])
+                    else:
+                        att_label = label
+                    # You get Foma's default here since it cannot be configured
+                    att_label = ["@0@" if sym == "" else sym for sym in att_label]
                     for transition in s.transitions[label]:
                         st += '{}\t{}\t{}\t{}\n'.format(statenums[id(s)],\
-                        statenums[id(transition.targetstate)], '\t'.join(label),\
+                        statenums[id(transition.targetstate)], '\t'.join(att_label),\
                         transition.weight)
         for s in self.states:
             if s in self.finalstates:
@@ -491,6 +593,68 @@ class FST:
             tokens.append(t)
             start += len(t)
         return tokens
+
+    def todict(self, utf16_maxlen=False) -> Dict[str, Any]:
+        """Create a dictionary form of the FST for export to
+        JSON/Javascript.  If it will ultimately be used by Javascript,
+        pass `utf16_maxlen=True`."""
+        # (re-)number all the states making sure the initial state is 0
+        # (the Javascript code depends on this, all other state numbers
+        # are arbitrary strings)
+        statenums = {id(self.initialstate): 0}
+        for s in self.states:
+            if s == self.initialstate:
+                continue
+            statenums[id(s)] = len(statenums)
+        # No need to hold out the initial state since it has number 0
+        transitions = {}
+        finals = {}
+        alphabet = {}
+        maxlen = 0
+        for s in self.states:
+            src = statenums[id(s)]
+            for label, arcs in s.transitions.items():
+                if len(label) == 1:
+                    isym = osym = label[0]
+                else:
+                    isym, osym = label
+                for sym in isym, osym:
+                    # Omit epsilon from symbol table
+                    if sym == "":
+                        continue
+                    if sym not in alphabet:
+                        # Reserve 0, 1, 2 for epsilon, identity, unknown
+                        alphabet[sym] = 3 + len(alphabet)
+                        # For Javascript we will recompute this based on
+                        # evil UTF-16
+                        maxlen = max(maxlen, len(sym))
+                # Nothing to do to the symbols beyond that as pyfoma
+                # already uses the same convention of epsilon='', and JSON
+                # encoding will take care of escaping everything for us
+                transitions.setdefault(f"{src}|{isym}", []).extend(
+                    # Note, weights are ignored...
+                    {statenums[id(arc.targetstate)]: osym} for arc in arcs
+                )
+            if s in self.finalstates:
+                finals[src] = 1
+        if utf16_maxlen:
+            # Note utf-16le because we do not want a valuable BOM
+            maxlen = max(len(k.encode('utf-16le')) for k in alphabet) // 2
+        return {
+            "t": transitions,
+            "s": alphabet,
+            "f": finals,
+            "maxlen": maxlen,
+        }
+
+    def tojson(self, utf16_maxlen=False) -> str:
+        """Create JSON (which is also Javascript) for an FST for use with
+        `foma_apply_down.js`"""
+        return json.dumps(self.todict(utf16_maxlen=utf16_maxlen), ensure_ascii=False)
+
+    def tojs(self, jsnetname: str = "myNet") -> str:
+        """Create Javascript compatible with `foma2js.perl`"""
+        return " ".join(("var", jsnetname, "=", self.tojson(utf16_maxlen=True), ";"))
     # endregion
 
 


Test patch:
diff --git a/test_pyfoma.py b/test_pyfoma.py
index e6ccae0..8521046 100644
--- a/test_pyfoma.py
+++ b/test_pyfoma.py
@@ -1,9 +1,11 @@
 import unittest
+from pathlib import Path
+from tempfile import TemporaryDirectory
 from pyfoma import algorithms
 from pyfoma.fst import FST
 
 class TestFST(unittest.TestCase):
-
+    """Test basic FST functionality"""
     def test_rewrite(self):
         f1 = FST.re("$^rewrite((ab):x / a b _ a)")
         self.assertEqual(set(f1.generate("abababa")), {"abxxa"})
@@ -124,6 +126,7 @@ class TestFST(unittest.TestCase):
 
 
 class TestSymbols(unittest.TestCase):
+    """Test multi-character symbol feature"""
     MULTICHAR_SYMBOLS = "u: ch ll x̌ʷ".split()
 
     def test_rlg(self):
@@ -201,5 +204,82 @@ class TestSymbols(unittest.TestCase):
         self.assertEqual("xux̌ʷ", next(rule.generate("xux̌ʷ")))
 
 
+class TestUtil(unittest.TestCase):
+    """Test utility functions."""
+    fst = FST.regex(r"'[NO\'UN]' '[VERB]' (cat):(dog)? 'ROTFLMAO🤣'")
+
+    def verify_att_format(self, att, epsilon="@0@"):
+        """Verify some expected states and such in AT&T FST"""
+        self.assertIn("[NO'UN]\t[NO'UN]", att)
+        self.assertIn("[VERB]\t[VERB]", att)
+        self.assertIn(f"c\t{epsilon}", att)
+        self.assertIn(f"a\t{epsilon}", att)
+        self.assertIn(f"t\t{epsilon}", att)
+        self.assertIn("c\td", att)
+        self.assertIn("a\to", att)
+        self.assertIn("t\tg", att)
+
+    def test_to_str(self):
+        """Test simple AT&T format conversion."""
+        att = str(self.fst)
+        self.verify_att_format(att)
+
+    def test_to_att(self):
+        """Test more complete AT&T format conversion."""
+        with TemporaryDirectory() as tempdir:
+            path = Path(tempdir)
+            f = self.fst
+            # Verify expected path behaviour
+            f.save_att(path / "test")
+            self.assertTrue((path / "test").exists())
+            self.assertTrue((path / "test.isyms").exists())
+            self.assertTrue((path / "test.osyms").exists())
+            f.save_att(path / "test.att", epsilon="<eps>")
+            self.assertTrue((path / "test.att").exists())
+            self.assertTrue((path / "test.isyms").exists())
+            self.assertTrue((path / "test.osyms").exists())
+            # Now verify contents
+            with open(path / "test.att", "rt") as infh:
+                att = infh.read()
+                self.verify_att_format(att, epsilon="<eps>")
+                # If you have OpenFST you can verify this with:
+                #   fstcompile --isymbols=test.isyms \
+                #      --osymbols=test.osyms --keep_isymbols \
+                #      --keep_osymbols --keep_state_numbering \
+                #      test.att  | fstprint
+            # Check state symbols get output too
+            f = FST.rlg({"Root": [("", "Sublex")],
+                         "Sublex": [(("foo", "bar"), "#")]}, "Root")
+            f.save_att(path / "test_st.fst", state_symbols=True)
+            self.assertTrue((path / "test_st.fst").exists())
+            self.assertTrue((path / "test_st.isyms").exists())
+            self.assertTrue((path / "test_st.osyms").exists())
+            self.assertTrue((path / "test_st.ssyms").exists())
+            with open(path / "test_st.fst", "rt") as infh:
+                att = infh.read()
+                self.assertIn("Root\tSublex\t@0@\t@0@", att)
+                self.assertIn("#\n", att)
+                # If you have OpenFST you can verify this with:
+                #   fstcompile --ssymbols=test_st.ssyms \
+                #      --isymbols=test_st.isyms \
+                #      --osymbols=test_st.osyms --keep_isymbols \
+                #      --keep_osymbols --keep_state_numbering \
+                #      test_st.fst | fstprint
+
+    def test_to_js_on(self):
+        d = self.fst.todict()
+        # Sensible Python definition of "character"
+        # len('ROTFLMAO🤣') == 9
+        self.assertEqual(d["maxlen"], 9)
+        # Nonsense Java(script)? definition of "character"
+        # 'ROTFLMAO🤣'.length === 10
+        d = self.fst.todict(utf16_maxlen=True)
+        self.assertEqual(d["maxlen"], 10)
+        js = self.fst.tojs()
+        self.assertIn('"maxlen": 10', js)
+        # As to whether the Javascript is correct... you're on your
+        # own (don't ask the browser)
+
+
 if __name__ == "__main__":
     unittest.main()