michael@0: /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
michael@0: /* This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: #include "txXPathOptimizer.h"
michael@0: #include "txExprResult.h"
michael@0: #include "nsIAtom.h"
michael@0: #include "nsGkAtoms.h"
michael@0: #include "txXPathNode.h"
michael@0: #include "txExpr.h"
michael@0: #include "txIXPathContext.h"
michael@0: 
michael@0: class txEarlyEvalContext : public txIEvalContext
michael@0: {
michael@0: public:
michael@0:     txEarlyEvalContext(txResultRecycler* aRecycler)
michael@0:         : mRecycler(aRecycler)
michael@0:     {
michael@0:     }
michael@0: 
michael@0:     // txIEvalContext
michael@0:     nsresult getVariable(int32_t aNamespace, nsIAtom* aLName,
michael@0:                          txAExprResult*& aResult)
michael@0:     {
michael@0:         NS_NOTREACHED("shouldn't depend on this context");
michael@0:         return NS_ERROR_FAILURE;
michael@0:     }
michael@0:     bool isStripSpaceAllowed(const txXPathNode& aNode)
michael@0:     {
michael@0:         NS_NOTREACHED("shouldn't depend on this context");
michael@0:         return false;
michael@0:     }
michael@0:     void* getPrivateContext()
michael@0:     {
michael@0:         NS_NOTREACHED("shouldn't depend on this context");
michael@0:         return nullptr;
michael@0:     }
michael@0:     txResultRecycler* recycler()
michael@0:     {
michael@0:         return mRecycler;
michael@0:     }
michael@0:     void receiveError(const nsAString& aMsg, nsresult aRes)
michael@0:     {
michael@0:     }
michael@0:     const txXPathNode& getContextNode()
michael@0:     {
michael@0:         NS_NOTREACHED("shouldn't depend on this context");
michael@0: 
michael@0:         // This will return an invalid node, but we should never
michael@0:         // get here so that's fine.
michael@0: 
michael@0:         return *static_cast<txXPathNode*>(nullptr);
michael@0:     }
michael@0:     uint32_t size()
michael@0:     {
michael@0:         NS_NOTREACHED("shouldn't depend on this context");
michael@0:         return 1;
michael@0:     }
michael@0:     uint32_t position()
michael@0:     {
michael@0:         NS_NOTREACHED("shouldn't depend on this context");
michael@0:         return 1;
michael@0:     }
michael@0: 
michael@0: private:
michael@0:     txResultRecycler* mRecycler;
michael@0: };
michael@0: 
michael@0: 
michael@0: nsresult
michael@0: txXPathOptimizer::optimize(Expr* aInExpr, Expr** aOutExpr)
michael@0: {
michael@0:     *aOutExpr = nullptr;
michael@0:     nsresult rv = NS_OK;
michael@0: 
michael@0:     // First check if the expression will produce the same result
michael@0:     // under any context.
michael@0:     Expr::ExprType exprType = aInExpr->getType();
michael@0:     if (exprType != Expr::LITERAL_EXPR &&
michael@0:         !aInExpr->isSensitiveTo(Expr::ANY_CONTEXT)) {
michael@0:         nsRefPtr<txResultRecycler> recycler = new txResultRecycler;
michael@0:         NS_ENSURE_TRUE(recycler, NS_ERROR_OUT_OF_MEMORY);
michael@0: 
michael@0:         rv = recycler->init();
michael@0:         NS_ENSURE_SUCCESS(rv, rv);
michael@0: 
michael@0:         txEarlyEvalContext context(recycler);
michael@0:         nsRefPtr<txAExprResult> exprRes;
michael@0: 
michael@0:         // Don't throw if this fails since it could be that the expression
michael@0:         // is or contains an error-expression.
michael@0:         rv = aInExpr->evaluate(&context, getter_AddRefs(exprRes));
michael@0:         if (NS_SUCCEEDED(rv)) {
michael@0:             *aOutExpr = new txLiteralExpr(exprRes);
michael@0:         }
michael@0:         
michael@0:         return NS_OK;
michael@0:     }
michael@0: 
michael@0:     // Then optimize sub expressions
michael@0:     uint32_t i = 0;
michael@0:     Expr* subExpr;
michael@0:     while ((subExpr = aInExpr->getSubExprAt(i))) {
michael@0:         Expr* newExpr = nullptr;
michael@0:         rv = optimize(subExpr, &newExpr);
michael@0:         NS_ENSURE_SUCCESS(rv, rv);
michael@0:         if (newExpr) {
michael@0:             delete subExpr;
michael@0:             aInExpr->setSubExprAt(i, newExpr);
michael@0:         }
michael@0: 
michael@0:         ++i;
michael@0:     }
michael@0: 
michael@0:     // Finally see if current expression can be optimized
michael@0:     switch (exprType) {
michael@0:         case Expr::LOCATIONSTEP_EXPR:
michael@0:             return optimizeStep(aInExpr, aOutExpr);
michael@0: 
michael@0:         case Expr::PATH_EXPR:
michael@0:             return optimizePath(aInExpr, aOutExpr);
michael@0: 
michael@0:         case Expr::UNION_EXPR:
michael@0:             return optimizeUnion(aInExpr, aOutExpr);
michael@0: 
michael@0:         default:
michael@0:             break;
michael@0:     }
michael@0: 
michael@0:     return NS_OK;
michael@0: }
michael@0: 
michael@0: nsresult
michael@0: txXPathOptimizer::optimizeStep(Expr* aInExpr, Expr** aOutExpr)
michael@0: {
michael@0:     LocationStep* step = static_cast<LocationStep*>(aInExpr);
michael@0: 
michael@0:     if (step->getAxisIdentifier() == LocationStep::ATTRIBUTE_AXIS) {
michael@0:         // Test for @foo type steps.
michael@0:         txNameTest* nameTest = nullptr;
michael@0:         if (!step->getSubExprAt(0) &&
michael@0:             step->getNodeTest()->getType() == txNameTest::NAME_TEST &&
michael@0:             (nameTest = static_cast<txNameTest*>(step->getNodeTest()))->
michael@0:                 mLocalName != nsGkAtoms::_asterix) {
michael@0: 
michael@0:             *aOutExpr = new txNamedAttributeStep(nameTest->mNamespace,
michael@0:                                                  nameTest->mPrefix,
michael@0:                                                  nameTest->mLocalName);
michael@0:             NS_ENSURE_TRUE(*aOutExpr, NS_ERROR_OUT_OF_MEMORY);
michael@0: 
michael@0:             return NS_OK; // return since we no longer have a step-object.
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     // Test for predicates that can be combined into the nodetest
michael@0:     Expr* pred;
michael@0:     while ((pred = step->getSubExprAt(0)) &&
michael@0:            !pred->canReturnType(Expr::NUMBER_RESULT) &&
michael@0:            !pred->isSensitiveTo(Expr::NODESET_CONTEXT)) {
michael@0:         txNodeTest* predTest = new txPredicatedNodeTest(step->getNodeTest(), pred);
michael@0:         NS_ENSURE_TRUE(predTest, NS_ERROR_OUT_OF_MEMORY);
michael@0: 
michael@0:         step->dropFirst();
michael@0:         step->setNodeTest(predTest);
michael@0:     }
michael@0: 
michael@0:     return NS_OK;
michael@0: }
michael@0: 
michael@0: nsresult
michael@0: txXPathOptimizer::optimizePath(Expr* aInExpr, Expr** aOutExpr)
michael@0: {
michael@0:     PathExpr* path = static_cast<PathExpr*>(aInExpr);
michael@0: 
michael@0:     uint32_t i;
michael@0:     Expr* subExpr;
michael@0:     // look for steps like "//foo" that can be turned into "/descendant::foo"
michael@0:     // and "//." that can be turned into "/descendant-or-self::node()"
michael@0:     for (i = 0; (subExpr = path->getSubExprAt(i)); ++i) {
michael@0:         if (path->getPathOpAt(i) == PathExpr::DESCENDANT_OP &&
michael@0:             subExpr->getType() == Expr::LOCATIONSTEP_EXPR &&
michael@0:             !subExpr->getSubExprAt(0)) {
michael@0:             LocationStep* step = static_cast<LocationStep*>(subExpr);
michael@0:             if (step->getAxisIdentifier() == LocationStep::CHILD_AXIS) {
michael@0:                 step->setAxisIdentifier(LocationStep::DESCENDANT_AXIS);
michael@0:                 path->setPathOpAt(i, PathExpr::RELATIVE_OP);
michael@0:             }
michael@0:             else if (step->getAxisIdentifier() == LocationStep::SELF_AXIS) {
michael@0:                 step->setAxisIdentifier(LocationStep::DESCENDANT_OR_SELF_AXIS);
michael@0:                 path->setPathOpAt(i, PathExpr::RELATIVE_OP);
michael@0:             }
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     // look for expressions that start with a "./"
michael@0:     subExpr = path->getSubExprAt(0);
michael@0:     LocationStep* step;
michael@0:     if (subExpr->getType() == Expr::LOCATIONSTEP_EXPR &&
michael@0:         path->getSubExprAt(1) &&
michael@0:         path->getPathOpAt(1) != PathExpr::DESCENDANT_OP) {
michael@0:         step = static_cast<LocationStep*>(subExpr);
michael@0:         if (step->getAxisIdentifier() == LocationStep::SELF_AXIS &&
michael@0:             !step->getSubExprAt(0)) {
michael@0:             txNodeTest* test = step->getNodeTest();
michael@0:             txNodeTypeTest* typeTest;
michael@0:             if (test->getType() == txNodeTest::NODETYPE_TEST &&
michael@0:                 (typeTest = static_cast<txNodeTypeTest*>(test))->
michael@0:                   getNodeTestType() == txNodeTypeTest::NODE_TYPE) {
michael@0:                 // We have a '.' as first step followed by a single '/'.
michael@0: 
michael@0:                 // Check if there are only two steps. If so, return the second
michael@0:                 // as resulting expression.
michael@0:                 if (!path->getSubExprAt(2)) {
michael@0:                     *aOutExpr = path->getSubExprAt(1);
michael@0:                     path->setSubExprAt(1, nullptr);
michael@0: 
michael@0:                     return NS_OK;
michael@0:                 }
michael@0: 
michael@0:                 // Just delete the '.' step and leave the rest of the PathExpr
michael@0:                 path->deleteExprAt(0);
michael@0:             }
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     return NS_OK;
michael@0: }
michael@0: 
michael@0: nsresult
michael@0: txXPathOptimizer::optimizeUnion(Expr* aInExpr, Expr** aOutExpr)
michael@0: {
michael@0:     UnionExpr* uni = static_cast<UnionExpr*>(aInExpr);
michael@0: 
michael@0:     // Check for expressions like "foo | bar" and
michael@0:     // "descendant::foo | descendant::bar"
michael@0: 
michael@0:     nsresult rv;
michael@0:     uint32_t current;
michael@0:     Expr* subExpr;
michael@0:     for (current = 0; (subExpr = uni->getSubExprAt(current)); ++current) {
michael@0:         if (subExpr->getType() != Expr::LOCATIONSTEP_EXPR ||
michael@0:             subExpr->getSubExprAt(0)) {
michael@0:             continue;
michael@0:         }
michael@0: 
michael@0:         LocationStep* currentStep = static_cast<LocationStep*>(subExpr);
michael@0:         LocationStep::LocationStepType axis = currentStep->getAxisIdentifier();
michael@0: 
michael@0:         txUnionNodeTest* unionTest = nullptr;
michael@0: 
michael@0:         // Check if there are any other steps with the same axis and merge
michael@0:         // them with currentStep
michael@0:         uint32_t i;
michael@0:         for (i = current + 1; (subExpr = uni->getSubExprAt(i)); ++i) {
michael@0:             if (subExpr->getType() != Expr::LOCATIONSTEP_EXPR ||
michael@0:                 subExpr->getSubExprAt(0)) {
michael@0:                 continue;
michael@0:             }
michael@0: 
michael@0:             LocationStep* step = static_cast<LocationStep*>(subExpr);
michael@0:             if (step->getAxisIdentifier() != axis) {
michael@0:                 continue;
michael@0:             }
michael@0:             
michael@0:             // Create a txUnionNodeTest if needed
michael@0:             if (!unionTest) {
michael@0:                 nsAutoPtr<txNodeTest> owner(unionTest = new txUnionNodeTest);
michael@0:                 NS_ENSURE_TRUE(unionTest, NS_ERROR_OUT_OF_MEMORY);
michael@0:                 
michael@0:                 rv = unionTest->addNodeTest(currentStep->getNodeTest());
michael@0:                 NS_ENSURE_SUCCESS(rv, rv);
michael@0: 
michael@0:                 currentStep->setNodeTest(unionTest);
michael@0:                 owner.forget();
michael@0:             }
michael@0: 
michael@0:             // Merge the nodetest into the union
michael@0:             rv = unionTest->addNodeTest(step->getNodeTest());
michael@0:             NS_ENSURE_SUCCESS(rv, rv);
michael@0: 
michael@0:             step->setNodeTest(nullptr);
michael@0: 
michael@0:             // Remove the step from the UnionExpr
michael@0:             uni->deleteExprAt(i);
michael@0:             --i;
michael@0:         }
michael@0: 
michael@0:         // Check if all expressions were merged into a single step. If so,
michael@0:         // return the step as the new expression.
michael@0:         if (unionTest && current == 0 && !uni->getSubExprAt(1)) {
michael@0:             // Make sure the step doesn't get deleted when the UnionExpr is
michael@0:             uni->setSubExprAt(0, nullptr);
michael@0:             *aOutExpr = currentStep;
michael@0: 
michael@0:             // Return right away since we no longer have a union            
michael@0:             return NS_OK;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     return NS_OK;
michael@0: }