Are you thinking of lookarounds? Backreferences do have some performance impact but a lookahead or lookbehind much more so. That definitely breaks the regularity, but I’m not sure that applies to backreferences (which may be my own ignorance). Performance wise unmatched lookarounds are the least performant getting worse as the size of the corpus increases. A positive lookahead/lookbehind has to scan all the text before or after the assertion to determine match failure and likewise negatives must do the same to determine match success. Greedier matching also amplifies things here (do you want just the first match or all of them?)
I’m more fluent in regex syntaxes than in the implementation details of any specific regex engine, so please correct me if you know Im wrong, both for my own edification and so that when I share things going forward Im sharing the most accurate information that I can.
Turns out we’re both off the mark: it’s catastrophic backtracking that is “dangerously” vulnerable to performance issues. Something as simple as (a+)+b is enough to trigger the “bad” behavior. I assume you can achieve it with back references and lookarounds as well.
Thank you friend! I honestly had almost forgotten that you could + on a group (in extended syntax i think?) like you can with *. In my experience I find lots of * groups and I do my best to convert those to a range eg {3,5}. When you can’t typically you can set least still use an open range floor {3,} or ceiling {,5}. I’m a big fan of explicit constraints when you have enough information to set them. It’s another good maintainability practice in my experience. The more clear the regex the less example data you need to understand the intention. I especially like eg ruby’s regexp.x flag that let’s you ignore literal newlines and whitespace in the pattern (not to be confused with regexp.X which does the same but for the corpus), so you can split your pattern over multiple lines. I like to use indentations when it helps readability and that also allows a multi line comment header indented the same way. Sometimes you can even set inline comments depending on language/engine/syntax. For significant whitespace in the pattern wrap each whitespace character in a character class containing only itself: eg [ ][ ] for two literal spaces to match. This is also how I handle patterns for eg sed or grep in bash/zsh which have their own whitespace semantics, to get whitespace literals in your patterns without the need to escape anything. The non-literal part of the pattern doesnt change, and the literal part gets substituted in piped through something like sed -E ‘/./[\1]/g’
Are you thinking of lookarounds? Backreferences do have some performance impact but a lookahead or lookbehind much more so. That definitely breaks the regularity, but I’m not sure that applies to backreferences (which may be my own ignorance). Performance wise unmatched lookarounds are the least performant getting worse as the size of the corpus increases. A positive lookahead/lookbehind has to scan all the text before or after the assertion to determine match failure and likewise negatives must do the same to determine match success. Greedier matching also amplifies things here (do you want just the first match or all of them?)
I’m more fluent in regex syntaxes than in the implementation details of any specific regex engine, so please correct me if you know Im wrong, both for my own edification and so that when I share things going forward Im sharing the most accurate information that I can.
Turns out we’re both off the mark: it’s catastrophic backtracking that is “dangerously” vulnerable to performance issues. Something as simple as
(a+)+bis enough to trigger the “bad” behavior. I assume you can achieve it with back references and lookarounds as well.This video gives a good breakdown of what exactly is going on inside a compiled regex automata that encodes such a case: https://www.youtube.com/watch?v=gITmP0IWff0
Thank you friend! I honestly had almost forgotten that you could + on a group (in extended syntax i think?) like you can with *. In my experience I find lots of * groups and I do my best to convert those to a range eg {3,5}. When you can’t typically you can set least still use an open range floor {3,} or ceiling {,5}. I’m a big fan of explicit constraints when you have enough information to set them. It’s another good maintainability practice in my experience. The more clear the regex the less example data you need to understand the intention. I especially like eg ruby’s regexp.x flag that let’s you ignore literal newlines and whitespace in the pattern (not to be confused with regexp.X which does the same but for the corpus), so you can split your pattern over multiple lines. I like to use indentations when it helps readability and that also allows a multi line comment header indented the same way. Sometimes you can even set inline comments depending on language/engine/syntax. For significant whitespace in the pattern wrap each whitespace character in a character class containing only itself: eg [ ][ ] for two literal spaces to match. This is also how I handle patterns for eg sed or grep in bash/zsh which have their own whitespace semantics, to get whitespace literals in your patterns without the need to escape anything. The non-literal part of the pattern doesnt change, and the literal part gets substituted in piped through something like sed -E ‘/./[\1]/g’