Code scanning and Ruby: turning source code into a queryable database

From Ruby source to a queryable database

CodeQL analyzes code by running queries against a database that is built from the source of a program. The database construction phase is handled by a component called an extractor, which parses the source code, converts the resulting parse tree into a relational form, and writes those relations to disk. A schema is also required, defining the names of the database tables and the types of columns they contain.

The general flow is depicted below:

Parse trees and ASTs

Source code is text, and to analyze it meaningfully you need to transform that text into a parse tree (also called a concrete syntax tree). For a program that prints two greetings:

puts("Hello", "Ahoy")

the relevant syntax consists of two string literals and a method call to puts. A minimal parse tree for this code would contain an expression for each literal and one for the call. The structure is shown here:

Many compilers and static analysis tools convert the parse tree into an abstract syntax tree (AST) that discards details like whitespace and parentheses. CodeQL's Ruby extractor instead stores the full parse tree in its database, because syntactic details can occasionally be useful. Queries operate on an AST layer built on top of that raw tree.

Parser selection

Each language CodeQL supports uses a different parser. For C# the extractor uses the Roslyn compiler; for JavaScript it uses a parser derived from Acorn. For Ruby, the choice was tree-sitter and its dedicated Ruby parser. Tree-sitter is a fast parser framework with good error recovery that also powers syntax highlighting and code navigation on GitHub.com. It provides bindings for several languages; the CodeQL Ruby extractor uses the Rust bindings.

Tree-sitter offers machine-readable grammar descriptions for a wide range of languages. That turns out to have useful implications for schema generation, discussed below.

The actual parse trees produced by tree-sitter have more detail than the simplified diagram: string literal nodes, for instance, contain child nodes to support interpolation. You can see the structure interactively in the tree-sitter playground.

Ambiguity in Ruby syntax

Ruby's elegant, English-like syntax is also deeply ambiguous. The canonical Ruby parser lives in a 14,000-line Bison grammar file (parse.y) in the MRI source tree—a good measure of the complexity.

Consider an identifier like foo appearing bare with no parentheses. It could be a method call with zero arguments or a variable reference; the parser cannot know which it actually is, because it does not track which variables are in scope. In an expression like:

the parse tree contains an identifier node rather than a call node. It is only later, during analysis, that the AST library uses the program's control-flow graph to determine whether that identifier refers to a variable or a method.

A relational view of the parse tree

Standard parser libraries represent trees using objects and pointers, but CodeQL uses a relational database. A simplified schema can demonstrate the concepts:

expressions(id: int, kind: int)
calls(expr_id: int, name: string)
call_arguments(call_id: int, arg_id: int, arg_index: int)
string_literals(expr_id: int, val: string)

The expressions table holds one row per expression with a unique id primary key and a kind column distinguishing expression types—for instance, type 1 for a method call and type 2 for a string literal. Additional data gets stored in separate tables. Method calls go in the calls table with a receiver_id foreign key to the expression's id and a method_name column. Because calls have a variable number of arguments, arguments live in their own call_arguments table with columnswhich constrain foreign keys, include an index column, and reference the argument's expression row. The string_literals table pairs a literal's text with its expression ID.

For our greeting program, the populated tables look as follows:

expressions

calls

call_arguments

string_literals

A SQL query for all expressions that are arguments in calls to puts would look like:

SELECT call_arguments.arg_id
FROM call_arguments
INNER JOIN calls ON calls.expr_id = call_arguments.call_id
WHERE calls.name = "puts";

CodeQL itself uses SQL only conceptually. Queries are written in QL, an object-oriented declarative language based on Datalog:

from MethodCall call, Expr arg
where
  call.getMethodName() = "puts" and
  arg = call.getAnArgument()
select arg

The QL version wraps tables in classes (MethodCall, Expr) and uses predicates like getMethodName() and getAnArgument() instead of raw joins.

Schemas: manually tuned or generated

The toy schema would not generalize well. Ruby adds constructs such as optional blocks attached to method calls; every language has comparable quirks. For JavaScript and C/C++, the CodeQL schemas define over 100 expression kinds each and were refined by hand over years. Ruby takes a different approach.

Because tree-sitter provides node-types.json — a machine-readable description of every node the parser emits, including field names and types — a tool reads that file and generates a CodeQL database schema for Ruby automatically. The resulting schema is then stored as the authoritative definition for Ruby databases. This substantially reduces the manual effort required to support the language.

Keeping the connection stable

The heart of an extractor is transferring the parse tree into the database while both structures resemble each other. For languages where the schema matches the parser's node structure closely, the transformation is straightforward. When the tree-to-schema mapping is more complex, extra logic is needed.

For Ruby the mapping is clean: since the schema generator pulls directly from tree-sitter's grammar, the extractor performs the same node-type translations and writes tree-sitter's output to the database with minimal work.

One toolchain, many languages

The extraction pipeline is deliberately agnostic to any specific language. Because it operates solely on tree-sitter’s node-types.json, the schema-generator and extractor require no knowledge of Ruby’s syntax or rules. Tree-sitter maintains parsers for dozens of languages, each with a corresponding node-types.json, so the same pair of tools can theoretically produce CodeQL databases for any of them.

This design paid off immediately when the team needed to analyze ERB templates for Rails applications. ERB is a separate language requiring its own parse and extraction pass. The existing tree-sitter ERB parser meant the team could simply point the tooling at its node-types.json and gain ERB support without additional work.

ERB itself is mostly a set of tags demarcating template text from Ruby code. The ERB parser only identifies those boundaries; it does not parse the embedded Ruby. Instead, tree-sitter returns byte offsets for the Ruby regions, which can then be fed into the Ruby parser. Extraction of an ERB file therefore happens in two passes: first the ERB parse tree, then the Ruby parse tree with the template’s text portions skipped.

This automated extraction scheme does push some complexity into the analysis stage. The QL AST library must perform additional transformation to produce a friendly AST from the parse tree, compared to languages where AST classes serve as thin database wrappers. The C# extractor, for example, pulls type data from the Roslyn compiler frontend and stores it directly in the database. The language-independent tooling performs no type analysis, so applying it to a statically typed language would require implementing that type resolution in QL.

Despite those tradeoffs, the approach looks promising for expanding CodeQL to future languages, particularly dynamic ones. Database generation is just one part of language support, but automating it should save considerable effort.

Testing against the largest Ruby codebase

github/github — the Rails application behind GitHub.com — served as the extractor’s stress test. It was only the second Ruby program ever extracted, after “Hello, World!” Unsurprisingly, initial extraction encountered parser errors, which were fixed upstream in the tree-sitter-ruby project. Those fixes improved Ruby code viewing on GitHub.com and benefited other tree-sitter consumers like Neovim’s syntax highlighting.

The codebase also provided a benchmark for extraction speed, since analysis cannot begin until the database is ready. Tree-sitter’s performance helped, as did the translation layer’s simplicity. The biggest gain came from the decision to implement the extractor in Rust, which enabled straightforward parallelism. Each source file’s extraction is fully independent, making the problem embarrassingly parallel. Switching a for loop to a Rayon parallel iterator gave an eightfold speedup on an eight-core laptop.

In production, CodeQL now runs on every pull request against github/github using a 32-core Actions runner, with Ruby extraction completing in 15 seconds. Database finalization adds some time — it parallelizes but less efficiently — yet the extractor’s performance on that codebase compares favorably with other languages. That should be sufficient for Ruby codebases of any size.

Getting started

Further details on enabling CodeQL for Ruby projects are available in the announcement of the Ruby public beta, which includes links for getting started.