...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
call/cc (call with current continuation) is a universal control operator (well-known from the programming language Scheme) that captures the current continuation as a first-class object and pass it as an argument to another continuation.
A continuation (abstract concept of functional programming languages) represents the state of the cotnrol flow of a program at a given point in time. Continuations can be suspended and resumed later in order to change the control flow of a program.
Modern mico-processors are registers machines; the content of processor registers represent a continuation of the executed program at a given point in time. Operating systems simulate parallel execution of programs on a single processor by switching between programs (context switch) by preserving and restoring the continuation, e.g. the content of all registers.
callcc() is the C++ equivalent to Scheme's call/cc operator. It captures the current continuation (the rest of the computation; code after callcc()) and trickers a context switch. The context switch is achived by preserving certain registers (including instruction and stack pointer), defined by the calling convention of the ABI, of the current continuation and restoring those registers of the resumed continuation. The control flow of the resumed continuation continues. The current continuation is suspended and passed as argument to the resumed continuation.
callcc() expects a context-function
with signature 'continuation(continuation &&
c, Arg ...arg)'
. The parameter c
represents the current continuation from which this continuation was resumed
(e.g. that has called callcc())
and arg
are the data passed
to callcc().
On return the context-function of the current continuation has to specify an continuation to which the execution control is transferred after termination of the current continuation.
If an instance with valid state goes out of scope and the context-function has not yet returned, the stack is traversed in order to access the control structure (address stored at the first stack frame) and continuation's stack is deallocated via the StackAllocator.
Important | |
---|---|
Segmented stacks are not supported by call/cc. |
continuation represents a contiunation; it contains the content of preserved registers and manages the associated stack (allocation/deallocation). continuation s a one-shot continuation - it can be used only once, after applied to callcc() it is invalidated.
continuation is only move-constructible and move-assignable.
As a first-class object continuation can be applied to and returned from a function, assigned to a variable or stored in a container.
A contiunation is continued by calling resume()
/resume_with()
.
namespace ctx=boost::context; ctx::continuation source=ctx::callcc( [](ctx::continuation && sink){ int a=0; int b=1; for(;;){ sink=sink.resume(a); auto next=a+b; a=b; b=next; } return std::move(sink); }); for (int j=0;j<10;++j) { std::cout << source.get_data<int>() << " "; source=source.resume(); } output: 0 1 1 2 3 5 8 13 21 34 55
This simple example demonstrates the basic usage of call/cc
as a generator. The continuation sink
represents the main-continuation (function main()
).
sink
is captured (current-contiunation)
and passed as parameter to the lambda.
Because the state is invalidated (one-shot continuation) by each call of callcc(), the new state of the continuation, returned by callcc(),
needs to be assigned to sink
after each call.
The lambda that calculates the Fibonacci numbers is executed inside the continuation
represented by source
. Calculated
Fibonacci numbers are transferred between the two continuations' as argument
of callcc() (and returned by
source.get_data<int>()
).
Note that this example represents a generator thus no
value is transferred into the lambda via callcc().
The locale variables a
, b
and next
remain their values during each context switch. This is possible due source
has its own stack and the stack is
exchanged by each context switch.
Calling callcc() without arguments means, that no data will be transferred, only the context switch is executed.
The arguments passed to callcc(),
in one continuation, are accessible via c.get_data<>()
in the other continuation.
namespace ctx=boost::context; int i=1; ctx::continuation c1=callcc([](ctx::continuation && c2){ int j=c2.get_data<int>(); std::printf("inside c1,j==%d\n",j); return c2.resume(j+1); }, i); i=c1.get_data<int>(); std::printf("i==%d\n",i); output: inside c1,j==1 i==2
callcc(<lambda>,i)
enters
the lambda in continuation represented by c1
with argument i=1
. The expression c2.resume(j+1)
resumes the continuation c2
and transfers back an integer of j+1
. On return
of callcc(<lambda>, i)
, the variable
i
gets the value of j+1
assigned (i=c1.get_data<int>()
).
More than one argument can be transferred too.
namespace ctx=boost::context; int i=2,j=1; ctx::continuation c1=callcc([](ctx::continuation && c2){ int i, j; std::tie(i,j)=c2.get_data<int,int>(); std::printf("inside c1,i==%d,j==%d\n",i,j); return c2.resume(i+j,i-j); }, i, j); std::tie(i,j)=c1.get_data<int,int>(); std::printf("i==%d,j==%d\n",i,j); output: inside c1,i==2,j==1 i==3,j==1
For use-cases, that require to transfer data of different type:
namespace ctx=boost::context; ctx::continuation f1(ctx::continuation && c) { int i=3; c=c.resume(i); std::string s{ "abc" }; c=c.resume(s); i=7;s="xyz"; c=c.resume(i,s); c=c.resume(); return std::move(c); } ctx::continuation c=ctx::callcc(f1); int i=c.get_data<int>(); std::cout << "f1: returned : " << i << std::endl; c=c.resume(); std::string s=c.get_data<std::string>(); std::cout << "f1: returned : " << s << std::endl; c=c.resume(); std::tie(i,s)=c.get_data< int, std::string >(); std::cout << "f1: returned : " << i << ", " << s << std::endl; c=c.resume(); std::cout << std::boolalpha; std::cout << "f1: returned data : " << ctx::data_available( c) << std::endl; output: f1: returned : 3 f1: returned : abc f1: returned : 7, xyz f1: returned data : false
If the function executed inside a context-function emits
ans exception, the application is terminated by calling std::terminate()
. std::exception_ptr
can be used to transfer exceptions between different continuations.
Important | |
---|---|
Do not jump from inside a catch block and then re-throw the exception in another continuation. |
Sometimes it is useful to execute a new function on top of a resumed continuation.
For this purpose callcc() with
second argument exec_ontop_arg
has to be used. The function passed as argument must accept a rvalue reference
to continuation and return,
depending on functions argument list, a tuple of its argument types, a single
return type or void.
namespace ctx=boost::context; ctx::continuation f1(ctx::continuation && c) { int data=c.get_data<int>(); std::cout << "f1: entered first time: " << data << std::endl; c=c.resume(data+1); data=c.get_data<int>(); std::cout << "f1: entered second time: " << data << std::endl; c=c.resume(data+1); data=c.get_data<int>(); std::cout << "f1: entered third time: " << data << std::endl; return std::move(c); }; int f2(ctx::continuation && c){ int data=c.get_data<int>(c); std::cout << "f2: entered: " << data << std::endl; return data; }; int data = 0; ctx::continuation c=ctx::callcc(f1,data+1); data=c.get_data<int>(); std::cout << "f1: returned first time: " << data << std::endl; c=c.resume(data+1); data=c.get_data<int>(); std::cout << "f1: returned second time: " << data << std::endl; c=c.resume_with(f2,-1); std::cout << "f1: returned third time" << std::endl; output: f1: entered first time: 1 f1: returned first time: 2 f1: entered second time: 3 f1: returned second time: 4 f2: entered: -1 f1: entered third time: -1 f1: returned third time
The expression c.resume_with(f2,-1)
executes f2()
on top of contiunation c
,
e.g. an additional stack frame is allocated on top of the stack (in front of
f1()
).
f2()
returns argument -1
that will returned by the second invocation of c.resume(data+1)
in f1()
.
Another option is to execute a function on top of the continuation that throws an exception.
namespace ctx=boost::context; struct my_exception : public std::runtime_error { ctx::continuation c; my_exception(ctx::continuation && c_,std::string const& what) : std::runtime_error{ what }, c{ std::move( c_) } { } }; ctx::continuation c=ctx::callcc([](ctx::continuation && c) { for (;;) { try { std::cout << "entered" << std::endl; c=c.resume(); } catch (my_exception & ex) { std::cerr << "my_exception: " << ex.what() << std::endl; return std::move(ex.c); } } return std::move(c); }); c = c.resume_with( [](ctx::continuation && c){ throw my_exception(std::move(c),"abc"); }); output: entered my_exception: abc
In this exception my_exception
is throw from a function invoked ontop of continuation c
and catched inside the for
-loop.
On construction of continuation
a stack is allocated. If the context-function returns
the stack will be destructed. If the context-function
has not yet returned and the destructor of an valid continuation
instance (e.g. continuation::operator bool() returns
true
) is called, the stack will
be destructed too.
Important | |
---|---|
Code executed by context-function must not prevent the propagation of the detail::forced_unwind exception. Absorbing that exception will cause stack unwinding to fail. Thus, any code that catches all exceptions must re-throw any pending detail::forced_unwind exception. |
Allocating control structures on top of the stack requires to allocated the stack_context and create the control structure with placement new before continuation is created.
Note | |
---|---|
The user is responsible for destructing the control structure at the top of the stack. |
namespace ctx=boost::context; // stack-allocator used for (de-)allocating stack fixedsize_stack salloc(4048); // allocate stack space stack_context sctx(salloc.allocate()); // reserve space for control structure on top of the stack void * sp=static_cast<char*>(sctx.sp)-sizeof(my_control_structure); std::size_t size=sctx.size-sizeof(my_control_structure); // placement new creates control structure on reserved space my_control_structure * cs=new(sp)my_control_structure(sp,size,sctx,salloc); ... // destructing the control structure cs->~my_control_structure(); ... struct my_control_structure { // captured continuation ctx::continuation c; template< typename StackAllocator > my_control_structure(void * sp,std::size_t size,stack_context sctx,StackAllocator salloc) : // create captured continuation c{} { c=ctx::callcc(std::allocator_arg,preallocated(sp,size,sctx),salloc,entry_func); } ... };
namespace ctx=boost::context; /* * grammar: * P ---> E '\0' * E ---> T {('+'|'-') T} * T ---> S {('*'|'/') S} * S ---> digit | '(' E ')' */ class Parser{ char next; std::istream& is; std::function<void(char)> cb; char pull(){ return std::char_traits<char>::to_char_type(is.get()); } void scan(){ do{ next=pull(); } while(isspace(next)); } public: Parser(std::istream& is_,std::function<void(char)> cb_) : next(), is(is_), cb(cb_) {} void run() { scan(); E(); } private: void E(){ T(); while (next=='+'||next=='-'){ cb(next); scan(); T(); } } void T(){ S(); while (next=='*'||next=='/'){ cb(next); scan(); S(); } } void S(){ if (isdigit(next)){ cb(next); scan(); } else if(next=='('){ cb(next); scan(); E(); if (next==')'){ cb(next); scan(); }else{ throw std::runtime_error("parsing failed"); } } else{ throw std::runtime_error("parsing failed"); } } }; std::istringstream is("1+1"); // execute parser in new continuation ctx::continuation source; // user-code pulls parsed data from parser // invert control flow source=ctx::callcc( [&is](ctx::continuation && sink){ // create parser with callback function Parser p(is, [&sink](char c){ // resume main continuation sink=sink.resume(c); }); // start recursive parsing p.run(); // resume main continuation return std::move(sink); }); while(ctx::data_available(source)){ char c=source.get_data<char>(); printf("Parsed: %c\n",c); source=source.resume(); } output: Parsed: 1 Parsed: + Parsed: 1
In this example a recursive descent parser uses a callback to emit a newly passed symbol. Using call/cc the control flow can be inverted, e.g. the user-code pulls parsed symbols from the parser - instead to get pushed from the parser (via callback).
The data (character) is transferred between the two continuations.
continuation
#include <boost/context/continuation.hpp> class continuation { public: continuation() noexcept = default; ~continuation(); continuation(continuation && other) noexcept; continuation & operator=(continuation && other) noexcept; continuation(continuation const& other) noexcept = delete; continuation & operator=(continuation const& other) noexcept = delete; template<typename ...Arg> continuation resume(Arg ...arg); template<typename Fn,typename ...Arg> continuation resume_with(Fn && fn,Arg ...arg); bool data_available() noexcept; template<typename ...Arg> <unspecified> get_data(); explicit operator bool() const noexcept; bool operator!() const noexcept; bool operator==(continuation const& other) const noexcept; bool operator!=(continuation const& other) const noexcept; bool operator<(continuation const& other) const noexcept; bool operator>(continuation const& other) const noexcept; bool operator<=(continuation const& other) const noexcept; bool operator>=(continuation const& other) const noexcept; template<typename charT,class traitsT> friend std::basic_ostream<charT,traitsT> & operator<<(std::basic_ostream<charT,traitsT> & os,continuation const& other) { void swap(continuation & other) noexcept; };
continuation() noexcept;
Creates a invalid continuation.
Nothing.
~continuation();
Destructs the associated stack if *this
is a valid continuation, e.g. continuation::operator
bool() returns true
.
Nothing.
continuation(continuation && other) noexcept;
Moves underlying capture continuation to *this
.
Nothing.
continuation & operator=(continuation && other) noexcept;
Moves the state of other
to *this
using move semantics.
Nothing.
operator()
()
template<typename ...Arg> continuation resume(Arg ...arg); template<typename Fn,typename ...Arg> continuation resume_with(Fn && fn,Arg ...arg);
Captures current continuation and resumes *this
. The function with argument type
exec_ontop_arg
, is used
to execute function fn
in continuation *this
(e.g. the stack frame of fn
is allocated on stack of *this
).
The continuation representing the continuation that has been suspended.
The returned arguments from fn
are passed as arguments to the context-function of resumed continuation.
Function fn
needs to
return a tuple of arguments (see description).
The returned continuation indicates if the suspended continuation has
terminated (return from context-function) via bool
operator()
.
If the returned continuation has terminated no data are transferred.
data_available
()
bool data_available() noexcept;
Tests if c
has data.
true
if data have been transferred,
otherwise false
.
Nothing.
get_available
()
template<typename ...Arg> <unspecified> get_data();
Data that have been transferred via callcc()
or operator()
are returned as std::tuple<Arg...>
or Arg
if single parameter.
operator bool
()
explicit operator bool() const noexcept;
true
if *this
points to a captured continuation.
Nothing.
operator!
()
bool operator!() const noexcept;
true
if *this
does not point to a captured continuation.
Nothing.
operator==
()
bool operator==(continuation const& other) const noexcept;
true
if *this
and other
represent the same continuation, false
otherwise.
Nothing.
operator!=
()
bool operator!=(continuation const& other) const noexcept;
! (other == * this)
Nothing.
operator<
()
bool operator<(continuation const& other) const noexcept;
true
if *this != other
is true and the implementation-defined
total order of continuation
values places *this
before other
, false otherwise.
Nothing.
operator>
()
bool operator>(continuation const& other) const noexcept;
other <
* this
Nothing.
operator<=
()
bool operator<=(continuation const& other) const noexcept;
! (other <
* this)
Nothing.
operator>=
()
bool operator>=(continuation const& other) const noexcept;
! (*
this <
other)
Nothing.
operator<<()
template<typename charT,class traitsT> std::basic_ostream<charT,traitsT> & operator<<(std::basic_ostream<charT,traitsT> & os,continuation const& other);
Writes the representation of other
to stream os
.
os
#include <boost/context/continuation.hpp> template<typename Fn,typename ...Arg> continuation callcc(Fn && fn,Arg ...arg); template<typename StackAlloc,typename Fn,typename ...Arg> continuation callcc(std::allocator_arg_t,StackAlloc salloc,Fn && fn,Arg ...arg); template<typename StackAlloc,typename Fn,typename ...Arg> continuation callcc(std::allocator_arg_t,preallocated palloc,StackAlloc salloc,Fn && fn,Arg ...arg);
Captures current continuation and creates a new continuation prepared
to execute fn
. fixedsize_stack
is used as default
stack allocator (stack size == fixedsize_stack::traits::default_size()).
The function with argument type preallocated
,
is used to create a user defined data (for
instance additional control structures) on top of the stack. The
arguments, ... arg
,
are passed to the current continuation to be transferred by the call
to callcc()
in the same thread.
The continuation representing the contexcontinuation that has been suspended.
The returned continuation indicates if the suspended continuation has
terminated (return from context-function) via bool
operator()
.
If the returned continuation has terminated no data are transferred.