# Grid DAG Plan Format Specification

**Version:** 1.7.x
**Status:** Active
**Related:** GRID_DAG_EXECUTION_SPEC.md

---

## Overview

This document specifies the DAG-based plan format for The Grid. Plans express task dependencies explicitly via `depends_on` fields, enabling true parallel execution where any task whose dependencies are satisfied can start immediately.

---

## Plan YAML Frontmatter

### Required Fields

```yaml
---
cluster: "E-Commerce Platform"           # Mission/project name
block: 1                                  # Block number in mission
type: execute                             # Block type: plan | execute | verify
dag_enabled: true                         # REQUIRED for DAG execution

# Task definitions with explicit dependencies
tasks:
  - id: task-01                           # Unique task identifier
    name: "Create user model"             # Human-readable name
    type: auto                            # Task type (see Thread Types)
    depends_on: []                        # Empty = root task, can start immediately
    files_modified: [src/models/user.ts]  # Files this task will modify
    estimated_duration: 120               # Seconds (for scheduling)

  - id: task-02
    name: "Create auth API"
    type: auto
    depends_on: [task-01]                 # Waits for task-01 to complete
    files_modified: [src/api/auth.ts]
    estimated_duration: 180

# Computed by Planner (for visualization and scheduling)
dag_structure:
  layers: {}                              # Computed layer assignment
  critical_path: []                       # Computed critical path
  total_estimated: 0                      # Sum of critical path durations

# Backward-compatible wave assignment (computed from DAG)
computed_waves:
  1: [task-01]
  2: [task-02]
---
```

### Optional Fields

```yaml
---
# ... required fields ...

# Existing must_haves (unchanged from wave-based)
must_haves:
  truths: []
  artifacts: []
  key_links: []

# Test requirements (unchanged)
test_requirements:
  coverage_target: 80
  required_tests: []

# Blueprint data for visualization
blueprint:
  nodes: []                               # Visual node definitions
  edges: []                               # Visual edge definitions
  layout: "dagre"                         # Layout algorithm hint
---
```

---

## Dependency Specification

### Rules

1. **Empty `depends_on`**: Task is immediately executable (root node)
2. **Single dependency**: Task starts when that one task completes
3. **Multiple dependencies**: Task starts when ALL listed tasks complete (AND logic)
4. **No cycles allowed**: DAG validator rejects circular dependencies
5. **Transitive dependencies are implicit**: If A depends_on B, B depends_on C, don't list C in A's depends_on

### Examples

#### Parallel Tasks (No Dependencies)

```yaml
tasks:
  - id: scout-codebase
    name: "Scout codebase"
    depends_on: []                        # Can start immediately

  - id: scout-docs
    name: "Scout documentation"
    depends_on: []                        # Can start in parallel with above
```

**Result:** Both tasks start simultaneously at t=0.

#### Sequential Tasks (Linear Chain)

```yaml
tasks:
  - id: create-model
    name: "Create user model"
    depends_on: []

  - id: create-api
    name: "Create user API"
    depends_on: [create-model]            # Must wait for model

  - id: create-ui
    name: "Create user UI"
    depends_on: [create-api]              # Must wait for API
```

**Result:** create-model -> create-api -> create-ui (strictly sequential)

#### Fan-Out (One to Many)

```yaml
tasks:
  - id: setup-db
    name: "Setup database"
    depends_on: []

  - id: create-users
    name: "Create users table"
    depends_on: [setup-db]

  - id: create-products
    name: "Create products table"
    depends_on: [setup-db]

  - id: create-orders
    name: "Create orders table"
    depends_on: [setup-db]
```

**Result:** setup-db first, then all three table tasks run in parallel.

#### Fan-In (Many to One)

```yaml
tasks:
  - id: build-api
    name: "Build API"
    depends_on: []

  - id: build-ui
    name: "Build UI"
    depends_on: []

  - id: integration
    name: "Wire API and UI"
    depends_on: [build-api, build-ui]     # Waits for BOTH
```

**Result:** API and UI build in parallel, integration waits for both.

#### Diamond Pattern

```yaml
tasks:
  - id: init
    name: "Initialize"
    depends_on: []

  - id: left-branch
    name: "Left processing"
    depends_on: [init]

  - id: right-branch
    name: "Right processing"
    depends_on: [init]

  - id: merge
    name: "Merge results"
    depends_on: [left-branch, right-branch]
```

**Visual:**
```
        init
       /    \
   left      right
       \    /
        merge
```

---

## File Conflict Detection

Tasks with overlapping `files_modified` cannot run in parallel, even if the dependency graph allows.

### Automatic Conflict Resolution

```yaml
tasks:
  - id: task-a
    files_modified: [src/shared/types.ts, src/api/users.ts]

  - id: task-b
    files_modified: [src/shared/types.ts, src/api/products.ts]  # CONFLICT on types.ts
```

**DAG executor adds implicit dependency:** `task-b.depends_on.push(task-a)`

### Avoiding Conflicts

Plan tasks to minimize file overlap:

