Reviewed by Darin.
[WebKit-https.git] / WebCore / xml / XPathPath.cpp
1 /*
2  * Copyright 2005 Frerich Raabe <raabe@kde.org>
3  * Copyright (C) 2006 Apple Computer, 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 }
45
46 Filter::~Filter()
47 {
48     delete m_expr;
49     deleteAllValues(m_predicates);
50 }
51
52 Value Filter::evaluate() const
53 {
54     Value v = m_expr->evaluate();
55     
56     if (!v.isNodeSet()) 
57         return v;
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 }
87
88 LocationPath::~LocationPath()
89 {
90     deleteAllValues(m_steps);
91 }
92
93 Value LocationPath::evaluate() const
94 {
95     EvaluationContext& evaluationContext = Expression::evaluationContext();
96     EvaluationContext backupContext = evaluationContext;
97     /* For absolute location paths, the context node is ignored - the
98      * document's root node is used instead.
99      */
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     for (unsigned i = 0; i < m_steps.size(); i++) {
115         Step* step = m_steps[i];
116         NodeSet newNodes;
117         HashSet<Node*> newNodesSet;
118
119         for (unsigned j = 0; j < nodes.size(); j++) {
120             NodeSet matches;
121             step->evaluate(nodes[j], matches);
122             
123             for (size_t nodeIndex = 0; nodeIndex < matches.size(); ++nodeIndex) {
124                 Node* node = matches[nodeIndex];
125                 if (newNodesSet.add(node).second)
126                     newNodes.append(node);
127             }
128         }
129         
130         nodes.swap(newNodes);
131     }
132
133     nodes.markSorted(false);
134 }
135
136 void LocationPath::optimizeStepPair(unsigned index)
137 {
138     Step* first = m_steps[index];
139     
140     if (first->axis() == Step::DescendantOrSelfAxis
141         && first->nodeTest().kind() == Step::NodeTest::AnyNodeTest
142         && first->predicates().size() == 0) {
143
144         Step* second = m_steps[index + 1];
145         if (second->axis() == Step::ChildAxis
146             && second->nodeTest().namespaceURI().isEmpty()
147             && second->nodeTest().kind() == Step::NodeTest::NameTest
148             && second->nodeTest().data() == "*") {
149
150             // Optimize the common case of "//*" AKA descendant-or-self::node()/child::*.
151             first->setAxis(Step::DescendantAxis);
152             second->setAxis(Step::SelfAxis);
153             second->setNodeTest(Step::NodeTest::ElementNodeTest);
154             ASSERT(second->nodeTest().data().isEmpty());
155         }
156     }
157 }
158
159 void LocationPath::appendStep(Step* step)
160 {
161     m_steps.append(step);
162     
163     unsigned stepCount = m_steps.size();
164     if (stepCount > 1)
165         optimizeStepPair(stepCount - 2);
166 }
167
168 void LocationPath::insertFirstStep(Step* step)
169 {
170     m_steps.insert(0, step);
171
172     if (m_steps.size() > 1)
173         optimizeStepPair(0);
174 }
175
176 Path::Path(Filter* filter, LocationPath* path)
177     : m_filter(filter),
178     m_path(path)
179 {
180 }
181
182 Path::~Path()
183 {
184     delete m_filter;
185     delete m_path;
186 }
187
188 Value Path::evaluate() const
189 {
190     Value v = m_filter->evaluate();
191
192     NodeSet& nodes = v.modifiableNodeSet();
193     m_path->evaluate(nodes);
194     
195     return v;
196 }
197
198 }
199 }
200
201 #endif // ENABLE(XPATH)