NFAエンジンを叩く #390

koron · 2013-05-20T13:13:30Z

NFAエンジンに対して以下のいずれかを目指す

徹底的に叩いて、直して使えるようにする
徹底的に叩いて、不具合報告で押しつぶして 7.3 からは取下げさせる(もしくはデフォルトをBTエンジンに切り替えさせる)

いずれにせよ再現しやすい例を示したほうが良い。

~~#386 から残っている問題~~ 残課題:

優先度: 高
- ~~[[:cntrl:]] にマルチバイト文字がマッチする。~~
- ~~幾らかのプラグインで誤動作が見られる(Vimに付属のものが引っかかってくれると嬉しい)~~
- ~~[[:alpha:]] とかの判定がおかしい。 check_char_class() の中で、マルチバイト文字もお構いなしに isalpha() などに放り込んでる。~~
- ~~\%u 等のコード指定が無効化されている。~~
- ~~先頭に * を入れるとE866~~
優先度: 低
- ~~if (*regparse == 'n' || *regparse == 'n')~~
- ~~test64 にマルチバイトのテストが混ざっている。~~
- ~~test95 が enc=utf-8 以外だと通らない。~~

The text was updated successfully, but these errors were encountered:

k-takata · 2013-05-20T13:22:11Z

文字クラスの修正。

