Writing a (Ruby) compiler in Ruby bottom up - step 36 2014-06-27

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.

Scanning for problems

Where we left off last time, we'd just barely scratched the surface of what it will take to self-host the Scanner.

This time we'll keep digging into that. I will skip or gloss over fixes to some bugs etc., and focus mostly on the bits that are filling in intentional omissions from earlier that are now finally coming back to bite us, with the exception of some particularly interesting (to me at least) bugs.

One of the bugfixes were actually pushed out with the previous branch. See e6ae4ba - this is worth at least a cursory note as it got the order in which we determined the size of an object instance vs. where I actually counted up the number of immediately visible instance variables wrong. Ouch.

By the time this version is out, I'll also have merged a bunch of fixes to make the code work with Ruby 1.9, finally.

But back to the Scanner code. This part ended up a lot more convoluted than I'd planned. I've skipped over some of the details of my debugging, as it got tedious to write and probably twice as much to read, with lots of jumping back and forth. Th

For the purposes of this series, I've added features/inputs/scanner4.rb which is a variation of the Scanner code and some minor test code that I will make work in this article. I'll walk through a few issues with it at the end.


In scanner.rb we define Scanner::ScannerString. ScannerString is "just" a subclass of String that allows us to have the scanner attach a Position to a token, which again allows us to add position information to the syntax tree for error reporting and debugging.

For this part we will lift ScannerString out of the Scanner class as embedded classes is not yet supported.

The next issue is our lack of attr_accessor. So we end up with this:

    class ScannerString < String
      # Instance variables in inherited classes did not work
      def initialize
        @position = 0 # Note: It's still awkward to use "nil", so we cop out for now.
      # "=" was not handled correctly for vtable thunks?
      def position= newp
        @position = newp
      def position

Compiling even this, however, proves a challenge, as per the inline comments above. The latter was just a trivial issue with the name handling. Test cases in 8cd9c18 and a one character fix (!) in 55b9d23

The former was trickier - I messed up in some subtle ways when I added the instance variable support that I missed by not testing with instance variables in sub-classes. I added a test case for this in e828033

In fixing this, I muddied things up a bit, and I've been too lazy to untangle the changes, as while tracking down these issues, I added some initial support for #inspect and getting hold of class names. We'll finish up that next, to not leave changes hanging.

In ca6f420 there are some minor changes in GlobalScope that follows from the changes in ClassScope - I'll ignore those - read the commit. The meat is in ClassScope in scope.rb (and later we'll look at changes to compiler.rb):

       @@ -186,14 +194,17 @@ class ClassScope
       # slot 0 is reserved for the vtable pointer for _all_ classes.
       # slot 1 is reserved for @instance_size for objects of class Class
    -  CLASS_IVAR_NUM = 2
    +  # slot 2 is reserved for @name
    +  CLASS_IVAR_NUM = 3
    -  def initialize(next_scope, name, offsets)
    +  def initialize(next_scope, name, offsets, superclass)
         @next = next_scope
    +    @superclass = superclass
         @name = name
         @vtable = {}
         @vtableoffsets = offsets
    -    @instance_vars = [:@__class__] # FIXME: Do this properly
    +    @ivaroff = @superclass ? @superclass.instance_size : 0
    +    @instance_vars = !@superclass ? [:@__class__]  : [] # FIXME: Do this properly
         @class_vars = {}

The bump in CLASS_IVAR_NUM is due to adding Class#name as mentioned above. More interestingly we now rectify a long standing omission: The scope chain did not keep track of superclass. We could look it up separately as needed, I guess, but we did not do that either. We now pass in a scope object that represents the super class.

We then assign @ivaroff to represent the offset that instance variables for this class start at. This bug is well into the "embarrassing" category. Without this, when we subclass a class, and add instance variables, the instance variables will get overlapping offsets, and overwrite each other. Oops.

Lastly, we set @instance_vars to start with @__class__ if there is no super class provided, to guarantee that we have a place to stash the class pointer (we could alternatively do this by setting @ivaroff to 1 in the same situation).

Next we ensure @ivaroff is included when we calculate the instance size, so we actually allocate enough memory for the instances too, unlike before (double-oops...)

    @@ -210,7 +221,7 @@ class ClassScope
       def instance_size
    -    @instance_vars.size
    +    @instance_vars.size + @ivaroff

