Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

submatch対応 #8 #33

Merged
merged 14 commits into from
Dec 7, 2020
Merged

submatch対応 #8 #33

merged 14 commits into from
Dec 7, 2020

Conversation

masa5555
Copy link
Collaborator

No description provided.

@masa5555
Copy link
Collaborator Author

masa5555 commented Nov 28, 2020

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

@makenowjust
Copy link
Collaborator

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

@masa5555
Copy link
Collaborator Author

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

@masa5555 masa5555 linked an issue Nov 28, 2020 that may be closed by this pull request
@masa5555 masa5555 linked an issue Nov 30, 2020 that may be closed by this pull request
@n4o847
Copy link
Owner

n4o847 commented Nov 30, 2020

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

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

@n4o847 n4o847 changed the base branch from master to fix/22-redefine-state November 30, 2020 15:26
@n4o847 n4o847 changed the base branch from fix/22-redefine-state to master November 30, 2020 15:26
@n4o847
Copy link
Owner

n4o847 commented Nov 30, 2020

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

@yapatta
Copy link
Collaborator

yapatta commented Nov 30, 2020

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

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

@masa5555
Copy link
Collaborator Author

masa5555 commented Nov 30, 2020

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

@masa5555
Copy link
Collaborator Author

偽判定残り

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

@masa5555 masa5555 requested review from n4o847 and yapatta December 2, 2020 17:34
@masa5555
Copy link
Collaborator Author

masa5555 commented Dec 2, 2020

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

@yapatta yapatta changed the base branch from master to add_attacker December 5, 2020 07:22
@yapatta yapatta changed the base branch from add_attacker to master December 5, 2020 07:22
@n4o847 n4o847 changed the base branch from master to develop December 6, 2020 05:38
src/enfa.ts Outdated
Comment on lines 30 to 33
if (
this.pattern.child.type === 'Capture' ||
this.pattern.child.type === 'Group'
) {
Copy link
Owner

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

NamedCapture の場合が抜けている気がします

@n4o847
Copy link
Owner

n4o847 commented Dec 6, 2020

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

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

@masa5555
Copy link
Collaborator Author

masa5555 commented Dec 6, 2020

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

@masa5555
Copy link
Collaborator Author

masa5555 commented Dec 6, 2020

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

Copy link
Collaborator

@yapatta yapatta left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

レビューが遅くなってしまい申し訳ないです!
先程述べてくださった/^$/は、childがSequenceであり286行目のelseを通ることとViz表示がうまくいっていることから正しく判定されていると思います!
次に^$が端にないときなどのbuildChild内で投げられた例外をちゃんと処理していなかった(これは自分の責任)ので何かしら例外処理いいの考えたいですね。

src/enfa.ts Outdated
) {
// 遷移を削除
this.transitions = this.transitions.filter(
([s, n, d]) => s !== source || n !== node || d !== dest,
Copy link
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Suggested change
([s, n, d]) => s !== source || n !== node || d !== dest,
([s, n, d]) => !(s === source && n === node && d === dest),

もしよければここも変えてほしいです

src/enfa.ts Outdated
) {
// 元の遷移を削除
this.transitions = this.transitions.filter(
([s, n, d]) => s !== source || n !== node || d !== dest,
Copy link
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Suggested change
([s, n, d]) => s !== source || n !== node || d !== dest,
([s, n, d]) => !(s === source && n === node && d === dest),

これ初期状態からpatChildへの遷移を消すという意味だと思うのですが意図が伝わりやすいようにこっちの方が良さそうです(完全に僕の好みですが)

Copy link
Collaborator Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

確かに、そのほうが可読性が高いと思いました。ありがとうございます

@yapatta yapatta merged commit 7d2787a into develop Dec 7, 2020
@yapatta yapatta deleted the submatch branch December 7, 2020 11:46
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

サブマッチに対応する
4 participants