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

新正規表現エンジンで後方参照を使っていると正しくマッチしない場合がある #479

Closed
rhysd opened this issue Oct 9, 2013 · 28 comments

Comments

@rhysd
Copy link

rhysd commented Oct 9, 2013

問題点

"aba" =~# '^\(.\+\).*\1$'

set re=1 のとき \1a にマッチしますが,set re=0 または set re=2 のときはマッチしないようです.

"aa" =~# '^\(.\+\).*\1$'

は問題なくマッチするので,グループ化部分と後方参照部分の間に何か文字が挟まるとマッチしなくなる気がしています(推測)

再現環境

  • Ubuntu 12.04
  • Vim 7.4-45
@koron
Copy link
Member

koron commented Oct 9, 2013

パターンから考えるにバックトラックからNFAに変わったせいだよね。
ただ本当はそういう正規表現は書くべきではないんだけどね…
(そもそも厳密には正規表現とは言えないし)

とりあえず問題を避けるだけなら /\%#=1 を足すのオススメ。

@rhysd
Copy link
Author

rhysd commented Oct 9, 2013

パターンから考えるにバックトラックからNFAに変わったせいだよね。

正規表現エンジン周りについて知識が無いのですが,re=0re=1 で挙動が違うのはバグと見て良いんでしょうか?

ただ本当はそういう正規表現は書くべきではないんだけどね…
(そもそも厳密には正規表現とは言えないし)

確かにそれはおっしゃる通りですね…

とりあえず問題を避けるだけなら /%#=1 を足すのオススメ。

とりあえずはそれで対処しようと思います.
ちなみに,'re'/\%#= が実装されているかどうかってどうやってチェックできますでしょうか? :help 're':help /\%#= 見た限りでは載っていないようなのですが…

@osyo-manga
Copy link

とりあえず問題を避けるだけなら /%#=1 を足すのオススメ。

とりあえずはそれで対処しようと思います.
ちなみに,'re' や /%#= が実装されているかどうかってどうやってチェックできますでしょうか? :help 're' や :help /%#= 見た限りでは載っていないようなのですが…

're'exists('+regexpengine') で判定すればよいと思います。

@rhysd
Copy link
Author

rhysd commented Oct 9, 2013

おお,ありがとうございます.とりあえずのほうはそれでいきます.

ちなみに,この件はバグ報告したほうが良いでしょうか?

@osyo-manga
Copy link

パターンから考えるにバックトラックからNFAに変わったせいだよね。

正規表現エンジン周りについて知識が無いのですが,re=0 と re=1 で挙動が違うのはバグと見て良いんでしょうか?

re=0 の場合は自動的にエンジンが選択されるので(re=1 の場合もあれば re=2 の場合もある)挙動を比較するのであれば re=1re=2 の場合の挙動を比較するのが正しいような気がします。

@k-takata
Copy link
Member

k-takata commented Oct 9, 2013

ちなみに,この件はバグ報告したほうが良いでしょうか?

した方が良いと思います。

re=0 の場合は自動的にエンジンが選択されるので

7.4.029 で re=0 と re=2 は同じになってしまったのではないかと思います。

@rhysd
Copy link
Author

rhysd commented Oct 9, 2013

うーむ,NFA エンジンは未実装の機能とかもあるらしいので,re=1re=2 で結果に差異があるのは問題ない気も…
re=0 が,"使える時のみ NFA エンジンを使う"設定なのなら,re=0re=1 の挙動が一致していないといけないと思ったのですが,どうなんでしょう.

@rhysd
Copy link
Author

rhysd commented Oct 9, 2013

した方が良いと思います。

承知しました.
時間あるときに文面考えてみるので,どなたかざっとレビューしていただけると嬉しいです.

@osyo-manga
Copy link

re=0 の場合は自動的にエンジンが選択されるので

7.4.029 で re=0 と re=2 は同じになってしまったのではないかと思います。

oh! そうなのですか…。

うーむ,NFA エンジンは未実装の機能とかもあるらしいので,re=1re=2 で結果に差異があるのは問題ない気も…
re=0 が使える時のみ NFA エンジンを使う設定なのなら,re=0re=1 の挙動が一致していないといけないと思ったのですが,どうなんでしょう.

なるほど。そういう事であれば @rhysd さんの比較が正しいですね。
失礼しました。

@k-takata
Copy link
Member

k-takata commented Oct 9, 2013

https://groups.google.com/d/msg/vim_dev/HcZVZT7fQno/ID_SndJv6CcJ

The retry with the backtracking engine used to be for when the NFA
engine could not handle the pattern. This no longer exists, the NFA
only fails when the pattern is invalid or it runs out of memory.

I think we can just drop the retry, it will never work. Perhaps some
day we'll find a mechanism to use the backtracking when it is expected
to be faster for the specific pattern, thus we don't need to remove the
"0" value of 'regexpengine'.

