zxsl

An XSLT 1.0 processor for Zig 0.16, built on zxpath, ztree, zxml and zig-datetime.

It is a library first and a command line tool second. The library reads no files and opens no sockets: a stylesheet's xsl:include and its document() calls go through a Loader the caller supplies, so a transformation can be run against a bundle, a cache, or nothing at all, and an untrusted stylesheet cannot reach the filesystem because there is nothing there to reach it with. The zxsl binary is the one place a Loader is wired to a directory.

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

Repository

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

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

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

and this fetches it:

$ rad clone rad:z2dxNbg5hyMZBET2t6Laok4jH43ba

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

Standards

Standard	Title	Support in zxsl
XSLT 1.0	XSL Transformations	Every instruction and top-level declaration; see the table below for what within them is not covered
XPath 1.0	XML Path Language	Through zxpath: all thirteen axes, all four types and the core function library. XSLT's own additions — key, document, current, format-number, generate-id and the rest — are supplied from here
XML 1.0 (5th ed.)	Extensible Markup Language	Through ztree and zxml. The internal subset is read — entities, attribute defaults and ID declarations — but nothing external is ever fetched
XML Namespaces 1.0	Namespaces in XML	Resolved into expanded names by ztree when a document is parsed, and here when an expression is compiled
EXSLT common	node-set, object-type	A result tree fragment is already a tree here, so node-set hands a node-set back unchanged and wraps anything else in a fragment holding one text node
EXSLT functions	func:function, func:result	A stylesheet declares its own functions and calls them from any expression. func:script names code in another language and is not implemented
EXSLT sets	difference intersection distinct has-same-node leading trailing	All six
EXSLT math	min max highest lowest abs sqrt power log exp constant	The trigonometric and random functions are not implemented
EXSLT strings	replace tokenize split padding concat align encode-uri decode-uri	All eight
EXSLT crypto	md5, sha1	The digests, and not the ciphers — see below
EXSLT dynamic	evaluate, map	An expression that will not compile or will not run is an empty node-set rather than an error: it came from the document, not the stylesheet. closure, min, max and sum are not implemented
EXSLT dates-and-times	date-time date time year leap-year month-in-year month-name month-abbreviation week-in-year week-in-month day-in-year day-in-month day-of-week-in-month day-in-week day-name day-abbreviation hour-in-day minute-in-hour second-in-minute add add-duration sum difference duration seconds	format-date and parse-date are not implemented; they want a locale and a strftime. date:date-time() needs a clock, which Options.io supplies

What is here and what is not

XSLT needs a tree. zxml is a pull parser and never builds one, which is the right shape for reading a feed once and the wrong shape for a language whose questions a stream cannot answer: chapter/title asks for a node's parent, xsl:sort reorders a node-set and then wants document order back, and a key indexes every node in the document before the first template runs.

That tree is ztree, and it is a separate library because none of it is about XSLT — it resolves namespace prefixes, merges adjacent character data, orders every node, and serializes a document back out by the XML, HTML or text method. It lived here first and was lifted out once it was clear the import graph had no edges back.

XPath went the same way, for the same reason, and is zxpath. EXSLT's dates-and-times module needs a calendar, and a calendar is the kind of thing that is wrong in the same way in every project that reimplements one, so that comes from zig-datetime: the ISO 8601 parsing, the durations and the arithmetic are its, and what is here is only the part that is XSLT's — XML Schema's eight right-truncated date types, the rule deciding which of them an answer is written in, and the year numbering that has no zero.

What is left here is XSLT itself: match patterns and their priorities, the stylesheet reader, xsl:number and format-number, and the engine that decides which template handles which node. The other layers still matter to all of it — an XSLT result is a tree and not a string, and nearly every instruction evaluates an expression — but building trees, running XPath and counting days are somebody else's job now.

Design

