1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 /* This Source Code Form is subject to the terms of the Mozilla Public
3 * License, v. 2.0. If a copy of the MPL was not distributed with this
4 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
5
6 #include "mozilla/Assertions.h"
7 #include "txXPathOptimizer.h"
8 #include "txExprResult.h"
9 #include "nsAtom.h"
10 #include "nsGkAtoms.h"
11 #include "txXPathNode.h"
12 #include "txExpr.h"
13 #include "txIXPathContext.h"
14
15 using mozilla::UniquePtr;
16 using mozilla::Unused;
17
18 class txEarlyEvalContext : public txIEvalContext {
19 public:
txEarlyEvalContext(txResultRecycler * aRecycler)20 explicit txEarlyEvalContext(txResultRecycler* aRecycler)
21 : mRecycler(aRecycler) {}
22
23 // txIEvalContext
getVariable(int32_t aNamespace,nsAtom * aLName,txAExprResult * & aResult)24 nsresult getVariable(int32_t aNamespace, nsAtom* aLName,
25 txAExprResult*& aResult) override {
26 MOZ_CRASH("shouldn't depend on this context");
27 }
isStripSpaceAllowed(const txXPathNode & aNode,bool & aAllowed)28 nsresult isStripSpaceAllowed(const txXPathNode& aNode,
29 bool& aAllowed) override {
30 MOZ_CRASH("shouldn't depend on this context");
31 }
getPrivateContext()32 void* getPrivateContext() override {
33 MOZ_CRASH("shouldn't depend on this context");
34 }
recycler()35 txResultRecycler* recycler() override { return mRecycler; }
receiveError(const nsAString & aMsg,nsresult aRes)36 void receiveError(const nsAString& aMsg, nsresult aRes) override {}
getContextNode()37 const txXPathNode& getContextNode() override {
38 MOZ_CRASH("shouldn't depend on this context");
39 }
size()40 uint32_t size() override { MOZ_CRASH("shouldn't depend on this context"); }
position()41 uint32_t position() override {
42 MOZ_CRASH("shouldn't depend on this context");
43 }
44
45 private:
46 txResultRecycler* mRecycler;
47 };
48
optimize(Expr * aInExpr,Expr ** aOutExpr)49 nsresult txXPathOptimizer::optimize(Expr* aInExpr, Expr** aOutExpr) {
50 *aOutExpr = nullptr;
51 nsresult rv = NS_OK;
52
53 // First check if the expression will produce the same result
54 // under any context.
55 Expr::ExprType exprType = aInExpr->getType();
56 if (exprType != Expr::LITERAL_EXPR &&
57 !aInExpr->isSensitiveTo(Expr::ANY_CONTEXT)) {
58 RefPtr<txResultRecycler> recycler = new txResultRecycler;
59 txEarlyEvalContext context(recycler);
60 RefPtr<txAExprResult> exprRes;
61
62 // Don't throw if this fails since it could be that the expression
63 // is or contains an error-expression.
64 rv = aInExpr->evaluate(&context, getter_AddRefs(exprRes));
65 if (NS_SUCCEEDED(rv)) {
66 *aOutExpr = new txLiteralExpr(exprRes);
67 }
68
69 return NS_OK;
70 }
71
72 // Then optimize sub expressions
73 uint32_t i = 0;
74 Expr* subExpr;
75 while ((subExpr = aInExpr->getSubExprAt(i))) {
76 Expr* newExpr = nullptr;
77 rv = optimize(subExpr, &newExpr);
78 NS_ENSURE_SUCCESS(rv, rv);
79 if (newExpr) {
80 delete subExpr;
81 aInExpr->setSubExprAt(i, newExpr);
82 }
83
84 ++i;
85 }
86
87 // Finally see if current expression can be optimized
88 switch (exprType) {
89 case Expr::LOCATIONSTEP_EXPR:
90 return optimizeStep(aInExpr, aOutExpr);
91
92 case Expr::PATH_EXPR:
93 return optimizePath(aInExpr, aOutExpr);
94
95 case Expr::UNION_EXPR:
96 return optimizeUnion(aInExpr, aOutExpr);
97
98 default:
99 break;
100 }
101
102 return NS_OK;
103 }
104
optimizeStep(Expr * aInExpr,Expr ** aOutExpr)105 nsresult txXPathOptimizer::optimizeStep(Expr* aInExpr, Expr** aOutExpr) {
106 LocationStep* step = static_cast<LocationStep*>(aInExpr);
107
108 if (step->getAxisIdentifier() == LocationStep::ATTRIBUTE_AXIS) {
109 // Test for @foo type steps.
110 txNameTest* nameTest = nullptr;
111 if (!step->getSubExprAt(0) &&
112 step->getNodeTest()->getType() == txNameTest::NAME_TEST &&
113 (nameTest = static_cast<txNameTest*>(step->getNodeTest()))
114 ->mLocalName != nsGkAtoms::_asterisk) {
115 *aOutExpr = new txNamedAttributeStep(
116 nameTest->mNamespace, nameTest->mPrefix, nameTest->mLocalName);
117 return NS_OK; // return since we no longer have a step-object.
118 }
119 }
120
121 // Test for predicates that can be combined into the nodetest
122 Expr* pred;
123 while ((pred = step->getSubExprAt(0)) &&
124 !pred->canReturnType(Expr::NUMBER_RESULT) &&
125 !pred->isSensitiveTo(Expr::NODESET_CONTEXT)) {
126 txNodeTest* predTest = new txPredicatedNodeTest(step->getNodeTest(), pred);
127 step->dropFirst();
128 step->setNodeTest(predTest);
129 }
130
131 return NS_OK;
132 }
133
optimizePath(Expr * aInExpr,Expr ** aOutExpr)134 nsresult txXPathOptimizer::optimizePath(Expr* aInExpr, Expr** aOutExpr) {
135 PathExpr* path = static_cast<PathExpr*>(aInExpr);
136
137 uint32_t i;
138 Expr* subExpr;
139 // look for steps like "//foo" that can be turned into "/descendant::foo"
140 // and "//." that can be turned into "/descendant-or-self::node()"
141 for (i = 0; (subExpr = path->getSubExprAt(i)); ++i) {
142 if (path->getPathOpAt(i) == PathExpr::DESCENDANT_OP &&
143 subExpr->getType() == Expr::LOCATIONSTEP_EXPR &&
144 !subExpr->getSubExprAt(0)) {
145 LocationStep* step = static_cast<LocationStep*>(subExpr);
146 if (step->getAxisIdentifier() == LocationStep::CHILD_AXIS) {
147 step->setAxisIdentifier(LocationStep::DESCENDANT_AXIS);
148 path->setPathOpAt(i, PathExpr::RELATIVE_OP);
149 } else if (step->getAxisIdentifier() == LocationStep::SELF_AXIS) {
150 step->setAxisIdentifier(LocationStep::DESCENDANT_OR_SELF_AXIS);
151 path->setPathOpAt(i, PathExpr::RELATIVE_OP);
152 }
153 }
154 }
155
156 // look for expressions that start with a "./"
157 subExpr = path->getSubExprAt(0);
158 LocationStep* step;
159 if (subExpr->getType() == Expr::LOCATIONSTEP_EXPR && path->getSubExprAt(1) &&
160 path->getPathOpAt(1) != PathExpr::DESCENDANT_OP) {
161 step = static_cast<LocationStep*>(subExpr);
162 if (step->getAxisIdentifier() == LocationStep::SELF_AXIS &&
163 !step->getSubExprAt(0)) {
164 txNodeTest* test = step->getNodeTest();
165 if (test->getType() == txNodeTest::NODETYPE_TEST &&
166 (static_cast<txNodeTypeTest*>(test))->getNodeTestType() ==
167 txNodeTypeTest::NODE_TYPE) {
168 // We have a '.' as first step followed by a single '/'.
169
170 // Check if there are only two steps. If so, return the second
171 // as resulting expression.
172 if (!path->getSubExprAt(2)) {
173 *aOutExpr = path->getSubExprAt(1);
174 path->setSubExprAt(1, nullptr);
175
176 return NS_OK;
177 }
178
179 // Just delete the '.' step and leave the rest of the PathExpr
180 path->deleteExprAt(0);
181 }
182 }
183 }
184
185 return NS_OK;
186 }
187
optimizeUnion(Expr * aInExpr,Expr ** aOutExpr)188 nsresult txXPathOptimizer::optimizeUnion(Expr* aInExpr, Expr** aOutExpr) {
189 UnionExpr* uni = static_cast<UnionExpr*>(aInExpr);
190
191 // Check for expressions like "foo | bar" and
192 // "descendant::foo | descendant::bar"
193
194 nsresult rv;
195 uint32_t current;
196 Expr* subExpr;
197 for (current = 0; (subExpr = uni->getSubExprAt(current)); ++current) {
198 if (subExpr->getType() != Expr::LOCATIONSTEP_EXPR ||
199 subExpr->getSubExprAt(0)) {
200 continue;
201 }
202
203 LocationStep* currentStep = static_cast<LocationStep*>(subExpr);
204 LocationStep::LocationStepType axis = currentStep->getAxisIdentifier();
205
206 txUnionNodeTest* unionTest = nullptr;
207
208 // Check if there are any other steps with the same axis and merge
209 // them with currentStep
210 uint32_t i;
211 for (i = current + 1; (subExpr = uni->getSubExprAt(i)); ++i) {
212 if (subExpr->getType() != Expr::LOCATIONSTEP_EXPR ||
213 subExpr->getSubExprAt(0)) {
214 continue;
215 }
216
217 LocationStep* step = static_cast<LocationStep*>(subExpr);
218 if (step->getAxisIdentifier() != axis) {
219 continue;
220 }
221
222 // Create a txUnionNodeTest if needed
223 if (!unionTest) {
224 UniquePtr<txNodeTest> owner(unionTest = new txUnionNodeTest);
225 rv = unionTest->addNodeTest(currentStep->getNodeTest());
226 NS_ENSURE_SUCCESS(rv, rv);
227
228 currentStep->setNodeTest(unionTest);
229 Unused << owner.release();
230 }
231
232 // Merge the nodetest into the union
233 rv = unionTest->addNodeTest(step->getNodeTest());
234 NS_ENSURE_SUCCESS(rv, rv);
235
236 step->setNodeTest(nullptr);
237
238 // Remove the step from the UnionExpr
239 uni->deleteExprAt(i);
240 --i;
241 }
242
243 // Check if all expressions were merged into a single step. If so,
244 // return the step as the new expression.
245 if (unionTest && current == 0 && !uni->getSubExprAt(1)) {
246 // Make sure the step doesn't get deleted when the UnionExpr is
247 uni->setSubExprAt(0, nullptr);
248 *aOutExpr = currentStep;
249
250 // Return right away since we no longer have a union
251 return NS_OK;
252 }
253 }
254
255 return NS_OK;
256 }
257