Profiling Org->HTML formal grammar and optimizing it: orgwebalchemy

OrgWebAlchemy is a Guile library that parses Org mode with a Parsing Expression Grammar and renders it to HTML, Markdown, or SXML. I wrote an earlier article about why a PEG is the right tool for Org: the grammar describes the language, the parser builds a tree, the renderers turn that tree into output.

This is the follow-up, and it turned into a harder question than I expected: how do you make a parser fast without making it wrong? I didn’t want something that’s quick on my test files and quietly behaves differently on yours.

So: the features I added, how I measured them, what the profiler said, the two rounds of fixes, and how I checked the language didn’t change. Every number below comes with a way to reproduce it, because a number you can’t check is advertising, not evidence.

TLDR; Here is the whole article in five sentences:

OrgWebAlchemy is free software under the GNU Lesser General Public License, version 3 or later, with this documentation under the GNU Free Documentation License. Run it, study it, change it, ship your changed versions.

It could have been a service instead: you send your Org file to a server you don’t control, and get HTML back. That can be convenient, and it can even be gratis, but it leaves you helpless in the ways that matter. You can’t study it, can’t fix it, and can’t keep using it when the operator loses interest or changes the terms. A library goes into your program, on your machine, under your control.

The LGPL is a compromise, and I’ll name it as one. The GPL would keep every program that uses this code free too, and that’s the stronger guarantee for users. For libraries the GNU Project has long accepted a weaker license so that more programs can use them, including some that aren’t free, and I’ve followed that tradition. Use it in a free program and you’re helping the community; use it in a nonfree one and I’d rather you made that program free.

There’s a second reason it’s a library. Org mode is a language, and a language is worth as much as the number of programs that can read it. A parser only Emacs can use is a parser for one program. One that any Guile program can call is a parser for a text editor, a static site generator, a wiki, a notebook, a mail archiver, a package’s docs build, or something nobody has written yet. I don’t know what you’ll build with it, and that’s the point.

And a word on what it isn’t: it’s not Emacs and doesn’t try to be. Emacs is where Org lives, where it gets edited, and where its export machinery started. OrgWebAlchemy doesn’t replace that, it just lets other Scheme programs read the same files. When it disagrees with Emacs about some corner of the syntax, Emacs is right and this is a bug.

OrgWebAlchemy is still three small modules. What changed is how much of the language each one covers.

The API is still small enough to hold in your head.

(use-modules (orgwebalchemy html) (orgwebalchemy markdown) (orgwebalchemy peg))

(org->html "This is test code.") ;; => "This is <code>test</code> code."

(org->markdown "This is test code.") ;; => "This is test code."

;; parse once, render as often as you like (define ast (org->ast "* Hello\nA bold line.\n")) (org-ast->html ast) (org-ast->markdown ast)

The rest of this article is about what happens between those calls.

“Supporting Org” hides a lot of work, because Org isn’t a markup language with a tidy grammar. It’s a pile of conventions accumulated over years of a GNU Emacs major mode, some of them deliberately informal, and each one has to be considered on its own terms. Every feature below started as a sentence in the Org manual, became a grammar pattern, then became a test.

An Org link’s target says what kind of link it is. A target starting with https:// is external. file:photo.png is a file, and so is a bare notes.org. #custom-id points inside the document, *Heading at a heading, and a ::search suffix says where inside the target you land.

The old code let each renderer read the target and decide for itself, which is exactly how two back ends drift apart. HTML grows a special case for image extensions, Markdown grows a slightly different one, and after a year of small repairs the same document means two things depending on which function you call. A user who notices won’t know which one is right, and will be right not to trust either.

So classification moved into the parser, where it happens once.

(org-link-parts "https://example.org/a") ;; => (https . "//example.org/a") (org-link-parts "file:photo.png") ;; => (file . "photo.png") (org-link-parts "notes.org") ;; => (file . "notes.org") (org-link-parts "#custom-id") ;; => (internal . "custom-id") (org-link-parts "*My Section") ;; => (heading . "My Section") (org-link-parts "notes.org::*Heading") ;; => (file . "notes.org") (org-link-search "notes.org::*Heading") ;; => "*Heading" (org-image-link? "photo.jpeg?raw=1") ;; => #t

Both renderers then ask the same questions and follow the same answer.

Two details deserve a sentence each. The ::search suffix is set aside before the path is used as a file name, so file:notes.org::*Heading doesn’t produce a broken file name. And C:/tmp/x.txt isn’t mistaken for a link with a scheme named c, because a real scheme is lower case. Small stuff, but it’s the kind of small stuff that decides whether a program is pleasant to use on somebody else’s computer.

Org gives the element after a #+CAPTION: or #+NAME: keyword a caption and a name. When that element is a link to an image, the three things are one object: a figure. The parser folds them together, so renderers get a single node instead of three neighbors they have to guess about.

(org->html "#+NAME: fig:arch\n#+CAPTION: The architecture\n[[file:diagram.png][a diagram]]\n") ;; => "<figure id="fig:arch"><img src="diagram.png" alt="a diagram" /><figcaption>The architecture</figcaption></figure>"

