Planner: splitParts regex is quadratic on a quote followed by many backticks, so the fuzz test fails at random

オープン 初心者向け
#300 コメント 0 件 リアクション 0 件 担当者 0 名 GitHub で見る

メンテナーはふだん 1 日以内に返信

@FredApps がすでに取り組んでいます。

2026年11月17日 から。

  • #302 @FredApps による — オープン

評価

難易度
2/5
見積もり時間
1〜3時間
初心者へのやさしさ
86/100
issue の種類
バグ
明瞭さ
明確に書かれている
活発さ
活発
技術スタック
node.js, typescript

調査の方向性

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

環境構築

Codespaces で開く

このプロジェクトの開発コンテナを、あなたの GitHub アカウントでブラウザ上に起動します。

はじめの一歩

  1. issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
  2. 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
  3. リポジトリをフォークし、ブランチを切って変更します。
  4. issue 番号を参照したプルリクエストを送ります。

DiffCI/core のほかの issue

DiffCI/core の issue をすべて見る

似ている issue

TypeScript の issue をもっと見る

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。