Writing a (Ruby) compiler in Ruby bottom up - step 31 2013-12-31

This is part of a series I started in March 2008 - you may want to go back and look at older parts if you're new to this series.

I promised to get a second part out in December somewhere, and it seems like I only barely made it. I'm still hoping to push two out in January, but that's contingent on actually getting time to finish the next one too. But there'll be at least one in January, sometimes towards the middle of the month. Anyway...

Stringing things together

With the new, though basic, Fixnum support, it makes sense to want to print the numbers without having to resort to %s(). Let us add some basic output and conversion functionality.

First lets make compiler.feature actually run again. This turned out to be an embarrassing case of me forgetting to check in two files. With 66d56ef you can run these tests again.

Even more embarrassingly that reveals a few regressions - a motivation for the next part, where we will discuss testing og code generation in more detail, since that's definitively a current weak spot.

We will see soon to what extent these regressions affect what comes next, though.

For now we will only support Kernel#puts and Kernel#print, and only the simplest of use cases, though we will actually put them in Object, again due to lack of include support.

We will assume that the output field separator ($,) is always a linefeed, and we will not do anything to explicitly support array arguments.

We add this test case to compiler.feature:

    puts "Should be one line down due to linefeed above"
    print "Hello "
    puts 42
    print "World\n"
    print "This","is",1,"test\n"
    puts "This","is","test",2

We hope to see at least part of this:

$ ruby features/inputs/06print.rb

Should be one line down due to linefeed above
Hello 42

Instead we get a segmentation fault. There's a number of issues here:

Stubbing out the basics

To begin with, we put a stub Fixnum#to_s with an error, and a String#to_s which simply returns self in place, as well as #puts and #print versions in Object (rather than Kernel, as noted above):

See 6af2c31:

       def puts str
    -    %s(puts (callm str __get_raw))
    +    raw = str.to_s.__get_raw
    +    %s(if raw
    +         (puts raw)
    +         (puts "")
    +         )
    +  end
    +  def print str
    +    raw = str.to_s.__get_raw
    +    %s(if raw
    +         (printf "%s" raw)
    +         )

These are woefully incomplete, but at least in theory they ought to not faily completely....

However, let us take a look what happens if we run the compiler with --parsetree:

    $ ruby compiler.rb  --parsetree --norequire features/inputs/06print.rb
    reading from file: features/inputs/06print.rb
      (call puts (
          (sexp (call __get_string .L0))))
      (call print (
          (sexp (call __get_string .L1))))
      (call puts ())
      (call print (
          (sexp (call __get_string .L2))))
      (call print (
          (sexp (call __get_string .L3)) (sexp (call __get_string .L4)) (sexp (call __get_fixnum 1))
          (sexp (call __get_string .L5))))
      (call puts (
          (sexp (call __get_string .L3)) (sexp (call __get_string .L4)) (sexp (call __get_string .L6))
          (sexp (call __get_fixnum 2))))

Some likely problems to begin with:

Now, while the methods we added are obviously broken, some stuff ought to get executed anyway (subject to buffering, some of it ought to make it to output too), so lets deal with puts 42 first, then add splats to the methods, try to get just puts to work, and then see if we get through any of the above at that point.

Tracking down the 'puts 42' regression

Passing --notransform shows us the likely culprit is the rewrites in transform.rb"

    $ ruby compiler.rb  --parsetree --norequire --notransform features/inputs/06print.rb
    reading from file: features/inputs/06print.rb
      (call puts Should be one line down due to linefeed above)
      (call print Hello )
      (call puts 42)
      (call print World\n)
      (call print (This is 1 test\n))
      (call puts (This is test 2))

We'll use that to add tests targetting specific the transforms as a whole, and then specifically for rewrite_fixnumconst since that seems like a reasonable place to start.

But first, since running this code from gdb and doing a backtrace consistently shows crashes related to our __send__ fallback or method_missing - neither which should get triggered at this stage, lets change __send__ to make it more resilient to implementation bugs for now (in 1e23ae0) and give better debug output:

    --- a/lib/core/object.rb
    +++ b/lib/core/object.rb
    @@ -19,7 +19,10 @@ class Object
       def __send__ sym, *args
    -    %s(printf "WARNING: __send__ bypassing vtable not yet implemented. Called with %s\n" (callm sym to_s))
    +    %s(printf "WARNING: __send__ bypassing vtable not yet implemented.\n")
    +    %s(printf "WARNING:    Called with %p\n" sym)
    +    %s(printf "WARNING:    self = %p\n" self)
    +    %s(if sym (printf "WARNING:    (string: '%s'\n" (callm sym to_s)))

Next I've added a basic test case for 'puts 42' and the expected output only to compiler.feature in ae61dfd

In 5f792c4 I've added a simple test case for the transformations:

        | "puts 42" | [:do, [:call, :puts, [[:sexp,[:call, :__get_fixnum, 42]]]]]

