From ebfdb1dafa430786db10dad2ef7d5467c1bdbed1 Mon Sep 17 00:00:00 2001 From: Laurenz Date: Sun, 2 Jul 2023 19:59:52 +0200 Subject: Move everything into `crates/` directory --- docs/dev/architecture.md | 171 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 171 insertions(+) create mode 100644 docs/dev/architecture.md (limited to 'docs/dev') diff --git a/docs/dev/architecture.md b/docs/dev/architecture.md new file mode 100644 index 00000000..af48401d --- /dev/null +++ b/docs/dev/architecture.md @@ -0,0 +1,171 @@ +# Typst Compiler Architecture +Wondering how to contribute or just curious how Typst works? This document +covers the general architecture of Typst's compiler, so you get an understanding +of what's where and how everything fits together. + +The source-to-PDF compilation process of a Typst file proceeds in four phases. + +1. **Parsing:** Turns a source string into a syntax tree. +2. **Evaluation:** Turns a syntax tree and its dependencies into content. +4. **Layout:** Layouts content into frames. +5. **Export:** Turns frames into an output format like PDF or a raster graphic. + +The Typst compiler is _incremental:_ Recompiling a document that was compiled +previously is much faster than compiling from scratch. Most of the hard work is +done by [`comemo`], an incremental compilation framework we have written for +Typst. However, the compiler is still carefully written with incrementality in +mind. Below we discuss the four phases and how incrementality affects each of +them. + + +## Parsing +The syntax tree and parser are located in `src/syntax`. Parsing is a pure +function `&str -> SyntaxNode` without any further dependencies. The result is a +concrete syntax tree reflecting the whole file structure, including whitespace +and comments. Parsing cannot fail. If there are syntactic errors, the returned +syntax tree contains error nodes instead. It's important that the parser deals +well with broken code because it is also used for syntax highlighting and IDE +functionality. + +**Typedness:** +The syntax tree is untyped, any node can have any `SyntaxKind`. This makes it +very easy to (a) attach spans to each node (see below), (b) traverse the tree +when doing highlighting or IDE analyses (no extra complications like a visitor +pattern). The `typst::syntax::ast` module provides a typed API on top of +the raw tree. This API resembles a more classical AST and is used by the +interpreter. + +**Spans:** +After parsing, the syntax tree is numbered with _span numbers._ These numbers +are unique identifiers for syntax nodes that are used to trace back errors in +later compilation phases to a piece of syntax. The span numbers are ordered so +that the node corresponding to a number can be found quickly. + +**Incremental:** +Typst has an incremental parser that can reparse a segment of markup or a +code/content block. After incremental parsing, span numbers are reassigned +locally. This way, span numbers further away from an edit stay mostly stable. +This is important because they are used pervasively throughout the compiler, +also as input to memoized functions. The less they change, the better for +incremental compilation. + + +## Evaluation +The evaluation phase lives in `src/eval`. It takes a parsed `Source` file and +evaluates it to a `Module`. A module consists of the `Content` that was written +in it and a `Scope` with the bindings that were defined within it. + +A source file may depend on other files (imported sources, images, data files), +which need to be resolved. Since Typst is deployed in different environments +(CLI, web app, etc.) these system dependencies are resolved through a general +interface called a `World`. Apart from files, the world also provides +configuration and fonts. + +**Interpreter:** +Typst implements a tree-walking interpreter. To evaluate a piece of source, you +first create a `Vm` with a scope stack. Then, the AST is recursively evaluated +through trait impls of the form `fn eval(&self, vm: &mut Vm) -> Result`. +An interesting detail is how closures are dealt with: When the interpreter sees +a closure / function definition, it walks the body of the closure and finds all +accesses to variables that aren't defined within the closure. It then clones the +values of all these variables (it _captures_ them) and stores them alongside the +closure's syntactical definition in a closure value. When the closure is called, +a fresh `Vm` is created and its scope stack is initialized with the captured +variables. + +**Incremental:** +In this phase, incremental compilation happens at the granularity of the module +and the closure. Typst memoizes the result of evaluating a source file across +compilations. Furthermore, it memoizes the result of calling a closure with a +certain set of parameters. This is possible because Typst ensures that all +functions are pure. The result of a closure call can be recycled if the closure +has the same syntax and captures, even if the closure values stems from a +different module evaluation (i.e. if a module is reevaluated, previous calls to +closures defined in the module can still be reused). + + +## Layout +The layout phase takes `Content` and produces one `Frame` per page for it. To +layout `Content`, we first have to _realize_ it by applying all relevant show +rules to the content. Since show rules may be defined as Typst closures, +realization can trigger closure evaluation, which in turn produces content that +is recursively realized. Realization is a shallow process: While collecting list +items into a list that we want to layout, we don't realize the content within +the list items just yet. This only happens lazily once the list items are +layouted. + +When we a have realized the content into a layoutable element, we can then +layout it into _regions,_ which describe the space into which the content shall +be layouted. Within these, an element is free to layout itself as it sees fit, +returning one `Frame` per region it wants to occupy. + +**Introspection:** +How content layouts (and realizes) may depend on how _it itself_ is layouted +(e.g., through page numbers in the table of contents, counters, state, etc.). +Typst resolves these inherently cyclical dependencies through the _introspection +loop:_ The layout phase runs in a loop until the results stabilize. Most +introspections stabilize after one or two iterations. However, some may never +stabilize, so we give up after five attempts. + +**Incremental:** +Layout caching happens at the granularity of the element. This is important +because overall layout is the most expensive compilation phase, so we want to +reuse as much as possible. + + +## Export +Exporters live in `src/export`. They turn layouted frames into an output file +format. + +- The PDF exporter takes layouted frames and turns them into a PDF file. +- The built-in renderer takes a frame and turns it into a pixel buffer. +- HTML export does not exist yet, but will in the future. However, this requires + some complex compiler work because the export will start with `Content` + instead of `Frames` (layout is the browser's job). + + +## IDE +The `src/ide` module implements IDE functionality for Typst. It builds heavily +on the other modules (most importantly, `syntax` and `eval`). + +**Syntactic:** +Basic IDE functionality is based on a file's syntax. However, the standard +syntax node is a bit too limited for writing IDE tooling. It doesn't provide +access to its parents or neighbours. This is a fine for an evaluation-like +recursive traversal, but impractical for IDE use cases. For this reason, there +is an additional abstraction on top of a syntax node called a `LinkedNode`, +which is used pervasively across the `ide` module. + +**Semantic:** +More advanced functionality like autocompletion requires semantic analysis of +the source. To gain semantic information for things like hover tooltips, we +directly use other parts of the compiler. For instance, to find out the type of +a variable, we evaluate and realize the full document equipped with a `Tracer` +that emits the variable's value whenever it is visited. From the set of +resulting values, we can then compute the set of types a value takes on. Thanks +to incremental compilation, we can recycle large parts of the compilation that +we had to do anyway to typeset the document. + +**Incremental:** +Syntactic IDE stuff is relatively cheap for now, so there are no special +incrementality concerns. Semantic analysis with a tracer is relatively +expensive. However, large parts of a traced analysis compilation can reuse +memoized results from a previous normal compilation. Only the module evaluation +of the active file and layout code that somewhere within evaluates source code +in the active file needs to re-run. This is all handled automatically by +`comemo` because the tracer is wrapped in a `comemo::TrackedMut` container. + + +## Tests +Typst has an extensive suite of integration tests. A test file consists of +multiple tests that are separated by `---`. For each test file, we store a +reference image defining what the compiler _should_ output. To manage the +reference images, you can use the VS code extension in `tools/test-helper`. + +The integration tests cover parsing, evaluation, realization, layout and +rendering. PDF output is sadly untested, but most bugs are in earlier phases of +the compiler; the PDF output itself is relatively straight-forward. IDE +functionality is also mostly untested. PDF and IDE testing should be added in +the future. + +[`comemo`]: https://github.com/typst/comemo/ -- cgit v1.2.3