Lastly, we ensure we return the right offset from the instance pointer in ClassScope:

    @@ -239,7 +250,14 @@ class ClassScope
           offset = @instance_vars.index(a)
           add_ivar(a) if !offset
           offset = @instance_vars.index(a)
    -      return [:ivar, offset]
    +      # This will show the name of the current class, the superclass name, the instance variable 
    +      # name, the offset of the instance variable relative to the current class "base", and the
    +      # instance variable offset for the current class which comes in quite handy when debugging
    +      # object layout:
    +      #
    +      # STDERR.puts [:ivar, @name, @superclass ? @superclass.name : "",a, offset, @ivaroff].inspect
    +      return [:ivar, offset + @ivaroff]

This isn't quite enough. We also need to update compile_class in compiler.rb:

First we obtain the pointer to the super class, and use that to properly initialize the class scope:

    @@ -635,7 +635,9 @@ class Compiler
       def compile_class(scope, name,superclass, *exps)
         @e.comment("=== class #{name} ===")
    -    cscope = ClassScope.new(scope, name, @vtableoffsets)
    +    superc = @classes[superclass]
    +    cscope = ClassScope.new(scope, name, @vtableoffsets, superc)

Note that there's another shortcut here: Ultimately we need to compute this too, as people can do nasty stuff like dynamically picking a class, assigning it to a constant, and subclassing that, so even if we have something that looks like a class name, what we actually have is actually an expression that evaluates to the Class object of the class that should be the superclass. I don't remember if the parser will even allow that at the moment, and I'm not in the mood to fix even the "simple" case of someone assigning stuff to constants and expecting me to treat it as a class, so we'll continue to ignore this for now and stumble over it later.

Then we fix up the assignment to the Class instance for the new class. The inline comment says it all, really:

    @@ -679,7 +681,17 @@ class Compiler
         compile_exp(scope, [:assign, name.to_sym, [:sexp,[:call, :__new_class_object, [cscope.klass_size,superclass,ssize]]]])
         @global_constants << name
    -    compile_exp(cscope, [:assign, :@instance_size, cscope.instance_size])
    +    # In the context of "cscope", "self" refers to the Class object of the newly instantiated class.
    +    # Previously we used "@instance_size" directly instead of [:index, :self, 1], but when fixing instance
    +    # variable handling and adding offsets to avoid overwriting instance variables in the superclass,
    +    # this broke, as obviously we should not be able to directly mess with the superclass's instance
    +    # variables, so we're intentionally violating encapsulation here.
    +    compile_exp(cscope, [:assign, [:index, :self, 1], cscope.instance_size])
    +    # We need to store the "raw" name here, rather than a String object,
    +    # as String may not have been initialized yet
    +    compile_exp(cscope, [:assign, [:index, :self, 2], name.to_s])

But all of that is not enough to fix our test-case (features/inputs/ivar.rb) as it turns out - now the instances variables of Foo are undefined in instances of Bar, since Bar#initialize does not call super (nor have we implemented support for super yet...). We need to patch #puts to handle our "fake" nils (that are still actual null values), which once again demonstrates that I need to make a decision on exactly what to do about this (in 10d7c6e):

    --- a/lib/core/object.rb
    +++ b/lib/core/object.rb
    @@ -49,8 +49,12 @@ class Object
         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))
    +      if raw
    +        raw = raw.to_s.__get_raw
    +        %s(if raw (puts raw))
    +      else
    +        puts
    +      end

Adding Class#name to improve #inspect and "send" debug output

Since parts of this made it into the previous commits. e977bfc adds test cases, and this:

    --- a/lib/core/class.rb
    +++ b/lib/core/class.rb
    @@ -40,6 +40,10 @@ class Class
    +  def name
    +    %s(__get_string @name)
    +  end

As mentioned earlier, we store the name "raw" to avoid bootstrap issues with String.

Another insidious little bug reared its head when dealing with the debugging output. The method name needs to be the second argument, since the first argument is our "hidden" place to store any block that gets passed to a method:

    --- a/compiler.rb
    +++ b/compiler.rb
    @@ -522,7 +522,7 @@ class Compiler
           if !off
             # Argh. Ok, then. Lets do send
             off = @vtableoffsets.get_offset(:__send__)
             -        args = [":#{method}".to_sym] + args
             +        args.insert(1,":#{method}".to_sym)
             warning("WARNING: No vtable offset for '#{method}' (with args: #{args.inspect}) -- you're likely to get a method_missing")
             #error(err_msg, scope, [:callm, ob, method, args])

