Task.delay test fails

[thomasvargiu]

🐛 Bug report

I was working to a new feature and before to open a PR I run npm test. It fails creating docs because Task/delay tests failed.

Current Behavior

Test file:

./docs/examples/src-Task.ts-function-delay-0.ts

  [
+   'd',
-   'a',
    'b',
+   'a',
-   'd',
    'c'
  ]

Expected behavior

Same order on my system (?)

Reproducible example

import * as assert from 'assert'
import { sequenceT } from '../../src/Apply'
import * as T from '../../src/Task'

async function test() {
  const log: Array<string> = []
  const append = (message: string): T.Task<void> =>
    T.fromIO(() => {
      log.push(message)
    })
  const fa = append('a')
  const fb = append('b')
  const fc = T.delay(10)(append('c'))
  const fd = append('d')
  await sequenceT(T.ApplyPar)(fa, fb, fc, fd)()
  assert.deepStrictEqual(log, ['a', 'b', 'd', 'c'])
}

test()

Command:

$ npx mocha -r ts-node/register docs/examples/src-Task.ts-function-delay-0.ts

Suggested solution(s)

I don't know if it's a bug or a different behaviour on my system (MacOS), but I tested it even with docker.

Additional context

I know it's different, but the following snippet using Promise.all() works as expected.

import * as assert from 'assert'
import * as T from '../../src/Task'

async function test() {
  const log: Array<string> = []
  const append = (message: string): T.Task<void> =>
    T.fromIO(() => {
      log.push(message)
    })
  const fa = append('a')
  const fb = append('b')
  const fc = T.delay(10)(append('c'))
  const fd = append('d')
  await Promise.all([fa(), fb(), fc(), fd()])
  assert.deepStrictEqual(log, ['a', 'b', 'd', 'c'])
}

test()

Your environment

Same as master@13e94a4183c7f7878fc7a4c99c9b3c170672916d branch.

OS: MacOS Monterey 12.0.1
Node: v17.0.1
Tested even with docker-for-mac with node:12: v12.22.7

[fmpanelli]

I can confirm the same problem on
OS: Win11 Pro 21H2 build 22000.318
Node: v14.18.2 and v16.13.1 (I tried both)

The problem is not systematic, I mean:

• it seems to happen each every time if I run the single test npx mocha -r ts-node/register docs/examples/src-Task.ts-function-delay-0.ts
• it happens occasionally if I run npm run docs

[imcotton]

Tested fails under v2.11.5 and v2.11.4, but was OK in v2.11.3, seems broken by #1591.

/cc @mikearnaldi

[mikearnaldi]

Using parallel combinators while relying on ordering is a funny combo. Apparently microtasks execution order isn't guaranteed.

[imcotton]

@mikearnaldi Do you mean it's uncommonly used code example from docs?

I think these two should exchangeable behavior-wise here:

import { sequenceT } from '../../src/Apply'
import * as T from '../../src/Task'

- await sequenceT(T.ApplyPar)(fa, fb, fc, fd)()

+ await T.sequenceArray([     fa, fb, fc, fd])()

[thomasvargiu]

@mikearnaldi @imcotton The weird thing is that output is in reverse order. I'm asking myself whether there is a way to fix it.

Changing the ap function

fp-ts/src/Task.ts

Lines 131 to 132 in ee7c1da

	export const ap: <A>(fa: Task<A>) => <B>(fab: Task<(a: A) => B>) => Task<B> = (fa) => (fab) => () =>
	Promise.all([Promise.resolve().then(fab), Promise.resolve().then(fa)]).then(([f, a]) => f(a))

with:

export const ap: <A>(fa: Task<A>) => <B>(fab: Task<(a: A) => B>) => Task<B> = (fa) => (fab) => () =>
  Promise.all([fab(), Promise.resolve().then(fa)]).then(([f, a]) => f(a))

removing the deferred promise for fab that it's the function to apply fix the issue. But I'm not sure whether is logically correct to change it or not.

[mikearnaldi]

@mikearnaldi Do you mean it's uncommonly used code example from docs?

I think these two should exchangeable behavior-wise here:

import { sequenceT } from '../../src/Apply'
import * as T from '../../src/Task'

