3505. split_view::outer-iterator::operator++ misspecified

Section: 25.7.16.3 [range.lazy.split.outer] Status: C++23 Submitter: Tim Song Opened: 2020-11-20 Last modified: 2023-11-22

Priority: 2

View all other issues in [range.lazy.split.outer].

View all issues with C++23 status.

Discussion:

Prior to the application of P1862R1, the part of split_view::outer-iterator::operator++ that searches for the pattern is specified as:

do {
  const auto [b, p] = ranges::mismatch(current, end, pbegin, pend);
  if (p == pend) {
    current = b; // The pattern matched; skip it
    break;
  }
} while (++current != end);

P1862R1, trying to accommodate move-only iterators, respecified this as

do {
  auto [b, p] = ranges::mismatch(std::move(current), end, pbegin, pend);
  current = std::move(b);
  if (p == pend) {
    break; // The pattern matched; skip it
  }
} while (++current != end);

but this is not correct, because if the pattern didn't match, it advances current to the point of first mismatch, skipping elements before that point. This is totally wrong if the pattern contains more than one element.

Consider std::views::split("xxyx"sv, "xy"sv):

• at the beginning, current points to the first 'x'

• ranges::mismatch produces [iterator to second 'x', iterator to 'y' in pattern]

• current now points to second 'x'

• we increment current in the condition, so it now points to 'y'

At this point there's no way we can find the "xy" in the middle. In fact, in this particular example, we'll increment past the end of the source range at the end of the third iteration.

[2020-11-29; Reflector prioritization]

Set priority to 2 during reflector discussions.

[2021-02-08; Reflector poll]

Set status to Tentatively Ready after six votes in favour during reflector poll.

[2021-02-26 Approved at February 2021 virtual plenary. Status changed: Tentatively Ready → WP.]

Proposed resolution:

This wording is relative to N4868.

1. Modify [range.split.outer] as indicated:

   constexpr outer-iterator& operator++();
   

   -6- Effects: Equivalent to:

   const auto end = ranges::end(parent_->base_);
   if (current == end) return *this;
   const auto [pbegin, pend] = subrange{parent_->pattern_};
   if (pbegin == pend) ++current;
   else if constexpr (tiny-range<Pattern>) {
     current = ranges::find(std::move(current), end, *pbegin);
     if (current != end) {
       ++current;
     }
   }
   else {
     do {
       auto [b, p] = ranges::mismatch(std::move(current), end, pbegin, pend);
       current = std::move(b);
       if (p == pend) {
         current = b;
         break; // The pattern matched; skip it
       }
     } while (++current != end);
   }
   return *this;