rexml: Fix XPath bug of //#{ELEMENT_NAME}[#{POSITION}]

The position should be counted for each nodeset but the previous
implementation counts position for union-ed nodeset.

For example, "/a/*/*[1]" should be matched to "<c1/>" and "<c2/>" with
the following XML.

    <a>
      <b>
        <c1/>
      </b>
      <b>
        <c2/>
      </b>
    </a>

But the previous implementation just returns only "<c1/>".

* lib/rexml/element.rb (REXML::Attributes#each_attribute):
  Support Enumerator for no block use.

* lib/rexml/element.rb (REXML::Attributes#each):
  Support Enumerator for no block use.

* lib/rexml/functions.rb (REXML::Functions.string):
  Support NaN again.

* lib/rexml/xpath_parser.rb: Re-implement "Step" evaluator.
  It should evaluate "AxisSpecifier", "NodeTest" and "Predicate" in one
  step to respect position for each nodeset.

* test/rexml/test_jaxen.rb: Enable more tests. Remained tests should
  be also enabled but it'll not be near future.

* test/rexml/xpath/test_base.rb: Fix expected value.


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

5 files changed, 505 insertions, 326 deletions

diff --git a/lib/rexml/element.rb b/lib/rexml/element.rb
index ac9b10872c..1ef22d29a2 100644
--- a/lib/rexml/element.rb
+++ b/lib/rexml/element.rb
@@ -1033,6 +1033,7 @@ module REXML
     #    p attr.expanded_name+" => "+attr.value
     #  }
     def each_attribute # :yields: attribute
+      return to_enum(__method__) unless block_given?
       each_value do |val|
         if val.kind_of? Attribute
           yield val
@@ -1048,6 +1049,7 @@ module REXML
     #  doc = Document.new '<a x="1" y="2"/>'
     #  doc.root.attributes.each {|name, value| p name+" => "+value }
     def each
+      return to_enum(__method__) unless block_given?
       each_attribute do |attr|
         yield [attr.expanded_name, attr.value]
       end
diff --git a/lib/rexml/functions.rb b/lib/rexml/functions.rb
index b0029660fa..452426703c 100644
--- a/lib/rexml/functions.rb
+++ b/lib/rexml/functions.rb
@@ -154,12 +154,16 @@ module REXML
         case object
         when Array
           string(object[0])
-        when Numeric
-          integer = object.to_i
-          if object == integer
-            "%d" % integer
+        when Float
+          if object.nan?
+            "NaN"
           else
-            object.to_s
+            integer = object.to_i
+            if object == integer
+              "%d" % integer
+            else
+              object.to_s
+            end
           end
         when nil
           ""
diff --git a/lib/rexml/xpath_parser.rb b/lib/rexml/xpath_parser.rb
index d217ae78e8..2d21f68416 100644
--- a/lib/rexml/xpath_parser.rb
+++ b/lib/rexml/xpath_parser.rb
@@ -76,7 +76,7 @@ module REXML
 
     def predicate path, nodeset
       path_stack = @parser.parse( path )
-      expr( path_stack, nodeset )
+      match( path_stack, nodeset )
     end
 
     def []=( variable_name, value )
@@ -124,9 +124,18 @@ module REXML
     end
 
 
-    def match( path_stack, nodeset )
-      r = expr( path_stack, nodeset )
-      r
+    def match(path_stack, nodeset)
+      nodeset = nodeset.collect.with_index do |node, i|
+        position = i + 1
+        XPathNode.new(node, position: position)
+      end
+      result = expr(path_stack, nodeset)
+      case result
+      when Array # nodeset
+        unnode(result)
+      else
+        result
+      end
     end
 
     private
@@ -149,11 +158,8 @@ module REXML
 
     # Expr takes a stack of path elements and a set of nodes (either a Parent
     # or an Array and returns an Array of matching nodes
-    ALL = [ :attribute, :element, :text, :processing_instruction, :comment ]
-    ELEMENTS = [ :element ]
     def expr( path_stack, nodeset, context=nil )
       # enter(:expr, path_stack, nodeset)
-      node_types = ELEMENTS
       return nodeset if path_stack.length == 0 || nodeset.length == 0
       while path_stack.length > 0
         # trace(:while, path_stack, nodeset)
@@ -161,251 +167,167 @@ module REXML
           path_stack.clear
           return []
         end
-        case (op = path_stack.shift)
+        op = path_stack.shift
+        case op
         when :document
-          nodeset = [ nodeset[0].root_node ]
-
-        when :qname
-          prefix = path_stack.shift
-          name = path_stack.shift
-          # enter(:qname, path_stack, prefix, name, nodeset)
-          nodeset.select! do |node|
-            if node.node_type == :element
-              if prefix.nil?
-                node.name == name
-              elsif prefix.empty?
-                node.name == name and node.namespace == ""
-              else
-                node.name == name and
-                  # FIXME: This DOUBLES the time XPath searches take
-                  node.namespace == get_namespace(node, prefix)
-              end
-            else
-              false
-            end
-          end
-          # leave(:qname, path_stack, nodeset)
-          node_types = ELEMENTS
-
-        when :any
-          nodeset.delete_if { |node| !node_types.include?(node.node_type) }
-
+          first_raw_node = nodeset.first.raw_node
+          nodeset = [XPathNode.new(first_raw_node.root_node, position: 1)]
         when :self
-          # This space left intentionally blank
-
-        when :processing_instruction
-          target = path_stack.shift
-          nodeset.delete_if do |node|
-            (node.node_type != :processing_instruction) or
-            ( target!='' and ( node.target != target ) )
+          nodeset = step(path_stack) do
+            [nodeset]
           end
-
-        when :text
-          nodeset.delete_if { |node| node.node_type != :text }
-
-        when :comment
-          nodeset.delete_if { |node| node.node_type != :comment }
-
-        when :node
-          # This space left intentionally blank
-          node_types = ALL
-
         when :child
-          new_nodeset = []
-          nt = nil
-          nodeset.each do |node|
-            nt = node.node_type
-            # trace(:child, nt, node)
-            case nt
-            when :element
-              new_nodeset.concat(node.children)
-            when :document
-              node.children.each do |child|
-                case child
-                when XMLDecl, Text
-                  # ignore
-                else
-                  new_nodeset << child
-                end
-              end
-            end
+          nodeset = step(path_stack) do
+            child(nodeset)
           end
-          nodeset = new_nodeset
-          node_types = ELEMENTS
-
         when :literal
           # trace(:literal, path_stack, nodeset)
           return path_stack.shift
-
         when :attribute
-          new_nodeset = []
-          case path_stack.shift
-          when :qname
-            prefix = path_stack.shift
-            name = path_stack.shift
-            for element in nodeset
-              if element.node_type == :element
-                attrib = element.attribute( name, get_namespace(element, prefix) )
-                new_nodeset << attrib if attrib
+          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
-          when :any
-            for element in nodeset
-              if element.node_type == :element
-                new_nodeset += element.attributes.to_a
+            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
-          nodeset = new_nodeset
-
         when :parent
-          new_nodeset = []
-          nodeset.each do |node|
-            if node.is_a?(Attribute)
-              parent = node.element
-            else
-              parent = node.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
-            new_nodeset << parent if parent
+            nodesets
           end
-          nodeset = new_nodeset
-          node_types = ELEMENTS
-
         when :ancestor
-          new_nodeset = []
-          nodeset.each do |node|
-            while node.parent
-              node = node.parent
-              new_nodeset << node unless new_nodeset.include? node
-            end
-          end
-          nodeset = new_nodeset
-          node_types = ELEMENTS
-
-        when :ancestor_or_self
-          new_nodeset = []
-          nodeset.each do |node|
-            if node.node_type == :element
-              new_nodeset << node
-              while ( node.parent )
-                node = node.parent
-                new_nodeset << node unless new_nodeset.include? node
+          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
-          nodeset = new_nodeset
-          node_types = ELEMENTS
-
-        when :predicate
-          new_nodeset = []
-          subcontext = { :size => nodeset.size }
-          pred = path_stack.shift
-          # enter(:predicate, pred, nodeset)
-          nodeset.each_with_index { |node, index|
-            subcontext[ :node ] = node
-            subcontext[ :index ] = index+1
-            pc = pred.dclone
-            result = expr( pc, [node], subcontext )
-            result = result[0] if result.kind_of? Array and result.length == 1
-            if result.kind_of? Numeric
-              new_nodeset << node if result == (index+1)
-            elsif result.instance_of? Array
-              if result.size > 0 and result.inject(false) {|k,s| s or k}
-                new_nodeset << node if result.size > 0
+        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
-            else
-              new_nodeset << node if result
+              nodesets << new_nodeset unless new_nodeset.empty?
             end
-          }
-          nodeset = new_nodeset
-          # leave(:predicate_return, nodeset)
-=begin
-          predicate = path_stack.shift
-          ns = nodeset.clone
-          result = expr( predicate, ns )
-          if result.kind_of? Array
-            nodeset = result.zip(ns).collect{|m,n| n if m}.compact
-          else
-            nodeset = result ? nodeset : []
+            nodesets
           end
-=end
-
         when :descendant_or_self
-          rv = descendant_or_self( path_stack, nodeset )
-          path_stack.clear
-          nodeset = rv
-          node_types = ELEMENTS
-
+          nodeset = step(path_stack) do
+            descendant(nodeset, true)
+          end
         when :descendant
-          results = []
-          nt = nil
-          nodeset.each do |node|
-            nt = node.node_type
-            results += expr( path_stack.dclone.unshift( :descendant_or_self ),
-              node.children ) if nt == :element or nt == :document
+          nodeset = step(path_stack) do
+            descendant(nodeset, false)
           end
-          nodeset = results
-          node_types = ELEMENTS
-
         when :following_sibling
-          results = []
-          nodeset.each do |node|
-            next if node.parent.nil?
-            all_siblings = node.parent.children
-            current_index = all_siblings.index( node )
-            following_siblings = all_siblings[ current_index+1 .. -1 ]
-            results += following_siblings
+          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
-          nodeset = results
-          node_types = ELEMENTS
-
         when :preceding_sibling
-          results = []
-          nodeset.each do |node|
-            next if node.parent.nil?
-            all_siblings = node.parent.children
-            current_index = all_siblings.index( node )
-            preceding_siblings = all_siblings[ 0, current_index ].reverse
-            results += preceding_siblings
+          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
-          nodeset = results
-          node_types = ELEMENTS
-
         when :preceding
-          new_nodeset = []
-          nodeset.each do |node|
-            new_nodeset += preceding( node )
+          nodeset = step(path_stack, order: :reverse) do
+            unnode(nodeset) do |node|
+              preceding(node)
+            end
           end
-          nodeset = new_nodeset
-          node_types = ELEMENTS
-
         when :following
-          new_nodeset = []
-          nodeset.each do |node|
-            new_nodeset += following( node )
-          end
-          nodeset = new_nodeset
-          node_types = ELEMENTS
-
-        when :namespace
-          new_nodeset = []
-          prefix = path_stack.shift
-          nodeset.each do |node|
-            if (node.node_type == :element or node.node_type == :attribute)
-              if @namespaces
-                namespaces = @namespaces
-              elsif (node.node_type == :element)
-                namespaces = node.namespaces
-              else
-                namespaces = node.element.namesapces
-              end
-              if (node.namespace == namespaces[prefix])
-                new_nodeset << node
-              end
+          nodeset = step(path_stack) do
+            unnode(nodeset) do |node|
+              following(node)
             end
           end
-          nodeset = new_nodeset
-
         when :variable
           var_name = path_stack.shift
           return [@variables[var_name]]
@@ -431,40 +353,37 @@ module REXML
           res = equality_relational_compare( left, op, right )
           return res
 
-        when :div
-          left = Functions::number(expr(path_stack.shift, nodeset, context)).to_f
-          right = Functions::number(expr(path_stack.shift, nodeset, context)).to_f
-          return (left / right)
-
-        when :mod
-          left = Functions::number(expr(path_stack.shift, nodeset, context )).to_f
-          right = Functions::number(expr(path_stack.shift, nodeset, context )).to_f
-          return (left % right)
-
-        when :mult
-          left = Functions::number(expr(path_stack.shift, nodeset, context )).to_f
-          right = Functions::number(expr(path_stack.shift, nodeset, context )).to_f
-          return (left * right)
-
-        when :plus
-          left = Functions::number(expr(path_stack.shift, nodeset, context )).to_f
-          right = Functions::number(expr(path_stack.shift, nodeset, context )).to_f
-          return (left + right)
-
-        when :minus
-          left = Functions::number(expr(path_stack.shift, nodeset, context )).to_f
-          right = Functions::number(expr(path_stack.shift, nodeset, context )).to_f
-          return (left - 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 )
-          return -(res.to_f)
-
+          res = unnode(res) if res.is_a?(Array)
+          return -Functions.number(res)
         when :not
         when :function
           func_name = path_stack.shift.tr('-','_')
@@ -473,21 +392,30 @@ module REXML
 
           res = []
           cont = context
-          nodeset.each_with_index { |n, i|
+          nodeset.each_with_index do |node, i|
             if subcontext
-              subcontext[:node]  = n
-              subcontext[:index] = i
+              if node.is_a?(XPathNode)
+                subcontext[:node]  = node.raw_node
+                subcontext[:index] = node.position
+              else
+                subcontext[:node]  = node
+                subcontext[:index] = i
+              end
               cont = subcontext
             end
             arg_clone = arguments.dclone
-            args = arg_clone.collect { |arg|
-              expr( arg, [n], cont )
-            }
+            args = arg_clone.collect do |arg|
+              result = expr( arg, [node], cont )
+              result = unnode(result) if result.is_a?(Array)
+              result
+            end
             Functions.context = cont
             res << Functions.send( func_name, *args )
-          }
+          end
           return res
 
+        else
+          raise "[BUG] Unexpected path: <#{op.inspect}>: <#{path_stack.inspect}>"
         end
       end # while
       return nodeset
@@ -495,6 +423,190 @@ module REXML
     #   leave(:expr, path_stack, nodeset)
     end
 
+    def step(path_stack, any_type: :element, order: :forward)
+      nodesets = yield
+      begin
+        # enter(:step, path_stack, nodesets)
+        nodesets = node_test(path_stack, nodesets, any_type: any_type)
+        while path_stack[0] == :predicate
+          path_stack.shift # :predicate
+          predicate_expression = path_stack.shift.dclone
+          nodesets = predicate(predicate_expression, nodesets)
+        end
+        if nodesets.size == 1
+          ordered_nodeset = nodesets[0]
+        else
+          raw_nodes = []
+          nodesets.each do |nodeset|
+            nodeset.each do |node|
+              if node.respond_to?(:raw_node)
+                raw_nodes << node.raw_node
+              else
+                raw_nodes << node
+              end
+            end
+          end
+          ordered_nodeset = sort(raw_nodes, order)
+        end
+        new_nodeset = []
+        ordered_nodeset.each do |node|
+          # TODO: Remove duplicated
+          new_nodeset << XPathNode.new(node, position: new_nodeset.size + 1)
+        end
+        new_nodeset
+      # ensure
+      #   leave(:step, path_stack, new_nodeset)
+      end
+    end
+
+    def node_test(path_stack, nodesets, any_type: :element)
+      # enter(:node_test, path_stack, nodesets)
+      operator = path_stack.shift
+      case operator
+      when :qname
+        prefix = path_stack.shift
+        name = path_stack.shift
+        new_nodesets = nodesets.collect do |nodeset|
+          filter_nodeset(nodeset) do |node|
+            raw_node = node.raw_node
+            case raw_node.node_type
+            when :element
+              if prefix.nil?
+                raw_node.name == name
+              elsif prefix.empty?
+                raw_node.name == name and raw_node.namespace == ""
+              else
+                # FIXME: This DOUBLES the time XPath searches take
+                ns = get_namespace(raw_node, prefix)
+                raw_node.name == name and raw_node.namespace == ns
+              end
+            when :attribute
+              if prefix.nil?
+                raw_node.name == name
+              elsif prefix.empty?
+                # FIXME: This DOUBLES the time XPath searches take
+                raw_node.name == name and
+                  raw_node.namespace == raw_node.element.namespace
+              else
+                # FIXME: This DOUBLES the time XPath searches take
+                ns = get_namespace(raw_node.element, prefix)
+                raw_node.name == name and raw_node.namespace == ns
+              end
+            else
+              false
+            end
+          end
+        end
+      when :namespace
+        prefix = path_stack.shift
+        new_nodesets = nodesets.collect do |nodeset|
+          filter_nodeset(nodeset) do |node|
+            raw_node = node.raw_node
+            case raw_node.node_type
+            when :element
+              namespaces = @namespaces || raw_node.namespaces
+              raw_node.namespace == namespaces[prefix]
+            when :attribute
+              namespaces = @namespaces || raw_node.element.namespaces
+              raw_node.namespace == namespaces[prefix]
+            else
+              false
+            end
+          end
+        end
+      when :any
+        new_nodesets = nodesets.collect do |nodeset|
+          filter_nodeset(nodeset) do |node|
+            raw_node = node.raw_node
+            raw_node.node_type == any_type
+          end
+        end
+      when :comment
+        new_nodesets = nodesets.collect do |nodeset|
+          filter_nodeset(nodeset) do |node|
+            raw_node = node.raw_node
+            raw_node.node_type == :comment
+          end
+        end
+      when :text
+        new_nodesets = nodesets.collect do |nodeset|
+          filter_nodeset(nodeset) do |node|
+            raw_node = node.raw_node
+            raw_node.node_type == :text
+          end
+        end
+      when :processing_instruction
+        target = path_stack.shift
+        new_nodesets = nodesets.collect do |nodeset|
+          filter_nodeset(nodeset) do |node|
+            raw_node = node.raw_node
+            (raw_node.node_type == :processing_instruction) and
+              (target.empty? or (raw_node.target == target))
+          end
+        end
+      when :node
+        new_nodesets = nodesets.collect do |nodeset|
+          filter_nodeset(nodeset) do |node|
+            true
+          end
+        end
+      else
+        message = "[BUG] Unexpected node test: " +
+          "<#{operator.inspect}>: <#{path_stack.inspect}>"
+        raise message
+      end
+      new_nodesets
+    # ensure
+    #   leave(:node_test, path_stack, new_nodesets)
+    end
+
+    def filter_nodeset(nodeset)
+      new_nodeset = []
+      nodeset.each do |node|
+        next unless yield(node)
+        new_nodeset << XPathNode.new(node, position: new_nodeset.size + 1)
+      end
+      new_nodeset
+    end
+
+    def predicate(expression, nodesets)
+      # enter(:predicate, expression, nodesets)
+      new_nodesets = nodesets.collect do |nodeset|
+        new_nodeset = []
+        subcontext = { :size => nodeset.size }
+        nodeset.each_with_index do |node, index|
+          if node.is_a?(XPathNode)
+            subcontext[:node] = node.raw_node
+            subcontext[:index] = node.position
+          else
+            subcontext[:node] = node
+            subcontext[:index] = index + 1
+          end
+          result = expr(expression.dclone, [node], subcontext)
+          # trace(:predicate_evaluate, expression, node, subcontext, result)
+          result = result[0] if result.kind_of? Array and result.length == 1
+          if result.kind_of? Numeric
+            if result == node.position
+              new_nodeset << XPathNode.new(node, position: new_nodeset.size + 1)
+            end
+          elsif result.instance_of? Array
+            if result.size > 0 and result.inject(false) {|k,s| s or k}
+              if result.size > 0
+                new_nodeset << XPathNode.new(node, position: new_nodeset.size + 1)
+              end
+            end
+          else
+            if result
+              new_nodeset << XPathNode.new(node, position: new_nodeset.size + 1)
+            end
+          end
+        end
+        new_nodeset
+      end
+    # ensure
+    #   leave(:predicate, new_nodesets)
+    end
+
     def trace(*args)
       indent = "  " * @nest
       puts("#{indent}#{args.inspect}")
@@ -510,33 +622,6 @@ module REXML
       trace(:leave, tag, *args)
     end
 
-    ##########################################################
-    # FIXME
-    # The next two methods are BAD MOJO!
-    # This is my achilles heel.  If anybody thinks of a better
-    # way of doing this, be my guest.  This really sucks, but
-    # it is a wonder it works at all.
-    # ########################################################
-
-    def descendant_or_self( path_stack, nodeset )
-      rs = []
-      d_o_s( path_stack, nodeset, rs )
-      document_order(rs.flatten.compact)
-      #rs.flatten.compact
-    end
-
-    def d_o_s( p, ns, r )
-      nt = nil
-      ns.each_index do |i|
-        n = ns[i]
-        x = expr( p.dclone, [ n ] )
-        nt = n.node_type
-        d_o_s( p, n.children, x ) if nt == :element or nt == :document and n.children.size > 0
-        r.concat(x) if x.size > 0
-      end
-    end
-
-
     # Reorders an array of nodes so that they are in document order
     # It tries to do this efficiently.
     #
@@ -545,7 +630,7 @@ module REXML
     # in and out of function calls.  If I knew what the index of the nodes was,
     # I wouldn't have to do this.  Maybe add a document IDX for each node?
     # Problems with mutable documents.  Or, rewrite everything.
-    def document_order( array_of_nodes )
+    def sort(array_of_nodes, order)
       new_arry = []
       array_of_nodes.each { |node|
         node_idx = []
@@ -556,42 +641,68 @@ module REXML
         end
         new_arry << [ node_idx.reverse, node ]
       }
-      new_arry.sort{ |s1, s2| s1[0] <=> s2[0] }.collect{ |s| s[1] }
+      ordered = new_arry.sort_by do |index, node|
+        if order == :forward
+          index
+        else
+          -index
+        end
+      end
+      ordered.collect do |_index, node|
+        node
+      end
     end
 
-
-    def recurse( nodeset, &block )
-      for node in nodeset
-        yield node
-        recurse( node, &block ) if node.node_type == :element
+    def descendant(nodeset, include_self)
+      nodesets = []
+      nodeset.each do |node|
+        new_nodeset = []
+        new_nodes = {}
+        descendant_recursive(node.raw_node, new_nodeset, new_nodes, include_self)
+        nodesets << new_nodeset unless new_nodeset.empty?
       end
+      nodesets
     end
 
+    def descendant_recursive(raw_node, new_nodeset, new_nodes, include_self)
+      if include_self
+        return if new_nodes.key?(raw_node)
+        new_nodeset << XPathNode.new(raw_node, position: new_nodeset.size + 1)
+        new_nodes[raw_node] = true
+      end
 
+      node_type = raw_node.node_type
+      if node_type == :element or node_type == :document
+        raw_node.children.each do |child|
+          descendant_recursive(child, new_nodeset, new_nodes, true)
+        end
+      end
+    end
 
     # Builds a nodeset of all of the preceding nodes of the supplied node,
     # in reverse document order
     # preceding:: includes every element in the document that precedes this node,
     # except for ancestors
-    def preceding( node )
+    def preceding(node)
       ancestors = []
-      p = node.parent
-      while p
-        ancestors << p
-        p = p.parent
+      parent = node.parent
+      while parent
+        ancestors << parent
+        parent = parent.parent
       end
 
-      acc = []
-      p = preceding_node_of( node )
-      while p
-        if ancestors.include? p
-          ancestors.delete(p)
+      precedings = []
+      preceding_node = preceding_node_of(node)
+      while preceding_node
+        if ancestors.include?(preceding_node)
+          ancestors.delete(preceding_node)
         else
-          acc << p
+          precedings << XPathNode.new(preceding_node,
+                                      position: precedings.size + 1)
         end
-        p = preceding_node_of( p )
+        preceding_node = preceding_node_of(preceding_node)
       end
-      acc
+      precedings
     end
 
     def preceding_node_of( node )
@@ -609,14 +720,16 @@ module REXML
       psn
     end
 
-    def following( node )
-      acc = []
-      p = next_sibling_node( node )
-      while p
-        acc << p
-        p = following_node_of( p )
+    def following(node)
+      followings = []
+      position = 1
+      following_node = next_sibling_node(node)
+      while following_node
+        followings << XPathNode.new(following_node,
+                                    position: followings.size + 1)
+        following_node = following_node_of(following_node)
       end
-      acc
+      followings
     end
 
     def following_node_of( node )
@@ -638,13 +751,40 @@ module REXML
       return psn
     end
 
+    def child(nodeset)
+      nodesets = []
+      nodeset.each do |node|
+        raw_node = node.raw_node
+        node_type = raw_node.node_type
+        # trace(:child, node_type, node)
+        case node_type
+        when :element
+          nodesets << raw_node.children.collect.with_index do |node, i|
+            XPathNode.new(node, position: i + 1)
+          end
+        when :document
+          new_nodeset = []
+          raw_node.children.each do |child|
+            case child
+            when XMLDecl, Text
+              # Ignore
+            else
+              new_nodeset << XPathNode.new(child, position: new_nodeset.size + 1)
+            end
+          end
+          nodesets << new_nodeset unless new_nodeset.empty?
+        end
+      end
+      nodesets
+    end
+
     def norm b
       case b
       when true, false
         return b
       when 'true', 'false'
         return Functions::boolean( b )
-      when /^\d+(\.\d+)?$/
+      when /^\d+(\.\d+)?$/, Numeric
         return Functions::number( b )
       else
         return Functions::string( b )
@@ -652,11 +792,10 @@ module REXML
     end
 
     def equality_relational_compare( set1, op, set2 )
+      set1 = unnode(set1) if set1.is_a?(Array)
+      set2 = unnode(set2) if set2.is_a?(Array)
       if set1.kind_of? Array and set2.kind_of? Array
-        if set1.size == 1 and set2.size == 1
-          set1 = set1[0]
-          set2 = set2[0]
-        elsif set1.size == 0 or set2.size == 0
+        if set1.size == 0 or set2.size == 0
           nd = set1.size==0 ? set2 : set1
           rv = nd.collect { |il| compare( il, op, nil ) }
           return rv
@@ -687,15 +826,15 @@ module REXML
 
         case b
         when true, false
-          return a.collect {|v| compare( Functions::boolean(v), op, b ) }
+          return unnode(a) {|v| compare( Functions::boolean(v), op, b ) }
         when Numeric
-          return a.collect {|v| compare( Functions::number(v), op, b )}
+          return unnode(a) {|v| compare( Functions::number(v), op, b )}
         when /^\d+(\.\d+)?$/
           b = Functions::number( b )
-          return a.collect {|v| compare( Functions::number(v), op, b )}
+          return unnode(a) {|v| compare( Functions::number(v), op, b )}
         else
           b = Functions::string( b )
-          return a.collect { |v| compare( Functions::string(v), op, b ) }
+          return unnode(a) { |v| compare( Functions::string(v), op, b ) }
         end
       else
         # If neither is nodeset,
@@ -705,8 +844,10 @@ module REXML
         #     Else, convert to string
         #   Else
         #     Convert both to numbers and compare
-        s1 = set1.to_s
-        s2 = set2.to_s
+        set1 = unnode(set1) if set1.is_a?(Array)
+        set2 = unnode(set2) if set2.is_a?(Array)
+        s1 = Functions.string(set1)
+        s2 = Functions.string(set2)
         if s1 == 'true' or s1 == 'false' or s2 == 'true' or s2 == 'false'
           set1 = Functions::boolean( set1 )
           set2 = Functions::boolean( set2 )
@@ -751,5 +892,34 @@ module REXML
         false
       end
     end
+
+    def unnode(nodeset)
+      nodeset.collect do |node|
+        if node.is_a?(XPathNode)
+          unnoded = node.raw_node
+        else
+          unnoded = node
+        end
+        unnoded = yield(unnoded) if block_given?
+        unnoded
+      end
+    end
+  end
+
+  # @private
+  class XPathNode
+    attr_reader :raw_node, :context
+    def initialize(node, context=nil)
+      if node.is_a?(XPathNode)
+        @raw_node = node.raw_node
+      else
+        @raw_node = node
+      end
+      @context = context || {}
+    end
+
+    def position
+      @context[:position]
+    end
   end
 end
diff --git a/test/rexml/test_jaxen.rb b/test/rexml/test_jaxen.rb
index 0f8653c956..81cef500a3 100644
--- a/test/rexml/test_jaxen.rb
+++ b/test/rexml/test_jaxen.rb
@@ -24,14 +24,17 @@ module REXMLTests
     # document() function for XSLT isn't supported
     def _test_message ; process_test_case("message") ; end
     def test_moreover ; process_test_case("moreover") ; end
-    def _test_much_ado ; process_test_case("much_ado") ; end
-    def _test_namespaces ; process_test_case("namespaces") ; end
-    def _test_nitf ; process_test_case("nitf") ; end
+    def test_much_ado ; process_test_case("much_ado") ; end
+    def test_namespaces ; process_test_case("namespaces") ; end
+    def test_nitf ; process_test_case("nitf") ; end
+    # Exception should be considered
     def _test_numbers ; process_test_case("numbers") ; end
     def test_pi ; process_test_case("pi") ; end
     def test_pi2 ; process_test_case("pi2") ; end
     def test_simple ; process_test_case("simple") ; end
+    # TODO: namespace node is needed
     def _test_testNamespaces ; process_test_case("testNamespaces") ; end
+    # document() function for XSLT isn't supported
     def _test_text ; process_test_case("text") ; end
     def test_underscore ; process_test_case("underscore") ; end
     def _test_web ; process_test_case("web") ; end
diff --git a/test/rexml/xpath/test_base.rb b/test/rexml/xpath/test_base.rb
index 497bd9fc8f..790dcaea22 100644
--- a/test/rexml/xpath/test_base.rb
+++ b/test/rexml/xpath/test_base.rb
@@ -713,7 +713,7 @@ module REXMLTests
       XML
       d = REXML::Document.new( source )
       r = REXML::XPath.match( d, %q{/a/*/*[1]} )
-      assert_equal(["1"],
+      assert_equal(["1", "3"],
                    r.collect {|element| element.attribute("id").value})
     end
 
@@ -849,7 +849,7 @@ module REXMLTests
       EOL
       d = REXML::Document.new( string )
       cs = XPath.match( d, '/a/*/*[1]' )
-      assert_equal(["c1"], cs.collect(&:name))
+      assert_equal(["c1", "c2"], cs.collect(&:name))
     end
 
     def test_sum