Re: Safe user-facing pattern matching.

[Coda Highland <chighland@...>]

On Thu, Mar 30, 2017 at 8:38 AM, Jorge <xxopxe@gmail.com> wrote:
> Well, that does not make the program safe, it just kills it, no? :)
>
> I was thinking something Lua only, like pattern subset/sanitization or such
>
> Jorge

In terms of computational theory, there's not a whole lot you can do
without sacrificing something significant somewhere. The biggest time
sink in a pattern-matching system is the need to perform backtracking
when an option fails.

Every regular expression (in the true computational sense, not in the
Perl sense) can be converted to a non-backtracking parser. A
non-backtracking parser is guaranteed to complete in linear time.
However, that transformation can itself be expensive, and for a
one-off pattern on a small subject this transformation is probably
more expensive than just running the backtracking version.

You could, hypothetically, create a pattern syntax that makes it
easier to construct a non-backtracking parser out of it, but you might
be surprised what you lose in convenience. You don't lose anything in
true expressive power, but the equivalent patterns might end up being
substantially bulkier to write. Basically, every form of repetition
has to encode its termination condition somehow, and alternatives have
to go with the first available choice because once the decision is
made there's no backtracking.

/s/ Adam