xpath.mjs

/**
 * The XPath of Processing-Model predicates and params: a subset, compiled once
 * to closures over xast. Anything outside it throws when the expression is
 * compiled, so a generator can fail on it and name the model.
 *
 * Paths: `.`, `..`, `@name`, `name`, `*`, `node()`, `text()`, the axes in AXES,
 * `/`, `//`, absolute paths and `[predicate]`. Operators: or, and, the general
 * (= != < <= > >=) and value (eq ne lt le gt ge) comparisons, + -, mod,
 * `if (…) then … else …`. Sequences `(a, b)`, string and number literals, and
 * the functions in FUNCTIONS, whose number of arguments is checked when compiled.
 *
 * A path gives each node once, in document order. A value comparison with more
 * than one item on a side throws when evaluated, as in XPath. Regular expressions
 * are JavaScript's.
 *
 * A name means what XSLT's xpath-default-namespace makes it mean: unprefixed, or
 * prefixed tei:, it is TEI's; another namespace is written Q{uri}local, which
 * readOdd makes of the ODD's prefixes. Any other prefix does not compile.
 *
 * A position is `{ node, up }`: the node and its ancestor elements, outermost
 * first. Attributes evaluate to their string values.
 */

/**
 * TEI as xast, the tree every renderer reads. An element's name is nameOf its
 * namespace and local name; an attribute of a namespace other than xml's is
 * keyed {uri}local, and namespace declarations are not attributes.
 * @typedef {{ type: "element", name: string, attributes: Record<string, string>, children: XastNode[] }} XastElement
 * @typedef {{ type: "text", value: string }} XastText
 * @typedef {{ type: "root", children: XastNode[] }} XastRoot
 * @typedef {XastElement | XastText | XastRoot} XastNode
 */
/**
 * A node where it stands; `i`, where known, is its index among its parent's element and text children.
 * @typedef {{ node: XastNode, up: XastElement[], i?: number }} Position
 */
/**
 * What an expression evaluates to: an item, or a sequence of them.
 * @typedef {Position | string | number | boolean} Item
 * @typedef {Item | Item[]} Value
 * @typedef {(pos: Position) => Value} Expression
 */

/** @type {(n: any) => n is XastElement} */
const isElement = (n) => n?.type === "element";
/** @type {(n: any) => n is XastText} */
const isText = (n) => n?.type === "text";
export const TEI_NS = "http://www.tei-c.org/ns/1.0";
/** An element's name: the local name in TEI's namespace, {uri}local in another, {}local in none. */
export const nameOf = (uri, local) => (uri === TEI_NS ? local : `{${uri}}${local}`);
const localName = (name = "") => name.replace(/^\{.*\}/, "");
const textOf = (n) => (isText(n) ? n.value : (n?.children ?? []).map(textOf).join(""));

/** @type {(item: unknown) => item is Position} */
export const isPos = (item) => typeof item === "object" && item !== null && "node" in item;
const atom = (item) => (isPos(item) ? textOf(item.node) : item);
/** @type {(v: Value) => Item[]} */
export const seq = (v) => (Array.isArray(v) ? v : [v]);
const normalizeSpace = (s) => s.replace(/[ \t\n\r]+/g, " ").replace(/^ | $/g, "");
const num = (v) => (typeof v === "number" ? v : Number(str(v)));

/** @type {(v: Value) => boolean} */
export const bool = (v) =>
  // A string in a sequence may be an attribute, whose node is always true.
  Array.isArray(v) ? (v.length === 1 && ["boolean", "number"].includes(typeof v[0]) ? bool(v[0]) : v.length > 0) : typeof v === "number" ? v !== 0 && !Number.isNaN(v) : Boolean(v);
/** The string value of the first item. @type {(v: Value) => string} */
export const str = (v) => (Array.isArray(v) ? (v.length ? String(atom(v[0])) : "") : String(v));

const COMPARE = {
  "=": (a, b) => a === b,
  "!=": (a, b) => a !== b,
  "<": (a, b) => a < b,
  "<=": (a, b) => a <= b,
  ">": (a, b) => a > b,
  ">=": (a, b) => a >= b,
};
const VALUE_COMPARE = { eq: "=", ne: "!=", lt: "<", le: "<=", gt: ">", ge: ">=" };

