xml

XML Reading and Writing — machines/xml.shoddy

Summary

xml reads an XML document into a tree you can walk, and writes a tree back out as XML. It handles elements, attributes, text, comments, processing instructions, CDATA sections and the doctype. It keeps all of them, so a document that goes in comes back out — not a paraphrase of it.

It is a well-formedness parser, not a validating one, and it says so loudly. Well-formed means the punctuation is right: every tag closed, every quote matched. (A validating parser would also check the document against a rulebook of allowed elements; this one does not.) What it will not do is guess. A malformed document comes back as an error with a reason and an offset — the position in the text where the parser gave up. It never comes back as a tree that quietly lost something.

A Brief History of XML

XML's ancestor is SGML, a markup language IBM built in the 1970s. Its idea was that a document should carry its own structure rather than its own typesetting codes. SGML was enormously capable and enormously difficult. The specification ran to five hundred pages, and almost nobody implemented all of it.

In 1996 a working group under Jon Bosak set out to cut SGML down to something a programmer could implement in a weekend. XML 1.0 became a Recommendation — a finished web standard — in February 1998. For about a decade afterwards it was simply what data interchange meant. It was also, briefly, what everything meant: configuration, remote procedure calls, user interfaces, spreadsheets, build scripts. Some of that was a mistake and has been undone.

What survived the correction is the part XML is genuinely good at: documents. Text with markup in it, where the order of things matters, where an element can hold a mix of words and other elements, where a comment is worth keeping. JSON is better at records. XML is better at prose that has structure. Both machines are here because both jobs are real.

The one piece of XML this machine deliberately declines is the document type definition, or DTD. A DTD can declare entities — named abbreviations the parser must expand. That lets a DTD make a document expand to a thousand times its own size (the "billion laughs" attack). It can also make a parser fetch a file from the network or the local disk. Refusing to read the internal subset — the part of the doctype that carries those declarations — is not a shortcut here. It is the only responsible default for a parser pointed at a document you did not write.

Why It's Useful

XML is what a great deal of the world still speaks. RSS and Atom feeds, SVG images, Office documents, configuration files, SOAP services, sitemaps, Android layouts, patent filings, half of publishing — all of it is XML. Most of it will outlive whatever is fashionable this decade.

This machine exists so that reading any of that is nine lines of Shoddy rather than two weeks of string surgery. String surgery does not fail on the happy case. It fails on the comment containing a <, the CDATA section containing a &, and the attribute quoted with an apostrophe because its value contains a quotation mark. A parser gets those right once, on purpose, and then stops being interesting.

Include "xml.shoddy"

Def Main()
    Let doc = XmlLoad("feed.xml")
    Let items = XFindAll(doc, "item")
    Print(Str(Length(items)) & " items")
    Print(XTextOf(XFind(XNth(items, 1), "title")))

User's Guide

The tree

A node is an Xml, and there are seven kinds:

Type Xml = XDocument(XNodes As List Of Xml)
         | XElem(XTag As String, XAttrs As List Of Pair, XKids As List Of Xml)
         | XText(XChars As String)
         | XComment(XBody As String)
         | XPI(XTarget As String, XData As String)
         | XCData(XRaw As String)
         | XDoctype(XDtd As String)

Reading gives you an XDocument, not the root element. The XML declaration, the comments around the root and the doctype are part of the document, and throwing them away would make a round trip impossible. XRoot reaches the root element, which is what most programs actually want. It is idempotent, meaning applying it twice is the same as applying it once: XRoot of an element is that element. So a function taking "a document or an element" can just call it.

Reading, strictly or totally

Shoddy has no catchable errors. A parser that could only abort would be untestable on malformed input and unusable on input you did not write, so there are two:

Let doc = XmlParse(src)             ' aborts, with a reason and an offset
Select Case XmlRead(src)            ' total: XOk or XErr
    Case XOk(doc)
        UseIt(doc)
    Case XErr(why, at)
        Print("line noise at " & Str(at) & ": " & why)

That pairing runs through the whole machine. The strict word aborts; the total word always returns an answer, handing back your default instead. XAttr aborts and XAttrOr hands back your default. The same pairs exist for XChild, XFind, XPath and XRoot. Reach for the strict one when the document is yours, and the total one the moment it is not.

Finding things

You want	Word
the root element	`XRoot(doc)`
a named child	`XChild(e, "title")`
every named child	`XChildren(e, "item")`
a descendant anywhere	`XFind(doc, "title")`
every one of them	`XFindAll(doc, "item")`
down a path of names	`XPath(e, { "channel", "title" })`
an attribute	`XAttrOr(e, "href", "")`
the text under a node	`XTextOf(e)`

XPath here is a path of child names and nothing more. It is not the W3C query language of the same name (the W3C is the body that writes web standards). Predicates, axes and functions are not here. A machine that pretended otherwise would be lying about a thousand pages of specification.

Attributes are a dictionary

An element's attributes are a List Of Pair, which is exactly dict's association list — a list of name-and-value pairs. So XAttr and XPutAttr are DictGet and DictPut wearing a hat. Anything else dict can do to an association list works on them unchanged.

Writing

XmlText writes compactly. XmlPretty(doc, 2) re-indents. XmlCanonical sorts every element's attributes by name, recursively, for when you need two documents to be comparable rather than merely equivalent.

Under the Hood

What a round trip guarantees

Text is decoded on the way in, so a round trip is canonical, not literal: the writer produces one standard spelling, not the exact bytes it read. A comes back as A. An attribute quoted with apostrophes comes back quoted with quotation marks. What the writer does guarantee is that it is a fixed point: from the first write onwards, writing again changes nothing. And XmlText(XmlParse(x)) = x exactly when x is already in that canonical form. This repository's own docs/sitemap.xml is, and the test suite checks it byte for byte against all 154 of its elements.