• Template dispatch is indexed, not scanned. Rules are filed by what their pattern's last step can match -- an element name, an attribute name, a wildcard, text(), / -- because a pattern is matched from its last step backwards, so that step alone decides whether a rule could apply at all. Each bucket is sorted by the order conflicts resolve in, so a lookup is a merge across at most four of them that stops at the first rule which really matches. At a thousand templates that is about four times faster than testing every rule against every node.
• The library does no I/O. A Loader is a pair of function pointers the caller supplies. Loader.none refuses everything, which is the default.
• Expressions are compiled once and cached by where they were written. A prefix in select="x:a" means whatever x was bound to on the element the attribute sits on, so an expression is compiled against that element and cached against that attribute node.
• The stylesheet is interpreted from its tree. There is no instruction set in between. An instruction set would run faster and would be several hundred lines whose only job is to restate a tree that is already in memory; since every expression is compiled once, the work that repeats is not the parsing.
• Values own their storage. An arena would be easier to write and would make the peak memory of a transformation whatever the worst template happened to allocate. A node-set can hold every node in a large document.
• Nesting is bounded. Expressions, evaluation and template instantiation are all capped, so a stylesheet that recurses without a base case is an error rather than a stack overflow in whatever is calling the library.

Usage

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

const sheet = try zxsl.stylesheet.parse(gpa, stylesheet_text, .{});
defer sheet.destroy();

const source = try zxsl.tree.parse(gpa, document_text, .{});
defer source.destroy();

const output = try zxsl.transform.transformToString(gpa, sheet, source, .{});
defer gpa.free(output);

transform returns the result tree instead, for a caller that wants to walk it rather than serialize it. Top-level xsl:params are supplied through Options.parameters, and xsl:message goes wherever Options.messages points.

When a stylesheet will not compile, sheet.diagnostic says what was wrong with it — the expression, the attribute it was in, and what the parser objected to. The error itself is only error.InvalidStylesheet, because an unbound prefix and a stray bracket are the same kind of problem to a caller and neither is findable without the text that caused it.

Conformance

Suite	Result
libxslt's own test corpus: its regression suite, the XSLT Recommendation's examples, and the per-subject suites	376 of 408
tests/cases, recorded from xsltproc for this project	29 of 29

The first number is the honest one, and the second is why it needs saying: a suite you wrote yourself passes because you wrote it. Running somebody else's found four bugs within an hour, one of which was silent heap corruption — and pointing it at libxslt's EXSLT suites, after those modules were already written and passing the tests here, found six more in an afternoon.

$ zig build corpus
libxslt corpus: 376/408 pass, 32 known failures

The corpus is fetched, not vendored. corpus/ is a project of its own whose manifest names libxslt's release tarball as a lazy dependency, so nothing that merely builds this library pays for it, and somebody else's tests stay under somebody else's licence and outside this repository.

corpus/expected.txt lists every case that does not pass and why, and it is a ratchet in both directions: a case that fails without being listed is an error, and so is a case that passes while still listed. A fix cannot land without deleting its line, and a regression cannot hide behind a long list of known failures. Nothing is skipped and nothing is untriaged: every case in the corpus is run, and each of the 32 that fail says what it is waiting on. Six of those are cases whose recorded output is not what libxslt produces any more — running xsltproc over the whole corpus and comparing is how that was found, and an expectation is only an oracle while the oracle still produces it.

Category	Count	What it says
exslt, libxslt-extension	8	libxslt's own extensions, and the Saxon and Xalan ones it provides, are not implemented
spec-divergence	7	zxsl follows the Recommendation and libxslt does not; the recorded output is the oracle's own behaviour
stale-expectation	6	The recorded output is not what libxslt produces today, so the case is not an oracle for anything
generate-id	3	Untestable: the test compares generated ids literally, and only uniqueness is specified
harness	2	libxslt's own harness runs the case with parameters, or with a plugin built; plain xsltproc does not reproduce it either
strict-error	2	key() on an undeclared key raises here and recovers in libxslt
external-entity	1	The internal subset is read; nothing external is ever fetched
output-encoding	1	xsl:output names an encoding written as character references rather than bytes — valid in that encoding, but not byte for byte
sort-collation	1	zxsl orders text by UTS #10 and libxslt compares code points; _ and - sort below letters in DUCET and above D by code point
declined	1	crypto:rc4-encrypt; see below