/** General comparison: true if any pair of items compares. */
function compare(op, a, b) {
  if (typeof a === "boolean" || typeof b === "boolean") return COMPARE[op](bool(a), bool(b));
  return seq(a).some((x) =>
    seq(b).some((y) => {
      const [p, q] = [atom(x), atom(y)];
      return typeof p === "number" || typeof q === "number" ? COMPARE[op](Number(p), Number(q)) : COMPARE[op](p, q);
    }),
  );
}

// Each parent's element and text children, and where each child stands among them.
const lists = new WeakMap();
const index = new WeakMap();
function nodesOf(parent) {
  let list = lists.get(parent);
  if (!list) {
    list = (parent.children ?? []).filter((n) => isElement(n) || isText(n));
    list.forEach((n, i) => index.set(n, i));
    lists.set(parent, list);
  }
  return list;
}
const kids = (p) => {
  const up = [...p.up, p.node];
  return nodesOf(p.node).map((node) => ({ node, up }));
};
const parent = (p) => (p.up.length ? [{ node: p.up.at(-1), up: p.up.slice(0, -1) }] : []);
const siblings = (p, after) => {
  if (!p.up.length) return [];
  const list = nodesOf(p.up.at(-1));
  const i = index.get(p.node);
  return (after ? list.slice(i + 1) : list.slice(0, i).reverse()).map((node) => ({ node, up: p.up }));
};
const descendants = (p) => kids(p).flatMap((k) => [k, ...descendants(k)]);
const ancestors = (p) => p.up.map((node, i) => ({ node, up: p.up.slice(0, i) })).reverse();
/** The document node above the outermost element, where an absolute path starts. */
const documentOf = (p) => ({ node: { type: "root", children: [p.up[0] ?? p.node] }, up: [] });

/** Where a node stands: its index under each of its ancestors, outermost first. */
const orderKey = ({ node, up }) => up.map((a, k) => (nodesOf(a), index.get(up[k + 1] ?? node)));
/** Each node once, in document order; attribute values are strings, in the order of their elements. */
function inOrder(items) {
  if (items.length < 2 || !isPos(items[0])) return items;
  const keyed = [...new Map(items.map((p) => [p.node, p])).values()].map((p) => [orderKey(p), p]);
  keyed.sort(([a], [b]) => {
    for (let k = 0; k < Math.max(a.length, b.length); k++) if (a[k] !== b[k]) return (a[k] ?? -1) - (b[k] ?? -1);
    return 0;
  });
  return keyed.map(([, p]) => p);
}

/** The axes, each in proximity order. */
const AXES = {
  self: (p) => [p],
  child: kids,
  parent,
  ancestor: ancestors,
  "ancestor-or-self": (p) => [p, ...ancestors(p)],
  descendant: descendants,
  "descendant-or-self": (p) => [p, ...descendants(p)],
  "preceding-sibling": (p) => siblings(p, false),
  "following-sibling": (p) => siblings(p, true),
  preceding: (p) => [p, ...ancestors(p)].flatMap((a) => siblings(a, false).flatMap((s) => [...descendants(s).reverse(), s])),
  following: (p) => [p, ...ancestors(p)].flatMap((a) => siblings(a, true).flatMap((s) => [s, ...descendants(s)])),
};

const REVERSE = ["parent", "ancestor", "ancestor-or-self", "preceding-sibling", "preceding"];

/** Position and size of the context in the predicate being evaluated. */
let focus = { position: 1, size: 1 };

/** Called without arguments, a function gets the context item. */
const FUNCTIONS = {
  position: () => focus.position,
  last: () => focus.size,
  exists: (v) => seq(v).length > 0,
  empty: (v) => seq(v).length === 0,
  "local-name": (v) => {
    const [item] = seq(v);
    return isPos(item) && isElement(item.node) ? localName(item.node.name) : "";
  },
  "string-length": (a) => [...str(a)].length,
  "ends-with": (a, b) => str(a).endsWith(str(b)),
  matches: (a, re, flags) => new RegExp(str(re), flags === undefined ? "" : str(flags)).test(str(a)),
  replace: (a, re, to, flags) => str(a).replace(new RegExp(str(re), `g${flags === undefined ? "" : str(flags)}`), str(to)),
  not: (v) => !bool(v),
  count: (v) => seq(v).length,
  concat: (...vs) => vs.map(str).join(""),
  contains: (a, b) => str(a).includes(str(b)),
  "contains-token": (a, t) => seq(a).some((i) => String(atom(i)).split(/[ \t\n\r]+/).includes(normalizeSpace(str(t)))),
  "starts-with": (a, b) => str(a).startsWith(str(b)),
  "normalize-space": (a) => normalizeSpace(str(a)),
  translate: (a, from, to) =>
    [...str(a)].map((c) => { const i = [...str(from)].indexOf(c); return i < 0 ? c : [...str(to)][i] ?? ""; }).join(""),
  string: (a) => str(a),
  true: () => true,
  false: () => false,
};

/** Arguments a function takes where they are not those it declares. */
const ARITY = {
  "local-name": [0, 1], "string-length": [0, 1], "normalize-space": [0, 1], string: [0, 1],
  matches: [2, 3], replace: [3, 4], concat: [2, Infinity],
};

const TOKEN = /\s*(?:'([^']*)'|"([^"]*)"|(\d+(?:\.\d+)?)|(::|\.\.|!=|<=|>=|[=<>()[\],@/.*+|-])|(Q\{[^}]*\}[A-Za-z_][\w.-]*|[A-Za-z_][\w.-]*(?::[A-Za-z_][\w.-]*)?))/y;

/**
 * Compile an expression to a function of a position; throws on anything outside
 * the subset. An error when evaluated names the expression and `at`, where it was written.
 * @param {string} expr
 * @param {string} [at]
 * @returns {Expression}
 */
export function xpath(expr, at) {
  const fail = (why) => {
    throw new Error(`XPath "${expr}": ${why}`);
  };

  const toks = [];
  for (let at = 0; at < expr.length; ) {
    TOKEN.lastIndex = at;
    const m = TOKEN.exec(expr);
    if (!m) {
      if (expr.slice(at).trim()) fail(`cannot read "${expr.slice(at).trim()}"`);
      break;
    }
    at = TOKEN.lastIndex;
    if (m[1] !== undefined || m[2] !== undefined) toks.push({ t: "str", v: m[1] ?? m[2] });
    else if (m[3]) toks.push({ t: "num", v: m[3] });
    else if (m[4]) toks.push({ t: "op", v: m[4] });
    else toks.push({ t: "name", v: m[5] });
  }

  let i = 0;
  const is = (v, t = "op") => toks[i]?.t === t && toks[i].v === v;
  const eat = (v, t = "op") => (is(v, t) ? (i++, true) : false);
  const expect = (v) => eat(v) || fail(`expected "${v}"`);
  const name = () => (toks[i]?.t === "name" ? toks[i++].v : fail("expected a name"));
  /** A name as the tree spells it. */
  const resolved = (n, attribute) => {
    const [, uri, local] = n.match(/^Q\{([^}]*)\}(.+)$/) ?? (n.startsWith("tei:") ? [n, TEI_NS, n.slice(4)] : []);
    if (local) return attribute ? `{${uri}}${local}` : nameOf(uri, local);
    return n.includes(":") && !(attribute && n.startsWith("xml:")) ? fail(`the namespace prefix of ${n} is not declared`) : n;
  };

  /** Keep the items a predicate admits: a number is a position, anything else a test. */
  const filter = (items, preds, outer) =>
    preds.reduce((list, pred) => {
      const saved = focus;
      const kept = list.filter((item, k) => {
        focus = { position: k + 1, size: list.length };
        const v = pred(isPos(item) ? item : outer);
        return typeof v === "number" ? v === k + 1 : bool(v);
      });
      focus = saved;
      return kept;
    }, items);
  const predicates = () => {
    const preds = [];
    while (eat("[")) {
      preds.push(or());
      expect("]");
    }
    return preds;
  };

  function or() {
    let left = and();
    while (eat("or", "name")) {
      const [a, b] = [left, and()];
      left = (p) => bool(a(p)) || bool(b(p));
    }
    return left;
  }
  function and() {
    let left = comparison();
    while (eat("and", "name")) {
      const [a, b] = [left, comparison()];
      left = (p) => bool(a(p)) && bool(b(p));
    }
    return left;
  }
  function comparison() {
    const left = additive();
    const word = Object.keys(VALUE_COMPARE).find((o) => is(o, "name"));
    const op = Object.keys(COMPARE).find((o) => is(o)) ?? VALUE_COMPARE[word];
    if (!op) return left;
    i++;
    const right = additive();
    const single = (v) => (seq(v).length > 1 ? fail(`${word} compares single items, not ${seq(v).length}`) : v);
    return word ? (p) => compare(op, single(left(p)), single(right(p))) : (p) => compare(op, left(p), right(p));
  }
  function additive() {
    let left = multiplicative();
    for (let op; (op = ["+", "-"].find((o) => is(o))); ) {
      i++;
      const [a, b] = [left, multiplicative()];
      left = op === "+" ? (p) => num(a(p)) + num(b(p)) : (p) => num(a(p)) - num(b(p));
    }
    return left;
  }
  function multiplicative() {
    let left = primary();
    while (eat("mod", "name")) {
      const [a, b] = [left, primary()];
      left = (p) => num(a(p)) % num(b(p));
    }
    return left;
  }

  /** A literal, a parenthesised sequence, a conditional, a function call — or a location path. */
  function primary() {
    const tok = toks[i] ?? fail("unexpected end");
    const call = tok.t === "name" && toks[i + 1]?.v === "(" && tok.v !== "node" && tok.v !== "text";
    let base;
    if (tok.t === "str" || tok.t === "num") {
      i++;
      const v = tok.t === "num" ? Number(tok.v) : tok.v;
      base = () => v;
    } else if (eat("(")) {
      const items = [];
      if (!is(")")) do items.push(or()); while (eat(","));
      expect(")");
      base = items.length === 1 ? items[0] : (p) => items.flatMap((f) => seq(f(p)));
    } else if (call && tok.v === "if") {
      i += 2;
      const test = or();
      expect(")");
      if (!eat("then", "name")) fail('expected "then"');
      const yes = or();
      if (!eat("else", "name")) fail('expected "else"');
      const no = or();
      base = (p) => (bool(test(p)) ? yes(p) : no(p));
    } else if (call) {
      const f = FUNCTIONS[tok.v] ?? fail(`unknown function ${tok.v}()`);
      i += 2;
      const args = [];
      if (!is(")")) do args.push(or()); while (eat(","));
      expect(")");
      const [min, max] = ARITY[tok.v] ?? [f.length, f.length];
      if (args.length < min || args.length > max) fail(`${tok.v}() cannot take ${args.length} argument(s)`);
      base = (p) => f(...(args.length ? args.map((a) => a(p)) : [[p]]));
    }
    if (!base) return path();
    const [inner, preds] = [base, predicates()];
    return preds.length ? (p) => filter(seq(inner(p)), preds, p) : inner;
  }

  /** Steps joined by `/`; `//` is `/descendant-or-self::node()/`, a leading `/` the document. */
  function path() {
    const absolute = is("/");
    const steps = absolute ? [] : [step()];
    while (eat("/")) {
      if (eat("/")) steps.push(AXES["descendant-or-self"]);
      steps.push(step());
    }
    return (p) => steps.reduce((ctx, s) => {
      const next = ctx.flatMap((c) => (isPos(c) ? s(c) : []));
      return ctx.length > 1 ? inOrder(next) : next;
    }, [absolute ? documentOf(p) : p]);
  }

  function step() {
    if (eat(".")) return (p) => [p];
    if (eat("..")) return parent;
    if (eat("@")) {
      const attr = resolved(name(), true);
      return (p) => {
        const v = isElement(p.node) ? p.node.attributes?.[attr] : undefined;
        return v == null ? [] : [v];
      };
    }
    let axis = "child";
    if (toks[i]?.t === "name" && toks[i + 1]?.v === "::") {
      axis = name();
      i++;
    }
    const move = AXES[axis] ?? fail(`unsupported axis ${axis}`);
    /** @type {(q: XastNode) => boolean} */
    let test = isElement;
    if (!eat("*")) {
      const n = name();
      if ((n === "node" || n === "text") && eat("(")) {
        expect(")");
        test = n === "node" ? () => true : (q) => isText(q);
      } else {
        const wanted = resolved(n, false);
        test = (q) => isElement(q) && q.name === wanted;
      }
    }
    const preds = predicates();
    // Predicates count in proximity order; the step gives its nodes in document order.
    return (p) => {
      const kept = filter(move(p).filter((q) => test(q.node)), preds, p);
      return REVERSE.includes(axis) ? [...kept].reverse() : kept;
    };
  }

  const root = or();
  if (i < toks.length) fail(`unexpected "${toks[i].v}"`);
  return (p) => {
    try {
      return root(p);
    } catch (/** @type {any} */ e) {
      throw new Error(`XPath "${expr}"${at ? ` (${at})` : ""}: ${e.message.replace(`XPath "${expr}": `, "")}`);
    }
  };
}