@rhysd
Copy link
Author

rhysd commented Oct 9, 2013

いえ,ありがとうございます.
vim_dev 漁り中…
いくつかの issue みた感じ,ここのトピックをそのまま訳せば済む感じでしょうか

@rhysd
Copy link
Author

rhysd commented Oct 9, 2013

@k-takata おお,ありがとうございます.確かに re=0re=2 は同じ意味になっているっぽいですね…

@rhysd
Copy link
Author

rhysd commented Oct 9, 2013

Backward reference fails in some cases
======================================

Hello.

* Problem

    "aba" =~# '^\(.\+\).*\1$'

This expression is equivalent to 1 when 'regexpengine' is set to 1.
However, when it is set to 0 or 2, the expression is equivalent to 0.

Backward reference seems to fail.
The reason seems to be that the retry with backtracking engine has been removed, which means 're=0' is equivalent to 're=2'.
https://groups.google.com/forum/#!msg/vim_dev/HcZVZT7fQno/ID_SndJv6CcJ

Note that below expression gets 1 whatever the value of 'regexpengine' is.

    "aa" =~# '^\(.\+\).*\1$'

* Environment
- Vim 7.4-45
- Ubuntu 12.04


Regards,
{my name}

こんな感じでどうでしょう.

@k-takata
Copy link
Member

k-takata commented Oct 9, 2013

The reason seems to be that the retry with backtracking engine has been removed, which means 're=0' is equivalent to 're=2'.
https://groups.google.com/forum/#!msg/vim_dev/HcZVZT7fQno/ID_SndJv6CcJ

ここは違うと思います。
削除された機能は、NFAエンジンで正規表現のコンパイルに失敗したときに、BTエンジンでコンパイルし直すというものです。今回のパターンはNFAエンジンでのコンパイルは通っています。

@rhysd
Copy link
Author

rhysd commented Oct 9, 2013

レビューありがとうございます.
なるほど.思い違いをしていました.
ではその行と URL を削って,

Backward reference fails in some cases
    ======================================

Hello.

* Problem

    "aba" =~# '^\(.\+\).*\1$'

This expression is equivalent to 1 when 'regexpengine' is set to 1.
However, when it is set to 0 or 2, the expression is equivalent to 0.
Backward reference seems to fail.

Note that below expression gets 1 whatever the value of 'regexpengine' is.

    "aa" =~# '^\(.\+\).*\1$'

* Environment
- Vim 7.4-45
- Ubuntu 12.04


Regards,
{my name}

な感じでしょうか.
原因についてまったく考察できていないのが若干気になりますが…

@k-takata
Copy link
Member

いいと思います。

@rhysd
Copy link
Author

rhysd commented Oct 10, 2013

バグレポート出しました.
レビューありがとうございました.

@rhysd rhysd closed this as completed Oct 10, 2013
@h-east
Copy link
Member

h-east commented Oct 10, 2013

@rhysd 👍 乙です。

vim_devにレポートを出した場合はその反応をみてからクローズする運用になっています。
https://github.com/vim-jp/issues/wiki/Member

vim_devに投稿が出てきたらリンクをここにコメントしてもらえると助かります。

(なので再オープンさせてもらいますね:smile:)

@h-east h-east reopened this Oct 10, 2013
@k-takata
Copy link
Member

@rhysd
Copy link
Author

rhysd commented Oct 11, 2013

おお,よくルール分かっていなくて申し訳ないです.
ご対応ありがとうございます.

@k-takata
Copy link
Member

k-takata commented Nov 3, 2013

todo入りしました。

NFA regexp doesn't handle backreference correctly. (Ryuichi Hayashida, 2013
Oct 10)

@k-takata k-takata closed this as completed Nov 3, 2013
@k-takata
Copy link
Member

k-takata commented Nov 3, 2013

todo.txtの上から3番目に入ったので、重要度は高いと認識されたようです。(すぐ直るとは限りませんが。)

@rhysd
Copy link
Author

rhysd commented Nov 3, 2013

おお,チェックありがとうございます.

@k-takata
Copy link
Member

7.4.100で直ったようです。
https://groups.google.com/d/topic/vim_dev/Dox10yhk58A/discussion

@rhysd
Copy link
Author

rhysd commented Nov 22, 2013

こちらでも確認しました。
ありがとうございました。

@rhysd
Copy link
Author

rhysd commented Nov 22, 2013

todo.txt からは削除されていないようなのですが,これは問題ないのでしょうか?

@k-takata
Copy link
Member

todo.txtの更新はruntimeファイルの更新時に行われますので、タイムラグがあります。
(たまに間違えてそのまま残っている場合もありますが。)

@rhysd
Copy link
Author

rhysd commented Nov 22, 2013

なるほど,分かりました.ありがとうございます.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

5 participants