/****************************************************************************

**

** Copyright (C) 2010 Nokia Corporation and/or its subsidiary(-ies).

** All rights reserved.

** Contact: Nokia Corporation (qt-info@nokia.com)

**

** This file is part of the QtXmlPatterns module of the Qt Toolkit.

**

** $QT_BEGIN_LICENSE:LGPL$

** No Commercial Usage

** This file contains pre-release code and may not be distributed.

** You may use this file in accordance with the terms and conditions

** contained in the Technology Preview License Agreement accompanying

** this package.

**

** GNU Lesser General Public License Usage

** Alternatively, this file may be used under the terms of the GNU Lesser

** General Public License version 2.1 as published by the Free Software

** Foundation and appearing in the file LICENSE.LGPL included in the

** packaging of this file.  Please review the following information to

** ensure the GNU Lesser General Public License version 2.1 requirements

** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.

**

** In addition, as a special exception, Nokia gives you certain additional

** rights.  These rights are described in the Nokia Qt LGPL Exception

** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.

**

** If you have questions regarding the use of this file, please contact

** Nokia at qt-info@nokia.com.

**

**

**

**

**

**

**

**

** $QT_END_LICENSE$

**

****************************************************************************/

//

//  W A R N I N G

//  -------------

//

// This file is not part of the Qt API.  It exists purely as an

// implementation detail.  This header file may change from version to

// version without notice, or even be removed.

//

// We mean it.

#ifndef Patternist_Expression_H

#define Patternist_Expression_H

#include <QFlags>

#include <QSharedData>

#include "qcppcastinghelper_p.h"

#include "qdebug_p.h"

#include "qdynamiccontext_p.h"

#include "qexpressiondispatch_p.h"

#include "qitem_p.h"

#include "qsequencetype_p.h"

#include "qsourcelocationreflection_p.h"

#include "qstaticcontext_p.h"

QT_BEGIN_HEADER

QT_BEGIN_NAMESPACE

template<typename T> class QList;

template<typename T> class QVector;

namespace QPatternist

{

    template<typename T, typename ListType> class ListIterator;

    class OptimizationPass;

    /**

     * @short Base class for all AST nodes in an XPath/XQuery/XSL-T expression.

     *

     * @section ExpressionCreation Expression Compilation

     *

     * @subsection ExpressionCreationParser The process of creating an Expression

     *

     * The initial step of creating an internal representation(in some circles

     * called an IR tree) of the XPath string follows classic compiler design: a scanner

     * is invoked, resulting in tokens, which sub-sequently are consumed by a parser

     * which groups the tokens into rules, resulting in the creation of

     * Abstract Syntax Tree(AST) nodes that are arranged in a hierarchical structure

     * similar to the EBNF.

     *

     * More specifically, ExpressionFactory::createExpression() is called with a

     * pointer to a static context, and the string for the expression. This is subsequently

     * tokenized by a Flex scanner. Mistakes detected at this stage is syntax

     * errors, as well as a few semantical errors. Syntax errors can be divided

     * in two types:

     *

     *     - The scanner detects it. An example is the expression "23Eb3" which

     *     is not a valid number literal, or "1prefix:my-element" which is not a

     *     valid QName.

     *     - The parser detects it. This means a syntax error at a

     *     higher level, that a group of tokens couldn't be reduced to a

     *     rule(expression). An example is the expression "if(a = b) 'match' else

     *     'no match'"; the tokenizer would handle it fine, but the parser would

     *     fail because the tokens could not be reduced to a rule due to the token

     *     for the "then" word was missing.

     *

     * Apart from the syntax errors, the actions in the parser also detects

     * errors when creating the corresponding expressions. This is for example

     * that no namespace binding for a prefix could be found, or that a function

     * call was used which no function implementation could be found for.

     *

     * When the parser has finished, the result is an AST. That is, a

     * hierarchical structure consisting of Expression sub-classes. The

     * individual expressions haven't at this point done anything beyond

     * receiving their child-expressions(if any), and hence reminds of a

     * "construction scaffold". In other words, a tree for the expression

     * <tt>'string' + 1 and xs:date('2001-03-13')</tt> could have been created, even if

     * that expression contains errors(one can't add a xs:integer to a xs:string,

     * and the Effective %Boolean Value cannot be extracted for date types).

     *

     * @subsection ExpressionCreationTypeChecking Type Checking

     *

     * After the AST creation, ExpressionFactory::createExpression continues with

     * calling the AST node(which is an Expression instance)'s typeCheck()

     * function. This step ensures that the static types of the operands matches

     * the operators, and in the cases where it doesn't, modifies the AST such

     * that the necessary conversions are done -- if possible, otherwise the

     * result is a type error.

     *

     *

     * This step corresponds roughly to what <a

     * href="http://www.w3.org/TR/xpath20/#id-static-analysis">2.2.3.1 Static Analysis Phase</a>

     * labels operation tree normalization; step SQ5.

     *

     * @subsection ExpressionCreationCompression Compressing -- Optimization and Fixup

     *

     * The last step is calling compress(). This function is not called

     * 'optimize', 'simplify' or the like, because although it performs all

     * optimization, it also involves mandatory stages.

     *

     * One such is const folding, which while being an efficient optimization,

     * also is a necessity for many XSL-T constructs. Another important step is

     * that functions which had an evaluation dependency on the static context(as

     * opposed to the dynamic) performs their "fixup".

     *

     * In other words, this stage potentially performs AST re-writes. For example,

     * the expression <tt>3 + 3, concat('foo', '-', 'bar'), true() and false()</tt> would

     * result in an AST corresponding to <tt>6, 'foo-bar', false()</tt>. This process

     * is done backwards; each expression asks its operands to compress before it

     * performs its own compression(and so forth, until the root expression's call

     * returns to the caller).

     *

     * @see <a href="http://www.w3.org/TR/xpath20/#id-errors-and-opt">XML Path Language

     * (XPath) 2.0, 2.3.4 Errors and Optimization</a>

     * @see <a href="http://www.w3.org/TR/xpath20/#id-expression-processing">XML Path

     * Language (XPath) 2.0, 2.2.3 Expression Processing</a>

     * @see <a href="http://www.w3.org/TR/xquery-xpath-parsing/">Building a Tokenizer

     * for XPath or XQuery</a>

     * @see ExpressionFactory

     * @author Frans Englich <frans.englich@nokia.com>

     * @ingroup Patternist_expressions

     */

    class Q_AUTOTEST_EXPORT Expression : public QSharedData

                                       , public CppCastingHelper<Expression>

                                       , public SourceLocationReflection

    {

    public:

        /**

         * @short A smart pointer wrapping mutable Expression instances.

         */

        typedef QExplicitlySharedDataPointer<Expression> Ptr;

        /**

         * @short A smart pointer wrapping @c const Expression instances.

         */

        typedef QExplicitlySharedDataPointer<const Expression> ConstPtr;

        /**

         * A list of Expression instances, each wrapped in a smart pointer.

         */

        typedef QList<Expression::Ptr> List;

        /**

         * A vector of Expression instances, each wrapped in a smart pointer.

         */

        typedef QVector<Expression::Ptr> Vector;

        typedef QT_PREPEND_NAMESPACE(QAbstractXmlForwardIterator<Expression::Ptr>)

            QAbstractXmlForwardIterator;

        /**

         * Enum flags describing the characteristics of the expression.

         *

         * @see Expression::properties()

         */

        enum Property

        {

            /**

             * This flag applies for functions, and results in the expression <tt>.</tt>

             * being appended to its operands if its operand count is lower than the

             * maximum amount of arguments.

             *

             * In effect, it result in a modification of the function's arguments to have

             * appended the context item.

             *

             * One function which has this property is <tt>fn:number()</tt>.

             *

             * @see ContextItem

             * @see <a href="http://www.w3.org/TR/xpath-functions/#func-signatures">XQuery 1.0 and

             * XPath 2.0 Functions and Operators, 1.3 Function Signatures and Descriptions</a>

             */

            UseContextItem              = 1,

            /**

             * Disables compression(evaluation at compile time), such that the

             * Expression isn't const-folded, but ensured to be run at runtime. The

             * operands are still attempted to be compressed, unless

             * they override compression as well.

             *

             * @see compress()

             */

            DisableElimination          = 1 << 1,

            /**

             * Signals that the expression is already evaluated and can be considered

             * a constant value.

             * For example, atomic values return this flag in their

             * implementations of the properties() functions.

             *

             * @see isEvaluated()

             */

            IsEvaluated                 = 1 << 2,

            /**

             * Signals that the expression cannot be optimized away by judging

             * its static type.

             *

             * This is currently used for properly handling the @c none type, in

             * the <tt>fn:error()</tt> function. In type operations, the none type doesn't show

             * up and that can make expressions, such as InstanceOf, believe

             * it is safe to const fold, while it in fact is not.

             */

            DisableTypingDeduction      = 1 << 3,

            /**

             * This property affects the static type -- staticType() -- of an expression. It

             * is implemented in FunctionCall::staticType() and therefore only work for FunctionCall

             * sub-classes and when that function is not re-implemented in an inhibiting way.

             *

             * When set, the cardinality of the static type is zero if the Expression's first

             * operand allows an empty sequence, otherwise it is the cardinality of the Expression's

             * static type modulo Cardinality::empty(). This is used for specifying proper static

             * type inference for functions that have "If $arg is the empty sequence,

             * the empty sequence is returned." However, before setting this property one

             * must be aware that no other conditions can lead to the empty sequence, since

             * otherwise the static type would be wrong.

             */

            EmptynessFollowsChild       = 1 << 4,

            /**

             * This is similar to EmptynessFollowsChild, and also implemented in FunctionCall.

             * When set, it makes FunctionCall::typeCheck() rewrite itself into an empty sequence

             * if the first operand is the empty sequence.

             *

             * This property is often used together with EmptynessFollowsChild.

             */

            RewriteToEmptyOnEmpty       = 1 << 5,

            /**

             * When set, it signals that the focus cannot be undefined. For example,

             * the <tt>fn:position()</tt> function extracts information from the focus. Setting

             * this flag ensures type checking is carried out appropriately.

             *

             * However, setting RequiresFocus does not imply this Expression requires the context

             * item to be defined. It only means the focus, of somekind, needs to be defined.

             *

             * @see RequiresContextItem

             */

            RequiresFocus               = 1 << 6,

            /**

             * An Expression with this Property set, signals that it only affects

             * the order of its return value.

             */

            AffectsOrderOnly            = 1 << 7,

            /**

             * When set, signals that the context item, must be defined for this Expression. When

             * setting this property, expectedContextItemType() must be re-implemented.

             *

             * Setting this property also sets RequiresFocus.

             *

             * @see DynamicContext::contextItem()

             */

            RequiresContextItem         = (1 << 8) | RequiresFocus,

            /**

             * When set, signals that this expression creates a focus for its last operand.

             * When set, newFocusType() must be overridden to return the static type

             * of the context item.

             *

             * @see announceFocusType()

             * @see newFocusType()

             */

            CreatesFocusForLast         = 1 << 9,

            /**

             * Signals that the last operand is a collation argument. This ensures

             * that the necessary code is generated for checking that the collation

             * is supported.

             *

             * This only applies to sub-classes of FunctionCall.

             */

            LastOperandIsCollation      = 1 << 10,

            /**

             * When set, the Expression depends on local variables such as

             * those found in @c for expressions. However, this does not

             * include let bindings.

             */

            DependsOnLocalVariable      = (1 << 11) | DisableElimination,

            /**

             * When set, it signals that the Expression does not need

             * an evaluation cache, despite what other flags might imply.

             */

            EvaluationCacheRedundant       = (1 << 12),

            /**

             * Signals that the Expression constructs nodes, either directly

             * or computationally. For example, AttributeConstructor has this property

             * set.

             *

             * Since node constructors constructs nodes which have node

             * identities, node constructors are considered creative on

             * evaluation.

             */

            IsNodeConstructor           = 1 << 13,

            /**

             * Whether this expression requires the current item, as returned

             * from @c fn:current().

             *

             * CurrentFN uses this flag.

             */

            RequiresCurrentItem         = 1 << 14

        };

        /**

         * A QFlags template for type-safe handling of ExpressionProperty values. If

         * Expression::Property flags needs to be stored in a class, declared the variable

         * to be of type Expression::Properties.

         *

         * @see QFlags

         */

        typedef QFlags<Property> Properties;

        /**

         * Enumerators that identifies Expression sub-classes.

         *

         * @see id()

         */

        enum ID

        {

            /**

             * Identifies Boolean.

             */

            IDBooleanValue = 1,

            /**

             * Identifies CountFN.

             */

            IDCountFN,

            /**

             * Identifies EmptyFN.

             */

            IDEmptyFN,

            /**

             * Identifies ExistsFN.

             */

            IDExistsFN,

            /**

             * Identifies ExpressionSequence and LiteralSequence.

             */

            IDExpressionSequence,

            /**

             * Identifies GeneralComparison.

             */

            IDGeneralComparison,

            /**

             * Identifies IfThenClause.

             */

            IDIfThenClause,

            /**

             * Identifies nothing in particular. The default implementation

             * of id() returns this, which is suitable for Expression instances

             * which never needs to be identified in this aspect.

             */

            IDIgnorableExpression,

            /**

             * Identifies Integer.

             */

            IDIntegerValue,

            /**

             * Identifies PositionFN.

             */

            IDPositionFN,

            /**

             * Identifies AtomicString, AnyURI, and UntypedAtomic.

             */

            IDStringValue,

            /**

             * Identifies ValueComparison.

             */

            IDValueComparison,

            /**

             * Identifies VariableReference.

             */

            IDRangeVariableReference,

            /**

             * Identifies ContextItem.

             */

            IDContextItem,

            /**

             * Identifies UserFunctionCallsite.

             */

            IDUserFunctionCallsite,

            /**

             * Identifies ExpressionVariableReference.

             */

            IDExpressionVariableReference,

            /**

             * Identifies ExpressionVariableReference.

             */

            IDAttributeConstructor,

            /**

             * Identifies UpperCaseFN.

             */

            IDUpperCaseFN,

            /**

             * Identifies LowerCaseFN.

             */

            IDLowerCaseFN,

            /**

             * Identifies FirstItemPredicate.

             */

            IDFirstItemPredicate,

            IDEmptySequence,

            IDReturnOrderBy,

            IDLetClause,

            IDForClause,

            IDPath,

            IDNamespaceConstructor,

            IDArgumentReference,

            IDGenericPredicate,

            IDAxisStep,

            /**

             * A literal which is either @c xs:float or

             * @c xs:double.

             */

            IDFloat,

            IDCombineNodes,

            IDUnresolvedVariableReference,

            IDCardinalityVerifier

        };

        inline Expression()

        {

        }

        virtual ~Expression();

        /**

         * Evaluate this Expression by iterating over it. This is a central function

         * for evaluating expressions.

         *

         * Expressions must always always return a valid QAbstractXmlForwardIterator and may

         * never return 0. If an empty result is of interest to be returned, the

         * EmptyIterator should be returned.

         *

         * The default implementation returns a SingletonIterator over the

         * item returned from evaluateSingleton().

         *

         * @note This function may raise an exception when calling, not only

         * when QAbstractXmlForwardIterator::next() is called on the return value. This is because

         * in some cases evaluateSingleton() is called directly.

         */

        virtual Item::Iterator::Ptr evaluateSequence(const DynamicContext::Ptr &context) const;

        /**

         * @todo Docs

         */

        virtual Item evaluateSingleton(const DynamicContext::Ptr &context) const;

        /**

         * Determines the Effective %Boolean Value of the expression.

         *

         * The Effective %Boolean Value of a value is not necessarily the same

         * as converting the value to a new value of type xs:boolean.

         *

         * Note that this function cannot return the empty sequence,

         * evaluateSingleton() must be overridden in order to be able to do

         * that.

         *

         * The default implementation results in a type error. Hence, this function

         * must be overridden if such behavior is not of interest.

         *