Finding Unused Methods Statically

Note: This article is part of a series exploring how Laser, my Ruby static analysis tool, can help improve the quality of Ruby code. I'm presenting on this at RubyConf 2011 about it, and you should come!

One of the more frustrating aspects of keeping a clean Ruby codebase is getting rid of unused methods. Heavy refactoring, failed designs, or requirements changes lead to leftover cruft, no matter how vigilant we are. We'd like to know what methods aren't being used so we can just remove them.

Challenges for Ruby

Unfortunately, that's not so easy in a dynamic language, let alone Ruby. A statically-typed language can piggyback off the type-checker: as dispatches are calculated, each method potentially dispatched can be marked. In Java, you can imagine a call to instanceOfSomeInterface.foo marking each implementation of SomeInterface's foo method as potentially dispatched.

Ruby naturally doesn't have such a mechanism going on, it's dynamically-typed. You can create new methods at runtime, near-trivially use send to dispatch to any number of methods, violate privacy (again using send), and so forth. So how do we do it?

Coverage?

Most folks use a combination of coverage, experience, and thinking. Ruby has RCov for Ruby 1.8 and tools like SimpleCov and CoverMe for Ruby 1.9. These tools have their quirks but are generally quite accurate - these tools can tell you every method your test suite calls.

The question is: how comprehensive is your test suite? Do you write tests before you write your program code? Are you positive none of your tests test code that is otherwise unused? Probably not. Hell, Laser has a few modules that aren't used but are thoroughly tested. Coverage isn't as accurate as it could be for purely human factors, and I suspect those factors will stick around. How can we do better?

Laser Calculates Dispatch Already!

Well, it turns out Laser already calculates dispatch at every callsite, using the Cartesian Product Algorithm (PDF warning, but it's a classic paper). Actually Laser does a more advanced version which is flow-sensitive, because Laser calculates a control-flow graph for your Ruby code. The original CPA (and most implementations I've seen) are flow-insensitive. Regardless, we calculate dispatch in the way you'd expect: every possible type for a given variable foo is considered in all dispatches involving foo. We try to keep that set as small as possible while staying accurate. CPA is just what makes it efficient.

We also check privacy (just public/non-public right now - who uses protected anyway?) and arity on each dispatch. So we've got all the ingredients for seeing if a given method is called or not!

Examples

So let's see how it works!

$ cat temp.rb
class UnusedMethod2
  def foo(x)
    x
  end
  def bar(x, y=x)
  end
end
class UnusedMethod3 < UnusedMethod2
  def foo(x)
    bar(x)
  end
  def bar(x, y=x)
    super
    y
  end
  def baz
  end
end
UnusedMethod3.new.foo(gets)

$ laser temp.rb
(stdin):0 Unused method () - The method UnusedMethod2#foo is never called.
(stdin):0 Unused method () - The method UnusedMethod3#baz is never called.

Note: Not all warnings are shown, just the relevant ones for this article.

You can see here Laser has seen the entry point to the program as a call to UnusedMethod3#foo with one String | NilClass argument. UnusedMethod3#foo calls UnusedMethod3#bar, which uses super to call UnusedMethod2#bar. The arities all line up, so those methods are all marked as called. Those not called by the time Laser terminates are spat out as warnings!

Eventually, we'll want the filenames and line numbers to be correct, so perhaps this output could be sorted in a meaningful way. But for now, that was cool.

Working with `#send`

How about something that uses Ruby's more dynamic features?

$ cat temp.rb
class UnusedMethod5
  def zero
  end
  def one_or_two(a, b=1)
  end
  def two(a, b)
  end
  def three(a, b, c)
  end
  def any(*rest)
  end
end
choice = [:zero, :one_or_two, :two, :three, :any][gets.to_i]
UnusedMethod5.new.send(choice, gets, gets)

$ laser temp.rb
(stdin):0 Unused method () - The method UnusedMethod5#zero is never called.
(stdin):0 Unused method () - The method UnusedMethod5#three is never called.

Here we've got a non-deterministic call to send, but one that Laser can figure out! We have no idea which symbol (or nil) will end up in choice, but Laser restricts its view to those constants and nil when it calculates the dispatch at UnusedMethod5#send. Thus, only the five methods listed are considered for dispatch. Then, zero and three are tossed out: they aren't successfully called, because the call to send has two arguments, and those methods can't accept two arguments.

Privacy checking:

$ cat temp.rb
class UnusedMethod6
  def public_one_or_two(a, b=1)
  end
  def public_two(a, b)
  end
 private
  def private_two(a, b)
  end
 protected
  def protected_two(a, b)
  end
end
choice = [:public_one_or_two, :public_two, 
          :private_two, :protected_two][gets.to_i]
UnusedMethod6.new.public_send(choice, gets, gets)

$ laser temp.rb
(stdin):0 Unused method () - The method UnusedMethod6#private_two is never called.
(stdin):0 Unused method () - The method UnusedMethod6#protected_two is never called.

The Kernel#public_send method only dispatches to public methods, so here we know that private_two and protected_two won't get called. The arities match up on public_one_or_two and public_two, so they are marked as used.

Totally unknown `send`s

That's all well and good, but what about if you call send with a String coming from a query string? Or from a file? There's room for Laser to grow here, but it can handle a simple case:

$ cat temp.rb
class UnusedMethod7
  def zero
  end
  def one_or_two(a, b=1)
  end
  def two(a, b)
  end
  def three(a, b, c)
  end
  def any(*rest)
  end
end
UnusedMethod7.new.send(gets, gets, gets)

$ laser temp.rb
(stdin):0 Unused method () - The method UnusedMethod7#three is never called.

As expected, only UnusedMethod7#three was marked as not called. Did you expect zero to be marked as unused? I did, before I ran this test.

Then, after Laser returned just #three, I remembered that this call could end up as:

UnusedMethod7.new.send('send', 'send', 'zero')

Which Laser figured out. Cool.

Room to Grow

As I said, Laser could know more. A common way to use send with an target based on untrusted input is to prefix it and the relevant methods:

class Foo
  def dispatch(method)
    send("do_#{method}", 1, 2, 3) if respond_to?("do_#{method}")
  end
  def do_bar(a, b, c)
  end
  def do_baz(a, b, c)
  end
end
Foo.new.dispatch(gets)

Unfortunately, Laser just sees "do_" + gets as any old String. Just as tuples require explicit modeling, so too do such constructions. I haven't looked into this yet, but it'll be an important case to consider.

Laser watches you alias

Just so you know, Laser isn't just checking for the text "send" and "public_send" - it's watching when you alias and undef methods:

$ cat temp.rb
class UnusedMethod9
  def foo(a)
  end
  def baz(a)
  end
  def bar(a)
  end

  alias_method :qux, :send
  alias_method :send, :bar
end
UnusedMethod9.new.send(:foo)
UnusedMethod9.new.qux(:baz, 1)

$ laser temp.rb
(stdin):0 Unused method () - The method UnusedMethod9#foo is never called.

Cool, eh?