zxpath

XPath 1.0 for Zig 0.16, over a ztree document: all thirteen axes, all four types, and the whole core function library.

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/zxpath.git

Repository

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

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

It is mirrored on Tangled at https://tangled.org/jcollie.dev/zxpath, 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:z3ENN7bhRPTk3JFJPQ9HjJgyAYmmX

and this fetches it:

$ rad clone rad:z3ENN7bhRPTk3JFJPQ9HjJgyAYmmX

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:z3ENN7bhRPTk3JFJPQ9HjJgyAYmmX

Usage

const zxpath = @import("zxpath");

var compiled = try zxpath.Compiled.init(gpa, "//book[@lang='en']/title", .none);
defer compiled.deinit();

var ev: zxpath.Evaluator(error{}) = .init(gpa);
const v = try ev.eval(compiled.expr, .{ .node = doc.ref(doc.root) });
defer v.deinit(gpa);

const text = try v.toString(gpa);
defer gpa.free(text);

Compiling and evaluating are separate because they answer to different contexts. A prefix in an expression means whatever the document the expression was written in said it meant, which is settled once; the context node, the position and the variables are settled every time it runs. NsResolver is how the first is supplied, and Focus is the second.

Errors are the caller's too

Evaluator is generic over the error set a host's own variables and functions can fail with:

const Evaluator = zxpath.Evaluator(error{ UnknownKey, DocumentNotFound });

The parameter is there so that XPath does not have to know what a host can go wrong at. An XSLT engine's key() fails with UnknownKey and its xsl:message with Terminated; neither is an XPath error, and neither belongs in the error set of a library that has no keys and no messages. zxpath.CoreError is what XPath itself raises — six errors and OutOfMemory — and Evaluator(H).Error is that plus H.

For a caller with no extensions, Evaluator(error{}) is the whole story.

What it implements

Axes	All thirteen, with correct proximity position — preceding-sibling::a[1] is the nearest, not the first in the document
Types	node-set, boolean, number, string, with XPath's conversions between them
Functions	The core library: last position count id local-name namespace-uri name string concat starts-with contains substring-before substring-after substring string-length normalize-space translate boolean not true false lang number sum floor ceiling round
Extensions	A caller supplies its own through FunctionResolver, which is asked before the core library so a host may shadow one

id() resolves xml:id, whose type is fixed by its own specification, and also any attribute the document's internal subset declares to be of type ID — which means a document parsed with ParseOptions.dtd. Parsed without it there are no declarations to consult and only xml:id answers, which is what libxslt does with a document whose type it never read.

The parts that are easy to get wrong

Three things account for most of this code, and each is a place where the obvious implementation is wrong:

• Comparison against a node-set is existential. @x = 1 is true when some node in the set is 1, so @x != 1 is not not(@x = 1) — for a set holding 1 and 2 both are true, and for the empty set both are false.
• Predicates are numbered along the axis. In preceding-sibling::a[1] the [1] means the nearest preceding sibling, because a reverse axis counts outwards from the context node. So a step filters in axis order and only then merges into the document-ordered set a node-set has to be.
• A step is evaluated once per context node and merged. a/b is the union over every a, not the b children of the first one, and the union is what makes a/../a report each element once.

Numbers are formatted the way XPath says

XPath 1.0 §4.2 writes a number in decimal with no exponent form at all and with as many digits as it takes to identify the double. libxslt hands the number to C instead, switching to scientific notation past INT_MAX and rounding to fifteen significant digits:

Expression	XPath 1.0, and zxpath	libxslt 1.1.45
1000000 * 1000000	1000000000000	1e+12
1 div 3	0.3333333333333333	0.333333333333333
1 div 100000000	0.00000001	1e-08

The first is the one that bites: an identifier computed in an expression and written out as 1e+12 is not the same string.

Testing

$ zig build test
$ zig build fuzz-run -- --seconds 600
$ zig build fuzz-run -- --iterations 500000 --target evaluate

There are two fuzz targets because a compiler and an evaluator break in different ways: one is a parser and breaks on shapes, the other breaks on what those shapes mean once there is a document underneath. Both check that a bad expression returns — an error is a fine answer — rather than panicking, leaking or running off the stack, and the evaluate target additionally converts whatever came back to all four types, since a conversion is where an evaluator that built something malformed finally trips.

Two bugs turned up within the first three million inputs, both of which had survived a full XSLT conformance suite:

• 'x'[1] — a filter over something that is not a node-set — freed the operand twice. An errdefer sat beside an explicit free on the error path, so returning the type error ran both.
• substring('abcd\xf0', 1, 9) walked off the end of the string. A lead byte announcing a four-byte sequence in the last byte stepped the character cursor past the end, and substring used that as a slice index. Nothing forbids a string literal that is not valid UTF-8.

Both are in the corpus now, so the seed replay in zig build test catches them without the mutator having to rediscover the shape.

Where it came from

This was the XPath layer of zxsl, an XSLT 1.0 processor, and was lifted out because none of it is about XSLT. One thing did carry XSLT's fingerprints and was fixed on the way out: the evaluator's error set used to name UnknownKey, Terminated and InvalidStylesheet — because the host's functions call back into the evaluator and the two sets would otherwise be mutually recursive. Making Evaluator generic over the host's errors is what let XPath's own set shrink to what XPath can actually raise.