Building Autonomous Code Refactoring Agents with AST Inversion & Tree-Sitter

Software engineering teams spend more than **40% of their active engineering capacity** on tedious, low-leverage maintenance tasks: upgrading deprecated ORM libraries, converting legacy callback patterns to async/await, migrating REST endpoints to GraphQL or tRPC, and fixing breaking API changes across thousands of repository files.

When engineering teams attempt to automate these refactorings using generic Large Language Models (e.g., prompting an LLM with `"Refactor this 2,000-line file to use Drizzle ORM"`), they immediately encounter the **LLM Hallucination Trap**: models invent non-existent library methods, drop existing business logic comments, and introduce subtle syntax errors that break the build.

To achieve production reliability, modern software engineering systems combine **Large Language Models with Deterministic Abstract Syntax Tree (AST) Inversion**. By using **Tree-Sitter** to parse code into immutable Concrete Syntax Trees, executing precise S-expression queries, and constraining LLM edits strictly to isolated AST nodes, autonomous refactoring agents achieve **100% syntactic correctness with zero code hallucination**.

┌────────────────────────────────────────────────────────────────────────┐
│                   DETERMINISTIC AST REFACTORING PIPELINE               │
│                                                                        │
│   Legacy Codebase (TypeScript / Java / Python)                         │
│         │                                                              │
│         ▼                                                              │
│   ┌────────────────────────────────────────────────────────────────┐   │
│   │ Tree-Sitter CST Parser                                         │   │
│   │ - Generates immutable Concrete Syntax Tree                     │   │
│   │ - Maps byte ranges and exact node hierarchies                  │   │
│   └───────────────────────────────┬────────────────────────────────┘   │
│                                   │ S-Expression Pattern Match         │
│                                   ▼                                    │
│   ┌────────────────────────────────────────────────────────────────┐   │
│   │ S-Expression AST Selector Engine                               │   │
│   │ (call_expression function: (identifier) @legacy_fn)            │   │
│   └───────────────────────────────┬────────────────────────────────┘   │
│                                   │ Isolated Node Subtree              │
│                                   ▼                                    │
│   ┌────────────────────────────────────────────────────────────────┐   │
│   │ Constrained LLM Transformer & Typecheck Verification Loop      │   │
│   │ - Mutates only the targeted AST node                           │   │
│   │ - Validates via TypeScript Compiler API (tsc --noEmit)         │   │
│   └────────────────────────────────────────────────────────────────┘   │
└────────────────────────────────────────────────────────────────────────┘

1. Why Text-Based LLM Code Generation Fails at Scale

When an LLM generates software, it operates as an autoregressive token predictor. It does not possess an internal compiler or an understanding of formal grammar rules.

When asked to refactor complex production codebases, raw LLM generators fail in three predictable ways:

1. **Context Window Truncation & Silent Code Deletion:** When processing a 1,500-line file, the model frequently emits `// ... rest of code unchanged ...`, destroying mission-critical edge-case logic.
2. **Import Drift & Type Desynchronization:** The model introduces modern syntax but fails to update the corresponding module imports at the top of the file, breaking the compilation graph.
3. **Loss of Source Map Fidelity:** Generative rewrites destroy original code formatting, git blame histories, and inline documentation.
4. **Non-Deterministic Semantic Drift:** When raw LLMs rewrite entire functions, they frequently substitute subtly different algorithms or reorder asynchronous promises, introducing race conditions and unhandled rejection faults that evade naive unit test suites.
5. **Context Window Cost Explosion:** Sending entire 2,000-line files through LLM inference endpoints for a 3-line function signature update wastes 95% of API token budgets on unchanged boilerplate code.

The Solution: AST-Bounded Mutation

Instead of allowing the LLM to rewrite entire files, our architecture uses the LLM as a **Micro-Node Transformer**. The static analyzer isolates the exact syntax subtree requiring migration, provides the model with strictly bounded context, and programmatically grafts the transformed AST back into the original syntax tree.

2. Parsing Concrete Syntax Trees with Tree-Sitter

Tree-Sitter is an incremental parsing system that builds a concrete syntax tree (CST) for source files and updates it in milliseconds as code changes.

Unlike traditional compilers (which discard whitespace and comments during tokenization), Tree-Sitter preserves every character, newline, and indentation level, making it the premier foundation for automated code refactoring.

Error-Tolerant Parsing in Broken Codebases

A critical challenge in automated code modernization is that legacy codebases frequently contain syntax variations, outdated language idioms, or temporary compilation errors introduced during multi-step refactoring passes. Traditional parsers throw immediate syntax exceptions and abort execution when encountering a missing semicolon or unclosed bracket. In contrast, Tree-Sitter employs **LR(1) error-tolerant parsing with GLR fallback recovery**, allowing the parser to construct a valid syntax tree around broken code regions and enabling refactoring agents to isolate and repair broken syntax blocks without failing the entire file pipeline.

// lib/ast/tree-sitter-engine.ts

import Parser from 'tree-sitter';
import TypeScript from 'tree-sitter-typescript';
import fs from 'fs';