The name the figure carries is the identifier that a [[fig:arch]] link resolves to, so the cross-reference can’t break. Both facts come from one place, and one place can’t disagree with itself.

(org->html "#+NAME: fig:arch\n#+CAPTION: The arch\n[[file:a.png]]\n\nSee [[fig:arch]].\n") ;; => "<figure id="fig:arch">...</figure><p>See <a href="#fig:arch">fig:arch</a>.</p>"

Markdown has no figure element, so it gets the image, the caption as an emphasised line, and an explicit anchor for the cross-reference. What counts as a figure is deliberately narrow: the keywords must sit immediately before a paragraph holding exactly one image link and nothing else. Everything else stays a keyword line. Inventing a caption for an element this parser doesn’t caption is worse than saying nothing, because the reader would never learn that something got silently dropped.

A figure is the image case of a more general rule. A #+NAME: line names the element after it, and anything that renders as something a link can land on can be named: a table, a source block, a quote, a list, a separator, a paragraph.

(org->html "#+NAME: tbl:users\n| Users | 1024 |\n\nSee [[tbl:users]].\n") ;; => "<table id="tbl:users">...</table><p>See <a href="#tbl:users">tbl:users</a>.</p>"

HTML puts the identifier on the element itself. Markdown has nothing to hang it on, so it emits an anchor in front, same as for a figure. A bare target that matches the name of an element in the same document resolves as a cross-reference, which is why [[tbl:users]] and [[notes]] work. A target that already says what it is — a scheme, a file: prefix, a leading # or *, or a ::search suffix — keeps the meaning it wrote.

One asymmetry, documented rather than hidden: a #+CAPTION: in front of a named table isn’t folded into it, because captions on tables aren’t rendered yet. The line stays an ordinary keyword line where the writer put it.

Tables looked finished until I looked at the edges. What should | on a line of its own be? What is | a ||? What happens to a row that ends the input with no newline?

The old pattern counted separators and made one cell for each, which meant a row with no cells could raise an error, and a row that ended the input got a phantom empty cell from the newline it didn’t have. The rewrite reads a row the way Org does: by the bars that separate the cells, where a bar closes a row when nothing but the end of the line follows it. That one rule answers all three questions.

An empty cell also keeps its column, because an empty value is now the empty string instead of the bare tag symbol that an empty (* ...) match leaves behind. The difference sounds academic until it is your table.

Org lets a list change its bullet type part-way through, and it lets a nested list use a different kind from its parent. So the grammar stopped having three separate list productions and grew one.

(define-peg-pattern org-list all (+ (or desc-item unordered-item ordered-item)))

The renderers group consecutive items of the same kind into the proper element, which is what makes - outer with 1. nested inside it come out as an unordered list containing an ordered one. Checkboxes, description items and arbitrary nesting depth follow from the same rule.

Between those features and the earlier work, the supported set is now: headings with TODO keywords, priorities and tags; paragraphs; unordered, ordered and description lists in any mixture and at any depth; checkboxes; tables with empty cells; source, example, quote, verse, center, export and comment blocks; keywords and in-buffer settings; comments; fixed-width lines; separators; footnotes, whether references, definitions or inline; bold, italic, underline, strikethrough, code, verbatim, superscript, subscript, escaped markup and forced line breaks; links with and without descriptions, bare URLs, images, figures, named elements and heading anchors.

That’s most of what people actually write. Not all of Org, and the manual has a section listing the gaps instead of hiding them, because a library that lies about its coverage just wastes everyone’s time.

Before optimizing anything I wanted a benchmark that could tell me whether a change helped, and that couldn’t be fooled by the change itself.

The benchmarks live in test/veritas/benchmark/scope.scm. They use the same Veritas framework as the unit suite, selected by test type so they never slow down maak test.

VERITAS_TEST_TYPE=benchmark
guix shell -m manifest.scm -- guile -L ./src -L ./test
-c '((@ (veritas runner) run-tests))'

The suite measures five workloads and prints three tables — wall clock, allocation, and the collapse pass — formatted as Markdown, ready to paste into the manual. That last part matters: a number you have to retype by hand quietly stops being true.

One wall clock reading on a laptop isn’t a measurement, it’s a rumor. The suite runs each workload five times and reports the fastest, on the theory that the other four got interrupted by a browser, a compiler, or the collector arriving at a bad moment.

It’s not statistically pure and I won’t pretend it is. It’s a lower bound on the cost of the work, measured on a machine that’s also doing other things. Allocation is the stable half and stays within a few percent; wall clock moves 10–20% between sessions. Repeat it and get a different number and you’ve found the noise, not an error. Be suspicious of anyone who reports wall clock figures without it.

Guile’s collector is good enough that you can write a parser allocating a megabyte per kilobyte of input and still call it fast, right up until it’s in a server serving several documents at once. So the suite measures the heap too. The heap is collected before each workload, and what’s reported is heap-total-allocated: every