* test/ruby/sentence.rb: Sentence class implemented

  based on sentgen.rb

* test/ruby/sentgen.rb: removed.

* test/ruby/test_assignment.rb: use sentence.rb.

* test/ruby/test_yield.rb: block parameter passing emulator
  implemented.


git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@13064 b2dd03c8-39d4-4d8f-98ff-823fe69b080e

4 files changed, 470 insertions, 277 deletions

diff --git a/test/ruby/sentence.rb b/test/ruby/sentence.rb
new file mode 100644
index 0000000000..3697fbea10
--- /dev/null
+++ b/test/ruby/sentence.rb
@@ -0,0 +1,338 @@
+# sentence
+
+class Sentence
+  def initialize(ary)
+    @sent = ary
+  end
+
+  def to_s
+    @sent.join('')
+  end
+
+  def to_a
+    @sent
+  end
+
+  def [](i)
+    Sentence.new(@sent[i])
+  end
+
+  def inspect
+    "#<#{self.class}: #{@sent.inspect}>"
+  end
+
+  def subst(target, &b)
+    Sentence.new(subst_rec(@sent, target, &b))
+  end
+
+  def subst_rec(obj, target, &b)
+    if obj.respond_to? :to_ary
+      a = []
+      obj.each {|e| a << subst_rec(e, target, &b) }
+      a
+    elsif target === obj
+      yield obj
+    else
+      obj
+    end
+  end
+
+  def find_subtree(&b)
+    if r = find_subtree_rec(@sent, &b)
+      Sentence.new(r)
+    else
+      nil
+    end
+  end
+
+  def find_subtree_rec(obj, &b)
+    if obj.respond_to? :to_ary
+      if b.call obj
+        return obj
+      else
+        obj.each {|e|
+          r = find_subtree_rec(e, &b)
+          return r if r
+        }
+      end
+    end
+    nil
+  end
+
+  def expand(&b)
+    Sentence.new(expand_rec(@sent, &b))
+  end
+
+  def expand_rec(obj, r=[], &b)
+    #puts "#{obj.inspect}\t\t#{r.inspect}"
+    if obj.respond_to? :to_ary
+      if b.call obj
+        obj.each {|o|
+          expand_rec(o, r, &b)
+        }
+      else
+        a = []
+        obj.each {|o|
+          expand_rec(o, a, &b)
+        }
+        r << a
+      end
+    else
+      r << obj
+    end
+    r
+  end
+
+  def Sentence.each(syntax, sym, limit)
+    Gen.new(syntax).each_tree(sym, limit) {|tree|
+      yield Sentence.new(tree)
+    }
+  end
+
+  class Gen
+    def Gen.each_tree(syntax, sym, limit, &b)
+      Gen.new(syntax).each_tree(sym, limit, &b)
+    end
+
+    def Gen.each_string(syntax, sym, limit, &b)
+      Gen.new(syntax).each_string(sym, limit, &b)
+    end
+
+    def initialize(syntax)
+      @syntax = syntax
+    end
+
+    def self.expand_syntax(syntax)
+      syntax = remove_underivable_rules(syntax)
+      syntax = expand_justempty_rules(syntax)
+      syntax = remove_emptyable_rules(syntax)
+      syntax = expand_channel_rules(syntax)
+
+      syntax = expand_noalt_rules(syntax)
+      syntax = reorder_rules(syntax)
+    end
+
+    def self.remove_underivable_rules(syntax)
+      deribable_syms = {}
+      changed = true
+      while changed
+        changed = false
+        syntax.each {|sym, rules|
+          next if deribable_syms[sym]
+          rules.each {|rhs|
+            if rhs.all? {|e| String === e || deribable_syms[e] }
+              deribable_syms[sym] = true
+              changed = true
+              break
+            end
+          }
+        }
+      end
+      result = {}
+      syntax.each {|sym, rules|
+        next if !deribable_syms[sym]
+        rules2 = []
+        rules.each {|rhs|
+          rules2 << rhs if rhs.all? {|e| String === e || deribable_syms[e] }
+        }
+        result[sym] = rules2.uniq
+      }
+      result
+    end
+
+    def self.expand_justempty_rules(syntax)
+      justempty_syms = {}
+      changed = true
+      while changed
+        changed = false
+        syntax.each {|sym, rules|
+          next if justempty_syms[sym]
+          if rules.all? {|rhs| rhs.all? {|e| justempty_syms[e] } }
+            justempty_syms[sym] = true
+            changed = true
+          end
+        }
+      end
+      result = {}
+      syntax.each {|sym, rules|
+        result[sym] = rules.map {|rhs| rhs.reject {|e| justempty_syms[e] } }.uniq
+      }
+      result
+    end
+
+    def self.expand_emptyable_syms(rhs, emptyable_syms)
+      if rhs.empty?
+      elsif rhs.length == 1
+        if emptyable_syms[rhs[0]]
+          yield rhs
+          yield []
+        else
+          yield rhs
+        end
+      else
+        butfirst = rhs[1..-1]
+        if emptyable_syms[rhs[0]]
+          expand_emptyable_syms(butfirst, emptyable_syms) {|rhs2| 
+            yield [rhs[0]] + rhs2
+            yield rhs2
+          }
+        else
+          expand_emptyable_syms(butfirst, emptyable_syms) {|rhs2|
+            yield [rhs[0]] + rhs2
+          }
+        end
+      end
+    end
+
+    def self.remove_emptyable_rules(syntax)
+      emptyable_syms = {}
+      changed = true
+      while changed
+        changed = false
+        syntax.each {|sym, rules|
+          next if emptyable_syms[sym]
+          rules.each {|rhs|
+            if rhs.all? {|e| emptyable_syms[e] }
+              emptyable_syms[sym] = true
+              changed = true
+              break
+            end
+          }
+        }
+      end
+      result = {}
+      syntax.each {|sym, rules|
+        rules2 = []
+        rules.each {|rhs|
+          expand_emptyable_syms(rhs, emptyable_syms) {|rhs2|
+            rules2 << rhs2
+          }
+        }
+        result[sym] = rules2.uniq
+      }
+      result
+    end
+
+    def self.expand_channel_rules(syntax)
+      channel_rules = {}
+      syntax.each {|sym, rules|
+        channel_rules[sym] = {sym=>true}
+        rules.each {|rhs|
+          if rhs.length == 1 && Symbol === rhs[0]
+            channel_rules[sym][rhs[0]] = true
+          end
+        }
+      }
+      changed = true
+      while changed
+        changed = false 
+        channel_rules.each {|sym, set|
+          n1 = set.size
+          set.keys.each {|s|
+            set.update(channel_rules[s])
+          }
+          n2 = set.size
+          changed = true if n1 < n2
+        }
+      end
+      result = {}
+      syntax.each {|sym, rules|
+        rules2 = []
+        channel_rules[sym].each_key {|s|
+          syntax[s].each {|rhs|
+            unless rhs.length == 1 && Symbol === rhs[0]
+              rules2 << rhs
+            end
+          }
+        }
+        result[sym] = rules2.uniq
+      }
+      result
+    end
+
+    def self.expand_noalt_rules(syntax)
+      noalt_syms = {}
+      syntax.each {|sym, rules|
+        if rules.length == 1
+          noalt_syms[sym] = true
+        end
+      }
+      result = {}
+      syntax.each {|sym, rules|
+        rules2 = []
+        rules.each {|rhs|
+          rhs2 = []
+          rhs.each {|e|
+            if noalt_syms[e]
+              rhs2.concat syntax[e][0]
+            else
+              rhs2 << e
+            end
+          }
+          rules2 << rhs2
+        }
+        result[sym] = rules2.uniq
+      }
+      result
+    end
+
+    def self.reorder_rules(syntax)
+      result = {}
+      syntax.each {|sym, rules|
+        result[sym] = rules.sort_by {|rhs|
+          [rhs.find_all {|e| Symbol === e }.length, rhs.length]
+        }
+      }
+      result
+    end
+
+    def each_tree(sym, limit)
+      generate_from_sym(sym, limit) {|_, tree|
+        yield tree
+      }
+      nil
+    end
+
+    def each_string(sym, limit)
+      generate_from_sym(sym, limit) {|_, tree|
+        yield [tree].join('')
+      }
+      nil
+    end
+
+    def generate_from_sym(sym, limit, &b)
+      return if limit < 0
+      if String === sym
+        yield limit, sym
+      else
+        rules = @syntax[sym]
+        raise "undefined rule: #{sym}" if !rules
+        rules.each {|rhs|
+          if rhs.length == 1 || rules.length == 1
+            limit1 = limit
+          else
+            limit1 = limit-1
+          end
+          generate_from_rhs(rhs, limit1, &b)
+        }
+      end
+      nil
+    end
+
+    def generate_from_rhs(rhs, limit)
+      return if limit < 0
+      if rhs.empty?
+        yield limit, []
+      else
+        generate_from_sym(rhs[0], limit) {|limit1, child|
+          generate_from_rhs(rhs[1..-1], limit1) {|limit2, arr|
+            yield limit2, [child, *arr]
+          }
+        }
+      end
+      nil
+    end
+  end
+
+end
+
diff --git a/test/ruby/sentgen.rb b/test/ruby/sentgen.rb
deleted file mode 100644
index 49eae5c4ae..0000000000
--- a/test/ruby/sentgen.rb
+++ /dev/null
@@ -1,259 +0,0 @@
-# sentence generator
-
-class SentGen
-  def SentGen.each_tree(syntax, sym, limit, &b)
-    SentGen.new(syntax).each_tree(sym, limit, &b)
-  end
-
-  def SentGen.each_string(syntax, sym, limit, &b)
-    SentGen.new(syntax).each_string(sym, limit, &b)
-  end
-
-  def initialize(syntax)
-    @syntax = syntax
-  end
-
-  def self.expand_syntax(syntax)
-    syntax = remove_underivable_rules(syntax)
-    syntax = expand_justempty_rules(syntax)
-    syntax = remove_emptyable_rules(syntax)
-    syntax = expand_channel_rules(syntax)
-
-    syntax = expand_noalt_rules(syntax)
-    syntax = reorder_rules(syntax)
-  end
-
-  def self.remove_underivable_rules(syntax)
-    deribable_syms = {}
-    changed = true
-    while changed
-      changed = false
-      syntax.each {|sym, rules|
-        next if deribable_syms[sym]
-        rules.each {|rhs|
-          if rhs.all? {|e| String === e || deribable_syms[e] }
-            deribable_syms[sym] = true
-            changed = true
-            break
-          end
-        }
-      }
-    end
-    result = {}
-    syntax.each {|sym, rules|
-      next if !deribable_syms[sym]
-      rules2 = []
-      rules.each {|rhs|
-        rules2 << rhs if rhs.all? {|e| String === e || deribable_syms[e] }
-      }
-      result[sym] = rules2.uniq
-    }
-    result
-  end
-
-  def self.expand_justempty_rules(syntax)
-    justempty_syms = {}
-    changed = true
-    while changed
-      changed = false
-      syntax.each {|sym, rules|
-        next if justempty_syms[sym]
-        if rules.all? {|rhs| rhs.all? {|e| justempty_syms[e] } }
-          justempty_syms[sym] = true
-          changed = true
-        end
-      }
-    end
-    result = {}
-    syntax.each {|sym, rules|
-      result[sym] = rules.map {|rhs| rhs.reject {|e| justempty_syms[e] } }.uniq
-    }
-    result
-  end
-
-  def self.expand_emptyable_syms(rhs, emptyable_syms)
-    if rhs.empty?
-    elsif rhs.length == 1
-      if emptyable_syms[rhs[0]]
-        yield rhs
-        yield []
-      else
-        yield rhs
-      end
-    else
-      butfirst = rhs[1..-1]
-      if emptyable_syms[rhs[0]]
-        expand_emptyable_syms(butfirst, emptyable_syms) {|rhs2| 
-          yield [rhs[0]] + rhs2
-          yield rhs2
-        }
-      else
-        expand_emptyable_syms(butfirst, emptyable_syms) {|rhs2|
-          yield [rhs[0]] + rhs2
-        }
-      end
-    end
-  end
-
-  def self.remove_emptyable_rules(syntax)
-    emptyable_syms = {}
-    changed = true
-    while changed
-      changed = false
-      syntax.each {|sym, rules|
-        next if emptyable_syms[sym]
-        rules.each {|rhs|
-          if rhs.all? {|e| emptyable_syms[e] }
-            emptyable_syms[sym] = true
-            changed = true
-            break
-          end
-        }
-      }
-    end
-    result = {}
-    syntax.each {|sym, rules|
-      rules2 = []
-      rules.each {|rhs|
-        expand_emptyable_syms(rhs, emptyable_syms) {|rhs2|
-          rules2 << rhs2
-        }
-      }
-      result[sym] = rules2.uniq
-    }
-    result
-  end
-
-  def self.expand_channel_rules(syntax)
-    channel_rules = {}
-    syntax.each {|sym, rules|
-      channel_rules[sym] = {sym=>true}
-      rules.each {|rhs|
-        if rhs.length == 1 && Symbol === rhs[0]
-          channel_rules[sym][rhs[0]] = true
-        end
-      }
-    }
-    changed = true
-    while changed
-      changed = false 
-      channel_rules.each {|sym, set|
-        n1 = set.size
-        set.keys.each {|s|
-          set.update(channel_rules[s])
-        }
-        n2 = set.size
-        changed = true if n1 < n2
-      }
-    end
-    result = {}
-    syntax.each {|sym, rules|
-      rules2 = []
-      channel_rules[sym].each_key {|s|
-        syntax[s].each {|rhs|
-          unless rhs.length == 1 && Symbol === rhs[0]
-            rules2 << rhs
-          end
-        }
-      }
-      result[sym] = rules2.uniq
-    }
-    result
-  end
-
-  def self.expand_noalt_rules(syntax)
-    noalt_syms = {}
-    syntax.each {|sym, rules|
-      if rules.length == 1
-        noalt_syms[sym] = true
-      end
-    }
-    result = {}
-    syntax.each {|sym, rules|
-      rules2 = []
-      rules.each {|rhs|
-        rhs2 = []
-        rhs.each {|e|
-          if noalt_syms[e]
-            rhs2.concat syntax[e][0]
-          else
-            rhs2 << e
-          end
-        }
-        rules2 << rhs2
-      }
-      result[sym] = rules2.uniq
-    }
-    result
-  end
-
-  def self.reorder_rules(syntax)
-    result = {}
-    syntax.each {|sym, rules|
-      result[sym] = rules.sort_by {|rhs|
-        [rhs.find_all {|e| Symbol === e }.length, rhs.length]
-      }
-    }
-    result
-  end
-
-  def each_tree(sym, limit)
-    generate_from_sym(sym, limit) {|_, tree|
-      yield tree
-    }
-    nil
-  end
-
-  def each_string(sym, limit)
-    generate_from_sym(sym, limit) {|_, tree|
-      yield [tree].join('')
-    }
-    nil
-  end
-
-  def generate_from_sym(sym, limit, &b)
-    return if limit < 0
-    if String === sym
-      yield limit, sym
-    else
-      rules = @syntax[sym]
-      raise "undefined rule: #{sym}" if !rules
-      rules.each {|rhs|
-        if rhs.length == 1 || rules.length == 1
-          limit1 = limit
-        else
-          limit1 = limit-1
-        end
-        generate_from_rhs(rhs, limit1, &b)
-      }
-    end
-    nil
-  end
-
-  def generate_from_rhs(rhs, limit)
-    return if limit < 0
-    if rhs.empty?
-      yield limit, []
-    else
-      generate_from_sym(rhs[0], limit) {|limit1, child|
-        generate_from_rhs(rhs[1..-1], limit1) {|limit2, arr|
-          yield limit2, [child, *arr]
-        }
-      }
-    end
-    nil
-  end
-
-  def SentGen.subst(obj, target, &b)
-    if obj.respond_to? :to_ary
-      a = []
-      obj.each {|e| a << subst(e, target, &b) }
-      a
-    elsif target === obj
-      yield obj
-    else
-      obj
-    end
-  end
-end
-
diff --git a/test/ruby/test_assignment.rb b/test/ruby/test_assignment.rb
index 055a6e8132..e7d27fbc4b 100644
--- a/test/ruby/test_assignment.rb
+++ b/test/ruby/test_assignment.rb
@@ -490,7 +490,7 @@ class TestAssignment < Test::Unit::TestCase
   end
 end
 
