Prism: Ruby 3.3's new error-tolerant parser

Prism is a new library shipping as a default gem in Ruby 3.3.0 that provides access to the Prism parser, a new parser for the Ruby programming language. Prism is designed to be error tolerant, portable, maintainable, fast, and efficient.

Usage

To use the Prism parser through the Ruby bindings, you would require the prism library and the call any of the various parse methods on the Prism module. For example:

require "prism"
Prism.parse("1 + 2")

This method will return to you a parse result object, which contains the syntax tree corresponding to the parsed source code, lists of errors, warnings, and comments, as well as various other metadata related to the parse operation. Importantly this method will always return a parse result (as opposed to raising an exception when a syntax error is found), which makes it suitable for working on source code that may contain syntax errors.

History

Prism was originally designed in 2021. It originated at Shopify, where the need for a fast and efficient error-tolerant parser became quite evident. In 2021, Shopify was already heavily invested in CRuby, TruffleRuby, Sorbet, and various Ruby tooling. In total, Shopify developers were helping to maintain four different parsers for the Ruby programming language. This was a lot of work, and it was clear that the community would benefit from a single parser that could be used by all of these projects.

In consultation with the maintainers of all of these projects and more, the project went through various prototyping and design phases before eventually landing on the current design. This progressed over the course of a year and a half to get us to where we are today. In that time the project has been open sourced, and has been integrated into various projects in the Ruby ecosystem.

Design

As mentioned, Prism is designed to be error tolerant, portable, maintainable, fast, and efficient. The parser and nodes therein are designed to be as simple as possible to deal with from the perspective of an implementation or tooling. We will discuss each of these design goals in turn.

Error tolerance

Since Microsoft created Visual Studio Code and the language server protocol, error tolerance has been much more in the spotlight for programming languages. It has become tablestakes for a good developer experience that the parser powering your editor is able to parse code that contains syntax errors, because most of the time that code is being written it is not in a completed state. Prism was designed and hand-written with error tolerance in mind for this reason. At a minimum, with a file containing myriad syntax errors, Prism will always return a list of the top-most statements.

As Prism has been developed, the team has worked closely with the team designing Ruby LSP, a language server for Ruby. This has allowed the developers to ensure that Prism is able to parse the code that Ruby LSP is sending it, and that the errors Prism is returning are useful to the end user. As we continue this work in Ruby 3.4.x, we will continue to iterate on and improve the error tolerance of Prism.

Portability

Prism was designed to be a replacement for all of the various parsers that had been developed over the years of Ruby’s lifetime. This includes CRuby’s parser, but also the parsers of all of the other Ruby implementations and third-party tools. Because of this, the developers of Prism have been consulting from the beginning with the maintainers of JRuby, TruffleRuby, IRB, and various other implementations and tools.

To that end — CRuby, JRuby, TruffleRuby, and Natalie have all integrated Prism as a replacement for their existing parsers. Within CRuby (the default Ruby implementation) it ships as an optional parser. JRuby and TruffleRuby are both working on making it their default parsers in their next version. Natalie has already made it their default parser.

Over the course of the Ruby programming language’s lifetime, there have been various other third-party parsers that have been developed. This includes whitequark/parser and seattlerb/ruby_parser. Both of these parsers have powered various tools and libraries over the years, including big names in the ecosystem like rubocop. We have been working with the developers of these tools to provide alternate options to include Prism as a backend in order to fully integrate the entire ecosystem into one cohesive effort.

Prism is a standalone library with no dependencies, which makes it easy to also ship bindings to other languages. As of writing this article, Prism is already powering tooling written in Ruby, C, C++, Rust, Java, and JavaScript. We are actively working with maintainers of libraries in all of these languages to ensure that Prism is a viable option for them.

Maintainability

Prism was designed to be as maintainable as possible in order for it to last as the default parser for the community. To that end, every node and field in the entire syntax tree is documented with comments and tests. Additionally a whole blog series has been written about the design and implementation of Prism to provide additional context. We hope that by continuing to invest in the maintainability of Prism, we can provide the community with a basis for all kinds of excellent developer tooling for years to come.

Parser design

Prism is a hand-written recursive descent parser. It is written in C99, and is designed to be portable to any platform that Ruby supports. It is structured as a large Pratt parser, with additional modification when the Ruby grammar changes precedence or associativity rules.

In general, Prism parses a superset of valid Ruby code. For example, in addition to parsing a constant path in the place of the name of a class, it will also parse any valid expression beginning with a constant. This would look like:

class foo.bar
end

We do this to enable good error recovery. By allowing the parser to parse expressions where they would normally not be permitted, we can recover from errors in a way that is more useful to the end user.

It is also beneficial to parse a superset because of incremental parsing. Incremental parsing refers to the ability to parse a subset of a file as it is being written. By parsing any kind of expression in any position (like above), we enable tools to represent more of the syntax tree even when it is in an invalid form. This becomes particularly important for linters and type checkers because they do not have to discard as much information whenever the file changes.

If you take the example from above, even though foo.bar is in an invalid location in the parse tree, typecheckers and linters can still process the method call as if it were valid. Then, if the user types additional characters to make it valid, the tool can keep around the method call node without having to reprocess it.

