You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
I'm currently writing a library to construct NFA from JS RegExp, so plugged it into Prism's pattern test to check for exponential backtracking and fixed (almost) all offending patterns. Please note that my test was not great. It only tested for one kind of exponential backtracking and it couldn't handle assertions and lookarounds at all, so there might very well be other patterns that still have exponential backtracking.
Now for the complex part: Textile.
The modifierRegex looks like this: \([^|)]+\)|\[[^\]]+\]|\{[^}]+\} with the important parting being the \([^|)]+\). Many pattern then use the pattern like this: (?:<MOD>|[<>=()])+ to get modifiers and some other characters.
The problem is that these other characters include ( and ), so for a string of the form /(?:\(=\)){100}/ there are 2^100 ways to match it.
The problem here is that I can't just remove the () from the set of other characters because unholy creations like p((. some text are valid.
So, how do we solve this?
Regarding Textile, would it help to constrain the modifier regexp more?
Inside the pair of parentheses, there can only be either a classname followed by an optional id or just an id, I believe. So the content could be restricted to [\w-][\w\d-]*(?:#[\w-][\w\d-]*)?|#[\w-][\w\d-] (yes, this is not the exact grammar for identifiers in CSS but it's good enough). Would that help mitigate the backtracking issue?
Similarly, the content inside square brackets could be constrained too but I'm not sure there is the need.
Actually, maybe it's even simpler to just ban [<>=()] from the modifier? \([^|<>=()]+\)|\[[^\]]+\]|\{[^}]+\}
Ok. I solved it by using a special pattern for parentheses.
The "only classnames and attributes" approach (was my first thought as well) wouldn't have worked because textile basically allows anything in between brackets.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
I'm currently writing a library to construct NFA from JS RegExp, so plugged it into Prism's pattern test to check for exponential backtracking and fixed (almost) all offending patterns. Please note that my test was not great. It only tested for one kind of exponential backtracking and it couldn't handle assertions and lookarounds at all, so there might very well be other patterns that still have exponential backtracking.
Now for the complex part: Textile.
The
modifierRegexlooks like this:\([^|)]+\)|\[[^\]]+\]|\{[^}]+\}with the important parting being the\([^|)]+\). Many pattern then use the pattern like this:(?:<MOD>|[<>=()])+to get modifiers and some other characters.The problem is that these other characters include
(and), so for a string of the form/(?:\(=\)){100}/there are 2^100 ways to match it.The problem here is that I can't just remove the
()from the set of other characters because unholy creations likep((. some textare valid.So, how do we solve this?
(I refactored textile a little anyway.)