How YARV controls your program’s execution flow
similar to the structures you use in Ruby.
We’ve seen how YARV uses a stack while executing its instruction set and how it can access variables locally or dynamically, but what about control structures? Controlling the flow of execution is a fundamental requirement for any programming language, and Ruby has a rich set of control structures. How does YARV implement it?
Just like Ruby itself, YARV has it own control structures, albeit at a much lower level. Instead of if or unless statements, YARV uses two low level instructions called branchif and branchunless. And instead of using control structures such as “while…end” or “until…end” loops, YARV has a single low level function called jump that allows it to change the program counter and move from one place to another in your compiled program. By combining the branchif or branchunless instruction with the jump instruction YARV is able to execute most of Ruby’s simple control structures.
How Ruby executes an if statement
A good way to understand how YARV controls execution flow is to take a look at how the if/else statement works. Here’s a simple Ruby script that uses both if and else:
On the right you can see the corresponding snippet of compiled YARV instructions. Reading the YARV instructions, you can see Ruby follows a pattern for implementing the if/else statement:
evaluate condition
jump to false code if condition is false
true code; jump to end
false code
This is a bit easier to follow if I paste the instructions into a flowchart:
You can see how the branchunless instruction in the center is the key to how Ruby implements if statements; here’s how it works:
First at the top Ruby evaluates the condition of my if statement, “i < 10,” using the opt_lt (optimized less-than) instruction. This will leave either a true or false value on the stack.
Then branchunless will jump down to the false/else condition if the condition is false. That is, it “branches unless” the condition is true. Ruby uses branchunless and not branchif for if/else conditions since the positive case, the code that immediately follows the if statement, is compiled to appear right after the condition code. Therefore YARV needs to jump if the condition is false.
Or if the condition is true Ruby will not branch and will just continue to execute the positive case code. After finishing the positive code Ruby will then jump down to the instructions following the if/else statement using the jump instruction.
Finally either way Ruby will continue to execute the subsequent code.
YARV implements the unless statement in a similar way using the same branchunless instruction, except the positive and negative code snippets are in reverse order. For looping control structures like “while…end” and “until…end” YARV uses the branchif instruction instead. But the idea is the same: calculate the loop condition, then execute branchif to jump as necessary, and finally use jump statements to implement the loop.
Jumping from one scope to another
One of the challenges YARV has implementing some control structures is that, similar to dynamic variable access, Ruby sometimes can jump from one scope to another. The simplest example of this is the break statement. break can be used both to exit a simple loop like this:
i = 0 while i<10 puts i i += 1 break end
…or from a block iteration like this:
10.times do |n| puts n break end puts "continue from here"
In the first case, YARV can exit the while loop using simple jump instructions like we saw above in the if/else example. However, exiting a block is not so simple: in this case YARV needs to jump to the parent scope and continue execution after the call to 10.times. How does it do this? How does it know where to jump to? And how does it adjust both its internal stack and your Ruby call stack to be able to continue execution properly in the parent scope?
To implement jumping from one place to another in the Ruby call stack – that is, outside of the current scope – Ruby uses the throw YARV instruction. YARV’s throw instruction resembles the Ruby throw keyword: it sends or throws the execution path back up to a higher scope. It also resembles the throw keyword from C++ or Java – it’s similar to raising an exception, except there is no exception object here.
Let’s take a look at how that works; here’s the compiled code for the block above containing the break statement:
You can see a “throw 2” instruction appears in the compiled code for the block. throw implements throwing an exception at the YARV instruction level by using something called a “catch table” A catch table is a table of pointers optionally attached to any YARV code snippet. Conceptually, a catch table might look like this:
Here, the catch table from my example contains just a single pointer to the pop statement, which is where execution would continue after an exception. Whenever you use a break statement in a block, Ruby not only compiles the throw instruction into the block’s code, but it also adds the BREAK entry into the catch table of the parent scope. For a break within a series of nested blocks, Ruby would add the BREAK entry to a catch table even farther down the rb_control_frame stack.
Later, when YARV executes the throw instruction it checks to see whether there’s a catch table containing a BREAK pointer for the current YARV instruction sequence:
If there isn’t, Ruby will start to iterate down through the stack of rb_control_frame structures looking for a catch table containing a break pointer…
…and continue to iterate until it finds one:
In my simple example, there is only one level of block nesting, so Ruby will find the catch table and BREAK pointer after just one iteration:
Once Ruby finds the catch table pointer, it resets both the Ruby call stack (the CFP pointer) and the internal YARV stack to reflect the new program execution point. Then YARV continues to execute your code from there. That is, YARV resets the internal PC and SP pointers as needed.
What is interesting to me about this is how Ruby uses a process similar to raising and rescuing an exception internally to implement a very commonly used control structure: the break keyword. In other words, what in more verbose languages is an exceptional occurrence becomes in Ruby a common, everyday action. Ruby has wrapped up a confusing, unusual syntax – raising/rescuing of exceptions – into a simple keyword, break, and made it very easy to understand and use. Of course, Ruby needs to use exceptions because of the way blocks work: they are on one hand like separate functions or subroutines, but on the other hand just part of the surrounding code. For this reason Ruby needs a keyword like break that seems simple at first glance but internally is quite complex.
Another commonplace, ordinary Ruby control structure that also uses catch tables is the return keyword. Whenever you call return from inside a block, Ruby internally raises an exception and rescues it with a catch table pointer like this. In fact, break and return are implemented with exactly the same YARV instructions; the only difference is that for return Ruby passes a 1 to the throw instruction (e.g. throw 1), while for break it passes a 2 (throw 2) as we saw above. The return and break keywords are really two sides of the same coin.
Finally, besides BREAK there are other types of pointers that Ruby can use in the catch table. The others are used to implement different control structures: RESCUE, ENSURE, RETRY, REDO and NEXT. For example, when you explicitly raise an exception in your Ruby code using the raise keyword, Ruby implements the rescue block in a similar way by using the catch table, but this time with a RESCUE pointer. The catch type is simply a list of event types that can be caught and handled by that sequence of YARV instructions, similar to how you would use a rescue block in your Ruby code.
Experiment 2-3: Testing how Ruby implements for loops internally
I always knew that Ruby’s for loop control structure worked essentially the same way as using a block with the each Enumerable method. That is to say, I knew this code:
for i in 0..5 puts i end
… worked the same way as this code:
(0..5).each do |i| puts i end
But I never suspected that internally Ruby actually implements for loops using each! That is, there really is no for loop control structure in Ruby at all; instead, the for keyword is really just syntactical sugar for calling each with a range.
To prove this is the case, all you have to do is inspect the YARV instructions that are produced by Ruby when you compile a for loop. Let’s use the same RubyVM::InstructionSequence.compile method that I did in Chapter 1:
code = <<END for i in 0..5 puts i end END puts RubyVM::InstructionSequence.compile(code).disasm
Running this I get:
== disasm: <RubyVM::InstructionSequence:<compiled>@<compiled>>========== == catch table | catch type: break st: 0002 ed: 0010 sp: 0000 cont: 0010 |------------------------------------------------------------------------ local table (size: 2, argc: 0 [opts: 0, rest: -1, post: 0, block: -1] s1) [ 2] i 0000 trace 1 ( 1) 0002 putobject 0..5 0004 send :each, 0, block in <compiled>, 0, <ic:0> 0010 leave == disasm: <RubyVM::InstructionSequence:block in <compiled>@<compiled>>= == catch table | catch type: redo st: 0005 ed: 0016 sp: 0000 cont: 0005 | catch type: next st: 0005 ed: 0016 sp: 0000 cont: 0016 |------------------------------------------------------------------------ local table (size: 2, argc: 1 [opts: 0, rest: -1, post: 0, block: -1] s3) [ 2] ?<Arg> 0000 getdynamic *, 0 ( 3) 0003 setlocal i ( 1) 0005 trace 1 ( 2) 0007 putself 0008 getlocal i 0010 send :puts, 1, nil, 8, <ic:0> 0016 leave
To make this a bit easier to follow, I’ll repeat these YARV instructions in a diagram, and remove some of the technical details like the trace statements:
You should notice right away there are two separate YARV code blocks: the outer scope which calls each on the range 0..5 and then an inner block that makes the puts i call. The “getdynamic *, 0” instruction in the inner block loads the implied block parameter value - i in my Ruby code - and the following setlocal instruction saves it into a local variable also called i.
Taking a step back and thinking about this, what Ruby has done here is:
Automatically converted the “for i in 0..5” code into “(0..5).each do”
Automatically created a block parameter to hold each value in the range, and:
Automatically created a local variable in the block with the same name as the for loop variable, and saved the block parameter’s value into it.