Re: Our regex vs. POSIX on "longest match"

Martijn van Oosterhout <kleptog@svana.org> writes:
> On the otherhand, I think requiring an "overall longest match" makes
> your implementation non-polynomial complexity.

Only if you don't know how to implement it -- a DFA-based implementation
doesn't have much trouble with this.

> [ equivalence of knapsack problem to regexes with bounded repetition ]

Interesting, but note that neither the POSIX spec nor our implementation
permit arbitrarily large repetition counts, so the theoretical
NP-completeness is only theoretical.

> The question is, what are users expecting of the PostgreSQL regex
> implementation?

I think a minimum expectation is that we adhere to the POSIX
specification.
        regards, tom lane