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 #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)