add stack-free impl

1 files changed, 186 insertions, 26 deletions

diff --git a/promise.hpp b/promise.hpp
index 853c285..7a18609 100644
--- a/promise.hpp
+++ b/promise.hpp
@@ -24,6 +24,7 @@
  * SOFTWARE.
  */
 
+#include <stack>
 #include <vector>
 #include <memory>
 #include <functional>
@@ -179,10 +180,20 @@ namespace promise {
 #define PROMISE_ERR_MISMATCH_TYPE do {throw std::runtime_error("mismatching promise value types");} while (0)
     
     class Promise {
+        template<typename PList> friend promise_t all(const PList &promise_list);
+        template<typename PList> friend promise_t race(const PList &promise_list);
         std::vector<callback_t> fulfilled_callbacks;
         std::vector<callback_t> rejected_callbacks;
+#ifndef CPPROMISE_USE_STACK
+        std::vector<Promise *> fulfilled_pms;
+        std::vector<Promise *> rejected_pms;
+#endif
         enum class State {
             Pending,
+#ifndef CPPROMISE_USE_STACK
+            PreFulfilled,
+            PreRejected,
+#endif
             Fulfilled,
             Rejected,
         } state;
@@ -202,9 +213,22 @@ namespace promise {
         static constexpr auto cps_transform(
                 Func f, const pm_any_t &result, const promise_t &npm) {
             return [&result, npm, f = std::forward<Func>(f)]() mutable {
+#ifdef CPPROMISE_USE_STACK
                 f(result)->then(
                     [npm] (pm_any_t result) {npm->resolve(result);},
                     [npm] (pm_any_t reason) {npm->reject(reason);});
+#else
+                promise_t rpm{f(result)};
+                rpm->then(
+                    [rpm, npm] (pm_any_t result) {
+                        npm->_resolve(result);
+                    },
+                    [rpm, npm] (pm_any_t reason) {
+                        npm->_reject(reason);
+                    });
+                rpm->_dep_resolve(npm);
+                rpm->_dep_reject(npm);
+#endif
             };
         }
 
@@ -213,9 +237,22 @@ namespace promise {
         static constexpr auto cps_transform(
                 Func f, const pm_any_t &, const promise_t &npm) {
             return [npm, f = std::forward<Func>(f)]() mutable {
+#ifdef CPPROMISE_USE_STACK
                 f()->then(
                     [npm] (pm_any_t result) {npm->resolve(result);},
                     [npm] (pm_any_t reason) {npm->reject(reason);});
+#else
+                promise_t rpm{f()};
+                rpm->then(
+                    [rpm, npm] (pm_any_t result) {
+                        npm->_resolve(result);
+                    },
+                    [rpm, npm] (pm_any_t reason) {
+                        npm->_reject(reason);
+                    });
+                rpm->_dep_resolve(npm);
+                rpm->_dep_reject(npm);
+#endif
             };
         }
 
@@ -239,7 +276,7 @@ namespace promise {
             return [this, npm,
                     on_fulfilled = std::forward<Func>(on_fulfilled)]() mutable {
                 on_fulfilled(result);
-                npm->resolve();
+                npm->_resolve();
             };
         }
 
@@ -249,7 +286,7 @@ namespace promise {
         constexpr auto gen_on_fulfilled(Func on_fulfilled, const promise_t &npm) {
             return [on_fulfilled = std::forward<Func>(on_fulfilled), npm]() mutable {
                 on_fulfilled();
-                npm->resolve();
+                npm->_resolve();
             };
         }
 
@@ -260,7 +297,7 @@ namespace promise {
             return [this, npm,
                     on_rejected = std::forward<Func>(on_rejected)]() mutable {
                 on_rejected(reason);
-                npm->reject();
+                npm->_reject();
             };
         }
 
@@ -271,7 +308,7 @@ namespace promise {
             return [npm,
                     on_rejected = std::forward<Func>(on_rejected)]() mutable {
                 on_rejected();
-                npm->reject();
+                npm->_reject();
             };
         }
 
@@ -281,7 +318,7 @@ namespace promise {
         constexpr auto gen_on_fulfilled(Func on_fulfilled, const promise_t &npm) {
             return [this, npm,
                     on_fulfilled = std::forward<Func>(on_fulfilled)]() mutable {
-                npm->resolve(on_fulfilled(result));
+                npm->_resolve(on_fulfilled(result));
             };
         }
 
@@ -290,7 +327,7 @@ namespace promise {
             typename function_traits<Func>::empty_arg * = nullptr>
         constexpr auto gen_on_fulfilled(Func on_fulfilled, const promise_t &npm) {
             return [npm, on_fulfilled = std::forward<Func>(on_fulfilled)]() mutable {
-                npm->resolve(on_fulfilled());
+                npm->_resolve(on_fulfilled());
             };
         }
 
@@ -299,7 +336,7 @@ namespace promise {
             typename function_traits<Func>::non_empty_arg * = nullptr>
         constexpr auto gen_on_rejected(Func on_rejected, const promise_t &npm) {
             return [this, npm, on_rejected = std::forward<Func>(on_rejected)]() mutable {
-                npm->reject(on_rejected(reason));
+                npm->_reject(on_rejected(reason));
             };
         }
 
@@ -308,11 +345,107 @@ namespace promise {
             typename function_traits<Func>::empty_arg * = nullptr>
         constexpr auto gen_on_rejected(Func on_rejected, const promise_t &npm) {
             return [npm, on_rejected = std::forward<Func>(on_rejected)]() mutable {
-                npm->reject(on_rejected());
+                npm->_reject(on_rejected());
+            };
+        }
+
+#ifndef CPPROMISE_USE_STACK
+        void _trigger() {
+            std::stack<std::tuple<
+                std::vector<Promise *>::const_iterator,
+                std::vector<Promise *> *,
+                Promise *>> s;
+            auto push_frame = [&s](Promise *pm) {
+                if (pm->state == State::PreFulfilled)
+                {
+                    pm->state = State::Fulfilled;
+                    for (auto &cb: pm->fulfilled_callbacks) cb();
+                    s.push(std::make_tuple(pm->fulfilled_pms.begin(),
+                                          &pm->fulfilled_pms,
+                                          pm));
+                }
+                else if (pm->state == State::PreRejected)
+                {
+                    pm->state = State::Rejected;
+                    for (auto &cb: pm->rejected_callbacks) cb();
+                    s.push(std::make_tuple(pm->rejected_pms.begin(),
+                                          &pm->rejected_pms,
+                                          pm));
+                }
             };
+            push_frame(this);
+            while (!s.empty())
+            {
+                auto &u = s.top();
+                auto &it = std::get<0>(u);
+                auto vec = std::get<1>(u);
+                auto pm = std::get<2>(u);
+                if (it == vec->end())
+                {
+                    s.pop();
+                    vec->clear();
+                    pm->fulfilled_callbacks.clear();
+                    pm->rejected_callbacks.clear();
+                    continue;
+                }
+                push_frame(*it++);
+            }
         }
 
         void trigger_fulfill() {
+            state = State::PreFulfilled;
+            _trigger();
+        }
+
+        void trigger_reject() {
+            state = State::PreRejected;
+            _trigger();
+        }
+
+        void _resolve() {
+            if (state == State::Pending) state = State::PreFulfilled;
+        }
+
+        void _reject() {
+            if (state == State::Pending) state = State::PreRejected;
+        }
+
+        void _dep_resolve(const promise_t &npm) {
+            if (state == State::Pending)
+                fulfilled_pms.push_back(npm.pm);
+            else
+                npm->_trigger();
+        }
+
+        void _dep_reject(const promise_t &npm) {
+            if (state == State::Pending)
+                rejected_pms.push_back(npm.pm);
+            else
+                npm->_trigger();
+        }
+
+        void _resolve(pm_any_t _result) {
+            if (state == State::Pending)
+            {
+                result = _result;
+                state = State::PreFulfilled;
+            }
+        }
+
+        void _reject(pm_any_t _reason) {
+            if (state == State::Pending)
+            {
+                reason = _reason;
+                state = State::PreRejected;
+            }
+        }
+#else
+        void _resolve() { resolve(); }
+        void _reject() { reject(); }
+        void _resolve(pm_any_t result) { resolve(result); }
+        void _reject(pm_any_t reason) { reject(reason); }
+
+        void trigger_fulfill() {
             state = State::Fulfilled;
             for (const auto &cb: fulfilled_callbacks) cb();
             fulfilled_callbacks.clear();
@@ -323,7 +456,7 @@ namespace promise {
             for (const auto &cb: rejected_callbacks) cb();
             rejected_callbacks.clear();
         }
-
+#endif
         public:
 
         Promise(): state(State::Pending) {}
@@ -337,18 +470,25 @@ namespace promise {
                 case State::Pending:
                 return promise_t([this,
                                 on_fulfilled = std::forward<FuncFulfilled>(on_fulfilled),
-                                on_rejected = std::forward<FuncRejected>(on_rejected)](promise_t npm) {
+                                on_rejected = std::forward<FuncRejected>(on_rejected)
+                                ](promise_t &npm) {
                     add_on_fulfilled(gen_on_fulfilled(std::move(on_fulfilled), npm));
                     add_on_rejected(gen_on_rejected(std::move(on_rejected), npm));
+#ifndef CPPROMISE_USE_STACK
+                    _dep_resolve(npm);
+                    _dep_reject(npm);
+#endif
                 });
                 case State::Fulfilled:
                 return promise_t([this,
-                                on_fulfilled = std::forward<FuncFulfilled>(on_fulfilled)](promise_t npm) {
+                                on_fulfilled = std::forward<FuncFulfilled>(on_fulfilled)
+                                ](promise_t &npm) {
                     gen_on_fulfilled(std::move(on_fulfilled), npm)();
                 });
                 case State::Rejected:
                 return promise_t([this,
-                                on_rejected = std::forward<FuncRejected>(on_rejected)](promise_t npm) {
+                                on_rejected = std::forward<FuncRejected>(on_rejected)
+                                ](promise_t &npm) {
                     gen_on_rejected(std::move(on_rejected), npm)();
                 });
                 default: PROMISE_ERR_INVALID_STATE;
@@ -361,17 +501,23 @@ namespace promise {
             {
                 case State::Pending:
                 return promise_t([this,
-                                on_fulfilled = std::forward<FuncFulfilled>(on_fulfilled)](promise_t npm) {
+                                on_fulfilled = std::forward<FuncFulfilled>(on_fulfilled)
+                                ](promise_t &npm) {
                     add_on_fulfilled(gen_on_fulfilled(std::move(on_fulfilled), npm));
-                    add_on_rejected([this, npm]() {npm->reject(reason);});
+                    add_on_rejected([this, npm]() {npm->_reject(reason);});
+#ifndef CPPROMISE_USE_STACK
+                    _dep_resolve(npm);
+                    _dep_reject(npm);
+#endif
                 });
                 case State::Fulfilled:
                 return promise_t([this,
-                                on_fulfilled = std::forward<FuncFulfilled>(on_fulfilled)](promise_t npm) {
+                                on_fulfilled = std::forward<FuncFulfilled>(on_fulfilled)
+                                ](promise_t &npm) {
                     gen_on_fulfilled(std::move(on_fulfilled), npm)();
                 });
                 case State::Rejected:
-                return promise_t([this](promise_t npm) {npm->reject(reason);});
+                return promise_t([this](promise_t &npm) {npm->_reject(reason);});
                 default: PROMISE_ERR_INVALID_STATE;
             }
         }
@@ -382,16 +528,22 @@ namespace promise {
             {
                 case State::Pending:
                 return promise_t([this,
-                                on_rejected = std::forward<FuncRejected>(on_rejected)](promise_t npm) {
+                                on_rejected = std::forward<FuncRejected>(on_rejected)
+                                ](promise_t &npm) {
                     callback_t ret;
                     add_on_rejected(gen_on_rejected(std::move(on_rejected), npm));
-                    add_on_fulfilled([this, npm]() {npm->resolve(result);});
+                    add_on_fulfilled([this, npm]() {npm->_resolve(result);});
+#ifndef CPPROMISE_USE_STACK
+                    _dep_resolve(npm);
+                    _dep_reject(npm);
+#endif
                 });
                 case State::Fulfilled:
-                return promise_t([this](promise_t npm) {npm->resolve(result);});
+                return promise_t([this](promise_t &npm) {npm->_resolve(result);});
                 case State::Rejected:
                 return promise_t([this,
-                                on_rejected = std::forward<FuncRejected>(on_rejected)](promise_t npm) {
+                                on_rejected = std::forward<FuncRejected>(on_rejected)
+                                ](promise_t &npm) {
                     gen_on_rejected(std::move(on_rejected), npm)();
                 });
                 default: PROMISE_ERR_INVALID_STATE;
@@ -424,7 +576,7 @@ namespace promise {
     };
         
     template<typename PList> promise_t all(const PList &promise_list) {
-        return promise_t([&promise_list] (promise_t npm) {
+        return promise_t([&promise_list] (promise_t &npm) {
             auto size = std::make_shared<size_t>(promise_list.size());
             auto results = std::make_shared<values_t>();
             if (!*size) PROMISE_ERR_MISMATCH_TYPE;
@@ -435,19 +587,27 @@ namespace promise {
                     [results, size, idx, npm](pm_any_t result) {
                         (*results)[idx] = result;
                         if (!--(*size))
-                            npm->resolve(*results);
+                            npm->_resolve(*results);
                     },
-                    [npm](pm_any_t reason) {npm->reject(reason);});
+                    [npm](pm_any_t reason) {npm->_reject(reason);});
+#ifndef CPPROMISE_USE_STACK
+                pm->_dep_resolve(npm);
+                pm->_dep_reject(npm);
+#endif
                 idx++;
             }
         });
     }
 
     template<typename PList> promise_t race(const PList &promise_list) {
-        return promise_t([&promise_list] (promise_t npm) {
+        return promise_t([&promise_list] (promise_t &npm) {
             for (const auto &pm: promise_list) {
-                pm->then([npm](pm_any_t result) {npm->resolve(result);},
-                        [npm](pm_any_t reason) {npm->reject(reason);});
+                pm->then([npm](pm_any_t result) {npm->_resolve(result);},
+                        [npm](pm_any_t reason) {npm->_reject(reason);});
+#ifndef CPPROMISE_USE_STACK
+                pm->_dep_resolve(npm);
+                pm->_dep_reject(npm);
+#endif
             }
         });
     }