Running it gives us this:

          expected: [:do, [:call, :puts, [[:sexp, [:call, :__get_fixnum, 42]]]]]
               got: [:do, [:call, :puts, [nil]]] (using ==) (RSpec::Expectations::ExpectationNotMetError)
          ./step_definitions/shunting_steps.rb:32:in `/^the parse tree should become (.*)$/'
          transform.feature:10:in `Then the parse tree should become <tree>'

Looking carefully at rewrite_fixnumconst and comparing to rewrite_strconst reveals the source: "FIXME" warning has been subtly broken to use the wrong index.

The correct line reads (in bfecf5d):

    e[i] = E[e[i]] if is_call && i > 1

Fixing this gets us the following output instead for the compiler.feature puts 42 test:

      expected: "42\n"
      got: "Fixnum#to_s is not implemented\n" (using ==)

... which is reasonable, given that we haven't implemented it yet.

Implementing to_s for Fixnum

Handling this in pure Ruby should be possible with what we have available, though probably not very efficiently. And again in pure laziness, let's defer to the C libs snprintf. And leak some memory in the process, but what's a little memory leak amongst friends who aren't freeing anything at all until exit at the moment? ... (yeah, another fun subject we'll have to bite the bullet on)

This takes care of that (in a2f36be):

       def to_s
    -    "Fixnum#to_s is not implemented"
    +    %s(let (buf)
    +       (assign buf (malloc 16))
    +       (snprintf buf 16 "%ld" @value)
    +       (__get_string buf)
    +       )

Our puts 42 test now works.

Handling variable arguments for puts an print

We now want to make puts (with no arguments) and various other variations work. I'll go through tracking down these regressions in some detail debugging code generation is frankly often one of the most annoying and time consuming parts of writing a compiler. And just maybe it'll teach me to write more tests...

So lets start by adding one:

        | inputs/01ctrivial.rb    | outputs/01ctrivial.txt    | A puts with no argument                     |

Where the input looks like this:


and the output like this:

... and it fails (I've run it directly rather than bothering to let Cucumber run it yet):

    $ gdb /tmp/01ctrivial
    GNU gdb 6.8-debian
    Copyright (C) 2008 Free Software Foundation, Inc.
    License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
    This is free software: you are free to change and redistribute it.
    There is NO WARRANTY, to the extent permitted by law.  Type "show copying"
    and "show warranty" for details.
    This GDB was configured as "i486-linux-gnu"...
    (gdb) run
    Starting program: /tmp/01ctrivial
    Program received signal SIGSEGV, Segmentation fault.
    0x00000000 in ?? ()
    (gdb) bt
    #0  0x00000000 in ?? ()
    #1  0x0804c128 in __method_Object_puts () at /home/vidarh/src/compiler-experiments/writing-a-compiler-in-ruby/lib/core/object.rb:36
    #2  0x0804a622 in main () at 01ctrivial.rb:1
    (gdb) quit

That's def puts str. First problem is that we're currently expecting an argument, but we're not getting any. In reality the compiler should throw an ArgumentError when the method is declared like this and called with too few arguments. But we've not gotten that far. Anyway, first step is to change this to def puts *str. But we still need to handle the difference in argument numbers and it currently won't be very elegant, as we don't convert str to an actual Ruby array or anything, so we have to dip down to %s(numargs) etc.

We first try to add this to the start of Object#puts:

        %s(assign na (call __get_fixnum (numargs)))
        if na == 2
           %s(puts "")

We expect na to be 2 because of self + the optional __closure__ argument we pass (but that is always present).

This fixes puts on its own, but breaks puts 42. The reason is the splat operator - we can't any longer refer directly to str and expect to get an object - str now refers to an address to an array of objects.

So we change the entire puts to this:

      def puts *str
        %s(assign na (__get_fixnum numargs))
        if na == 2
          %s(puts "")
        %s(assign raw (index str 0))
        raw = raw.to_s.__get_raw
        %s(if raw
             (puts raw)
             (puts "")

Apart from being horribly ugly, this also doesn't handle multiple arguments, but it's a step further.

You find this and test in 6918bf8

So, lets try something more convoluted, like, say, puts "foo", "bar".

Uh-oh. Doesn't work. What more, if we add a debug printout like %s(printf "numargs=%d\n" numargs) we get a nasty surprise: It returns 3. For me at least.

Some probing in the assembler output shows us this:

       # callm :self.:puts
        subl    $20, %esp
        movl    $4, %ebx
        movl    self, %eax
        movl    %eax, (%esp)
        movl    $0, 4(%esp)
        subl    $4, %esp
        movl    $1, %ebx
        movl    $.L11, %eax
        movl    %eax, (%esp)
        movl    $__get_string, %eax
        call    *%eax
        addl    $4, %esp
        movl    %eax, 8(%esp)
        subl    $4, %esp
        movl    $1, %ebx
        movl    $.L12, %eax
        movl    %eax, (%esp)
        movl    $__get_string, %eax
        call    *%eax
        addl    $4, %esp
        movl    %eax, 12(%esp)
        movl    (%esp), %edx
        movl    (%edx), %edx
        movl    36(%edx), %eax
        call    *%eax
        addl    $20, %esp
        # callm self.puts END

Spot the problem? We use %ebx to hold the number of arguments we calculate, but with our new "proper" support for strings, we now call __get_string on the string argument, and each one of them causes %ebx to get clobbered. As, incidentally does __get_string itself, as we don't actually store this value anywhere. We have two choices: Load it "closer" (That's generally a good idea anyway) or calculate it closer (for splat arguments).

This again underlines that we need proper register allocation including ability to "spill" registers to the stack. This is complicated in that if we push and pop values all over the place, we need to be able to adjust all accesses to %esp all over.

For now we "fake" spilling of %ebx by pushing %ebx indiscriminately onto the stack, and adjusting the generation of the arguments accordingly "manualy" so that when we pop it off the stack again everything happens to work. We end up with changing the central parts of Compiler#compile_callm_args as follows (in 6901567)

        @e.with_stack(args.length+1, true) do
          if splat
          # we're for now going to assume that %ebx is likely
          # to get clobbered later, in the case of a splat,
          # so we store it here until it's time to call the method.
          ret = compile_eval_arg(scope, ob)
          @e.save_to_stack(ret, 1)
          args.each_with_index do |a,i|
            param = compile_eval_arg(scope, a)
            @e.save_to_stack(param, i+2)
          # This is where the actual call gets done
          # This differs depending on whether it's a normal
          # method call or a closure call.
          # But first we pull the number of arguments off the stack.

The main change here is the @e.pushl(:ebx) and @e.popl(:ebx) lines. But notice that we change the offsets for self and method arguments accordingly.

This finally allows us to handle #puts and #print reasonably close to can see the result of this in 4511cea:

      def puts *str
        %s(assign na (__get_fixnum numargs))
        if na == 2
          %s(puts "")
        na = na - 2
        i = 0
        while i < na
          %s(assign raw (index str (callm i __get_raw)))
          raw = raw.to_s.__get_raw
          %s(if raw (puts raw))
          i = i + 1
      def print *str
        %s(assign na (__get_fixnum numargs))
        if na == 2
          %s(printf "nil")
        na = na - 2
        i = 0
        while i < na
          %s(assign raw (index str (callm i __get_raw)))
          raw = raw.to_s.__get_raw
          %s(if raw (printf "%s" raw))
          i = i + 1

It's not pretty, and there's certainly a lot of room for improvement. In particular "proper" access to the splat arguments would help tremendously, so that's on the agendy for soon too, I think, after code generation testing and some cleaner register allocation.

Some string interpolation

While we're at it, we might as well take a look at string interpolation and see what kind of trouble we might run into.

First we add a trivial test case (in c7b4b540bb):

    a = "Hello World"
    b = 42
    puts "#{a}, #{b}"

Unsurprisingly it doesn't work, so lets try compiling it with --norequire --parsetree:

      (assign a (sexp (call __get_string .L0)))
      (assign b (sexp (call __get_fixnum 42)))
      (call puts (
          (concat (sexp (call __get_string .L1)) a (sexp (call __get_string .L2)) b)))

This is clearly outdated - we'd expect concat to be a method call on the string.

Let us turn of transformations, to see what the parser actually created:

    $ ruby compiler.rb --parsetree --norequire --notransform features/inputs/interpolate.rb 
    reading from file: features/inputs/interpolate.rb
      (assign a "Hello World")
      (assign b "42")
      (call puts (
          (concat "" a " , " b)))

A-ha. concat nodes were how we implemented interpolation in the parser. So what we need is to transform them to generate the equivalent of "".concat(a.to_s).concat(" , ").concat(b.to_s)

Here is how we do that (in 35d93b0):

      def create_concat(sub)
        right = sub.pop
        right = E[:callm,right,:to_s] if !right.is_a?(Array)
        return right if sub.size == 0
        E[:callm, create_concat(sub), :concat, [right]]
      def rewrite_concat(exp)
        exp.depth_first do |e|
          if e[0] == :concat

We replace the existing (concat a b c ...) with a series of method calls to create and convert nodes to strings, and then call String#concat to create the result.

We for now implement String#concat like this:

    +  def concat(other)
    +    %s(do
    +         (assign ro (callm other __get_raw))
    +         (assign osize (strlen ro))
    +         (assign bsize (strlen @buffer))
    +         (assign size (add bsize osize))
    +         (assign size (add size 1))
    +         (assign newb (malloc size))
    +         (strcpy newb @buffer)
    +         (strcat newb ro)
    +         (assign @buffer newb)
    +   )
    +    self
    +  end

While this is simple - it just allocates buffers and copies data into them - it isn't very elegant code. So I might as well admit: Some of the simplicity is because of bugs that rears its head if we make the expressions too advanced - likely due to memory protection issues.

But we will take care of that in our part on testing code generation, next time. For now, this works.

blog comments powered by Disqus