如何通过重载 yield_value 递归生成生成器？

Question

我创建了一个 generator 将有一个重载 operator* 以便转换为 std::ranges::subrange 我还想从 [= 重载 yield_value 20=] 接受将递归产生的子范围类型。

源代码：

template <typename T>
class [[nodiscard]] generator {
  public:
    using value_type = T;
    struct promise_type;
    using handle_type = std::coroutine_handle<promise_type>;

  private:
    handle_type handle_ { nullptr };

    explicit generator(handle_type handle) : handle_(handle) {}

  public:
    struct promise_type {
      value_type value_;

      generator<value_type> get_return_object() {
        return generator{ handle_type::from_promise(*this) };
      }

      std::suspend_always initial_suspend() { return {}; }
            
      std::suspend_always final_suspend() { return {}; }
           
      void unhandled_exception() { std::terminate(); }

      std::suspend_always yield_value(const value_type& value) noexcept {
        value_ = value;
        return {};
      }
            
      template <typename U>
      std::suspend_never await_transform(U&&) = delete;

      void return_void() {}
    };

    generator() noexcept = default;
    generator(const generator&) = delete;
    generator(generator&& other) noexcept
    : handle_(std::move(other.handle_)) {
      other.handle_ = nullptr;
    }

    ~generator() { if (handle_) handle_.destroy(); }

    generator& operator=(const generator&) = delete;

    generator& operator=(generator&& other) noexcept {
      handle_ = std::move(other.handle_);
      other.handle_ = nullptr;
      return *this;
    }

    void swap(generator& other) noexcept {
      using std::swap;
      swap(handle_, other.handle_);
    }

    class iterator {
      private:
        handle_type handle_;
        friend generator;

        explicit iterator(handle_type handle) noexcept
        : handle_(handle) {}

      public:
        using value_type = std::remove_cvref_t<T>;
        using reference  = value_type&;
        using const_reference = const value_type&;
        using pointer = value_type*;
        using const_pointer = const value_type*;
        using size_type = std::size_t;
        using difference_type = std::ptrdiff_t;
        using iterator_category = std::input_iterator_tag;

        iterator() noexcept = default;

        friend bool operator==(const iterator& iter, std::default_sentinel_t) noexcept {
          return iter.handle_.done();
        }

        friend bool operator==(std::default_sentinel_t s, const iterator& iter) noexcept {
          return (iter == s);
        }

        iterator& operator++() {
          if (handle_.done()) handle_.promise().unhandled_exception();
          handle_.resume();
          return *this;          
        }

        iterator operator++(int) {
          auto temp = *this;
          ++*this;
          return temp;
        }

        reference operator*() noexcept {
          return handle_.promise().value_;
        }

        pointer operator->() noexcept {
          return std::addressof(operator*());
        }

    };

    iterator begin() noexcept {
      if (handle_) {
        handle_.resume();
        if (handle_.done())
          handle_.promise().unhandled_exception();
      }
      return iterator{handle_};
    }

    std::default_sentinel_t end() noexcept {
        return std::default_sentinel;
    }
};

示例：

auto generate_0(int n) -> generator<int> {
  while (n != 0)
    co_yield n--;
}

auto generate_1() -> generator<int> {
  for (const auto& elem : generate_0(10)) {
    co_yield elem;
  }
}

generate_1 显然可以工作，但我希望得到与 generate_1 相同的输出，即每个元素直接在 yield_value:[=27 中 co_yield-ed =]

auto generate_1() -> generator<int> {
  co_yield* generate_0(10);
}

这样：在 class generator:

auto operator*() {
      return std::ranges::subrange(begin(), end());
}

在嵌套中 class generator<...>::promise_type:

template <typename U>
std::suspend_always yield_value(const std::ranges::subrange<U, std::default_sentinel_t>& r) noexcept {
  /** ... **/
  return {};
}

Answer 1

要事第一：bugs/odd 位在你这边。