The one that used to be skipped

general/bug-166 is the corpus's largest document -- fifteen thousand elements against six keys, one of which indexes on a call to another -- and it is worth keeping the history of this entry, because each correction was more interesting than the last.

It began as too-slow, on the grounds that template dispatch was a linear scan over every rule and the case took minutes. Dispatch was a linear scan and is now indexed by name, but the minutes were an artefact of measuring a debug build, whose allocator captures a stack trace per allocation: the profile was sixty per cent DWARF unwinding. A benchmark is not a measurement until you have looked at where the time went.

Measured properly it took seven seconds and produced the wrong answer, so it became skipped: a correctness failure with a stability problem on top, since it also exhausted the runner's memory budget and took the other 280 results down with it. The wrong answer was one bug — xsl:sort evaluated its keys without setting the current node, so a key using current() gave the same answer for every node and a two-level sort silently became a one-level one. The seven seconds and the memory went somewhere in the work on key(), which had a dangling pointer in it at the time; which of those changes paid for it was never measured.

It now runs in about a third of a second — 310ms, measured in a ReleaseFast build — and produces the right bytes. It is still by a wide margin the slowest case in the corpus: nothing else reaches twenty milliseconds.

Using libxslt as an oracle

The test suite does not compare against expectations somebody wrote down. It compares against what libxslt actually printed.

tools/oracle.sh runs xsltproc over every case in tests/cases and captures its output verbatim into an expected file; tests/conformance.zig then asserts that this library produces the same bytes. For a specification this size the difference matters, because what a careful reading of the words suggests and what every implementation does are not always the same thing. Four of the first twenty-nine cases disagreed, and all four were bugs here:

• The HTML output method indents by default, and its indentation is nothing like the XML method's — no spaces at all, newlines in exactly three places, and only around elements HTML actually defines.
• An HTML <head> gets a character encoding declaration inserted into it.
• format-number keeps a leading integer digit: a # before the decimal point means "no padding here", not "no digit here".
• xsl:namespace-alias replaces a name's namespace URI and leaves its prefix alone.

Those rules 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, because matching the reference implementation's whitespace means matching it.

Where this library disagrees on purpose

One case, xpath-number-format, carries a second expected output. XPath 1.0 §4.2 says a number is written 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 zxsl	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 of those is the one that bites: an identifier computed in a stylesheet and written out as 1e+12 is not the same document. A case that diverges must carry a why.md arguing why, and a test fails if one does not — a disagreement nobody wrote down is indistinguishable from a bug that was papered over.

The other disagreement worth knowing about before porting a stylesheet is about parameters and the built-in template rules. XSLT 1.0 §5.8 defines those rules as literal templates — <xsl:template match="*|/"><xsl:apply-templates/></xsl:template> — and they have no xsl:param, so §11.6 says a parameter passed to one is ignored, and its own xsl:apply-templates passes nothing on. libxslt threads the parameters through instead, so a with-param survives any number of elements that no template matches:

<xsl:template match="/">
  <xsl:apply-templates select="//wrapper">
    <xsl:with-param name="p" select="'passed'"/>
  </xsl:apply-templates>
</xsl:template>
<xsl:template match="leaf">
  <xsl:param name="p" select="'default'"/>
  <xsl:value-of select="$p"/>
</xsl:template>

Against <r><wrapper><leaf/></wrapper></r>, libxslt writes passed and this writes default, because nothing matches wrapper. A stylesheet relying on it will not work here without an explicit rule for the elements in between — which it needs anyway to work on any other conforming processor.

One function of one module is missing on purpose rather than for want of time. EXSLT crypto has crypto:rc4-encrypt and crypto:rc4-decrypt alongside its digests, and those two are not here. RC4 is broken, and a function named "encrypt" is an invitation to rely on it — a stylesheet author who reaches for it is reaching for secret-keeping, which is the one thing it cannot do. libxslt provides them for the stylesheets that already call them; a new implementation has no such debt. crypto:md5 and crypto:sha1 are here, because the things a stylesheet actually wants a digest for — naming a fragment, keying a cache, telling two documents apart — are not secret-keeping claims.

