Structural Parsing

The source of the previous lesson’s data was an interface designed for the party that receives its data: the field names were inside the response, and the page limit was declared. Part of the data, however, does not stand behind such an interface; it stands inside the structure of a page arranged for human eyes. There are no field names there; only position and appearance markers say which part of the record is where.

The lesson’s measure is this: when the structure of the page changes, how many selectors break, how many rows drop, and how many rows survive having been read from the wrong field. The real question of the measure is not the number itself but whether the break is heard. The technical question is not enough on its own here either: collecting data from a page by scraping, without the source’s terms of use and an explicit access permission, is a legal and professional problem even if it is technically possible; here a permitted collection is assumed, and fields carrying personal data were never put on the page.

• DC15. The page is fiction and is modeled with node: the document tree is built in memory, and no network call is made. The running code is not a collection tool; it only parses, verifies, and counts. It is a model.
• DC16. The page publishes the set of the previous two lessons — 1,877 reading rows, 38,690.7 m³.
• DC17. The four structure versions carry the same data, and their layout changes: Y0 is the base, Y1 puts the table into a wrapper layer, Y2 inserts a column, Y3 renews the presentation layer.
• DC18. A selector is counted as broken in two cases: if it matches no node, or if the column position that has to be resolved from the header text cannot be found.
• DC19. The threshold for counting two readings as the same is 0.05 m³, because the page publishes values with one decimal and a difference below that can only come from rounding.

The Structure of the Page

// page.mjs — the document tree of a fictional public publication page and a small
// selector engine. IT IS A MODEL: there is no network call, the page is built in memory
// and publishes the same 1877 reading rows. Four structure versions carry the same
// data, and their layout changes.
export const SEED = 4711;
const rng = (t) => { let s = t >>> 0;
  return () => { s = (Math.imul(s, 1103515245) + 12345) >>> 0; return s / 4294967296; }; };
const r = rng(SEED);
export const REGION = ["north", "east", "central", "south", "west"];
export const RECORDS = [];
for (let i = 0; i < 1877; i++) {           // first the first period of 1400 subscribers, then 477 second
  const n = i < 1400 ? i : i - 1400, deci = 50 + Math.floor(r() * 321);
  RECORDS.push({ subscriber_no: 10000 + n, period: i < 1400 ? "2024-01" : "2024-02", deci,
    previous: 50 + ((deci * 37 + 11) % 321), region: REGION[n % 5] });
}
export const recordId = (k) => `${k.subscriber_no}-${k.period}`;
export const m3 = (d) => d / 10;

// Node: { tag, props, children }; children is either an array of nodes or a text.
const d = (tag, props, children) => ({ tag, props, children });
export const text = (n) => (typeof n.children === "string" ? n.children
  : n.children.map(text).join(""));
const childrenOf = (n) => (Array.isArray(n.children) ? n.children : []);
const descendants = (n) => childrenOf(n).flatMap((c) => [c, ...descendants(c)]);

// Selector language: space = any descendant level, ">" = direct child.
// Step form: tag, .class, [name=value] or a combination of these.
const part = (p) => {
  const m = /^([\w-]*)(?:\.([\w-]+))?(?:\[([\w-]+)=([\w-]+)\])?$/.exec(p);
  return { tag: m[1], cls: m[2], attr: m[3], value: m[4] };
};
const matches = (n, t) => (!t.tag || n.tag === t.tag)
  && (!t.cls || (n.props.class ?? "") === t.cls)
  && (!t.attr || n.props[t.attr] === t.value);
export function find(root, selector) {
  let nodes = [root], direct = false;
  for (const p of selector.trim().split(/\s+/)) {
    if (p === ">") { direct = true; continue; }
    const t = part(p);
    nodes = nodes.flatMap((n) => (direct ? childrenOf(n) : descendants(n)).filter((x) => matches(x, t)));
    direct = false;
  }
  return nodes;
}

// Y0 is the base; Y1 puts the table into a wrapper layer; Y2 inserts a "previous_m3"
// column; Y3 renews the presentation: class names change to generated names and
// the header of the reading column is renamed.
export function page(version) {
  const extra = version === "Y2", renewed = version === "Y3";
  const cn = (a) => (renewed ? { summary: "b-7f2", total: "b-91c", row: "b-4ad" }[a] : a);
  const header = extra ? ["subscriber_no", "period", "previous_m3", "reading_m3", "region"]
    : ["subscriber_no", "period", renewed ? "usage_m3" : "reading_m3", "region"];
  const cells = (k) => (extra ? [k.subscriber_no, k.period, m3(k.previous), m3(k.deci), k.region]
    : [k.subscriber_no, k.period, m3(k.deci), k.region])
    .map((v) => d("cell", {}, String(v)));
  const table = d("table", {}, [
    d("header", {}, [d("row", {}, header.map((b) => d("cell", {}, b)))]),
    d("body", {}, RECORDS.map((k) => d("row",
      { class: cn("row"), "data-kind": "reading" }, cells(k)))),
  ]);
  const total = RECORDS.reduce((t, k) => t + m3(k.deci), 0).toFixed(1);
  return d("page", {}, [
    d("summary", { class: cn("summary") }, [d("p", { class: cn("total") },
      `Total: ${total} m3`)]),
    d("section", {}, [version === "Y1" ? d("wrapper", { class: "box" }, [table]) : table]),
  ]);
}

if (import.meta.url === `file://${process.argv[1]}`) {
  console.log(`seed ${SEED}; page publishes ${RECORDS.length} reading rows, total ` +
    `${RECORDS.reduce((t, k) => t + m3(k.deci), 0).toFixed(1)} m3`);
  const y = (h) => h.map((v, j) => (j ? String(v).padStart([0, 8, 8, 52, 32][j])
    : String(v).padEnd(8))).join("");
  console.log(y(["version", "nodes", "rows", "column headers", "first data row"]));
  for (const s of ["Y0", "Y1", "Y2", "Y3"]) {
    const k = page(s), rows = find(k, "body > row");
    console.log(y([s, descendants(k).length, rows.length,
      find(k, "header row cell").map(text).join(","),
      find(rows[0], "cell").map(text).join(",")]));
  }
}

seed 4711; page publishes 1877 reading rows, total 38690.7 m3
version    nodes    rows                                      column headers                  first data row
Y0          9396    1877              subscriber_no,period,reading_m3,region          10000,2024-01,18,north
Y1          9397    1877              subscriber_no,period,reading_m3,region          10000,2024-01,18,north
Y2         11274    1877  subscriber_no,period,previous_m3,reading_m3,region     10000,2024-01,30.1,18,north
Y3          9396    1877                subscriber_no,period,usage_m3,region          10000,2024-01,18,north

What the four versions have in common does not show in the second column from the right: the number of data rows is 1,877 in all four. The published record set did not change at all. What changed is the node count and the column layout. Y1 adds a single node to the page (from 9,396 to 9,397), Y2 adds a cell to every row and raises the node count to 11,274, Y3 adds no node and changes only the texts.

None of these three changes corrupts the data. Y1 may have been made to put the view in a box, Y2 to publish one more column, Y3 to renew the presentation; all three are ordinary maintenance work from the point of view of the side that publishes the page. The structure of the page is not a contract, and the publishing side has no obligation to tell anyone. What the parser attaches itself to is exactly this contractless surface.

The last column shows why Y2 is special. The cells of the first row are now 10000,2024-01,30.1,18,north: the third cell holds not 18 but 30.1, and 30.1 also looks like a reading value. Because the new column is numeric and in the same range, a parser that takes the third cell to be the reading finds a valid number.

What Breaks When the Structure Changes

// parse.mjs — two selector sets read the same page. A1 relies on position: a path and
// a fixed column order. A2 relies on meaning: the row is found by a data marker, the
// column by the header text. What is measured is how many selectors broke when the
// structure changed and how many rows dropped or survived having been read from the wrong field.
import { page, find, text, RECORDS, recordId, m3, REGION } from "./page.mjs";

const A1 = { name: "A1 positional", row: "section > table > body > row", total: "summary > p",
  columns: () => ({ subscriber: 0, period: 1, reading: 2, region: 3 }) };
const A2 = { name: "A2 semantic", row: "row[data-kind=reading]", total: ".summary .total",
  columns: (root) => {
    const b = find(root, "header row cell").map(text);
    return { subscriber: b.indexOf("subscriber_no"), period: b.indexOf("period"),
      reading: b.indexOf("reading_m3"), region: b.indexOf("region") };
  } };

// Threshold 0.05 m3: readings are published with one decimal, and a difference
// below that can only come from rounding.
const THRESHOLD = 0.05;
const TRUTH = new Map(RECORDS.map((k) => [recordId(k), m3(k.deci)]));
const TARGET = RECORDS.reduce((t, k) => t + m3(k.deci), 0);

function extract(root, a) {
  const broken = [], rows = find(root, a.row), totals = find(root, a.total);
  if (rows.length === 0) broken.push(a.row);
  if (totals.length === 0) broken.push(a.total);
  const k = a.columns(root);
  for (const [name, i] of Object.entries(k)) if (i < 0) broken.push(`column:${name}`);
  const out = [];
  for (const s of rows) {
    const h = find(s, "cell").map(text), reading = Number(h[k.reading]);
    if (!Number.isFinite(reading)) continue;         // silently dropped row
    out.push({ id: `${h[k.subscriber]}-${h[k.period]}`, reading, region: h[k.region] });
  }
  const reported = totals.length ? Number(/[\d.]+/.exec(text(totals[0]))[0]) : null;
  return { broken, out, reported };
}

const y = (h) => h.map((v, j) => (j > 1 ? String(v).padStart([0, 0, 8, 9, 10, 9, 7, 11, 10][j])
  : String(v).padEnd(j ? 14 : 8))).join("");
console.log(y(["version", "parser", "broken", "rows in", "rows out", "dropped", "wrong",
  "total m3", "reported"]));
const results = {};
for (const version of ["Y0", "Y1", "Y2", "Y3"]) {
  const root = page(version);
  for (const a of [A1, A2]) {
    const r = results[version + a.name] = extract(root, a);
    const t = r.out.reduce((s, x) => s + x.reading, 0);
    const wrong = r.out.filter((x) => !(Math.abs((TRUTH.get(x.id) ?? -1) - x.reading) < THRESHOLD));
    console.log(y([version, a.name, r.broken.length, RECORDS.length, r.out.length,
      RECORDS.length - r.out.length, wrong.length, t.toFixed(1),
      r.reported === null ? "-" : r.reported.toFixed(1)]));
  }
}
const y1a = results["Y1A1 positional"], y2a = results["Y2A1 positional"], y3b = results["Y3A2 semantic"];
console.log(`\nIn Y1 a single layer was added and the path selector of A1, ${y1a.broken[0]}, found no ` +
  `rows: all ${RECORDS.length} rows dropped, the failure is loud`);
const t2 = y2a.out.reduce((s, x) => s + x.reading, 0);
console.log(`In Y2 A1 has no broken selector, ${y2a.out.length} records came out and none ` +
  `dropped; but because the columns shifted by one the total deviated by ${(t2 - TARGET).toFixed(1)} m3 and ` +
  `the region field of ${y2a.out.filter((x) => !REGION.includes(x.region)).length} records is not a region ` +
  `name`);
console.log(`In Y2 the difference between the ${y2a.reported.toFixed(1)} m3 the page itself reports and the ` +
  `${t2.toFixed(1)} m3 A1 computes is ${Math.abs(t2 - y2a.reported).toFixed(1)} ` +
  `m3, ${Math.round(Math.abs(t2 - y2a.reported) / THRESHOLD)} times the ${THRESHOLD} m3 threshold`);
console.log(`In Y3 ${y3b.broken.length} selectors of A2 broke (${y3b.broken.join(", ")}) and the ` +
  `records out are ${y3b.out.length}; in the same version A1 lost nothing`);

version parser          broken  rows in  rows out  dropped  wrong   total m3  reported
Y0      A1 positional        0     1877      1877        0      0    38690.7   38690.7
Y0      A2 semantic          0     1877      1877        0      0    38690.7   38690.7
Y1      A1 positional        1     1877         0     1877      0        0.0   38690.7
Y1      A2 semantic          0     1877      1877        0      0    38690.7   38690.7
Y2      A1 positional        0     1877      1877        0   1877    38630.6   38690.7
Y2      A2 semantic          0     1877      1877        0      0    38690.7   38690.7
Y3      A1 positional        0     1877      1877        0      0    38690.7   38690.7
Y3      A2 semantic          2     1877         0     1877      0        0.0         -

In Y1 a single layer was added and the path selector of A1, section > table > body > row, found no rows: all 1877 rows dropped, the failure is loud
In Y2 A1 has no broken selector, 1877 records came out and none dropped; but because the columns shifted by one the total deviated by -60.1 m3 and the region field of 1877 records is not a region name
In Y2 the difference between the 38690.7 m3 the page itself reports and the 38630.6 m3 A1 computes is 60.1 m3, 1202 times the 0.05 m3 threshold
In Y3 2 selectors of A2 broke (.summary .total, column:reading) and the records out are 0; in the same version A1 lost nothing

In the base structure, both sets produce the same set: 1,877 records, zero dropped, zero wrong, 38,690.7 m³. Two parsers that give the same result are not the same parser, and the difference can be measured only when the structure changes.

In the Y1 row there is one layer, one selector, and 1,877 rows. The single wrapper node that came in between invalidated the four-step path selector of A1, because section > table asks for a direct child and the table is now a grandchild of section. The number of broken selectors is 1, the dropped rows 1,877. This loss is loud: the records out are zero, and not noticing it would require running no check at all. The row selector of A2, row[data-kind=reading], looks for the marker and not the path, so it finds 1,877 rows on the same page.

Y2 is the lesson’s main finding. None of the selectors of A1 broke: the path is in place, all four indexes are within bounds, 1,877 records came out, and none dropped. But because the columns shifted by one, the previous period’s reading came into the reading field, and all 1,877 records carry a wrong value. The total is 38,630.6 m³, that is, in fact only 60.1 m³, 0.16%, away. A threshold, a magnitude check, a glance asking “is it plausible” lets this number through. The region field, meanwhile, now carries the reading value: the region field of 1,877 records is not even a region name. The number of broken selectors does not measure the damage — when that number was 1 in Y1, not a single wrong value was produced; when it was 0 in Y2, not a single correct value was produced.

Y3 turns the direction of the same problem around. When the presentation was renewed, the class-based total selector and the header-text-based reading column of A2 broke together: 2 broken selectors, zero records out. A1, which relies on position, lost nothing in the same version, because neither the class name nor the header text matters to it. Semantic selectors are not more durable; they depend on other things, and which set will hold depends on which direction the structure changes. It cannot be known without measuring.

The last lines show the only real defense. The page publishes its own total, and in Y2 this number is 38,690.7 m³ while the parsed set gives 38,630.6 m³; the difference is 60.1 m³, 1,202 times the threshold. In the case where no selector broke, no row dropped, and the total looked plausible, the only thing that caught the error was comparison with the number the source itself reports. Verifying a parser is not looking at whether the selectors match, it is counting the set that came out against the source’s own declaration.

Summary

• The structure of a page is not a contract; the same 1,877 rows can be published in four layouts, and a layout change is ordinary maintenance work for the publishing side.
• Inserting a single layer breaks the positional path selector: 1 broken selector, 1,877 dropped rows, zero records out. This failure is loud and hard to miss.
• Inserting a column breaks no selector: 1,877 records come out, zero drop, and the value of all 1,877 is wrong; the total deviates by only 60.1 m³, 0.16%, and the region field stops being a region name.
• Renewing the presentation layer this time breaks the semantic set (2 selectors, zero records) while the positional set is not harmed by the same version; durability comes not from the type of the set but from the direction of the change.
• The number of broken selectors does not measure the damage; comparing the parsed set with the total the source itself reports is the only check that catches the silent shift.

Next Step

In four lessons the data came by four routes, and how many rows were lost on each route was counted. The common assumption of these lessons was that the whole set could be collected: the file could be read, the query could run, the interface could be paged to the end, the page could be parsed from start to finish. When the population grows, this assumption falls, and a decision takes its place — a subset is taken instead of all the records. The next lesson measures the four answers four sampling decisions give to the same question and asks the real question: how well the subset taken represents the population, and who the records left outside are.