Planner: splitParts regex is quadratic on a quote followed by many backticks, so the fuzz test fails at random
Maintainer thường phản hồi trong vòng 1 ngày
Đánh giá
- Độ khó
- 2/5
- Thời gian dự kiến
- 1-3 giờ
- Mức phù hợp với người mới
- 86/100
- Loại issue
- Lỗi
- Độ rõ ràng
- Đặc tả rõ ràng
- Mức độ hoạt động
- Sôi nổi
- Công nghệ
- node.js, typescript
- Lĩnh vực
- performance, testing
Hướng nghiên cứu
Bắt đầu với splitParts() trong src/planner/pipeline-steps.ts và thuộc tính bị lỗi trong tests/fuzz/repository-text.fuzz.test.ts. Chạy lệnh tái hiện của issue với seed được cung cấp, sau đó so sánh kết quả của regex hiện tại với một phép kiểm tra tuyến tính trên dạng của phản ví dụ. Hoàn tất khi phép kiểm tra chạy trong thời gian tuyến tính, giữ nguyên kết quả của regex và bài kiểm tra fuzz vượt qua với nhiều seed khác nhau.
Do mô hình lập chỉ mục viết ra từ nội dung của issue.
Mô tả
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.
- Ngôn ngữ chính
- TypeScript
- Star
- 0
- Fork
- 4
- Merge trung bình
- 18 giờ 41 phút
- Pull request đã merge (30 ngày)
- 48
Chuẩn bị môi trường
Khởi chạy dev container của dự án ngay trên trình duyệt, bằng tài khoản GitHub của bạn.
- Không có Dockerfile hay tệp Docker Compose
- Không có mẫu pull request
- Đọc hướng dẫn đóng góp
Bắt đầu từ đâu
- Đọc hết issue, rồi đọc hướng dẫn đóng góp của dự án.
- Bình luận trên issue rằng bạn sẽ nhận — tránh hai người làm cùng một việc.
- Fork repository và làm thay đổi trên một nhánh.
- Mở pull request có tham chiếu số hiệu của issue.
Issue khác của DiffCI/core
-
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 78/100
Maintainer thường phản hồi trong vòng 1 ngày
-
Agent tools: changed_files lists only the new path of a renamed fileCó thể đã có người làm @FredApps đã nhận hôm nay. Đang mở
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 88/100
Maintainer thường phản hồi trong vòng 1 ngày
-
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 84/100
DiffCI/core#243 · 1 bình luận ·
Maintainer thường phản hồi trong vòng 1 ngày
-
adapter good first issue
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 88/100
Maintainer thường phản hồi trong vòng 1 ngày
-
adapter bug good first issue
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 84/100
Maintainer thường phản hồi trong vòng 1 ngày
Issue tương tự
-
agent-ready area: ui-server priority: p3 type: test
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 78/100
schlessera/brain-kit#4249 ·
Maintainer thường phản hồi trong vòng 1 ngày
-
documentation tool triaged
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 73/100
can1357/oh-my-pi#19608 · 2 bình luận ·
Maintainer thường phản hồi trong vòng 1 ngày
-
dependencies tech-debt
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 65/100
bcgov/nr-waste-plus#1549 ·
Maintainer thường phản hồi trong vòng 1 ngày
-
enhancement good first issue
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 78/100
blixvip/solana-token-meta#17 ·
-
enhancement good first issue
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 78/100
blixvip/solana-tx-parse#18 ·