Debugging ParseTree (or Walking in Great Footsteps)

In the course of creating CheckR, Pat Eyler and I discovered the following strangeness:

First example. Case with expression followed by multiple whens and an else.

$ echo 'case 1; when 2; 3; when 4; 5; else; 6;end' | parse_tree_show -f
[[:class,
 :Example,
 :Object,
 [:defn,
  :example,
  [:scope,
   [:block,
    [:args],
    [:case,
     [:lit, 1],
     [:when, [:array, [:lit, 2]], [:lit, 3]],
     [:when, [:array, [:lit, 4]], [:lit, 5]],
     [:lit, 6]]]]]]]
$

This results in a clear AST (abstract syntax tree).

Second example. Case with no expression followed by identical whens and else.

$ echo 'case; when 2; 3; when 4; 5; else; 6;end' | parse_tree_show -f
[[:class,
 :Example,
 :Object,
 [:defn,
  :example,
  [:scope, [:block, [:args], [:when, [:array, [:lit, 2]], [:lit, 3]]]]]]]
$

Since the only change was making case 1;' into 'case;, this AST is far from clear and is obviously missing things. There is no case node, no second when node and no else value. Unfortunately, for CheckR, we need the when nodes for our testing. Something has to be done.

Pat is on very good terms with drbrain (Eric Hodel) and zenspider (Ryan Davis) as the three of them ran Seattle.rb together. A few IMs later the bug was confirmed against the development branch of ParseTree. drbrain recorded a bug on the ParseTree RubyForge bug tracker and assigned it to zenspider.

Because I want to be a responsible netizen and (let's admit it) because I want to be cool like the big boys, I decided to create a test case for inclusion in the ParseTree test suite. Then, because it would be even cooler, and because Pat is always there egging me on, I thought I would take a whack at fixing ParseTree myself, with Pat's help.

Because of Pat's relationship with zenspider, we had access to a snapshot of the development tips of ParseTree. zenspider is not using RubyForge to host the dev code, so not everyone has access to this. As a result, I will document the rest of this story as if we had access to the same things the world has access to. All references to source code will be to the released code for ParseTree-1.3.7.

First the test case. This is very likely to be wrong since I don't have a correct AST of the case;when syntax but it is a start. ParseTree uses two files to dynamically generate its test case, something.rb and test_parse_tree.rb. something.rb contains method and class definitions to be parsed. test_parse_tree.rb contains expected ASTs to be compared against the ASTs generated during the tests. All it takes to add a new test case is add the method definition to something.rb and the expected AST to test_parse_tree.rb.

Before we go mucking things up, we need to know where the test suite stands as released. We have to make sure we don't break anything else when we add our own tests.

The following results were produced on Cygwin. It was also necessary on Cygwin to comment out $TESTING = true in test_composite_sexp_processor.rb and test_sexp_processor.rb in order to get RubyInline to work correctly when compiling for the test. Many thanks to drbrain for his patience and help with that particular problem.

$ cd /usr/lib/ruby/gems/1.8/gems/ParseTree-1.3.7
$ make test
Loaded suite test/test_all
Started
.....F.F..F......F..............................F................................
Finished in 0.328 seconds.

-- output snipped due to length --

81 tests, 94 assertions, 5 failures, 0 errors
make: *** [test] Error 1
$

If I recall, there were only 4 errors in linux when I ran this same test. Either way, it is very important to know about the failing tests before we start. We don't want to assume we broke more than we intended when we add our tests. (As an asside, the dev branch doesn't have these errors, allowing us to be even more confident in what we do.) Now, on to the test.

in test/something.rb

def case_stmt2
 case
 when 1
   2
 when 3
   4
 else
   5
 end
end

This is fairly simple but contains everything I know about the problem to date. Namely, ParseTree seems to eat the case, when 3 and else.

in test/test_parse_tree.rb

 @@case_stmt2 = [:defn, :case_stmt2,
   [:scope,
     [:block,
       [:args],
       [:case,
         [:when, [:array, [:lit, 1]], [:lit, 2]],
         [:when, [:array, [:lit, 3]], [:lit, 4]],
         [:lit, 5]]]]]

At first glance, it seems fairly difficult to generate this and it would have been if I had done it by hand. The easy way was to run the following command, steal its output and munge it just a little bit.

$ echo 'class Blah; def case_stmt2; case true; when 1; 2; when 3; 4; else; 5; end; end; end' | parse_tree_show
[[:class,
 :Blah,
 :Object,
 [:defn,
  :case_stmt2,
  [:scope,
   [:block,
    [:args],
    [:case,
     [:true],
     [:when, [:array, [:lit, 1]], [:lit, 2]],
     [:when, [:array, [:lit, 3]], [:lit, 4]],
     [:lit, 5]]]]]]]

Looking at the other expected trees, we see they all start with the method definition. Also, we need to remove the [:true] because it doesn't appear in our test method. I want to reiterate, the resulting expectation, recorded above in test_parse_tree.rb may not be correct but it is a place to start.

Finally, we run our test again.

$ make test
ruby  -w -Ilib:bin:../../RubyInline/dev test/test_all.rb
Loaded suite test/test_all
Started
.....F.F..FF......F..............................F................................
Finished in 0.354 seconds.

-- output snipped due to length --

  3) Failure:
test_case_stmt2(TestParseTree) [(eval):1]:
<[:defn,
 :case_stmt2,
 [:scope,
  [:block,
   [:args],
   [:case,
    [:when, [:array, [:lit, 1]], [:lit, 2]],
    [:when, [:array, [:lit, 3]], [:lit, 4]],
    [:lit, 5]]]]]> expected but was
<[:defn,
 :case_stmt2,
 [:scope, [:block, [:args], [:when, [:array, [:lit, 1]], [:lit, 2]]]]]>.

-- output snipped due to length --

82 tests, 95 assertions, 6 failures, 0 errors
make: *** [test] Error 1
$

One new test failure and it's our test. Perfect. Also, if you look closely, you will see our new test is included in the massive output of test_class. That's important because even if we started with no test failures at all, our addition of one test would cause two failures. test_class is an integration test of the class as a whole (including all methods) and ensures that working methods still parse in a sane way as a class and also that the AST for the class definition itself is correct.

Now, any sane person would stop here, submit the test to the ParseTree developers and call it a day. Unfortunately, neither Pat nor I appears to be sane, so we started chasing the cause of the failure.

To Be Continued....