State の定義を string に変更

n4o847 commented 3 years ago

たびたび問題になっていたことなので、 State の定義を変更します。

今のところ最低限の部分を置き換えただけです。State がプリミティブになることでアルゴリズム的に改善できる部分があれば、このブランチ上で改善していってもいいかなと思います。

定義が string & { ～ } みたいになってるのは branded types と呼ばれる通常の string と区別するための手法なんですが、過剰な気もする……？のでなくしてもいいです。

関連: #18

n4o847 commented 3 years ago

なお State を string にしたところで、古い State の集合・タプルと新しい State の対応を得るときに

文字列的処理によって分解・結合する
対応を Map などで持っておき、変換する

の2通りの方法があると思います。現状 DirectProductNFA では前者、TripleDirectProductNFA と DFA では後者ですかね。

yapatta commented 3 years ago

僕も同上です

yapatta commented 3 years ago

なお State を string にしたところで、古い State の集合・タプルと新しい State の対応を得るときに

文字列的処理によって分解・結合する

対応を Map などで持っておき、変換する

の2通りの方法があると思います。現状 DirectProductNFA では前者、TripleDirectProductNFA と DFA では後者ですかね。

統一しましょうか、対応をMapで持つと仕様変更に強いと思いますが、これから状態をstringから変えることがないなら文字列分解が楽で高速だなという悩みですね..

n4o847 commented 3 years ago

なお State を string にしたところで、古い State の集合・タプルと新しい State の対応を得るときに

文字列的処理によって分解・結合する

対応を Map などで持っておき、変換する

の2通りの方法があると思います。現状 DirectProductNFA では前者、TripleDirectProductNFA と DFA では後者ですかね。

統一しましょうか、対応をMapで持つと仕様変更に強いと思いますが、これから状態をstringから変えることがないなら文字列分解が楽で高速だなという悩みですね..

まさにそこですね。

今回考えるのはたしか「状態」、「状態の集合」、「状態のタプル」、「状態と状態の集合のタプル」の場合だけでいいので、フォーマットをちゃんと定めることで文字列操作に振り切るのが楽ならそうしましょうかね。

枝刈りで DFA を使うときは集合のフォーマット方法についても考える必要があるかもしれませんが、そのとき考えましょうか。

yapatta commented 3 years ago

そうですね、今現在枝切りが実装できていないので予想ですが、デバッグ時にDFA表示をしたいなと思っており、 q1_q2_q3_q5みたいな感じでDFAの状態を持っておいた方が楽な気がしてきて、それなら表記が統一できるので文字列操作に振り切ってもいいなと思いました。(枝切りやってみてもう一度話しましょう)

n4o847 / seccamp-redos

State の定義を string に変更 #19