Serializer: `write_escaped` is O(n²) when text doesn't contain `<`, `>` or `"`
メンテナーはふだん 1 日以内に返信
まだ誰も着手していません。
評価
- 難易度
- 3/5
- 見積もり時間
- 1〜2日
- 初心者へのやさしさ
- 68/100
- issue の種類
- バグ
- 明瞭さ
- 明確に書かれている
- 活発さ
- 活発
- 技術スタック
- rust
- 領域
- performance
調査の方向性
Start in html5ever/src/serialize/mod.rs at HtmlSerializer::write_escaped, then build and run the html2html example with the reproduction in the issue. Compare timings as the input grows for & and versus &<; done means the problematic inputs no longer show the reported quadratic scaling.
索引モデルが issue の本文から書いたものです。
説明
HtmlSerializer::write_escaped finds the next byte to escape with two memchr searches (introduced by #740):
If the text doesn't have an <, > or ", every & or non-breaking space will cause a full scan of the remaining text.
It's pretty common for text to contain & and without <s or >s.
Repro using the html2html example:
cargo build --release -p markup5ever_rcdom --example html2html
TIMEFORMAT='%R s'
for text in '&' '&<' ' '; do
for count in 100000 200000 400000; do
yes "$text" | head -n "$count" | tr -d '\n' > input.html
echo -n "$text x $count: "
time target/release/examples/html2html < input.html > /dev/null
done
done
On a Linode G6 Dedicated machine with 2 vCPUs and 4 GB RAM, I get:
& x 100000: 0.148 s
& x 200000: 0.462 s
& x 400000: 1.665 s
&< x 100000: 0.096 s
&< x 200000: 0.197 s
&< x 400000: 0.376 s
x 100000: 0.241 s
x 200000: 0.839 s
x 400000: 3.492 s
- 主要言語
- Rust
- スター
- 2.6k
- フォーク
- 299
- 平均マージ
- 8日 22時間
- マージ済み PR（30日）
- 3
環境構築
このプロジェクトには開発コンテナ、Dockerfile、コントリビューションガイドがありません。まず README を読み、一般的な手順ははじめてのコントリビューションガイドを参照してください。
はじめの一歩
- issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
- 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
- リポジトリをフォークし、ブランチを切って変更します。
- issue 番号を参照したプルリクエストを送ります。
servo/html5ever のほかの issue
-
難易度 2/5 1〜3時間 初心者へのやさしさ 70/100
メンテナーはふだん 1 日以内に返信
-
rcdom: selectedcontent lookup reads self.data, option clone never runs対応中かも @jdm が 74 日前に担当しました。 オープン
難易度 1/5 1時間未満 初心者へのやさしさ 90/100
servo/html5ever#776 · コメント 1 件 ·
メンテナーはふだん 1 日以内に返信
-
難易度 3/5 1〜2日 初心者へのやさしさ 62/100
メンテナーはふだん 1 日以内に返信
-
難易度 3/5 半日 初心者へのやさしさ 66/100
servo/html5ever#797 · コメント 1 件 ·
メンテナーはふだん 1 日以内に返信
-
Tokenizer: duplicate-attribute check is O(n²) in a tag's attribute count対応中かも @tstreule が 5 日前に担当しました。 オープン
難易度 4/5 3〜5日 初心者へのやさしさ 42/100
メンテナーはふだん 1 日以内に返信
servo/html5ever の issue をすべて見る
似ている issue
-
難易度 2/5 1〜3時間 初心者へのやさしさ 65/100
メンテナーはふだん 1 日以内に返信
-
難易度 2/5 1〜3時間 初心者へのやさしさ 62/100
メンテナーはふだん 2 日以内に返信
-
Android visitors are offered the Linux .deb on cap.so's homepage and download page対応中かも @patrickballard が今日担当しました。 オープン
難易度 2/5 1〜3時間 初心者へのやさしさ 78/100
CapSoftware/Cap#3677 · コメント 1 件 ·
メンテナーはふだん 1 日以内に返信
-
難易度 2/5 1〜3時間 初心者へのやさしさ 72/100
メンテナーはふだん 1 日以内に返信
-
難易度 2/5 1〜3時間 初心者へのやさしさ 72/100
DioxusLabs/blitz#1371 ·
メンテナーはふだん 1 日以内に返信