# Apply Patch

**Source:** `src/runtime/apply-patch.ts` (Claude Code-style patching)  
**Category:** Agent Management - Code Modification  
**Purpose:** Safe, atomic code modifications with validation and rollback

## Overview

The Apply Patch algorithm enables AI agents to modify source code atomically using a structured patch format. It provides search-and-replace semantics with validation, conflict detection, and automatic rollback on failure.

```
┌─────────────────────────────────────────────────────────────┐
│                    AI Agent                                 │
│  "I need to fix the bug in line 42 of app.ts"               │
└─────────────────────┬───────────────────────────────────────┘
                      │ Generates patch
                      v
┌─────────────────────────────────────────────────────────────┐
│                 Apply Patch Algorithm                       │
│                                                             │
│  1. Parse patch format                                      │
│  2. Locate target file                                      │
│  3. Search for old_string (with context)                    │
│  4. Validate single match                                   │
│  5. Replace with new_string                                 │
│  6. Write atomically                                        │
│  7. Verify syntax (optional)                                │
│  8. Return success/error                                    │
└─────────────────────┬───────────────────────────────────────┘
                      │
                      v
┌─────────────────────────────────────────────────────────────┐
│                File System (Modified)                       │
│  app.ts saved with atomic write                             │
└─────────────────────────────────────────────────────────────┘
```

## Patch Format

### Basic Structure

```json
{
  "command": "apply_patch",
  "patches": [
    {
      "file": "src/app.ts",
      "old_string": "function greet(name: string) {\n  return `Hello, ${name}`\n}",
      "new_string": "function greet(name: string) {\n  if (!name) throw new Error('Name required')\n  return `Hello, ${name}`\n}"
    }
  ]
}
```

### Multi-Hunk Patches

```json
{
  "command": "apply_patch",
  "patches": [
    {
      "file": "src/app.ts",
      "old_string": "const PORT = 3000",
      "new_string": "const PORT = process.env.PORT ?? 3000"
    },
    {
      "file": "src/app.ts",
      "old_string": "app.listen(PORT)",
      "new_string": "app.listen(PORT, () => console.log(`Listening on ${PORT}`))"
    }
  ]
}
```

## Core Algorithm

### Search-and-Replace with Context

```typescript
interface Patch {
  file: string;
  old_string: string;
  new_string: string;
}

async function applyPatch(params: {
  patches: Patch[];
  dryRun?: boolean;
  validateSyntax?: boolean;
}): Promise<ApplyPatchResult> {
  const results: PatchResult[] = [];

  for (const patch of params.patches) {
    const result = await applySinglePatch(patch, params);
    results.push(result);

    // Stop on first failure (atomic behavior)
    if (!result.success) {
      return {
        success: false,
        results,
        error: `Patch failed at ${patch.file}: ${result.error}`,
      };
    }
  }

  return { success: true, results };
}

async function applySinglePatch(
  patch: Patch,
  options: { dryRun?: boolean; validateSyntax?: boolean },
): Promise<PatchResult> {
  try {
    // Step 1: Read file
    const filePath = path.resolve(patch.file);
    const originalContent = await fs.readFile(filePath, "utf-8");

    // Step 2: Find all occurrences of old_string
    const matches = findAllOccurrences(originalContent, patch.old_string);

    // Step 3: Validate match count
    if (matches.length === 0) {
      return {
        success: false,
        error: "String not found in file",
        matches: 0,
      };
    }

    if (matches.length > 1) {
      return {
        success: false,
        error: `Found ${matches.length} occurrences, expected exactly 1`,
        matches: matches.length,
        locations: matches,
      };
    }

    // Step 4: Apply replacement
    const newContent = originalContent.replace(patch.old_string, patch.new_string);

    // Step 5: Validate content changed
    if (newContent === originalContent) {
      return {
        success: false,
        error: "Content unchanged after replacement",
      };
    }

    // Step 6: Write atomically (dry run check)
    if (options.dryRun) {
      return { success: true, matches: 1, dryRun: true };
    }

    await atomicWrite(filePath, newContent);

    // Step 7: Optional syntax validation
    if (options.validateSyntax) {
      const syntaxValid = await validateSyntax(filePath);
      if (!syntaxValid) {
        // Rollback
        await atomicWrite(filePath, originalContent);
        return {
          success: false,
          error: "Syntax validation failed, rolled back",
        };
      }
    }

    return { success: true, matches: 1 };
  } catch (error) {
    return {
      success: false,
      error: error instanceof Error ? error.message : "Unknown error",
    };
  }
}
```

### Occurrence Finding Algorithm

