org-lsp

The parser

server/org-syntax is a hand-written parser. It has no dependency on the language server and can be used on its own.

Shape of the tree#

The parser produces a lossless rowan tree. Every byte of the input is in exactly one token, so the tree always prints back to the input, and every node knows its source range. parse never fails.

Parsing follows org-element.el:

  • Headlines are found first, by line prefix alone. That fixes the outline.
  • Each section is parsed into elements in the order org-element--current-element tries them. Blocks, drawers and LaTeX environments are only elements when their closing line exists.
  • What ends a paragraph is decided by a separate, looser rule than what starts an element, as in Org.
  • Affiliated keywords (#+NAME:, #+CAPTION:, #+ATTR_*: …) are the leading children of the element they belong to.
  • Inline objects follow org-element-object-restrictions: for example a link description cannot contain another link.

The document is parsed again in full on every change. In a release build, a 2 KB file parses in about 0.1 ms and a 4 MB file with 177,000 lines in about 130 ms.

Conformance#

The reference is Org 9.8.10, the latest release, not the older Org bundled with Emacs. Set ORG_LISP_DIR to the lisp directory of an Org checkout and the scripts below use that version.

tests/fixtures/*.org are parsed by both this parser and Emacs (scripts/org-element-dump.el). The test server/org-syntax/tests/org_element.rs requires the same set of elements and objects, with the same types, at the same positions, and for every headline the same keyword, priority, tags and title.

scripts/fuzz-against-emacs.py does the same for randomly generated documents. Several thousand have been compared.

Known differences from org-element:

  • A priority cookie holds a capital letter or a number. Org's expression also takes a small letter ([#a]) when it runs with case folding on, which depends on the command: the parser does, the agenda does not. Here a small letter is never a priority.
  • Org takes the first priority cookie on the headline, wherever it is, and drops what stands before it from the title (* foo [#A] bar has the title bar). The cookie is a priority here too; the text before it stays in the tree as plain text.
  • Radio links (text that matches a <<<radio target>>> elsewhere) are not recognised by the parser; the server finds them itself.
  • Inline tasks are not recognised; they parse as headlines, which the server tells apart by their stars (org_inlinetask_min_level).
  • Line breaks (\\ at the end of a line) are not a separate node.
  • Citations are a single node: their references are not split out, and objects in their prefixes and suffixes are not parsed.
  • A #+TBLFM: line that follows a table inside a list item, but is indented less than the item, ends the item here. In Org the table reaches past the end of the item that contains it.
  • A document that is nothing but blanks without a line end has no paragraph here; Org makes one.

Limits#

Nesting is capped at 64 levels for elements (blocks, drawers, list items) and for objects (emphasis, footnotes). Anything deeper is kept as plain text. Searches for closing delimiters are memoised, so documents with thousands of unclosed openers still parse in linear time. tests/robustness.rs covers both.

Tools#

cargo run -p org-syntax --example dump -- file.org           # print the tree
cargo run --release -p org-lsp --example timing -- file.org   # time it
scripts/update-fixtures.sh                                    # needs Emacs
scripts/update-entities.sh                                    # needs Emacs
scripts/fuzz-against-emacs.py --count 500 --seed 1            # needs Emacs