Problems with Regular Expressions

The Emacs regexp implementation, like many of its kind, is generally robust but occasionally causes trouble in either of two ways: matching may run out of internal stack space and signal an error, and it can take a long time to complete. The advice below will make these symptoms less likely and help alleviate problems that do arise.

• Anchor regexps at the beginning of a line, string or buffer using zero-width assertions (‘^’ and \`). This takes advantage of fast paths in the implementation and can avoid futile matching attempts. Other zero-width assertions may also bring benefits by causing a match to fail early.
• Avoid or-patterns in favor of character alternatives: write ‘[ab]’ instead of ‘a\|b’. Recall that ‘\s-’ and ‘\sw’ are equivalent to ‘[[:space:]]’ and ‘[[:word:]]’, respectively.
• Since the last branch of an or-pattern does not add a backtrack point on the stack, consider putting the most likely matched pattern last. For example, ‘^\(?:a\|.b\)*c’ will run out of stack if trying to match a very long string of ‘a’s, but the equivalent ‘^\(?:.b\|a\)*c’ will not.

  (It is a trade-off: successfully matched or-patterns run faster with the most frequently matched pattern first.)

• Try to ensure that any part of the text can only match in a single way. For example, ‘a*a*’ will match the same set of strings as ‘a*’, but the former can do so in many ways and will therefore cause slow backtracking if the match fails later on. Make or-pattern branches mutually exclusive if possible, so that matching will not go far into more than one branch before failing.

  Be especially careful with nested repetitions: they can easily result in very slow matching in the presence of ambiguities. For example, ‘\(?:a*b*\)+c’ will take a long time attempting to match even a moderately long string of ‘a’s before failing. The equivalent ‘\(?:a\|b\)*c’ is much faster, and ‘[ab]*c’ better still.

• Don’t use capturing groups unless they are really needed; that is, use ‘\(?:…\)’ instead of ‘\(…\)’ for bracketing purposes.
• Consider using rx (see Rx Notation); it can optimize some or-patterns automatically and will never introduce capturing groups unless explicitly requested.

If you run into regexp stack overflow despite following the above advice, don’t be afraid of performing the matching in multiple function calls, each using a simpler regexp where backtracking can more easily be contained.