BugTrack/2081

ページ数が増えるとAutoLinkが原因でmake_link()が正常に動作しない†

ページ: BugTrack
投稿者: nao-pon
優先順位: 普通
状態: 保留
カテゴリー: 本体バグ
投稿日: 2005-06-20 (月) 20:04:57
バージョン: 1.4.5_1

ページ数が増えるとAutoLinkが原因でmake_link()が正常に動作しない
コメント

↑

メッセージ (from nao-pon)†

ページ数が増えると、AutoLink の正規表現が原因で、make_link()が正常に動作しなくなり、空白を返します。

結果的にページが正常に表示されなくなります。

ページ数は5400ページほど、autolink.datのサイズが 38KB ほどで、この問題が出ています。

原因は解りませんが、正規表現パターンが大きすぎるのが原因かもしれません。

PHP: パターン構文 - Manual（http://www.php.net/manual/ja/reference.pcre.pattern.syntax.php）の以下の記述は関係あるのかな？

再帰的パターン
一つのパターン中に 15 以上のキャプチャ用サブパターンを用いると、PCRE は再帰を行っている間のデータ保存用に追加の記憶領域を確保する必要があります。
記憶領域が確保できない場合、メモリ不足エラーを再帰の内側から出力する手段がないため、最初の 15 個のキャプチャ用サブパターンについてのみデータが保存されます。

↑

テスト環境†

OS: Vine Linux 3.1
Apache: 1.3.33
PHP: 4.3.11
PukiWiki: 1.4.5_1

↑

メッセージ (from asari, BugTrack2/105)†

データベース的な使い方をしようと思い、スクリプトを使ってページを 10000 件ほど追加したところ、デフォルト表示の部分とプラグインの部分をのぞいてページが表示されない状態になりました。

cache/autolink.dat を削除するとページ編集時に一時的に見えるようになったので、 autolink 周りが怪しいと思いました。
関連しそうな pukiwiki.ini.php の設定項目は:

$autolink = 8;

ちなみに、 cache/autolink.dat のサイズは、 45KB 程度です。

$autolink = 0;

とすると、正常に表示されるようになりました。

CVS版 (ただし、 iconv で UTF-8 に変換済み) でも修正されていないことを確認しました。 BugTrack2/44 と重複しているかとも思ったのですが、違うかもです。 -- asari 2005-09-07 (水) 04:44:47

↑

テスト環境†

OS: Mac OS X "Tiger" 10.4.2
Apache: 2.0.54
PHP: 5.0.4
PukiWiki: CVS 2005-09-07 (水) 04:44:47

↑

コメント†

たしかに、他の正規表現ライブラリをみるかぎりでも、それはありえそうですね (^^; AutoLinkの場合、ただ単に単語をしらべているだけだからもうすこし方法があるかも・・・（たしか、文字の長さにも関係したような・・・） -- みこ 2005-06-22 (水) 15:11:55
BugTrack2/105 に重複したバグ報告をしました。今後の話題はこちらがいいでしょうかね。 -- asari 2005-09-09 (金) 07:11:44
- こんにちは。このような時の対応としては、ケース次第ではありますが、重複項目をこのままにしていた場合に情報が発散(分散)してしまう事を防ぐため、可能なら後から投稿された内容をこちらに移して(情報をまとめて)、後のページを削除するようなこともできます :) Wikiなので。 -- henoheno 2005-09-09 (金) 07:29:26
- 移しましたっと。
  - こんにちは :) autolinkの分量がきっかけとなっていて、$autolinkの値を減らせば治まるというのは、正規表現モジュール(pcre?)に依存した既知の現象だったかと思います。どこかに似た話題があるかもしれません -- henoheno 2005-09-07 (水) 07:46:14
  - コメントありがとうございます。BugTrack2/81 で既出の問題でしたね。すみません。 -- asari 2005-09-09 (金) 07:06:16
cache/autolink.dat ってキャプチャ用サブパターンを使ってましたっけ？
下のように、全部「(?:正規表現)」の形で書いてあったような（本当は1行の文章です）。
```
(?:BracketName|F(?:ormattingRules|rontPage)|InterWiki(?:Name|SandBox)?
|MenuBar|PukiWiki|RecentChanges|SandBox|Wiki(?:Engines|Name|WikiWeb)|YukiWiki)
```
サブパターン
また、キャプチャを行うものと行わないものを合わせて、サブパターンの数は最大 200 までです。
の部分の方が当てはまるのでは。 -- 2007-06-25 (月) 09:14:49

↑

AutoLink の正規表現を分割して処理する例 (from nao-pon)†

