Provide an API for comparing the equivalence of two `Regex` values (while permitting false negatives)

[dolezvo1]

I'd like to test a function that is supposed to output a regular expression, however I wasn't able to find a reasonably accurate way to do this, and I suspect there currently isn't any.

I'm aware that the reason for removal has been explained in #178. A workaround using r1.as_str() == r2.as_str() has been mentioned in both #313 and #364, however this does not appear to handle the cases where the regexes are compiled from the same string while using different options, i.e. has false positives in the context of "do two regexes return the same output for any possible input?".

A method that would not require the user of this library to maintain their own comparison code (i.e. r1.source_and_options_equals(r2)) would be preferable to a mechanism for exposing the compile options (i.e. r1.as_str() == r2.as_str() && r1.case_insensitive() == r2.case_insensitive() && ...).

[dolezvo1]

Would it be reasonable to introduce a new feature gate, and add a conditional regex_automata::util::syntax::Config field to Regex, along with a conditional method that would use it and the source string for the comparison?

Since this is supposed to be used for testing, there hopefully shouldn't be performance penalty for release binaries with this approach, however perhaps the size of regex_automata::util::syntax::Config is negligible considering the Regex already has to contain the original string and the feature gate is in fact unnecessary?

Regarding the comparison itself, is the original string and regex_automata::util::syntax::Config sufficient to determine whether two Regexes are "equal", or does the meta::Config field of the RegexBuilder have any impact on the matching behaviour?

[BurntSushi]

I would also like to have this impl personally. It's just extremely convenient, and realistically, any "true" definition of equivalent regexes that corresponds to the actual language of the regular expression (formally) won't really be possible. Or at the very least, it would require a different API that makes the costs of such an operation---in the fully general case---much clearer. Even then, it would only work for the subset of regexes that can compile to a full DFA. Not all can. Moreover, one can implement that today, quite annoyingly, using the lowest level APIs for traversing DFAs in regex-automata.

But as a maintainer, I feel somewhat the opposite about this, because I think an Eq (and I say Eq because we'd add an Eq if we add a PartialEq) impl could lead to some very surprising results. That is, I think it's perfectly reasonable for someone to expect Regex::new("a").unwrap() == Regex::new("[a]").unwrap() to always return true. It's easier to argue in favor of the Eq impl when the looming threat of users confused and citing the principle of least surprise is over your head. :P And of course, once this impl is added, that's it.

I think this is a request about semantics. I don't think performance concerns really come into this. I think we could defensibly define equality inherently containing false negatives with respect to the language described by the regular expression. We could do that. But it won't stop people from being surprised.

i.e. has false positives in the context of "do two regexes return the same output for any possible input?".

The problem here is that it's trivial to make your implementation have false positives. My example of a and [a] is one such example.

The main way to work around this is to include all options in the regex string itself instead of using the builder. It's annoying to encode shit in strings like it's the 80s or something, but it's probably the most robust way to do what you want. I've certainly lowered myself to committing similar crimes in the past.

Given that the stated use case here is tests and some that is, from what I can tell, at worst an inconvenience... I'd say I've talked myself into passing on this one.

In theory I'd be open to this, but it would require several compelling use cases that can't otherwise be worked around. And an analysis on the user confusion this may cause.

[dolezvo1]

Yes, I understand your objections to implementing PartialEq. I personally disagree, but regardless, would you at least be open to providing a method that would expose the functionality while adequately describing the semantics of the operation, i.e. something like r1.source_and_options_equals(r2)?

[BurntSushi]

I think I'm open to that. Ideally it would be as minimal as possible. The semantics here may be tricky to get correct, but I think the API promises can be vague enough to leave us wiggle room. The most important bit is that we cannot have false positives. That is, if we say two regexes are equivalent, then they must describe the same regular language. False negatives are okay. (They must be.)