submatch対応 #8 - Githubissues

masa5555 commented 3 years ago

（seqenceじゃない場合に）確認ミスでまだできてませんでした。。。。

makenowjust commented 3 years ago

node.range で末尾かどうかを判断すると /^a|b$/ のような場合に問題になります。(これはaから始まる文字列かbで終わる文字列にマッチします) ε-NFAの構築と同時に求めるのは不可能なので、パターンの意味的な先頭(末尾)に^($)があるかどうかを判定するような関数を書いて、ε-NFA構築の必要な辺を追加するようにするといいと多います。

masa5555 commented 3 years ago

確かにそうですね。。。ありがとうございます！

n4o847 commented 3 years ago

差分を見るなら https://github.com/n4o847/seccamp-redos/compare/submatch とかですかね

プルリクがこんなんなってることの解消法は、わからず……

n4o847 commented 3 years ago

ぽちぽちいじってたらいい感じになりました

yapatta commented 3 years ago

masterとの差分がうまく表示されないことを防ぐために, 自分の編集ブランチをpushする前に, masterブランチでgit pullした後に自分の編集ブランチでgit merge masterをやってからpushしているのですが, このお作法自ブランチを最新にする+プルリクで差分をきれいに表示する効能があったのですが後者の効能がどうして働くかよくわかっていなかったんですよね

根本君の件で気になって調べたところ, プルリクのFile Changedがマージベースとの差分を表示しているらしくて, それでマージベースを調べたら, 最新のmasterのコミット番号b3a261ec3536128dd973a718d928866f3ad40e8fだったので, 現在のmasterとの差分が正しく表示されずに不思議に思いました. 三浦くんがプルリクのマージ先を一度変えてまた戻したら正しく差分が表示されたということは何かしらの誤検知とかだったんですかね..

masa5555 commented 3 years ago

なるほど、ありがたいです。 /a/ のときに上手く動いていなかったので直しますというか非貪欲と貪欲が逆になってました

masa5555 commented 3 years ago

偽判定残り

/(a|b)*$/ false negative (IDA)
/(a*)*/ false positive (EDA)
/(a+)+/ false positive (EDA & IDA) この種類の遷移の作り方を間違っていそう

masa5555 commented 3 years ago

これまでに行っていた方法は間違っていたので大幅に変更し、 /pattern/ が入力のときに、/.*?pattern.*/のε-NFAと同等のオートマトンが構成されるようにしました。テストケースはすべて確認したので、内容的にはこれで大丈夫だと思います。

n4o847 commented 3 years ago

^$ でエラーになる
^ や $ が変な位置にあるものはスルーしてしまう

まあそんな正規表現あんまり無いだろうということで放っといてもいい気もします

masa5555 commented 3 years ago

細かい所まで見ていただきありがたいです。 NamedCapture, ^$が端にない場合はすぐ直せそうです。 /^$/はそれ単体で例外処理する以外思いつきませんね。。。

masa5555 commented 3 years ago

sequenceの処理順を少し変えたら、/^$/にも対応できた気がしています

n4o847 / seccamp-redos

submatch対応 #8 #33