Working with ASTs

Parse, walk, change, print

An abstract syntax tree, or AST, is your code turned into nested objects, one for each part. The parsing lesson showed how a parser builds it. This lesson uses it the way tool authors do: to find code, check it and change it.

import { parse } from "acorn";

const code = "const total = price * 2;";
const ast = parse(code, { ecmaVersion: "latest" });
const declaration = ast.body[0];
console.log(declaration.type, declaration.kind);
console.log(declaration.declarations[0].id.name);
console.log(declaration.declarations[0].init.type, declaration.declarations[0].init.operator);

Line 4 parses the code into a tree. ecmaVersion: "latest" tells Acorn to accept every finished feature. Line 5 takes the first statement in the program's body.

Line 6 prints VariableDeclaration const: the node's type, and the keyword it used. Line 7 prints the name, total. Line 8 prints BinaryExpression *: the value is a calculation with *.

Reading a node: type, fields and positions

Every node has a type, such as CallExpression. Its other fields hold its parts, and some of those are nodes too. Acorn also gives each node start and end: where its text begins and ends in the code.

import { parse } from "acorn";

const code = 'greet("Ada");\nconsole.log("hi");';
const ast = parse(code, { ecmaVersion: "latest", locations: true });
const call = ast.body[1].expression;
console.log(call.type, call.start, call.end);
console.log(code.slice(call.start, call.end));
console.log(call.loc.start.line, call.loc.start.column);

Line 3 holds two lines of code. Line 4 parses them with locations: true, which adds line and column numbers. Line 5 takes the second statement, then its expression: an ExpressionStatement wraps every expression used as a statement.

Line 6 prints CallExpression 14 31. Counting from 0, the call starts at character 14, and end is the position just after its last character. So line 7, code.slice(call.start, call.end), prints exactly console.log("hi"). Line 8 prints 2 0: line 2, column 0. Lines count from 1 and columns from 0.

Positions are what let a tool point at your code: an editor's red underline, a linter's file.js:2:1, and the edits later in this lesson all come from them.

Parsers: Acorn, Babel, SWC and Oxc

ESTree is a shared description of what a JavaScript AST looks like. Not every parser follows it. Read each row of the table as: "this parser is written in this language, gives this format, and is used by these tools."

Rust parsers such as SWC and Oxc are much faster on big projects, which is why newer tools use them. But a different format matters as soon as you write code that checks node types.

// A check written for ESTree, the format Acorn gives.
function isString(node) {
  return node.type === "Literal" && typeof node.value === "string";
}

const fromAcorn = { type: "Literal", value: "tea", raw: '"tea"' };
const fromBabel = { type: "StringLiteral", value: "tea" };
console.log(isString(fromAcorn), isString(fromBabel));

Line 3 accepts a node only if its type is Literal, ESTree's name for a string. Line 6 is a string node from Acorn, and line 7 is the same string from @babel/parser. Line 8 prints true false: the check misses Babel's StringLiteral.

Read each row of the next table as: "for this part of the code, ESTree, Babel and SWC use these names."

So write your tool for the format your parser gives. Babel has an estree plugin that makes @babel/parser give ESTree nodes, for tools that expect them.

Visiting every node

To find something, a tool visits every node. A walker is a function that does that: it looks at a node, then at every node in its fields, and so on down. You can write one in a few lines.

import { parse } from "acorn";

function walk(node, depth = 0) {
  console.log("  ".repeat(depth) + node.type);
  for (const value of Object.values(node)) {
    const children = Array.isArray(value) ? value : [value];
    for (const child of children) {
      if (child && typeof child.type === "string") walk(child, depth + 1);
    }
  }
}

walk(parse("total(price, 2);", { ecmaVersion: "latest" }));

Line 4 prints the node's type, indented by its depth. Lines 5 and 6 go through every field, and treat a single value like a list of one. Line 8 walks any value that has a type: that is how it knows a field holds a node.

Line 13 starts the walk. It prints Program, then ExpressionStatement, then CallExpression, then three nodes for total, price and 2, each indented one level more than its parent.

