Planner: splitParts regex is quadratic on a quote followed by many backticks, so the fuzz test fails at random
メンテナーはふだん 1 日以内に返信
評価
- 難易度
- 2/5
- 見積もり時間
- 1〜3時間
- 初心者へのやさしさ
- 86/100
- issue の種類
- バグ
- 明瞭さ
- 明確に書かれている
- 活発さ
- 活発
- 技術スタック
- node.js, typescript
- 領域
- performance, testing
調査の方向性
src/planner/pipeline-steps.ts の splitParts() と、tests/fuzz/repository-text.fuzz.test.ts で失敗しているプロパティから始めてください。提供された seed を使って issue の再現コマンドを実行し、現在の正規表現の結果を、反例の形状に対する線形チェックの結果と比較してください。チェックが線形時間で実行され、正規表現の答えを維持し、異なる seed で fuzz テストが通れば完了です。
索引モデルが issue の本文から書いたものです。
説明
tests/fuzz/repository-text.fuzz.test.ts ("workflow files and package scripts") fails on main from time to time, depending on the random seed. It failed in CI on #291, a docs-only PR (run 44197635763, check (ubuntu-26.04, 22)):
not ok 2 - workflow files and package scripts
Property failed after 4 tests
{ seed: -1959240610, path: "3:6:4:7:7", endOnFailure: true }
Counterexample: ["\"\"`````````…"]
[cause]: Error: took 3238 ms
Reproduce (main @ 40aa308):
FC_SEED=-1959240610 npx tsx --test --test-name-pattern="workflow files and package scripts" tests/fuzz/repository-text.fuzz.test.ts
Cause. A CPU profile puts almost all the time in one regex in splitParts(), in src/planner/pipeline-steps.ts (L103):
if (parts.some((part) => !part || /"[^"]*[$`][^"]*"/.test(part)) || …
On a part that holds a " followed by a long run of backticks with no closing quote, [^"]* backtracks over the whole run from every starting point, so time grows quadratically. discoverGateChecks() reaches this through any gate script, for example "check": "tsc && \"\"" + "".repeat(n)`:
| backticks | discoverGateChecks({ check: "tsc && " + text }) |
|---|---|
| 25,000 | 0.9 s |
| 50,000 | 3.5 s |
| 100,000 | 12.9 s |
Without the leading "" it takes 1 to 3 ms. The text comes from the analysed repository's package.json, so a repository can stall planning. The fuzz test was written to catch exactly this, which is why it fails whenever the generator draws that shape.
Expected: the check is linear and gives the same answers as the regex, and the fuzz test passes for every seed.
- 主要言語
- TypeScript
- スター
- 0
- フォーク
- 4
- 平均マージ
- 18時間 41分
- マージ済み PR(30日)
- 48
環境構築
このプロジェクトの開発コンテナを、あなたの GitHub アカウントでブラウザ上に起動します。
- Dockerfile・Docker Compose ファイルなし
- プルリクエストのテンプレートなし
- コントリビューションガイドを読む
はじめの一歩
- issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
- 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
- リポジトリをフォークし、ブランチを切って変更します。
- issue 番号を参照したプルリクエストを送ります。
DiffCI/core のほかの issue
-
難易度 2/5 1〜3時間 初心者へのやさしさ 78/100
メンテナーはふだん 1 日以内に返信
-
Agent tools: changed_files lists only the new path of a renamed file対応中かも @FredApps が今日担当しました。 オープン
難易度 2/5 1〜3時間 初心者へのやさしさ 88/100
メンテナーはふだん 1 日以内に返信
-
難易度 2/5 1〜3時間 初心者へのやさしさ 84/100
メンテナーはふだん 1 日以内に返信
-
adapter good first issue
難易度 2/5 1〜3時間 初心者へのやさしさ 88/100
メンテナーはふだん 1 日以内に返信
-
adapter bug good first issue
難易度 2/5 1〜3時間 初心者へのやさしさ 84/100
メンテナーはふだん 1 日以内に返信
似ている issue
-
agent-ready area: ui-server priority: p3 type: test
難易度 2/5 1〜3時間 初心者へのやさしさ 78/100
schlessera/brain-kit#4249 ·
メンテナーはふだん 1 日以内に返信
-
documentation tool triaged
難易度 2/5 1〜3時間 初心者へのやさしさ 73/100
can1357/oh-my-pi#19608 · コメント 2 件 ·
メンテナーはふだん 1 日以内に返信
-
dependencies tech-debt
難易度 2/5 1〜3時間 初心者へのやさしさ 65/100
bcgov/nr-waste-plus#1549 ·
メンテナーはふだん 1 日以内に返信
-
enhancement good first issue
難易度 2/5 1〜3時間 初心者へのやさしさ 78/100
blixvip/solana-token-meta#17 ·
-
enhancement good first issue
難易度 2/5 1〜3時間 初心者へのやさしさ 78/100
blixvip/solana-tx-parse#18 ·