総ページ数が増えるとAutoLinkが原因で正常にページが表示されなくなる-PukiWikiMod/BugTrack/30-Wiki [自由帳]-XOOPSマニアにて、PukiWikiMod 用に考えてみてますが、なにぶんにも素人考えなので問題ありありです。なにかもっといい方法はないものでしょうか・・・。 -- nao-pon 2005-06-25 (土) 23:22:22
- 正規表現を3000ページごとに分割して処理する例
- 約30kbで正規表現を分割する例

↑

コメント†

ふむ。仮にそれらの「巨大な正規表現」を「適当な大きさの複数個の正規表現」に分割できて、しかもそれらはAutoLinkの表示/更新処理でも適切に動作できるとしましょう。そうした適度な正規表現は何KB以内なら許されるのでしょう? 環境依存でも構いませんから、困っている方の環境でその限界がどの位か教えていただけないでしょうか。 -- henoheno 2007-02-22 (木) 23:36:02
Name OS PHP version Max size of autolink.dat
that works

example Debian sarge 4.3.10-18 ?? KB まではOKだった

Ilfa Windows Vista Ultima (32bit)
Apache 2.2.4 5.2.2 16KBで○、17KBで×
- ・・・・と書いてはみたものの、これを調べるためにautolink.datを手でいじるのは大変そうですね*1。テスト用の巨大なautolink.datを用意する方法もありますね。いずれにせよ、妥当な限界値を知りたく思います。本日はひとまずここまで。 -- henoheno 2007-02-22 (木) 23:42:17
(巨大な文字配列を複数個の文字配列に分割して、それぞれから正規表現を作り)正規表現のマッチを複数回実行することで異常を回避する、という戦略をとる場合、分割前の配列は逆順(降順)にソートしておかないと、最長一致の原則を無視したマッチが起きる可能性があると思います。昇順にソートした文字配列というのは、そもそも短いページ名がより前に配置されているため、「ソートされた順番に比較しなければならない」状況が生まれた場合、最長一致の原則を無視したマッチが起きる可能性が生まれます。勘違いじゃないと思うけれど実証はしていません。 -- henoheno 2007-03-03 (土) 09:08:19
```
 // この順番に preg_match() にかける場合
 array(
   '/A/'      // <= 'ABCD' にはこちらが先にマッチしてしまう
   '/ABCD/',  // <= 永遠にマッチしない
 )
```
文字が長い順番にソートすると解決するのではないかと思いますがどうなのでしょうか。 -- はいふん 2021-12-12 (日) 19:39:03
検証してみたんですが、AutoLinksを有効にしてページを生成してみると自分の場合は8500ページまでが限界でした。 -- はいふん 2021-12-16 (木) 00:50:18
- 計測ありがとうございます。具体的な数字が出てくると問題がはっきりしますね。環境がわかりませんが、8500ページとはかなり大きい数ですね。驚きです -- umorigu 2021-12-16 (木) 19:31:19
この問題、今実際に困ってる方は居るのでしょうかね？当時は求められたかもしれませんが・・・最初に報告されたのも15年以上前ですし。数千ページの規模までは大丈夫ということなのでそれを超えるような規模で使っていて、全ページの相互自動リンクが必要だとは思えないんですよね。それよりも commit:9755151b64 や PKW-2081 のような AutoTicketLink (外部チケットシステムへの半自動リンク) の方が現実には便利に使えると思っています。このページを見ても2010年代の10年間は書き込みがなかったようです -- umorigu 2021-12-16 (木) 19:38:21
AutoLinkの現行の設計・実装は画期的で、数百-数千のページ名を、単一の正規表現で一度に検索するという正気とは思えない (誉め言葉) もので、ページ表示時にはった一回 (ではないですね、見つかったページ分) の preg_match() だけで済むものになってます。画期的であるが故に、同じ動作を実現できる他の実装を全く思いつきません。また仮に何か対策ができたとしても利用する人がそれほど多いとは思えないんですよね。どちらかというと BugTrack/2485 (Client side AutoLink) のような方向の方がまだやりようがある (内容的に面白い) のではないかと考えています。(これも使われないとは思います..) -- umorigu 2021-12-16 (木) 19:53:15

Name	OS	PHP version	Max size of autolink.dat that works
example	Debian sarge	4.3.10-18	?? KB まではOKだった
Ilfa	Windows Vista Ultima (32bit) Apache 2.2.4	5.2.2	16KBで○、17KBで×

↑

コメント†

