Always enable ENABLE(XPATH)
[WebKit.git] / 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 }