1import { parse } from "acorn";2 3function walk(node, depth = 0) {4  console.log("  ".repeat(depth) + node.type);5  for (const value of Object.values(node)) {6    const children = Array.isArray(value) ? value : [value];7    for (const child of children) {8      if (child && typeof child.type === "string") walk(child, depth + 1);9    }10  }11}12 13walk(parse("total(price, 2);", { ecmaVersion: "latest" }));Run

Press Step and watch line 4 print each node before line 8 goes into its children. This replays the example code; it isn't a view inside the JavaScript engine.

Most tools don't walk by hand. They take a visitor: an object with one function for each node type you care about. acorn-walk, Babel and ESLint rules all work this way.

import { parse } from "acorn";
import { simple } from "acorn-walk";

const code = [
  "function add(a, b) { return a + b; }",
  "const double = (n) => n * 2;",
  "setTimeout(function () {}, 10);",
].join("\n");
const ast = parse(code, { ecmaVersion: "latest" });
const found = [];
simple(ast, {
  FunctionDeclaration(node) {
    found.push(node.id.name + ": " + node.params.length);
  },
  ArrowFunctionExpression(node) {
    found.push("arrow: " + node.params.length);
  },
  FunctionExpression(node) {
    found.push("function: " + node.params.length);
  },
});
console.log(found.join(", "));

Lines 4 to 8 hold three kinds of function. acorn-walk's simple, on line 11, calls the function named after each node's type. Lines 12, 15 and 18 handle the three kinds, and line 22 prints add: 2, arrow: 1, function: 0: each function and how many parameters it has.

Changing code at node positions

There are two ways to change code with an AST. You can change the tree and print all of it back as code, or you can use node positions to edit just those parts of the original text. Printing a whole tree often loses comments and spacing. Editing at positions keeps everything else exactly as it was.

import { parse } from "acorn";
import { simple } from "acorn-walk";

const code = "var cups = 2; // two cups\nvar tea = cups * 3;\nconsole.log(tea);";
const ast = parse(code, { ecmaVersion: "latest" });
const edits = [];
simple(ast, {
  VariableDeclaration(node) {
    if (node.kind === "var") edits.push({ start: node.start, end: node.start + 3, text: "let" });
  },
});
let output = code;
for (const edit of edits.sort((a, b) => b.start - a.start)) {
  output = output.slice(0, edit.start) + edit.text + output.slice(edit.end);
}
console.log(output);

Line 9 finds each var declaration and plans an edit: replace its first 3 characters with let. Lines 13 and 14 apply the edits to the text. Line 16 prints the code with let twice, and the comment // two cups is still there.

Line 13 sorts the edits so the last one comes first. That order matters whenever an edit changes the length of the text.

const code = "let cups = 2;\nconsole.log(cups);";
const edits = [{ start: 4, end: 8 }, { start: 26, end: 30 }];

function apply(list) {
  let text = code;
  for (const edit of list) text = text.slice(0, edit.start) + "cupCount" + text.slice(edit.end);
  return text;
}
console.log(apply(edits));
console.log(apply([...edits].reverse()));

Line 2 lists the positions of both cups. Line 9 applies them from the start: the first rename makes the text 4 characters longer, so position 26 now points at log(, and the second line prints console.cupCountcups);.

Line 10 applies them from the end. The later edit can't move the earlier position, so it prints the right code. Libraries such as magic-string, used by Rollup and Vite, keep track of this for you.

One more trap: a name is not a variable. Renaming every Identifier called cups changes far more than one variable.

import { parse } from "acorn";

function walk(node, visit) {
  visit(node);
  for (const value of Object.values(node)) {
    for (const child of Array.isArray(value) ? value : [value]) {
      if (child && typeof child.type === "string") walk(child, visit);
    }
  }
}

const code = [
  "let cups = 2;",
  "const order = { cups: 5 };",
  "function pour(cups) { return cups; }",
  "console.log(cups, order.cups);",
].join("\n");
const ast = parse(code, { ecmaVersion: "latest", locations: true });
const lines = [];
walk(ast, (node) => {
  if (node.type === "Identifier" && node.name === "cups") lines.push(node.loc.start.line);
});
console.log(lines.length, lines.join(" "));

