module PatternMatching
  class NotMatched < Exception
  end
  
  class NodeBuilder
    def method_missing(name, *args)
      Node.new(name, args)
    end
  end
  
  class Node
    def initialize(name, children)
      @name = name
      @children = children
    end
    attr :name
    def [](index)
      @children[index]
    end
    def size
      @children.size
    end
  end
  
  class Collector
    def self.walk(source, target, list)
      case source
      when Symbol
        list[source] = target
      when Node
        walk_node(source, target, list)
      when Hash
        walk_hash(source, target, list)
      when Enumerable
        walk_enumerable(source, target, list)
      else
        raise NotMatched.new unless source === target
      end
    end
    
    def self.walk_node(source, target, list)
      return if source.name == :_ and source.size == 0
      begin
        if source.size != target.size
          raise NotMatched.new 
        end
        if source.name != :_ and source.name != target.name
          raise NotMatched.new
        end
      rescue
        raise NotMatched.new
      end
      source.size.times do |i|
        walk(source[i], target[i], list)
      end
    end
    
    def self.walk_enumerable(source, target, list)
      if source.size == 0 and not (target == nil or target.size == 0)
        raise NotMatched.new 
      end
      source.size.times do |i|
        svalue = source[i]
        if i + 1 == source.size 
          if  svalue.class == Node and svalue.name == :_! and 
              svalue.size == 1
            tvalue = target[i .. -1]
            tvalue = if tvalue == nil then [] else tvalue end
            walk(svalue[0], tvalue, list)
          else
            raise NotMatched.new if source.size != target.size
            walk(svalue, target[i], list)
          end
        else
          raise NotMatched.new if target.size <= i
          walk(svalue, target[i], list)
        end
      end
    end
    
    def self.walk_hash(source, target, list)
      begin
        case target
        when Node
          raise NotMatched.new
        when Hash
          source.each do |key, svalue|
            walk(svalue, target[key], list)
          end
        else
          source.each do |key, svalue|
            walk(svalue, target.send(key), list)
          end
        end
      rescue
        raise NotMatched.new
      end
    end
  end
  
  class MatchExec
    def self.exec_as(target, patterns, receiver)
      patterns.each do |pair|
        pattern = pair.keys[0]
        action = pair[pattern]
        source = NodeBuilder.new.instance_eval(&pattern)
        args = {}
        begin
          Collector.walk(source, target, args)
        rescue NotMatched
          next
        end
        return ExecuteAs.new(args, receiver).call(&action)
      end      
    end
    
    class ExecuteAs
      def initialize(args, receiver)
        @this = receiver
        @args = args
      end
      def call(&action)
        args = @args
        mod = Module.new
        mod.instance_eval do
          define_method(:method_missing) do |name, *margs|
            return args[name] if args.key?(name)
            super(name, *margs)
          end
        end
        # this block is not thread safe
        @this.extend mod
        result = @this.instance_eval(&action)
        mod.instance_eval do
          remove_method(:method_missing)
        end
        # 
        result
      end
    end
  end
  
  class PatternFragments
    def initialize(patterns)
      @patterns = patterns
    end
    def seems(pattern, &action)
      @patterns << {pattern => action}
      self
    end
    def as(&block)
      block
    end
    def something
      proc {_}
    end
  end
  
  # DSL element
  def build(&block)
    NodeBuilder.new.instance_eval(&block)
  end
  def self.build(&block)
    NodeBuilder.new.instance_eval(&block)
  end
  def make(target, &block)
    patterns = []
    PatternFragments.new(patterns).instance_eval(&block)
    MatchExec.exec_as(target, patterns, self)
  end
  def as(&block)
    block
  end
  def something
    proc {_}
  end
  def func(name, &block)
    pattern_name = ("@_pattern_" + name.to_s ).to_sym
    unless method_defined?(name)
      patterns = []
      instance_variable_set(pattern_name, patterns)
      define_method(name) do |target|
        MatchExec.exec_as(target, patterns, self)
      end
    end
    patterns = instance_variable_get(pattern_name)
    fragments = PatternFragments.new(patterns)
    if block
      fragments.instance_eval(&block)
    end
    fragments
  end
end

=begin
# If installed from rubygems
require "rubygems"
gem "patternmatching"

# for use 
require "patternmatching"


# partial func example
class Calc
  extend PatternMatching
  
  func(:calcm).seems as {plus(:a, :b)} do
    calcm(a) + calcm(b)
  end
  func(:calcm).seems as {mul(:a, :b)} do
    calcm(a) * calcm(b)
  end
  func(:calcm).seems as {:value} do
    value
  end
end

val = 200
code = PatternMatching.build {plus(mul(100, 100), val)}
p Calc.new.calcm(code)

# another partial func example
class CalcX
  extend PatternMatching
  
  func(:calcx) do
    seems as {plus(:a, :b)} do
      calcx(a) + calcx(b)
    end
    seems as {mul(:a, :b)} do
      calcx(a) * calcx(b)
    end
  end
  func(:calcx).seems as {:value} do
    value
  end
end

p CalcX.new.calcx(code)

# pattern example
include PatternMatching

def calc(code)
  make(code) {
    seems as {plus(:a, :b)} do calc(a) + calc(b) end
    seems as {mul(:a, :b)} do  calc(a) * calc(b) end
    seems something do code end
  }
end

p calc(code)


# enumerable match example
is = build { exact([1,2,3,4,5]) }
make is do
  seems as {exact([:a,:b, _!(:c)])} do
    puts a.to_s + ", " + b.to_s  + " and " + c.to_s 
  end
  seems something do
    puts "not matched"
  end
end

# hash to hash match example
dict = build { {:name => "Taro", :age => 5} }
make dict do
  seems as {{:name => :name}} do
    puts "He is " + name
  end
  seems something do
    puts "no name"
  end
end

# hash to obj match example
class Person
  def initialize(name, age)
    @name = name
    @age = age
  end
  attr :name
  attr :age
end

make Person.new("Jiro", 3) do
  seems as {{:name => :name}} do
    puts "He is " + name
  end
  seems something do
    puts "no name"
  end
end
=end