I was reading §5.1.7.2 of Rainer Grimm's book C 20: Get the Details about defining one's own view type when I decided to modify the provided code sample to see if it would work with a std::list. The code ultimately looks like this:

#include <concepts>
#include <iostream>
#include <list>
#include <ranges>
#include <vector>

template <std::ranges::input_range Range>
  requires std::ranges::view<Range>
class ContainerView : public std::ranges::view_interface<ContainerView<Range>> {
  private:
  std::ranges::iterator_t<Range> begin_ {};
  std::ranges::sentinel_t<Range> end_ {};
  Range range_ {};

  public:
  constexpr ContainerView() = default;

  constexpr ContainerView(Range r)
      : begin_(std::begin(r))
      , end_(std::end(r))
      , range_(std::move(r))
  {
  }

  constexpr auto begin() const { return begin_; }
  constexpr auto end() const { return end_; }
};

int main()
{
  std::list my_list { 1, 2, 3 };
  auto my_container_view { ContainerView(std::views::all(my_list)) };

  for (auto const& c : my_container_view)
    std::cout << c << '\n';
}

The program compiles successfully with x86-64 clang v17.0.1 and the flags -std=c 20 -fsanitize=undefined -fsanitize=address -Wall -Wextra -Werror, and, when run, it prints the numbers 1, 2 and 3 and exits gracefully as expected.

However, out of curiosity, when I altered the main function to wrap my_list in a call to std::move when passing it to std::views::all, the program appears to get stuck in an infinite recursion repeatedly printing the elements of the list.

int main()
{
  std::list my_list { 1, 2, 3 };
  auto my_container_view { ContainerView(std::views::all(std::move(my_list))) };

  for (auto const& c : my_container_view)
    std::cout << c << '\n';
}

What I found strange is that when I simply exchange the std::list for a std::vector instead and keep the rest of the code untouched, the program prints each element once and exits gracefully:

int main()
{
  std::vector my_vec { 1, 2, 3 };
  auto my_container_view { ContainerView(std::views::all(std::move(my_vec))) };

  for (auto const& c : my_container_view)
    std::cout << c << '\n';
}

I also do not get the aberrant behavior when I remove the indirection of the ContainerView type and iterate over the std::list directly:

int main()
{
  std::list my_list { 1, 2, 3 };

  for (auto const& c : std::move(my_list))
    std::cout << c << '\n';
}

Given that each variation of the code compiles and yields no compile time constraint errors, is there a semantic constraint that I am violating with the use of std::move and std::list in combination with the custom view type that would cause the apparent undefined behavior?

CodePudding user response：

std::list needs to use a sentinel node for its end iterator (it needs to support --). There are two ways to do it:

• a sentinel node embedded in the list itself. libstdc and libc do this.
• a dynamically allocated sentinel node. MSVC does this.

In the first case, when you move a list, iterators to elements become iterators of the new list, but the end iterator still points to the original list. So in your code, if r wasn't empty then begin_ is pointing the first element in range_ after the move, but end_ is still pointing into the soon-to-be-destroyed r. So when the loop tries to increment begin_ until it reaches end_...well, it will never do that and you get an infinite loop. (It is convenient for the sentinel node's next pointer to point to *begin(), which is why this looks like it's iterating the list multiple times.)

This is only a problem when you move the list because views::all is by-reference on lvalues, so in that case everything is dealing with the same list object.

Side note: It's pretty tricky to store an iterator (or sentinel) and the range it points to at the same time if the containing class can be copied or moved. The default memberwise copy/move will not work - you'd need to do the equivalent of non-propagating-cache for the iterator.

CodePudding user response：

Following the advice of @273K, ensuring that begin_ and end_ are initialized in the constructor body following the move of the Range r into range_ in the member initializer list eliminates the undefined behavior.

#include <concepts>
#include <iostream>
#include <list>
#include <ranges>
#include <vector>

template <std::ranges::input_range Range>
  requires std::ranges::view<Range>
class ContainerView : public std::ranges::view_interface<ContainerView<Range>> {
  private:
  std::ranges::iterator_t<Range> begin_ {};
  std::ranges::sentinel_t<Range> end_ {};
  Range range_ {};

  public:
  constexpr ContainerView() = default;

  constexpr ContainerView(Range r)
      : range_(std::move(r))
  {
    begin_ = std::begin(range_);
    end_ = std::end(range_);
  }

  constexpr auto begin() const { return begin_; }
  constexpr auto end() const { return end_; }
};

int main()
{
  std::list my_list { 1, 2, 3 };
  auto my_container_view { ContainerView(std::views::all(std::move(my_list))) };

  for (auto const& c : my_container_view)
    std::cout << c << '\n';
}