```typescript
function findAllOccurrences(content: string, searchString: string): number[] {
  const locations: number[] = [];
  let index = 0;

  while (true) {
    const pos = content.indexOf(searchString, index);

    if (pos === -1) {
      break;
    }

    locations.push(pos);
    index = pos + searchString.length;
  }

  return locations;
}
```

**Complexity:** O(n\*m) where n=file length, m=search string length

**Optimization for large files:**

```typescript
function findAllOccurrencesOptimized(content: string, searchString: string): number[] {
  // Use regex for faster search on large files
  const escaped = searchString.replace(/[.*+?^${}()|[\]\\]/g, "\\$&");
  const regex = new RegExp(escaped, "g");
  const locations: number[] = [];

  let match: RegExpExecArray | null;
  while ((match = regex.exec(content)) !== null) {
    locations.push(match.index);
  }

  return locations;
}
```

## Atomic Write Strategy

### Write-To-Temp-Then-Rename

```typescript
async function atomicWrite(filePath: string, content: string): Promise<void> {
  const dir = path.dirname(filePath);
  const tempName = `.tmp-${Date.now()}-${randomUUID()}`;
  const tempPath = path.join(dir, tempName);

  try {
    // Step 1: Write to temporary file
    await fs.writeFile(tempPath, content, { encoding: "utf-8" });

    // Step 2: Rename (atomic on POSIX systems)
    await fs.rename(tempPath, filePath);
  } catch (error) {
    // Cleanup temp file on failure
    try {
      await fs.unlink(tempPath);
    } catch {
      // Ignore cleanup errors
    }
    throw error;
  }
}
```

**Why atomic?**

- Prevents partial writes on power failure
- Readers always see complete file state
- Rename is atomic on POSIX (same filesystem)

## Syntax Validation

### Language-Specific Validation

```typescript
async function validateSyntax(filePath: string): Promise<boolean> {
  const ext = path.extname(filePath).toLowerCase();

  switch (ext) {
    case ".ts":
    case ".tsx":
      return await validateTypeScript(filePath);

    case ".js":
    case ".jsx":
      return await validateJavaScript(filePath);

    case ".json":
      return await validateJson(filePath);

    case ".py":
      return await validatePython(filePath);

    case ".rs":
      return await validateRust(filePath);

    default:
      return true; // No validation for unknown types
  }
}
```

### TypeScript Validation

```typescript
async function validateTypeScript(filePath: string): Promise<boolean> {
  try {
    const { exec } = await import("child_process");
    const util = await import("util");
    const execAsync = util.promisify(exec);

    // Run TypeScript compiler in check mode
    await execAsync(`tsc --noEmit --skipLibCheck "${filePath}"`, {
      timeout: 10000, // 10s timeout
    });

    return true;
  } catch (error) {
    // TypeScript errors indicate syntax issues
    return false;
  }
}
```

### JSON Validation

```typescript
async function validateJson(filePath: string): Promise<boolean> {
  try {
    const content = await fs.readFile(filePath, "utf-8");
    JSON.parse(content);
    return true;
  } catch {
    return false;
  }
}
```

## Error Handling

### Error Categories

```typescript
enum PatchErrorCode {
  FILE_NOT_FOUND = "FILE_NOT_FOUND",
  STRING_NOT_FOUND = "STRING_NOT_FOUND",
  MULTIPLE_MATCHES = "MULTIPLE_MATCHES",
  NO_CHANGE = "NO_CHANGE",
  SYNTAX_ERROR = "SYNTAX_ERROR",
  WRITE_ERROR = "WRITE_ERROR",
  ROLLBACK_FAILED = "ROLLBACK_FAILED",
}

class PatchError extends Error {
  constructor(
    public code: PatchErrorCode,
    message: string,
    public patch: Patch,
    public locations?: number[],
  ) {
    super(message);
  }
}
```

### Error Recovery

```typescript
async function applyPatchWithRetry(
  patch: Patch,
  options: { maxRetries?: number },
): Promise<PatchResult> {
  const maxRetries = options.maxRetries ?? 3;

  for (let attempt = 1; attempt <= maxRetries; attempt++) {
    const result = await applySinglePatch(patch, {});

    if (result.success) {
      return result;
    }

    // Don't retry on certain errors
    if (result.code === PatchErrorCode.SYNTAX_ERROR) {
      return result; // Syntax errors won't fix themselves
    }

    if (result.code === PatchErrorCode.STRING_NOT_FOUND) {
      // File may have changed - reload and try fuzzy matching
      if (attempt < maxRetries) {
        await new Promise((r) => setTimeout(r, 100 * attempt));
        continue;
      }
    }

    return result;
  }

  return { success: false, error: "Max retries exceeded" };
}
```

