# UNDF: UNDF-2026-000000349
# argo-0001 — O(N) Linear Scan in GetTask() Called Inside DAG Execution Loop

**Severity:** HIGH
**Complexity:** O(N·D) → O(D) per execution cycle, overall O(N²) → O(N)
**CWE:** CWE-407 (Algorithmic Complexity)

## Affected File

`workflow/controller/dag.go` lines 83–89

## Defective Code

```go
// dagContext holds context information about this context's DAG
type dagContext struct {
    // tasks are all the tasks in the template
    tasks []wfv1.DAGTask   // <-- stored as a SLICE
    ...
}

// GetTask returns the DAGTask for the given taskName.
// Called from: resolveDependencies, assessDAGPhase, executeDAG task loop,
//              ancestry.go GetTaskDependencies, validate.go
func (d *dagContext) GetTask(ctx context.Context, taskName string) *wfv1.DAGTask {
    for _, task := range d.tasks {          // O(N) linear scan
        if task.Name == taskName {
            return &task
        }
    }
    panic("target " + taskName + " does not exist")
}
```

**Why it is O(N²):** `GetTask()` is called multiple times per task during
`executeDAG()`, which itself iterates over all tasks (or target tasks). The
outer loop runs once per task being executed. Each call to `GetTask()` scans
the entire `tasks` slice. For a DAG with N tasks, this yields O(N²) total
comparisons per reconciliation cycle.

### Call graph (defective paths)

```
executeDAG()
  └── for _, taskName := range targetTasks              [O(N) tasks]
        ├── GetTask(taskName)                            [O(N) each]
        ├── GetTask(taskName).Hooks → GetTask(taskName) [O(N) each]
        └── GetTask(taskName).GetExitHook(...)           [O(N) each]

assessDAGPhase()
  └── for _, depName := range targetTasks               [O(N)]
        └── GetTask(depName)                             [O(N) each]

ancestry.go:GetTaskAncestry()
  └── recursive DFS over all ancestors
        └── GetTaskDependencies → resolveDependencies
              └── GetTask(taskName)                      [O(N) each]

ancestry.go:getTaskDependsLogic()
  └── for _, dependency := range dagTask.Dependencies   [O(D)]
        └── GetTask(dependency)                          [O(N) each]
```

Note: `dagValidationContext.GetTask()` in `validate.go:1315` correctly uses a
`map[string]wfv1.DAGTask` for O(1) lookup. The runtime `dagContext` uses a
slice — this discrepancy is the defect.

## Fixed Code

### Step 1: Add a task lookup map to `dagContext`

```go
type dagContext struct {
    boundaryName string
    boundaryID   string
    tasks        []wfv1.DAGTask
    taskByName   map[string]*wfv1.DAGTask  // <-- add this field
    ...
}
```

### Step 2: Populate the map in `executeDAG` where dagContext is constructed

```go
dagCtx := &dagContext{
    boundaryName: nodeName,
    boundaryID:   node.ID,
    tasks:        tmpl.DAG.Tasks,
    visited:      make(map[string]bool),
    tmpl:         tmpl,
    wf:           woc.wf,
    tmplCtx:      tmplCtx,
    dependencies: make(map[string][]string),
    dependsLogic: make(map[string]string),
    log:          woc.log,
}
// Build O(1) task lookup map
dagCtx.taskByName = make(map[string]*wfv1.DAGTask, len(tmpl.DAG.Tasks))
for i := range dagCtx.tasks {
    dagCtx.taskByName[dagCtx.tasks[i].Name] = &dagCtx.tasks[i]
}
```

### Step 3: Replace GetTask body

```go
func (d *dagContext) GetTask(ctx context.Context, taskName string) *wfv1.DAGTask {
    if task, ok := d.taskByName[taskName]; ok {
        return task
    }
    panic("target " + taskName + " does not exist")
}
```

## Complexity Analysis

| Version | GetTask | Per executeDAG cycle | N=500 tasks |
|---------|---------|---------------------|-------------|
| Defective | O(N) | O(N²) | ~125,000 compares |
| Fixed | O(1) | O(N) | ~500 lookups |

For a DAG with 500 tasks, the fixed version performs 250× fewer operations per
reconciliation cycle.

## Trigger Path

Every time Argo's workflow controller reconciles a running DAG workflow, it
calls `executeDAG()` → `executeDAGTask()` for each pending task. With N=500 tasks
and 3 `GetTask()` calls per task in the hot path, each reconciliation does 750×500=375,000
string comparisons instead of 750 map lookups. At 1 reconcile/second for a
long-running workflow, this adds seconds of unnecessary CPU per minute.
