First some background - strongly connected components affect execution in the module system in only subtle ways:

1. Error state propagation together as a single unit
2. Cycle root handling in supporting TLA attachment when multiple top-level entry points try to execute the same strongly connected component, allowing them to coordinate execution state through the same shared component root module [[CycleRoot]].

That's it! Otherwise strongly connected components are indeed relatively unobservable to end users. But correctly classifying strongly connected components is a fundamental invariant.

Now for (1) we don't formally propagate errors through the entire strongly connected component, we actually only propagate errors up the current stack of a strongly connected component.

Your simplification based on this observation does seem to be unobservable so far as (1) is concerned.

But, as mentioned when we discused this, your change very much does break the Tarjan algorithm's detection in being able to identify the strongly connected components correctly per Tarjan's algorithm.

Simple counter example where [1,1] indicates the final DFSIndex 1, DFSAncestorIndex 1 states.

A [0, 0]
A -> B [1,1]
A -> C [2, 1]
A -> D [3, 3]
D -> E [4, 3]

Under your scheme you would not correctly classify the two separate strongly connected components { B, C } and { D, E }, and instead classify both B and D as having the same ancestor index 1 since you are incorrectly conflating the component root index with the stack index.

That is you would transition all 4 modules together instead of handling them separately. This would also incorrectly set the cycle root in the evaluation code. The comparison between sccAncestorIndex and moduleIndex is also invalid as the stack indexing diverges from the module indexing for large parallel graphs.

As a side note - the onus is on you here to prove your modification or Tarjan's algorithm handles the edge cases, not on me to point out the counter examples.

As a side note - the onus is on you here to prove your modification or Tarjan's algorithm handles the edge cases, not on me to point out the counter examples.

I understand, that's why I split the change in small commits each of them trying to carefully explain why the change is correct 😅

Assuming that the example you mean is the following, which yields those [dfs index, dfs ancestor index] pairs and those two SCCs:

This is what happens with the updated algorithm:

• InnerModuleEvaluation(A):
  • stack depth: 0
  • A's _sccAncestorIndex_: 0
  • recursion (stack: [A]):
    • InnerModuleEvaluation(B):
      • stack depth: 1
      • B's _sccAncestorIndex_: 1
      • recursion (stack: [A, B]):
        • InnerModuleEvaluation(C):
          • stack depth: 2
          • C's _sccAncestorIndex_: 2
          • recursion (stack: [A, B, C]):
            • InnerModuleEvaluation(B):
              • returns B's stack depth: 1 → C's _sccAncestorIndex_ is updated to 1
          • returns C's _sccAncestorIndex_: 1 → B's _sccAncestorIndex_ is not updated
      • B's _sccAncestorIndex_ is the same as its stack depth (1): we detected a SCC!. The member of the SCC are B and all the subsequent elements in the stack (so B,C). We reset the stack to [A].
      • returns B's _sccAncestorIndex_: 1 → A's _sccAncestorIndex_ is not updated
    • InnerModuleEvaluation(D):
      • stack depth: 1
      • D's _sccAncestorIndex_: 1
      • recursion (stack: [A, D]):
        • InnerModuleEvaluation(E):
          • stack depth: 2
          • E's _sccAncestorIndex_: 2
          • recursion (stack: [A, D, E]):
            • InnerModuleEvaluation(D):
              • returns D's stack depth: 1 → E's _sccAncestorIndex_ is updated to 1
          • returns E's _sccAncestorIndex_: 1 → D's _sccAncestorIndex_ is not updated
      • D's _sccAncestorIndex_ is the same as its stack depth (1): we detected a SCC!. The member of the SCC are D and all the subsequent elements in the stack (so D,E). We reset the stack to [A].
      • returns D's _sccAncestorIndex_: 1 → A's _sccAncestorIndex_ is not updated
  • A's _sccAncestorIndex_ is the same as its stack depth (1): we detected a SCC!. The members of the SCC are A and all the subsequente elements in the stack (so just A). We reset the stack to [].

The updated algorithm correctly detects the three SCCs: BC, DE, and A.

Note that, both before and after this PR, the SCC detection rule is not "a set of module with the same associated number is a SCC". Already before these changes, multiple modules in the same SCC can have different [[DFSAncestorIndex]] values. For example (interactive):

Here the [[DFSIndex]], [[DFSAncestorIndex]] values are

• A: [0,0]
• B: [1,1]
• C: [2,1]
• D: [3,2]
• E: [4,1]

Even though D is in the same SCC as B/C/E.

