class REXML::XPathParser

def expr( path_stack, nodeset, context=nil )
  enter(:expr, path_stack, nodeset) if @debug
  return nodeset if path_stack.length == 0 || nodeset.length == 0
  while path_stack.length > 0
    trace(:while, path_stack, nodeset) if @debug
    if nodeset.length == 0
      path_stack.clear
      return []
    end
    op = path_stack.shift
    case op
    when :document
      first_raw_node = nodeset.first.raw_node
      nodeset = [XPathNode.new(first_raw_node.root_node, position: 1)]
    when :self
      nodeset = step(path_stack) do
        [nodeset]
      end
    when :child
      nodeset = step(path_stack) do
        child(nodeset)
      end
    when :literal
      trace(:literal, path_stack, nodeset) if @debug
      return path_stack.shift
    when :attribute
      nodeset = step(path_stack, any_type: :attribute) do
        nodesets = []
        nodeset.each do |node|
          raw_node = node.raw_node
          next unless raw_node.node_type == :element
          attributes = raw_node.attributes
          next if attributes.empty?
          nodesets << attributes.each_attribute.collect.with_index do |attribute, i|
            XPathNode.new(attribute, position: i + 1)
          end
        end
        nodesets
      end
    when :namespace
      pre_defined_namespaces = {
        "xml" => "http://www.w3.org/XML/1998/namespace",
      }
      nodeset = step(path_stack, any_type: :namespace) do
        nodesets = []
        nodeset.each do |node|
          raw_node = node.raw_node
          case raw_node.node_type
          when :element
            if @namespaces
              nodesets << pre_defined_namespaces.merge(@namespaces)
            else
              nodesets << pre_defined_namespaces.merge(raw_node.namespaces)
            end
          when :attribute
            if @namespaces
              nodesets << pre_defined_namespaces.merge(@namespaces)
            else
              nodesets << pre_defined_namespaces.merge(raw_node.element.namespaces)
            end
          end
        end
        nodesets
      end
    when :parent
      nodeset = step(path_stack) do
        nodesets = []
        nodeset.each do |node|
          raw_node = node.raw_node
          if raw_node.node_type == :attribute
            parent = raw_node.element
          else
            parent = raw_node.parent
          end
          nodesets << [XPathNode.new(parent, position: 1)] if parent
        end
        nodesets
      end
    when :ancestor
      nodeset = step(path_stack) do
        nodesets = []
        # new_nodes = {}
        nodeset.each do |node|
          raw_node = node.raw_node
          new_nodeset = []
          while raw_node.parent
            raw_node = raw_node.parent
            # next if new_nodes.key?(node)
            new_nodeset << XPathNode.new(raw_node,
                                         position: new_nodeset.size + 1)
            # new_nodes[node] = true
          end
          nodesets << new_nodeset unless new_nodeset.empty?
        end
        nodesets
      end
    when :ancestor_or_self
      nodeset = step(path_stack) do
        nodesets = []
        # new_nodes = {}
        nodeset.each do |node|
          raw_node = node.raw_node
          next unless raw_node.node_type == :element
          new_nodeset = [XPathNode.new(raw_node, position: 1)]
          # new_nodes[node] = true
          while raw_node.parent
            raw_node = raw_node.parent
            # next if new_nodes.key?(node)
            new_nodeset << XPathNode.new(raw_node,
                                         position: new_nodeset.size + 1)
            # new_nodes[node] = true
          end
          nodesets << new_nodeset unless new_nodeset.empty?
        end
        nodesets
      end
    when :descendant_or_self
      nodeset = step(path_stack) do
        descendant(nodeset, true)
      end
    when :descendant
      nodeset = step(path_stack) do
        descendant(nodeset, false)
      end
    when :following_sibling
      nodeset = step(path_stack) do
        nodesets = []
        nodeset.each do |node|
          raw_node = node.raw_node
          next unless raw_node.respond_to?(:parent)
          next if raw_node.parent.nil?
          all_siblings = raw_node.parent.children
          current_index = all_siblings.index(raw_node)
          following_siblings = all_siblings[(current_index + 1)..-1]
          next if following_siblings.empty?
          nodesets << following_siblings.collect.with_index do |sibling, i|
            XPathNode.new(sibling, position: i + 1)
          end
        end
        nodesets
      end
    when :preceding_sibling
      nodeset = step(path_stack, order: :reverse) do
        nodesets = []
        nodeset.each do |node|
          raw_node = node.raw_node
          next unless raw_node.respond_to?(:parent)
          next if raw_node.parent.nil?
          all_siblings = raw_node.parent.children
          current_index = all_siblings.index(raw_node)
          preceding_siblings = all_siblings[0, current_index].reverse
          next if preceding_siblings.empty?
          nodesets << preceding_siblings.collect.with_index do |sibling, i|
            XPathNode.new(sibling, position: i + 1)
          end
        end
        nodesets
      end
    when :preceding
      nodeset = step(path_stack, order: :reverse) do
        unnode(nodeset) do |node|
          preceding(node)
        end
      end
    when :following
      nodeset = step(path_stack) do
        unnode(nodeset) do |node|
          following(node)
        end
      end
    when :variable
      var_name = path_stack.shift
      return [@variables[var_name]]
    when :eq, :neq, :lt, :lteq, :gt, :gteq
      left = expr( path_stack.shift, nodeset.dup, context )
      right = expr( path_stack.shift, nodeset.dup, context )
      res = equality_relational_compare( left, op, right )
      trace(op, left, right, res) if @debug
      return res
    when :or
      left = expr(path_stack.shift, nodeset.dup, context)
      return true if Functions.boolean(left)
      right = expr(path_stack.shift, nodeset.dup, context)
      return Functions.boolean(right)
    when :and
      left = expr(path_stack.shift, nodeset.dup, context)
      return false unless Functions.boolean(left)
      right = expr(path_stack.shift, nodeset.dup, context)
      return Functions.boolean(right)
    when :div, :mod, :mult, :plus, :minus
      left = expr(path_stack.shift, nodeset, context)
      right = expr(path_stack.shift, nodeset, context)
      left = unnode(left) if left.is_a?(Array)
      right = unnode(right) if right.is_a?(Array)
      left = Functions::number(left)
      right = Functions::number(right)
      case op
      when :div
        return left / right
      when :mod
        return left % right
      when :mult
        return left * right
      when :plus
        return left + right
      when :minus
        return left - right
      else
        raise "[BUG] Unexpected operator: <#{op.inspect}>"
      end
    when :union
      left = expr( path_stack.shift, nodeset, context )
      right = expr( path_stack.shift, nodeset, context )
      left = unnode(left) if left.is_a?(Array)
      right = unnode(right) if right.is_a?(Array)
      return (left | right)
    when :neg
      res = expr( path_stack, nodeset, context )
      res = unnode(res) if res.is_a?(Array)
      return -Functions.number(res)
    when :not
    when :function
      func_name = path_stack.shift.tr('-','_')
      arguments = path_stack.shift
      if nodeset.size != 1
        message = "[BUG] Node set size must be 1 for function call: "
        message += "<#{func_name}>: <#{nodeset.inspect}>: "
        message += "<#{arguments.inspect}>"
        raise message
      end
      node = nodeset.first
      if context
        target_context = context
      else
        target_context = {:size => nodeset.size}
        if node.is_a?(XPathNode)
          target_context[:node]  = node.raw_node
          target_context[:index] = node.position
        else
          target_context[:node]  = node
          target_context[:index] = 1
        end
      end
      args = arguments.dclone.collect do |arg|
        result = expr(arg, nodeset, target_context)
        result = unnode(result) if result.is_a?(Array)
        result
      end
      Functions.context = target_context
      return Functions.send(func_name, *args)
    else
      raise "[BUG] Unexpected path: <#{op.inspect}>: <#{path_stack.inspect}>"
    end
  end # while
  return nodeset
ensure
  leave(:expr, path_stack, nodeset) if @debug
end