Do Not Resuscitate Learning static analysis of Ruby by building a dead code detector Jason Gedge
Founding Engineer
Hey, everyone. My name's Jason, but everyone knows me by my last name, Gedge. I work at local startup called Gadget,
where I write next to no Ruby, so it makes total sense that I'm here to talk about static analysis in Ruby.
So what do we mean by static analysis? It's when we analyze some source code without actually running it. Ruby makes
this an exceptionally hard problem, since there can be a lot of metaprogramming, but that doesn't mean we can't do
interesting things with it.
Tonight we'll learn a bit about this through building a script that can detect unused methods in a codebase. Let's
start by learning a bit about abstract syntax trees.
My biggest journey into static analysis was at Shopify, working on a tool called packwerk.
We had a requirement that we needed a tool that could very quickly analyze Shopify's huge monolith quickly. The tricky
part was properly resolving constants statically, but it was a ton of fun and we learned a lot.
Abstract Syntax Tree (AST)
It is a tree representation of the abstract syntactic structure of text (often source code)
written in a formal language.
Wikipedia The key thing to remember is that we can break down our code into a tree-like structure.
Note "abstract" here means it's not necessarily directly connected to the original text. For example, whitespace and
comments may not be represented in an AST.
If the tree can map perfectly back to the source text, it's called a concrete syntax tree.
So what does that look like?
ruby-parse -e "
# a simple class
class MyClass;
def initialize
@ivar = 1
end
end
" ( class
( const nil :MyClass )
nil
( def :initialize
( args
( ivasgn
:@ivar
( int 1 ) ) ) ) ) Ruby has this great tool called ruby-parse that can take some Ruby code and output an AST in format known as
"s-expression" (popularized by Lisp).
It's a great tool to use so you can quickly visualize an AST for a statement. In this example you can see several
different kinds of nodes: class, const, def, args, ivasgn, and int (the word immediately after each opening
parenthesis).
Note how there's no reference to line/column numbers, and the comment is nowhere to be found. That's what makes it an
AST.
But you might wonder: what are all the possible node types? And what are the other bits in the s-expression like those
nil values?
node_dump.c
Where you can find all of the possible node types you can encounter.
static void
dump_node ( VALUE buf , VALUE indent , int comment , const NODE * node ) {
case NODE_CLASS :
} Well, there's no real reference that I know of. When that happens, I like to go to the source!
In the Ruby source code you can find a file called node_dump.c. In there is a method called "dump_node", which has
some great examples of the node types, what each part of the s-expression for that node means, and examples of what it
looks like in source code.
case NODE_CLASS :
ANN ( "class definition" ) ;
ANN ( "format: class [nd_cpath] < [nd_super]; [nd_body]; end" ) ;
ANN ( "example: class C2 < C; ..; end" ) ;
F_NODE ( nd_cpath , "class path" ) ;
F_NODE ( nd_super , "superclass" ) ;
LAST_NODE ;
F_NODE ( nd_body , "class definition" ) ;
return ; For example, here's an example of the NODE_CLASS node type, which we saw earlier. Focus on each of the F_NODE calls to
get a good description of each subnode.
case NODE_CLASS :
ANN ( "class definition" ) ;
ANN ( "format: class [nd_cpath] < [nd_super]; [nd_body]; end" ) ;
ANN ( "example: class C2 < C; ..; end" ) ;
F_NODE ( nd_cpath , "class path" ) ;
F_NODE ( nd_super , "superclass" ) ;
LAST_NODE ;
F_NODE ( nd_body , "class definition" ) ;
( class
( const nil :MyClass )
nil
( def :initialize
( args )
( ivasgn :@ivar
( int 1 ) ) ) ) For example, here's an example of the NODE_CLASS node type, which we saw earlier. Focus on each of the F_NODE calls to
get a good description of each subnode.
And here's the s-expression for the Ruby code we saw earlier. You can see how the s-expression maps to the node type. We
now know that the nil we saw earlier was the super class.
So how do we actually get an AST in Ruby?
I've been out of the Ruby game for some time, so there may be newer options, but I'll highlight three I'm familiar with.
Parser options 💎 parser 👮 Rubocop 🌲 RubyVM::AbstractSyntaxTree First, we have the parser gem. It has the benefit of being able to parse many different versions of Ruby code. Being
pure Ruby, it isn't the fastest option though.
(click)
Secondly, we have Rubocop, which is built on the parser gem. It can make it really easy to deal with parsing a lot of
files, and it comes with a DSL to make it easier to work with ASTs.
(click)
Finally, available since Ruby 2.6, is the AbstractSyntaxTree module. It's built into the standard library, and is
really fast, but is much more "raw".
We're going to focus on this one.
This class is experimental and its API is not stable, therefore it might change without notice. As examples, the order
of children nodes is not guaranteed, the number of children nodes might change, there is no way to access children nodes
by name, etc.
If you are looking for a stable API or an API working under multiple Ruby implementations, consider using the parser
gem or Ripper. If you would like to make RubyVM::AbstractSyntaxTree stable, please join the discussion at
https://bugs.ruby-lang.org/issues/14844 .
It's important to call out that the builtin AST module is not considered a stable API yet. Expect it to break from one
version to the next.
For me, that's okay. Most of the time I'm doing these analyses I am making quick scripts that are meant to be thrown
away.
RubyVM :: AbstractSyntaxTree . parse ( string )
RubyVM :: AbstractSyntaxTree . parse_file ( pathname ) Fortunately, producing an AST is super simple in Ruby!
You simply call the parse_file method with a path to some Ruby file and voila, you have the AST. There's also the
parse method if you have a string with some Ruby source code.
So that gives you a tree-like structure that you can traverse, but how do we do that?
RubyVM::AbstractSyntaxTree::NodeWe're primarily going to focus on two attributes.
(click)
type will be the type of node (uppercase). You can find those saw in the dump_node method earlier. Don't forget you
can use ruby-parse too!
(click)
children are the child nodes under the current node. You'll generally be writing a recursive function to traverse the
tree. Note that not all children will be nodes. Sometimes there'll be symbol or other literal values, depending on the
type of node we're in.
ast.c
shows the ordering of children, which can be different than ruby-parse / node_dump.c.
case NODE_CALL :
return rb_ary_new_from_args (
3 ,
NEW_CHILD ( ast_value , RNODE_CALL ( node ) -> nd_recv ) ,
ID2SYM ( RNODE_CALL ( node ) -> nd_mid ) ,
NEW_CHILD ( ast_value , RNODE_CALL ( node ) -> nd_args )
) ; Just one side note.
Most of the times the ordering of children you get from ruby-parse will be the same, but if it isn't you can either
print out the types yourself, or head over to ast.c to see.
Okay, let's traverse the tree. We're going to build what's known as a "depth-first traversal".
This means we'll go as deep as possible down one branch of the tree before moving on to the next. We'll process nodes in
"pre-order", which means we'll do something before descending. That's the red dots in this diagram.
Public domain source Designing our dead code detector For every Ruby file in current path, collect two pieces of information:
Function calls
Method definitions
We're going to start off keeping our approach really simple. We'll collect two pieces of information while traversing
the ASTs of all files under a directory.
First, we need to find all of the function calls. Second, we need to find all of the method definitions.
We're almost certainly going to have false positives here, but the idea is to start simple, and figure out how to build
heuristics on top of that to filter out those false positives. As an example: Rails, being a framework, will call many
methods in our codebase. We're not going to find a function call, for example, for a controller's index function.
def traverse ( node , & blk )
return unless node . is_a ( RubyVM :: AbstractSyntaxTree :: Node )
blk . call ( node )
node . children . each do | child |
traverse ( child , & blk )
end
end
traverse ( RubyVM :: AbstractSyntaxTree . parse_file ( pathname ) ) do | node |
end So here's the usual template for our traversal function. We're going to take a block to make it really easy to reuse.
Let's start filling it in.
calls = Set . new
defs = Set . new
traverse ( RubyVM :: AbstractSyntaxTree . parse_file ( pathname ) ) do | node |
end
puts "Calls: #{ calls . to_a } "
puts " Defs: #{ defs . to_a } " Next, we'll create our sets that will keep track of the function calls and definitions
calls = Set . new
defs = Set . new
traverse ( RubyVM :: AbstractSyntaxTree . parse_file ( pathname ) ) do | node |
case node . type
when :FCALL
calls << node . children [ 0 ]
when :CALL
calls << node . children [ 1 ]
end
end
puts "Calls: #{ calls . to_a } "
puts " Defs: #{ defs . to_a } " Now, let's start tracking function calls. The tricky bit is always getting the right child.
Note how we only care about the name of the functional call. We're ignoring the receiver, but a more intelligent dead
code detector may want to use that.
calls = Set . new
defs = Set . new
traverse ( RubyVM :: AbstractSyntaxTree . parse_file ( pathname ) ) do | node |
case node . type
when :FCALL
calls << node . children [ 0 ]
when :CALL
calls << node . children [ 1 ]
when :DEFN
defs << node . children [ 0 ]
when :DEFS
defs << node . children [ 1 ]
end
end
puts "Calls: #{ calls . to_a } "
puts " Defs: #{ defs . to_a } " Now, function definitions.
calls = Set . new
defs = Set . new
traverse ( RubyVM :: AbstractSyntaxTree . parse_file ( pathname ) ) do | node |
case node . type
when :FCALL
calls << node . children [ 0 ]
when :CALL
calls << node . children [ 1 ]
when :DEFN
defs << node . children [ 0 ]
when :DEFS
defs << node . children [ 1 ]
end
end
puts " Calls: #{ calls . to_a } "
puts " Defs: #{ defs . to_a } "
puts "Maybe dead: #{ ( defs - calls ) . to_a } " Finally, we tie it all together by removing all of the called methods from the definitions set.
$ ruby find_dead_code.rb unused_example.rb
Calls: [:include, :attr_reader, :new, :value, :create, :puts, :to_s, :squared]
Defs: [:create, :initialize, :squared, :incremented, :<=>]
Maybe dead: [:initialize, :incremented, :<=>] Let's run that against our test file.
(demo)
So, we got pretty close! The only false positive we got was initialize, but it's actually implicitly called when we
instantiate a class.
The spaceship operator -- <=> -- is used for comparisons, and could also be called implicitly by other code.
So there you have it. We built a primitive dead code detector in Ruby.
If you want a slightly more sophisticated example, you can check out one of my gists. It has a few bonus features like
parsing many files, ERB support, and some heuristics for excluding methods that are likely to be called, even if we
couldn't find a call for them.
Thanks for listening!️
❤️ ❤️ ❤️ ❤️ ❤️ ❤️
Thanks for listening! I'm looking forward to seeing you all build some cool static analysis tools :)
