Home | History | Annotate | Download | only in xml 
      1 /*
      2  * Copyright (C) 2005 Frerich Raabe <raabe (at) kde.org>
      3  * Copyright (C) 2006, 2009 Apple Inc.
      4  * Copyright (C) 2007 Alexey Proskuryakov <ap (at) 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(PassOwnPtrWillBeRawPtr<Expression> expr, WillBeHeapVector<OwnPtrWillBeMember<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 void Filter::trace(Visitor* visitor)
     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         OwnPtrWillBeRawPtr<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 #if !ENABLE(OILPAN)
     96     deleteAllValues(m_steps);
     97 #endif
     98 }
     99 
    100 void LocationPath::trace(Visitor* visitor)
    101 {
    102 #if ENABLE(OILPAN)
    103     visitor->trace(m_steps);
    104 #endif
    105     Expression::trace(visitor);
    106 }
    107 
    108 Value LocationPath::evaluate(EvaluationContext& evaluationContext) const
    109 {
    110     EvaluationContext clonedContext = evaluationContext;
    111     // http://www.w3.org/TR/xpath/
    112     // Section 2, Location Paths:
    113     // "/ selects the document root (which is always the parent of the document element)"
    114     // "A / by itself selects the root node of the document containing the context node."
    115     // In the case of a tree that is detached from the document, we violate
    116     // the spec and treat / as the root node of the detached tree.
    117     // This is for compatibility with Firefox, and also seems like a more
    118     // logical treatment of where you would expect the "root" to be.
    119     Node* context = evaluationContext.node.get();
    120     if (m_absolute && context->nodeType() != Node::DOCUMENT_NODE)  {
    121         if (context->inDocument())
    122             context = context->ownerDocument();
    123         else
    124             context = &NodeTraversal::highestAncestorOrSelf(*context);
    125     }
    126 
    127     OwnPtrWillBeRawPtr<NodeSet> nodes(NodeSet::create());
    128     nodes->append(context);
    129     evaluate(clonedContext, *nodes);
    130 
    131     return Value(nodes.release(), Value::adopt);
    132 }
    133 
    134 void LocationPath::evaluate(EvaluationContext& context, NodeSet& nodes) const
    135 {
    136     bool resultIsSorted = nodes.isSorted();
    137 
    138     for (unsigned i = 0; i < m_steps.size(); i++) {
    139         Step* step = m_steps[i];
    140         OwnPtrWillBeRawPtr<NodeSet> newNodes(NodeSet::create());
    141         WillBeHeapHashSet<RawPtrWillBeMember<Node> > newNodesSet;
    142 
    143         bool needToCheckForDuplicateNodes = !nodes.subtreesAreDisjoint() || (step->axis() != Step::ChildAxis && step->axis() != Step::SelfAxis
    144             && step->axis() != Step::DescendantAxis && step->axis() != Step::DescendantOrSelfAxis && step->axis() != Step::AttributeAxis);
    145 
    146         if (needToCheckForDuplicateNodes)
    147             resultIsSorted = false;
    148 
    149         // This is a simplified check that can be improved to handle more cases.
    150         if (nodes.subtreesAreDisjoint() && (step->axis() == Step::ChildAxis || step->axis() == Step::SelfAxis))
    151             newNodes->markSubtreesDisjoint(true);
    152 
    153         for (unsigned j = 0; j < nodes.size(); j++) {
    154             OwnPtrWillBeRawPtr<NodeSet> matches(NodeSet::create());
    155             step->evaluate(context, nodes[j], *matches);
    156 
    157             if (!matches->isSorted())
    158                 resultIsSorted = false;
    159 
    160             for (size_t nodeIndex = 0; nodeIndex < matches->size(); ++nodeIndex) {
    161                 Node* node = (*matches)[nodeIndex];
    162                 if (!needToCheckForDuplicateNodes || newNodesSet.add(node).isNewEntry)
    163                     newNodes->append(node);
    164             }
    165         }
    166 
    167         nodes.swap(*newNodes);
    168     }
    169 
    170     nodes.markSorted(resultIsSorted);
    171 }
    172 
    173 void LocationPath::appendStep(Step* step)
    174 {
    175     unsigned stepCount = m_steps.size();
    176     if (stepCount) {
    177         bool dropSecondStep;
    178         optimizeStepPair(m_steps[stepCount - 1], step, dropSecondStep);
    179         if (dropSecondStep) {
    180 #if !ENABLE(OILPAN)
    181             delete step;
    182 #endif
    183             return;
    184         }
    185     }
    186     step->optimize();
    187     m_steps.append(step);
    188 }
    189 
    190 void LocationPath::insertFirstStep(Step* step)
    191 {
    192     if (m_steps.size()) {
    193         bool dropSecondStep;
    194         optimizeStepPair(step, m_steps[0], dropSecondStep);
    195         if (dropSecondStep) {
    196 #if !ENABLE(OILPAN)
    197             delete m_steps[0];
    198 #endif
    199             m_steps[0] = step;
    200             return;
    201         }
    202     }
    203     step->optimize();
    204     m_steps.insert(0, step);
    205 }
    206 
    207 Path::Path(Expression* filter, LocationPath* path)
    208     : m_filter(adoptPtrWillBeNoop(filter))
    209     , m_path(adoptPtrWillBeNoop(path))
    210 {
    211     setIsContextNodeSensitive(filter->isContextNodeSensitive());
    212     setIsContextPositionSensitive(filter->isContextPositionSensitive());
    213     setIsContextSizeSensitive(filter->isContextSizeSensitive());
    214 }
    215 
    216 Path::~Path()
    217 {
    218 }
    219 
    220 void Path::trace(Visitor* visitor)
    221 {
    222     visitor->trace(m_filter);
    223     visitor->trace(m_path);
    224     Expression::trace(visitor);
    225 }
    226 
    227 Value Path::evaluate(EvaluationContext& context) const
    228 {
    229     Value v = m_filter->evaluate(context);
    230 
    231     NodeSet& nodes = v.modifiableNodeSet(context);
    232     m_path->evaluate(context, nodes);
    233 
    234     return v;
    235 }
    236 
    237 }
    238 }
    239