With that out of the way, our failure to handle "send" can now easily be made to produce more useful output for things like this:

    class Foo
    f = Foo.new

As of 7fc23ae840 you get something like this, correctly identifying the class name and method:

WARNING: __send__ bypassing vtable (name not statically known at compile time) not yet implemented.
WARNING:    Method: 'bar'
WARNING:    symbol address = 0x8a36750
WARNING:    self = 0x8a36740
WARNING:    class 'Foo'

And a first pass on a default #inspect in 8c74cd6. Clearly adding cleaner support for string formatting also needs to go on the big list of outstanding items:

  def inspect
    %s(assign buf (malloc 20))
    %s(snprintf buf 20 "%p" self)
    %s(assign buf (__get_string buf))

Chasing rabbits...

Like ScannerString, we'll lift Position out of Scanner. We also avoid using Struct, and so get to write a few lines extra.

Thanks to the changes above, we now get semi-useful debugging output, and get the dubious pleasure of chasing down missing piece after piece. With my "scanner test in progress" it warned of a missing String#empty? used in Scanner#fill. I added String#empty in 334902c.

Next up, I get a method missing for ==. On adding the class name to the method_missing output, I get Class#==, which makes no sense. But String#length is empty, so this represents garbage where we don't properly clear the return value for an empty method. I added a first pass at String#length in c3eac1f.

Next up we're warned about Fixnum#getc?!? Turns out we call @io.getc in Scanner#get, and we stubbed out STDIN as 0 a while back... Changing it to IO.new (in 66e976f) suddenly gets us somewhere: My test code waits for input!

echo Foo | /tmp/scanner4 gave me a "send warning" for Fixnum#chr which I added in 186986f

Repeating this gave me method missing for String#[]. And here we'll spend a little bit more time, as there are (minor) complications ahead.

String#[] and %s(bindex)

First lets look at a not particularly inspired first version of String#[] in 7bc84e6:

    --- a/lib/core/string.rb
    +++ b/lib/core/string.rb
    @@ -16,6 +16,23 @@ class String
         %s(assign @buffer 0)
    +  def [] index
    +    l = length
    +    if index < 0
    +      index = l + index
    +      if index < 0
    +        return nil
    +      end
    +    end
    +    if index >= l
    +      return nil
    +    end
    +    %s(assign index (callm index __get_raw))
    +    %s(assign c (bindex @buffer index))
    +    %s(__get_fixnum c)
    +  end

First of all, we need bounds checking. String#length currently counts, which is obviously stupid, but we'll sort that out later. It's really only the last 3 lines we care about here. How do we get a single byte out of our strings? Well, so far we can't easily do that - we haven't exposed any way of addressing single bytes.

Above that's fixed by introducing bindex as a byte-oriented alternative to our 32-bit (or in theory pointer-sized - if/when we add a 64 bit target, it needs to be 64-bit) index primitive.

