Document Object Model Concept

The previous lesson passed over the tree-building stage in one sentence: a token stream is turned into a tree. This lesson opens that sentence. The tree is not an intermediate product in processing the document, it is the actual product: style is applied to it, layout is computed over it, scripts read and change it. The source text is never used again once the tree is built.

This tree’s name is the Document Object Model — DOM for short. The name says two things at once: it is a model of the document (not the source text itself, but a structured representation built from it), and it is made of objects (every node is a unit that can be queried and changed).

Why a Tree

The Tree Terminology lesson in the Data Structures course defined a tree as a structure where every node has a single parent and ordered children. The structure markup produces is exactly this, because markup itself is nested: an element is either entirely inside another element or entirely outside it. Partial overlap — half of an element being inside, half outside — is not defined.

This constraint is what makes tracking nesting with a stack possible. The Stacks lesson in the Data Structures course defined last-in-first-out behavior; the tree builder uses exactly this: an opened element is placed on the stack, a closed element is taken off the stack, a new node always becomes the child of the element sitting at the top of the stack.

The Building Algorithm

The script below implements the core of the algorithm that builds a tree from a token stream. Two rules have been added to the previous lesson’s tokenizer: void elements are not put on the stack, and some elements close on their own when another element is opened.

// tree.mjs — builds a node tree from a token stream
const VOID_TAG = new Set(["br", "hr", "img", "input", "link", "meta"]);
const CLOSES = { li: ["li"], p: ["p"], h1: ["p"], div: ["p"], ul: ["p"] };

function tokenize(text) {
  const tokens = [];
  let i = 0;
  while (i < text.length) {
    const k = text.indexOf("<", i);
    if (k === -1) { tokens.push({ kind: "text", value: text.slice(i) }); break; }
    if (k > i) tokens.push({ kind: "text", value: text.slice(i, k) });
    const end = text.indexOf(">", k);
    const inner = text.slice(k + 1, end);
    if (inner.startsWith("!")) tokens.push({ kind: "doctype", value: inner.slice(1) });
    else if (inner.startsWith("/")) tokens.push({ kind: "closing", name: inner.slice(1).toLowerCase() });
    else {
      const space = inner.search(/[\s/]/);
      tokens.push({ kind: "opening", name: (space === -1 ? inner : inner.slice(0, space)).toLowerCase() });
    }
    i = end + 1;
  }
  return tokens;
}

function buildTree(text) {
  const root = { kind: "document", name: "#document", children: [] };
  const stack = [root];
  const top = () => stack[stack.length - 1];
  for (const token of tokenize(text)) {
    if (token.kind === "text") {
      if (token.value.trim() === "") continue;
      top().children.push({ kind: "text", value: token.value.trim(), children: [] });
    } else if (token.kind === "opening") {
      while (stack.length > 1 && (CLOSES[token.name] ?? []).includes(top().name)) stack.pop();
      const node = { kind: "element", name: token.name, children: [] };
      top().children.push(node);
      if (!VOID_TAG.has(token.name)) stack.push(node);
    } else if (token.kind === "closing") {
      const position = stack.map((d) => d.name).lastIndexOf(token.name);
      if (position > 0) stack.length = position;
    }
  }
  return root;
}

function write(node, depth = 0) {
  const indent = "  ".repeat(depth);
  if (node.kind === "text") console.log(`${indent}"${node.value}"`);
  else console.log(`${indent}${node.name}`);
  for (const child of node.children) write(child, depth + 1);
}

function count(node, counter = { element: 0, text: 0, depth: 0 }, depth = 0) {
  if (node.kind === "element") counter.element += 1;
  if (node.kind === "text") counter.text += 1;
  counter.depth = Math.max(counter.depth, depth);
  for (const child of node.children) count(child, counter, depth + 1);
  return counter;
}

const source = `<!doctype html>
<html>
<head><title>North Slope Station</title></head>
<body>
<h1>North Slope Station</h1>
<p>At an elevation of 1840 meters above sea level.
<ul>
<li>Temperature
<li>Relative humidity
</ul>
</body>
</html>`;

