Idea: make it possible to obtain std::partial_ordering from a match

[leni536]

Right now there is an implicit conversion from a match (more explicitly from a captured_content::storage as I can see). I wonder if it was possible to convert a match to std::partial_ordering to obtain more information from a non-match. The semantics of the returned values would be:

• std::less/std::greater : Not a match and the subject orders lexicographically before/after all possible strings that match the regular expression.
• std::equivalent : It's a match.
• std::unordered : All else.

Use case: searching matching strings in a lexicographically ordered collection of strings efficiently. Right now there is no interface for std::map and std::set to allow this, but other maps and sets could offer searching with a partial_ordering predicate.

Some examples for return values:

constexpr auto re = ctre::match<"^abc[0-46-9]+$">;
static_assert(re("abc1"sv).to_partial_ordering() == std::equivalent);
static_assert(re("bac1"sv).to_partial_ordering() == std::greater);
static_assert(re("aaa1"sv).to_partial_ordering() == std::less);
static_assert(re("abc5"sv).to_partial_ordering() == std::unordered);

[hanickadot]

Sounds interesting, but I'm not sure how to implement it with current backtracking mechanism.

[leni536]

I made a little proof of concept: leni536/compile-time-regular-expressions@53883de

One can try it out with make test_ordering && ./test_ordering, the full project fails to compile just yet. I implemented the partial ordering for CharacterLike matchers and only a few character atoms, only the ones that are required to compile test_ordering.cpp.

These modifications are rather intrusive and dirty. If it ever grows into a pull request I would prefer writing it from the ground up.

[hanickadot]

If I go this way ... I will introduce function named "ordered_match" or something like this. Calculating partial ordering for every match would be expansive. And I'm still not sure if you can easily do that, especially with things like alternation.

[leni536]

Yeah, think a separate "ordered_match" and "ordered_evaluate" could make sense.

About alternations: As I see the problem is how to handle an empty select<> since it can't possibly match any string. So it's not clear how a target should order against it as the conditions for both 'less' and 'greater' apply. Maybe partial_ordering is the wrong type for this and an enum is needed that has "less_and_greater" as an element. If an ordered_match returned less_and_greater on an empty select<> then alternations could be handled in the recursion:

• If both evaluate() returns less_and_greater, then return less_and_greater
• Else if both return with less or less_and_greater then return less
• Else the same for greater
• Else return unordered

Then if we really need to return an std::partial_order then we convert less_and_greater to greater (note, that it would mean that the regex can't match any string).

Alternatively an empty select could be disallowed and evaluate can be specialized for a select with one element (I don't know if it would break anything). Then in the recursion we only need to check if both evaluate returns the same ordering.

Also I think we can safely return 'unordered' from any non-match. Just that when we return less or greater

[leni536]

I realized that my current approach doesn't work at all (for the pattern "[0-2]b" and target "1a" it returns less). Keeping track only of a single partial ordering doesn't work. Instead I need to keep track of the set of possible partial orderings during evaluation (possibly in a bit field). I will work on an other proof of concept and I think it should give an elegant solution for alternations as well.

[leni536]

I now have a working PoC with a new approach (leni536/compile-time-regular-expressions@bfb5faa). I now keep track in captures if comparing less or greater is still possible at a given point. This also gives a nice way to deal with alternations and targets that compare greater because of their length.

It's quite dirty and intrusive yet again. For the actual implementation I would like to do the following:

• Use a scoped enum or a proper class for partial_ordering
• Implement separate ordered_match and ordered_evaluation functions.
• When returning less or greater is no longer possible from a given capture then falling back to the unordered evaluation functions might help with performance.