emscipten_platform: do not use `append` on String

[nit.git] / contrib / nitcc / src / autom.nit

diff --git a/contrib/nitcc/src/autom.nit b/contrib/nitcc/src/autom.nit
index 79f5a0c..c86f085 100644 (file)
--- a/contrib/nitcc/src/autom.nit
+++ b/contrib/nitcc/src/autom.nit
@@ -278,6 +278,97 @@ class Automaton
                return res
        end
 
+       # Reverse an automaton in place
+       fun reverse
+       do
+               for s in states do
+                       var tmp = s.ins
+                       s.ins = s.outs
+                       s.outs = tmp
+                       for t in s.outs do
+                               var tmp2 = t.from
+                               t.from = t.to
+                               t.to = tmp2
+                       end
+               end
+               var st = start
+               if accept.length == 1 then
+                       start = accept.first
+               else
+                       var st2 = new State
+                       start = st2
+                       states.add(st2)
+
+                       for s in accept do
+                               st2.add_trans(s, null)
+                       end
+               end
+               accept.clear
+               accept.add(st)
+       end
+
+       # Generate a minimal DFA
+       # REQUIRE: self is a DFA
+       fun to_minimal_dfa: Automaton
+       do
+               var distincts = new HashMap[State, Set[State]]
+               for s in states do
+                       distincts[s] = new HashSet[State]
+               end
+
+               # split accept states
+               for s1 in states do
+                       for s2 in states do
+                               if distincts[s1].has(s2) then continue
+                               if not accept.has(s1) then continue
+                               if not accept.has(s2) then
+                                       distincts[s1].add(s2)
+                                       distincts[s2].add(s1)
+                                       continue
+                               end
+                               if tags[s1] != tags[s2] then
+                                       distincts[s1].add(s2)
+                                       distincts[s2].add(s1)
+                                       continue
+                               end
+                       end
+               end
+
+               var changed = true
+               var ints = new Array[Int]
+               while changed do
+                       changed = false
+                       for s1 in states do for s2 in states do
+                               if distincts[s1].has(s2) then continue
+                               ints.clear
+                               for t in s1.outs do
+                                       var sym = t.symbol
+                                       assert sym != null
+                                       ints.add sym.first
+                                       var l = sym.last
+                                       if l != null then ints.add l
+                               end
+                               for i in ints do
+                                       var ds1 = s1.trans(i)
+                                       var ds2 = s2.trans(i)
+                                       if ds1 == null and ds2 == null then continue
+                                       if ds1 != null and ds2 != null and not distincts[ds1].has(ds2) then continue
+                                       distincts[s1].add(s2)
+                                       distincts[s2].add(s1)
+                                       changed = true
+                                       break
+                               end
+                       end
+               end
+
+               for s1 in states do for s2 in states do
+                       if distincts[s1].has(s2) then continue
+                       s1.add_trans(s2, null)
+               end
+
+               return to_dfa
+       end
+
        # Produce a graphvis file for the automaton
        fun to_dot(filepath: String)
        do
@@ -296,6 +387,8 @@ class Automaton
                                        f.write("{token.name.escape_to_c}\\n")
                                end
                                f.write("\"")
+                       else
+                               f.write(",label=\"\"")
                        end
                        f.write("];\n")
                        var outs = new HashMap[State, Array[nullable TSymbol]]
@@ -594,6 +687,20 @@ class State
                to.ins.add(t)
                return t
        end
+
+       fun trans(i: Int): nullable State
+       do
+               for t in outs do
+                       var sym = t.symbol
+                       assert sym != null
+                       var f = sym.first
+                       var l = sym.last
+                       if i < f then continue
+                       if l != null and i > l then continue
+                       return t.to
+               end
+               return null
+       end
 end
 
 # A range of symbols on a transition