Issue 4127: The Standard Library should not use predicates of the form pred(*i) != false

4127. The Standard Library should not use predicates of the form `pred(*i) != false`

Section: 22.10.18.3 [func.search.bm], 22.10.18.4 [func.search.bmh], 23.2.7.1 [associative.reqmts.general], 23.3.9.5 [list.ops], 26.6.6 [alg.find], 26.6.9 [alg.find.first.of], 26.6.10 [alg.adjacent.find], 26.6.11 [alg.count], 26.6.12 [alg.mismatch], 26.6.15 [alg.search], 26.8.1 [alg.sorting.general] Status: New Submitter: Hewill Kang Opened: 2024-07-25 Last modified: 2024-08-05

Priority: 3

View all issues with New status.

Discussion:

The boolean-testable concept introduced in P1964R2 places appropriate constraints on boolean-ish types, so that !pred(x) or i != last && pred(*i) always has a valid definition.

Subsequently, P2167R3 applied this concept to 26.2 [algorithms.requirements] p6, requiring that decltype(pred(*first)) should model boolean-testable.

However, boolean-testable does not guarantee that pred(*i) != false is valid, because the type may overload operator==. It is necessary to replace this form of expression with an appropriate one as we do in P1964R2.

[2024-07-27; Daniel comments]

I would recommend to add a wrapping "bool(pred([…]))" and possibly even extend to "bool(pred([…])) is true" following our usual wording convention, since an English phrase of the form "if pred([…])" where pred([…]) is potential non-bool and the English "if" is not a C++ language if (with built-in conversion semantics) doesn't sound like a meaningful phrase to me.

[2024-08-02; Reflector poll]

Set priority to 3 after reflector poll. "Needs more 'is true' added". "Would prefer not to have explicit conversions to bool unless boolean-testable requires that. The 'Let E be' lists don't need an 'is true' there, but the use of 'E' should say 'is true'". [alg.search] and [func.search.bm] have changed editorially in the draft, the proposed resolution needs updating.

Previous resolution [SUPERSEDED]:

This wording is relative to N4986.
Modify 22.10.18.3 [func.search.bm] as indicated:
boyer_moore_searcher(RandomAccessIterator1 pat_first,
                     RandomAccessIterator1 pat_last,
                     Hash hf = Hash(),
                     BinaryPredicate pred = BinaryPredicate());
-1- Preconditions: The value type of RandomAccessIterator1 meets the Cpp17DefaultConstructible, the Cpp17CopyConstructible, and the Cpp17CopyAssignable requirements.
-2- Let V be iterator_traits<RandomAccessIterator1>::value_type. For any two values A and B of type V, if pred(A, B) == true, then hf(A) == hf(B) is true.
[…]
-7- Returns: A pair of iterators i and j such that

(7.1) — i is the first iterator in the range [first, last - (pat_last_ - pat_first_)) such that for every non-negative integer n less than pat_last_ - pat_first_ the following condition holds: pred(*(i + n), *(pat_first_ + n)) != false, and

[…]
Modify 22.10.18.4 [func.search.bmh] as indicated:
boyer_moore_horspool_searcher(RandomAccessIterator1 pat_first,
                              RandomAccessIterator1 pat_last,
                              Hash hf = Hash(),
                              BinaryPredicate pred = BinaryPredicate());
-1- Preconditions: The value type of RandomAccessIterator1 meets the Cpp17DefaultConstructible, Cpp17CopyConstructible, and Cpp17CopyAssignable requirements.
-2- Let V be iterator_traits<RandomAccessIterator1>::value_type. For any two values A and B of type V, if pred(A, B) == true, then hf(A) == hf(B) is true.
[…]
-7- Returns: A pair of iterators i and j such that

(7.1) — i is the first iterator in the range [first, last - (pat_last_ - pat_first_)) such that for every non-negative integer n less than pat_last_ - pat_first_ the following condition holds: pred(*(i + n), *(pat_first_ + n)) != false, and

