Skip to content

Instantly share code, notes, and snippets.

@rsms

rsms/chromium-v8-firefox-regexp-bug.md

Last active November 4, 2019 21:05
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save rsms/88d1f241f9a7d8ca21e39293d98b5fe3 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save rsms/88d1f241f9a7d8ca21e39293d98b5fe3 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
chromium-v8-firefox-regexp-bug.md

Subject

RegExp that never finishes; hangs with 100% CPU. Easy repro

Repro steps

  1. Run the attached script in V8/Chrome
  2. Sample the process
  3. Notice how it's stuck in v8::internal::NativeRegExpMacroAssembler::Execute

Expected outcome

The code to not take forever to finish

Actual outcome

The code takes seemingly forever to finish. I've ran it on a MacBook Pro 15" 2019 for a few minutes (seemingly stuck in an infinite loop.)

Notes

This code finished in a few milliseconds in Safari 12, but it does also get stuck in Firefox 70.

The script "re-bug-repro.js" is the main, simple repro case.

The script "re-bug-step-by-step.js" measures time taken incrementally as it increases the match input. Running this script will print out run times which will look like this:

// input line range: time to execute regexp
0-1: 0.010ms
0-2: 0.008ms
0-3: 0.010ms
0-4: 0.265ms
0-5: 9.143ms
0-6: 253.939ms
0-7: 10121.292ms
0-8: 260236.880ms

graph

Raw
re-bug-repro.js
let s = `
graph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
`
console.time("match")
console.log(s.match(/\b(?:di)?graph(?:\s+[^\{]+|)*[\r\n\s]*\{/m))
console.timeEnd("match")
Raw
re-bug-step-by-step.js
let s = `
graph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
raph raph raph raph raph raph raph raph raph raph
`
// Search our way to degenerate cases
let lines = s.trim().split("\n"), m
for (let start = 0; start < lines.length; start++) {
for (let end = start+1; end < lines.length; end++) {
let s2 = lines.slice(start, end).join("\n")
console.log(`———————————————————————————————————————\n${start}-${end}\n${s2}`)
console.time(`${start}-${end}`)
m = s2.match(/\b(?:di)?graph(?:\s+[^\{]+|)*[\r\n\s]*\{/m)
console.timeEnd(`${start}-${end}`)
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment