In this article, we will analyze in detail the concept of coroutines, their classification, take a closer look at the implementation, assumptions and tradeoffs offered by the new C ++ 20 standard.

General information

Coroutines can be viewed as a generalization of the concept of routines (functions) in terms of operations performed on them. The fundamental difference between coroutines and subroutines is that a coroutine provides the ability to explicitly pause its execution, giving control to other program units and resume its work at the same point when control is gained back, using additional operations, while maintaining local data (execution state). between successive calls, thus providing a more flexible and extended control flow.

To clarify this definition and further reasoning and introduce auxiliary concepts and terms, consider the mechanics of ordinary functions in C ++ and their stack nature.

We will consider the semantics of a function in the context of two operations.

(call). . :

1. — (activation record, activation frame), ;
2. ( ) , ;
3. . ;
4. — , .

, .

(return). . :

1. ( ) ;
2. , ;
3. .

, . ().

:

1. (strictly nested lifetime) . , : . .
2. .

, . — , : ss ( ), bp ( ), sp ( ), ( ). , , .

. , (Calling Convention). , . ( ) . , , , .

:

void bar(int a, int b)
{}

void foo()
{
    int a = 1;
    int b = 2;
    bar(a, b);
}

int main()
{
    foo();
}

- (x86-64 clang 10.0.0 -m32,

32 . 64 , , , ):

bar(int, int):
        push    ebp
        mov     ebp, esp
        mov     eax, dword ptr [ebp + 12]
        mov     ecx, dword ptr [ebp + 8]
        pop     ebp
        ret
foo():
        push    ebp 
        mov     ebp, esp
        sub     esp, 24 
        mov     dword ptr [ebp - 4], 1
        mov     dword ptr [ebp - 8], 2
        mov     eax, dword ptr [ebp - 4]
        mov     ecx, dword ptr [ebp - 8]
        mov     dword ptr [esp], eax
        mov     dword ptr [esp + 4], ecx
        call    bar(int, int)
        add     esp, 24
        pop     ebp
        ret
main:
        push    ebp
        mov     ebp, esp
        sub     esp, 8  
        call    foo()
        xor     eax, eax
        add     esp, 8
        pop     ebp
        ret

:

main, , ebp ( ) .. , ebp esp ( )

| ...            |
+----------------+
| return address |
+----------------+
| saved rbp      |     <-- ebp, esp
+----------------+

foo. . .. 16 8 (4 4 ebp) 8 , .

| ...            |
+----------------+
| return address |
+----------------+
| saved rbp      |     <-- ebp
+----------------+
| ...            |
| 8 byte padding |
| ...            |     <-- esp
-----------------+

foo. call . foo ebp ( ) ebp esp ( ), .

| ...            |
+----------------+
| return address |
+----------------+
| saved rbp      |     <-- ebp
+----------------+
| ...            |
| 8 byte padding |
| ...            |
+----------------+
| return address |
+----------------+
| saved rbp      |     <-- ebp, esp
+----------------+

bar. int — 8 , bar int — 8 . .. 8 ( ebp) 8 . 8 + 8 + 8 = 24 , .

| ...            |
+----------------+
| return address |
+----------------+
| saved rbp      |     <-- ebp
+----------------+
| ...            |
| 8 byte padding |
| ...            |
+----------------+
| return address |
+----------------+
| saved rbp      |     <-- ebp
+----------------+
| local a        |     <-- ebp - 4
+----------------+
| local b        |     <-- ebp - 8
+----------------+
| ...            |
| 8 byte padding |
| ...            |
+----------------+
| arg a          |     <-- esp + 4
+----------------+
| arg b          |     <-- esp
+----------------+

bar. , foo. call . bar ebp ebp esp, .

| ...            |
+----------------+
| return address |
+----------------+
| saved rbp      |     <-- ebp
+----------------+
| ...            |
| 8 byte padding |
| ...            |
+----------------+
| return address |
+----------------+
| saved rbp      |     <-- ebp
+----------------+
| local a        |     <-- ebp - 4
+----------------+
| local b        |     <-- ebp - 8
+----------------+
| ...            |
| 8 byte padding |
| ...            |
+----------------+
| arg a          |     <-- ebp + 12
+----------------+
| arg b          |     <-- ebp + 8
+----------------+
| return address |
+----------------+
| saved rbp      |     <-- ebp, esp
+----------------+