ページ数が多くなるとAutoLinkが正常に機能しないという問題ですが、1.4.6でも起きました。AutoLink自体のロジックを見直す必要があるように思いますが・・・ -- よっちゃん 2005-11-02 (水) 11:09:18
official:質問箱3/442 -- 2006-06-27 (火) 21:20:07
ページ数が多くなるとAutoLinkが正常に機能しない問題について、1.4.7でも起きました(文書数26,995, cache/autolink.dat 218,090byte)。AutoLink機能を使い続けたいのですが回避策はありますか? -- puga 2006-08-23 (水) 02:17:40
official:質問箱4/40 特定のページをautolink.dat の正規表現に含めたくない -- 2007-04-07 (土) 01:38:39
こちらでも1.4.7でautolink.datのサイズが 38KB ほどで内容が表示されなくなりました。重要度普通になっていますが，他の頁にもあったように，スパム攻撃にも使えるし，utf-8環境ではどうしてもファイル名が長くなるので，このバグは早急に解決して欲しいです。また，インストールの頁などにこの問題点の記載が必要では？ここにたどり着くまでずいぶん悩みました。 -- kaz 2007-07-23 (月) 23:29:35
- 上記にあるように、phpの正規表現モジュール(pcre?)に依存した現象です。今のところ対策が分かっていません。kazさん直して～^^;
  現実問題として、FAQとかその他インストールのページとかに注意事項として書いておいた方がよさそうですね。 -- ぃぉぃぉ 2007-07-23 (月) 23:58:20
- デフォルトではAutolink無効にしておいて、pukiwiki.ini.phpのAutolinkの部分のコメントにAutolink有効の場合の問題点を記載しておいてはどうかな? -- ぃぉぃぉ 2007-07-24 (火) 00:13:42
- 根本的な解決ができるまで，エラー処理はできないのでしょうか。正規表現モジュールが上限に達した(？)ときに，Autolinkを無効にしてその旨警告するというような処理ですが・・・kaz2007-07-24 (火) 00:13:45

もし次のように正規表現パターンを書き換えた場合に、問題がでる環境ってあるのでしょうか。
```
WebTrack\/(?:
1(?:0|1|2|3|4|5|6|7|8|9)?
|2(?:0|1|2|3|4|5|6|7|8|9)?
|3(?:0|1|2|3|4|5|6|7|8)?
|4(?:0|1|2|3|4|5|6|7|8|9)?
|5(?:0|1|2|3|4|5|6|7|8|9)?
|6(?:0|2|3|4|6|7|8|9)?
|7(?:0|1|2|3|4|5|6(?:\/てすと)?|7|8|9)?
|8(?:0)?
|9
)
```
上を下に（改行位置がややいい加減）。
```
WebTrack\/(?:
1[0123456789]?
|2[0123456789]?
|3[012345678]?
|4[0123456789]?
|5[0123456789]?
|6[02346789]?
|7(?:0|1|2|3|4|5|6(?:\/てすと)?|7|8|9)?
|8[0]?
|9
)
```
$result = generate_trie_regex($auto_pages) の結果を置換えているのがバレバレなんですが（つまり対処療法であって、根本解決ではない）。
ちなみに(?:0|1|2) を[012] にしようと思った理由は、パターン構文（http://jp2.php.net/manual/ja/reference.pcre.pattern.syntax.php）のパフォーマンスに
```
パターンに記述可能な要素のうち、幾つかの要素は、他の要素よりも 効率的に処理されます。
(a|e|i|o|u) のような選択肢の集合よりも [aeiou] のような文字クラスの方が効率的です。
```
とあったからです。サブパターンの数を減らすのにも少しは役立ちそうだったので。
余談ですが、このページの最適化後が今の生成パターンに似ているんですけど、もし正規表現パターンをそのページの最適化前のような状態（ページ名とページ名の間に'|'を挟んだだけの物に...）にして、（時間はかかっても）動くのなら「速度とサブパターン数のバランスをどこで取るのか」という問題に限定できるんだけど（そうでなければ、他の原因を探さねば）。 -- 2007-09-17 (月) 20:36:46
この問題は未解決という理解であっておりますでしょうか？ -- Mike 2007-12-30 (日) 10:06:04
出来れば分かり易い位置に書いててほしかった。オートリンク前提だったので今から全ページ修正しなきゃorz -- 2008-04-08 (火) 11:56:19
関連?: BugTrack2/311 -- 2009-03-10 (火) 17:48:17

total: 13970
today: 1
yesterday: 2
now: 3

ページ数が増えるとAutoLinkが原因でmake_link()が正常に動作しない†

メッセージ (from nao-pon)†

テスト環境†

メッセージ (from asari, BugTrack2/105)†

テスト環境†

コメント†

AutoLink の正規表現を分割して処理する例 (from nao-pon)†

コメント†

コメント†

最新の16件