const tree = buildTree(source);
write(tree);
console.log("---");
console.log(count(tree));

#document
  html
    head
      title
        "North Slope Station"
    body
      h1
        "North Slope Station"
      p
        "At an elevation of 1840 meters above sea level."
      ul
        li
          "Temperature"
        li
          "Relative humidity"
---
{ element: 9, text: 5, depth: 5 }

The source text has no closing tag for the p element, and neither of the two li elements do. In the tree, though, all three are closed and stand in the correct place. What achieves this is the CLOSES table: when ul is opened, an open p closes; when li is opened, an open li closes. These rules are not an optional convenience, they are part of the language’s definition; every parser applies the same ones.

Node Types

Three kinds of node appear in the output above, and a fourth sits at the document’s root.

The document node is the tree’s root. It corresponds to no element; it is the handle for the whole tree.

Element nodes are produced from opening tags. They have a name, attributes, and ordered children.

Text nodes are produced from the characters between tags. They have no children; they are the tree’s leaves. The five text nodes in the count above correspond to the document’s five pieces of text.

Comment nodes (the <!-- ... --> form) stay in the document and are not painted. Scripts can read them; information embedded in markup should not be assumed hidden.

In the count, the element: 9 value corresponds to the nine opening tags in the source text. depth: 5 is the number of edges crossed from the root to the farthest leaf: document → html → body → ul → li → text node.

Elements Not Present in the Source Text

In the example above, the html, head, and body elements were written in the source text. Had they not been written, they would still be in the tree. This is the most concrete consequence of the tag–element distinction established in the previous lesson: not every element in the tree has a tag in the source text.

There is a reverse consequence too: not every tag in the source text corresponds to an element in the tree. A closing tag with no matching opening is ignored; in the algorithm above, this is what doing nothing when the lastIndexOf call returns -1 corresponds to.

This disconnect running in both directions explains why validating a document cannot be done by looking at the source text. The question to ask is not “what did I write,” it is “what got built.”

Void Elements

Some elements cannot have content, and for this reason have no closing tag: br, hr, img, input, link, meta, and a few more. These are called void elements. In the algorithm, these elements are never placed on the stack at all; they are added to the tree as a child and the top of the stack does not change.

For void elements, a closing form written as <br/> is accepted by the parser but has no effect; the element is already empty. For a non-void element, the same form — <div/>, for example — does not do what might be expected: the element does not close, content continues to flow into it.

The Tree Is a Living Structure

The tree does not freeze once it is built. Scripts can add nodes, remove them, change their attributes; every change reruns the relevant part of the style and layout stages. This is why a page’s tree at a given moment and the source text that came from the server can differ: the source text describes the initial state, the tree describes the state at that moment.

No script will be written in this course; but knowing that written markup is directly turned into a data structure is the foundation for later courses. Writing markup is not typesetting text, it is declaring a tree.

Summary

• The Document Object Model is the node tree built from the token stream; style, layout, and scripts apply not to the source text but to this tree.
• The tree builder uses a stack: an opened element goes onto the stack, a closed element comes off, a new node becomes the child of the element sitting at the top of the stack.
• Some elements with no written closing tag close on their own when another element opens; these rules are part of the language’s definition.
• There are four node types: document, element, text, and comment. Comment nodes are not painted but stay in the document.
• The source text and the tree do not map onto each other one to one: elements that are not written can appear in the tree, and some written tags may never enter the tree at all.
• Void elements cannot have content and are never placed on the stack; a closing form has no effect on them and is misleading on a non-void element.

Next Step

This lesson showed how the tree is built from the document’s text and assumed parsing proceeds without interruption. In reality, a document refers to other resources beyond itself: style files, scripts, images. These references appear while parsing is under way, and some of them halt parsing. The next lesson examines, through an event timeline, which resource holds up which stage, and how this changes depending on where it is written in the document.