non-self referencial cyclical promises?

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

non-self referencial cyclical promises?

Bradley Meck
I was doing some recursive data structure work and ended up with a cyclical promise that did not use a direct self reference. It can be reduced down to:

```javascript
var af, a = new Promise(f=>af=f);
var bf, b = new Promise(f=>bf=f);

af(b);bf(a); // the problem

a.then(_=>_) // some env/libs need this to start checking status
```

According to https://tc39.github.io/ecma262/#sec-promise-resolve-functions it looks like this should cause a recursive and infinite set of `EnqueueJob("PromiseJobs",...)`

This code currently does strange things in stable browsers, but doesn't seem to always cause infinite loops in the nightly builds of some things. I was wondering what the expected behavior is here because I am having trouble making sense of things.

_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Re: non-self referencial cyclical promises?

Kris Kowal-2
With Mark’s direction, the v2 branch of Q handles "vicious cycles" through the WeakMap that maps promises to their underlying handler. Whenever a promise is resolved with another promise, it walks forward through the chain of promises that the promise handler "became" through resolution. The first promise’s initial handler is a "vicious cycle" rejected promise handler, so if the walk forward through the resolution returns to itself, it remains resolved to the vicious cycle.


On Wed, Feb 24, 2016 at 11:38 AM Bradley Meck <[hidden email]> wrote:
I was doing some recursive data structure work and ended up with a cyclical promise that did not use a direct self reference. It can be reduced down to:

```javascript
var af, a = new Promise(f=>af=f);
var bf, b = new Promise(f=>bf=f);

af(b);bf(a); // the problem

a.then(_=>_) // some env/libs need this to start checking status
```

According to https://tc39.github.io/ecma262/#sec-promise-resolve-functions it looks like this should cause a recursive and infinite set of `EnqueueJob("PromiseJobs",...)`

This code currently does strange things in stable browsers, but doesn't seem to always cause infinite loops in the nightly builds of some things. I was wondering what the expected behavior is here because I am having trouble making sense of things.
_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss

_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Re: non-self referencial cyclical promises?

Bergi
In reply to this post by Bradley Meck
Bradley Meck wrote:

> I was doing some recursive data structure work and ended up with a cyclical
> promise that did not use a direct self reference. It can be reduced down to:
>
> ```javascript
> var af, a = new Promise(f=>af=f);
> var bf, b = new Promise(f=>bf=f);
>
> af(b);bf(a); // the problem
>
> a.then(_=>_) // some env/libs need this to start checking status
> ```
>
> According to https://tc39.github.io/ecma262/#sec-promise-resolve-functions
> it looks like this should cause a recursive and infinite set of
> `EnqueueJob("PromiseJobs",...)`

I fear that's what the standard says, yes. The ES6 spec does too many
(and in some cases, unreasonably many) `then` calls on promises anyway
to be followed by an efficient promise implementation.

[Promises/A+](https://promisesaplus.com/) in contrast says

| Implementations are encouraged, but not required, to detect such
| recursion and reject promise with an informative TypeError as the
| reason.

Regards,
  Bergi
_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Re: non-self referencial cyclical promises?

Mark S. Miller-2


On Wed, Feb 24, 2016 at 11:54 AM, Bergi <[hidden email]> wrote:
Bradley Meck wrote:
I was doing some recursive data structure work and ended up with a cyclical
promise that did not use a direct self reference. It can be reduced down to:

```javascript
var af, a = new Promise(f=>af=f);
var bf, b = new Promise(f=>bf=f);

af(b);bf(a); // the problem

a.then(_=>_) // some env/libs need this to start checking status
```

According to https://tc39.github.io/ecma262/#sec-promise-resolve-functions
it looks like this should cause a recursive and infinite set of
`EnqueueJob("PromiseJobs",...)`

I fear that's what the standard says, yes. The ES6 spec does too many (and in some cases, unreasonably many) `then` calls on promises anyway to be followed by an efficient promise implementation.

[Promises/A+](https://promisesaplus.com/) in contrast says

| Implementations are encouraged, but not required, to detect such
| recursion and reject promise with an informative TypeError as the
| reason.

I think the standard *should* require a deterministic error. E <https://github.com/kpreid/e-on-java/blob/master/src/jsrc/org/erights/e/elib/ref/ViciousCycleException.java>, Q, and my own Q-like system <https://github.com/tvcutsem/es-lab/blob/master/src/ses/makeQ.js#L700> all do. Within an engine, this technique should be straightforward to implement without slowing down the non-cyclic case.




Regards,
 Bergi

_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss



--
    Cheers,
    --MarkM

_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Re: non-self referencial cyclical promises?

Dean Tribble-2
I agree that the standard shoudl require a deterministic error, and I thought it did. In https://tc39.github.io/ecma262/#sec-promise-resolve-functions:

6. If SameValue(resolution, promise) is true, then
  a.Let selfResolutionError be a newly created TypeError object.
  b.Return RejectPromise(promise, selfResolutionError).

I suspect I assumed to much for "SameValue" here though. There's no well-defined other semantic answer to a cycle; it essentially always represents a bug, but could emerge dynamically out of bad code. You must either catch that as soon as possible or it's extremely difficult to isolate.

Another approach to efficiently achieve this in the implementation is to vigorously shorten targets. In this approach, the `bf(a)` would first shorten `a` so that it's internally pointing at the cell that `bf` will resolve to (chains are typically short, so keeping chains short is typically fast). Then the cycle check is simple and O(1). All the work is in shortening. There are some patterns that can make for interim long chains but they are straightforward to avoid.

On Wed, Feb 24, 2016 at 12:16 PM, Mark S. Miller <[hidden email]> wrote:


On Wed, Feb 24, 2016 at 11:54 AM, Bergi <[hidden email]> wrote:
Bradley Meck wrote:
I was doing some recursive data structure work and ended up with a cyclical
promise that did not use a direct self reference. It can be reduced down to:

```javascript
var af, a = new Promise(f=>af=f);
var bf, b = new Promise(f=>bf=f);

af(b);bf(a); // the problem

a.then(_=>_) // some env/libs need this to start checking status
```

According to https://tc39.github.io/ecma262/#sec-promise-resolve-functions
it looks like this should cause a recursive and infinite set of
`EnqueueJob("PromiseJobs",...)`

I fear that's what the standard says, yes. The ES6 spec does too many (and in some cases, unreasonably many) `then` calls on promises anyway to be followed by an efficient promise implementation.

[Promises/A+](https://promisesaplus.com/) in contrast says

| Implementations are encouraged, but not required, to detect such
| recursion and reject promise with an informative TypeError as the
| reason.

I think the standard *should* require a deterministic error. E <https://github.com/kpreid/e-on-java/blob/master/src/jsrc/org/erights/e/elib/ref/ViciousCycleException.java>, Q, and my own Q-like system <https://github.com/tvcutsem/es-lab/blob/master/src/ses/makeQ.js#L700> all do. Within an engine, this technique should be straightforward to implement without slowing down the non-cyclic case.




Regards,
 Bergi

_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss



--
    Cheers,
    --MarkM

_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss



_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss