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.
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.
end
# "=" was not handled correctly for vtable thunks?
def position= newp
@position = newp
end
def position
@position
end
end
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 = {}
end
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
end
def instance_size
- @instance_vars.size
+ @instance_vars.size + @ivaroff
end
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]
end
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
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
ob
end
+ 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])
end
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
end
f = Foo.new
f.bar
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))
"#"
end
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.
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)
end
+ 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
movl(src,"(%#{dest.to_s})")
end
+ 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
+
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 : ""
end
end
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:
.L189:
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
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))))
pos
)
)
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)
else
@vstack << leftv + args
end
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.
The next problem up is a method missing for Class#==, which occurs in Scanner#get where
I marked with "(1)":
def get
fill
pos = self.position
# (2)
ch = @buf.slice!(-1,1)
@col = @col + 1
# (1)
if ch == "\n"
@lineno = @lineno + 1
@col = 1
end
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)
end
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.
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
@e.leave
@e.ret
[:subexpr]
And there we are...
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}"
end
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
s.__set_raw(r)
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.