require 'pp'

# Make sure Rockit module exists if we are loaded separetely from rest
# of Rockit
module Rockit; end 

# Rockit::Tree defines a superclass for syntax trees. The trees has methods
# for easily creating and pattern matching trees.
module Rockit::Tree
  class Base
    include Enumerable
    
    def self.new_tree_class(name, children_names = [])
      name_as_str = name.to_s
      unless name_as_str =~ /^[A-Z]/
	raise NameError, "identifier #{name} needs to be constant"
      end
      unless constants.include?(name_as_str)
	s = <<-EOC
        class #{name_as_str} < #{self.inspect}
	    #{child_accessor_codes(children_names)}
	end
	EOC
	class_eval s
      end
      class_eval "#{name_as_str}"
    end

    def self.child_accessor_codes(children_names)
      i, s = 0, ""
      while i < children_names.length
	s += child_accessor_code(children_names[i], i)
	i += 1
      end
      s
    end

    def self.child_accessor_code(children_name, index)
      name = children_name.to_s
      s = <<-EOC
        def #{name}
          @children[#{index}]
        end
	def #{name}=(newValue)
	  @children[#{index}] = newValue
        end
      EOC
    end

    def self.[](*children)
      new(*children)
    end

    attr_reader :children

    def initialize(*children)
      @children = children
    end

    def [](index)
      self.children[index]
    end

    def num_children
      self.children.length
    end

    def ==(other)
      self.class == other.class && self.children == other.children
    end

    def inspect
      class_name + "[" +
        self.children.map {|c| c.inspect}.join(", ") + 
        "]"
    end

    def class_name
      self.class.inspect.split("::").last
    end

    def each_child
      children.each {|c| yield(c)}
    end

    alias each each_child

    # Depth-first traversal of (sub)trees in tree
    def each_tree(&block)
      block.call(self)
      self.children.each do |c|
	if Base === c
	  c.each_tree(&block)
	else
	  block.call(c)
	end
      end
    end

    # Assuming klass is a subclass of Base
    def each_tree_of_class(klass, recursive = false, &block)
      cs = self.children
      if self.kind_of?(klass)
	block.call(self)
	cs = [] unless recursive
      end
      cs.each do |c|
	if Base === c
	  c.each_tree_of_class(klass, recursive, &block)
	elsif Array === c
	  c.each {|ac| 
	    ac.each_tree_of_class(klass, recursive, &block) if Base === ac
	  }
	end
      end
    end

    def match_tree(tree, matches = Hash.new)
      if self.class == tree.class && 
	  self.num_children == tree.num_children
        self.each_with_index do |child, i|
	  unless child.match_tree(tree[i], matches)
	    matches = nil
	    break
	  end
        end
	matches
      else
        nil
      end
    end

    def =~(patternTree)
      pattern = patternTree.upcase_symbols_to_pattern_vars
      pattern.match_tree(self)
    end

    def select_trees_of_class(klass, recursive = false)
      ary = []
      each_tree_of_class(klass, recursive) {|t| ary << t}
      ary
    end

    # Return all subtrees in tree which match the pattern self.
    def all_matching_trees(tree)
      # Only the subtrees with a root node of the right type are candidates
      candidates = tree.select_trees_of_class(self.class, true)
      pattern = self.upcase_symbols_to_pattern_vars
      candidates.map do |t| 
	res = pattern.match_tree(t)
	res ? [res, t] : nil
      end.compact
    end
  
    # Representing a variable in a patternTree
    class PatternVar
      attr_reader :name

      def initialize(name)
	@name = name
      end

      # A variable match anything and the binding is noted in the matches
      # hash.
      def match_tree(tree, matches = Hash.new)
	matches[@name] = tree
	matches
      end

      def inspect
	"Var_" + @name.to_s
      end

      # No need to def upcase_symbols_to_pattern_vars here since it
      # inherits the one defined for Object below
    end

    # Convert upper case symbols to pattern variables 
    def upcase_symbols_to_pattern_vars    
      new_children = Array.new
      self.each {|child| new_children << child.upcase_symbols_to_pattern_vars}
      self.class.new(*new_children)
    end

    def pretty_print(pp)
      pp.text class_name
      pp.group(1, '[', ']') do 
	pp.breakable ""
	pp.seplist(self.children) {|c| pp.pp c}
      end
    end

    # The nodes in a tree are not linked upwards by default but by calling
    # the set_parents method on the root the parent attribute on each subtree
    # is set and can then be accessed.
    attr_accessor :parent

    def set_parents(parent = nil)
      self.parent = parent
      each_child {|c| c.set_parents(self) if c.kind_of?(Base)}
    end
  end
end

class Object
  def match_tree(tree, matches = Hash.new)
    self == tree
  end
  
  def upcase_symbols_to_pattern_vars
    self
  end
end

class Symbol
  def upcase_symbols_to_pattern_vars
    if self.to_s =~ /^[A-Z]/
      Rockit::Tree::Base::PatternVar.new(self)
    else
      self
    end
  end
end