## Fuzzy Matching (Advanced)

### Whitespace-Normalized Search

```typescript
function normalizeWhitespace(text: string): string {
  return text
    .replace(/\r\n/g, "\n") // Normalize line endings
    .replace(/[ \t]+/g, " ") // Collapse whitespace
    .trim();
}

function findFuzzyMatch(content: string, searchString: string): number[] {
  const normalizedContent = normalizeWhitespace(content);
  const normalizedSearch = normalizeWhitespace(searchString);

  // Find in normalized content
  const normalizedPos = normalizedContent.indexOf(normalizedSearch);

  if (normalizedPos === -1) {
    return [];
  }

  // Map back to original positions (approximate)
  // This is a simplification - real implementation needs character mapping
  return [normalizedPos];
}
```

### Line-Based Matching

```typescript
function findMatchByLines(
  content: string,
  searchString: string,
): Array<{ startLine: number; endLine: number; position: number }> {
  const contentLines = content.split("\n");
  const searchLines = searchString.split("\n");

  const matches: Array<{ startLine: number; endLine: number; position: number }> = [];

  // Sliding window search
  for (let i = 0; i <= contentLines.length - searchLines.length; i++) {
    const windowLines = contentLines.slice(i, i + searchLines.length);
    const windowText = windowLines.join("\n");

    if (windowText === searchString) {
      const position = contentLines.slice(0, i).join("\n").length + (i > 0 ? 1 : 0);
      matches.push({
        startLine: i,
        endLine: i + searchLines.length - 1,
        position,
      });
    }
  }

  return matches;
}
```

## Security Considerations

### Path Traversal Prevention

```typescript
function sanitizeFilePath(filePath: string, allowedRoot: string): string | null {
  // Resolve to absolute path
  const resolved = path.resolve(allowedRoot, filePath);

  // Ensure within allowed root
  if (!resolved.startsWith(allowedRoot)) {
    return null; // Path traversal attempt
  }

  // Block sensitive patterns
  const blockedPatterns = [
    /\/\.(env|git|ssh)/, // Hidden config
    /\/node_modules\//, // Dependencies
    /\/(?:etc|proc|dev)\//, // System directories
  ];

  for (const pattern of blockedPatterns) {
    if (pattern.test(resolved)) {
      return null;
    }
  }

  return resolved;
}
```

### File Size Limits

```typescript
const MAX_FILE_SIZE = 1024 * 1024; // 1MB

async function applySinglePatch(patch: Patch): Promise<PatchResult> {
  const stats = await fs.stat(patch.file);

  if (stats.size > MAX_FILE_SIZE) {
    return {
      success: false,
      error: `File too large (${stats.size} bytes, max: ${MAX_FILE_SIZE})`,
    };
  }

  // ... continue with patch
}
```

## Testing Strategy

### Unit Tests

```typescript
describe("applyPatch", () => {
  it("replaces single occurrence", async () => {
    const original = "const x = 1\nconst y = 2\n";
    const patch = {
      file: "/tmp/test.ts",
      old_string: "const x = 1",
      new_string: "const x = 10",
    };

    await fs.writeFile(patch.file, original);
    const result = await applyPatch({ patches: [patch] });

    expect(result.success).toBe(true);

    const modified = await fs.readFile(patch.file, "utf-8");
    expect(modified).toBe("const x = 10\nconst y = 2\n");
  });

  it("fails on multiple matches", async () => {
    const original = "const x = 1\nconst x = 1\n";
    const patch = {
      file: "/tmp/test.ts",
      old_string: "const x = 1",
      new_string: "const x = 10",
    };

    await fs.writeFile(patch.file, original);
    const result = await applyPatch({ patches: [patch] });

    expect(result.success).toBe(false);
    expect(result.error).toContain("Found 2 occurrences");
  });

  it("rolls back on syntax error", async () => {
    const original = "const x = 1\n";
    const patch = {
      file: "/tmp/test.ts",
      old_string: "const x = 1",
      new_string: "const x =  // invalid",
    };

    await fs.writeFile(patch.file, original);
    const result = await applyPatch({
      patches: [patch],
      validateSyntax: true,
    });

    expect(result.success).toBe(false);

    // Verify rollback
    const content = await fs.readFile(patch.file, "utf-8");
    expect(content).toBe(original);
  });
});
```

## Related Documentation

- [Runtime Execution](/docs/runtime/execution.md)
- [Tool Safety](/docs/tools/safety.md)
- [File Operations](/docs/tools/file-ops.md)