Skip to the main content
mkfifo.com

Stream parsers and selector lines

Updated planned discovered changed

Each streaming parser of mkfifo.com has one shape. On that shape came a JSON tokenizer, then selector lines that read the values of a JSON or HTML body, later one read of the body for all the envelopes of a FIFO, and last the HTML part of an email.

One shape for stream parsers

I wanted a streaming Markdown parser, and saw that it looks like the multipart parser. Each streaming parser here keeps only the bytes that it cannot decide yet. So they got one shape.

The shape

The shape of TransformStream of the web: init, transform and flush (FIFO.Transform). The multipart parser, the header of a MIME part, and the decoders of base64 and quoted-printable are steps of this shape now. One shared property test checks each step: all splits of an input into chunks give the same output, and the step keeps few bytes.

Bugs that the test found

  • My first stream decoder of quoted-printable removed the spaces before an = that it kept at the end of a chunk.
  • An =, a CR and a space before the LF is a soft line break too.

After the fixes, a check of all the texts of up to 6 characters, with all their splits into three chunks, found no more difference.

A changed limit

The limit of a text part of an email (4 MiB) now counts the bytes after the decode of base64 or quoted-printable, because the decoders work on the stream.

Markdown

The Markdown converter of this blog was the first new step of this shape, and egress envelopes can use it now.

  • The converter keeps the last line and one block. On 200,000 random texts with random splits, it gave the same HTML as the converter before it.
  • {{note | markdown}} in an HTML body gives the capture as Markdown. A form can send a message with a list and links, and the HTML email shows them.
  • An email with Content-Type: text/markdown has a plain text part and an HTML part. The Markdown is the text of the envelope, and a capture is only text in it (see The rules of an envelope).
  • The filter in any other place is an error at the save.

Later: tables

On 6 October I put a table in two posts, and the blog showed rows of pipes and dashes in one paragraph. My converter did not know tables. Now it reads the tables of GitHub, in the blog, in the FIFO markdown and in an email of text/markdown.

A table is hard for a stream. Its header row looks like a line of a paragraph until the next line comes: a row of --- cells. So the header waits in the paragraph, as each line of a paragraph does. When a row of --- cells comes, with the same number of cells, the last line of the paragraph becomes the header. The converter still keeps only the last line and one block. The property test now puts |, --- and : in its chunks, and each split still gives the same HTML.

On a phone, a wide table scrolls in its place, and the page does not.

Later: quotes and images

I wanted quotes and images in the posts, and the converter knew neither. A line that starts with > is a line of a quote now, and a line with only > starts a new paragraph in it. The quote ends at an empty line, or at a line with no >. CommonMark continues a paragraph of the quote on such a line, but then the converter must keep more than one block.

![alt](url "title") is an image. The URL must start with https://, or with / for a path of the site. A path that starts with // or /\ goes to a different host in a browser, so it is not a path of the site. An image alone in a paragraph is a figure, and its title is the caption. The alt text and the title get the escapes of HTML, as each text does.

A page of Markdown could show only the images of the site: its Content-Security-Policy had img-src 'self' data:. Now it also has https:, so a page can show an image of a different site. Then that site sees the network address of each person who opens the page, and the privacy page tells this. The Referrer-Policy of a page sends only https://mkfifo.com/ to that site, not the path of the page.

The live view of Markdown in the editor follows the same rules, so a quote and an image get their styles there. The property test of the splits now has > and parts of images in its chunks, and each split still gives the same HTML.

A streaming JSON tokenizer

To read values out of a JSON body while it streams, I wrote a tokenizer that gives each value with its path.

Why my own

Jaxon streams JSON, but its last release is from 2021. The JSON module of OTP can continue a decode with more bytes, but it gives no path while it reads, and it keeps each string whole.

Model first

specs/JSONTokens.tla tells which bytes the tokenizer keeps at the end of a chunk. TLC finds the two faults: a number that goes out at the end of a chunk (11 in two chunks gives two numbers), and a backslash that goes out as a character.

My first version of the model had a bug of its own: at the end of the text, it compared an open string with an error. TLC showed it at once.

Tests against other code

  • Random JSON texts give the value of JSON.decode/1.
  • Random values through JSON.encode!/1 come back the same.
  • All the texts of up to 4 symbols, with all their splits into three chunks, give the same events.

Limits: 64 levels of objects and arrays, a key of 1 KiB, a number of 64 bytes.

Later: the JSON module of OTP

The stress test showed that a JSON body with selector lines was the slowest request in WebAssembly. But the body of a Request is in memory anyway (at most 1 MiB), so the stream saved nothing there. Now the selector lines decode the body with :json.decode/3 of OTP and walk only the parts that a path can find. Natively that is 3.6 times faster for a body of 200 KB; in WebAssembly, the selector went from about 55 ms to 35 to 45 ms. The interpreter is the limit now.

Two details:

  • The callbacks of :json keep the order of the keys and the limits of my tokenizer. But :json does not always give the text of a number: -0 becomes 0, and 1E2 becomes 1.0e2. The value of a number is its text in the body, so for those two forms only, a scan of the body gives the text.
  • A property test compares the new code with the old code on my tokenizer, with random JSON, parts of JSON, and bytes in the wrong place. 20,000 runs found no difference.

