ztree

An XML document tree for Zig 0.16, built on zxml: parents, document order, expanded names, and a serializer to write one back out.

zxml is a pull parser, which is the right shape for reading a document once and the wrong shape for anything that needs to ask questions about it. chapter/title wants a parent. Sorting nodes and then restoring document order wants an order to restore. Indexing every element by an attribute wants random access. Validating against a DTD wants to answer an IDREF that points at an element not yet parsed. None of that is answerable from a stream, so this reads the stream once and builds the tree those questions need.

The API documentation is generated from the doc comments, which is where most of the explanation lives.

Installation

$ zig fetch --save git+https://git.jcollie.dev/jeff/ztree.git

Repository

The repository's home is my Forgejo instance at git.jcollie.dev/jeff/ztree, which is where CI runs.

$ git clone https://git.jcollie.dev/jeff/ztree.git

It is mirrored on Tangled at https://tangled.org/jcollie.dev/ztree, and it is also published on Radicle, a peer-to-peer forge built on git, where the copy needs no account and no server anyone has to keep running. The repository's identifier there is

rad:zz3g23UMxti2LuRoUa5fxvDDMeEE

and this fetches it:

$ rad clone rad:zz3g23UMxti2LuRoUa5fxvDDMeEE

Any of the three is the whole project, on the main branch, with the same history.

rad clone finds seeds through your local node's routing table rather than through a known host, so the node has to be running before it can find anything:

$ rad node start

If you already have the repository and only want to help host it, seeding it tells your node to carry a copy for others:

$ rad seed rad:zz3g23UMxti2LuRoUa5fxvDDMeEE

Usage

const std = @import("std");
const ztree = @import("ztree");

const doc = try ztree.parse(gpa, source, .{});
defer doc.destroy();

const root = doc.documentElement().?;
for (doc.node(root).children.items) |child| {
    if (doc.node(child).kind != .element) continue;
    std.debug.print("{s}\n", .{doc.node(child).name.local});
}

const out = try ztree.serialize.toOwnedSlice(gpa, doc, .{ .indent = true });
defer gpa.free(out);

What it does

• Resolves namespaces. A prefix becomes a namespace URI when the document is parsed, so a Name is an expanded name — a URI and a local part — and comparing two names never involves a prefix. The prefix is kept only because the serializer has to write something back out.
• Coalesces character data. <a>x&amp;y</a> has one text child and <a>x<!--c-->y</a> has two, which is what the data model says and what makes text()[2] mean anything.
• Orders every node. NodeRef.before is a total order across documents, so a set of nodes gathered from several trees still sorts.
• Is a builder as well as a reader. The interesting thing to do with a document is usually to produce another one, so Document has as many functions for appending and setting as it has for walking.
• Writes three ways. serialize has the XML, HTML and text output methods, with the namespace fixup, escaping and indentation each of them needs.
• Validates against a DTD. validate checks a document against the declarations of its own internal subset: content models, attribute types and defaults, ID uniqueness and IDREF resolution. Every problem is reported rather than the first one thrown.

Design

• Nodes are indices, not pointers. A NodeId is a u32 into one flat array, so a set of nodes is a list of integers, deduplication is sorting, and the whole tree frees in one deinit because every string in it belongs to the document's arena.
• The source is not borrowed. Every string in the tree is copied into that arena with entity references already resolved, so the text a document was parsed from may be freed the moment parse returns.
• Namespaces are fixed up when writing, not when building. A result element knows the namespace URI of its name, but a prefix only means something against the declarations in scope where it lands — and a subtree copied out of another document brings none with it. The writer keeps its own scope stack and emits whatever is missing, which is the only point at which the question has a definite answer.
• The declarations are copied, like everything else. zxml's Dtd borrows from the text it was read out of, and this tree's whole contract is that the source may be freed the moment parse returns. So the document type declaration is copied into the arena first and read from there, which costs one string and buys a document that can still be validated after the bytes it came from are gone.

Validating against a DTD

Reading the declarations is off by default, because it changes what the tree says: the general entities the internal subset declares resolve, and the attribute defaults it gives arrive as attribute nodes the start tag never wrote. Ask for it, and Document.dtd holds what the document type declared.

const doc = try ztree.parse(gpa, source, .{ .dtd = true });
defer doc.destroy();

const report = try ztree.validate.run(gpa, doc);
defer report.deinit(gpa);

for (report.problems) |problem| {
    std.debug.print("{t}: {s}\n", .{ problem.code, problem.detail });
}

incomplete_content: <product> ends with its content model, (name, note?), unsatisfied
duplicate_id: `id` is "p1", which another element already carries
unresolved_idref: `ref` refers to "p9", and no element carries that ID

Every problem is collected rather than the first one thrown, because a document that fails validation usually fails it in several places and fixing them one run at a time is miserable. They come back in document order, code is an enum to branch on, and detail is the sentence above.

Why the split with zxml is where it is

XML asks a processor that does not validate to supply attribute defaults and resolve the entities an internal subset declares. Those change what the document says, so only the parser can do them, and zxml does: it reads a <!DOCTYPE> into declarations, compiles each <!ELEMENT> content model to an automaton, and stops.

Reaching a verdict is a different job with a different shape. It wants a per-element automaton state, a table of every ID in the document, and a list of references held until the end — and an IDREF may point forward, which a stream cannot answer at all. That is this library's whole reason to exist, so the verdict lives here.

What is not checked is what nothing here will fetch. A document type naming an external subset is error.ExternalSubsetNotRead rather than a verdict reached against half the declarations, since the missing half would show up as a flood of undeclared elements. Nothing opens a file or a socket at any point.

One consequence worth knowing: a DTD predates namespaces and validates names exactly as they are written. x:item is declared as x:item, and the same element reached through a different prefix bound to the same URI is, to the document type, an element it never heard of. That is XML's answer rather than this library's, and pretending otherwise would accept documents no other validator does.

HTML output reproduces libxslt, quirks included

The HTML method is not a variation on the XML one. It indents by default, and its indentation inserts no spaces at all — only newlines, in three specific places, and only around elements HTML actually defines. An element HTML does not know is never formatted; <br> has no end tag and no slash; <script> is not escaped; a <head> gets a character encoding declaration inserted.

Those rules, and the table of which elements are empty, inline or raw text, are taken from libxml2's source rather than guessed at — down to its name[0] != 'p' test for "p, pre and param", which also catches picture and is reproduced with the quirk intact. The point of matching the reference implementation's whitespace is to match it.

Testing

$ zig build test

That runs the unit tests and replays the fuzz corpus. The property worth knowing about is the strong one:

$ zig build fuzz-run -- --seconds 600
$ zig build fuzz-run -- --iterations 500000 --target document

Whatever parsed must serialize to something that parses again. A tree is not much use if writing it out produces a document nobody can read, and the two halves drift apart easily because nothing else compares them. That property is what found the bug behind zxml's name validation: <:/> parsed as an element whose name was a single colon, and serialized to <>.

The validate target carries a property of its own: the source is freed before the verdict is reached. The declarations are copied into the arena precisely so a tree outlives the text it came from, and a validator reaching back into that text would read freed memory — the kind of bug that surfaces six months later rather than in the test that introduced it.

The loop is this project's own rather than Zig's, because Zig 0.16.0's fuzzer cannot be used — a test executable will not build in fuzz mode without the one-line standard library patch the devshell applies, and even with it the table of program counters comes back empty, so there is no coverage feedback to have. What the loop has instead is a corpus of inputs that already parse, which for a parser is most of the way there.

Documentation

$ zig build docs         # into zig-out/docs
$ zig build docs-serve   # and read it at http://127.0.0.1:8000

It has to be served rather than opened: the viewer fetches its sources and its WebAssembly at runtime, which a browser refuses to do from a file:// page.

Where it came from

This was the tree layer of zxsl, an XSLT 1.0 processor, and was lifted out because none of it is about XSLT. The import graph had no edges back: the tree reads only zxml, and the serializer reads only the tree.

Two things did carry XSLT's fingerprints and were renamed on the way out. Node.disable_escaping is Node.verbatim, since writing a node through untouched is a general idea and disable-output-escaping is only the best known instance of it. serialize.Output kept its name, because what it holds really is the set of output settings — but it is worth knowing that the vocabulary came from xsl:output, which is why it has cdata_section_elements in it.