Metaprogramming magic in Ruby
The past week I’ve been playing with implementing LinkedList in Ruby, mainly Single and Double. Both of them include an Enumerable like module called Iteration. It provides methods like: each, count, map, select etc. Double also inclues IterationReverse which provides: reverse, map_reverse etc. As you can tell there’s a lot of code common between the two Iteration modules. The only real difference is each. Iteration#each starts at tail and iterates to head, while IterationReverse#each starts at head and iterates to tail. head being the first node added to list, while tail is last node added. (I know crappy class names right, we’ll fix it later). Late last night I started thinking about ways to DRY the two modules, this post is direct result of that.
First I renamed Iteration and IterationReverse to BackwardIteration and ForwardIteration. My original plan then was to extract out the common methods into Iteration, while implementing each in the respective modules.
module Iteration def map end end module ForwardIteration include Iteration def each end module BackwardIteration include Iteration def each end end class SingleLinkedList include ForwardIteration end class DoubleLinkedList include ForwardIteration include BackwardIteration end
The problem here is when you include BackwardIteration in DoubleLinkedList, it will override ForwardIteration#each.
Before we get any further, let’s write some specs. The below should be fairly self explanatory. We test #first which returns first added node, #last, first’s counterpart. #to_a iterates through list from head to tail, while #to_a_reverse, well you can guess. The last test was a regression test, which we’ll get to later.
describe 'LinkedList' do
context SingleLinkedList do
subject { described_class.new }
it 'returns first character' do
subject.first.should == 'F'
end
end
context DoubleLinkedList do
subject { described_class.new }
it 'returns first character' do
subject.first.should == 'F'
end
it 'returns last character' do
subject.first_reverse.should == 'B'
end
it 'returns array from head to tail' do
subject.to_a.should == %w(F o r w a r d)
end
it 'returns array from tail to head' do
subject.to_a_reverse.should == %w(B a c k w a r d)
end
it 'does not override #each method' do
subject.to_a_reverse.should == %w(B a c k w a r d)
subject.to_a.should == %w(F o r w a r d)
end
end
endWhat we need to do is to stop ForwardIteration#each from clashing with BackwardIteration#each, while also renaming the methods in BackwardIteration with _reverse added to them if ForwardIteration is defined.
First I tried to do this:
module BackwardIteration
def self.included(base)
if base.ancestors.include?(ForwardIteration)
instance_methods.each do |method|
base.class_eval do
alias_method "#{method}_reverse", method
define_method method do
unbound = ForwardIteration.instance_method(method)
unbound.bind(self).call
end
end
end
end
end
endWhat it does is it looks for ForwardIteration, if its defined, it changes its own method name, by adding _reverse to it. Then it forwards the method to point to ForwardIteration. Ruby lets you get a method as an object with #instance_method(method), you’ll have to bind the method to the object, i.e. put the method in the lookup chain, then you can call it. But it didn’t work as I thought it would, so I decided to try another way.
Below I use method_missing is catch methods with _reverse suffix. For those methods, I temporarily redefine each to point to BackwardIteration#each and then call the method. Once done, I redefine each to point to ForwardIteration#each.
module BackwardIteration
include Iteration
def method_missing(method, *args, &blk)
if method.to_s =~ /^(.*)_reverse/
define_each
result = send($1.to_sym)
undef_each
result
end
end
def define_each
class << self
define_method :each do
e = BackwardIteration.instance_method(:each)
e.bind(self).call
end
end
end
def undef_each
class << self
define_method :each do
super()
end
end
end
def each
'Backward'
end
end
class DoubleLinkedList
include ForwardIteration
include BackwardIteration
endClearly the constant defining and redefining of each isn’t a very good idea, but this was just a learning experience and I had a whole lot of fun trying to get it to work. Hopefully the specs pass for you and you learned a little bit more about the dynamic nature of Ruby.