[…]
Modify 23.2.7.1 [associative.reqmts.general] as indicated:
-3- The phrase "equivalence of keys" means the equivalence relation imposed by the comparison object. That is, two keys k1 and k2 are considered to be equivalent if for the comparison object comp, !comp(k1, k2) == false && !comp(k2, k1) == false.
[…]
-177- The fundamental property of iterators of associative containers is that they iterate through the containers in the non-descending order of keys where non-descending is defined by the comparison that was used to construct them. For any two dereferenceable iterators i and j such that distance from i to j is positive, the following condition holds:
!value_comp(*j, *i) == false
-178- For associative containers with unique keys the stronger condition holds:
value_comp(*i, *j) != false
Modify 23.3.9.5 [list.ops] as indicated:
size_type remove(const T& value);
template<class Predicate> size_type remove_if(Predicate pred);
-15- Effects: Erases all the elements in the list referred to by a list iterator i for which the following conditions hold: *i == value, pred(*i) != false. Invalidates only the iterators and references to the erased elements.
-16- Returns: The number of elements erased.
-17- Throws: Nothing unless an exception is thrown by *i == value or pred(*i) != false.
[…]
Modify 26.6.6 [alg.find] as indicated:

-1- Let E be:

(1.1) — *i == value for find;

(1.2) — pred(*i) != false for find_if;

(1.3) — !pred(*i) == false for find_if_not;
[…]

Modify 26.6.9 [alg.find.first.of] as indicated:

-1- Let E be:

(1.1) — *i == *j for the overloads with no parameter pred;

(1.2) — pred(*i, *j) != false for the overloads with a parameter pred and no parameter proj1;
[…]

Modify 26.6.10 [alg.adjacent.find] as indicated:

-1- Let E be:

(1.1) — *i == *(i + 1) for the overloads with no parameter pred;

(1.2) — pred(*i, *(i + 1)) != false for the overloads with a parameter pred and no parameter proj1;
[…]

Modify 26.6.11 [alg.count] as indicated:

-1- Let E be:

(1.1) — *i == value for the overloads with no parameter pred or proj;

(1.2) — pred(*i) != false for the overloads with a parameter pred but no parameter proj;
[…]

Modify 26.6.12 [alg.mismatch] as indicated:

-2- Let E be:

(2.1) — !(*(first1 + n) == *(first2 + n)) for the overloads with no parameter pred;

(2.2) — !pred(*(first1 + n), *(first2 + n)) == false for the overloads with a parameter pred and no parameter proj1;
[…]

Modify 26.6.15 [alg.search] as indicated:

-1- Returns: The first iterator i in the range [first1, last1 - (last2-first2)) such that for every non-negative integer n less than last2 - first2 the following corresponding conditions hold: *(i + n) == *(first2 + n), pred(*(i + n), *(first2 + n)) != false. Returns first1 if [first2, last2) is empty, otherwise returns last1 if no such iterator is found.
[…]
-6- Returns: The first iterator i in the range [first, last-count) such that for every non-negative integer n less than count the following corresponding conditions hold: *(i + n) == value, pred(*(i + n), value) != false. Returns last if no such iterator is found.

Modify 26.8.1 [alg.sorting.general] as indicated:

-3- For all algorithms that take Compare, there is a version that uses operator< instead. That is, comp(*i, *j) != false defaults to *i < *j != false. For algorithms other than those described in 26.8.4 [alg.binary.search], comp shall induce a strict weak ordering on the values.

[2024-08-03; Daniel provides improved wording]

The current wording is inconsistent in regard to explicit conversion to bool and lack of them in cases of expressions whose value is required to satisfy the boolean-testable constraints. To realize consistent results for all subclause references touched by the changes required by this issue I decided that every E definition remains unconverted but and that every E evaluation is interpreted as if an implied bool conversion has been applied based on the reflector preference for that simplified approach.

Nonetheless, during the wording preparation I noticed that the wording in the Throws: element 23.3.9.5 [list.ops] p17 is seriously missing the additional extra conversion to bool for both expressions, because the boolean-testable requirements do not impose a no-throw requirement for that conversion, and they must therefore be included here.

This problem will be handled by a separate issue (LWG 4132), because the rationale for this change is different from the actual target of this issue and not related to the other consistency adjustments done by the wording below.

Proposed resolution:

This wording is relative to N4988.