Node design

The nodes in Prism’s syntax tree are designed to make it as simple as possible to compile, while retaining enough information to be able to recreate the source code at any point. With this in mind, Prism splits up a lot of nodes that other syntax trees general keep together to make their intention as clear as possible. For example the following code:

@foo = 1
for @foo in 1..10 do end

In both of the lines above, the @foo instance variable is being written to. In the first line it is being written directly with the value of 1, in the second line it is being written indirectly with the current value of the iteration of the loop. In other syntax trees, this is usually represented with a single node type (instance variable write) with an optional value attached. This means that in order to compile and understand the node, the consumer always has to check if a value is present. In Prism, we split up these two cases into two separate nodes: InstanceVariableWriteNode and InstanceVariableTargetNode. The first node is used for direct writes, and the second node is used for indirect writes.

With these splits in place, the resulting compiler within CRuby ends up being a “flatter” compiler because there are fewer nested branches to deal with. This is intentional; one of the key tenets of designing the Prism nodes is that you never have to consult a child node to determine how to compile the parent node. We believe this will make it easier to maintain and extend the compiler in the future. We also end up saving on space because we don’t end up storing any null values in the nodes where it’s not possible for them to have a value.

Speed and efficiency

Lots of benchmarking has been done to ensure that Prism is as fast as possible and as efficient with memory as it can be, though there is a lot of room for improvement here. We have been benchmarking by parsing large suites of Ruby code and measuring both the time it takes to parse on its own, as well as the time it takes to reify the syntax tree into Ruby. This work will continue in the new year.

Testing

It has been massively important to our development efforts to build a robust test suite for Prism. Various test suites have been created over the years for the Ruby programming language, but few — if any — have been built with a parser in mind. In addition to our own set of fixtures that we have built over the regular course of development, we have also vendored parser test suites from whitequark/parser and seattlerb/ruby_parser. We have also been testing against the latest version of every released gem on rubygems.org, which has been a great source of bugs and edge cases.

In testing, we have used a combination of many different forms of tests. The first is regression tests: we take snapshots of syntax trees that are the result of parsing fixtures and on subsequent runs of the test suite we compare them against the saved version. This is useful for ensuring that we do not regress on syntax trees that we have already parsed correctly. The second is manual unit tests addressing both particular functionality and error tolerance. These are useful for testing specific edge cases and for ensuring we are able to recover from errors in a consistent manner. Finally, we have small test suites for specific features like regular expressions, encodings, and escape sequences. These test suites employ brute-force testing (i.e., testing every possible combination of values). For example, with encodings we test every codepoint in every encoding. These test suites ensure those concerns are handled correctly.

Finally, it has been very important to fuzz the various inputs to the Prism parser. As with any C project, there are many ways to introduce memory corruption bugs. We use AFL++ to fuzz the parser and lexer to ensure we never crash or read off the ends of the input. In conjunction with ASAN and various other memory sanitizers, we have been able to ensure that Prism is as stable as possible.

Challenges

There are many challenges in working with Ruby source code. The grammar itself is very complicated, and has been extended many times over the years. Beyond this, there are some specific challenges that we have faced in developing Prism.

Local variable reads and method calls are indistinguishable when they are represented using a single identifier. Unfortunately, this becomes quite significant because an identifier being a local variable can change the shape of the parse tree. As such, all local variable scopes must be resolved at parse time. Normally, this wouldn’t be particularly difficult. But certain structures can introduce local variables that are more complex than simple writes. As an example, regular expressions with named capture groups can introduce or modify local variables. The implication is that in order to properly parse Ruby code, Prism must therefore have a regular expression parser that parses as CRuby does. In code, this looks like:

/(?<foo>bar)/ =~ "bar"
foo / bar#/

In the code above, the first line introduces a local variable foo that is then used in the second line. The second line is a method call to the / method with bar as an argument. However, if foo is not introduced, this will be parsed as a method call to foo with a regular expression as an argument. This is a very subtle distinction, but it illustrates the importance of having all of the local variables resolved at parse time.

Source code in Ruby can be encoded in any of the 90 ASCII-compatible encodings that CRuby supports. Therefore in order to properly parse Ruby code, Prism has to explicitly support every encoding that CRuby does. Fortunately it is only a subset of the functionality; just enough to determine if the subsequent bytes form an alphabetic, alphanumeric, or uppercase character. In code, this looks like:

# encoding: Shift_JIS

The name of the encoding can be any of the 154 aliases for the ASCII-compatible encodings. This must be resolved as soon as the encoding comment is encountered to ensure all subsequent strings and identifiers are parsed correctly.

Finally, Ruby has a very rich set of escape sequences that can be used in strings and regular expressions. These escape sequences can be used to represent any Unicode codepoint, as well as various other special characters. In order to properly parse Ruby code, Prism has to support all of these escape sequences and return the exact bytes that they represent. This makes it easier on individual implementations as they no longer have to parse escape sequences, but makes it more difficult to maintain on the Prism side.

APIs

