Repository: vercel/next.js
Pull request: Turbopack: fix race condition when invalidating

### What?

Fixes a race condition where invalidations got lost, especially after restoring from persistent cache.

Theoretically when executing a task again we would remove all dependencies and they would be slowly added again while outputs/cells are read during the execution.

But in practice we don't want to do that, as removing and re-adding dependencies would be very expensive and usually most dependencies stay the same anyway.
This is especially expensive as dependencies are bi-directional, so we would also need to remove and re-add the `dependent` edge (the reverse edge) which would require touching a lot tasks.
Touching persisted items of a task is also expensive as touching them would mark the task as "needs persisting", which would store it to DB causing more unnecessary work.

So instead we mark all dependencies as outdated when the task starts to execute and slowly remove the outdated flags. When the task has finished we really remove all remaining outdated dependencies. The "outdated" marker is transient, so it won't be persisted and it's only uni-directional, meaning it will only be on the in-progress task and not on the reverse edge.

But that also means we need to make an additional check when invalidating a task based on the "dependent" edge. These edge might be outdated, so we need to make the extra check whether the "dependency" (the reverse edge) is marked as "outdated". In that case we can ignore the "dependent" edge.

At least that was my thinking before this change...

There is also "recomputing" of tasks. This happens when some cells are no longer available (e. g. they might not be serializable and therefore not in the persistent cache). In this phase we re-execute a tasks to recompute these cells. For a "recomputing" tasks we don't expect any changes to cells. We detect if we are in the "recomputing" phase, by checking the "dirty" flag of the task. If it's not dirty, we are recomputing and don't expect changes. If it's dirty, some inputs might have changed and we can expect potential changes to cell. It's important to note that a task might become dirty during execution so we would start the task for recomputing, but while it's executing there are concurrent changes to cells it did read or will read which switches it to the normal execution. Note that therefore it need to be made dirty.

Let's considers the two cases "did read" and "will read":

"did read": In this case there is a normal dependency and we can follow it as usual and make the task dirty and stale. Note that the task might read the cell again during the current execution, but that's not a problem.

"will read": In this case there is a outdated dependency. (Luckily we have a dependency at all. If we would do the "theoretical" solution, where all dependencies are removed when starting to execute, we couldn't detect that case at all.) We can follow the outdated dependency, and we want to flag the task as dirty (That's the change of this PR), but don't want to flag the task as stale. So the current execution is still valid, but it's potentially switched from "recomputing" to normal execution.

Before this change the task was not made dirty in the "will read" case and this caused it to stay in the "recomputing" execution. But since we don't expect (and allow) changes to cells in that phase, the change got lost and didn't fully propagate through the dependency graph causing all kind of weird effects:
* stuck errors
* cell not found errors
* missing updates
* inconsistent states
* incorrect content hashes on files

Explainer on dirty vs stale:

`dirty` is persisted and indicates whether some task inputs have changed. It will become clean again after the task execution has finished.
`stale` is a flag on `InProgress` tasks. It's not persisted. It indicates that the current in progress task execution is outdated/stale, since some inputs, that have already been read, have changed during the execution.
When a task finishes executing and it's stale, dirty will not cleared and the task will directly execute again.

Changed files:
filename: turbopack/crates/turbo-tasks-backend/src/backend/mod.rs
patch: @@ -2176,15 +2176,17 @@ impl<B: BackingStorage> TurboTasksBackendInner<B> {
                 span.record("result", "once task");
                 continue;
             }
+            let mut make_stale = true;
             let dependent = ctx.task(dependent_task_id, TaskDataCategory::All);
             if dependent.has_key(&CachedDataItemKey::OutdatedOutputDependency { target: task_id }) {
-                // output dependency is outdated, so it hasn't read the output yet
-                // and doesn't need to be invalidated
                 #[cfg(feature = "trace_task_output_dependencies")]
                 span.record("result", "outdated dependency");
-                continue;
-            }
-            if !dependent.has_key(&CachedDataItemKey::OutputDependency { target: task_id }) {
+                // output dependency is outdated, so it hasn't read the output yet
+                // and doesn't need to be invalidated
+                // But importantly we still need to make the task dirty as it should no longer
+                // be considered as "recomputation".
+                make_stale = false;
+            } else if !dependent.has_key(&CachedDataItemKey::OutputDependency { target: task_id }) {
                 // output dependency has been removed, so the task doesn't depend on the
                 // output anymore and doesn't need to be invalidated
                 #[cfg(feature = "trace_task_output_dependencies")]
@@ -2194,7 +2196,7 @@ impl<B: BackingStorage> TurboTasksBackendInner<B> {
             make_task_dirty_internal(
                 dependent,
                 dependent_task_id,
-                true,
+                make_stale,
                 #[cfg(feature = "trace_task_dirty")]
                 TaskDirtyCause::OutputChange { task_id },
                 &mut queue,

filename: turbopack/crates/turbo-tasks-backend/src/backend/operation/update_cell.rs
patch: @@ -184,15 +184,17 @@ impl Operation for UpdateCellOperation {
                             // once tasks are never invalidated
                             continue;
                         }
+                        let mut make_stale = true;
                         let dependent = ctx.task(dependent_task_id, TaskDataCategory::All);
                         if dependent.has_key(&CachedDataItemKey::OutdatedCellDependency {
                             target: cell_ref,
                         }) {
                             // cell dependency is outdated, so it hasn't read the cell yet
-                            // and doesn't need to be invalidated
-                            continue;
-                        }
-                        if !dependent
+                            // and doesn't need to be invalidated.
+                            // But importantly we still need to make the task dirty as it should no
+                            // longer be considered as "recomputation".
+                            make_stale = false;
+                        } else if !dependent
                             .has_key(&CachedDataItemKey::CellDependency { target: cell_ref })
                         {
                             // cell dependency has been removed, so the task doesn't depend on the
@@ -203,7 +205,7 @@ impl Operation for UpdateCellOperation {
                         make_task_dirty_internal(
                             dependent,
                             dependent_task_id,
-                            true,
+                            make_stale,
                             #[cfg(feature = "trace_task_dirty")]
                             TaskDirtyCause::CellChange {
                                 value_type: cell_ref.cell.type_id,