- await sequenceT(T.ApplyPar)(fa, fb, fc, fd)()

+ await T.sequenceArray([     fa, fb, fc, fd])()

No, one is doing things in sequence and the other one in parallel which has completely different guarantees, the output should be the same (and it is) ofc but not the behaviour.

@mikearnaldi @imcotton The weird thing is that output is in reverse order. I'm asking myself whether there is a way to fix it.

Changing the ap function

fp-ts/src/Task.ts

Lines 131 to 132 in ee7c1da

	export const ap: <A>(fa: Task<A>) => <B>(fab: Task<(a: A) => B>) => Task<B> = (fa) => (fab) => () =>
	Promise.all([Promise.resolve().then(fab), Promise.resolve().then(fa)]).then(([f, a]) => f(a))

with:

export const ap: <A>(fa: Task<A>) => <B>(fab: Task<(a: A) => B>) => Task<B> = (fa) => (fab) => () =>
  Promise.all([fab(), Promise.resolve().then(fa)]).then(([f, a]) => f(a))

removing the deferred promise for fab that it's the function to apply fix the issue. But I'm not sure whether is logically correct to change it or not.

Calling fab() without suspension makes it stack unsafe as it will force sync recursion, the evaluation should be deferred. The order is already respected in many JS engines, in fact the there are tests that rely on order of execution and are passing in the CI but there is simply no guarantee of that being the case in general across engines and across systems.

We may get away with a different approach that centralize suspension in a suspended loop that will respect the order in starting the operations but generally speaking you should never rely on order of execution of parallel things, in fact the sole reason we can even talk about that is because JS is single threaded.

[imcotton]

Just make sure we were on the same page, sequenceT(T.ApplyPar) and T.sequenceArray are parallel, the sequential one should be sequenceT(T.ApplySeq) and T.sequenceSeqArray (not the case here), correct?

the output should be the same (and it is)

But it rather not in v2.11.5 and v2.11.4 which lead OP to this issue.

[mikearnaldi]

Just make sure we were on the same page, sequenceT(T.ApplyPar) and T.sequenceArray are parallel, the sequential one should be sequenceT(T.ApplySeq) and T.sequenceSeqArray (not the case here), correct?

the output should be the same (and it is)

But it rather not in v2.11.5 and v2.11.4 which lead OP to this issue.

So sequenceArray is ultimately implemented in terms of traverseReadonlyNonEmptyArrayWithIndex

fp-ts/src/Task.ts

Line 484 in ee7c1da

export const traverseReadonlyNonEmptyArrayWithIndex = <A, B>(f: (index: number, a: A) => Task<B>) => (

that isn't using any applicative but is directly implemented in terms of Promise.all so it is true that it is parallel but it is not an alias, in fact I believe it was implemented that way to get a degree of safety in a previous PR.

The output of the program is the same, the execution order is not guaranteed to be the same. The OP issue comes from observing the execution order via:

T.fromIO(() => {
  log.push(message)
})

This isn't the same as collecting the output, in fact the result of T.sequenceArray([fa, fb, fc]) is the same as A.sequence(T.ApplyPar)([fa, fb, fc]) both are Task<[a, b, c]>.

[thomasvargiu]

Ok, I agree with @mikearnaldi, the behavior is different but the output is the same, it's not a bug. I think we should just change the test in the example.

[thomasvargiu]

I opened a PR #1639 if you want to review it. It just checks delayed task.

[mikearnaldi]

Seems like the only real needed suspension point is chain the order screw-up comes from suspending map:

#1640

Not too sure why that would be the case though.

[imcotton]

I come to agree to fix the example code as in #1639 since micro tasks are not in guaranteed ordering, as long as delay part have been properly addressed then it's good enough maybe?

[mikearnaldi]

I agree that the tests and demos should show code that only rely on guaranteed behaviour but also it's very strange that suspending map changes the behaviour, microtasks don't have a strong guarantee but de-facto the order of execution is preserved...

Promise.resolve().then(() => {
log("a")
})
Promise.resolve().then(() => {
log("b")
})

logs a before b so I truly don't understand what's going on at a deeper level