Provide a possibility to check if a regex matches a string in full

[Dirk-Herrmann]

Hello,

it would be great if there could be some built-in way to check if a regex matches a string in full.
This would correspond to the fullmatch function in Python: https://docs.python.org/3/library/re.html

Rationale:
In my use case, the regex string is provided as user input and then compiled. The compiled regex is then used to match against some string, and the match is only considered successful if that string is matched completely. For convenience reasons, the user is not expected to enclose their regex with "^" and "$" anchors.

I have tried to emulate this "fullmatch" with the current feature set and the tdfa engine.
What I have come up with are the following options:

Option A: Use the (MatchOffset, MatchLength) overload of the match function. If a full match is possible, the tdfa engine will find it, and then MatchLength will be equal to the length of the string that was matched. This works, but it brings some performance disadvantages: The lack of the anchors seems to slow down the matching significantly (see below). Moreover, the MatchLength result is not really needed in my case, its only purpose is to be compared against the length of the string being matched. Moreover, this string length is also only used for the comparison against MatchLength.

Option B: Enclose the regex string between "^" and "$" anchors and use the Bool overload of the match function.
This is much faster than option A, about a factor of 10. The problem is that this does not work reliably. It does not work if the user has added the "^" and "$" anchors themselves. Figuring this out, however, is tricky, particularly for the "$": A "$" at the end of the user provided regex string could be a quoted "$". Moreover, there are corner cases where adding the anchors also does not work as intended: a stray "\" at the end of a regex string, which would lead to a compile error of the regex engine, would with the added "$" become a valid regex, but the "$" would then be treated as a character rather than an anchor...

Maybe I have missed some option C? If so, I would be glad to learn about it.
If not, then I hope I could convince you why this feature would add value to the regex library.

In any case, thanks a lot for this great piece of software and its nicely designed user interface.

Kind regards,
Dirk

[andreasabel]

regex-tdfa is part of a package collection that all implement a common interface, regex-base: https://hackage-content.haskell.org/package/regex-base-0.94.0.3/docs/Text-Regex-Base-RegexLike.html
As you say there is no "full match" function, and the matchOnce function will also succeed if there is a partial match. As you detail in part "A", there are extra checks needed that the returned match was full (this is maybe negligible effort), and, importantly, there is no option to return Nothing early if the full match fails.

Since I am a third generation maintainer without insights into the original motivation behind the API, I cannot tell why a full-match function does not exist. One can speculate that the availability of the $ and ^ anchors was deemed sufficient, but as you note, the introduction of these anchors into a regex-string is brittle, since regex composition by string concatenation is not compositional..

Maybe the underlying issue is that there is no grammar for regexes that the library collection exposes. Why is the only way to construct a regex this arcane string format whose details no one can remember and whose main motivation can only have been to save keystrokes?

An approach paying tribute the the principles of functional programming would have exposed a functional API to construct regexes.

Maybe this was not pursued because it would have been extra efforts to implement the low-level variants regex-posix and regex-pcre that simply pass the regex to an existing OS library function and marshall the result. So basically, the GIGO way (garbage in - garbage out).

While a general solution for regex-base does not seem feasible, there could be one for regex-tdfa. There is already an accessible grammar for regexes, called Pattern.
Can you try if you can utilize this data structure to add anchors in a safe way, and report back? (Maybe this would be method "C"?)

[Dirk-Herrmann]

Hi Andreas, thanks for the quick response.

It may be possible to add the anchors to a Pattern - but that seems a bit awkward: One could use PConcat, where the pattern is enclosed between PCarat and PDollar - the problem being, that with PCarat and PDollar you would have to give some DoPa number, which seems to reflect the respective character's position in the parsed string. Maybe these DoPa values are not relevant, but this is unclear and for me leaves some doubt about this strategy.

However, your comment pointed me in a good direction: By playing with Pattern a bit I figured out that adding an extra "^" at the beginning of a string does not make any difference: "^^a" is equivalent to "^a", and also equivalent to "^(^a)" etc. Surprisingly, there are no test cases for this scenario: regex-posix-unittest repo. It may be worth adding some - it seems to be in accordance with POSIX.

Similarly, adding "$" to the end of the regex string seems to be OK - given that the regex string could be parsed correctly before adding the "$": Again "x$$" is equivalent to "x$" and "(x$)$". Performance wise this parsing check can be done more cheaply with parseRegex than with makeRegex.

Thus, I now have my "Option C": First parse the regex string with parseRegex, and if that is successful, simply enclose the whole string with "^" and "$", and then do the makeRegex. A nice benefit of this approach is, that - in contrast to makeRegex - parseRegex gives detailed explanations in case of parse errors.

Nevertheless, even if this "Option C" is an acceptable solution for me, a fullmatch feature would be a nice addition...

Thanks a lot again and Kind regards,
Dirk

[andreasabel]

Good point: Pattern is not what it seems on the first glance. It is not a grammar for regexes, but already some "compiled" form of them.

Indeed, ˆ and $ are idempotent operators (in the language of algebra) and it would be easy to express this in tests. It seems though that this package only has unit-test, no QuickCheck tests that would make it easy to state algebraic laws of regular expressions and test them on random data.

Personally, I do not have time to work on this code base beyond the minimal maintenance tasks.
So I won't implement a full-match function myself.

But high-quality PRs would be accepted. A first step could be a reproducer with for the performance problems with partial matches if you want a full match. Such would be necessary to warrant the introduction of a new full-match function. Alas, we do not even have a benchmark suite in this repo, so there would be some infrastructure work required.