markz
On this page

AST

The flat, read-only document markz parses into. A node is an index; its type, range and tree links live in parallel typed arrays, and the few node types that carry data keep it in a side table. The parser fills a Builder, which hands over a Document once and is done: there is no mutation API, so offsets can never drift from the source they point into (design: AST).

import { NAMED } from "./chars";
import { WARNINGS, type WarningCode } from "./warnings";

#Node types

T is the one list of node types. Its keys are the public string names and its values the internal numeric codes stored in the type array, in the same order, so the name table below is just its keys. The list is the spec's node list, no more.

export const T = {
  document: 0,
  metadata: 1,
  comment: 2,
  heading: 3,
  paragraph: 4,
  text: 5,
  emphasis: 6,
  strong: 7,
  delete: 8,
  link: 9,
  image: 10,
  code: 11,
  inlineCode: 12,
  blockquote: 13,
  list: 14,
  listItem: 15,
  thematicBreak: 16,
  break: 17,
  table: 18,
  tableRow: 19,
  tableCell: 20,
  element: 21,
  math: 22,
  raw: 23,
  expression: 24,
} as const;

/** A node type's name, like `"heading"`. */
export type NodeType = keyof typeof T;

const NAMES = Object.keys(T) as NodeType[];

/** A node is its index. `NONE` stands for a missing parent, child or sibling. */
export type NodeId = number;
/** No node: the parent of the root, or a child or sibling that isn't there. */
export const NONE: NodeId = -1;

/** A half-open range of UTF-16 offsets into the parsed source. */
export interface Range {
  start: number;
  end: number;
}

#Node data

What each node type carries beyond its range and links. Strings that a node may lack are null rather than empty, because the output distinguishes them ([a](b "") has a title). Values that are decoded or stripped of container prefixes (> inside a blockquote) are stored as strings; everything else is a range, so the source stays the one copy of the text.

export interface NodeData {
  /** The object, and the range of the lines between the `---` fences. */
  metadata: { value: MetadataObject; range: Range };
  heading: { depth: 1 | 2 | 3 | 4 | 5 | 6; id: string; idExplicit: boolean };
  /** Decoded text; the node's range covers the raw characters. */
  text: { value: string };
  link: Destination & { autolink: boolean };
  image: Destination & { alt: string };
  code: { lang: string | null; meta: string | null; value: string; body: Range };
  inlineCode: { value: string };
  list: { ordered: boolean; start: number; tight: boolean };
  /** `null` for an ordinary item, a boolean for a GFM task item. */
  listItem: { checked: boolean | null };
  table: { align: Align[] };
  /**
   * An element Markdown has no syntax for, named by `@name`: inline (a span, which is `span` when
   * it has no name), a leaf, whose `[label]` is its children, or a container holding blocks.
   */
  element: { kind: "inline" | "leaf" | "container"; name: string };
  math: { block: boolean; value: string; range: Range };
  /** A ` ```=format ` fence; `value` is its content. */
  raw: { format: string; value: string; range: Range };
  /**
   * `${…}`; `code` is what is between the braces, read as the paragraph reads its lines: joined
   * by `\n`, each trimmed, as inline math keeps its TeX. `range` is the code in the source.
   */
  expression: { code: string; range: Range };
}

/** A metadata value YAML can hold on one line. */
export type MetadataScalar = string | number | boolean | null;
/** A metadata value: a scalar, or a list of scalars. */
export type MetadataValue = MetadataScalar | readonly MetadataScalar[];
/** The metadata block's keys and values. Keys are flat, and may hold a `.`. */
export interface MetadataObject {
  readonly [key: string]: MetadataValue;
}

/** Where a link or an image points, and its title. */
export interface Destination {
  destination: string;
  title: string | null;
  destinationRange: Range;
  /** `${…}` inside the destination. */
  expressions: Range[];
}

/** A table column's alignment, or `null` when it has none. */
export type Align = "left" | "center" | "right" | null;

/** The node types that carry data, and so the ones `Document.data` accepts. */
export type DataType = keyof NodeData;

#Attributes

A {…} block, wherever it is allowed, becomes an Attributes in a second side table, so the common case costs one empty slot. #id and .class are stored under the keys id and class, each item with its own range, in source order: the renderer applies "classes accumulate, a later value wins" and the AST stays verbatim.

