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 "third_party/blink/renderer/core/xml/xpath_path.h"
29
30 #include "third_party/blink/renderer/core/dom/document.h"
31 #include "third_party/blink/renderer/core/dom/node_traversal.h"
32 #include "third_party/blink/renderer/core/xml/xpath_predicate.h"
33 #include "third_party/blink/renderer/core/xml/xpath_step.h"
34 #include "third_party/blink/renderer/core/xml/xpath_value.h"
35
36 namespace blink {
37 namespace xpath {
38
Filter(Expression * expr,HeapVector<Member<Predicate>> & predicates)39 Filter::Filter(Expression* expr, HeapVector<Member<Predicate>>& predicates)
40 : expr_(expr) {
41 predicates_.swap(predicates);
42 SetIsContextNodeSensitive(expr_->IsContextNodeSensitive());
43 SetIsContextPositionSensitive(expr_->IsContextPositionSensitive());
44 SetIsContextSizeSensitive(expr_->IsContextSizeSensitive());
45 }
46
47 Filter::~Filter() = default;
48
Trace(Visitor * visitor)49 void Filter::Trace(Visitor* visitor) {
50 visitor->Trace(expr_);
51 visitor->Trace(predicates_);
52 Expression::Trace(visitor);
53 }
54
Evaluate(EvaluationContext & evaluation_context) const55 Value Filter::Evaluate(EvaluationContext& evaluation_context) const {
56 Value v = expr_->Evaluate(evaluation_context);
57
58 NodeSet& nodes = v.ModifiableNodeSet(evaluation_context);
59 nodes.Sort();
60
61 for (const auto& predicate : predicates_) {
62 NodeSet* new_nodes = NodeSet::Create();
63 evaluation_context.size = nodes.size();
64 evaluation_context.position = 0;
65
66 for (const auto& node : nodes) {
67 evaluation_context.node = node;
68 ++evaluation_context.position;
69
70 if (predicate->Evaluate(evaluation_context))
71 new_nodes->Append(node);
72 }
73 nodes.Swap(*new_nodes);
74 }
75
76 return v;
77 }
78
LocationPath()79 LocationPath::LocationPath() : absolute_(false) {
80 SetIsContextNodeSensitive(true);
81 }
82
83 LocationPath::~LocationPath() = default;
84
Trace(Visitor * visitor)85 void LocationPath::Trace(Visitor* visitor) {
86 visitor->Trace(steps_);
87 Expression::Trace(visitor);
88 }
89
Evaluate(EvaluationContext & evaluation_context) const90 Value LocationPath::Evaluate(EvaluationContext& evaluation_context) const {
91 EvaluationContext cloned_context = evaluation_context;
92 // http://www.w3.org/TR/xpath/
93 // Section 2, Location Paths:
94 // "/ selects the document root (which is always the parent of the document
95 // element)"
96 // "A / by itself selects the root node of the document containing the context
97 // node."
98 // In the case of a tree that is detached from the document, we violate
99 // the spec and treat / as the root node of the detached tree.
100 // This is for compatibility with Firefox, and also seems like a more
101 // logical treatment of where you would expect the "root" to be.
102 Node* context = evaluation_context.node;
103 if (absolute_ && context->getNodeType() != Node::kDocumentNode) {
104 if (context->isConnected())
105 context = context->ownerDocument();
106 else
107 context = &NodeTraversal::HighestAncestorOrSelf(*context);
108 }
109
110 NodeSet* nodes = NodeSet::Create();
111 nodes->Append(context);
112 Evaluate(cloned_context, *nodes);
113
114 return Value(nodes, Value::kAdopt);
115 }
116
Evaluate(EvaluationContext & context,NodeSet & nodes) const117 void LocationPath::Evaluate(EvaluationContext& context, NodeSet& nodes) const {
118 bool result_is_sorted = nodes.IsSorted();
119
120 for (const auto& step : steps_) {
121 NodeSet* new_nodes = NodeSet::Create();
122 HeapHashSet<Member<Node>> new_nodes_set;
123
124 bool need_to_check_for_duplicate_nodes =
125 !nodes.SubtreesAreDisjoint() ||
126 (step->GetAxis() != Step::kChildAxis &&
127 step->GetAxis() != Step::kSelfAxis &&
128 step->GetAxis() != Step::kDescendantAxis &&
129 step->GetAxis() != Step::kDescendantOrSelfAxis &&
130 step->GetAxis() != Step::kAttributeAxis);
131
132 if (need_to_check_for_duplicate_nodes)
133 result_is_sorted = false;
134
135 // This is a simplified check that can be improved to handle more cases.
136 if (nodes.SubtreesAreDisjoint() && (step->GetAxis() == Step::kChildAxis ||
137 step->GetAxis() == Step::kSelfAxis))
138 new_nodes->MarkSubtreesDisjoint(true);
139
140 for (const auto& input_node : nodes) {
141 NodeSet* matches = NodeSet::Create();
142 step->Evaluate(context, input_node, *matches);
143
144 if (!matches->IsSorted())
145 result_is_sorted = false;
146
147 for (const auto& node : *matches) {
148 if (!need_to_check_for_duplicate_nodes ||
149 new_nodes_set.insert(node).is_new_entry)
150 new_nodes->Append(node);
151 }
152 }
153
154 nodes.Swap(*new_nodes);
155 }
156
157 nodes.MarkSorted(result_is_sorted);
158 }
159
AppendStep(Step * step)160 void LocationPath::AppendStep(Step* step) {
161 unsigned step_count = steps_.size();
162 if (step_count && OptimizeStepPair(steps_[step_count - 1], step))
163 return;
164 step->Optimize();
165 steps_.push_back(step);
166 }
167
InsertFirstStep(Step * step)168 void LocationPath::InsertFirstStep(Step* step) {
169 if (steps_.size() && OptimizeStepPair(step, steps_[0])) {
170 steps_[0] = step;
171 return;
172 }
173 step->Optimize();
174 steps_.insert(0, step);
175 }
176
Path(Expression * filter,LocationPath * path)177 Path::Path(Expression* filter, LocationPath* path)
178 : filter_(filter), path_(path) {
179 SetIsContextNodeSensitive(filter->IsContextNodeSensitive());
180 SetIsContextPositionSensitive(filter->IsContextPositionSensitive());
181 SetIsContextSizeSensitive(filter->IsContextSizeSensitive());
182 }
183
184 Path::~Path() = default;
185
Trace(Visitor * visitor)186 void Path::Trace(Visitor* visitor) {
187 visitor->Trace(filter_);
188 visitor->Trace(path_);
189 Expression::Trace(visitor);
190 }
191
Evaluate(EvaluationContext & context) const192 Value Path::Evaluate(EvaluationContext& context) const {
193 Value v = filter_->Evaluate(context);
194
195 NodeSet& nodes = v.ModifiableNodeSet(context);
196 path_->Evaluate(context, nodes);
197
198 return v;
199 }
200
201 } // namespace xpath
202
203 } // namespace blink
204