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