Modify 22.10.18.3 [func.search.bm] as indicated:
```
boyer_moore_searcher(RandomAccessIterator1 pat_first,
                     RandomAccessIterator1 pat_last,
                     Hash hf = Hash(),
                     BinaryPredicate pred = BinaryPredicate());
```
-1- Preconditions: The value type of RandomAccessIterator1 meets the Cpp17DefaultConstructible, Cpp17CopyConstructible, and Cpp17CopyAssignable requirements.
-2- Let V be iterator_traits<RandomAccessIterator1>::value_type. For any two values A and B of type V, if pred(A, B) == true is true, then hf(A) == hf(B) is true.
[…]
```
template<class RandomAccessIterator2>
  pair<RandomAccessIterator2, RandomAccessIterator2>
    operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const;
```
[…]
-7- Returns: A pair of iterators i and j such that
1. (7.1) — i is the first iterator in the range [first, last - (pat_last_ - pat_first_)) such that for every non-negative integer n less than pat_last_ - pat_first_ the following condition holds: pred(*(i + n), *(pat_first_ + n)) != false is true, and
2. (7.2) — j == next(i, distance(pat_first_, pat_last_)) is true.
Modify 22.10.18.4 [func.search.bmh] as indicated:
```
boyer_moore_horspool_searcher(RandomAccessIterator1 pat_first,
                              RandomAccessIterator1 pat_last,
                              Hash hf = Hash(),
                              BinaryPredicate pred = BinaryPredicate());
```
-1- Preconditions: The value type of RandomAccessIterator1 meets the Cpp17DefaultConstructible, Cpp17CopyConstructible, and Cpp17CopyAssignable requirements.
-2- Let V be iterator_traits<RandomAccessIterator1>::value_type. For any two values A and B of type V, if pred(A, B) == is true, then hf(A) == hf(B) is true.
[…]
```
template<class RandomAccessIterator2>
  pair<RandomAccessIterator2, RandomAccessIterator2>
    operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const;
```
[…]
-7- Returns: A pair of iterators i and j such that
1. (7.1) — i is the first iterator in the range [first, last - (pat_last_ - pat_first_)) such that for every non-negative integer n less than pat_last_ - pat_first_ the following condition holds: pred(*(i + n), *(pat_first_ + n)) != false is true, and
2. (7.2) — j == next(i, distance(pat_first_, pat_last_)) is true.
Modify 23.2.7.1 [associative.reqmts.general] as indicated:

-3- The phrase "equivalence of keys" means the equivalence relation imposed by the comparison object. That is, two keys k1 and k2 are considered to be equivalent if for the comparison object comp, !comp(k1, k2) == false && !comp(k2, k1) == false is true.
[…]
-177- The fundamental property of iterators of associative containers is that they iterate through the containers in the non-descending order of keys where non-descending is defined by the comparison that was used to construct them. For any two dereferenceable iterators i and j such that distance from i to j is positive, the following condition holds:

!value_comp(*j, *i) == false is true.

-178- For associative containers with unique keys the stronger condition holds:

value_comp(*i, *j) != false is true.
Modify 23.3.9.5 [list.ops] as indicated:
```
size_type remove(const T& value);
template<class Predicate> size_type remove_if(Predicate pred);
```
-15- Effects: Erases all the elements in the list referred to by a list iterator i for which the following conditions hold: *i == value is true, pred(*i) != false is true. Invalidates only the iterators and references to the erased elements.
-16- Returns: The number of elements erased.
-17- Throws: Nothing unless an exception is thrown by *i == value or pred(*i) != false.
[…]
Modify 26.6.6 [alg.find] as indicated:

