Skip to main content

Execution Order Algorithm

This document explains how Traces calculates the order in which endpoints execute during a collection. Understanding this algorithm helps when debugging dependency issues or unexpected execution sequences.

Overview​

Endpoints execute in an order that respects their dependencies. If endpoint B needs data from endpoint A, then A must execute first. The system uses Kahn's algorithm (topological sort) to compute this order, in calculateExecutionOrder().

Source file: apps/web/src/lib/graph/execution-order.ts

The module also exports several related helpers:

  • calculateExecutionOrder(endpoints, mappings) — the plain topological sort described below.
  • calculateExecutionOrderPreferring(endpoints, mappings, preferred) — a topological sort that stays as close as possible to a preferred (analyst-chosen) order, "self-healing" only what a real dependency forces.
  • validatePhaseOrder(phases, mappings) / autoFixPhaseOrder(phases, mappings, endpoints) — validate and repair a manual phase/stage layout (see the [Phases / execution-order docs note] in the Architecture index) against the dependency graph.
  • canOrderBefore(sourceId, targetId, mappings) — whether source can be placed before target without creating a cycle (used when offering reusable variables from a later-running producer).
  • extractPathParameters(path) / checkEndpointParameterConfiguration(endpoint, mappings) — path-parameter analysis (below).

Algorithm Walk-Through​

Step 1: Filter Enabled Endpoints​

The algorithm starts by filtering to only enabled endpoints. Disabled endpoints are excluded from the execution order entirely.

Input endpoints: [A, B, C, D, E]
Enabled: A, B, C, D (E is disabled)
Working set: [A, B, C, D]

Step 2: Build the Dependency Graph​

For each dependency mapping, the algorithm creates a directed edge from the source endpoint to the target endpoint. This represents "source must run before target."

Mapping: A.response.ids -> B.userId (path)
Creates edge: A -> B

Mapping: B.response.profile -> C.profileId (path)
Creates edge: B -> C

Graph edges:
  A -> B
  B -> C
  D (no edges - independent)

Step 3: Calculate In-Degrees​

The in-degree of an endpoint is the count of endpoints it depends on. Endpoints with in-degree 0 have no dependencies and can run immediately.

In-degrees:
  A: 0 (no dependencies)
  B: 1 (depends on A)
  C: 1 (depends on B)
  D: 0 (no dependencies)

Step 4: Initialize the Queue​

All endpoints with in-degree 0 are added to a processing queue. These are the "root" endpoints that can execute first.

Queue: [A, D]
Result: []

Step 5: Process the Queue​

The algorithm repeatedly:

  1. Removes an endpoint from the queue
  2. Adds it to the result
  3. Decrements the in-degree of all endpoints that depend on it
  4. If any endpoint's in-degree becomes 0, adds it to the queue
Iteration 1:
  Remove A from queue
  Result: [A]
  B's in-degree: 1 -> 0 (add B to queue)
  Queue: [D, B]

Iteration 2:
  Remove D from queue
  Result: [A, D]
  Queue: [B]

Iteration 3:
  Remove B from queue
  Result: [A, D, B]
  C's in-degree: 1 -> 0 (add C to queue)
  Queue: [C]

Iteration 4:
  Remove C from queue
  Result: [A, D, B, C]
  Queue: []

Final order: [A, D, B, C]

Step 6: Handle Circular Dependencies​

If the queue is empty but not all endpoints are in the result, there's a circular dependency. These endpoints are appended at the end.

Example circular dependency:
  X depends on Y
  Y depends on X

Neither X nor Y can reach in-degree 0.
After queue empties: remaining = [X, Y]
Final result: [...other endpoints..., X, Y]

Key Code References​

All within calculateExecutionOrder():

StepWhat it does
Filter ep.enabled !== falseFilter to enabled endpoints only
Init adjacencyList / inDegree mapsOne entry per enabled endpoint
Loop over mappingsBuild edges (source → target) and increment target in-degree
Seed queue from in-degree 0Find initial nodes with no dependencies
while (queue.length > 0)Main processing loop (Kahn's algorithm)
Final loop over endpointIdsAppend endpoints with circular dependencies
note

Line numbers are intentionally omitted — this file is actively edited and the function has moved. Search for calculateExecutionOrder in execution-order.ts.

Path Parameter Configuration​

The file also contains checkEndpointParameterConfiguration() which determines if an endpoint can actually execute. An endpoint won't execute if it has path parameters (like {userId}) without configured mappings.

How Parameter Checking Works​

  1. Extract required parameters from the path (e.g., /users/{userId} requires userId)
  2. Check mappings for parameters targeting this endpoint's path location
  3. Check endpoint's parameterExtraction config for additional sources
  4. Return list of missing parameters
Path: /users/{userId}/posts/{postId}
Required: [userId, postId]

Mappings for this endpoint:
  - userId <- A.response.data[*].id (path)

Result:
  isConfigured: false
  missingParams: [postId]
  requiredParams: [userId, postId]

Debugging Tips​

"Endpoint runs before its dependency"​

Check that:

  1. The source endpoint is enabled
  2. The mapping connects the correct endpoints
  3. The target endpoint ID matches exactly

"Endpoint shows as skipped"​

The endpoint has unconfigured path parameters. Check:

  1. All {param} in the path have mappings
  2. Mappings target the path location (not query or body)

"Circular dependency detected"​

Review the dependency chain. Common causes:

  • A depends on B for parameter X, B depends on A for parameter Y
  • Indirect cycles through multiple endpoints