我认为尝试支持旧式迭代器不值得。默认构造 generator<T>::iterator 没有意义，新式迭代器概念不需要它。你可以从 iterator 中撕下很多垃圾。
- 还有，==很神奇。如果 x == y 没有找到匹配的 operator== 但 y == x 找到了，那么 x == y 会自动重写为 y == x。您不需要同时提供两个 operator==。
promise_type 不需要按值保存 T。从协程中产生东西的一个奇怪的事情是，如果你使 yield_value 成为引用，你可以获得对处于协程状态的东西的引用。但是协程状态会一直保留到你恢复它！所以 promise_type 可以代替 T const*。现在您不再需要 T.
generator 最初挂起似乎不自然。目前，如果您执行 g.begin(); g.begin();，即使您没有递增任何迭代器，您也会推进生成器。如果你让 g.begin() not 恢复协程并移除初始暂停，一切正常。或者，您可以让 generator 跟踪它是否已启动协程，并且仅将其推进到 begin() 的第一个 yield，但这很复杂。
虽然在通常为 UB 的每个操作上调用 std::terminate() 可能很好，但它也很嘈杂，我只是不打算将其包含在此答案中。另外，请不要通过unhandled_exception调用它。这只是令人困惑：unhandled_exception 有一个非常具体的目的和意义，而你只是不尊重这一点。
generator<T>::operator=(generator&&) 泄露了 *this 的协程状态！此外，您的 swap 是非标准的，因为它不是免费的 2-arg 函数。我们可以通过让 operator= 做 swap 做的事情然后摆脱 swap 来解决这些问题，因为 std::swap 有效。

从 design/theory 的角度来看，我认为改为实现此语法更有意义。

auto generate_1() -> generator<int> {
  co_await generate_0(10);
}

A generator 可以暂时放弃对另一个的控制，并且可以在 awaits 之后恢复运行ning 用于内部 generator 到运行 out .通过使生成器包装范围，可以很容易地在此基础上实现从范围产生的东西。这也符合其他语言的语法，例如 Haskell.

现在，协程没有堆栈。这意味着一旦我们越过函数调用边界远离像 generate_1 这样的协程，就不可能通过与调用者关联的协程状态 suspend/resume 该函数。所以我们必须实现我们自己的堆栈，在这里我们扩展我们的协程状态（promise_type），能够记录它当前正在从另一个协程中拉取而不是拥有自己的值。（请注意，这也适用于从范围中产生：调用任何函数以从 generator_1 接收范围将无法控制 generator_1 的协程。）我们通过使 promise_type 抱一个

std::variant<T const*, std::subrange<iterator, std::default_sentinel_t>> value;

请注意 promise_type 不拥有 subrange 代表的 generator。大多数时候（就像在 generator_1 中一样）应用与 yield_value 相同的技巧：拥有子协程状态的 generator 位于调用协程的堆栈中。

（这也是反对从范围直接实现 co_yield 的一点：我们需要修复进入 promise_type 的任何类型。从 API 的角度来看，它是对于 generator<T> 中的 co_await 接受 generator<T>s 是可以理解的。但是如果我们实现 co_yield 我们将只能直接处理一种特定类型的范围 - subrange 包装一个 generator。那会很奇怪。否则我们需要实现类型擦除；但在这种情况下，对范围进行类型擦除的最明显的方法是制作一个 generator。所以我们回到 generator awaiting 另一个作为更基本的操作。）

运行宁 generator 的堆栈现在是一个链表，贯穿其 promise_type。其他一切都只是自己写。

struct suspend_maybe { // just a general-purpose helper
    bool ready;
    explicit suspend_maybe(bool ready) : ready(ready) { }
    bool await_ready() const noexcept { return ready; }
    void await_suspend(std::coroutine_handle<>) const noexcept { }
    void await_resume() const noexcept { }
};

template<typename T>
class [[nodiscard]] generator {
public:
    struct iterator;
    struct promise_type;
    using handle_type = std::coroutine_handle<promise_type>;
    using range_type = std::ranges::subrange<iterator, std::default_sentinel_t>;

private:
    handle_type handle;

    explicit generator(handle_type handle) : handle(std::move(handle)) { }
public:
    class iterator {
    private:
        handle_type handle;
        friend generator;