Many APIs exist in Prism beyond just parsing that can be useful to a developer creating tooling on top of the Ruby syntax tree. Some APIs are novel, and exist to provide additional information. Others are replacements for existing workflows that have never had a standard API before.

One such existing workflow was to find all of the comments in a source file. Usually this was done with Ripper, but you can accomplish the same with Prism with less effort:

Prism.parse_comments(<<~RUBY)
# foo
# bar
RUBY

This will result in an array of comments, which looks like:

# =>
# [#<Prism::InlineComment @location=#<Prism::Location @start_offset=0 @length=5 start_line=1>>,
#  #<Prism::InlineComment @location=#<Prism::Location @start_offset=6 @length=5 start_line=2>>]

Another common workflow was to determine if a source file was valid or not. This was frequently accomplished using either Ripper or RubyVM::InstructionSequence. Prism provides a simpler API for this:

Prism.parse_success?("1 + 2") # => true
Prism.parse_success?("1 +") # => false

By providing these additional APIs, it makes it easier for the consumer to write less code and to have a more consistent experience across different versions of Ruby.

Every node in the syntax tree itself has a common set of APIs as well. All nodes have their own class (as opposed to every other Ruby syntax tree which tends to use a single class with a type attribute). These classes all respond to their own named fields for children and attributes. Additionally they all respond to #child_nodes (which includes nil values) and #compact_child_nodes (which does not include nil values) to gather up all child nodes contained in the current parent node. You can leverage this common interface to walk over every node in the syntax tree:

def walk(node, indent = 0)
  puts "#{" " * indent}#{node.type}"
  node.compact_child_nodes.each { |child| walk(child, indent + 2) }
end

walk(Prism.parse("foo.bar(1); baz(2)").value)

The above code will output the following tree-like structure:

program_node
  statements_node
    call_node
      call_node
      arguments_node
        integer_node
    call_node
      arguments_node
        integer_node

Each node also responds to #copy, which is useful for treating nodes as immutable and generating new nodes with certain fields overridden. They all implement pattern matching with #deconstruct and #deconstruct_keys. Finally they all respond to #location, which allows the user to determine the exact location in the source code that the node was parsed from.

For working with subsets of nodes, nodes all implement the #accept method, which accepts a visitor object. Visitors implement the double-dispatch visitor pattern to allow for easy traversal of the syntax tree. Prism ships with Prism::Visitor and Prism::Compiler to provide a common set of visitors for common use cases. The Prism::Visitor class is useful for finding subsets of the nodes or generally querying output. The Prism::Compiler class is useful for transforming the syntax tree into a different form, like a bytecode or other representation. As an example, if you wanted to find all method calls in a syntax tree, you could:

class MethodCallFinder < Prism::Visitor
  attr_reader :calls

  def initialize(calls)
    @calls = calls
  end

  def visit_call_node(node)
    super
    calls << node.name
  end
end

calls = []
Prism.parse("foo.bar.baz").value.accept(MethodCallFinder.new(calls))

calls
# => [:foo, :bar, :baz]

Prism ships with some visitors and compilers already built in, which are useful on their own and as examples of manipulating the tree. It ships with the ability to convert syntax trees into a directional graph in the Graphviz format. It also provides a Prism::DesugarCompiler, which “desugars” syntax into equivalent syntax using fewer node types. Finally, it provides a Prism::MutationCompiler, which allows users to modify syntax trees like you would to provide automated refactoring.

Future work

Now that we are shipping with Ruby 3.3.0, we will continue to develop Prism in harmony with the Ruby community to produce the best possible foundation for Ruby tooling going forwarding. In service to that goal, there are many directions that we are looking to take Prism in the future.

The first major goal of Prism is to achieve exact parity with CRuby’s current parser. Today, Prism parses all valid Ruby correctly, but there are still some edge cases where it fails to reject invalid Ruby code. We are working to close this gap as quickly as possible, and intend on having it closed by the time Ruby 3.4.0 ships. There are additionally some warnings, niceties in terms of error message ergonomics, and tweaks to error recovery that we are working on to ensure CRuby does not lose any functionality (like specific error recoveries or warnings) when and if they switch to using Prism as the default parser.

The second major goal of Prism in the new year is to increase adoption within the community. While we have already integrated many major tools and implementations, there are still many more places in the ecosystem that could benefit from Prism. This includes implementations like mruby and tools like Sorbet. We hope this year to work with the maintainers of these projects to ensure that Prism is a viable option for them.

Thirdly, we would like to improve documentation and the general developer experience when working with Prism. While we have worked hard to make this a good experience from the start, there is always room for improvement here. Ideally we would like to lower the bar as much as possible to make it approachable for anyone (regardless of experience level) to contribute to Prism.

Finally, we plan to spend time this year working on performance. While Prism is already quite fast, there are still some areas where we can improve. We will be looking at SIMD instructions and other low-level optimizations to optimize for specific target platforms. We will also be looking at optimizing memory layout and allocations to reduce the overall memory footprint of Prism.

Overall, we are very excited about Prism and the future of Ruby tooling that it enables. Already we are seeing a plethora of new tools and libraries being developed on top of Prism, and we hope that this trend continues with the release of Ruby 3.3.0.