diff --git a/src/regexp_nfa.c b/src/regexp_nfa.c
--- a/src/regexp_nfa.c
+++ b/src/regexp_nfa.c
@@ -2667,11 +2665,11 @@
     switch (class)
     {
    case NFA_CLASS_ALNUM:
-       if (isalnum(c))
+       if ((1 <= c && c <= 255) && isalnum(c))
        return OK;
        break;
    case NFA_CLASS_ALPHA:
-       if (isalpha(c))
+       if ((1 <= c && c <= 255) && isalpha(c))
        return OK;
        break;
    case NFA_CLASS_BLANK:
@@ -2679,7 +2677,7 @@
        return OK;
        break;
    case NFA_CLASS_CNTRL:
-       if (iscntrl(c))
+       if ((1 <= c && c <= 255) && iscntrl(c))
        return OK;
        break;
    case NFA_CLASS_DIGIT:
@@ -2687,7 +2685,7 @@
        return OK;
        break;
    case NFA_CLASS_GRAPH:
-       if (isgraph(c))
+       if ((1 <= c && c <= 255) && isgraph(c))
        return OK;
        break;
    case NFA_CLASS_LOWER:
@@ -2699,7 +2697,7 @@
        return OK;
        break;
    case NFA_CLASS_PUNCT:
-       if (ispunct(c))
+       if ((1 <= c && c <= 255) && ispunct(c))
        return OK;
        break;
    case NFA_CLASS_SPACE:

koron · 2013-05-20T13:25:53Z

@k-takata

文字クラスの修正。

マクロ定義したほうが良くない?

mattn · 2013-05-20T14:39:51Z

最初にフラグ取って使いまわしましょう。

k-takata · 2013-05-20T14:46:14Z

最初にフラグ取って使いまわしましょう。

どういうことでしょう？

mattn · 2013-05-20T14:48:23Z

https://gist.github.com/mattn/5612698

mattn · 2013-05-20T14:49:04Z

コードが太るか太らないかくらいでしかないですが

k-takata · 2013-05-20T14:53:19Z

postfix領域(?)が埋まっていると、デバッグログのPostfix notationにゴミが出力されます。

diff --git a/src/regexp_nfa.c b/src/regexp_nfa.c
--- a/src/regexp_nfa.c
+++ b/src/regexp_nfa.c
@@ -1824,13 +1824,13 @@
    else if (retval == OK)
        fprintf(f, ">>> NFA engine succeeded !\n");
    fprintf(f, "Regexp: \"%s\"\nPostfix notation (char): \"", expr);
-   for (p=post_start; *p; p++)
+   for (p = post_start; *p && p < post_end; p++)
    {
        nfa_set_code(*p);
        fprintf(f, "%s, ", code);
    }
    fprintf(f, "\"\nPostfix notation (int): ");
-   for (p=post_start; *p; p++)
+   for (p = post_start; *p && p < post_end; p++)
        fprintf(f, "%d ", *p);
    fprintf(f, "\n\n");
    fclose(f);

mattn · 2013-05-20T14:55:08Z

GJ

mattn · 2013-05-20T15:00:48Z

あわせて送っちゃって下さい。

koron · 2013-05-20T15:05:55Z

このパッチで下の2つが解決するのかな?

[[:cntrl:]] にマルチバイト文字がマッチする。

[[:alpha:]] とかの判定がおかしい。 check_char_class() の中で、マルチバイト文字もお構いなしに isalpha() などに放り込んでる。

koron · 2013-05-20T15:09:13Z

ふと気になった。パフォーマンスはどうなんだろう?
ヘルプファイルはsyntax使ってると心持ち遅くなった気がするのだが…

k-takata · 2013-05-20T15:12:19Z

NFA engine could not handle "[^A-z]"

postfix領域が足りないせいで、NFAエンジンでは扱えないようですね。
nstate_max の値をもっと増やせばいいのでしょうが…と思ったら、232行目付近にこんなコメントが。

    /* Some items blow up in size, such as [A-z].  Add more space for that.
     * TODO: some patterns may still fail. */
//    nstate_max += 1000;

k-takata · 2013-05-20T15:13:31Z

(1 <= c && c <= 255) の部分、どうしよう。

mattn · 2013-05-20T15:26:07Z

(1 <= c && c <= 255) の部分、どうしよう。

シェフのおまかせで

k-takata · 2013-05-20T15:55:33Z

結局、元のまま投げてしまいました。
https://groups.google.com/d/msg/vim_dev/Zmvbn5r5gE0/4upvo3emU8IJ

k-takata · 2013-05-20T22:37:21Z

残件:

if (*regparse == 'n' || *regparse == 'n')
\%u 等のコード指定がなぜか無効化されている。
test64 にマルチバイトのテストが混ざっている。（エンジン自身の問題ではないが。）
test95 が enc=utf-8 以外だと通らない。（実際にはlatin1などでも通るかもしれない。これも、エンジン自身の問題ではないが。）

k-takata · 2013-05-20T22:39:27Z

7.3.978
https://groups.google.com/d/topic/vim_dev/F7aE08KSGP0/discussion
7.3.979
https://groups.google.com/d/topic/vim_dev/2qWKMORM4rM/discussion
7.3.980
https://groups.google.com/d/topic/vim_dev/-5VdoYmTqUo/discussion

mattn · 2013-05-20T22:45:05Z

あと残課題なんだろ

On 5/21/13, K.Takata notifications@github.com wrote:

7.3.978
https://groups.google.com/d/topic/vim_dev/F7aE08KSGP0/discussion
7.3.979
https://groups.google.com/d/topic/vim_dev/2qWKMORM4rM/discussion
7.3.980
https://groups.google.com/d/topic/vim_dev/-5VdoYmTqUo/discussion

Reply to this email directly or view it on GitHub:
#390 (comment)

Yasuhiro Matsumoto

koron · 2013-05-20T23:57:09Z

トップの残課題を更新しました。

mattn · 2013-05-21T00:12:13Z

\u は影響大きいと見た

mattn · 2013-05-21T00:17:16Z

これもそうかな

https://groups.google.com/forum/?fromgroups#!topic/vim_dev/NTn5kBr5g2A

mattn · 2013-05-21T00:17:30Z

いったん報告したよ

https://groups.google.com/forum/?fromgroups#!topic/vim_dev/ec71SWian0I

k-takata · 2013-05-21T00:34:48Z

これもそうかな

regexp_nfa のコメント見ると \ze が動かないと書いてありますね。

mattn · 2013-05-21T00:38:37Z

regexp_nfa のコメント見ると \ze が動かないと書いてありますね。

そりゃプラグイン壊れるわw

k-takata · 2013-05-21T00:54:10Z

でも regexpengine=0 になっていれば、NFAエンジンでサポートしていないパターンは旧エンジンで実行されるので実用上は問題ないはずなんですがね。プラグインが壊れるのと \ze, %u が使えないのは別だと思います。
それともまさか、みんな regexpengine=2 で使ってるんですか!?

koron · 2013-05-21T00:55:05Z

僕はデフォを :set re=1 にしちゃた (・ω<)

mattn · 2013-05-21T01:04:49Z

0です

k-takata · 2013-05-21T01:17:15Z

0です

となると、NFA エンジンで処理しているが、結果が正しくないのが他にあるんでしょうね。

NFA engine could not handle "[^A-z]"

7.3.977 で nstate_max += 1000; の行が有効化されて NFA で扱えるようになってました。

k-takata · 2013-05-21T01:48:12Z

\%u はテスト不足のために無効化されているようですね。
1104行目にこんなコメントがありました。

/* TODO(RE) This needs more testing */

Shougo · 2013-06-06T03:55:06Z

確かに、そうですね。まだ英文に慣れていないので……。

itchyny · 2013-06-06T04:02:59Z

Shougoさんの英語に突っ込んじゃダメな気がする... (多すぎて)

h-east · 2013-06-06T05:11:36Z

なんだかんだ言っても実際にアクション起こしてる人はカッコいいよ。(千円くれ)

sgur · 2013-06-06T05:12:38Z

echo split("foo\XFFbar", "\xFF") と echo split("foo\XFFbar", '\xFF')がごっちゃになってませんか?

手元の 7.3.1128 では以下のようになりましたが…

echo &enc
=> utf-8

set re=0
echo split("foo\XFFbar", '[\xFF]')
=> ['foo<ff>bar']
echo split("foo\XFFbar", "\xFF")
=> ['foo', 'bar']
echo split("foo\XFFbar", '\xFF')
=> ['foo<ff>bar']

set re=1
echo split("foo\XFFbar", '[\xFF]')
=> ['foo', 'bar']
echo split("foo\XFFbar", "\xFF")
=> ['foo<ff>bar']
echo split("foo\XFFbar", '\xFF')
=> ['foo<ff>bar']

set re=2
echo split("foo\XFFbar", '[\xFF]')
=> ['foo<ff>bar'] 
echo split("foo\XFFbar", "\xFF")
=> ['foo', 'bar']
echo split("foo\XFFbar", '\xFF')
=> ['foo<ff>bar']

Shougo · 2013-06-06T05:18:16Z

あ、すみません。確かにヒストリをたどって実行した際に、ごっちゃになっていた可能性があります。

もう一度確認します。

なんだかんだ言っても実際にアクション起こしてる人はカッコいいよ。(千円くれ)

ありがとうございます。

Shougo · 2013-06-06T05:22:58Z

set re=0
echomsg string(split("foo\XFFbar", '[\xFF]'))
" => ['foo<ff>bar']
echomsg string(split("foo\XFFbar", "\xFF"))
" => ['foo', 'bar']
echomsg string(split("foo\XFFbar", '\xFF'))
" => ['foo<ff>bar']

set re=1
echomsg string(split("foo\XFFbar", '[\xFF]'))
" => ['foo', 'bar']
echomsg string(split("foo\XFFbar", "\xFF"))
" => ['foo<ff>bar']
echomsg string(split("foo\XFFbar", '\xFF'))
" => ['foo<ff>bar']

set re=2
echomsg string(split("foo\XFFbar", '[\xFF]'))
" => ['foo<ff>bar']
echomsg string(split("foo\XFFbar", "\xFF"))
" => ['foo', 'bar']
echomsg string(split("foo\XFFbar", '\xFF'))
" => ['foo<ff>bar']

私の環境ではこのような結果になりました。vim_devには訂正メールを送っておきます。

Shougo · 2013-06-06T05:26:31Z

修正版の結果を投稿しました。

msmhrt · 2013-06-06T12:23:43Z

:help pattern-multi-byteの内容を読んだ限りでは、"\xFF"はenc=utf-8な環境では不正なシーケンスなので、パターン内の"\xFF"が対象文字列内の"\xFF"にマッチしなくても仕方がないのではないか？と思いました。

旧エンジンでは代わりに U+00FF にマッチしているようですが、"\xFF"にマッチしてくれた方が嬉しい人は多いでしょうね。

Shougo · 2013-06-06T14:13:24Z

ふむふむ。ややこしいですね。

Shougo · 2013-06-07T02:06:19Z

Bram氏も同様の指摘をしていますね。了解です。私の件はcloseとさせてください。
vim_devにも返信しておきます。

k-takata · 2013-06-10T03:35:27Z

vim_jp の Google group に報告がありますが、マルチバイト文字に対する [[:print:]] 等の POSIX ブラケットの動作が re=1,2 で異なっているようです。そもそも re=1 の動作がおかしい気もしますが。
https://groups.google.com/d/msg/vim_jp/lP65zBtt9xo/T5k1Lsgvj0oJ

マニュアルを見ると、「これらのものは、8 ビット文字のみマッチします。」とあるので、マルチバイト文字にはマッチしないのが仕様の気がします。
（ちなみに、鬼車・鬼雲では Unicode とそれ以外の場合に動作が異なりますが、[[:print:]] についてはマルチバイト文字にはマッチするのが仕様です。 https://github.com/k-takata/Onigmo/blob/master/doc/RE.ja#L177 ）

mattn · 2013-06-10T03:52:37Z

http://en.wikipedia.org/wiki/Regular_expression#Character_classes

値の範囲はASCIIなのでおいとくとしてDescriptionではVisible characters and the space characterと書いてあるので、0x20以上のvalidな文字は全て出すべきでしょうね。

k-takata · 2013-06-10T15:22:25Z

そもそも re=1 の動作がおかしい気もしますが。

#413 を起票しました。

thinca · 2013-06-14T18:05:13Z

\%[[a]] で内部エラー。
INTERNAL: Negative state char: -165
7.3.1189 です。
ちなみにこれは旧エンジンでは内部の [a] は通常の正規表現として扱われて文字クラスになります。

ynkdir · 2013-06-17T08:04:36Z

%[[a]] で内部エラー。

報告しました。
https://groups.google.com/d/msg/vim_dev/Kq_dTKmWKMA/o2rHZKaRmN4J

thinca · 2013-06-17T08:08:05Z

あざす！

k-takata · 2013-06-19T15:20:54Z

%[[a]] で内部エラー。

7.3.1217 で直りました。
https://groups.google.com/d/topic/vim_dev/eZPkOoDbvFk/discussion
さらに、7.3.1219 で関連テストが入りました。
https://groups.google.com/d/topic/vim_dev/GGXY94iCFmc/discussion

`[[]` のテストもあった方がいいような？

Shougo · 2013-06-27T10:55:54Z

Vim 7.3.1243で正規表現エンジンのデグレードがありました。私の作成したスニペットプラグインが使い物にならなくなっています。

https://groups.google.com/forum/#!topic/vim_dev/EYyJJwFURVk

Shougo/neosnippet.vim#158

どうやら、Vim 7.3.1243で後方参照の実装が変更になったのが原因みたいです。

再現スクリプト：

set regexpengine=0
echomsg substitute('2013-06-27${0}',
      \'\\\@<!\${\(\d\+\%(:.\{-}\)\?\\\@<!\)}', ' \1 ', 'g')
set regexpengine=1
echomsg substitute('2013-06-27${0}',
      \'\\\@<!\${\(\d\+\%(:.\{-}\)\?\\\@<!\)}', ' \1 ', 'g')

上記のスクリプトをsourceしてみると、regexpengine=0とregexpengine=1で結果が異なります。
しかも、regexpengine=0のとき、E43が出ていて、

                            *E43* *E44*  >
  Damaged match string
  Corrupted regexp program

Something inside Vim went wrong and resulted in a corrupted regexp.  If you
know how to reproduce this problem, please report it. |bugs|

この挙動は明らかにバグと思われます。

確認環境：Ubuntu 13.04
Vim: 7.3.1251

koron · 2013-06-27T10:58:59Z

テスト漏れ

mattn · 2013-06-27T13:00:52Z

@Shougo 報告した方が直るの早いと思うよ。

mattn · 2013-06-28T00:51:29Z

https://groups.google.com/d/msg/vim_dev/EYyJJwFURVk/MNB_AqBKD54J

Shougo · 2013-06-28T02:04:35Z

報告ありがとうございます。昨日は時間がなく、まずはvim-jpに現象をまとめておこうと考えていたので、代わりに報告してもらって助かります。

k-takata · 2013-06-29T10:52:47Z

https://groups.google.com/d/msg/vim_dev/EYyJJwFURVk/GagpBMPcWuAJ

Looks like patch 7.3.1258 fixes this one as well.

だそうです。

Shougo · 2013-06-29T13:09:31Z

了解です。試してみます。

Shougo · 2013-06-29T13:15:49Z

Vim 7.3.1265にて、私が報告した現象が直っていることを確認しました。

k-takata · 2013-08-10T16:10:13Z

7.4 が出たことですので、閉じたいと思います。
以降は個別 issue にしましょう。

koron mentioned this issue May 20, 2013

Vim7.3.973でsearch("[^\x01-\x7e]", 'n')でCaught deadly signal ABRT #386

Closed

k-takata closed this as completed Aug 10, 2013

ynkdir mentioned this issue Oct 6, 2013

<SNR> のマッチの仕方が 'regexpengine' の値によって違う #477

Open

Shougo mentioned this issue Jan 12, 2014

Vim7.4 以降で位置にマッチするハイライト（正規表現？）が非常に遅い #511

Closed

k-takata mentioned this issue Mar 12, 2016

開発ブランチ(もしくは安定ブランチ)を導入させたい #872

Open

NFAエンジンを叩く #390

NFAエンジンを叩く #390

Comments

koron commented May 20, 2013

k-takata commented May 20, 2013

koron commented May 20, 2013

mattn commented May 20, 2013

k-takata commented May 20, 2013

mattn commented May 20, 2013

mattn commented May 20, 2013

k-takata commented May 20, 2013

mattn commented May 20, 2013

mattn commented May 20, 2013

koron commented May 20, 2013

koron commented May 20, 2013

k-takata commented May 20, 2013

k-takata commented May 20, 2013

mattn commented May 20, 2013

k-takata commented May 20, 2013

k-takata commented May 20, 2013

k-takata commented May 20, 2013

mattn commented May 20, 2013

koron commented May 20, 2013

mattn commented May 21, 2013

mattn commented May 21, 2013

mattn commented May 21, 2013

k-takata commented May 21, 2013

mattn commented May 21, 2013

k-takata commented May 21, 2013

koron commented May 21, 2013

mattn commented May 21, 2013

k-takata commented May 21, 2013

k-takata commented May 21, 2013

Shougo commented Jun 6, 2013

itchyny commented Jun 6, 2013

h-east commented Jun 6, 2013

sgur commented Jun 6, 2013

Shougo commented Jun 6, 2013

Shougo commented Jun 6, 2013

Shougo commented Jun 6, 2013

msmhrt commented Jun 6, 2013

Shougo commented Jun 6, 2013

Shougo commented Jun 7, 2013

k-takata commented Jun 10, 2013

mattn commented Jun 10, 2013

k-takata commented Jun 10, 2013

thinca commented Jun 14, 2013

ynkdir commented Jun 17, 2013

thinca commented Jun 17, 2013

k-takata commented Jun 19, 2013

[[] のテストもあった方がいいような？

Shougo commented Jun 27, 2013

koron commented Jun 27, 2013

mattn commented Jun 27, 2013

mattn commented Jun 28, 2013

Shougo commented Jun 28, 2013

k-takata commented Jun 29, 2013

Shougo commented Jun 29, 2013

Shougo commented Jun 29, 2013

k-takata commented Aug 10, 2013

`[[]` のテストもあった方がいいような？