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/dom/NodeTraversal.h"
  33 #include "core/xml/XPathPredicate.h"
  34 #include "core/xml/XPathStep.h"
  35 #include "core/xml/XPathValue.h"
  36
  37 namespace blink {
  38 namespace XPath {
  39
  40 Filter::Filter(Expression* expr, HeapVector<Member<Predicate>>& predicates)
  41     : m_expr(expr)
  42 {
  43     m_predicates.swap(predicates);
  44     setIsContextNodeSensitive(m_expr->isContextNodeSensitive());
  45     setIsContextPositionSensitive(m_expr->isContextPositionSensitive());
  46     setIsContextSizeSensitive(m_expr->isContextSizeSensitive());
  47 }
  48
  49 Filter::~Filter()
  50 {
  51 }
  52
  53 DEFINE_TRACE(Filter)
  54 {
  55     visitor->trace(m_expr);
  56     visitor->trace(m_predicates);
  57     Expression::trace(visitor);
  58 }
  59
  60 Value Filter::evaluate(EvaluationContext& evaluationContext) const
  61 {
  62     Value v = m_expr->evaluate(evaluationContext);
  63
  64     NodeSet& nodes = v.modifiableNodeSet(evaluationContext);
  65     nodes.sort();
  66
  67     for (unsigned i = 0; i < m_predicates.size(); i++) {
  68         NodeSet* newNodes = NodeSet::create();
  69         evaluationContext.size = nodes.size();
  70         evaluationContext.position = 0;
  71
  72         for (unsigned j = 0; j < nodes.size(); j++) {
  73             Node* node = nodes[j];
  74
  75             evaluationContext.node = node;
  76             ++evaluationContext.position;
  77
  78             if (m_predicates[i]->evaluate(evaluationContext))
  79                 newNodes->append(node);
  80         }
  81         nodes.swap(*newNodes);
  82     }
  83
  84     return v;
  85 }
  86
  87 LocationPath::LocationPath()
  88     : m_absolute(false)
  89 {
  90     setIsContextNodeSensitive(true);
  91 }
  92
  93 LocationPath::~LocationPath()
  94 {
  95 }
  96
  97 DEFINE_TRACE(LocationPath)
  98 {
  99     visitor->trace(m_steps);
 100     Expression::trace(visitor);
 101 }
 102
 103 Value LocationPath::evaluate(EvaluationContext& evaluationContext) const
 104 {
 105     EvaluationContext clonedContext = evaluationContext;
 106     // http://www.w3.org/TR/xpath/
 107     // Section 2, Location Paths:
 108     // "/ selects the document root (which is always the parent of the document element)"
 109     // "A / by itself selects the root node of the document containing the context node."
 110     // In the case of a tree that is detached from the document, we violate
 111     // the spec and treat / as the root node of the detached tree.
 112     // This is for compatibility with Firefox, and also seems like a more
 113     // logical treatment of where you would expect the "root" to be.
 114     Node* context = evaluationContext.node.get();
 115     if (m_absolute && context->nodeType() != Node::DOCUMENT_NODE)  {
 116         if (context->inDocument())
 117             context = context->ownerDocument();
 118         else
 119             context = &NodeTraversal::highestAncestorOrSelf(*context);
 120     }
 121
 122     NodeSet* nodes = NodeSet::create();
 123     nodes->append(context);
 124     evaluate(clonedContext, *nodes);
 125
 126     return Value(nodes, Value::adopt);
 127 }
 128
 129 void LocationPath::evaluate(EvaluationContext& context, NodeSet& nodes) const
 130 {
 131     bool resultIsSorted = nodes.isSorted();
 132
 133     for (unsigned i = 0; i < m_steps.size(); i++) {
 134         Step* step = m_steps[i];
 135         NodeSet* newNodes = NodeSet::create();
 136         WillBeHeapHashSet<RawPtrWillBeMember<Node>> newNodesSet;
 137
 138         bool needToCheckForDuplicateNodes = !nodes.subtreesAreDisjoint() || (step->axis() != Step::ChildAxis && step->axis() != Step::SelfAxis
 139             && step->axis() != Step::DescendantAxis && step->axis() != Step::DescendantOrSelfAxis && step->axis() != Step::AttributeAxis);
 140
 141         if (needToCheckForDuplicateNodes)
 142             resultIsSorted = false;
 143
 144         // This is a simplified check that can be improved to handle more cases.
 145         if (nodes.subtreesAreDisjoint() && (step->axis() == Step::ChildAxis || step->axis() == Step::SelfAxis))
 146             newNodes->markSubtreesDisjoint(true);
 147
 148         for (unsigned j = 0; j < nodes.size(); j++) {
 149             NodeSet* matches = NodeSet::create();
 150             step->evaluate(context, nodes[j], *matches);
 151
 152             if (!matches->isSorted())
 153                 resultIsSorted = false;
 154
 155             for (size_t nodeIndex = 0; nodeIndex < matches->size(); ++nodeIndex) {
 156                 Node* node = (*matches)[nodeIndex];
 157                 if (!needToCheckForDuplicateNodes || newNodesSet.add(node).isNewEntry)
 158                     newNodes->append(node);
 159             }
 160         }
 161
 162         nodes.swap(*newNodes);
 163     }
 164
 165     nodes.markSorted(resultIsSorted);
 166 }
 167
 168 void LocationPath::appendStep(Step* step)
 169 {
 170     unsigned stepCount = m_steps.size();
 171     if (stepCount && optimizeStepPair(m_steps[stepCount - 1], step))
 172         return;
 173     step->optimize();
 174     m_steps.append(step);
 175 }
 176
 177 void LocationPath::insertFirstStep(Step* step)
 178 {
 179     if (m_steps.size() && optimizeStepPair(step, m_steps[0])) {
 180         m_steps[0] = step;
 181         return;
 182     }
 183     step->optimize();
 184     m_steps.insert(0, step);
 185 }
 186
 187 Path::Path(Expression* filter, LocationPath* path)
 188     : m_filter(filter)
 189     , m_path(path)
 190 {
 191     setIsContextNodeSensitive(filter->isContextNodeSensitive());
 192     setIsContextPositionSensitive(filter->isContextPositionSensitive());
 193     setIsContextSizeSensitive(filter->isContextSizeSensitive());
 194 }
 195
 196 Path::~Path()
 197 {
 198 }
 199
 200 DEFINE_TRACE(Path)
 201 {
 202     visitor->trace(m_filter);
 203     visitor->trace(m_path);
 204     Expression::trace(visitor);
 205 }
 206
 207 Value Path::evaluate(EvaluationContext& context) const
 208 {
 209     Value v = m_filter->evaluate(context);
 210
 211     NodeSet& nodes = v.modifiableNodeSet(context);
 212     m_path->evaluate(context, nodes);
 213
 214     return v;
 215 }
 216
 217 } // namespace XPath
 218
 219 } // namespace blink