All the code does is obtain the raw index value, use it to obtain the raw byte value, and then obtain a Fixnum (note, we're still following Ruby 1.8 behaviour here - 1.9+ returns a String -, which we probably should stop with, given that the compiler itself is now updated to support 1.9; but devil you know and all that).

Apart from adding it to the @@keywords set in compiler.rb, we add this, which is a direct parallel to compile_index apart from not scaling the value, and the type we return. If we need more scales we might want to create a more generic version (also in 7bc84e6)

    +  # Compiles an 8-bit array indexing-expression.
    +  # Takes the current scope, the array as well as the index number to access.
    +  def compile_bindex(scope, arr, index)
    +    source = compile_eval_arg(scope, arr)
    +    r = @e.with_register do |reg|
    +      @e.movl(source, reg)
    +      source = compile_eval_arg(scope, index)
    +      @e.save_result(source)
    +      @e.addl(@e.result_value, reg)
    +    end
    +    return [:indirect8, r]
    +  end

This again requires some changes to emitter.rb to add support for loading :indirect8:

    --- a/emitter.rb
    +++ b/emitter.rb
    @@ -234,6 +234,8 @@ class Emitter
           return load_address(aparam)
         when :indirect
           return load_indirect(aparam)
    +    when :indirect8
    +      return load_indirect8(aparam)
         when :arg
           return load_arg(aparam,reg || result_value)
         when :lvar
    @@ -325,6 +327,13 @@ class Emitter
    +  def load_indirect8(arg)
    +    movzbl("(#{to_operand_value(arg,:stripdollar)})", :eax)
    +    # FIXME: gcc includes this second movzbl; why is it needed?
    +    movzbl(:al,:eax)
    +    :eax
    +  end

In which we unwillingly revisit register allocation

This leads us further down the rabbit hole: A method missing for String#position.... Which should be Scanner#position, accessed via self.position in Scanner#get.

I wish I'd taken better notes of how I tracked down this bug, but it involved lots of printf type debugging making use of our now available Class#name etc., as well as pouring over the asm output. The problem is actually triggered in Scanner#fill, which in my test version looks like this:

      def fill
        if @buf.empty?
          c = @io.getc
          c = c.chr if c
          @buf = c ? c.to_s : ""

Looks innocent, because it is. However, the asm output is not so innocent and reflects how tricky getting register allocation right is. The below fragment reflects just @buf = c ? c.to_s : "".

       # RA: Allocated reg 'ecx' for c
        # [:lvar, 0, :ecx]
        movl    -8(%ebp), %ecx
        testl   %ecx, %ecx
        je  .L189

Above we've loaded c and we're jumping to .L189 if false.

Now we execute c.to_s:

        # callm :c.:to_s
        subl    $8, %esp
        movl    $2, %ebx
        pushl   %ebx
        # RA: Already cached 'ecx' for c
        movl    %ecx, 4(%esp)
        movl    $0, 8(%esp)
        popl    %ebx
        movl    (%esp), %esi
        movl    (%esi), %eax
        call    *384(%eax)
        # Evicting self
        addl    $8, %esp
        # callm c.to_s END
        jmp .L190

At the end, note that we're marking self as evicted from %esi where we put it.

Now for the "else" part, that just returns an empty string:

        subl    $4, %esp
        movl    $1, %ebx
        movl    $.L0, %eax
        movl    %eax, (%esp)
        movl    $__get_string, %eax
        call    *%eax
        addl    $4, %esp
        # RA: Allocated reg 'esi' for self
        # [:arg, 0, :esi]
        movl    8(%ebp), %esi

Hang on? At the end, this reloads self into %esi, which in itself isn't a problem. The problem is that since the very next label, .L190, reflects a merge of two control flows, even though self was just reloaded, unless we know that self will be present in %esi when leaving the "if" arm above too, the code below is broken:

.L190: movl %eax, %ecx # RA: Already cached 'esi' for self movl %ecx, 8(%esi)

... because it assumes self is cached. And in fact, it is totally broken: %esi will reflect the class of c, because of the c.to_s call that is the last part of the ternary-if arm above. There are several ways of fixing this, one of them being to try to prove which registers are safe across both control flows. The other, the brute-force approach, is to assume all bets are off and start afresh.

The change is trivial, so you can see it in 549e091

Method 'comma' ?!?

    echo Foo | /tmp/scanner4
    Got: 70 (PEEK)
    WARNING: __send__ bypassing vtable (name not statically known at compile time) not yet implemented.
    WARNING:    Method: 'comma'
    WARNING:    symbol address = 0x8580510
    WARNING:    self = 0x85802e0
    WARNING:    class 'Scanner'
    Method missing: Class#==

We don't have a method comma. So let's break out the debug output with ruby compiler.rb --norequire --parsetree:

          (defm position ()
            (let (pos __env__ __tmp_proc)
              (assign pos (callm Position new (@filename (comma @lineno @col))))

The relevant part corresponds to:

        pos = Position.new(@filename,@lineno,@col)

So let's add a test case to parser.feature:

    +      | "Position.new(@filename,@lineno,@col)" | [:do, [:callm, :Position, :new, [:"@filename", :"@lineno", :"@col"]]] |       |

The problem here is in treeoutput.rb, which badly needs more comments... The code attempts to simplify the parse tree created by the operator precedence parser, in order to make it easier to work with later.

The relevant part is this, which triggers on method calls etc.. I've included the one line fix as a diff. It's in 13368e0:

          elsif la and leftv[0] == :callm and o.sym == :call
            block = ra && rightv[0] == :flatten && rightv[2].is_a?(Array) && rightv[2][0] == :block
            comma = ra && rightv[0] == :comma
    -       args = comma || block ? flatten(rightv[1..-1]) : rightv
    +       args = comma || block ? flatten(rightv) : rightv          
            args = E[args] if !comma && !block && args.is_a?(Array)
            args = E[args]
            if block
              @vstack << leftv.concat(*args)
              @vstack << leftv + args

The hint to the location comes from seeing the "comma" reference. If we add a --dont-rewrite flag and re-run ruby compiler.rb as above, we get this:

              (assign pos (call (callm Position new) (comma @filename (comma @lineno @col))))

So the rewrite fails to rewrite the last part. The bug probably stems from forgetting that rightv in the above case refers to the entire argument list.

Delayed reaction

The next problem up is a method missing for Class#==, which occurs in Scanner#get where I marked with "(1)":

      def get
        pos = self.position
    # (2)
        ch = @buf.slice!(-1,1)
        @col = @col + 1
    # (1)
        if ch == "\n"
          @lineno = @lineno + 1
          @col = 1

So at (1), ch is of object Class. Since we get ch from @buf.slice!(-1,1) above, that's where we need to look. The immediately obviously reason is that String#slice! was not implemented at all. It is in 5133315 which I'm not in the mood to walk through (but do feel free to ask in the comments if anything is unclear) - it's virtually guaranteed to be possible to clean up. The only thing I want to mention is __copy_raw, which is an alternative to __set_raw that will copy the raw buffer instead of just setting the pointer:

      def __copy_raw(str,len)
        %s(assign len (callm len __get_raw))
        %s(assign @buffer (malloc len))
        %s(memmove @buffer str len)

In the above commit I've also included String#== as that is the "next one out" and quite obviously so from the earlier error. The one thing to worth noting about that, is that "!" is not implemented, and that I also added an Object#true as a workaround. A shameful hack.

Next we need Object#nil?, because "!" does not work, and so a "!" occurrence in Scanner#get was changed to #nil? for the test code.

Fixnum#position !?

Since we've already run into problems with register allocation, I'm not going to go into a lot of detail about the debugging here. Suffice to say that given that we're not actually calling "#position" on what should be a Fixnum, it was time to break out the assembly source, and look at what was actually being called. It was quickly clear that the wrong value was in the register.

I decided it was time to add some rspec tests for regalloc.rb, and you can find the first set in 9bfee76.

That didn't reveal anything, and I had to start digging into #with_register. The test case that reproduces the problem is in 8dcd18b together with the one line fix. The problem turned out to be that #with_register calls evict on a register found in the cache, and then hands the register out, without taking into account that evict put the register back on the free list.


Next is another case of the wrong value being returned. Going over assembly output again, I could find no obvious register allocation issue. Next up was peppering some puts some_object.class.name around to see where the objects got confused, and this let to compile_return. This is likely indirectly a regression caused by the register allocation: As it turns out, previously, we've not used the return statement other than in cases where it was not strictly necessary, as the last computation left the result in %eax. But this is substantially less likely after introducing the register allocation.

#compile_return simply did not ensure the result of the evaluation of its argument would be saved to `%eax:

       def compile_return(scope, arg = nil)
    -    compile_eval_arg(scope, arg) if arg
    +    @e.save_result(compile_eval_arg(scope, arg)) if arg

And there we are...

Some notes on scanner4.rb

I'll just briefly mention some remaining problems.

First of all, I found a bug in string interpolation, that I'll likely fix separate from the following articles, unless it proves particularly interesting:

      def inspect
    # Works:
    #    puts self.lineno
    #    puts self.filename
    # FIXME: Seg faults
        #    "line #{self.lineno}, col #{self.col} in #{self.filename}"
    # FIXME: Including self.lineno or self.col seg faults:
        "line #{@lineno}, col #{@col} in #{@filename}"

Secondly there's this:

     # FIXME: += translates to "incr" primitive, which is a low level instrucion
     @col = @col + 1

As above, I might fix that separately. For now I considered the workaround the most expedient way of getting further.

Lastly there's this horrific piece:

# FIXME: ScannerString is broken -- need to handle String.new with an argument
#  - this again depends on handling default arguments

    s = ScannerString.new
    r = ch.__get_raw

This obviously needs to be fixed. The issue is that a proper fix it requires handling default arguments, as well as super so that ScannerString as a subclass of String can pass on the string argument rather than set it after the fact (I could have hidden the #__get_raw and #__set_raw bits in ScannerString, but that would just have obscured the problem)


Next we'll deal with the issue above, of default arguments and super.

Then in the following part, we'll be looking at the next step towards compiling a test program that uses the compiler code to parse s-expressions, which will be to get Scanner#expect to work.

blog comments powered by Disqus