bar . ebp ( , foo) , 4 . 4 . foo.

| ...            |
+----------------+
| return address |
+----------------+
| saved rbp      |     <-- ebp
+----------------+
| ...            |
| 8 byte padding |
| ...            |
+----------------+
| return address |
+----------------+
| saved rbp      |     <-- ebp
+----------------+
| local a        |     <-- ebp - 4
+----------------+
| local b        |     <-- ebp - 8
+----------------+
| ...            |
| 8 byte padding |
| ...            |
+----------------+
| arg a          |     <-- esp + 4
+----------------+
| arg b          |     <-- esp
+----------------+

foo bar . , 24 .

| ...            |
+----------------+
| return address |
+----------------+
| saved rbp      |     <-- ebp
+----------------+
| ...            |
| 8 byte padding |
| ...            |
+----------------+
| return address |
+----------------+
| saved rbp      |     <-- ebp, esp
+----------------+

ebp ( , main) . . main.

| ...            |
+----------------+
| return address |
+----------------+
| saved rbp      |     <-- ebp
+----------------+
| ...            |
| 8 byte padding |
| ...            |     <-- esp
-----------------+

main , , .

| ...            |
+----------------+
| return address |
+----------------+

, , .

, .

1. ;
2. ;
3. ( ).

(symmetric) (asymmetric, semi-symmetric).

, , . : , . , , , .

: , , .

.

A , .

(first-class object, first-class citizen) (constrained, compiler-internal), (handles), .

— , , , ( ). , , . , (function object): , , .

(stackful) (stackless). , , (proccesor stack).

:

• (Application stack). main. . , ;
• (Thread stack). . ( 1-2 );
• (Side stack). (Execution context) , (top level context function, ) . ( ), . : , , .

. — ( , : ) . , - , , .

, c: getcontext, makecontext swapcontext (. Complete Context Control)

#include <iostream>
#include <ucontext.h>

static ucontext_t caller_context;
static ucontext_t coroutine_context;

void print_hello_and_suspend()
{
     //  Hello 
    std::cout << "Hello";
    //     , 
    //    caller_context
    //    coroutine_context    ,
    //   ,     .
    swapcontext(&coroutine_context, &caller_context);
}

void simple_coroutine()
{
    //      coroutine_context
    //     
    //     print_hello_and_suspend.
    print_hello_and_suspend();
    //  print_hello_and_suspend   
    //        Coroutine!   ,
    //    ,
    //      coroutine_context.uc_link, .. caller_context
    std::cout << "Coroutine!" << std::endl;
}

int main()
{
    //  .
    char stack[256];

    //    coroutine_context
    // uc_link   caller_context,     .
    // uc_stack     
    coroutine_context.uc_link          = &caller_context;
    coroutine_context.uc_stack.ss_sp   = stack;
    coroutine_context.uc_stack.ss_size = sizeof(stack);
    getcontext(&coroutine_context);

    //  coroutine_context
    //    ,    
    //        simple_coroutine
    makecontext(&coroutine_context, simple_coroutine, 0);

    //   ,    coroutine_context
    //   caller_context    ,
    //   ,     .
    swapcontext(&caller_context, &coroutine_context);
    //       
    //  
    std::cout << " ";
    //    .
    swapcontext(&caller_context, &coroutine_context);

    return 0;
}

, Boost: Boost.Coroutine, Boost.Coroutine2, Boost ucontext_t fcontext_t — , (, / , ) POSIX .

, , , . , , , , . , , , , .. . .

:

1. (top level function), ;
2. ;
3. , , ;
4. ( ), , .

, C++20, , , .

C++20.

C++ Coroutine TS. Coroutine TS , , .

. range based for, , , begin end, , , . , , .

compile-internal .

, , . , -, , , , -, ( ), .

, , .. .

, C++20 compile-internal asymmetric stackless coroutines.

, , .

New Keywords.

:

• co_await. , , , , ;
• co_yield. , co_await, ;
• co_return. , , .

, .

:

• main;
• return;
• constexpr;
• (auto);
• (variadic arguments, variadic templates);
• ;
• .