Instead, the rule to tell that a module X is not a SCC root is that from X's outgoing edges you can reach a node with index lower than X. Then, if a module is a SCC root (so if the lowest index you can reach from X is X's index), the contents of the SCC is the list of modules in the stack starting from X.

The comparison between sccAncestorIndex and moduleIndex is also invalid as the stack indexing diverges from the module indexing for large parallel graphs.

Yes, and that's fine. When you have large parallel graphs (that are not in the same SCC), one of them is going to be processed before the other. What happens in the first of them has no effect at all on what SCCs there are in the second one. We can forget that we actually already used some indexes for that first completed graph part, and we can reuse them.

Edit: I'll publish a forked version of https://nicolo-ribaudo.github.io/es-module-evaluation with these changes.

I have a more precise proof that using the stack depth is equivalent to using the discovery index.

Consider a module graph that contains a module M, with the stack at the time M is first discovered (right after pushing M to it) being « s₀, s₁, ..., s_n-1, M = s_n ».

For a given module X, the discovery index of X is D(X) and the depth of the stack right before pushing it is S(X). Next(X) is the module that is discovered right after X (that is, D(Next(X)) = D(X)+1).

[*] There are two possible cases. One is the trivial one, when we are going down the left-most branch of the DFS tree, so D(s₀) = 0, D(s₁) = 1, ..., D(s_n) = n. In this case obviously D(s_i)=S(s_i) for each i.

If we are not in that situation, then there is a smallest j such that D(s_j) ≠ S(s_j) (that is, D(s_j) ≠ j). j > 0, because s₀ is the root module of the graph, which is pushed in the stack first and removed at the end of the whole process. Thus we have D(s₀)=S(s₀)=0, D(s₁)=S(s₁)=1, ..., D(s_j-1)=S(s_j-1)=j-1.

Now, we know that s_j ≠ Next(s_j-1) (otherwise D(s_j)=D(s_j-1)+1=(j-1)+1=j, which violates the condition on which we chose j). We also know that s_j is not reachable from Next(s_j-1), otherwise Next(s_j-1) would be on the stack between s_j-1 and s_j (which is impossible, since they are by definition consecutive in the stack).

Let { O₁...O_k } be the set of all k modules reachable from Next(s_j-1), Next(s_j-1) included, ordered such that D(O₁) < ... < D(O_k).

• [1] s_j is not in that set, because it's not reachable from Next(s_j-1). Given that s_j is reachable from all of s₀,...,s_j-1, all of those modules are also not in that set.
• [2] Given that j has been chosen to be minimal, s₀,s₁,...,s_j-1,O₁ are the beginning of the left-most branch of the DFS tree for s₀'s evaluation.

O₁...O_k are all discovered before s_j, so

• D(s_j-1) = S(s_j-1) = j-1
• D(O₁) = D(s_j-1) + 1 (by definition of O₁)
• D(O₂) = D(s_j-1) + 2
• ...
• D(O_k) = D(s_j-1) + k
• D(s_j-1) > D(O_k)

Given [1] and [2], Evaluation(s₀) is equivalent to first doing Evaluation(O₁) (which evaluates all and only the modules { O₁...O_k }) followed then by Evaluation(s₀). This has no effect on evaluation order, SCC detection, or on the modules in the stack when discovering a module not in the { O₁...O_k } set.

The effect of Evaluation(O₁) is that when we will then do Evaluation(s₀) all the modules { O₁...O_k } will have already been evaluated, thus we skip them in the DFS tree. Let's call D'(...) the discovery indexes of this Evaluation(s₀) that happens after Evaluation(O₁).

We have that for each module P:

• if D(P) > D(O_k), then D'(P) = D(P) - k < D(P).
• if D(P) < D(O₁), then D'(P) = D(P).

Thus we have that:

• D'(s₀)=D(s₀)=S(s₀), ..., D'(s_j-1)=D(s_j-1)=S(s_j-1)
• D'(s_j-1) < D'(s_j) < D(s_j)
• D'(s_j+1) < D(s_j+1)
• ...
• D'(M) < D(M)

Now, we repeat from [*]:

• either D'(M)=S(M), in which case we are done because we reached an equivalent situation in which the discovery index and the stack depth index of M correspond
• or D'(M)>S(M), in which case we do the whole process again to pre-evaluate a subtree while keeping the equivalence, obtaining a D''(M)<D'(M)<D(M). Iterating, we keep decreasing the discovery index of M, until when it must converge to being the same as S(M) (because we are decreasing it by at least 1 at each iteration).