1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/dom/xslt/xpath/txXPathOptimizer.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,302 @@
1.4 +/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
1.5 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.6 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.7 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.8 +
1.9 +#include "txXPathOptimizer.h"
1.10 +#include "txExprResult.h"
1.11 +#include "nsIAtom.h"
1.12 +#include "nsGkAtoms.h"
1.13 +#include "txXPathNode.h"
1.14 +#include "txExpr.h"
1.15 +#include "txIXPathContext.h"
1.16 +
1.17 +class txEarlyEvalContext : public txIEvalContext
1.18 +{
1.19 +public:
1.20 + txEarlyEvalContext(txResultRecycler* aRecycler)
1.21 + : mRecycler(aRecycler)
1.22 + {
1.23 + }
1.24 +
1.25 + // txIEvalContext
1.26 + nsresult getVariable(int32_t aNamespace, nsIAtom* aLName,
1.27 + txAExprResult*& aResult)
1.28 + {
1.29 + NS_NOTREACHED("shouldn't depend on this context");
1.30 + return NS_ERROR_FAILURE;
1.31 + }
1.32 + bool isStripSpaceAllowed(const txXPathNode& aNode)
1.33 + {
1.34 + NS_NOTREACHED("shouldn't depend on this context");
1.35 + return false;
1.36 + }
1.37 + void* getPrivateContext()
1.38 + {
1.39 + NS_NOTREACHED("shouldn't depend on this context");
1.40 + return nullptr;
1.41 + }
1.42 + txResultRecycler* recycler()
1.43 + {
1.44 + return mRecycler;
1.45 + }
1.46 + void receiveError(const nsAString& aMsg, nsresult aRes)
1.47 + {
1.48 + }
1.49 + const txXPathNode& getContextNode()
1.50 + {
1.51 + NS_NOTREACHED("shouldn't depend on this context");
1.52 +
1.53 + // This will return an invalid node, but we should never
1.54 + // get here so that's fine.
1.55 +
1.56 + return *static_cast<txXPathNode*>(nullptr);
1.57 + }
1.58 + uint32_t size()
1.59 + {
1.60 + NS_NOTREACHED("shouldn't depend on this context");
1.61 + return 1;
1.62 + }
1.63 + uint32_t position()
1.64 + {
1.65 + NS_NOTREACHED("shouldn't depend on this context");
1.66 + return 1;
1.67 + }
1.68 +
1.69 +private:
1.70 + txResultRecycler* mRecycler;
1.71 +};
1.72 +
1.73 +
1.74 +nsresult
1.75 +txXPathOptimizer::optimize(Expr* aInExpr, Expr** aOutExpr)
1.76 +{
1.77 + *aOutExpr = nullptr;
1.78 + nsresult rv = NS_OK;
1.79 +
1.80 + // First check if the expression will produce the same result
1.81 + // under any context.
1.82 + Expr::ExprType exprType = aInExpr->getType();
1.83 + if (exprType != Expr::LITERAL_EXPR &&
1.84 + !aInExpr->isSensitiveTo(Expr::ANY_CONTEXT)) {
1.85 + nsRefPtr<txResultRecycler> recycler = new txResultRecycler;
1.86 + NS_ENSURE_TRUE(recycler, NS_ERROR_OUT_OF_MEMORY);
1.87 +
1.88 + rv = recycler->init();
1.89 + NS_ENSURE_SUCCESS(rv, rv);
1.90 +
1.91 + txEarlyEvalContext context(recycler);
1.92 + nsRefPtr<txAExprResult> exprRes;
1.93 +
1.94 + // Don't throw if this fails since it could be that the expression
1.95 + // is or contains an error-expression.
1.96 + rv = aInExpr->evaluate(&context, getter_AddRefs(exprRes));
1.97 + if (NS_SUCCEEDED(rv)) {
1.98 + *aOutExpr = new txLiteralExpr(exprRes);
1.99 + }
1.100 +
1.101 + return NS_OK;
1.102 + }
1.103 +
1.104 + // Then optimize sub expressions
1.105 + uint32_t i = 0;
1.106 + Expr* subExpr;
1.107 + while ((subExpr = aInExpr->getSubExprAt(i))) {
1.108 + Expr* newExpr = nullptr;
1.109 + rv = optimize(subExpr, &newExpr);
1.110 + NS_ENSURE_SUCCESS(rv, rv);
1.111 + if (newExpr) {
1.112 + delete subExpr;
1.113 + aInExpr->setSubExprAt(i, newExpr);
1.114 + }
1.115 +
1.116 + ++i;
1.117 + }
1.118 +
1.119 + // Finally see if current expression can be optimized
1.120 + switch (exprType) {
1.121 + case Expr::LOCATIONSTEP_EXPR:
1.122 + return optimizeStep(aInExpr, aOutExpr);
1.123 +
1.124 + case Expr::PATH_EXPR:
1.125 + return optimizePath(aInExpr, aOutExpr);
1.126 +
1.127 + case Expr::UNION_EXPR:
1.128 + return optimizeUnion(aInExpr, aOutExpr);
1.129 +
1.130 + default:
1.131 + break;
1.132 + }
1.133 +
1.134 + return NS_OK;
1.135 +}
1.136 +
1.137 +nsresult
1.138 +txXPathOptimizer::optimizeStep(Expr* aInExpr, Expr** aOutExpr)
1.139 +{
1.140 + LocationStep* step = static_cast<LocationStep*>(aInExpr);
1.141 +
1.142 + if (step->getAxisIdentifier() == LocationStep::ATTRIBUTE_AXIS) {
1.143 + // Test for @foo type steps.
1.144 + txNameTest* nameTest = nullptr;
1.145 + if (!step->getSubExprAt(0) &&
1.146 + step->getNodeTest()->getType() == txNameTest::NAME_TEST &&
1.147 + (nameTest = static_cast<txNameTest*>(step->getNodeTest()))->
1.148 + mLocalName != nsGkAtoms::_asterix) {
1.149 +
1.150 + *aOutExpr = new txNamedAttributeStep(nameTest->mNamespace,
1.151 + nameTest->mPrefix,
1.152 + nameTest->mLocalName);
1.153 + NS_ENSURE_TRUE(*aOutExpr, NS_ERROR_OUT_OF_MEMORY);
1.154 +
1.155 + return NS_OK; // return since we no longer have a step-object.
1.156 + }
1.157 + }
1.158 +
1.159 + // Test for predicates that can be combined into the nodetest
1.160 + Expr* pred;
1.161 + while ((pred = step->getSubExprAt(0)) &&
1.162 + !pred->canReturnType(Expr::NUMBER_RESULT) &&
1.163 + !pred->isSensitiveTo(Expr::NODESET_CONTEXT)) {
1.164 + txNodeTest* predTest = new txPredicatedNodeTest(step->getNodeTest(), pred);
1.165 + NS_ENSURE_TRUE(predTest, NS_ERROR_OUT_OF_MEMORY);
1.166 +
1.167 + step->dropFirst();
1.168 + step->setNodeTest(predTest);
1.169 + }
1.170 +
1.171 + return NS_OK;
1.172 +}
1.173 +
1.174 +nsresult
1.175 +txXPathOptimizer::optimizePath(Expr* aInExpr, Expr** aOutExpr)
1.176 +{
1.177 + PathExpr* path = static_cast<PathExpr*>(aInExpr);
1.178 +
1.179 + uint32_t i;
1.180 + Expr* subExpr;
1.181 + // look for steps like "//foo" that can be turned into "/descendant::foo"
1.182 + // and "//." that can be turned into "/descendant-or-self::node()"
1.183 + for (i = 0; (subExpr = path->getSubExprAt(i)); ++i) {
1.184 + if (path->getPathOpAt(i) == PathExpr::DESCENDANT_OP &&
1.185 + subExpr->getType() == Expr::LOCATIONSTEP_EXPR &&
1.186 + !subExpr->getSubExprAt(0)) {
1.187 + LocationStep* step = static_cast<LocationStep*>(subExpr);
1.188 + if (step->getAxisIdentifier() == LocationStep::CHILD_AXIS) {
1.189 + step->setAxisIdentifier(LocationStep::DESCENDANT_AXIS);
1.190 + path->setPathOpAt(i, PathExpr::RELATIVE_OP);
1.191 + }
1.192 + else if (step->getAxisIdentifier() == LocationStep::SELF_AXIS) {
1.193 + step->setAxisIdentifier(LocationStep::DESCENDANT_OR_SELF_AXIS);
1.194 + path->setPathOpAt(i, PathExpr::RELATIVE_OP);
1.195 + }
1.196 + }
1.197 + }
1.198 +
1.199 + // look for expressions that start with a "./"
1.200 + subExpr = path->getSubExprAt(0);
1.201 + LocationStep* step;
1.202 + if (subExpr->getType() == Expr::LOCATIONSTEP_EXPR &&
1.203 + path->getSubExprAt(1) &&
1.204 + path->getPathOpAt(1) != PathExpr::DESCENDANT_OP) {
1.205 + step = static_cast<LocationStep*>(subExpr);
1.206 + if (step->getAxisIdentifier() == LocationStep::SELF_AXIS &&
1.207 + !step->getSubExprAt(0)) {
1.208 + txNodeTest* test = step->getNodeTest();
1.209 + txNodeTypeTest* typeTest;
1.210 + if (test->getType() == txNodeTest::NODETYPE_TEST &&
1.211 + (typeTest = static_cast<txNodeTypeTest*>(test))->
1.212 + getNodeTestType() == txNodeTypeTest::NODE_TYPE) {
1.213 + // We have a '.' as first step followed by a single '/'.
1.214 +
1.215 + // Check if there are only two steps. If so, return the second
1.216 + // as resulting expression.
1.217 + if (!path->getSubExprAt(2)) {
1.218 + *aOutExpr = path->getSubExprAt(1);
1.219 + path->setSubExprAt(1, nullptr);
1.220 +
1.221 + return NS_OK;
1.222 + }
1.223 +
1.224 + // Just delete the '.' step and leave the rest of the PathExpr
1.225 + path->deleteExprAt(0);
1.226 + }
1.227 + }
1.228 + }
1.229 +
1.230 + return NS_OK;
1.231 +}
1.232 +
1.233 +nsresult
1.234 +txXPathOptimizer::optimizeUnion(Expr* aInExpr, Expr** aOutExpr)
1.235 +{
1.236 + UnionExpr* uni = static_cast<UnionExpr*>(aInExpr);
1.237 +
1.238 + // Check for expressions like "foo | bar" and
1.239 + // "descendant::foo | descendant::bar"
1.240 +
1.241 + nsresult rv;
1.242 + uint32_t current;
1.243 + Expr* subExpr;
1.244 + for (current = 0; (subExpr = uni->getSubExprAt(current)); ++current) {
1.245 + if (subExpr->getType() != Expr::LOCATIONSTEP_EXPR ||
1.246 + subExpr->getSubExprAt(0)) {
1.247 + continue;
1.248 + }
1.249 +
1.250 + LocationStep* currentStep = static_cast<LocationStep*>(subExpr);
1.251 + LocationStep::LocationStepType axis = currentStep->getAxisIdentifier();
1.252 +
1.253 + txUnionNodeTest* unionTest = nullptr;
1.254 +
1.255 + // Check if there are any other steps with the same axis and merge
1.256 + // them with currentStep
1.257 + uint32_t i;
1.258 + for (i = current + 1; (subExpr = uni->getSubExprAt(i)); ++i) {
1.259 + if (subExpr->getType() != Expr::LOCATIONSTEP_EXPR ||
1.260 + subExpr->getSubExprAt(0)) {
1.261 + continue;
1.262 + }
1.263 +
1.264 + LocationStep* step = static_cast<LocationStep*>(subExpr);
1.265 + if (step->getAxisIdentifier() != axis) {
1.266 + continue;
1.267 + }
1.268 +
1.269 + // Create a txUnionNodeTest if needed
1.270 + if (!unionTest) {
1.271 + nsAutoPtr<txNodeTest> owner(unionTest = new txUnionNodeTest);
1.272 + NS_ENSURE_TRUE(unionTest, NS_ERROR_OUT_OF_MEMORY);
1.273 +
1.274 + rv = unionTest->addNodeTest(currentStep->getNodeTest());
1.275 + NS_ENSURE_SUCCESS(rv, rv);
1.276 +
1.277 + currentStep->setNodeTest(unionTest);
1.278 + owner.forget();
1.279 + }
1.280 +
1.281 + // Merge the nodetest into the union
1.282 + rv = unionTest->addNodeTest(step->getNodeTest());
1.283 + NS_ENSURE_SUCCESS(rv, rv);
1.284 +
1.285 + step->setNodeTest(nullptr);
1.286 +
1.287 + // Remove the step from the UnionExpr
1.288 + uni->deleteExprAt(i);
1.289 + --i;
1.290 + }
1.291 +
1.292 + // Check if all expressions were merged into a single step. If so,
1.293 + // return the step as the new expression.
1.294 + if (unionTest && current == 0 && !uni->getSubExprAt(1)) {
1.295 + // Make sure the step doesn't get deleted when the UnionExpr is
1.296 + uni->setSubExprAt(0, nullptr);
1.297 + *aOutExpr = currentStep;
1.298 +
1.299 + // Return right away since we no longer have a union
1.300 + return NS_OK;
1.301 + }
1.302 + }
1.303 +
1.304 + return NS_OK;
1.305 +}