Lines 3 to 10 are a walker that calls visit on every node. Line 23 prints 6 1 2 3 3 4 4: six identifiers, on lines 1, 2, 3, 3, 4 and 4 of the code. Only two of them are the cups variable from line 1.

The one on line 2 is a property name, and so is the second one on line 4. The two on line 3 are a different variable, the parameter of pour. Real rename tools use scope analysis to tell them apart; the scope analysis lesson explains how.

Exploring trees with AST Explorer

Before you write a check, you need to know what the tree looks like. AST Explorer is a website for exactly that: paste code, pick a parser, and see its tree. The parsing lesson has a live explorer built with Acorn too.

Read each row of the table as: "do this in AST Explorer, and this happens."

The usual way to work: type an example of the code you want to find, click on it, and copy the shape you see into your check.

import { parse } from "acorn";

function isConsoleLog(node) {
  return (
    node.type === "CallExpression" &&
    node.callee.type === "MemberExpression" &&
    !node.callee.computed &&
    node.callee.object.type === "Identifier" &&
    node.callee.object.name === "console" &&
    node.callee.property.name === "log"
  );
}

for (const line of ["console.log(1);", "logger.log(1);", "console.error(1);"]) {
  const call = parse(line, { ecmaVersion: "latest" }).body[0].expression;
  console.log(line, isConsoleLog(call));
}

Lines 5 to 10 check the shape AST Explorer shows for console.log(1): a CallExpression whose callee is a MemberExpression, with console before the dot and log after it. Line 7 rules out console["log"], where the name is computed.

Lines 14 to 16 try three lines. Only console.log(1); prints true: logger.log has the wrong object, and console.error the wrong property.

Build small tools

Each tool in the playground is a few lines of the code from this lesson: parse with Acorn, visit with acorn-walk, and edit the text at node positions. Pick a tool, then change the code and watch the results change.

Try typing var in another line, or a second ==. Then break the code, for example by deleting a ): no tool can run until the code parses.

Some rules of thumb for your own tools:

• Pick a parser that reads your files. Plain Acorn reads neither JSX nor TypeScript; @babel/parser, typescript-eslint's parser, SWC and Oxc read both.
• Find the shape in AST Explorer first, with the same parser your tool uses.
• Edit text at positions to keep comments and formatting, and apply edits from the end.
• Check what you change: parse the output again, and run your tests.

Common mix-ups

Most mix-ups come from treating the tree as if it were the text, or one parser's tree as everyone's.

• "Parentheses are nodes." No. They only decide the tree's shape. (tax + 1) is a BinaryExpression, with no node for the brackets.
• "Renaming means changing every Identifier with that name." No. Property names and other variables can share the name.
• "Every parser gives the same tree." No. Babel and SWC have their own formats.
• "Parsing runs the code." No. A parser only reads the text. That is why tools can safely read code they don't trust.
• "To change code, print the whole tree again." You can, but it often loses comments and spacing. Editing at positions keeps them.

The table below puts three of these side by side. Read each row as: "people often think this, but this is true."

Practice exercises

Each exercise reads or changes a real tree. Guess first, then run it.

import { parse } from "acorn";

const ast = parse("price * (tax + 1);", { ecmaVersion: "latest" });
const top = ast.body[0].expression;
console.log(top.type, top.operator, top.right.type, top.right.operator);

import { parse } from "acorn";

const ast = parse("price * (tax + 1);", { ecmaVersion: "latest" });
const top = ast.body[0].expression;
console.log(top.type, top.operator, top.right.type, top.right.operator);

const code = 'const greeting = "hi " + name;';
const node = { type: "BinaryExpression", start: 17, end: 29 };
console.log(code.slice(node.start, node.end));

const code = 'const greeting = "hi " + name;';
const node = { type: "BinaryExpression", start: 17, end: 29 };
console.log(code.slice(node.start, node.end));

import { parse } from "acorn";

function isConsoleCall(node) {
  return (
    node.type === "CallExpression" &&
    node.callee.type === "MemberExpression" &&
    node.callee.object.name === "console" &&
    node.callee.property.name === "log"
  );
}

