Every editor has a "format XML" button, and it feels like magic — paste a minified wall of angle brackets, get back a clean, indented tree. It is not magic, and it is definitely not a regex. I built one with no library, and the whole engine is a two-pass pipeline where the single most useful data structure — a stack — does the indentation and the validation at the same time.
XML is a tree written as flat text
That is the one mental shift that makes everything click. Every <tag> opens a branch and every </tag> closes it, so the nesting of the tags is the shape of the data. A minified document hides that shape by dropping the whitespace, but the tree is still encoded in the tags. Formatting is just recovering the shape and drawing it back with indentation; validating is confirming the branches close in the right order.
Pass one: tokenize
You cannot indent a document you have not broken into pieces, so the first pass is a single left-to-right scan that turns the raw string into an ordered array of tokens — each one tagged with a kind:
{ kind:"open"|"close"|"self"|"text"|"comment"|"cdata"|"decl", name, attrStr, raw, pos }
This pass stays deliberately dumb: it does not build the tree or check nesting, it just labels each atom in source order. When the scanner hits <, it classifies the markup by its prefix — <!-- is a comment (runs to -->), <![CDATA[ is raw data (runs to ]]>), <? is a declaration, <! is a doctype, anything else is a real element. Each special kind has its own terminator, and a missing terminator is already a clean, precise error.
The bug that separates a toy from a real formatter
Finding where a tag ends looks like indexOf(">") — until an attribute value contains one, like <rule expr="a > b"/>. A blind search stops inside the quotes and splits the tag in the wrong place, corrupting everything after it. The fix is a tiny state machine that ignores any > inside a quoted string:
function findTagEnd(s, start){
let quote = null;
for (let j = start + 1; j < s.length; j++){
const c = s[j];
if (quote){ if (c === quote) quote = null; } // leaving a quoted value
else if (c === '"' || c === "'") quote = c; // entering one
else if (c === ">") return j; // a REAL tag end
}
return -1; // unterminated
}
Five lines, and it is the exact difference between a demo that works on clean examples and something that survives real data with URLs, comparison operators, and JSON stuffed into attributes.
Pass two: walk with a depth stack
This is the heart of it. Keep a stack of open tags and an integer depth. An open tag prints at the current depth, pushes, and increments. A close tag must match the name on top of the stack:
if (t.kind === "close"){
if (!stack.length)
throw new XmlError("Unexpected </" + t.name + "> — nothing is open", ...);
const open = stack[stack.length - 1];
if (open.name !== t.name)
throw new XmlError("Mismatched: <" + open.name + "> open, found </" + t.name + ">", ...);
stack.pop(); depth = Math.max(0, depth - 1);
}
That one stack answers three questions at once: how deep to indent (its height), whether a close is legal (does the top match), and whether the document is complete (is it empty at the end — anything left over is unclosed). Indentation is then trivial: the line prefix is the indent unit repeated depth times. You get the validator for free, and it can name the exact offender — "this </title> should have been </price>" — which a browser's DOMParser cannot.
A small cosmetic touch: when an open tag is immediately followed by a single text token and its own close, a two-token lookahead collapses <name>John</name> onto one line instead of sprawling it across three.
Minify is the same tokens, inverted
The elegant payoff is that minify is not a second parser. It reuses the identical token list and emits it with the opposite layout policy — concatenate the tags back-to-back and drop the whitespace-only text between them (text inside a leaf is preserved because it can be meaningful):
for (const t of tokenize(xml)){
if (t.kind === "text"){ const x = t.raw.trim(); if (x) out += x; }
else out += emitTag(t); // tags back-to-back, no newlines
}
One tokenize() feeds two tiny emitters, so Format and Minify are provably consistent inverses of structure.
The lesson generalizes well beyond XML: pretty-printing anything nested is lex, then walk with a stack, and that stack doubles as your correctness check. It is the same shape real parsers and compilers use.
Paste something messy, hit the "broken" sample to watch it name the offending tag, and flip to Minify:
https://dev48v.infy.uk/solve/day34-xml-formatter.html
Top comments (0)