1/*
2 * Copyright (C) 2005 Frerich Raabe <raabe@kde.org>
3 * Copyright (C) 2006, 2009, 2013 Apple Inc. All rights reserved.
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
35namespace WebCore {
36namespace XPath {
37
38Filter::Filter(std::unique_ptr<Expression> expression, Vector<std::unique_ptr<Expression>> predicates)
39 : m_expression(WTFMove(expression)), m_predicates(WTFMove(predicates))
40{
41 setIsContextNodeSensitive(m_expression->isContextNodeSensitive());
42 setIsContextPositionSensitive(m_expression->isContextPositionSensitive());
43 setIsContextSizeSensitive(m_expression->isContextSizeSensitive());
44}
45
46Value Filter::evaluate() const
47{
48 Value result = m_expression->evaluate();
49
50 NodeSet& nodes = result.modifiableNodeSet();
51 nodes.sort();
52
53 EvaluationContext& evaluationContext = Expression::evaluationContext();
54 for (auto& predicate : m_predicates) {
55 NodeSet newNodes;
56 evaluationContext.size = nodes.size();
57 evaluationContext.position = 0;
58
59 for (auto& node : nodes) {
60 evaluationContext.node = node;
61 ++evaluationContext.position;
62
63 if (evaluatePredicate(*predicate))
64 newNodes.append(node.copyRef());
65 }
66 nodes = WTFMove(newNodes);
67 }
68
69 return result;
70}
71
72LocationPath::LocationPath()
73 : m_isAbsolute(false)
74{
75 setIsContextNodeSensitive(true);
76}
77
78Value LocationPath::evaluate() const
79{
80 EvaluationContext& evaluationContext = Expression::evaluationContext();
81 EvaluationContext backupContext = evaluationContext;
82 // http://www.w3.org/TR/xpath/
83 // Section 2, Location Paths:
84 // "/ selects the document root (which is always the parent of the document element)"
85 // "A / by itself selects the root node of the document containing the context node."
86 // In the case of a tree that is detached from the document, we violate
87 // the spec and treat / as the root node of the detached tree.
88 // This is for compatibility with Firefox, and also seems like a more
89 // logical treatment of where you would expect the "root" to be.
90 Node* context = evaluationContext.node.get();
91 if (m_isAbsolute && !context->isDocumentNode())
92 context = &context->rootNode();
93
94 NodeSet nodes;
95 nodes.append(context);
96 evaluate(nodes);
97
98 evaluationContext = backupContext;
99 return Value(WTFMove(nodes));
100}
101
102void LocationPath::evaluate(NodeSet& nodes) const
103{
104 bool resultIsSorted = nodes.isSorted();
105
106 for (auto& step : m_steps) {
107 NodeSet newNodes;
108 HashSet<Node*> newNodesSet;
109
110 bool needToCheckForDuplicateNodes = !nodes.subtreesAreDisjoint() || (step->axis() != Step::ChildAxis && step->axis() != Step::SelfAxis
111 && step->axis() != Step::DescendantAxis && step->axis() != Step::DescendantOrSelfAxis && step->axis() != Step::AttributeAxis);
112
113 if (needToCheckForDuplicateNodes)
114 resultIsSorted = false;
115
116 // This is a simplified check that can be improved to handle more cases.
117 if (nodes.subtreesAreDisjoint() && (step->axis() == Step::ChildAxis || step->axis() == Step::SelfAxis))
118 newNodes.markSubtreesDisjoint(true);
119
120 for (auto& node : nodes) {
121 NodeSet matches;
122 step->evaluate(*node, matches);
123
124 if (!matches.isSorted())
125 resultIsSorted = false;
126
127 for (auto& match : matches) {
128 if (!needToCheckForDuplicateNodes || newNodesSet.add(match.get()).isNewEntry)
129 newNodes.append(match.copyRef());
130 }
131 }
132
133 nodes = WTFMove(newNodes);
134 }
135
136 nodes.markSorted(resultIsSorted);
137}
138
139void LocationPath::appendStep(std::unique_ptr<Step> step)
140{
141 unsigned stepCount = m_steps.size();
142 if (stepCount) {
143 bool dropSecondStep;
144 optimizeStepPair(*m_steps[stepCount - 1], *step, dropSecondStep);
145 if (dropSecondStep)
146 return;
147 }
148 step->optimize();
149 m_steps.append(WTFMove(step));
150}
151
152void LocationPath::prependStep(std::unique_ptr<Step> step)
153{
154 if (m_steps.size()) {
155 bool dropSecondStep;
156 optimizeStepPair(*step, *m_steps[0], dropSecondStep);
157 if (dropSecondStep) {
158 m_steps[0] = WTFMove(step);
159 return;
160 }
161 }
162 step->optimize();
163 m_steps.insert(0, WTFMove(step));
164}
165
166Path::Path(std::unique_ptr<Expression> filter, std::unique_ptr<LocationPath> path)
167 : m_filter(WTFMove(filter))
168 , m_path(WTFMove(path))
169{
170 setIsContextNodeSensitive(m_filter->isContextNodeSensitive());
171 setIsContextPositionSensitive(m_filter->isContextPositionSensitive());
172 setIsContextSizeSensitive(m_filter->isContextSizeSensitive());
173}
174
175Value Path::evaluate() const
176{
177 Value result = m_filter->evaluate();
178
179 NodeSet& nodes = result.modifiableNodeSet();
180 m_path->evaluate(nodes);
181
182 return result;
183}
184
185}
186}
187