JavaScript traps · Chapter 16 of 16
Regex catastrophic backtracking
Build it in your browser: a real editor and terminal, AI that explains, and tests that tell you when it works.
- Part: Time
- 3 tasks
- JavaScript
- In the all labs plan
The first 2 chapters of JavaScript traps are free. This one comes with the all labs plan.
Why you need this
A regular expression runs synchronously: until it answers, nothing else in the process runs, not a timer, not a request. Here a 10 ms timer waits for one name check:
const started = performance.now();
setTimeout(() => {
console.log('timer due at 10 ms ran at', Math.round(performance.now() - started), 'ms');
}, 10);
/^([A-Za-z]+\s?)+$/.test('a'.repeat(24) + '!');
timer due at 10 ms ran at 587 ms
Node serves every customer from one event loop, so one slow check stops all of them. A valid code is quick: the first way to match succeeds. Only a code that fails late is slow, which is why every test of good coupons passed.
The cure is a pattern where every text can match in one way only: each repeated part must start with something the part before it cannot match. There is no library to install (the lab has none), and V8's linear-time engine needs a flag the lab does not set.
What you build: 3 tasks
Each task has tests. You write the code in the lab's editor and press Check.
- Task 1
repro.js: freeze checkout with one coupon on purpose
Write reproduce() in repro.js. Call isValidCoupon(code) from coupon.js with a code of 33 capital letters and digits followed by one ! (34 characters, like the ticket's), and resolve to what it returns. Call it directly, not through deadline.js.
The check runs your reproduce() twice, each time in a separate node process with a deadline: beside the original coupon.js it must still be running after 2 seconds (checkout frozen), and beside a fixed coupon.js it must resolve to false. So it must really call isValidCoupon with a long code that fails late. Beside today's coupon.js, node repro.js does not finish for minutes: that is the bug, so press Ctrl+C.
- Task 2
coupon.js: a pattern that cannot hang
Fix isValidCoupon(code) in coupon.js so it answers at once for any code, while accepting and refusing exactly the same codes as before. Valid: groups of capital letters and digits joined by single dashes, like CHAI40 or MONSOON-2026-FOR-TWO. Refused: anything else, such as lower case, spaces, a dash at the start or the end, two dashes together, any other character, or an empty code. There is no length limit: long festival codes are valid. Keep the log line coupon <code>: valid or refused, one per code, as it is.
The check uses its own codes, and runs long codes that fail late (up to 46 characters) in a separate process with a 4-second deadline. A length limit alone is not a fix: the old pattern hangs on 34 characters, and a long valid code must still be accepted.
- Task 3
coupon.test.js: a test that would have caught it
Write a vitest test file, coupon.test.js, that would have caught this bug before the coupon went out. The check runs your file three times: beside the original coupon.js, where at least one test must fail; beside the fixed coupon.js, where every test must pass; and beside a wrong fix that only refuses codes over 40 characters, where at least one test must fail.
So run isValidCoupon through runWithDeadline from deadline.js with a bad code shorter than 40 characters (about 34), and a deadline of a second or two (1500 ms is plenty), and expect { timedOut: false, value: false }; also check that a good code is still accepted. Never call isValidCoupon directly with a bad code in the test: a stuck test cannot be stopped, and the check stops the whole run after 20 seconds. Each test must finish within 3 seconds.
What you will learn
- repro.js: freeze checkout with one coupon on purpose
- coupon.js: a pattern that cannot hang
- coupon.test.js: a test that would have caught it
More in Time
Build "Regex catastrophic backtracking" yourself
Tapri runs on JavaScript, and Kabir, its senior developer, keeps assigning you tickets. Each is a real trap interviews love to ask about. A real editor and terminal in your browser, AI that explains, and a Check that says when it works.
The first 2 chapters of JavaScript traps are free. This one comes with the all labs plan.