#ifndef __PROCESS_FUTURE_HPP__ #define __PROCESS_FUTURE_HPP__ #include #include // For abort. #include #include #include #include #include #include #include // TODO(benh): Replace shared_ptr with unique_ptr. #include #include #include #include #include namespace process { // Forward declaration (instead of include to break circular dependency). template struct _Defer; namespace internal { template struct wrap; template struct unwrap; } // namespace internal { // Forward declaration of Promise. template class Promise; // Definition of a "shared" future. A future can hold any // copy-constructible value. A future is considered "shared" because // by default a future can be accessed concurrently. template class Future { public: // Constructs a failed future. static Future failed(const std::string& message); Future(); Future(const T& _t); Future(const Future& that); ~Future(); // Futures are assignable (and copyable). This results in the // reference to the previous future data being decremented and a // reference to 'that' being incremented. Future& operator = (const Future& that); // Comparision operators useful for using futures in collections. bool operator == (const Future& that) const; bool operator < (const Future& that) const; // Helpers to get the current state of this future. bool isPending() const; bool isReady() const; bool isDiscarded() const; bool isFailed() const; // Discards this future. This is similar to cancelling a future, // however it also occurs when the last reference to this future // gets cleaned up. Returns false if the future could not be // discarded (for example, because it is ready or failed). bool discard(); // Waits for this future to become ready, discarded, or failed. bool await(const Duration& duration = Seconds(-1.0)) const; // Return the value associated with this future, waits indefinitely // until a value gets associated or until the future is discarded. T get() const; // Returns the failure message associated with this future. std::string failure() const; // Type of the callback functions that can get invoked when the // future gets set, fails, or is discarded. typedef std::tr1::function ReadyCallback; typedef std::tr1::function FailedCallback; typedef std::tr1::function DiscardedCallback; typedef std::tr1::function&)> AnyCallback; // Installs callbacks for the specified events and returns a const // reference to 'this' in order to easily support chaining. const Future& onReady(const ReadyCallback& callback) const; const Future& onFailed(const FailedCallback& callback) const; const Future& onDiscarded(const DiscardedCallback& callback) const; const Future& onAny(const AnyCallback& callback) const; // Installs callbacks that get executed when this future is ready // and associates the result of the callback with the future that is // returned to the caller (which may be of a different type). template Future then(const std::tr1::function(const T&)>& f) const; template Future then(const std::tr1::function& f) const; // Helpers for the compiler to be able to forward std::tr1::bind results. template Future then(const std::tr1::_Bind& b) const { return then(std::tr1::function(b)); } #define TEMPLATE(Z, N, DATA) \ template \ Future then( \ const std::tr1::_Bind& b) const \ { \ return then(std::tr1::function(b)); \ } REPEAT_FROM_TO(1, 11, TEMPLATE, _) // Args A0 -> A9. #undef TEMPLATE template Future then(const std::tr1::_Bind(*(void))(void)>& b) const { return then(std::tr1::function(const T&)>(b)); } #define TEMPLATE(Z, N, DATA) \ template \ Future then( \ const std::tr1::_Bind(*(ENUM_PARAMS(N, A))) \ (ENUM_PARAMS(N, P))>& b) const \ { \ return then(std::tr1::function(const T&)>(b)); \ } REPEAT_FROM_TO(1, 11, TEMPLATE, _) // Args A0 -> A9. #undef TEMPLATE // Helpers for the compiler to be able to forward 'defer' results. template Future then(const _Defer(*(PID, X(U::*)(void))) (const PID&, X(U::*)(void))>& d) const { return then(std::tr1::function(const T&)>(d)); } #define TEMPLATE(Z, N, DATA) \ template \ Future then( \ const _Defer(*(PID, \ X(U::*)(ENUM_PARAMS(N, P)), \ ENUM_PARAMS(N, A))) \ (const PID&, \ X(U::*)(ENUM_PARAMS(N, P)), \ ENUM_PARAMS(N, P))>& d) const \ { \ return then(std::tr1::function(const T&)>(d)); \ } REPEAT_FROM_TO(1, 11, TEMPLATE, _) // Args A0 -> A9. #undef TEMPLATE template Future then(const _Defer(*(PID, Future(U::*)(void))) (const PID&, Future(U::*)(void))>& d) const { return then(std::tr1::function(const T&)>(d)); } #define TEMPLATE(Z, N, DATA) \ template \ Future then( \ const _Defer(*(PID, \ Future(U::*)(ENUM_PARAMS(N, P)), \ ENUM_PARAMS(N, A))) \ (const PID&, \ Future(U::*)(ENUM_PARAMS(N, P)), \ ENUM_PARAMS(N, P))>& d) const \ { \ return then(std::tr1::function(const T&)>(d)); \ } REPEAT_FROM_TO(1, 11, TEMPLATE, _) // Args A0 -> A9. #undef TEMPLATE // C++11 implementation (covers all functors). #if __cplusplus >= 201103L template auto then(F f) const -> typename internal::wrap::Type; #endif private: friend class Promise; // Sets the value for this future, unless the future is already set, // failed, or discarded, in which case it returns false. bool set(const T& _t); // Sets this future as failed, unless the future is already set, // failed, or discarded, in which case it returns false. bool fail(const std::string& _message); void copy(const Future& that); void cleanup(); enum State { PENDING, READY, FAILED, DISCARDED, }; int* refs; int* lock; State* state; T** t; std::string** message; // Message associated with failure. std::queue* onReadyCallbacks; std::queue* onFailedCallbacks; std::queue* onDiscardedCallbacks; std::queue* onAnyCallbacks; Latch* latch; }; // TODO(benh): Make Promise a subclass of Future? template class Promise { public: Promise(); Promise(const T& t); ~Promise(); bool set(const T& _t); bool set(const Future& future); // Alias for associate. bool associate(const Future& future); bool fail(const std::string& message); // Returns a copy of the future associated with this promise. Future future() const; private: // Not copyable, not assignable. Promise(const Promise&); Promise& operator = (const Promise&); Future f; }; template <> class Promise; template class Promise; template Promise::Promise() {} template Promise::Promise(const T& t) : f(t) {} template Promise::~Promise() {} template bool Promise::set(const T& t) { return f.set(t); } template bool Promise::set(const Future& future) { return associate(future); } template bool Promise::associate(const Future& future) { if (!f.isPending()) { return false; } future .onReady(std::tr1::bind(&Future::set, f, std::tr1::placeholders::_1)) .onFailed(std::tr1::bind(&Future::fail, f, std::tr1::placeholders::_1)) .onDiscarded(std::tr1::bind(&Future::discard, f)); return true; } template bool Promise::fail(const std::string& message) { return f.fail(message); } template Future Promise::future() const { return f; } // Internal helper utilities. namespace internal { template struct wrap { typedef Future Type; }; template struct wrap > { typedef Future Type; }; template struct unwrap { typedef T Type; }; template struct unwrap > { typedef X Type; }; inline void acquire(int* lock) { while (!__sync_bool_compare_and_swap(lock, 0, 1)) { asm volatile ("pause"); } } inline void release(int* lock) { // Unlock via a compare-and-swap so we get a memory barrier too. bool unlocked = __sync_bool_compare_and_swap(lock, 1, 0); assert(unlocked); } template void select( const Future& future, std::tr1::shared_ptr > > promise) { // We never fail the future associated with our promise. assert(!promise->future().isFailed()); if (promise->future().isPending()) { // No-op if it's discarded. if (future.isReady()) { // We only set the promise if a future is ready. promise->set(future); } } } } // namespace internal { // TODO(benh): Move select and discard into 'futures' namespace. // Returns a future that captures any ready future in a set. Note that // select DOES NOT capture a future that has failed or been discarded. template Future > select(const std::set >& futures) { std::tr1::shared_ptr > > promise( new Promise >()); Future > future = promise->future(); std::tr1::function&)> select = std::tr1::bind(&internal::select, std::tr1::placeholders::_1, promise); typename std::set >::iterator iterator; for (iterator = futures.begin(); iterator != futures.end(); ++iterator) { (*iterator).onAny(std::tr1::bind(select, std::tr1::placeholders::_1)); } return future; } template void discard(const std::set >& futures) { typename std::set >::const_iterator iterator; for (iterator = futures.begin(); iterator != futures.end(); ++iterator) { Future future = *iterator; // Need a non-const copy to discard. future.discard(); } } template void discard(const std::list >& futures) { typename std::list >::const_iterator iterator; for (iterator = futures.begin(); iterator != futures.end(); ++iterator) { Future future = *iterator; // Need a non-const copy to discard. future.discard(); } } template Future Future::failed(const std::string& message) { Future future; future.fail(message); return future; } template Future::Future() : refs(new int(1)), lock(new int(0)), state(new State(PENDING)), t(new T*(NULL)), message(new std::string*(NULL)), onReadyCallbacks(new std::queue()), onFailedCallbacks(new std::queue()), onDiscardedCallbacks(new std::queue()), onAnyCallbacks(new std::queue()), latch(new Latch()) {} template Future::Future(const T& _t) : refs(new int(1)), lock(new int(0)), state(new State(PENDING)), t(new T*(NULL)), message(new std::string*(NULL)), onReadyCallbacks(new std::queue()), onFailedCallbacks(new std::queue()), onDiscardedCallbacks(new std::queue()), onAnyCallbacks(new std::queue()), latch(new Latch()) { set(_t); } template Future::Future(const Future& that) { copy(that); } template Future::~Future() { cleanup(); } template Future& Future::operator = (const Future& that) { if (this != &that) { cleanup(); copy(that); } return *this; } template bool Future::operator == (const Future& that) const { assert(latch != NULL); assert(that.latch != NULL); return *latch == *that.latch; } template bool Future::operator < (const Future& that) const { assert(latch != NULL); assert(that.latch != NULL); return *latch < *that.latch; } template bool Future::discard() { bool result = false; assert(lock != NULL); internal::acquire(lock); { assert(state != NULL); if (*state == PENDING) { *state = DISCARDED; latch->trigger(); result = true; } } internal::release(lock); // Invoke all callbacks associated with this future being // DISCARDED. We don't need a lock because the state is now in // DISCARDED so there should not be any concurrent modifications. if (result) { while (!onDiscardedCallbacks->empty()) { // TODO(*): Invoke callbacks in another execution context. onDiscardedCallbacks->front()(); onDiscardedCallbacks->pop(); } while (!onAnyCallbacks->empty()) { // TODO(*): Invoke callbacks in another execution context. onAnyCallbacks->front()(*this); onAnyCallbacks->pop(); } } return result; } template bool Future::isPending() const { assert(state != NULL); return *state == PENDING; } template bool Future::isReady() const { assert(state != NULL); return *state == READY; } template bool Future::isDiscarded() const { assert(state != NULL); return *state == DISCARDED; } template bool Future::isFailed() const { assert(state != NULL); return *state == FAILED; } template bool Future::await(const Duration& duration) const { if (!isReady() && !isDiscarded() && !isFailed()) { assert(latch != NULL); return latch->await(duration); } return true; } template T Future::get() const { if (!isReady()) { await(); } CHECK(!isPending()) << "Future was in PENDING after await()"; if (!isReady()) { if (isFailed()) { std::cerr << "Future::get() but state == FAILED: " << failure() << std::endl; } else if (isDiscarded()) { std::cerr << "Future::get() but state == DISCARDED" << std::endl; } abort(); } assert(t != NULL); assert(*t != NULL); return **t; } template std::string Future::failure() const { assert(message != NULL); if (*message != NULL) { return **message; } return ""; } template const Future& Future::onReady(const ReadyCallback& callback) const { bool run = false; assert(lock != NULL); internal::acquire(lock); { assert(state != NULL); if (*state == READY) { run = true; } else if (*state == PENDING) { onReadyCallbacks->push(callback); } } internal::release(lock); // TODO(*): Invoke callback in another execution context. if (run) { callback(**t); } return *this; } template const Future& Future::onFailed(const FailedCallback& callback) const { bool run = false; assert(lock != NULL); internal::acquire(lock); { assert(state != NULL); if (*state == FAILED) { run = true; } else if (*state == PENDING) { onFailedCallbacks->push(callback); } } internal::release(lock); // TODO(*): Invoke callback in another execution context. if (run) { callback(**message); } return *this; } template const Future& Future::onDiscarded( const DiscardedCallback& callback) const { bool run = false; assert(lock != NULL); internal::acquire(lock); { assert(state != NULL); if (*state == DISCARDED) { run = true; } else if (*state == PENDING) { onDiscardedCallbacks->push(callback); } } internal::release(lock); // TODO(*): Invoke callback in another execution context. if (run) { callback(); } return *this; } template const Future& Future::onAny(const AnyCallback& callback) const { bool run = false; assert(lock != NULL); internal::acquire(lock); { assert(state != NULL); if (*state != PENDING) { run = true; } else if (*state == PENDING) { onAnyCallbacks->push(callback); } } internal::release(lock); // TODO(*): Invoke callback in another execution context. if (run) { callback(*this); } return *this; } namespace internal { template void thenf(const std::tr1::shared_ptr >& promise, const std::tr1::function(const T&)>& f, const Future& future) { if (future.isReady()) { promise->associate(f(future.get())); } else if (future.isFailed()) { promise->fail(future.failure()); } else if (future.isDiscarded()) { promise->future().discard(); } } template void then(const std::tr1::shared_ptr >& promise, const std::tr1::function& f, const Future& future) { if (future.isReady()) { promise->set(f(future.get())); } else if (future.isFailed()) { promise->fail(future.failure()); } else if (future.isDiscarded()) { promise->future().discard(); } } } // namespace internal { template template Future Future::then(const std::tr1::function(const T&)>& f) const { std::tr1::shared_ptr > promise(new Promise()); std::tr1::function&)> thenf = std::tr1::bind(&internal::thenf, promise, f, std::tr1::placeholders::_1); onAny(thenf); // Propagate discarding up the chain (note that we bind with a copy // of this future since 'this' might no longer be valid but other // references might still exist. // TODO(benh): Need to pass 'future' as a weak_ptr so that we can // avoid reference counting cycles! std::tr1::function discard = std::tr1::bind(&Future::discard, *this); promise->future().onDiscarded(discard); return promise->future(); } template template Future Future::then(const std::tr1::function& f) const { std::tr1::shared_ptr > promise(new Promise()); std::tr1::function&)> then = std::tr1::bind(&internal::then, promise, f, std::tr1::placeholders::_1); onAny(then); // Propagate discarding up the chain (note that we bind with a copy // of this future since 'this' might no longer be valid but other // references might still exist. // TODO(benh): Need to pass 'future' as a weak_ptr so that we can // avoid reference counting cycles! std::tr1::function discard = std::tr1::bind(&Future::discard, *this); promise->future().onDiscarded(discard); return promise->future(); } #if __cplusplus >= 201103L template template auto Future::then(F f) const -> typename internal::wrap::Type { typedef typename internal::unwrap::Type X; std::tr1::shared_ptr> promise(new Promise()); onAny([=] (const Future& future) { if (future.isReady()) { promise->set(f(future.get())); } else if (future.isFailed()) { promise->fail(future.failure()); } else if (future.isDiscarded()) { promise->future().discard(); } }); // TODO(benh): Need to use weak_ptr here so that we can avoid // reference counting cycles! Future future(*this); promise->future().onDiscarded([=] () { future.discard(); // Need a non-const copy to discard. }); return promise->future(); } #endif template bool Future::set(const T& _t) { bool result = false; assert(lock != NULL); internal::acquire(lock); { assert(state != NULL); if (*state == PENDING) { *t = new T(_t); *state = READY; latch->trigger(); result = true; } } internal::release(lock); // Invoke all callbacks associated with this future being READY. We // don't need a lock because the state is now in READY so there // should not be any concurrent modications. if (result) { while (!onReadyCallbacks->empty()) { // TODO(*): Invoke callbacks in another execution context. onReadyCallbacks->front()(**t); onReadyCallbacks->pop(); } while (!onAnyCallbacks->empty()) { // TODO(*): Invoke callbacks in another execution context. onAnyCallbacks->front()(*this); onAnyCallbacks->pop(); } } return result; } template bool Future::fail(const std::string& _message) { bool result = false; assert(lock != NULL); internal::acquire(lock); { assert(state != NULL); if (*state == PENDING) { *message = new std::string(_message); *state = FAILED; latch->trigger(); result = true; } } internal::release(lock); // Invoke all callbacks associated with this future being FAILED. We // don't need a lock because the state is now in FAILED so there // should not be any concurrent modications. if (result) { while (!onFailedCallbacks->empty()) { // TODO(*): Invoke callbacks in another execution context. onFailedCallbacks->front()(**message); onFailedCallbacks->pop(); } while (!onAnyCallbacks->empty()) { // TODO(*): Invoke callbacks in another execution context. onAnyCallbacks->front()(*this); onAnyCallbacks->pop(); } } return result; } template void Future::copy(const Future& that) { assert(that.refs > 0); __sync_fetch_and_add(that.refs, 1); refs = that.refs; lock = that.lock; state = that.state; t = that.t; message = that.message; onReadyCallbacks = that.onReadyCallbacks; onFailedCallbacks = that.onFailedCallbacks; onDiscardedCallbacks = that.onDiscardedCallbacks; onAnyCallbacks = that.onAnyCallbacks; latch = that.latch; } template void Future::cleanup() { assert(refs != NULL); if (__sync_sub_and_fetch(refs, 1) == 0) { // Discard the future if it is still pending (so we invoke any // discarded callbacks that have been setup). Note that we put the // reference count back at 1 here in case one of the callbacks // decides it wants to keep a reference. assert(state != NULL); if (*state == PENDING) { *refs = 1; discard(); __sync_sub_and_fetch(refs, 1); } // Now try and cleanup again (this time we know the future has // either been discarded or was not pending). Note that one of the // callbacks might have stored the future, in which case we'll // just return without doing anything, but the state will forever // be "discarded". assert(refs != NULL); if (*refs == 0) { delete refs; refs = NULL; assert(lock != NULL); delete lock; lock = NULL; assert(state != NULL); delete state; state = NULL; assert(t != NULL); delete *t; delete t; t = NULL; assert(message != NULL); delete *message; delete message; message = NULL; assert(onReadyCallbacks != NULL); delete onReadyCallbacks; onReadyCallbacks = NULL; assert(onFailedCallbacks != NULL); delete onFailedCallbacks; onFailedCallbacks = NULL; assert(onDiscardedCallbacks != NULL); delete onDiscardedCallbacks; onDiscardedCallbacks = NULL; assert(onAnyCallbacks != NULL); delete onAnyCallbacks; onAnyCallbacks = NULL; assert(latch != NULL); delete latch; latch = NULL; } } } } // namespace process { #endif // __PROCESS_FUTURE_HPP__