User types.

, .

Promise.

Promise . :

• ;
• ;
• ;
• co_await;
• .
  
  promise new delete, .
  
  promise .

Promise std::coroutine_traits , : , , , . std::coroutine_traits :

template <typename Ret, typename = std::void_t<>>
struct coroutine_traits_base
{};

template <typename Ret>
struct coroutine_traits_base<Ret, std::void_t<typename Ret::promise_type>>
{
    using promise_type = typename Ret::promise_type;
};

template <typename Ret, typename... Ts>
struct coroutine_traits : coroutine_traits_base<Ret>
{};

promise_type. std::coroutine_traits, , promise_type . promise_type , .

Promise .

struct Task
{
    struct Promise
    {
        ...
    };
    using promise_type = Promise;
};
...

Task foo()
{
    ...
}

Task , : , () .

Promise — std::coroutine_traits. , ,

class Coroutine
{
public:
    void call(int);
};

namespace std
{
    template<>
    struct coroutine_traits<void, Coroutine, int>
    {
        using promise_type = Coroutine;
    };
}

Promise , , . , lvalues, Promise .. . Promise .

Promise, : Awaitable.

Awaitable.

Awaitable . :

• , co_await;
• ( );
• co_await, .

Awaitable (overload resolution) co_await. , Awaitable. .

, , , , .

Task foo()
{
    using namespace std::chrono_literals;

    //    
    //  
    co_await 10s;
    //  10      .
}

std::chrono::duration<long long>, co_await .

template<typename Rep, typename Period>
auto operator co_await(std::chrono::duration<Rep, Period> duration) noexcept
{
    struct Awaitable
    {
        explicit Awaitable(std::chrono::system_clock::duration<Rep, Period> duration)
            : duration_(duration)
        {}

        ...

    private:

        std::chrono::system_clock::duration duration_;
    };

    return Awaitable{ duration };
}

Awaitable, , .

Awaitable, co_await <expr> , .

