Dependency Resolution

Topological Sort & Capability Registry

The CLI uses graph-based dependency resolution to ensure modules execute in the correct order.

The Problem

Modules have dependencies:

{
  id: 'connector/drizzle-nextjs',
  requires: ['framework/nextjs', 'database/drizzle']
}

Question: What order should modules execute?

Wrong order:

1. connector/drizzle-nextjs  ← Fails! Prerequisites missing
2. framework/nextjs          
3. database/drizzle

Correct order:

1. framework/nextjs        ← No prerequisites
2. database/drizzle        ← No prerequisites  
3. connector/drizzle-nextjs  ← Prerequisites met

Solution: Topological Sort

Dependency Graph

Implementation:

// src/core/services/dependency/dependency-graph.ts
export class DependencyGraph {
  private nodes: Set<string> = new Set();
  private edges: Map<string, Set<string>> = new Map();
 
  addNode(id: string): void {
    this.nodes.add(id);
  }
 
  addEdge(from: string, to: string): void {
    // Edge: from → to (from must execute before to)
    if (!this.edges.has(from)) {
      this.edges.set(from, new Set());
    }
    this.edges.get(from)!.add(to);
  }
 
  topologicalSort(): string[] {
    // Kahn's algorithm for topological sort
    const inDegree = new Map<string, number>();
    const queue: string[] = [];
    const result: string[] = [];
 
    // Calculate in-degrees
    this.nodes.forEach(node => {
      inDegree.set(node, 0);
    });
 
    this.edges.forEach((neighbors, node) => {
      neighbors.forEach(neighbor => {
        inDegree.set(neighbor, (inDegree.get(neighbor) || 0) + 1);
      });
    });
 
    // Find nodes with no dependencies
    inDegree.forEach((degree, node) => {
      if (degree === 0) queue.push(node);
    });
 
    // Process queue
    while (queue.length > 0) {
      const node = queue.shift()!;
      result.push(node);
 
      this.edges.get(node)?.forEach(neighbor => {
        const newDegree = (inDegree.get(neighbor) || 0) - 1;
        inDegree.set(neighbor, newDegree);
        
        if (newDegree === 0) {
          queue.push(neighbor);
        }
      });
    }
 
    return result;
  }
}

Capability Registry (Prerequisite Validator)

Dynamic Capability Tracking

The PrerequisiteValidator acts as a dynamic capability registry:

export class PrerequisiteValidator {
  private providedCapabilities: Set<string> = new Set();
 
  // Track what's been installed
  registerModule(blueprint: Blueprint): void {
    blueprint.provides?.forEach(capability => {
      this.providedCapabilities.add(capability);
    });
  }
 
  // Validate prerequisites
  validate(blueprint: Blueprint): ValidationResult {
    const missing = blueprint.requires?.filter(
      req => !this.providedCapabilities.has(req)
    ) || [];
 
    if (missing.length > 0) {
      return {
        valid: false,
        errors: [`Missing prerequisites: ${missing.join(', ')}`]
      };
    }
 
    return { valid: true };
  }
}

Execution Pattern

const validator = new PrerequisiteValidator();
 
for (const module of executionOrder) {
  const blueprint = loadBlueprint(module.id);
  
  // Check prerequisites
  const validation = validator.validate(blueprint);
  if (!validation.valid) {
    throw new Error(validation.errors.join(', '));
  }
  
  // Execute blueprint
  await execute(blueprint);
  
  // Register capabilities
  validator.registerModule(blueprint);
}

Key insight: Capabilities checked at runtime as modules execute, not statically.

Example: Execution Order Determination

Genome:

modules: [
  { id: 'ui/shadcn' },           // requires: framework
  { id: 'connector/drizzle-nextjs' },  // requires: framework, database
  { id: 'framework/nextjs' },    // requires: nothing
  { id: 'database/drizzle' }     // requires: nothing
]

Dependency Graph:

framework/nextjs  ──→  ui/shadcn
                  ──→  connector/drizzle-nextjs
database/drizzle  ──→  connector/drizzle-nextjs

Topological Sort Result:

1. framework/nextjs
2. database/drizzle
3. ui/shadcn
4. connector/drizzle-nextjs

Natural property: Adapters always before connectors!

Parallel Execution Batching

The ExecutionPlanner creates batches of modules that can execute in parallel, significantly improving performance.

The Problem

Sequential execution is slow:

Module 1 (5s)  →  Module 2 (5s)  →  Module 3 (5s)
Total: 15 seconds

But some modules have no dependencies - they could run simultaneously!

The Solution: Batched Parallel Execution

Batch 1 (parallel):        5s
├── framework/nextjs
├── database/drizzle
└── ui/shadcn-ui

Batch 2 (parallel):        5s
├── connectors/drizzle-nextjs
└── connectors/zustand-nextjs

Batch 3:                   5s
└── features/auth/tech-stack

Total: 15s → Same duration, but organized for future parallelization

Implementation

// ExecutionPlanner creates batches using topological levels
class ExecutionPlanner {
  createExecutionPlan(): ExecutionPlan {
    const batches: ExecutionBatch[] = [];
    const levels = this.calculateTopologicalLevels(graph);
    
    // Each level becomes a batch
    levels.forEach((modules, level) => {
      batches.push({
        batchNumber: level + 1,
        modules,
        canExecuteInParallel: modules.length > 1,
        estimatedDuration: this.estimateBatchDuration(modules),
        dependencies: this.getBatchDependencies(modules)
      });
    });
    
    return { batches, totalBatches: batches.length };
  }
}

Note: Current implementation executes batches sequentially but is architected for future parallel execution.

Feature Resolution System

When you request an abstract feature like features/auth, the CLI must resolve it to concrete implementations.

The Problem

Features have multiple implementations:

// User requests:
{ id: 'features/auth' }
 
// But which implementation?
// - Backend: better-auth-nextjs, clerk-nextjs, supabase-auth?
// - Frontend: auth-shadcn, auth-mui, auth-chakra?

The Solution: Manifest-Driven Resolution

The CLI uses a three-step intelligent resolution process:

Step 1: Stack Detection

Extract the project's technology stack from genome modules:

// From genome modules:
modules: [
  { id: 'framework/nextjs' },
  { id: 'database/drizzle' },
  { id: 'ui/shadcn-ui' }
]
 
// Detected stack:
{
  backend: ['nextjs', 'drizzle'],
  frontend: ['shadcn', 'nextjs'],
  ui: ['shadcn', 'tailwind']
}

Step 2: Fetch Feature Manifest

Load the auto-generated feature manifest:

// features/auth/auth.manifest.json
{
  "id": "auth",
  "implementations": [
    {
      "type": "backend",
      "stack": ["better-auth", "nextjs"],
      "moduleId": "features/auth/backend/better-auth-nextjs"
    },
    {
      "type": "frontend",
      "stack": ["shadcn", "nextjs"],
      "moduleId": "features/auth/frontend/shadcn"
    },
    {
      "type": "tech-stack",
      "moduleId": "features/auth/tech-stack"
    }
  ]
}

Step 3: Match & Return

// CLI resolves abstract feature to concrete modules:
[
  { id: 'features/auth/backend/better-auth-nextjs' },
  { id: 'features/auth/frontend/shadcn' },
  { id: 'features/auth/tech-stack' }
]

Why This Matters:

User-friendly: Just request features/auth, CLI figures out the rest Stack-aware: Automatically picks implementations that match your stack Future-proof: Adding new implementations doesn't break existing genomes

Next: Orchestrator Layer →

Type System Caching System