What is not covered

Everything in XSLT 1.0 is implemented except the following, which are accepted and ignored rather than rejected, so that a stylesheet using them still runs:

Feature	Status
External DTD subsets	The internal subset is read — its entity declarations resolve, its attribute defaults arrive as attributes, and its ID declarations are what id() looks for. Nothing external is ever fetched, so an entity declared SYSTEM cannot be resolved and an external subset is named and skipped
xsl:number lang, letter-value	Accepted and ignored; format, level, count, from, value, grouping-separator and grouping-size all work
xsl:sort lang	Implemented as far as the collations built in: it selects a CLDR tailoring through zig-collate's -Dlocales, and a language with none — which includes German and French, since CLDR has no standard tailoring for either — gets the root collation. Never an error
xsl:output media-type	Accepted and ignored; it names a MIME type and changes no bytes
Extension elements and functions	EXSLT common, functions, sets, math, strings, dates-and-times, dynamic and the digests of crypto; see the table above for what within them is not covered. libxslt's own extensions are absent. An unknown extension element runs its xsl:fallback

One place is deliberately more permissive than the specification: a result tree fragment is a real tree here, so $fragment/foo works where XSLT 1.0 says a fragment may only be converted to a string. The strict behaviour would be to raise an error, and raising one would break stylesheets that every other processor runs.

The collation that is missing

xsl:sort compares text by code point, which is the one entry in that table worth fixing rather than merely documenting: it is not just unlocalized but wrong in a way users notice, Mueller sorting before Märtens because u is U+0075 and ä is U+00E4. Doing it properly means the Unicode Collation Algorithm in a library of its own, for the same reason the calendar is zig-datetime's — issue #1 has the plan and what it would rest on.

Command line

$ zxsl style.xsl document.xml
$ zxsl --stringparam title 'A Report' style.xsl document.xml
$ zxsl -o out.html style.xsl -

The options are xsltproc's, because that is the program every example on the web is written for and because the test suite compares the two — a case that has to be invoked differently is a case that is not really being compared. A document of - is read from standard input.

Testing

$ zig build test

That runs the unit tests, the oracle suite and the fuzz targets over their seed corpus, all together. Re-recording the oracle needs xsltproc, which the devshell provides:

$ nix develop
$ zig build oracle          # re-record every case
$ zig build oracle -- keys  # or just one

The version of libxslt that produced the current recordings is in tests/cases/libxslt-version, because "what libxslt printed" is not a fact without it.

Fuzzing

Everything here takes bytes from outside — an expression out of a stylesheet, a stylesheet off disk, a document off the network — so tests/fuzz.zig checks the property that matters for all of them: return, do not crash. An error is a fine answer and so is a result; a panic, a leak or a stack overflow is a failure in whatever embedded the library rather than in the document that caused it.

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

That is a loop of 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 — the interesting inputs are the ones that are nearly right.

Eight targets: three that compile a small language (xpath, pattern, picture), two that read a document (document, stylesheet), one that runs the engine (transform), and two that read one of XSLT's other syntaxes (date, duration). Five of them check only that nothing crashed. The other three check a round trip, which is where the bugs have actually been: whatever parsed must be writable, and what was written must parse back to the same value.

That property has found three bugs so far, each of a different kind. zxml accepted <:/> as an element whose name was a single colon, nothing downstream objected, and the result serialized to <>, which is not a document any more — a parser that accepts what its own writer cannot write turns a malformed input into malformed output, so zxml validates names now. zig-datetime checked each component of a duration for overflow as it read it and not the total they accumulated into, so P9000000000000000000Y was refused while P900000000000000000Y900000000000000000M panicked. And format-number handed std.unicode.utf8Decode a clamped slice to find out whether a picture was valid UTF-8; that function dispatches on the length it is given and then asserts the lead byte agrees, so a four-byte lead with two bytes behind it panicked rather than failing. Its own doc comment calls the API too easy to use incorrectly.

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.