        explicit iterator(handle_type handle) noexcept : handle(handle) { }
    public:
        // less clutter
        using iterator_concept = std::input_iterator_tag;
        using value_type = std::remove_cvref_t<T>;
        using difference_type = std::ptrdiff_t;

        // just need the one
        bool operator==(std::default_sentinel_t) const noexcept {
            return handle.done();
        }
        // need to muck around inside promise_type for this, so the definition is pulled out to break the cycle
        inline iterator &operator++();
        void operator++(int) { operator++(); }
        // again, need to see into promise_type
        inline T const *operator->() const noexcept;
        T const &operator*() const noexcept {
          return *operator->();
        }
    };
    iterator begin() noexcept {
        return iterator{handle};
    }
    std::default_sentinel_t end() const noexcept {
        return std::default_sentinel;
    }

    struct promise_type {
        // invariant: whenever the coroutine is non-finally suspended, this is nonempty
        // either the T const* is nonnull or the range_type is nonempty
        // note that neither of these own the data (T object or generator)
        // the coroutine's suspended state is often the actual owner
        std::variant<T const*, range_type> value = nullptr;

        generator get_return_object() {
            return generator(handle_type::from_promise(*this));
        }
        // initially suspending does not play nice with the conventional asymmetry between begin() and end()
        std::suspend_never initial_suspend() { return {}; }
        std::suspend_always final_suspend() noexcept { return {}; }
        void unhandled_exception() { std::terminate(); }
        std::suspend_always yield_value(T const &x) noexcept {
            value = std::addressof(x);
            return {};
        }
        suspend_maybe await_transform(generator &&source) noexcept {
            range_type range(source);
            value = range;
            return suspend_maybe(range.empty());
        }
        void return_void() { }
    };

    generator(generator const&) = delete;
    generator(generator &&other) noexcept : handle(std::move(other.handle)) {
        other.handle = nullptr;
    }
    ~generator() { if(handle) handle.destroy(); }
    generator& operator=(generator const&) = delete;
    generator& operator=(generator &&other) noexcept {
        // idiom: implementing assignment by swapping means the impending destruction/reuse of other implicitly handles cleanup of the resource being thrown away (which originated in *this)
        std::swap(handle, other.handle);
        return *this;
    }
};

// these are both recursive because I can't be bothered otherwise
// feel free to change that if it actually bites
template<typename T>
inline auto generator<T>::iterator::operator++() -> iterator& {
    struct visitor {
        handle_type handle;
        void operator()(T const*) { handle(); }
        void operator()(range_type &r) {
            if(r.advance(1).empty()) handle();
        }
    };
    std::visit(visitor(handle), handle.promise().value);
    return *this;
}
template<typename T>
inline auto generator<T>::iterator::operator->() const noexcept -> T const* {
    struct visitor {
        T const *operator()(T const *x) { return x; }
        T const *operator()(range_type &r) {
            return r.begin().operator->();
        }
    };
    return std::visit(visitor(), handle.promise().value);
}

似乎没有东西着火。

static_assert(std::ranges::input_range<generator<unsigned>>); // you really don't need all that junk in iterator!
generator<unsigned> generate_0(unsigned n) {
    while(n != 0) co_yield n--;
}
generator<unsigned> generate_1(unsigned n) {
    co_yield 0;
    co_await generate_0(n);
    co_yield 0;
}
int main() {
    auto g = generate_1(5);
    for(auto i : g) std::cout << i << "\n"; // 0 5 4 3 2 1 0 as expected
    // even better, asan is happy!
}

如果你想从任意范围产生值，我会实现这个类型橡皮擦。

auto generate_all(std::ranges::input_range auto &&r) -> generator<std::ranges::range_value_t<decltype(r)>> {
    for(auto &&x : std::forward<decltype(r)>(r)) co_yield std::forward<decltype(x)>(x);
}

所以你得到例如

generator<unsigned> generate_1(unsigned n) {
    co_await generate_all(std::array{41u, 42u, 43u});
    co_await generate_0(n);
    co_yield 0;
}

如何通过重载 yield_value 递归生成生成器？

How to recursively yield generator by overloading yield_value?

c++

generator

c++-coroutine