>>> Older entries

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.

Messy further steps towards self-hosting

This part is going to be a hodge-podge of changes, as I walk through a good chunk of changes needed to prepare to compile the tokenization code in tokenizer.rb, and improves what we can handle from scanner.rb.

I'm going to start by briefly talking about this commit:

  • [part-41 d0ee180] Refactoring of tokenizer

This commit breaks tokenizer.rb into several separate files. And that was the starting point for this part. To identify what I had to do, I broke apart the Tokenizer module, and wrote a few small scripts to see what compiled, and what crashed. E.g:


    require 'selfhost/atom'
    require 'selfhost/scanner'
    
    s = Scanner.new(STDIN)
    
    i = Tokens::Atom.new
    
    puts i.expect(s)

(I haven't checked in the "selfhost" directory - the files there are mostly like the broken up tokenizer.rb)

The purpose was to tweak the classes however much I needed to compile them, then fix or tweak until I got them mostly working, based on whatever errors I run into.

The purpose of this is of course to get one step closer to the first big "selfhosting" goal of being able to run the s-expression parser.

Rather than following the entire process, which was simple yet tedious, I'll walk through the most important commits, and simply list the others.

A number of minor tweaks

I'm going to skip over these, other than mentioning the commits. They are all important, but trivial. If you have any questions about them, I'm happy to answer comments:

  • [part-41 8fe7103] Add FalseClass#to_s
  • [part-41 79d39f4] Add TrueClass#to_s
  • [part-41 e31a44e] Added first stab at NilClass#==
  • [part-41 814b520] Naive / incomplete (base 10 only) version of String#to_i
  • [part-41 2f8ecb7] Absent #is_a? etc., adding explicit nil check in Fixnum#== as a temporary hack to get the parser closer to self-hosted
  • [part-41 7ae9623] Replace += with << in tokenizer and scanner; partly because it may be more efficient, partly because it removes an obstacle to self-hosting
  • [part-41 6f1c5a1] Let get_arg transparently convert true/false to :true, :false
  • [part-41 7429885] Fixed handling of quoted strings in asm output
  • [part-41 72d255e] Prevent 'require' loops by 'registering' the required file as empty at the outset
  • [part-41 ffda923] Added String#+
  • [part-41 a1af1fb] Assume :assign outside %s() returns an object

Valid return addresses for empty methods

  • [part-41 7b4cf91] Ensure a valid return value for empty method (caused String#to_i to seg fault)

Until now, if a method did not specify a return value, we'd leave garbage in %eax. Ruby does in fact require nil to be returned in most instances where there's not a sane last expression value to depend on.

The case of the argumentative not operator

For a while I was baffled at why the not-operator methods required an extra argument, and used workarounds:

  • [part-41 e2f6b37] Another workaround for not operator requiring arguments
  • [part-41 d734bb4] Added dummy/trivial not operator for String

Here I fixed it:

  • [part-41 1d54cec] Fix situation where not operator methods needed an argument

The specific line that fixes it was this from transform.rb:


         e[3] = E[e[2]] if e[2]

Previously this was done unconditionally, which meant that if e[2] was already an empty array, we wrapped it in another array and unintentionally gave a method call an extra, though invalid, argument.

Range class

  • [part-41 a18cdef] Add first trivial version of Range class + rewrite :range nodes in AST to Range.new(...)

The tokenizer classes relies on ranges in a number of locations. This commit takes a first tiny stab at a basic version of the Range class, and also adds support for literal ranges (1..5), through this bit added to transform.rb:


    +  def rewrite_range(exp)
    +    exp.depth_first do |e|
    +      if e[0] == :range
    +        STDERR.puts e.inspect
    +        e.replace(E[:callm, :Range, :new, e[1..-1]])
    +      end
    +      :next
    +    end
    +  end
    +

Quirks of parsing Ruby

  • [part-41 dbfe020] Function/method calls with arguments inside () or without parentheses have different needs for the priority of the call operator; we need to push a variation with a different priority onto the operator stack if we detect a method call without an opening parenthesis (caveat: Ruby has rules regarding whitespace here too, that I believe we're currently not taking into account)

What this is talking about (unfortunately the commit is really messy and includes unrelated whitespace and documentation changes etc - I was sloppy; sorry about that), is for example the difference between these expressions:


        foo(45 + 5)
        foo 45 + 5

Prior to this change, these were handled differently. The synthetic "call" operator used by the shunting yard parser needs a high priority to bind tightly to the function arguments. But in the absence of parentheses, this means it bound too tightly to the tokens immediately following, so that the latter example above would be treated as foo(45) + 5 because the call operator was given higher precedence than +.

This was resolved by introducing a second call operator, and in the instance where we are handling functions without a leading parenthesis, that operator (with much lower priority) is pushed onto the operator stack instead:


        if possible_func
          reduce(ostack)
    -     ostack << opcall
    +     ostack << @opcall2
        end

Correctly compiling "||"

  • [part-41 456a989] Improved comments / label names for #compile_if and fixed rather broken 'or' logic
  • [part-41 c288585] Rewrite compile_or to deal properly with shortcut logic, and in process do slight refactor to split out common functionality also used by compile_if and compile_while

As it turned out, my previous attempt at implementing || was completely broken. I don't know what I was thinking. All evidence is that I was not.

The original "||" implementation basically turned <left> || <right> into if <left>; false; else <right>; end. Which sort-of works, except it discards the result from <left>, which obviously isn't acceptable.

The first commit above improves that every so slightly by changing the implementation into the equivalent of this pseudo code:


      __left = <left>
      if __left
         __left
      else
         <right>
      end

But that really was not a very satisfying solution. So the next commit changes it drastically, and also refactors #compile_if and #compile_while, and at the same time takes a stab at handling our minimal static typing in a reasonable way. Here's how #compile_or changed:


       def compile_or scope, left, right
         @e.comment("compile_or: #{left.inspect} || #{right.inspect}")
    -    # FIXME: Eek. need to make sure variables are assigned for these. Turn it into a rewrite?
    -    compile_eval_arg(scope,[:assign, :__left, left])
    -    compile_if(scope, :__left, :__left, right)
    +
    +    ret = compile_eval_arg(scope,left)
    +    l_or = @e.get_local + "_or"
    +    compile_jmp_on_false(scope, ret, l_or)
    +
    +    l_end_or = @e.get_local + "_end_or"
    +    @e.jmp(l_end_or)
    +
    +    @e.comment(".. or:")
    +    @e.local(l_or)
    +    or_ret = compile_eval_arg(scope,right)
    +    @e.local(l_end_or)
    +
    +    @e.evict_all
    +
    +    combine_types(ret,or_ret)
       end

Which does roughly this, as pseudo-code:


        ret = <left>
        if !ret goto <label>_or
        goto <label>_end_or
    <label>_or:
        <right>
    <label>_end_or:

You'll note this is not optimal, we can improve on it by adding code to avoid one of the branches, but this was a decent shortcut to let it still share code with #compile_if and #compile_while.

#compile_jmp_on_false and #combine_types are worth a quick look. #compile_jmp_on_false extracts part of #compile_if as follows:


    +  def compile_jmp_on_false(scope, r, target)
    +    if r && r.type == :object
    +      @e.save_result(r)
    +      @e.cmpl(@e.result_value, "nil")
    +      @e.je(target)
    +      @e.cmpl(@e.result_value, "false")
    +      @e.je(target)
    +    else
    +      @e.jmp_on_false(target, r)
    +    end
    +  end

As you can see, the main reason it has been given its own method is to handle the case where we check the truthyness of an object.

#combine_types looks like this:


        +  def combine_types(left, right)
        +    type = nil
        +    if left && (!right || left.type == right.type)
        +      type = left.type
        +    end
        +    return Value.new([:subexpr],type)
        +  end

This was also extracted from #compile_if, and is responsible for ensuring the weaken the type information. Which is the fancy way of saying that if the type of the left hand expression matches that of the right hand expression, we return that type. Otherwise, we return "nil" in the type field, which in our current incarnation means "we have no clue, this could be anything" which means we won't take any object-specific action elsewhere.

Resolving Foo::Bar

  • [part-41 3a7e275] Add default implementations for new Scope#add_constant and Scope#find_constant
  • [part-41 6ceb215] Turn '::' into internal operator :deref, and add machinery to pre-build scope chain and traverse it to resolve class constant names at compile time where possible
  • [part-41 960f1b0] Make use of new inner classes support to bring test case closer to real Scanner implementation

Next up we need to handle inner classes. The first step is to actually capture Foo::Bar as different to Foo.bar, as it was previously. We do this by introducing the internal :deref operator in the parse tree in 6ceb215 in operators.rb:


    -  "::"        => Oper.new(100, :callm,    :infix, 2,2,:left),
    +  "::"        => Oper.new(100, :deref,    :infix, 2,2,:left),

The next step is a major change to build a sequence of class scope objects. Consider the case where I open a class, define a method that refers to an as yet undefined class. Then later I re-open the class and define the earlier class as an inner class:


    class Foo
       def hello
         Bar.new
       end
    end
    
    class Foo
       class Foo
         class Bar
         end
       end
    end

To handle this case, ClassScope objects must persist across open/close of a class, and they do. However, to compile this to static references, I also must identify any references and resolve them, to be able to distinguish a possible ::Bar from ::Foo::Bar without being forced to do runtime lookups (we still need to be able to fall back to dynamic constant lookup at some point in the future).

So lets take a look at the code, in transform.rb:


    +  def build_class_scopes(exps, scope = nil)
    +    scope = @global_scope if !scope
    +
    +    return if !exps.is_a?(Array)
    +
    +    exps.each do |e|
    +      if e.is_a?(Array)
    +        if e[0] == :defm && scope.is_a?(ClassScope)
    +          scope.add_vtable_entry(e[1]) # add method into vtable of class-scope to associate with class
    +
    +          e[3].depth_first do |exp|
    +            exp.each do |n|
    +              scope.add_ivar(n) if n.is_a?(Symbol) and n.to_s[0] == ?@ && n.to_s[1] != ?@
    +            end
    +          end

Firstly, above, we deal with method definitions, by identifying instance variables that are plainly mentioned (we still don't support dynamically generated ivars).

Then this bit was extracted from compile_class as we may as well allocate these earlier:


    +        elsif e[0] == :call && e[1] == :attr_accessor
    +          # This is a bit presumptious, assuming noone are stupid enough to overload
    +          # attr_accessor, attr_reader without making them do more or less the same thing.
    +          # but the right thing to do is actually to call the method.
    +          #
    +          # In any case there is no actual harm in allocating the vtable
    +          # entry.`
    +          #
    +          # We may do a quick temporary hack to synthesize the methods,
    +          # though, as otherwise we need to implement the full define_method
    +          # etc.
    +          arr = e[1].is_a?(Array) ? e[2] : [e[2]]
    +          arr.each {|entry|
    +            scope.add_vtable_entry(entry.to_s[1..-1].to_sym) 
    +          }

And then we handle the case of the class or module blocks themselves, by creating the ClassScope objects that will hold the scope information, and recursing, as well as finally recursing for all other AST node types:


    +        elsif e[0] == :class || e[0] == :module
    +          superclass = e[2]
    +          superc = @classes[superclass.to_sym]
    +          cscope = @classes[e[1].to_sym]
    +          cscope = ClassScope.new(scope, e[1], @vtableoffsets, superc) if !cscope
    +          @classes[cscope.name.to_sym] =  cscope
    +          @global_scope.add_constant(cscope.name.to_sym,cscope)
    +          scope.add_constant(e[1].to_sym,cscope)
    +          build_class_scopes(e[3], cscope)
    +        elsif e[0] == :sexp
    +        else
    +          e[1..-1].each do |x|
    +            build_class_scopes(x,scope)
    +          end
    +        end
    +      end
    +    end
    +  end

And at the top level in transform.rb we hook this step in early, starting by initializing the GlobalScope object, so we have something to hook the class scopes into:


       def preprocess exp
    +    # The global scope is needed for some rewrites
    +    @global_scope = GlobalScope.new(@vtableoffsets)
    +    build_class_scopes(exp)
    +

There are a number of smaller supporting changes, but lets just look at compile_deref that handles the new internal :deref node as a starting point:


    +  def compile_deref(scope, left, right)
    +    cscope = scope.find_constant(left)
    +    raise "Unable to resolve: #{left}::#{right} statically (FIXME)" if !cscope || !cscope.is_a?(ClassScope)
    +    get_arg(cscope,right)
    +  end

This simply delegates to the new find_constant methods in the scope classes, which for ClassScope recurses and builds a multi-level class name (e.g. Foo__Bar) - in classcope.rb:


    +  def find_constant(c)
    +    const = @constants[c]
    +    return const if const
    +    return @next.find_constant(@name+"__"+c.to_s) if @next
    +    return nil
    +  end

Rewriting :incr

  • [part-41 b3edea5] Rewrite :incr internal operator into += method call

There's not much to say about this. The whole change simply adds a small bit to treeoutput.rb that on coming across [:incr, :foo] insteads translates it into [:callm, :foo, :"+", right hand expression.

is_a?

  • [part-41 e19a85d] Support for #is_a?; also needed to add default Object#==, since comparison of object references is used in the #is_a? implementation

This implements a very basic #is_a? implementation that simply loops up the superclass chain.

It required the implementation itself, but also adding a basic Object#== that does pointer based comparison, and Class#superclass itself.

attr_reader / accessor / writer

  • [part-41 af00ab3] Filter out leading nil's where E[node.position, ....] is called and node does not have a position set

The above is a one-liner that helps debugging by ensuring the position doesn't get accidentally set to nil.

  • [part-41 ee85225] Quick and dirty attr_accessor / attr_reader / attr_writer implementation and minor bug fix (array index e[1] => e[2])
  • [part-41 83f0333] Made use of attr_reader / writer / accessor, and fixed += operator to bring test Scanner version closer in line with the real Scanner

A while back I was holding back on this awaiting a full define_method implementation, so I could do this in pure Ruby, but since I pulled back on that, it's time for a simple implementation since it helps actually get closer to compile the unmodified scanner. The bulk of is this in transform.rb, which simply injects one or two method definitions:


    +
    +          # Then let's do the quick hack:
    +          #
    +
    +          type = e[1]
    +          syms = e[2]
    +
    +          e[0] = :do
    +          e.slice!(1..-1)
    +          syms.each do |mname|
    +            mname = mname.to_s[1..-1].to_sym
    +            if (type == :attr_reader || type == :attr_accessor)
    +              e << E[:defm, mname, [], ["@#{mname}".to_sym]]
    +            end
    +            if (type == :attr_writer || type == :attr_accessor)
    +              e << E[:defm, "#{mname}=".to_sym, [:value], [[:assign, "@#{mname}".to_sym, :value]]]
    +            end
    +          end

Refactoring

I won't comment further on these:

  • [part-41 0084643] Refactored *Scope classes into separate files
  • [part-41 d9d9d2b] Refactoring: Split compiler driver out into separate file
  • [part-41 7fe231b] Refactored out code related to compiling function and method calls
  • [part-41 2da30b5] Refactoring
  • [part-41 083d0b5] Additional refactoring

Next steps

My current plans (subject to changes):

  • Part 42 will cover re-opening classes
  • Part 43 will cover Eigenclasses.
  • Part 44 will wrap up a few niggling issues with compiling the tokenization code, such as named block arguments (&block), possibly Struct, and any other small issues required for self-hosting
  • Part 45 will start to attack ParserBase. The most likely subject is #send and according method lookup machinery (this also affects the main Compiler class). There's also the issue of exceptions, though I'm unsure if I want to deal with that yet, as well as #include'ing modules.
  • Part 46-50 - by this point I expect to wrap up self-hosting of the s-expression parser, and start attacking the operator precedence parser. At this point we should have gotten rid of the worst hindrances for full self-hosting, ad I hope to get there by part 50.

These may be hopelessly optimistic:

Parts 51-60 or so:

  • Parse (possibly not correctly) all of Rubyspec.
  • Run mspec (for Rubyspec)
  • Case studies of compiling (and fixing issues with) specific applications.
  • Yanking out "gas" and generate asm opcodes directly. JIT to support eval().
  • Refactoring towards better support for retargeting to another backend
  • Start on an x86-64 backend

Part 61-70 or so:

  • Optimization and re-targeting
  • Rubyspec compliance
  • A "review"/revisit of the major components
Read the comments / Have a comment? Click here

Older Entries 

<<< Back to top