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