Why the pretty printer refuses some elements

Indentation in XML is not free: whitespace inside an element is text, and text is content. So XmlPretty re-indents an element only when none of its children is text or CDATA. The moment words and markup are siblings — the <em>emphasis</em> and the rest — a line break inserted between them would add a space the author did not write. So that element goes out exactly as XmlText would write it. An element holding a CDATA section is left alone for the same reason, and more forcefully. Carrying characters exactly is the entire purpose of CDATA. Two spaces of indentation would end up inside the program it was carrying.

Entities become bytes, not code points

This is the load-bearing decision in the machine, and it comes from the runtime rather than from XML. ReadFile is Latin-1, an encoding where one byte in the file becomes one character in the string. That is what lets the same words read a PNG. So an em dash sitting literally in a UTF-8 document (UTF-8 spells one character as one to four bytes) arrives as the three characters 226, 128, 148.

Suppose — decoded to Chr(8212) instead. The same character written two ways would then give two different strings, and XEqual would say they differ. WriteFile would turn the second into a question mark, because a character above 255 has no byte to be written as. So a numeric reference is encoded to its UTF-8 bytes. The entity and the literal agree, and what comes out is a valid UTF-8 file again.

The depth budget

Elements nest, so the reader is genuinely recursive: it calls itself once for each level of nesting. Each call spends a little of the machine's stack, its working memory for calls in progress. That cost is small for real documents and unbounded on hostile ones. A budget of 200 levels is spent one level at a time, and running out is an error like any other. The loops that scan a long name, a wide element or a run of text call only themselves in tail position — as their very last step — so they compile to loops and cost no stack at all.

What is not here

Namespaces are not resolved. A prefixed name is carried literally, prefix and all, and xmlns is an ordinary attribute. XPrefix and XLocal split a name when you need the halves. Mapping a prefix to a URI — a namespace's identifying address — is the caller's business.
The doctype is opaque and its internal subset is never read, so a document declaring its own entities is refused rather than silently emptied.
The encoding declaration is advisory. ReadFile decided the bytes long before this machine saw them.
NUL cannot be carried. NUL is the character with code zero. Chr(0) is the empty string in Shoddy, so  is rejected by name rather than silently shortening the text.

Word Reference

Reading

Word	What it does
`XmlParse(s)`	Parse, or abort with the reason and offset.
`XmlRead(s)`	Total: `XOk(doc)` or `XErr(why, at)`.
`XmlReadDepth(s, n)`	As above with your own nesting budget.
`XmlLoad(path)`	`XmlParse(ReadFile(path))`.

Writing

Word	What it does
`XmlText(x)`	Compact XML.
`XmlPretty(x, n)`	Indented by `n`, leaving mixed content alone.
`XmlSave(path, x)`	Compact, to a file.
`XmlCanonical(x)`	Attributes sorted by name, recursively.
`XmlEscape(s)`	`&`, `<` and `>` to references.
`XmlEscapeAttr(s)`	Those, plus the quote and the control characters.
`XmlUnescape(s)`	References back to text.
`XUtf8(n)`	A code point as its UTF-8 bytes.

Navigating

Word	What it does
`XRoot(x)` / `XRootOr(x, d)`	The root element.
`XTag(e)`, `XAttrs(e)`, `XKids(e)`, `XChars(t)`	The record accessors; they abort on the wrong kind of node.
`XAttr(e, n)` / `XAttrOr(e, n, d)`	One attribute.
`XHasAttr(e, n)`, `XAttrNames(e)`	Ask first, or list them all.
`XAttrNumOr`, `XAttrBoolOr`	An attribute read as a number or a flag.
`XElems(e)`, `XCount(e)`	The element children; the number of all children.
`XChild(e, t)` / `XChildOr` / `XHasChild` / `XChildren`	By name, one level down.
`XFind(x, t)` / `XFindOr` / `XFindAll`	By name, anywhere below.
`XPath(x, ns)` / `XPathOr`	Down a path of child names.
`XDescend(x, acc)`	Every element in document order.
`XTextOf(x)`, `XTextNumOr(x, d)`	The character data underneath.
`XPrefix(n)`, `XLocal(n)`	The two halves of a prefixed name.
`IsXElem`, `IsXText`, `IsXCData`	Which kind of node this is.

Building and comparing

Word	What it does
`XLeaf(t, s)`, `XNode(t, ks)`	An element with text; an element with children.
`XPutAttr`, `XDelAttr`	Functional update of one attribute.
`XAddKid`, `XSetKids`, `XSetText`	Functional update of the children.
`XEqual(a, b)`	Deep comparison. Use this, never `=`.
`XIsBlank(s)`, `XTrimWs(s)`	Whitespace including tabs and newlines, which `Trim` ignores.

Who Uses It

	User	How
	html	A parsed page is an `Xml` tree, so every word above works on HTML and `html` never redefines one of them.

The Machines It Uses

	Machine	Why
	dict	An element's attributes are an association list, so `XAttr` and `XPutAttr` are `DictGet` and `DictPut` wearing a hat.
	seq	`Zip` and `Append` build the attribute list; `Any` and `All` walk the tree.
	sinq	`OrderBy` puts an element's attributes in name order for `XmlCanonical`, which the `Sort` builtin cannot do to a `List Of Pair`.
	str	`Join` assembles the writer's fragments in one pass at the end, and `StrRep` makes the pretty printer's indentation.