dom/xslt/xpath/txXPathOptimizer.cpp

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