src/third_party/WebKit/Source/core/xml/XPathPath.cpp

   1 /*
   2  * Copyright (C) 2005 Frerich Raabe <raabe@kde.org>
   3  * Copyright (C) 2006, 2009 Apple Inc.
   4  * Copyright (C) 2007 Alexey Proskuryakov <ap@webkit.org>
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  *
  10  * 1. Redistributions of source code must retain the above copyright
  11  *    notice, this list of conditions and the following disclaimer.
  12  * 2. Redistributions in binary form must reproduce the above copyright
  13  *    notice, this list of conditions and the following disclaimer in the
  14  *    documentation and/or other materials provided with the distribution.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  17  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  18  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  19  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  20  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  21  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  22  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  23  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  24  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  25  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  26  */
  27
  28 #include "config.h"
  29 #include "core/xml/XPathPath.h"
  30
  31 #include "core/dom/Document.h"
  32 #include "core/xml/XPathPredicate.h"
  33 #include "core/xml/XPathStep.h"
  34 #include "core/xml/XPathValue.h"
  35
  36 namespace WebCore {
  37 namespace XPath {
  38
  39 Filter::Filter(PassOwnPtr<Expression> expr, Vector<OwnPtr<Predicate> >& predicates)
  40     : m_expr(expr)
  41 {
  42     m_predicates.swap(predicates);
  43     setIsContextNodeSensitive(m_expr->isContextNodeSensitive());
  44     setIsContextPositionSensitive(m_expr->isContextPositionSensitive());
  45     setIsContextSizeSensitive(m_expr->isContextSizeSensitive());
  46 }
  47
  48 Filter::~Filter()
  49 {
  50 }
  51
  52 Value Filter::evaluate() const
  53 {
  54     Value v = m_expr->evaluate();
  55
  56     NodeSet& nodes = v.modifiableNodeSet();
  57     nodes.sort();
  58
  59     EvaluationContext& evaluationContext = Expression::evaluationContext();
  60     for (unsigned i = 0; i < m_predicates.size(); i++) {
  61         NodeSet newNodes;
  62         evaluationContext.size = nodes.size();
  63         evaluationContext.position = 0;
  64
  65         for (unsigned j = 0; j < nodes.size(); j++) {
  66             Node* node = nodes[j];
  67
  68             evaluationContext.node = node;
  69             ++evaluationContext.position;
  70
  71             if (m_predicates[i]->evaluate())
  72                 newNodes.append(node);
  73         }
  74         nodes.swap(newNodes);
  75     }
  76
  77     return v;
  78 }
  79
  80 LocationPath::LocationPath()
  81     : m_absolute(false)
  82 {
  83     setIsContextNodeSensitive(true);
  84 }
  85
  86 LocationPath::~LocationPath()
  87 {
  88     deleteAllValues(m_steps);
  89 }
  90
  91 Value LocationPath::evaluate() const
  92 {
  93     EvaluationContext& evaluationContext = Expression::evaluationContext();
  94     EvaluationContext backupContext = evaluationContext;
  95     // http://www.w3.org/TR/xpath/
  96     // Section 2, Location Paths:
  97     // "/ selects the document root (which is always the parent of the document element)"
  98     // "A / by itself selects the root node of the document containing the context node."
  99     // In the case of a tree that is detached from the document, we violate
 100     // the spec and treat / as the root node of the detached tree.
 101     // This is for compatibility with Firefox, and also seems like a more
 102     // logical treatment of where you would expect the "root" to be.
 103     Node* context = evaluationContext.node.get();
 104     if (m_absolute && context->nodeType() != Node::DOCUMENT_NODE)  {
 105         if (context->inDocument())
 106             context = context->ownerDocument();
 107         else
 108             context = &context->highestAncestor();
 109     }
 110
 111     NodeSet nodes;
 112     nodes.append(context);
 113     evaluate(nodes);
 114
 115     evaluationContext = backupContext;
 116     return Value(nodes, Value::adopt);
 117 }
 118
 119 void LocationPath::evaluate(NodeSet& nodes) const
 120 {
 121     bool resultIsSorted = nodes.isSorted();
 122
 123     for (unsigned i = 0; i < m_steps.size(); i++) {
 124         Step* step = m_steps[i];
 125         NodeSet newNodes;
 126         HashSet<Node*> newNodesSet;
 127
 128         bool needToCheckForDuplicateNodes = !nodes.subtreesAreDisjoint() || (step->axis() != Step::ChildAxis && step->axis() != Step::SelfAxis
 129             && step->axis() != Step::DescendantAxis && step->axis() != Step::DescendantOrSelfAxis && step->axis() != Step::AttributeAxis);
 130
 131         if (needToCheckForDuplicateNodes)
 132             resultIsSorted = false;
 133
 134         // This is a simplified check that can be improved to handle more cases.
 135         if (nodes.subtreesAreDisjoint() && (step->axis() == Step::ChildAxis || step->axis() == Step::SelfAxis))
 136             newNodes.markSubtreesDisjoint(true);
 137
 138         for (unsigned j = 0; j < nodes.size(); j++) {
 139             NodeSet matches;
 140             step->evaluate(nodes[j], matches);
 141
 142             if (!matches.isSorted())
 143                 resultIsSorted = false;
 144
 145             for (size_t nodeIndex = 0; nodeIndex < matches.size(); ++nodeIndex) {
 146                 Node* node = matches[nodeIndex];
 147                 if (!needToCheckForDuplicateNodes || newNodesSet.add(node).isNewEntry)
 148                     newNodes.append(node);
 149             }
 150         }
 151
 152         nodes.swap(newNodes);
 153     }
 154
 155     nodes.markSorted(resultIsSorted);
 156 }
 157
 158 void LocationPath::appendStep(Step* step)
 159 {
 160     unsigned stepCount = m_steps.size();
 161     if (stepCount) {
 162         bool dropSecondStep;
 163         optimizeStepPair(m_steps[stepCount - 1], step, dropSecondStep);
 164         if (dropSecondStep) {
 165             delete step;
 166             return;
 167         }
 168     }
 169     step->optimize();
 170     m_steps.append(step);
 171 }
 172
 173 void LocationPath::insertFirstStep(Step* step)
 174 {
 175     if (m_steps.size()) {
 176         bool dropSecondStep;
 177         optimizeStepPair(step, m_steps[0], dropSecondStep);
 178         if (dropSecondStep) {
 179             delete m_steps[0];
 180             m_steps[0] = step;
 181             return;
 182         }
 183     }
 184     step->optimize();
 185     m_steps.insert(0, step);
 186 }
 187
 188 Path::Path(Expression* filter, LocationPath* path)
 189     : m_filter(filter)
 190     , m_path(path)
 191 {
 192     setIsContextNodeSensitive(filter->isContextNodeSensitive());
 193     setIsContextPositionSensitive(filter->isContextPositionSensitive());
 194     setIsContextSizeSensitive(filter->isContextSizeSensitive());
 195 }
 196
 197 Path::~Path()
 198 {
 199     delete m_filter;
 200     delete m_path;
 201 }
 202
 203 Value Path::evaluate() const
 204 {
 205     Value v = m_filter->evaluate();
 206
 207     NodeSet& nodes = v.modifiableNodeSet();
 208     m_path->evaluate(nodes);
 209
 210     return v;
 211 }
 212
 213 }
 214 }