プレビューに長時間かかる sed のコードがある

[mikecat]

Sed で Welcome to AtCoder を解いてみた #競技プログラミング - Qiita

を書いていて気付いたのですが、sed のシンタックスハイライトをしようとするとプレビューに長時間かかることがあるようです。

たとえば、新規記事を書く画面を開き、本文に

```sed
:tthousand
s/d\(.*\)0\(...\)$/\11\2/
s/d\(.*\)1\(...\)$/\12\2/
s/d\(.*\)2\(...\)$/\13\2/
s/d\(.*\)3\(...\)$/\14\2/
tthousand
```

を入力すると、1回の preview のクエリに9秒くらいかかるようです。

[tanaka-asami415]

@mikecat
ご報告ありがとうございます！

Qiita のハイライトは Rouge を使用しているのですが、確認してみたところ Rouge が原因で時間がかかっていそうです。
なぜ今回の入力で時間がかかるかは不明でした🙇
優先度は低くなりますが、この問題を修正できないか引き続き調査してみます。

[mikecat]

ありがとうございます。
Rouge 側に報告しました。

Some sed code take very long time to be highlighted · Issue #2057 · rouge-ruby/rouge

[yoshi389111]

通りすがりのものです。

Rouge のソースを確認しましたが、いくつか問題があって複合的に起きているようです。

一つ目の問題は、sed の : や t などのラベルを指定するコマンドで、Rouge ではコマンドとラベルの間にスペースが必要になっているためです。

        rule %r/([:btT])(\s+)(\S+)/ do

https://github.com/rouge-ruby/rouge/blob/bf007b7382070f33f49350c48502b47ee2aaab20/lib/rouge/lexers/sed.rb#L125

本来、sed では空白は必須ではないと思うので、 Rouge 側のバグだろうと思います。

↓細かい動作確認などはしていませんが、Rouge 側を直すなら以下のような感じだと思います（ \s の後ろを + から * に変える）

-         rule %r/([:btT])(\s+)(\S+)/ do
+         rule %r/([:btT])(\s*)(\S+)/ do

逆にいえば、ラベルの前に空白を入れれば（ Rouge 的に適正な : コマンドにすれば）、後述する問題点の二つ目が発生しないので Qiita でのハイライトに時間がかからなくなります。

↓暫定的に修正するなら、こんな感じ

: thousand  # <- ラベルの前にスペースを追加
s/d\(.*\)0\(...\)$/\11\2/
s/d\(.*\)1\(...\)$/\12\2/
s/d\(.*\)2\(...\)$/\13\2/
s/d\(.*\)3\(...\)$/\14\2/
t thousand  # <- ラベルの前にスペースを追加

二つ目の問題は、s コマンドと y コマンドが不正な場合、かつそれ以降に \ がたくさんあると、ReDoS 的な不具合があり、ハイライトに時間がかかるようです。

• ご存じかもしれませんが ReDoS とは、使用している正規表現の問題で処理時間が非常にかかることがある脆弱性のことです
• ご参考: https://qiita.com/tags/redos

この場合の不正な s コマンドとは、以下の s ではなく

s/d\(.*\)0\(...\)$/\11\2/

ラベル内の s の方です

:thousand

: コマンドとラベルの間にスペースがないため、: は不正なごみデータとして扱われ、その後のラベルも別の sed コマンドではないかとチェックし続けて、そのうち thousand の s で、不正な s コマンドとなり正規表現のマッチングに時間がかかっているようです。

なので、ラベルから s を（今回は無いですが y も）除外すれば Qiita のハイライトも素早く動きます。

:thouand  # <- s を削除
s/d\(.*\)0\(...\)$/\11\2/
s/d\(.*\)1\(...\)$/\12\2/
s/d\(.*\)2\(...\)$/\13\2/
s/d\(.*\)3\(...\)$/\14\2/
tthouand # <- s を削除

ただし、: コマンドが不正だと判断されるため、ラベル周辺のハイライトがおかしくなるとおもいます。

また、s （と y）の後（同一行だけじゃなく、コードブロックの最後まで）に \ が 20 個よりも少なければあまり時間がかからないですが、\ が30 個を超えると処理時間が非常に伸びて、ほぼ返ってこないようです。
おそらく、使用している正規表現的に \ が 1 つ増えるごとに処理時間が約 2 倍になるのではないかと思います。

これを Rouge 側で直すなら、多分 edot として定義している正規表現を修正することになるのではないかと思います（もっと良い方法があるかもしれません）。

-       edot = /\\.|./m
+       edot = /\\.|[^\\]/m

https://github.com/rouge-ruby/rouge/blob/bf007b7382070f33f49350c48502b47ee2aaab20/lib/rouge/lexers/sed.rb#L73

利用者側の暫定対策としては、ラベルの前にスペースを 1 つ入れることが一番簡単、かつ見栄えも悪くないと思います。

ご参考まで。