```yaml
# BAD: Overlapping files
tasks:
  - id: task-a
    files_modified: [src/utils/helpers.ts]  # Conflict!
  - id: task-b
    files_modified: [src/utils/helpers.ts]  # Conflict!

# GOOD: Separate concerns
tasks:
  - id: task-a
    files_modified: [src/utils/string-helpers.ts]
  - id: task-b
    files_modified: [src/utils/date-helpers.ts]
```

---

## Blueprint Data (Visualization)

The `blueprint` section provides data for DAG visualization.

### Node Definition

```yaml
blueprint:
  nodes:
    - id: task-01
      label: "Create Model"
      type: auto                          # auto | checkpoint | verify
      status: pending                     # pending | ready | running | completed | failed
      position:                           # Optional: explicit positioning
        x: 100
        y: 50
      metadata:
        duration: 120
        files: [src/models/user.ts]
```

### Edge Definition

```yaml
blueprint:
  edges:
    - source: task-01
      target: task-02
      type: dependency                    # dependency | file-conflict
      label: ""                           # Optional edge label
```

### Layout Hints

```yaml
blueprint:
  layout: "dagre"                         # dagre | force | hierarchical
  direction: "TB"                         # TB (top-bottom) | LR (left-right)
  spacing:
    node: 50
    rank: 100
```

### Computed Blueprint (Generated by Planner)

```yaml
blueprint:
  nodes:
    - id: scout-codebase
      label: "Scout Codebase"
      type: auto
      layer: 0
    - id: scout-docs
      label: "Scout Docs"
      type: auto
      layer: 0
    - id: plan-api
      label: "Plan API"
      type: auto
      layer: 1
    - id: exec-api
      label: "Execute API"
      type: auto
      layer: 2
      on_critical_path: true

  edges:
    - source: scout-codebase
      target: plan-api
      type: dependency
    - source: scout-docs
      target: plan-api
      type: dependency
    - source: plan-api
      target: exec-api
      type: dependency

  critical_path: [scout-codebase, plan-api, exec-api]
  total_layers: 3
```

---

## DAG Structure Computation

### Layer Assignment Algorithm

```python
def compute_layers(tasks: list) -> dict:
    """
    Compute layer (topological level) for each task.
    Layer 0 = no dependencies, Layer N = max(dependency layers) + 1
    """
    layers = {}
    task_map = {t['id']: t for t in tasks}

    def get_layer(task_id: str) -> int:
        if task_id in layers:
            return layers[task_id]

        task = task_map[task_id]
        deps = task.get('depends_on', [])

        if not deps:
            layers[task_id] = 0
        else:
            layers[task_id] = max(get_layer(dep) for dep in deps) + 1

        return layers[task_id]

    for task in tasks:
        get_layer(task['id'])

    # Group by layer
    layer_groups = {}
    for task_id, layer in layers.items():
        layer_groups.setdefault(layer, []).append(task_id)

    return layer_groups
```

### Critical Path Computation

```python
def compute_critical_path(tasks: list) -> list:
    """
    Find the critical path (longest path through DAG by duration).
    """
    task_map = {t['id']: t for t in tasks}
    memo = {}

    def longest_path_to(task_id: str) -> tuple:
        """Returns (duration, path) of longest path ending at task_id."""
        if task_id in memo:
            return memo[task_id]

        task = task_map[task_id]
        duration = task.get('estimated_duration', 0)
        deps = task.get('depends_on', [])

        if not deps:
            result = (duration, [task_id])
        else:
            best_dep = max(
                (longest_path_to(dep) for dep in deps),
                key=lambda x: x[0]
            )
            result = (best_dep[0] + duration, best_dep[1] + [task_id])

        memo[task_id] = result
        return result

    # Find task with longest path (could be any leaf)
    all_paths = [longest_path_to(t['id']) for t in tasks]
    _, critical_path = max(all_paths, key=lambda x: x[0])

    return critical_path
```

### Wave Computation (Backward Compatibility)

```python
def compute_waves_from_dag(layers: dict) -> dict:
    """
    Convert DAG layers to wave format for backward compatibility.
    Wave N = Layer N (they're equivalent concepts).
    """
    waves = {}
    for layer, task_ids in layers.items():
        wave_num = layer + 1  # Waves are 1-indexed
        waves[wave_num] = task_ids
    return waves
```

---

## Migration from Wave-Based Plans

### Converting Wave Format to DAG

Old wave-based plan:
```yaml
---
wave: 2
depends_on: [block-01]
---
```

New DAG-based plan:
```yaml
---
dag_enabled: true
tasks:
  - id: task-01
    depends_on: []       # Was wave: 1
  - id: task-02
    depends_on: [task-01]  # Was wave: 2

computed_waves:
  1: [task-01]
  2: [task-02]
---
```

### Automatic Conversion

When `dag_enabled: false` or missing, executor treats the plan as wave-based:
- All tasks in same block run sequentially
- Block-level `depends_on` determines inter-block order

