Source/WebCore/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 "XPathPath.h"
  30
  31 #include "Document.h"
  32 #include "XPathPredicate.h"
  33 #include "XPathStep.h"
  34 #include "XPathValue.h"
  35
  36 namespace WebCore {
  37 namespace XPath {
  38
  39 Filter::Filter(Expression* expr, const Vector<Predicate*>& predicates)
  40     : m_expr(expr), m_predicates(predicates)
  41 {
  42     setIsContextNodeSensitive(m_expr->isContextNodeSensitive());
  43     setIsContextPositionSensitive(m_expr->isContextPositionSensitive());
  44     setIsContextSizeSensitive(m_expr->isContextSizeSensitive());
  45 }
  46
  47 Filter::~Filter()
  48 {
  49     delete m_expr;
  50     deleteAllValues(m_predicates);
  51 }
  52
  53 Value Filter::evaluate() const
  54 {
  55     Value v = m_expr->evaluate();
  56
  57     NodeSet& nodes = v.modifiableNodeSet();
  58     nodes.sort();
  59
  60     EvaluationContext& evaluationContext = Expression::evaluationContext();
  61     for (unsigned i = 0; i < m_predicates.size(); i++) {
  62         NodeSet newNodes;
  63         evaluationContext.size = nodes.size();
  64         evaluationContext.position = 0;
  65
  66         for (unsigned j = 0; j < nodes.size(); j++) {
  67             Node* node = nodes[j];
  68
  69             evaluationContext.node = node;
  70             ++evaluationContext.position;
  71
  72             if (m_predicates[i]->evaluate())
  73                 newNodes.append(node);
  74         }
  75         nodes.swap(newNodes);
  76     }
  77
  78     return v;
  79 }
  80
  81 LocationPath::LocationPath()
  82     : m_absolute(false)
  83 {
  84     setIsContextNodeSensitive(true);
  85 }
  86
  87 LocationPath::~LocationPath()
  88 {
  89     deleteAllValues(m_steps);
  90 }
  91
  92 Value LocationPath::evaluate() const
  93 {
  94     EvaluationContext& evaluationContext = Expression::evaluationContext();
  95     EvaluationContext backupContext = evaluationContext;
  96     // For absolute location paths, the context node is ignored - the
  97     // document's root node is used instead.
  98     Node* context = evaluationContext.node.get();
  99     if (m_absolute && context->nodeType() != Node::DOCUMENT_NODE)
 100         context = context->ownerDocument();
 101
 102     NodeSet nodes;
 103     nodes.append(context);
 104     evaluate(nodes);
 105
 106     evaluationContext = backupContext;
 107     return Value(nodes, Value::adopt);
 108 }
 109
 110 void LocationPath::evaluate(NodeSet& nodes) const
 111 {
 112     bool resultIsSorted = nodes.isSorted();
 113
 114     for (unsigned i = 0; i < m_steps.size(); i++) {
 115         Step* step = m_steps[i];
 116         NodeSet newNodes;
 117         HashSet<Node*> newNodesSet;
 118
 119         bool needToCheckForDuplicateNodes = !nodes.subtreesAreDisjoint() || (step->axis() != Step::ChildAxis && step->axis() != Step::SelfAxis
 120             && step->axis() != Step::DescendantAxis && step->axis() != Step::DescendantOrSelfAxis && step->axis() != Step::AttributeAxis);
 121
 122         if (needToCheckForDuplicateNodes)
 123             resultIsSorted = false;
 124
 125         // This is a simplified check that can be improved to handle more cases.
 126         if (nodes.subtreesAreDisjoint() && (step->axis() == Step::ChildAxis || step->axis() == Step::SelfAxis))
 127             newNodes.markSubtreesDisjoint(true);
 128
 129         for (unsigned j = 0; j < nodes.size(); j++) {
 130             NodeSet matches;
 131             step->evaluate(nodes[j], matches);
 132
 133             if (!matches.isSorted())
 134                 resultIsSorted = false;
 135
 136             for (size_t nodeIndex = 0; nodeIndex < matches.size(); ++nodeIndex) {
 137                 Node* node = matches[nodeIndex];
 138                 if (!needToCheckForDuplicateNodes || newNodesSet.add(node).second)
 139                     newNodes.append(node);
 140             }
 141         }
 142
 143         nodes.swap(newNodes);
 144     }
 145
 146     nodes.markSorted(resultIsSorted);
 147 }
 148
 149 void LocationPath::appendStep(Step* step)
 150 {
 151     unsigned stepCount = m_steps.size();
 152     if (stepCount) {
 153         bool dropSecondStep;
 154         optimizeStepPair(m_steps[stepCount - 1], step, dropSecondStep);
 155         if (dropSecondStep) {
 156             delete step;
 157             return;
 158         }
 159     }
 160     step->optimize();
 161     m_steps.append(step);
 162 }
 163
 164 void LocationPath::insertFirstStep(Step* step)
 165 {
 166     if (m_steps.size()) {
 167         bool dropSecondStep;
 168         optimizeStepPair(step, m_steps[0], dropSecondStep);
 169         if (dropSecondStep) {
 170             delete m_steps[0];
 171             m_steps[0] = step;
 172             return;
 173         }
 174     }
 175     step->optimize();
 176     m_steps.insert(0, step);
 177 }
 178
 179 Path::Path(Filter* filter, LocationPath* path)
 180     : m_filter(filter)
 181     , m_path(path)
 182 {
 183     setIsContextNodeSensitive(filter->isContextNodeSensitive());
 184     setIsContextPositionSensitive(filter->isContextPositionSensitive());
 185     setIsContextSizeSensitive(filter->isContextSizeSensitive());
 186 }
 187
 188 Path::~Path()
 189 {
 190     delete m_filter;
 191     delete m_path;
 192 }
 193
 194 Value Path::evaluate() const
 195 {
 196     Value v = m_filter->evaluate();
 197
 198     NodeSet& nodes = v.modifiableNodeSet();
 199     m_path->evaluate(nodes);
 200
 201     return v;
 202 }
 203
 204 }
 205 }