{
    //      Promise
    using coroutine_traits = std::coroutine_traits<ReturnValue, Args...>;
    using promise_type = typename coroutine_traits::promise_type;

    ...
    //  co_await <expr>   

    // 1.
    //    Awaitable,     co_await,
    //      (    
    //     Promise),   
    // ..   Awaitable    ,   .
    frame->awaitable = create_awaitable(<expr>);

    // 2.
    //   await_ready().
    //        
    //        
    //   ,   .
    if (!awaitable.await_ready())
    {
        // 3.
        //   await_ready()  false,
        //     ,
        //  :   ,  
        // (  ,    
        //    , 
        //        <resume-point>)

        <suspend-coroutine>

        // 4.
        //   coroutine_handle
        // corotine_handle -    .
        //      :
        //   ( )  .

        using handle_type = std::coroutine_handle<promise_type>;
        using await_suspend_result_type =
            decltype(frame->awaitable.await_suspend(handle_type::from_promise(promise)));

        // 5.
        //   await_suspend(handle), 
        //   await_suspend   
        //       
        //       ( ). 
        //     -  .
        //   ,    

        if constexpr (std::is_void_v<await_suspend_result_type>)
        {
            //    void,
            //      
            // (     ,
            //    )
            frame->awaitable.await_suspend(handle_type::from_promise(promise));
            <return-to-caller-or-resumer>;
        }
        else if constexpr (std::is_same_v<await_suspend_result_type, bool>)
        {
            //    bool,
            //    false,      
            //     
            //  , ,   
            //   Awaitable  
            if (frame->awaitable.await_suspend(handle_type::from_promise(promise))
                <return-to-caller-or-resumer>;
        }
        else if constexpr (is_coroutine_handle_v<await_suspend_result_type>)
        {
            //    std::coroutine_handle<OtherPromise>,
            // ..     ,
            //      ,   
            //       
            //   
            auto&& other_handle = frame->awaitable.await_suspend( 
                handle_type::from_promise(promise));
            other_handle.resume();
        }
        else
        {
            static_assert(false);
        }
    }

    // 6.
    //    ()
    //   await_resume().     .
    //        co_await.
resume_point:
    return frame->awaitable.await_resume();
}

:

1. , , co_await. , , ;
2. , await_suspend . . , - . , await_suspend . await_suspend. await_resume, Awaitable . Promise , await_suspend. , await_suspend: (this ) Promise, .

Awaitable type-traits :

//    std::coroutine_handle
template<typename Type>
struct is_coroutine_handle : std::false_type
{};

template<typename Promise>
struct is_coroutine_handle<std::coroutine_handle<Promise>> : std::true_type
{};

//      await_suspend
// - void
// - bool
// - std::coroutine_handle
template<typename Type>
struct is_valid_await_suspend_return_type : std::disjunction<
    std::is_void<Type>,
    std::is_same<Type, bool>,
    is_coroutine_handle<Type>>
{};

//  await_suspend
template<typename Type>
using is_await_suspend_method = is_valid_await_suspend_return_type<
    decltype(std::declval<Type>().await_suspend(std::declval<std::coroutine_handle<>>()))>;

//  await_ready
template<typename Type>
using is_await_ready_method = std::is_constructible<bool, decltype(
    std::declval<Type>().await_ready())>;

//   Awaitable
/*
templae<typename Type>
struct Awaitable
{
...
    bool await_ready();
    void await_suspend(std::coroutine_handle<>);
    Type await_resume();
...
}
*/
template<typename Type, typename = std::void_t<>>
struct is_awaitable : std::false_type
{};

template<typename Type>
struct is_awaitable<Type, std::void_t<
    decltype(std::declval<Type>().await_ready()),
    decltype(std::declval<Type>().await_suspend(std::declval<std::coroutine_handle<>>())),
    decltype(std::declval<Type>().await_resume())>> : std::conjunction<
    is_await_ready_method<Type>,
    is_await_suspend_method<Type>>
{};

template<typename Type>
constexpr bool is_awaitable_v = is_awaitable<Type>::value;

:

template<typename Rep, typename Period>
auto operator co_await(std::chrono::duration<Rep, Period> duration) noexcept
{
    struct Awaitable
    {
        explicit Awaitable(std::chrono::system_clock::duration duration)
            : duration_(duration)
        {}

        bool await_ready() const noexcept
        {
            return duration_.count() <= 0;
        }

        void await_resume() noexcept
        {}

        void await_suspend(std::coroutine_handle<> h)
        {
            //  timer::async      .
            //     ,   
            //     callback.
            timer::async(duration_, [h]()
            {
                h.resume();
            });
        }

    private:

        std::chrono::system_clock::duration duration_;
    };

    return Awaitable{ duration };
}

// ,         
Task tick()
{
    using namespace std::chrono_literals;

    co_await 1s;
    std::cout << "1..." << std::endl;

    co_await 1000ms;
    std::cout << "2..." << std::endl;
}

int main()
{
    tick();
    std::cin.get();
}

1. tick;
2. co_await Awaitable, 1 ;
3. await_ready, ;
4. tick, ;
5. await_suspend ;
6. await_suspend timer::async, callback. callback ;
7. — main;
8. main get, , . , ;
9. , callback, , ;
10. resume . : tick , , ;
11. await_resume Awaitable, co_await ;
12. await_resume , co_await , ;
13. tick "1...";
14. co_await. 2. , main, a , callback, .. resumer'. ;
15. tick ( )

co_await Awaitable, Promise .

Promise.

Awaitable, Promise , .

:

1. . . .. ;
2. - ( co_awat/co_yield/co_return). , .. ;
3. , . .

//    .
//       
// 1. resume -   , 
//         ,  -.
// 2. promise -   Promise
// 3. state -  
// 4. heap_allocated -        
//           
// 5. args -   
// 6. locals -     
// ...
struct coroutine_frame
{
    void (*resume)(coroutine_frame *);
    promise_type promise;
    int16_t state;
    bool heap_allocated;
    // args
    // locals
    //...
};

// 1.     .  .
template<typename ReturnValue, typename ...Args>
ReturnValue Foo(Args&&... args)
{
    // 1.
    //   Promise
    using coroutine_traits = std::coroutine_traits<ReturnValue, Args...>;
    using promise_type = typename coroutine_traits::promise_type;

    // 2.
    //   . 
    //      
    //      Promise,     
    //  ,    ,
    //     .
    // 1.   promise_type   
    //    get_return_object_on_allocation_failure,
    //        new,   
    //          get_return_object_on_allocation_failure,
    //        .
    // 2.      new.
    coroutine_frame* frame = nullptr;
    if constexpr (has_static_get_return_object_on_allocation_failure_v<promise_type>)
    {
        frame = reinterpret_cast<coroutine_frame*>(
            operator new(__builtin_coro_size(), std::nothrow));
        if(!frame)
            return promise_type::get_return_object_on_allocation_failure();
    }
    else
    {
        frame = reinterpret_cast<coroutine_frame*>(operator new(__builtin_coro_size()));
    }

    // 3.
    //      .
    //     .
    //     (lvalue  rvalue)   .
    <move-args-to-frame>

    // 4.
    //    promise_type     
    new(&frame->promise) create_promise<promise_type>(<frame-lvalue-args>);

    // 5.
    //   Promise::get_return_object().
    //      
    //         .
    //         ,
    // ..      (.  co_await).
    auto return_object = frame->promise.get_return_object();

    // 6.
    //    -  
    //    
    //   GCC, ,    
    // ramp-fucntion (  )  
    // action-function ( -) 
    void couroutine_states(coroutine_frame*);
    couroutine_states(frame);

    // 7.
    //    , 
    //          ,
    //         
    // - couroutine_states,       .
    return return_object;
}

Promise new delete. , , new delete:

struct Promise
{
    void* operator new(std::size_t size, std::nothrow_t) noexcept
    {
        ...
    }

    void operator delete(void* ptr, std::size_t size)
    {
        ...
    }

    //        
    static auto get_return_object_on_allocation_failure() noexcept
    {
        //       
        return make_invalid_task();
    }
};

new c , . , , leading-allocator convention.

//  Promise    new c  
template<typename Allocator>
struct Promise : PromiseBase
{
    // std::allocator_arg_t -  tag-
    //       
    void* operator new(std::size_t size, std::allocator_arg_t, Allocator allocator) noexcept
    {
        ...
    }

    void operator delete(void* ptr, std::size_t size)
    {
        ...
    }
};

//     std::coroutine_traits
namespace std
{
    template<typename... Args>
    struct coroutine_traits<Task, Args...>
    {
        using promise_type = PromiseBase;
    };

    template<typename Allocator>
    struct coroutine_traits<Task, std::allocator_arg_t, Allocator>
    {
        using promise_type = Promise<Allocator>;
    };
}

//        
int main()
{
    MyAlloc alloc;
    coro(std::allocator_arg, alloc);
    ...
}

, new delete , .

. .

-, . , , , . , , , Undefined Behavior.

void Coroutine(const std::vector<int>& data)
{
    co_await 10s;
    for(const auto& value : data)
        std::cout << value << std::endl;
}

void Foo()
{
    // 1.        vector<int>;
    // 2.          data;
    // 3.      , ..  
    //    ,  ,     data 
    //          ;
    // 4.       ;
    // 5. ,       vector<int>, 
    //     ,   co_await    
    //      Foo   ;
    // 6.  10 ,        
    //       c , ,    data 
    //    ( ,    ),   .
    Coroutine({1, 2, 3});
    ...
}

Promise. , , , , Promise ( ) , , . , Promise - , , Promise, .

Promise get_return_object. , . : get_return_object . , , - , . onadic composition.

class Task
{
public:

    struct promise_type
    {
        auto get_return_object() noexcept
        {
            return Task{ std::coroutine_handle<promise_type>::from_promise(*this) };
        }
        ...
    };

    void resume()
    {
        if(coro_handle)
            coro_handle.resume();
    }

private:

    Task() = default;
    explicit Task(std::coroutine_handle<> handle)
        : coro_handle(handle)
    {}

    std::coroutine_handle<> coro_handle;
};

std::coroutine_handle — , : ( ) . from_promise, Promise.

couroutine_states -, couroutine_states , , get_return_object .

State Machine.

couroutine_states - co_awat/co_yield/co_return : , resume. .

void couroutine_states(coroutine_frame* frame)
{
    switch(frame->state)
    {
        case 0:
        ... goto resume_point_0;
        case N:
            goto resume_point_N;
        ...
    }

    co_await promise.initial_suspend();

    try
    {
        // function body
    }
    catch(...)
    {
        promise.unhandled_exception();
    }

final_suspend:
    co_await promise.final_suspend();
}

, co_await, resume_point — .

{
    ...
resume_point:
    return frame->awaitable.await_resume();
}

co_await — co_await, state, . — , , co_await .

initial_suspend co_await. : . Awaitable: std::suspend_never, std::suspend_always, initial_suspend, .

namespace std
{
    struct suspend_never
    {
        bool await_ready() noexcept { return true; }
        void await_suspend(coroutine_handle<>) noexcept {}
        void await_resume() noexcept {}
    };

    struct suspend_always
    {
        bool await_ready() noexcept { return false; }
        void await_suspend(coroutine_handle<>) noexcept {}
        void await_resume() noexcept {}
    };
}

//   ,      
//  
class Task
{
public:
    struct promise_type
    {
        ...
        auto init_suspend() const noexcept
        {
            return std::suspend_never{};
        }
    }
    ...
};

//    ,   
//     
//      ,
//         resume.
class TaskManual
{
public:
    struct promise_type
    {
        ...
        auto init_suspend() const noexcept
        {
            return std::suspend_always{};
        }
    }
    ...
};

. , try-catch unhandled_exception .

, co_await, co_yield co_return. . Promise, .

co_yield <expr> :

co_await frame->promise.yield_value(<expr>);

.. Promise . yield_value :

template<typename Type>
class Task
{
public:
    struct promise_type
    {
        ...
        // C   ,
        //    , 
        //     co_await   std::suspend_always.
        auto yield_value(Type value)
        {
            current_value = std::move(value);
            return std::suspend_always{};
        }
    };
    ...
};

Task Promise . co_yield — . cppcoro

co_return return. .

• co_rturn :

  
  
  

  // co_return;
  frame->promise.return_void();
  goto final_suspend;

  
  
  

• , , void, co_rturn

  
  
  

  // co_return <expr>;
  frame->promise.return_value(<expr>);
  goto final_suspend;

  
  
  

• void,

  
  
  

  // co_return <expr>;
  <expr>;
  frame->promise.return_void();
  goto final_suspend;

  
  
  

, co_return, co_return;. .. frame->promise.return_void() .

Promise return_value return_void, final_suspend.

initial_suspend, final_suspend . , .

//   ,        
//      .  Promise   ,
//   ,       
//   delete,      .
//       Undefined Behavior.
//   ,       .
class Task
{
public:
    struct promise_type
    {
        ...
        auto final_suspend() const noexcept
        {
            //     
            return std::suspend_never{};
        }
    };
    ...
};

//    ,       
//         .
//          Undefined Behavior.
//      
//    coroutine_handle::destroy()
//   ,       , 
//          Promise.
class TaskManual
{
public:
    struct promise_type
    {
        ...
        auto final_suspend() const noexcept
        {
            //    
            return std::suspend_always{};
        }
    }
    ...
};

co_await . init_suspend final_suspend, co_yield, . . Promise await_transform, co_await

// co_await <expr>
co_await frame->promise.await_transform(<expr>);

, , co_await , Awaitable, . co_await .

class Task
{
public:
    struct promise_type
    {
        ...
        template<typename Type>
        auto await_transform(Type&& Whatever) const noexcept
        {
            static_assert(false,
                "co_await is not supported in coroutines of type Generator");
            return std::suspend_never{};
        }
    };
    ...
};

:

• cppcoro. Coroutine TS;
• folly. ;

:

• Coroutines TS Simplifications;
• Revisiting allocator model for coroutine;

:

• Working Draft, Standard for Programming Language C++ (N4830);
• Coroutine TS (N4760);
• First-class symmetric coroutines in C++;
• Core Coroutines;
• Low-level API for stackful coroutines;
• A low-level API for stackful context switching;
• Coroutines: Use-cases and Trade-offs;
• Revisiting Coroutines;
• Stackful Coroutines and Stackless Resumable Functions ;
• Resumable Functions ;
• Resumable Expressions ;
• Coroutines in LLVM ;
• Boost Coroutine2 ;

I would be glad to receive comments and suggestions (you can email yegorov.alex@gmail.com)

Thank you!