views don't work with std::experimental::generator objects

[aligature]

I was excited to try out the experimental coroutine features in Visual Studio 2017 RC with range v3 to see how well they worked together. I was surprised when it didn't work. It's a bit hard to wade through the machinery for pipeable, pipeable_binder, etc. to tell if this might be on purpose (like the restriction against viewing r-value containers) or an accidental side effect of the concept check or something else.

#include "stdafx.h"

#include <iostream>
#include <experimental/generator>
#include <range/v3/all.hpp>

std::experimental::generator<int> UpTo(int to)
{
   for (auto i = 0; i < to; ++i)
      co_yield i;
}

int main(int argc, char *argv[])
{
   auto generator = UpTo(10);
   for (auto i : generator | ranges::view::remove_if([](auto i) { return i % 2 == 1; }))
      std::cout << i << std::endl;

   return 0;
}

Errors:

Build started ...
test64.cpp
d:\code\test64\test64.cpp(17): error C3312: no callable 'begin' function found for type 'void'
d:\code\test64\test64.cpp(17): error C3312: no callable 'end' function found for type 'void'
d:\code\test64\test64.cpp(17): error C2065: 'i': undeclared identifier
Done building project "test64.vcxproj" -- FAILED.
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========

The generator is an l-value and it's iterator returns an int const&.

[CaseyCarter]

I believe the issue is that std::experimental::generator has iterators that don't model the Ranges TS InputIterator concept due to some persnickety semantic mismatch. I'll hash this out with Gor and we'll see if we can get the two to play well together.

[aligature]

Excellent. Thanks for pursuing it. I know the concept checks are being emulated, but is there any way to debug the checks? The no callable 'begin' function found for type 'void' error is inscrutable.

[toby-allsopp]

Here's the generator class I managed to get working today with the help of @CaseyCarter and @ericniebler in the cpplang slack today: https://gist.github.com/toby-allsopp/2a06027d37b5a6c7c54fbd3d7f77ad26

[CaseyCarter]

Status: After 00ed689bac7a9dcd8601dbde382758675516799d, Range-V3-VS2015 now admits input iterators that return void from their post-increment operator (i.e., '*i++' is not required to be a valid expression). This makes it straightforward to implement a generator wrapper for a coroutine with iterators that model InputIterator.

I have a new & improved <experimental/generator> with an implementation of generator that models InputRange. It has been code reviewed and is fighting its way through our internal CI queue. Once it has been finalized and checked into source control to appear "in an upcoming release of Visual Studio™" I'll attach here for interested persons, and leave this issue open until said "upcoming release" actually occurs.

[ericniebler]

Will that New And Improved™ generator use @toby-allsopp's clever reference counting trick? That is, will it satisfy View? Please?

[CaseyCarter]

Not at this time. To comply with [res.on.data.races], a reference counter must not introduce data races. I am opposed to introducing "invisible" atomics and making the abstraction non-zero cost for the common case.

I would certainly consider shipping a generator_view in the library distinct from std::experimental::generator with an atomic reference count or warnings in giant flashing red letters, though.

[ericniebler]

I don't see any place in https://github.com/toby-allsopp/ranges-coroutines where a non-atomic increment is done on a const object, logical or otherwise. Where is the race? I see that coroutine_handle<>::promise returns a mutable reference despite being const. Is that the problem? If such access is race-y, why does coroutine_handle do it this way? EDIT: because it represents a level of indirection. Where is the promise stored, anyway? Do these things ever get shared across threads?

What if we overload the constructor of shared_coroutine_handle to perform interlocked increments when copy constructing from a const object, and non-interlocked increments when copying from a non-const objects? generator only models InputRange and has non-const begin() and end(). These things will never be const-qualified, so we can avoid the cost of interlocked operations in all practical cases. EDIT: it could race with a destructor. Is that it?

My grasp of the rules on data races is tenuous, so take all this with a grain of salt.

[toby-allsopp]

I think more investigation/experimentation/measurement/etc is needed before we know what's best to do about making a generator that models View. Just being able to use generator as a Range is a big step forward - we can live without piping temporary generators for a little while longer :)

[CaseyCarter]

Where is the race?

If two threads with copies of a generator make unsequenced copies, the shared_coroutine_handle copy constructor makes unsequenced calls to promise_type::add_ref which make unsequenced writes to ref_count.

I think more investigation/experimentation/measurement/etc is needed before we know what's best to do about making a generator that models View.

I agree, and investigation/experimentation is MUCH easier for us to do in range-v3 than by trying to redesign std::experimental::generator that's shipping in VS.

[ericniebler]

So, if the coroutine is not inlined into the current thread's stack frame, the runtime allocates it on the heap, along with the promise. The promise could in theory be referenced from multiple threads. Got it.

[CaseyCarter]

