microsoft / microsoft/vscode-textmate

100% Freeze on any catastrophic backtracking

Open
#104 4 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

question
Dominant language
TypeScript
Stars
678
Forks
135
Avg merge
1d 14h
Merged PRs (30d)
2

Description

Reasons a change is needed:

  • Debugging catastrophic backtracking is tough because the entire process freezes. Inside of VS Code, basically the only way to find the bug is to guess what it is, and the see if the process still crashes.
  • Catastrophic backtracking is easy to accidentally introduce, even for regex veterans
  • Catastrophic backtracking is hard to write tests for; it can require a very specific circumstance to become catastrophic

Recommended change:
Find some way to have a timeout on a per-line check. If the line goes past the timeout (ex: 5 seconds) the parser just groups the entire rest of the document (all of the remaining lines) as one scope, and closes any unclosed scopes. The reason being: that it would fail safely (no freeze) but would fail badly (not-user friendly) so that the failsafe is not used a a crutch to allow poorly written regex to become acceptable. Failing like this would also give the dev the ability to see exactly which line the error occurred at.

Difficulty:
Probably pretty difficult. The only solutions I can imagine are that the code needs to be async (I'd assume its currently synchronous), or some advanced tool like worker threads would need to be used (pass the current line to the worker, let it start working, if the worker doesn't finish in the timeout, then fail)

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start by tracing the parser's per-line tokenization path and how regular expressions are evaluated. Done means a catastrophic-backtracking case no longer freezes the process: it times out, groups the remaining document as one scope, closes unclosed scopes, and identifies the failing line.

Written by the indexing model from the issue text.

Assessment

Tech stack
typescript
Domain
performance
Issue type
Bug
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.