Rope science, part 11 – practical syntax highlighting (2017)

Summary

23 Apr 2017 In this post, we present an incremental algorithm for syntax highlighting. It has very good performance, measured primarily by latency but also memory usage and power consumption. It does not require a large amount of code, but the analysis is subtle and sophisticated. Your favorite code editor would almost certainly benefit from adopting it. Pedagogically, this post also gives a case study in systematically transforming a simple functional program into an incremental algorithm, meaning an algorithm that takes a delta on input and produces a delta on output, so that applying that delta gives the same result as running the entire function from scratch, beginning to end. Such algorithms are the backbone of xi editor, the basis of near-instant response even for very large files. The syntax highlighting function Most syntax highlighting schemes (including the TextMate/Sublime/Atom format) follow this function signature for the basic syntax highlighting operation (code is in pseudo-rust): fn syntax (previous_state, line) -> (next_state, spans); Typically this “state” is a stack of finite states, i.e. this is a pushdown automaton. Such automata can express a large family of grammars. In fact, the incredibly general class of LR parsers could be accomodated by adding one additional token of lookahead in addition to the line, a fairly straightforward extension to this algorithm. I won’t go into more detail about the syntax function itself; within this framework, the algorithms described in this post are entirely generic. A batch algorithm The simplest algorithm to apply syntax highlighting to a file is to run the function on each line from beginning to end: let mut state = State::initial(); for line in input_file.lines() { let (new_state, spans) = syntax(state, line); output.render(line, spans); state = new_state; } This algorithm has some appealing properties. In addition to being quite simple, it also has minimal memory requirements: one line of text, plus what...