"How to prevent catastrophic regex? "redux

[Kenneth Lorber]

http://lua-users.org/lists/lua-l/2020-06/msg00083.html and the following thread discuss the ability for Lua patterns to chew up lots of CPU but never presented a solution. Here's a possible solution.

The idea is to add a counter that is decremented at each point the existing code tests ms->matchdepth; if the counter hits zero an error is raised, which can be caught with pcall. (If the counter starts at zero, no limit is imposed.)

The code is available at https://github.com/nhkeni/lua/tree/keni-pattern and is based off current code from https://github.com/lua/lua . The makefile in this repo is set for MacOS and there is a pattern_limit_demo.lua file using the pattern from the previous thread; the entire set of changes can be turned on and off with the PATTERN_LIMIT define in luaconf.h.

Questions:
- Does anyone have a pattern that this code cannot limit? (Did I miss any cases that can loop significantly?)
- What's the time penalty for this concept? On a M2 MacBook Pro, adding the code _reduces_ the run time by about 15%. I'll guess that cache line alignment is improved by adding one variable to MatchState, but I can't prove it. Regardless, it makes it hard to reason about the cost.

Insights/comments/questions welcome.

Thanks!