export interface Attributes extends Range {
  items: Attribute[];
}

/** One item of a `{…}` block, like `.note` or `lang=en`, with its range. */
export interface Attribute extends Range {
  key: string;
  value: string;
}

#Warnings

A warning is syntax markz kept as text or read in its own way: a stable code from warnings.ts, its range, what was wrong, and the supported form to write instead.

export interface Warning extends Range {
  code: WarningCode;
  message: string;
  instead: string;
}

#Document

The read-only view consumers get from parse. Accessors take a node and read one array slot, so a walk allocates nothing but the generator children returns. Node ids are only meaningful for the document that produced them and are not bounds-checked. data checks the type it is asked for, which keeps a wrong guess from reading another type's fields as if they were its own.

export class Document {
  readonly source: string;
  readonly root: NodeId = 0;
  readonly warnings: readonly Warning[];
  readonly #store: Store;

  /** @internal Documents come from `parse`; the constructor is not public API. */
  constructor(source: string, store: Store, warnings: readonly Warning[]) {
    this.source = source;
    this.#store = store;
    this.warnings = warnings;
  }

  /** The number of nodes. Ids run from 0 (the root) to `size - 1`, parents before children. */
  get size(): number {
    return this.#store.type.length;
  }

  type(node: NodeId): NodeType {
    return NAMES[this.#store.type[node]!]!;
  }

  start(node: NodeId): number {
    return this.#store.start[node]!;
  }

  end(node: NodeId): number {
    return this.#store.end[node]!;
  }

  parent(node: NodeId): NodeId {
    return this.#store.parent[node]!;
  }

  firstChild(node: NodeId): NodeId {
    return this.#store.firstChild[node]!;
  }

  nextSibling(node: NodeId): NodeId {
    return this.#store.nextSibling[node]!;
  }

  *children(node: NodeId): Generator<NodeId, void, undefined> {
    const { firstChild, nextSibling } = this.#store;
    for (let child = firstChild[node]!; child !== NONE; child = nextSibling[child]!) yield child;
  }

  data<K extends DataType>(node: NodeId, type: K): Readonly<NodeData[K]> {
    if (this.#store.type[node] !== T[type]) {
      throw new TypeError(`node ${node} is a ${this.type(node)}, not a ${type}`);
    }
    return this.#store.data[node] as NodeData[K];
  }

  attributes(node: NodeId): Readonly<Attributes> | undefined {
    return this.#store.attributes[node];
  }

  /** The metadata object, which can only be the root's first child. */
  get metadata(): MetadataObject | undefined {
    const first = this.firstChild(this.root);
    return first !== NONE && this.type(first) === "metadata"
      ? this.data(first, "metadata").value
      : undefined;
  }
}

/** @internal The arrays behind a `Document`, all `size` long. */
export interface Store {
  type: Uint8Array;
  start: Int32Array;
  end: Int32Array;
  parent: Int32Array;
  firstChild: Int32Array;
  nextSibling: Int32Array;
  data: unknown[];
  attributes: (Attributes | undefined)[];
}

#Builder

How the parser writes the tree. It keeps a stack of open nodes: open starts a child of the innermost one and makes it innermost, close sets its end and pops it, and leaf adds a finished child. Children are appended through a lastChild array that only the builder has, so appending is constant time and the document doesn't carry the extra column. Arrays grow by doubling from a guess based on the source length, which leaves room for dense documents. finish closes the root at the end of the source and copies each array down to its nodes. A view would keep the whole guess alive, which on real documents is several times the nodes (Lessons).

type DataArgs<K extends NodeType> = K extends DataType ? [data: NodeData[K]] : [];

export class Builder {
  readonly #source: string;
  #size = 0;
  #type: Uint8Array;
  #start: Int32Array;
  #end: Int32Array;
  #parent: Int32Array;
  #firstChild: Int32Array;
  #nextSibling: Int32Array;
  #lastChild: Int32Array;
  readonly #data: unknown[] = [];
  readonly #attributes: (Attributes | undefined)[] = [];
  readonly #warnings: Warning[] = [];
  readonly #open: NodeId[] = [];