So, if the coroutine is not inlined into the current thread's stack frame, the runtime allocates it on the heap, along with the promise.

Yes, although kind of the other way around: the runtime nominally allocates the promise and stack frame using the promise's operator new, which can be optimized away since C++14 decided we don't actually care about calls to operator new.

[aligature]

Thanks for the help, everyone.

[CaseyCarter]

It is very likely that a future release of Visual Studio will include an <experimental/generator> header with contents substantially similar to:

// generator experimental header

/***
*generator
*
*       Copyright (c) Microsoft Corporation. All rights reserved.
*
*       Purpose: Library support of coroutines. generator class
*       http://open-std.org/JTC1/SC22/WG21/docs/papers/2015/p0057r0.pdf
*
*       [Public]
*
****/
#pragma once
#ifndef _EXPERIMENTAL_GENERATOR_
#define _EXPERIMENTAL_GENERATOR_
#ifndef RC_INVOKED

#ifndef _RESUMABLE_FUNCTIONS_SUPPORTED
#error <experimental/generator> requires /await compiler option
#endif /* _RESUMABLE_FUNCTIONS_SUPPORTED */

#include <experimental/resumable>

#pragma pack(push, _CRT_PACKING)
#pragma push_macro("new")
#undef new

_STD_BEGIN

namespace experimental {

    template <typename _Ty, typename _Alloc = allocator<char>>
    struct generator
    {
        struct promise_type
        {
            _Ty const *_CurrentValue;

            promise_type &get_return_object()
            {
                return *this;
            }

            bool initial_suspend()
            {
                return (true);
            }

            bool final_suspend()
            {
                return (true);
            }

            void yield_value(_Ty const &_Value)
            {
                _CurrentValue = _STD addressof(_Value);
            }

            template <typename _Uty>
            _Uty && await_transform(_Uty &&_Whatever)
            {
                static_assert(_Always_false<_Uty>::value,
                    "co_await is not supported in coroutines of type std::experiemental::generator");
                return _STD forward<_Uty>(_Whatever);
            }

            using _Alloc_traits = allocator_traits<_Alloc>;
            using _Alloc_of_char_type =
                typename _Alloc_traits::template rebind_alloc<char>;

            void *operator new(size_t _Size)
            {
                _Alloc_of_char_type _Al;
                return _Al.allocate(_Size);
            }

            void operator delete(void *_Ptr, size_t _Size) _NOEXCEPT
            {
                _Alloc_of_char_type _Al;
                return _Al.deallocate(static_cast<char *>(_Ptr), _Size);
            }
        };

        struct iterator
        {
            using iterator_category = input_iterator_tag;
            using difference_type = ptrdiff_t;
            using value_type = _Ty;
            using reference = _Ty const &;
            using pointer = _Ty const *;

            coroutine_handle<promise_type> _Coro = nullptr;

            iterator() = default;
            iterator(nullptr_t) : _Coro(nullptr)
            {
            }

            iterator(coroutine_handle<promise_type> _CoroArg) : _Coro(_CoroArg)
            {
            }

            iterator &operator++()
            {
                _Coro.resume();
                if (_Coro.done())
                    _Coro = nullptr;
                return *this;
            }

            void operator++(int)
            {
                // This postincrement operator meets the requirements of the Ranges TS
                // InputIterator concept, but not those of Standard C++ InputIterator.
                ++*this;
            }

            bool operator==(iterator const &_Right) const
            {
                return _Coro == _Right._Coro;
            }

            bool operator!=(iterator const &_Right) const
            {
                return !(*this == _Right);
            }

            reference operator*() const
            {
                return *_Coro.promise()._CurrentValue;
            }

            pointer operator->() const
            {
                return _Coro.promise()._CurrentValue;
            }
        };

        iterator begin()
        {
            if (_Coro) {
                _Coro.resume();
                if (_Coro.done())
                    return {nullptr};
            }

            return {_Coro};
        }

        iterator end()
        {
            return {nullptr};
        }

        explicit generator(promise_type &_Prom)
            : _Coro(coroutine_handle<promise_type>::from_promise(_Prom))
        {
        }

        generator() = default;

        generator(generator const &) = delete;

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

        generator(generator &&_Right) : _Coro(_Right._Coro)
        {
            _Right._Coro = nullptr;
        }

        generator &operator=(generator &&_Right)
        {
            if (this != _STD addressof(_Right)) {
                _Coro = _Right._Coro;
                _Right._Coro = nullptr;
            }
            return *this;
        }

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

    private:
        coroutine_handle<promise_type> _Coro = nullptr;
    };

} // namespace experimental

_STD_END

#pragma pop_macro("new")
#pragma pack(pop)
#endif /* RC_INVOKED */
#endif /* _EXPERIMENTAL_GENERATOR_ */