const lines = ["console.log(1);", "console.error(2);", "logger.log(3);", "console.warn(4);"];
const found = lines.filter((line) => isConsoleCall(parse(line, { ecmaVersion: "latest" }).body[0].expression));
console.log(found.length);

import { parse } from "acorn";

function isConsoleCall(node) {
  return (
    node.type === "CallExpression" &&
    node.callee.type === "MemberExpression" &&
    node.callee.object.name === "console"
  );
}

const lines = ["console.log(1);", "console.error(2);", "logger.log(3);", "console.warn(4);"];
const found = lines.filter((line) => isConsoleCall(parse(line, { ecmaVersion: "latest" }).body[0].expression));
console.log(found.length);

const code = "let sum = price * 2;";
const edits = [
  { start: 4, end: 7, text: "total" },
  { start: 10, end: 15, text: "cost" },
];
let output = code;
for (const edit of edits) {
  output = output.slice(0, edit.start) + edit.text + output.slice(edit.end);
}
console.log(output);

const code = "let sum = price * 2;";
const edits = [
  { start: 4, end: 7, text: "total" },
  { start: 10, end: 15, text: "cost" },
];
let output = code;
for (const edit of [...edits].sort((a, b) => b.start - a.start)) {
  output = output.slice(0, edit.start) + edit.text + output.slice(edit.end);
}
console.log(output);

import { parse } from "acorn";
import { simple } from "acorn-walk";

const code = "if (count == 0) reset();\nif (name != null) greet(name);";
const ast = parse(code, { ecmaVersion: "latest" });
const edits = [];
simple(ast, {
  BinaryExpression(node) {
    // Find == or != between node.left.end and node.right.start, and add an edit.
  },
});
let output = code;
for (const edit of edits.sort((a, b) => b.start - a.start)) {
  output = output.slice(0, edit.start) + edit.text + output.slice(edit.end);
}
console.log(output);

import { parse } from "acorn";
import { simple } from "acorn-walk";

const code = "if (count == 0) reset();\nif (name != null) greet(name);";
const ast = parse(code, { ecmaVersion: "latest" });
const edits = [];
simple(ast, {
  BinaryExpression(node) {
    if (node.operator !== "==" && node.operator !== "!=") return;
    const between = code.slice(node.left.end, node.right.start);
    const start = node.left.end + between.indexOf(node.operator);
    edits.push({ start, end: start + 2, text: node.operator + "=" });
  },
});
let output = code;
for (const edit of edits.sort((a, b) => b.start - a.start)) {
  output = output.slice(0, edit.start) + edit.text + output.slice(edit.end);
}
console.log(output);

import { parse } from "acorn";
import { simple } from "acorn-walk";

const code = ["function add(a, b) { return a + b; }", "const double = (n) => n * 2;"].join("\n");
const ast = parse(code, { ecmaVersion: "latest" });
const names = [];
simple(ast, {
  FunctionDeclaration(node) {
    names.push(node.id.name);
  },
});
console.log(names.join(" "));

import { parse } from "acorn";
import { simple } from "acorn-walk";

const code = ["function add(a, b) { return a + b; }", "const double = (n) => n * 2;"].join("\n");
const ast = parse(code, { ecmaVersion: "latest" });
const names = [];
simple(ast, {
  FunctionDeclaration(node) {
    names.push(node.id.name);
  },
  VariableDeclarator(node) {
    if (node.init && node.init.type === "ArrowFunctionExpression") names.push(node.id.name);
  },
});
console.log(names.join(" "));

Check your understanding

For each question, picture the tree: which nodes there are, what is in their fields, and where their text is. Each answer explains why it's right or wrong.

Key takeaways

Once code is a tree, a few lines of JavaScript can find, check and change it exactly.

• Tools parse code into an AST, walk it, change it, and print code back.
• Every node has a type and fields; Acorn adds start and end positions.
• Acorn and Oxc give ESTree. Babel and SWC have their own formats, so write checks for your parser's format.
• A walker visits every node; a visitor gives you one function per node type.
• Edit the text at node positions, from the end, to keep comments and formatting.
• A name is not a variable: renaming needs scope analysis.

Coming next: Codemods and Babel plugins. They use these same steps to change code across a whole codebase.