Rewind of nested orchestration deadlocks when a Task.all had multiple failed activities (only one failed sibling re-dispatched on replay)

[YunchuWang]

Summary

Rewind support (added in #296) does not correctly complete a nested orchestration when a Task.all (fan-out) contained more than one failed activity. After a server-side rewind (Azure Storage / DurableTask.Core backend), the worker re-dispatches only one of the previously-failed sibling activities and leaves the other as a permanently-unresolved pending task. The child sub-orchestration's Task.all never resolves, so no SubOrchestrationInstanceCompleted is emitted after the rewind, the parent and root orchestrations never complete, and the instance hangs until the caller times out.

This blocks rewind parity for Azure Functions durable-functions v4 (the consolidation onto durabletask-js): the extension E2E test RewindOrchestratorTests.RewindFailedOrchestration_ShouldSucceed passes on the classic v3 SDK but times out on durabletask-js for the identical app + backend.

Impact

• Any rewind of a failed orchestration whose failure fanned out through a Task.all with 2+ failed activities in the same sub-orchestration will hang instead of completing.
• Single-failure and single-level cases appear unaffected; the defect is specific to multiple failed siblings inside one Task.all, in a sub-orchestration whose completion must propagate back up.

Scope / what this is NOT

• Reproduced on the Azure Storage backend, where rewind is computed server-side by DurableTask.Core. The worker receives an ordinary replay whose history has been rewritten by the backend — it does not go through the EXECUTIONREWOUND path. worker/rewind.ts buildRewindResult is not exercised here (0 EXECUTIONREWOUND events observed), so this is separate from Add rewind support #296's buildRewindResult.
• Not the entity-replay corruption fixed in Fix #291: accept EVENTSENT/EVENTRAISED confirmation for entity calls on classic (Azure Storage) backend #294 — 0 sendEvent ... trying to call a different method occurrences in the failing run.
• The host performed the rewind correctly (RewindInstance returns HTTP 200, State: Rewound), and re-dispatched the replay. The stall is worker-side: the executor returns 0 actions while still awaiting a task.

Reproduction

App: the RewindOrchestration sample used by the extension E2E suite (checked into Azure/azure-functions-durable-extension at test/e2e/Apps/BasicNode/src/functions/RewindOrchestration.ts). Shape:

RewindParentOrchestration
  Task.all([ SucceedSub, FailParentSub_1, FailParentSub_2, SucceedSub ])
    FailParentSub -> SucceedActivity -> (callEntity) -> FailChildSub
      FailChildSub:
        Task.all([ SucceedActivity, FailActivity_1, FailActivity_2, (callEntity) ])

FailActivity throws on the first numFailures invocations, then succeeds. Both FailActivity_1 and FailActivity_2 fail on the first attempt, so the failure propagates FailChildSub -> FailParentSub -> root, leaving the instance Failed.

Steps:

1. Start the orchestration (input=fail, numFailures=1), wait for Failed.
2. Call rewind on the instance.
3. Expected: retried activities succeed and the orchestration reaches Completed.
4. Actual: the orchestration never reaches Completed; the caller times out.

A/B confirmation (single variable = the JS SDK)

Same app source (verified byte-identical via SHA-256 of every source file), same Azure Storage backend, only the durable-functions/durabletask-js package swapped:

Arm	SDK	Result
A (control)	published classic v3 SDK	RewindFailedOrchestration_ShouldSucceed(1) and (2) PASS
B (treatment)	durabletask-js consolidated worker (this repo main, incl. #293/#294/#296)	both FAIL — Orchestration did not reach Completed status within 30 seconds

The v3 SDK completing the identical rewritten history confirms the scenario is completable on Azure Storage and that this is a durabletask-js worker defect, not a backend or sample issue. The extension's own CI corroborates the baseline: the azurestorage-*(node) legs (which run this test — it is only DTS/Java/Python/PowerShell-skipped, not Node/AzureStorage-skipped) are green on the published SDK.

Root cause (worker replay)

Post-rewind, the deepest child FailChildSubOrchestration replays a rewritten history that still contains a TASKSCHEDULED event for one of the two failed sibling activities, but with its terminal completion event (TaskFailed/TaskCompleted) stripped by the rewind. Observed in the worker trace (single child instance):

Rebuilding local state with 16 history events
... TASKSCHEDULED (6) ... TASKSCHEDULED (6) ...
Waiting for 2 task(s) and 0 event(s)   ->   Returning 1 action(s)     # only ONE failed sibling re-dispatched
FailActivity started -> completed "Success!"                          # that one retry runs and succeeds
Waiting for 1 task(s) and 0 event(s)   ->   Returning 0 action(s)     # DEADLOCK: second sibling orphaned

• The failed sibling whose TaskScheduled was removed by the rewind is correctly re-generated as a new scheduleTask action on replay → runs → succeeds.
• The failed sibling whose TaskScheduled was retained (completion stripped) is mis-handled: handleTaskScheduled deletes its entry from _pendingActions (assuming a completion will arrive later), but no completion ever arrives after a rewind. The corresponding _pendingTasks entry is never resolved and is never re-dispatched → the Task.all blocks forever.
• Because the child never resolves, 0 SubOrchestrationInstanceCompleted are emitted after the rewind; the parent and root Task.all never resolve; no root ExecutionCompleted → timeout.

Most-likely fix direction: during replay reconciliation, a task that is scheduled-but-not-completed because its terminal event was rewound away must be re-dispatched (its scheduleTask action retained), rather than treated as "already in flight" and dropped. This needs to cover all such orphaned siblings in a Task.all, not just the ones whose TaskScheduled the backend also removed. Verifying the _pendingTasks / _pendingActions bookkeeping in orchestration-executor.ts (handleTaskScheduled, getActions) for the rewound-history shape is the place to start.

Minor secondary observation

During replay the worker logs Unknown history event type: GENERICEVENT (18), skipping... and ... ORCHESTRATORCOMPLETED (15), skipping.... These appear benign (the run's failure is fully explained by the orphaned-task deadlock above), but the skipped GENERICEVENT/ORCHESTRATORCOMPLETED handling in the rewound-history path may be worth a confirming glance.

Suggested test

Add an in-memory executor/e2e case: a sub-orchestration whose Task.all contains two activities that both fail on first attempt; drive it to Failed, rewind, and assert the sub-orchestration and its parent reach Completed with each failed activity invoked exactly numFailures + 1 times. (This mirrors RewindOrchestratorTests.RewindFailedOrchestration_ShouldSucceed in the extension.)