Interactive implementation of the TeX typesetting algorithm

Published on

The algorithm that TeX (and various extensions based on it like LaTeX) uses, provides the currently unmatched standard of mathematical typesetting. Various implementations of it exist, including modern implementations like KaTeX that target web browsers. This makes it easy to include math on websites:

When rendering average-sized documents with TeX engines like XeTeX or LuaTex, it is normal for it to take several seconds for the typesetting to be finished. This is in stark contrast to the time that web browsers or most GUI’s need to fully layout and present the average website or application, which is often measured in mere milliseconds. To provide a positive user experience in interactive applications, it is absolutely necessary to have interactive timescales determined by the refresh rate of display devices (about 16 ms with the average refresh rate of 60 frames per second). This categorically excludes any TeX engine from direct usage for any interactive purpose, as their latencies are many orders of magnitude too large.

A clever solution used by Manim to create TeX animations is to render individual frames with classical TeX engines and stitch them together in an animated video format. The created animations are smooth, but non-interactive as the latency between the drawing instructions and the animation being finished still takes many seconds.

Goal

The goal is to implement a Rust crate that allows TeX typesetting, but also supports interaction and animation with the typeset output. KaTeX is very fast for individual equations, but the output isn’t meant to be interacted with, and interaction falls way outside the problem domain it tries to solve. Besides, it doesn’t even do full typesetting, as it outputs a DOM object that still needs to be typeset further by the web browser. This makes it impossible to use KaTeX from a context in which web typesetting is not available, or desirable.

A complete typesetting implementation must transform some abstract syntax tree into some list of glyphs, each correctly positioned and scaled with respect to some reference point. This requirement of how the data is transformed naturally leads to a type-signature for the algorithm like:

fn typeset(ast: &Ast) -> Vec<PositionedGlyph>;

Note that web applications aren’t excluded by choosing Rust, as it compiles to WebAssembly.

Progress

A good design decision that KaTeX made, and we simply copy, is to completely abandon the ancient TeX font situation. TeX predates the Unicode standards, and modern font formats by several decades. It even predates the IEEE 754 floating-point representation, just to really show its age. Several PR’s to KaTeX (#3713, #3714, #3715) are currently waiting to be accepted upstream. These first steps update font generation from Perl scripts to Python scripts, so that we can later easily add required features like kerning to the font files.

For the Rust implementation of the TeX algorithms we can simply refer to the TeXbook that describes quite verbosely everything we need to know. We don’t need to implement everything in the book, as TeX does much more than just typeset and is actually a Turing-complete programming language. This is actually one of the reasons why TeX engines are relatively slow.

The easy part of the book describes how boxes (chapter 11) and glue (chapter 12) work to provide us the relative positions between glyphs. The more complicated logic is the transformation of math lists to horizontal lists described in great detail in appendix G. All of this has been mostly implemented.

Current work

Currently the issue is to figure out how font selection works and to provide a way to actually visually debug the output. Subsequently the next issue will probably be to fix the logical bugs that will be discovered by the previously mentioned visual debugging capabilities.

Future work