-require 'sentgen'
+require 'sentence'
 class TestAssignmentGen < Test::Unit::TestCase
   Syntax = {
     :exp => [["0"],
@@ -537,7 +537,7 @@ class TestAssignmentGen < Test::Unit::TestCase
 
   def rename_var(obj)
     vars = []
-    r = SentGen.subst(obj, 'var') {
+    r = obj.subst('var') {
       var = "v#{vars.length}"
       vars << var
       var
@@ -646,7 +646,7 @@ class TestAssignmentGen < Test::Unit::TestCase
   end
 
   def do_assign(assign, vars)
-    assign = assign.join('')
+    assign = assign.to_s
     code = "#{assign}; [#{vars.join(",")}]"
     begin
       vals = eval(code)
@@ -659,12 +659,12 @@ class TestAssignmentGen < Test::Unit::TestCase
   end
 
   def test_assignment
-    syntax = SentGen.expand_syntax(Syntax)
-    SentGen.each_tree(syntax, :xassign, 3) {|assign|
-      assign[0], vars = rename_var(assign[0])
-      sent = [assign].join('')
+    syntax = Sentence::Gen.expand_syntax(Syntax)
+    Sentence.each(syntax, :xassign, 3) {|assign|
+      assign, vars = rename_var(assign)
+      sent = assign.to_s
       bruby = do_assign(assign, vars).to_a.sort
-      bemu = emu_assign(assign).to_a.sort
+      bemu = emu_assign(assign.to_a).to_a.sort
       assert_equal(bemu, bruby, sent)
     }
   end
diff --git a/test/ruby/test_yield.rb b/test/ruby/test_yield.rb
index 6e1d39353d..b49e3978c5 100644
--- a/test/ruby/test_yield.rb
+++ b/test/ruby/test_yield.rb
@@ -66,7 +66,7 @@ class TestRubyYield < Test::Unit::TestCase
 
 end
 
-require 'sentgen'
+require 'sentence'
 class TestRubyYieldGen < Test::Unit::TestCase
   Syntax = {
     :exp => [["0"],
@@ -154,12 +154,12 @@ class TestRubyYieldGen < Test::Unit::TestCase
                        []],
     :block_arg => [['&', :arg]],
     #:test => [['def m() yield', :command_args_noblock, ' end; r = m {', :block_param_def, 'vars', '}; undef m; r']]
-    :test => [['def m(&b) b.yield', :command_args_noblock, ' end; r = m {', :block_param_def, 'vars', '}; undef m; r']]
+    :test => [['def m() yield', :command_args_noblock, ' end; r = m {', :block_param_def, 'vars', '}; undef m; r']]
   }
 
   def rename_var(obj)
     vars = []
-    r = SentGen.subst(obj, 'var') {
+    r = obj.subst('var') {
       var = "v#{vars.length}"
       vars << var
       var
@@ -167,20 +167,134 @@ class TestRubyYieldGen < Test::Unit::TestCase
     return r, vars
   end
 
+  def split_by_comma(ary)
+    return [] if ary.empty?
+    result = [[]]
+    ary.each {|e|
+      if e == ','
+        result << []
+      else
+        result.last << e
+      end
+    }
+    result
+  end
+
+  def emu_return_args(*vs)
+    vs
+  end
+
+  def emu_eval_args(args)
+    if args.last == []
+      args = args[0...-1]
+    end
+    code = "emu_return_args #{args.map {|a| a.join('') }.join(",")}"
+    eval code
+  end
+
+  def emu_bind_single(arg, param, result_binding)
+    #p [:emu_bind_single, arg, param]
+    if param.length == 1 && String === param[0] && /\A[a-z0-9]+\z/ =~ param[0]
+      result_binding[param[0]] = arg
+    elsif param.length == 1 && Array === param[0] && param[0][0] == '(' && param[0][-1] == ')'
+      arg = [arg] unless Array === arg
+      emu_bind_params(arg, split_by_comma(param[0][1...-1]), result_binding)
+    else
+      raise "unexpected param: #{param.inspect}"
+    end
+    result_binding
+  end
+
+  def emu_bind_params(args, params, result_binding={})
+    #p [:emu_bind_params, args, params]
+    if params.last == [] # extra comma
+      params.pop
+    end
+
+    if params.last && params.last[0] == '&'
+      result_binding[params.last[1]] = nil
+      params.pop
+    end
+
+    star_index = nil
+    params.each_with_index {|par, i|
+      star_index = i if par[0] == '*'
+    }
+
+    # TRICK #2 : adjust mismatch on number of arguments
+    if star_index
+      pre_params = params[0...star_index]
+      rest_param = params[star_index]
+      post_params = params[(star_index+1)..-1]
+      pre_params.each {|par| emu_bind_single(args.shift, par, result_binding) }
+      if post_params.length <= args.length
+        post_params.reverse_each {|par| emu_bind_single(args.pop, par, result_binding) }
+      else
+        post_params.each {|par| emu_bind_single(args.shift, par, result_binding) }
+      end
+      if rest_param != ['*']
+        emu_bind_single(args, rest_param[1..-1], result_binding)
+      end
+    else
+      params.each_with_index {|par, i|
+        emu_bind_single(args[i], par, result_binding)
+      }
+    end
+
+    #p [args, params, result_binding]
+
+    result_binding
+  end
+
+  def emu(t)
+    #puts
+    #p t
+    command_args_noblock = t[1]
+    block_param_def = t[3]
+    command_args_noblock = command_args_noblock.expand {|a| !(a[0] == '[' && a[-1] == ']') }
+    block_param_def = block_param_def.expand {|a| !(a[0] == '(' && a[-1] == ')') }
+
+    if command_args_noblock.to_a[0] == ' '
+      args = command_args_noblock.to_a[1..-1]
+    elsif command_args_noblock.to_a[0] == '(' && command_args_noblock.to_a[-1] == ')'
+      args = command_args_noblock.to_a[1...-1]
+    else
+      raise "unexpected command_args_noblock: #{command_args_noblock.inspect}"
+    end
+    args = emu_eval_args(split_by_comma(args))
+
+    params = block_param_def.to_a[1...-1]
+    params = split_by_comma(params)
+
+    #p [:emu0, args, params]
+
+    # TRICK #1 : single array argument is expanded if there are two or more params.
+    if args.length == 1 && Array === args[0] && 1 < params.length
+      args = args[0]
+    end
+
+    result_binding = emu_bind_params(args, params)
+    #p result_binding
+    result_binding
+  end
+
   def check_nofork(t)
     t, vars = rename_var(t)
-    t = SentGen.subst(t, 'vars') { " [#{vars.join(",")}]" }
-    s = [t].join
+    t = t.subst('vars') { " [#{vars.join(",")}]" }
+    emu_binding = emu(t)
+    emu_values = vars.map {|var| emu_binding.fetch(var, "NOVAL") }
+    s = t.to_s
     #print "#{s}\t\t"
     #STDOUT.flush
-    v = eval(s)
-    #puts "#{v.inspect[1...-1]}"
-    ##xxx: assertion for v here.
+    eval_values = eval(s)
+    #success = emu_values == eval_values ? 'succ' : 'fail'
+    #puts "eval:#{vs_ev.inspect[1...-1].delete(' ')}\temu:#{vs_emu.inspect[1...-1].delete(' ')}\t#{success}"
+    assert_equal(emu_values, eval_values, s)
   end
 
   def test_yield
-    syntax = SentGen.expand_syntax(Syntax)
-    SentGen.each_tree(syntax, :test, 4) {|t|
+    syntax = Sentence::Gen.expand_syntax(Syntax)
+    Sentence.each(syntax, :test, 4) {|t|
       check_nofork(t)
     }
   end