When `dag_enabled: true`:
- Task-level `depends_on` determines exact execution order
- Maximum parallelism achieved automatically

---

## Complete Plan Example

```yaml
---
cluster: "User Management System"
block: 1
type: execute
dag_enabled: true

tasks:
  - id: create-user-model
    name: "Create user model and schema"
    type: auto
    depends_on: []
    files_modified: [src/models/user.ts, prisma/schema.prisma]
    estimated_duration: 120

  - id: create-auth-model
    name: "Create auth tokens model"
    type: auto
    depends_on: []
    files_modified: [src/models/auth.ts, prisma/schema.prisma]
    estimated_duration: 90

  - id: create-user-api
    name: "Create user CRUD API"
    type: auto
    depends_on: [create-user-model]
    files_modified: [src/api/users/route.ts]
    estimated_duration: 180

  - id: create-auth-api
    name: "Create auth API (login/logout)"
    type: auto
    depends_on: [create-user-model, create-auth-model]
    files_modified: [src/api/auth/route.ts]
    estimated_duration: 240

  - id: verify-integration
    name: "Verify user + auth integration"
    type: checkpoint:human-verify
    depends_on: [create-user-api, create-auth-api]
    estimated_duration: 60

dag_structure:
  layers:
    0: [create-user-model, create-auth-model]
    1: [create-user-api, create-auth-api]
    2: [verify-integration]
  critical_path: [create-user-model, create-auth-api, verify-integration]
  total_estimated: 420

computed_waves:
  1: [create-user-model, create-auth-model]
  2: [create-user-api, create-auth-api]
  3: [verify-integration]

must_haves:
  truths:
    - "User can register with email/password"
    - "User can login and receive JWT"
    - "Protected routes require valid JWT"
  artifacts:
    - path: src/models/user.ts
      provides: "User model definition"
      min_lines: 20
    - path: src/api/auth/route.ts
      provides: "Auth endpoints"
      min_lines: 50
      exports: [POST]
  key_links:
    - from: src/api/auth/route.ts
      to: src/models/user.ts
      via: "import and query"
      pattern: "import.*User.*from.*models"

blueprint:
  nodes:
    - id: create-user-model
      label: "User Model"
      type: auto
      layer: 0
    - id: create-auth-model
      label: "Auth Model"
      type: auto
      layer: 0
    - id: create-user-api
      label: "User API"
      type: auto
      layer: 1
    - id: create-auth-api
      label: "Auth API"
      type: auto
      layer: 1
      on_critical_path: true
    - id: verify-integration
      label: "Verify"
      type: checkpoint
      layer: 2
      on_critical_path: true

  edges:
    - source: create-user-model
      target: create-user-api
      type: dependency
    - source: create-user-model
      target: create-auth-api
      type: dependency
    - source: create-auth-model
      target: create-auth-api
      type: dependency
    - source: create-user-api
      target: verify-integration
      type: dependency
    - source: create-auth-api
      target: verify-integration
      type: dependency

  layout: dagre
  direction: TB
---
```

---

## Validation Rules

### Required for DAG Plans

1. `dag_enabled: true` must be set
2. All tasks must have unique `id` fields
3. All `depends_on` references must point to existing task IDs
4. No circular dependencies allowed
5. At least one task must have `depends_on: []` (entry point)

### Validation Errors

| Error | Description | Resolution |
|-------|-------------|------------|
| `CYCLE_DETECTED` | Circular dependency found | Remove cycle from depends_on |
| `MISSING_DEPENDENCY` | depends_on references unknown task | Fix task ID or add missing task |
| `NO_ENTRY_POINT` | All tasks have dependencies | Add task with depends_on: [] |
| `DUPLICATE_ID` | Multiple tasks with same ID | Make IDs unique |
| `FILE_CONFLICT_CYCLE` | File conflicts create cycle | Reorder tasks or split files |

---

## Integration with Existing Systems

### Executor Compatibility

Executors receive tasks with full dependency context:

```yaml
# Task prompt includes:
task:
  id: create-auth-api
  depends_on: [create-user-model, create-auth-model]
  dependency_outputs:
    create-user-model:
      files: [src/models/user.ts]
      exports: [User, UserSchema]
    create-auth-model:
      files: [src/models/auth.ts]
      exports: [AuthToken]
```

### Recognizer Compatibility

Recognizer verification unchanged - still checks:
- Artifact existence and substance
- Key link patterns
- Truth evidence

DAG execution doesn't affect verification, only scheduling.

### STATE.md Updates

```yaml
# New DAG fields in STATE.md
dag:
  enabled: true
  tasks:
    create-user-model:
      status: completed
      started_at: "2026-01-24T10:00:00Z"
      completed_at: "2026-01-24T10:02:00Z"
    create-auth-api:
      status: running
      started_at: "2026-01-24T10:02:00Z"
      progress: 0.4
  ready_queue: [create-user-api]
  file_locks:
    "src/api/auth/route.ts": create-auth-api
```

---

*DAG Plan Format Specification v1.7.x - The Grid Team*

*End of Line.*