Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

avoid catastrophic backtracking #99

Closed
wants to merge 1 commit into from
Closed

Conversation

mbostock
Copy link
Member

@mbostock mbostock commented Mar 27, 2022

Fixes #97. Supersedes #89. No change in behavior; just a new implementation that uses a tokenizer and a positive lookahead to mimic an atomic group.

Demo: https://observablehq.com/d/ae672b8cd8dacfab

On my computer, the input with 200,000 repeating ones took 57 seconds with the current version of d3-color, and <1ms with this new approach.

@mbostock mbostock requested a review from Fil March 27, 2022 23:50
This was referenced Mar 27, 2022
@mbostock
Copy link
Member Author

Superseded by #100. (This implementation is fine, too, but I think I’d prefer to minimize churn with the other approach.)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Development

Successfully merging this pull request may close these issues.

Avoid catastrophic backtracking when parsing
1 participant