Perhaps there is an iterative approach instead of recursive?

[mtdowling]

This library currently uses recursion for promise chain resolution. Using a promise and chaining off of the promise potentially forever, will cause a stack overflow due to deep recursion.

Here's a really contrived example:

$d = new \React\Promise\Deferred();
$p = $d->promise();
$f = function ($x) {
    echo xdebug_get_stack_depth() . ', ';
    return $x;
};

$last = $p;
for ($i = 0; $i < 1000; $i++) {
    $last = $last->then($f);
}

$d->resolve('test');

Running this code will show that the stack depth grows significantly for each promise resolution:

9, 14, 19, 24, 29, 34, 39, 44, 49, 54, 59, 64, 69, 74, 79, 84, 89, 94, PHP Fatal error:  Maximum function nesting level of '100' reached, aborting!

I don't usually use XDebug's default nesting limit of 100, but this illustrates the point that this library provides a recursive solution. I wonder if there is a way to implement promise resolution iteratively.

@jsor Have you ever attempted this or considered an iterative approach? It seems like some kind of directed acyclic graph structure that branches off of the deferred() would allow for an iterative approach.

[igorw]

We might be able to put a trampoline inside then or resolve to keep the stack size constant.

[jsor]

👍
Haven't done anything in this direction. Unfortunately, i'm swamped with work at the moment. So, if anyone wants to take a stab at it....

[mtdowling]

Here's a trimmed down stack trace that shows where the recursion is happening:

PHP Stack trace:
PHP   1. {main}() test.php:0
PHP   2. React\Promise\Deferred->resolve() test.php:18
PHP   3. call_user_func() /react/promise/src/Deferred.php:35
PHP   4. React\Promise\Promise->React\Promise\{closure}() /react/promise/src/Deferred.php:35
PHP   5. React\Promise\Promise->resolve() /react/promise/src/Promise.php:122
PHP   6. React\Promise\Promise->settle() /react/promise/src/Promise.php:83
PHP   7. React\Promise\Promise->React\Promise\{closure}() /react/promise/src/Promise.php:109
PHP   8. React\Promise\FulfilledPromise->then() /react/promise/src/Promise.php:70
PHP   9. React\Promise\Promise->React\Promise\{closure}() /react/promise/src/FulfilledPromise.php:24
PHP  10. React\Promise\Promise->resolve() /react/promise/src/Promise.php:122
PHP  11. React\Promise\Promise->settle() /react/promise/src/Promise.php:83
PHP  12. React\Promise\Promise->React\Promise\{closure}() /react/promise/src/Promise.php:109
PHP  13. React\Promise\FulfilledPromise->then() /react/promise/src/Promise.php:70
PHP  14. React\Promise\Promise->React\Promise\{closure}() /react/promise/src/FulfilledPromise.php:24
PHP  15. React\Promise\Promise->resolve() /react/promise/src/Promise.php:122
PHP  16. React\Promise\Promise->settle() /react/promise/src/Promise.php:83
PHP  17. React\Promise\Promise->React\Promise\{closure}() /react/promise/src/Promise.php:109
PHP  18. React\Promise\FulfilledPromise->then() /react/promise/src/Promise.php:70
PHP  19. React\Promise\Promise->React\Promise\{closure}() /react/promise/src/FulfilledPromise.php:24
PHP  20. React\Promise\Promise->resolve() /react/promise/src/Promise.php:122
PHP  21. React\Promise\Promise->settle() /react/promise/src/Promise.php:83
PHP  22. React\Promise\Promise->React\Promise\{closure}() /react/promise/src/Promise.php:109
PHP  23. React\Promise\FulfilledPromise->then() /react/promise/src/Promise.php:70
PHP  24. React\Promise\Promise->React\Promise\{closure}() /react/promise/src/FulfilledPromise.php:24

[mtdowling]

I think @igorw is right: using a trampoline with promise resolution should be possible. It looks like bluebird uses trampolines, and here's a proof of concept promises implementation that uses trampolines: https://gist.github.com/Twisol/4526419.

[jsor]

I played a little bit: https://github.com/reactphp/promise/compare/queue
At least it can now run your example code :)

[jsor]

Since the queue implementation only reduces recursion per each promise chain, i also played with a global queue: https://github.com/reactphp/promise/compare/global-queue. It's a little bit more difficult because done() could throw exceptions which could break the queue.

I also realized, that introducing a queue opens the possibility to implement future-turn resolutions (#4).

[mtdowling]

Interesting. How would you envision the global queue technique working with something like React? Would it just drain the task queue on each tick?

[jsor]

Exactly, $this->drain() would become nextTick(function() { $this->drain() }).