--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/WebCore/xml/XPathPath.cpp	Fri Sep 17 09:02:29 2010 +0300
@@ -0,0 +1,209 @@
+/*
+ * Copyright (C) 2005 Frerich Raabe <raabe@kde.org>
+ * Copyright (C) 2006, 2009 Apple Inc.
+ * Copyright (C) 2007 Alexey Proskuryakov <ap@webkit.org>
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "config.h"
+#include "XPathPath.h"
+
+#if ENABLE(XPATH)
+
+#include "Document.h"
+#include "XPathPredicate.h"
+#include "XPathStep.h"
+#include "XPathValue.h"
+
+namespace WebCore {
+namespace XPath {
+        
+Filter::Filter(Expression* expr, const Vector<Predicate*>& predicates)
+    : m_expr(expr), m_predicates(predicates)
+{
+    setIsContextNodeSensitive(m_expr->isContextNodeSensitive());
+    setIsContextPositionSensitive(m_expr->isContextPositionSensitive());
+    setIsContextSizeSensitive(m_expr->isContextSizeSensitive());
+}
+
+Filter::~Filter()
+{
+    delete m_expr;
+    deleteAllValues(m_predicates);
+}
+
+Value Filter::evaluate() const
+{
+    Value v = m_expr->evaluate();
+    
+    NodeSet& nodes = v.modifiableNodeSet();
+    nodes.sort();
+
+    EvaluationContext& evaluationContext = Expression::evaluationContext();
+    for (unsigned i = 0; i < m_predicates.size(); i++) {
+        NodeSet newNodes;
+        evaluationContext.size = nodes.size();
+        evaluationContext.position = 0;
+        
+        for (unsigned j = 0; j < nodes.size(); j++) {
+            Node* node = nodes[j];
+            
+            evaluationContext.node = node;
+            ++evaluationContext.position;
+            
+            if (m_predicates[i]->evaluate())
+                newNodes.append(node);
+        }
+        nodes.swap(newNodes);
+    }
+
+    return v;
+}
+
+LocationPath::LocationPath()
+    : m_absolute(false)
+{
+    setIsContextNodeSensitive(true);
+}
+
+LocationPath::~LocationPath()
+{
+    deleteAllValues(m_steps);
+}
+
+Value LocationPath::evaluate() const
+{
+    EvaluationContext& evaluationContext = Expression::evaluationContext();
+    EvaluationContext backupContext = evaluationContext;
+    // For absolute location paths, the context node is ignored - the
+    // document's root node is used instead.
+    Node* context = evaluationContext.node.get();
+    if (m_absolute && context->nodeType() != Node::DOCUMENT_NODE) 
+        context = context->ownerDocument();
+
+    NodeSet nodes;
+    nodes.append(context);
+    evaluate(nodes);
+    
+    evaluationContext = backupContext;
+    return Value(nodes, Value::adopt);
+}
+
+void LocationPath::evaluate(NodeSet& nodes) const
+{
+    bool resultIsSorted = nodes.isSorted();
+
+    for (unsigned i = 0; i < m_steps.size(); i++) {
+        Step* step = m_steps[i];
+        NodeSet newNodes;
+        HashSet<Node*> newNodesSet;
+
+        bool needToCheckForDuplicateNodes = !nodes.subtreesAreDisjoint() || (step->axis() != Step::ChildAxis && step->axis() != Step::SelfAxis
+            && step->axis() != Step::DescendantAxis && step->axis() != Step::DescendantOrSelfAxis && step->axis() != Step::AttributeAxis);
+
+        if (needToCheckForDuplicateNodes)
+            resultIsSorted = false;
+
+        // This is a simplified check that can be improved to handle more cases.
+        if (nodes.subtreesAreDisjoint() && (step->axis() == Step::ChildAxis || step->axis() == Step::SelfAxis))
+            newNodes.markSubtreesDisjoint(true);
+
+        for (unsigned j = 0; j < nodes.size(); j++) {
+            NodeSet matches;
+            step->evaluate(nodes[j], matches);
+
+            if (!matches.isSorted())
+                resultIsSorted = false;
+
+            for (size_t nodeIndex = 0; nodeIndex < matches.size(); ++nodeIndex) {
+                Node* node = matches[nodeIndex];
+                if (!needToCheckForDuplicateNodes || newNodesSet.add(node).second)
+                    newNodes.append(node);
+            }
+        }
+        
+        nodes.swap(newNodes);
+    }
+
+    nodes.markSorted(resultIsSorted);
+}
+
+void LocationPath::appendStep(Step* step)
+{
+    unsigned stepCount = m_steps.size();
+    if (stepCount) {
+        bool dropSecondStep;
+        optimizeStepPair(m_steps[stepCount - 1], step, dropSecondStep);
+        if (dropSecondStep) {
+            delete step;
+            return;
+        }
+    }
+    step->optimize();
+    m_steps.append(step);
+}
+
+void LocationPath::insertFirstStep(Step* step)
+{
+    if (m_steps.size()) {
+        bool dropSecondStep;
+        optimizeStepPair(step, m_steps[0], dropSecondStep);
+        if (dropSecondStep) {
+            delete m_steps[0];
+            m_steps[0] = step;
+            return;
+        }
+    }
+    step->optimize();
+    m_steps.insert(0, step);
+}
+
+Path::Path(Filter* filter, LocationPath* path)
+    : m_filter(filter)
+    , m_path(path)
+{
+    setIsContextNodeSensitive(filter->isContextNodeSensitive());
+    setIsContextPositionSensitive(filter->isContextPositionSensitive());
+    setIsContextSizeSensitive(filter->isContextSizeSensitive());
+}
+
+Path::~Path()
+{
+    delete m_filter;
+    delete m_path;
+}
+
+Value Path::evaluate() const
+{
+    Value v = m_filter->evaluate();
+
+    NodeSet& nodes = v.modifiableNodeSet();
+    m_path->evaluate(nodes);
+    
+    return v;
+}
+
+}
+}
+
+#endif // ENABLE(XPATH)