[Drafting note: Sub-bullets (1.4), (1.5), and (1.6) below regarding invoke expressions are similarly required model boolean-testable, as specified by concept predicate (18.7.4 [concept.predicate]), therefore the explicit conversion is removed here for consistency]
-1- Let E be:
1. (1.1) — *i == value for find;
2. (1.2) — pred(*i) != false for find_if;
3. (1.3) — !pred(*i) == false for find_if_not;
4. (1.4) — bool(invoke(proj, *i) == value) for ranges::find;
5. (1.5) — bool(invoke(pred, invoke(proj, *i))) for ranges::find_if;
6. (1.6) — bool(!invoke(pred, invoke(proj, *i))) for ranges::find_if_not.
-2- Returns: The first iterator i in the range [first, last) for which E is true. Returns last if no such iterator is found.
Modify 26.6.9 [alg.find.first.of] as indicated:
-1- Let E be:
1. (1.1) — *i == *j for the overloads with no parameter pred;
2. (1.2) — pred(*i, *j) != false for the overloads with a parameter pred and no parameter proj1;
3. (1.3) — bool(invoke(pred, invoke(proj1, *i), invoke(proj2, *j))) for the overloads with parameters pred and proj1.
[…]
-3- Returns: The first iterator i in the range [first1, last1) such that for some iterator j in the range [first2, last2) E ~~holds~~ is true. Returns last1 if [first2, last2) is empty or if no such iterator is found.
Modify 26.6.10 [alg.adjacent.find] as indicated:
-1- Let E be:
1. (1.1) — *i == *(i + 1) for the overloads with no parameter pred;
2. (1.2) — pred(*i, *(i + 1)) != false for the overloads with a parameter pred and no parameter proj;
3. (1.3) — bool(invoke(pred, invoke(proj, *i), invoke(proj, *(i + 1)))) for the overloads with both parameters pred and proj.
-2- Returns: The first iterator i such that both i and i + 1 are in the range [first, last) for which E ~~holds~~ is true. Returns last if no such iterator is found.
Modify 26.6.11 [alg.count] as indicated:
-1- Let E be:
1. (1.1) — *i == value for the overloads with no parameter pred or proj;
2. (1.2) — pred(*i) != false for the overloads with a parameter pred but no parameter proj;
3. (1.3) — invoke(proj, *i) == value for the overloads with a parameter proj but no parameter pred;
4. (1.4) — bool(invoke(pred, invoke(proj, *i))) for the overloads with both parameters proj and pred.
-2- Effects: Returns the number of iterators i in the range [first, last) for which E ~~holds~~ is true.
Modify 26.6.12 [alg.mismatch] as indicated:
-2- Let E be:
1. (2.1) — !(*(first1 + n) == *(first2 + n)) for the overloads with no parameter pred;
2. (2.2) — !pred(*(first1 + n), *(first2 + n)) == false for the overloads with a parameter pred and no parameter proj1;
3. (2.3) — !invoke(pred, invoke(proj1, *(first1 + n)), invoke(proj2, *(first2 + n))) for the overloads with both parameters pred and proj1.
[…]
-4- Returns: { first1 + n, first2 + n }, where n is the smallest integer in [0, N) such that E ~~holds~~ is true, or N if no such integer exists.
Modify 26.6.15 [alg.search] as indicated:

-1- Returns: The first iterator i in the range [first1, last1 - (last2-first2)) such that for every non-negative integer n less than last2 - first2 the following corresponding conditions hold: *(i + n) == *(first2 + n) is true, pred(*(i + n), *(first2 + n)) != false is true. Returns first1 if [first2, last2) is empty, otherwise returns last1 if no such iterator is found.
[…]
-6- Let E be pred(*(i + n), value) != false for the overloads with a parameter pred, and *(i + n) == value otherwise.
-7- Returns: The first iterator i in the range [first, last - count) such that for every non-negative integer n less than count the condition E is true. Returns last if no such iterator is found.
Modify 26.8.1 [alg.sorting.general] as indicated:

[Drafting note: The wording below does not require extra "is true" added to the adjusted expressions. This is comparable to the E cases above, since 26.8.1 [alg.sorting.general] p2 already points out:

The return value of the function call operation applied to an object of type Compare, when converted to bool, yields true if the first argument of the call is less than the second, and false otherwise.

]

-3- For all algorithms that take Compare, there is a version that uses operator< instead. That is, comp(*i, *j) != false defaults to *i < *j != false. For algorithms other than those described in 26.8.4 [alg.binary.search], comp shall induce a strict weak ordering on the values.

4127. The Standard Library should not use predicates of the form pred(*i) != false

4127. The Standard Library should not use predicates of the form `pred(*i) != false`