The tokenizer stays, for a body that streams.

Selector lines

An ingress envelope can now read the values of a JSON or HTML body:

$.order.id: ^(?<order>\d+)$
$.items[*].sku: (?<skus>.+)
$("td.code"): ^(?<code>[A-Z0-9]+)$

Why

A body line on JSON, such as "full_name":\s*"(?<repo>[^"]+)", breaks on an escaped quotation mark, and it finds the key at any depth. A path does not.

The syntax

$ for both. A JSON path starts with $ (a part of RFC 9535), and $("...") reads as in jQuery. The values work as a header field: more values are joined with a comma, and no value is an empty value. So $.coupon: ^$ accepts only an order with no coupon.

HTMLRewriter, later

I like HTMLRewriter of Cloudflare: it finds elements with CSS selectors while the HTML streams. But the VM cannot call a function of the Worker yet. So the CSS part uses lazy_html for now, behind one function, and I wrote a proposal for BEAM.com: functions of the host that Elixir can call.

Found on the way

  • A CSS selector can have spaces and colons: $("a:first-child > b"). So the name of a selector line ends at the first colon that is not in quotation marks, brackets or parentheses. The round-trip test of the envelopes then made the name $[, which has no end now. That test makes selector lines separately.
  • A random key of more than 1 KiB hit the limit of the tokenizer, so the selector had no value. The limit is correct. The test makes smaller keys now.
  • I ran it in the Worker, with the VM in WebAssembly: a JSON order and an HTML table both gave their values.

One read of the body

A FIFO can have many ingress envelopes, and mkfifo.com tests a Request with each of them. Until now, each envelope with selector lines ($.id, $("h1")) or with the fields of a JSON body read the body again. A FIFO with 16 such envelopes decoded a JSON body of 1 MiB 16 times, or made 16 HTML documents of it.

Now the body is read one time for all the envelopes of the FIFO. Before the test, mkfifo.com collects the selectors and the JSON paths of all the envelopes. At the first line that needs a value, one decode of JSON gives the values of all the JSON paths, and one HTML document gives the values of all the CSS selectors. The test of each next envelope uses these values. Two envelopes with the same selector have one value: the text of a selector is its key, and the name of a field gives its JSON path.

The read is still lazy. mkfifo.com examines the header lines first, so when Content-Type or Subject does not agree in any envelope, it does not read the body. And an envelope still stops at its first line that does not agree.

On my computer, natively, 16 envelopes and a JSON body of 765 KB took 355 ms before and 22 ms now. With a body of 1 MB of HTML, 542 ms before and 29 ms now. "Try" in the editor uses the same read for its marks.

A test counts the reads: it traces the calls of FIFO.Selector.values/2 while 16 envelopes test one Request, and expects one call. A process that traced itself got no trace messages, so the test runs the work in a different process, and waits for erlang:trace_delivered/1 before it counts the messages.

Not the FIFOs before

The list of ideas had one more item for the graph: the editor shows the next FIFOs of each egress envelope, and it could also show the FIFOs that send to this FIFO. It will not. Many FIFOs can send to one FIFO, for example to /bin/sh, and most of them are FIFOs of other persons. Their names are their keys, so the owner of the FIFO must not see them.

The HTML part of an email

The first use case of mkfifo.com was a movie ticket: the cinema sends an email, and a FIFO sends the code and the link on. I had never run a real ticket email through it. So I wrote five fake ones, in the shapes that cinemas send: text and HTML in quoted-printable, HTML only in base64, a forward by hand, an automatic forward, and the email that asks you to confirm a forward address.

Two things failed.

Text or HTML

Most emails have a plain text part and an HTML part. The body of the Request was the plain text, so $("td.booking-code") found nothing in them. Only an email with no plain text had HTML in its body.

Now an envelope says which part it reads, with the line that already tells the type of a body: Content-Type: text/html. That envelope reads the HTML part, and sees Content-Type: text/html; charset=utf-8. The other envelopes read the plain text, as before, so no envelope changed. When a FIFO has both kinds, mkfifo.com reads the body one time for each kind, not one time for each envelope.

An envelope is for text/html when each of its Content-Type patterns matches text/html, one or more do not match text/plain, and no pattern has a variable. html is enough. text is not, because it matches plain text too.

Attributes

The link to an e-ticket, or the link that confirms a forward address, is in the href of the link, not in its text. $("a.eticket").attr("href") gives it now, with the syntax of jQuery.

Found in the tests

  • A <td> outside a table is not an element: the HTML parser drops the tag and keeps the text. One of my small test emails had a lone <td>, and its selector found nothing.
  • An email with only HTML and a PDF has the type multipart/mixed, so Content-Type: text/html did not match it at first. Now the envelope for text/html gets the HTML part of each email that has one.
  • An egress envelope gets the captures, not the body. So nothing after the ingress envelope needs to know which part it read.