Title
split_view::outer-iterator::operator++ misspecified
Status
new
Section
[range.split.outer]
Submitter
Tim Song

Created on 2020-11-20.00:00:00 last changed 1 month ago

Messages

Date: 2020-11-30.16:33:04

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;
    
Date: 2020-11-15.00:00:00

[ 2020-11-29; Reflector prioritization ]

Set priority to 2 during reflector discussions.

Date: 2020-11-20.00:00:00

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.

History
Date User Action Args
2020-11-30 16:33:04adminsetmessages: + msg11638
2020-11-21 16:13:19adminsetmessages: + msg11630
2020-11-20 00:00:00admincreate