[Indirect]Relation + non-comparable sentinels and input iterators == :-(

[ericniebler]

The range-v3 calendar example has the following:

mismatch(rng-of-iterators, rng-of-sentinels, std::not_equal_to<>{})

This compiles in master but not in the deep-integration branch where mismatch is (properly) constrained with IndirectRelation. (In master, it is constrained with IndirectPredicate.) The issue is that Relation -- as opposed to Predicate -- requires the comparator to be called with all permutations of the two arguments. This falls down badly when, say, std::not_equal_to<> is called with an iterator and a sentinel, because sentinels are not required to be self-comparable.

If we made all sentinels self-comparable (as they were in the olden times), it would still be a problem because InputIterators are not required to be self-comparable.

I really hate that I can't use mismatch in the calendar example because of these aggressive constraints. I'm uncertain what the solution is. Perhaps add back the requirement that sentinels and input iterators are (trivially) self-comparable? That seems undesirable as well.

@CaseyCarter, thoughts?

[ericniebler]

My "fix" for the calendar example is to use std::mismatch instead of ranges::mismatch. 😭

[CaseyCarter]

Perhaps add back the requirement that sentinels and input iterators are (trivially) self-comparable? That seems undesirable as well.

+1. Equality means substitutability: I'm OMDB opposed to requiring delimiter_sentinel('x') and delimiter_sentinel('y') to compare equal if they are not substitutable. If we believe an algorithm can produce a meaningful result with weaker constraints it makes more sense to weaken the constraints than to require everyone who passes arguments to the algorithm to hack up their types to "pretend" to meet the constraints. (Note that IndirectRelation currently has no semantics other than to require a bunch of expressions to be equality-preserving - see #610.)

This is another occurrence of "If the algorithms/concepts require equality instead of equivalence I can't use them when I really want equivalence instead of equality". (See also: the ongoing reflector thread about weakly-equality-comparable-with.) I think it's time to admit that we can't ignore these use cases and take a hard look at how to weaken the requirements that algorithms place on their arguments and instead place requirements on implementations of the algorithms if necessary to provide the same guarantees when the arguments meet the original requirements.

[tomaszkam]

I think we should differentiate the algorithms, that are guaranteed to always compare values in two ranges in specific order (equal, mismatch) and the one that is using fact that provided relation is equivalence (i.e. basing on transitivity, so a == b && b == c => a == c). The former algorithm are then overconstrained, as they use provided functor as a predicate, not an equivalence relation (IndirectlyComparable is I believe supposed to mean).

Thus I propose to change the requirement of:

• find_first_of
• adjacent_find
• unique (in reality adjacent_remove)
• mismatch
• equal.
• search
• seach_n
• replace

[tomaszkam]

For illustration consider the described effects on mismatch:

Returns: { first1 + n, first2 + n }, where n is the smallest integer such that E (!invoke(pred, invoke(proj1, *(first1 + n)), invoke(proj2, *(first2 + n)))) holds, or min(last1 - first1, last2 - first2) if no such integer exists.

To find such n we need only following invocations to be valid invoke(pred, invoke(proj1, *(first1 + n)), invoke(proj2, *(first2 + n))) (in that direction). Note that when equal_to will be used, the additional requirement of this predicate will automaticall apply.

[tomaszkam]

For the use case that is currently not supported, imagine that I have std::vector<std::string> texts and std::vector<std::string> patterns, and I want to find a first pattern that is not found in corresponding text. In non-range version I can write:

std::mismatch(
    texts.begin(), texts.end(),
    patterns.begin(), patterns.end(),
    [](auto const& text, auto const& pattern) { reutrn serachPatternInText(text, pattern); });

Note that my lambda is not symmetric (does not give the same result), but mismatch is guranteed to invoke it with text as first argument and pattern as second.

[ericniebler]

Bumping this up to P1.

[tomaszkam]

P1716: ranges compare algorithm are over-constrained aims to address the problem.