  /** The root starts at `start`, which is 1 when the source begins with a BOM. */
  constructor(source: string, start = 0) {
    this.#source = source;
    const capacity = Math.max(16, source.length >> 3);
    this.#type = new Uint8Array(capacity);
    this.#start = new Int32Array(capacity);
    this.#end = new Int32Array(capacity);
    this.#parent = new Int32Array(capacity);
    this.#firstChild = new Int32Array(capacity);
    this.#nextSibling = new Int32Array(capacity);
    this.#lastChild = new Int32Array(capacity);
    this.#open.push(this.#add(T.document, start, source.length, NONE, undefined));
  }

  /** The innermost open node. */
  get current(): NodeId {
    return this.#open[this.#open.length - 1]!;
  }

  open<K extends NodeType>(type: K, start: number, ...data: DataArgs<K>): NodeId {
    const node = this.#add(T[type], start, start, this.current, data[0]);
    this.#open.push(node);
    return node;
  }

  close(end: number): NodeId {
    if (this.#open.length === 1) throw new Error("the root is closed by finish()");
    const node = this.#open.pop()!;
    this.#end[node] = end;
    return node;
  }

  leaf<K extends NodeType>(type: K, start: number, end: number, ...data: DataArgs<K>): NodeId {
    return this.#add(T[type], start, end, this.current, data[0]);
  }

  /** Data that is only known once a node's content has been read, such as a list's tightness. */
  setData<K extends DataType>(node: NodeId, type: K, data: NodeData[K]): void {
    if (this.#type[node] !== T[type]) throw new TypeError(`node ${node} is not a ${type}`);
    this.#data[node] = data;
  }

  /** Named character references in the values stay as written, and are reported, as elsewhere. */
  setAttributes(node: NodeId, attributes: Attributes): void {
    this.#attributes[node] = attributes;
    for (const item of attributes.items) {
      for (const m of this.#source.slice(item.start, item.end).matchAll(NAMED)) {
        const at = item.start + m.index;
        this.warn("named-reference", at, at + m[0].length, `named character reference \`${m[0]}\``);
      }
    }
  }

  /** A warning by its code; the message defaults to the code's, and `instead` is always its. */
  warn(code: WarningCode, start: number, end: number, message?: string, instead?: string): void {
    const [text, fix] = WARNINGS[code];
    this.#warnings.push({ code, start, end, message: message ?? text, instead: instead ?? fix });
  }

  finish(): Document {
    if (this.#open.length !== 1) throw new Error(`${this.#open.length - 1} nodes left open`);
    const n = this.#size;
    const store: Store = {
      type: this.#type.slice(0, n),
      start: this.#start.slice(0, n),
      end: this.#end.slice(0, n),
      parent: this.#parent.slice(0, n),
      firstChild: this.#firstChild.slice(0, n),
      nextSibling: this.#nextSibling.slice(0, n),
      data: this.#data,
      attributes: this.#attributes,
    };
    // A paragraph's inline warnings are found when it closes, after later block ones.
    this.#warnings.sort((a, b) => a.start - b.start);
    return new Document(this.#source, store, this.#warnings);
  }

  #add(type: number, start: number, end: number, parent: NodeId, data: unknown): NodeId {
    const node = this.#size++;
    if (node === this.#type.length) this.#grow();
    this.#type[node] = type;
    this.#start[node] = start;
    this.#end[node] = end;
    this.#parent[node] = parent;
    this.#firstChild[node] = NONE;
    this.#nextSibling[node] = NONE;
    this.#lastChild[node] = NONE;
    this.#data.push(data);
    this.#attributes.push(undefined);
    if (parent !== NONE) {
      const last = this.#lastChild[parent]!;
      if (last === NONE) this.#firstChild[parent] = node;
      else this.#nextSibling[last] = node;
      this.#lastChild[parent] = node;
    }
    return node;
  }

  #grow(): void {
    const grow = <A extends Uint8Array | Int32Array>(a: A): A => {
      const b = new (a.constructor as new (n: number) => A)(a.length * 2);
      b.set(a);
      return b;
    };
    this.#type = grow(this.#type);
    this.#start = grow(this.#start);
    this.#end = grow(this.#end);
    this.#parent = grow(this.#parent);
    this.#firstChild = grow(this.#firstChild);
    this.#nextSibling = grow(this.#nextSibling);
    this.#lastChild = grow(this.#lastChild);
  }
}