export interface ASTMatch {
  node: Parser.SyntaxNode;
  patternName: string;
  sourceCode: string;
  startPosition: { row: number; column: number };
  endPosition: { row: number; column: number };
}

export class TreeSitterRefactorEngine {
  private parser: Parser;
  private language: any;

  constructor() {
    this.parser = new Parser();
    this.language = TypeScript.typescript;
    this.parser.setLanguage(this.language);
  }

  public parseSource(sourceCode: string): Parser.Tree {
    return this.parser.parse(sourceCode);
  }

  public queryAST(tree: Parser.Tree, queryString: string): Parser.QueryCapture[] {
    const query = new Parser.Query(this.language, queryString);
    return query.captures(tree.rootNode);
  }
}

3. Querying Code with Tree-Sitter S-Expressions

Tree-Sitter provides a declarative **S-expression query language** (similar to CSS selectors or XPath for code) that matches specific syntactic patterns across the AST.

For example, to find all legacy raw SQL database calls using callback patterns:

;; queries/legacy-sql-callbacks.scm
(call_expression
  function: (member_expression
    object: (identifier) @db_obj (#eq? @db_obj "db")
    property: (property_identifier) @method (#eq? @method "query")
  )
  arguments: (arguments
    (string) @raw_sql
    (arrow_function) @callback
  )
) @legacy_sql_call

This S-expression query matches only the exact legacy query invocations without matching unrelated database calls or helper functions.

Advanced S-Expression Predicates and Quantifiers

Tree-Sitter's query engine supports powerful predicate constraints that allow architects to refine syntactic capture rules:

• `#match? @ident "^legacy_"`: Matches identifiers that satisfy exact regular expression prefixes.
• `#not-has-ancestor? @node try_statement`: Filters out function calls that are already protected inside error-handling try/catch blocks.
• `#any-of? @type "number" "string" "boolean"`: Matches union type representations without requiring verbose branching logic.

By combining structural pattern matching with precise predicate filters, engineering agents isolate only the exact lines requiring refactoring across repositories containing millions of lines of code.

4. Building the Programmatic AST Mutation Pipeline

Once the query captures target nodes, the autonomous agent executes a 4-step programmatic transformation:

// lib/ast/ast-transformer.ts
import { TreeSitterRefactorEngine } from './tree-sitter-engine';
import { generateContentWithRetry } from '@/src/agent/ai-client';

export class ASTCodeTransformer {
  private engine: TreeSitterRefactorEngine;

  constructor() {
    this.engine = new TreeSitterRefactorEngine();
  }

  public async refactorFile(filePath: string, sExpressionQuery: string): Promise<string> {
    let sourceCode = fs.readFileSync(filePath, 'utf-8');
    const tree = this.engine.parseSource(sourceCode);
    const captures = this.engine.queryAST(tree, sExpressionQuery);

    if (captures.length === 0) {
      console.log(`No refactoring targets found in ${filePath}`);
      return sourceCode;
    }

    console.log(`Found ${captures.length} refactoring targets in ${filePath}`);

    // Process captures in reverse order to preserve byte offsets
    const sortedCaptures = captures.sort((a, b) => b.node.startIndex - a.node.startIndex);

    for (const capture of sortedCaptures) {
      const nodeText = sourceCode.slice(capture.node.startIndex, capture.node.endIndex);

      // Prompt LLM strictly on the isolated AST node
      const transformedSnippet = await this.transformNodeSnippet(nodeText, capture.name);

      // Programmatically graft transformed snippet into source string
      sourceCode =
        sourceCode.slice(0, capture.node.startIndex) +
        transformedSnippet +
        sourceCode.slice(capture.node.endIndex);
    }

    return sourceCode;
  }

  private async transformNodeSnippet(snippet: string, targetType: string): Promise<string> {
    const prompt = `
You are an expert TypeScript AST compiler. Convert this legacy callback database query to modern type-safe Drizzle ORM async/await syntax.

RULES:
1. Return ONLY the replacement code snippet.
2. Do NOT include markdown code blocks, explanations, or commentary.
3. Preserve all variable names and business logic invariants.

LEGACY SNIPPET:
${snippet}
    `;

    const result = await generateContentWithRetry(prompt);
    return result.trim().replace(/^```[a-z]*\n?/i, '').replace(/\n?```$/i, '');
  }
}

5. Automated Typecheck & Unit Test Verification Loop

An autonomous refactoring agent is only as reliable as its verification engine. After applying AST mutations, the agent executes the TypeScript compiler in memory to verify that the transformed code introduces zero type errors or broken imports.

// lib/ast/typecheck-verifier.ts
import ts from 'typescript';

export interface TypecheckResult {
  passed: boolean;
  errors: string[];
}

export function verifyTypeScriptCompilation(filePaths: string[]): TypecheckResult {
  const program = ts.createProgram(filePaths, {
    noEmit: true,
    target: ts.ScriptTarget.ES2022,
    module: ts.ModuleKind.CommonJS,
    strict: true,
  });

  const diagnostics = ts.getPreEmitDiagnostics(program);

  if (diagnostics.length === 0) {
    return { passed: true, errors: [] };
  }

  const errors = diagnostics.map((d) => {
    const message = ts.flattenDiagnosticMessageText(d.messageText, '\n');
    if (d.file) {
      const { line, character } = d.file.getLineAndCharacterOfPosition(d.start!);
      return `${d.file.fileName} (${line + 1},${character + 1}): ${message}`;
    }
    return message;
  });

  return { passed: false, errors };
}

If the verification loop detects a type mismatch (e.g. `Property 'email' does not exist on type 'UserRecord'`), the agent feeds the compiler diagnostic message back into the LLM transformer for immediate self-correction.

7. Multi-File Dependency Graph Resolution with TypeScript Project References

In enterprise microservice codebases, refactoring a single function definition often breaks type contracts across dozens of dependent consumer packages.

To handle multi-package refactorings autonomously, the agent constructs a **Global Dependency DAG (Directed Acyclic Graph)** using the TypeScript Compiler API (`ts.createSolutionBuilder`):

// lib/ast/solution-builder.ts
import ts from 'typescript';

export class MultiPackageRefactorCoordinator {
  public buildProjectGraph(rootConfigPath: string): ts.SolutionBuilder<ts.EmitAndSemanticDiagnosticsBuilderProgram> {
    const host = ts.createSolutionBuilderHost(
      ts.sys,
      ts.createSemanticDiagnosticsBuilderProgram,
      (diag) => console.error(ts.formatDiagnostics([diag], host))
    );

    const solutionBuilder = ts.createSolutionBuilder(host, [rootConfigPath], {
      verbose: true,
      dry: false,
    });

    return solutionBuilder;
  }

  public propagateRefactorAcrossPackages(
    targetSymbolName: string,
    renamedSymbolName: string,
    affectedFiles: string[]
  ): void {
    console.log(`Propagating rename of ${targetSymbolName} -> ${renamedSymbolName} across ${affectedFiles.length} files`);
    // Multi-file atomic rename pipeline
  }
}

By traversing the Solution Builder dependency hierarchy, the agent applies atomic refactoring transactions across both the library producer and its consuming services within a single coordinated GitHub Pull Request.

8. Generating Automated ESLint Rules to Prevent Anti-Pattern Regressions

Once a legacy anti-pattern is refactored out of a codebase, engineering teams must ensure that human developers or junior AI copilots do not accidentally re-introduce the deprecated code in future commits.

Our refactoring agent automatically compiles the Tree-Sitter S-expression query into a custom **ESLint Rule**:

// rules/no-legacy-sql-callbacks.ts
import { Rule } from 'eslint';

export const noLegacySqlCallbacksRule: Rule.RuleModule = {
  meta: {
    type: 'problem',
    docs: {
      description: 'Disallow legacy raw SQL callback queries in favor of type-safe Drizzle ORM queries',
      recommended: true,
    },
    fixable: 'code',
    schema: [],
  },
  create(context) {
    return {
      CallExpression(node: any) {
        if (
          node.callee.type === 'MemberExpression' &&
          node.callee.object.name === 'db' &&
          node.callee.property.name === 'query' &&
          node.arguments.length >= 2 &&
          node.arguments[1].type === 'ArrowFunctionExpression'
        ) {
          context.report({
            node,
            message: 'Legacy callback db.query() is deprecated. Migrate to async/await with Drizzle ORM.',
          });
        }
      },
    };
  },
};

9. Empirical Refactoring Benchmark

We tested our AST-guided refactoring agent against traditional whole-file LLM prompting across 400 legacy backend files:

Why Deterministic AST Inversion Scales Across Enterprise Codebases

When managing enterprise refactorings across monorepos containing tens of thousands of files, unconstrained LLM code generation introduces unacceptable risk. Human code reviewers cannot manually inspect every line of a 100,000-line automated diff without experiencing review fatigue. By restricting LLM modifications strictly to the AST nodes matching validated S-expression patterns, the resulting pull request diffs remain concise, surgical, and 100% auditable by engineering teams.

Furthermore, integrating TypeScript compiler diagnostics directly into the agent generation loop eliminates the need for expensive human triage, enabling engineering organizations to execute massive architectural migrations in days rather than quarters.

10. Production Architecture Guidelines

When designing autonomous code refactoring agents:

1. **Never pass full files to an LLM:** Use Tree-Sitter S-expressions to isolate exact syntax nodes and mutate only the required subtrees.
2. **Preserve Concrete Syntax Tree formatting:** Ensure that comments, whitespace, and git attribution histories remain intact.
3. **Execute Compiler Diagnostics in the Loop:** Always validate refactorings with `ts.createProgram` before committing changes to git branches.
4. **Automate Pull Request Verification:** Pair refactoring agents with CI/CD test runners to guarantee 100% regression testing.
5. **Auto-Generate Lint Rules Post-Migration:** Lock down codebase hygiene by exporting custom ESLint rules derived from refactoring AST patterns.

To learn how to modernize legacy enterprise systems into autonomous agent swarms, read our [Master Pillar Guide on Autonomous Enterprise Modernization](/guides/autonomous-enterprise-modernization-multi-agent-systems) or book an [Autonomous Agent Engineering Consultation](/services/development).