<?php

/*

 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS

 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT

 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR

 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT

 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,

 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT

 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,

 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY

 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT

 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE

 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

 *

 * This software consists of voluntary contributions made by many individuals

 * and is licensed under the LGPL. For more information, see

 * <http://www.doctrine-project.org>.

 */

namespace Doctrine\ORM\Query;

use Doctrine\ORM\Query;

use Doctrine\ORM\Mapping\ClassMetadata;

/**

 * An LL(*) recursive-descent parser for the context-free grammar of the Doctrine Query Language.

 * Parses a DQL query, reports any errors in it, and generates an AST.

 *

 * @since   2.0

 * @author  Guilherme Blanco <guilhermeblanco@hotmail.com>

 * @author  Jonathan Wage <jonwage@gmail.com>

 * @author  Roman Borschel <roman@code-factory.org>

 * @author  Janne Vanhala <jpvanhal@cc.hut.fi>

 */

class Parser

{

    /** READ-ONLY: Maps BUILT-IN string function names to AST class names. */

    private static $_STRING_FUNCTIONS = array(

        'concat'    => 'Doctrine\ORM\Query\AST\Functions\ConcatFunction',

        'substring' => 'Doctrine\ORM\Query\AST\Functions\SubstringFunction',

        'trim'      => 'Doctrine\ORM\Query\AST\Functions\TrimFunction',

        'lower'     => 'Doctrine\ORM\Query\AST\Functions\LowerFunction',

        'upper'     => 'Doctrine\ORM\Query\AST\Functions\UpperFunction'

    );

    /** READ-ONLY: Maps BUILT-IN numeric function names to AST class names. */

    private static $_NUMERIC_FUNCTIONS = array(

        'length'    => 'Doctrine\ORM\Query\AST\Functions\LengthFunction',

        'locate'    => 'Doctrine\ORM\Query\AST\Functions\LocateFunction',

        'abs'       => 'Doctrine\ORM\Query\AST\Functions\AbsFunction',

        'sqrt'      => 'Doctrine\ORM\Query\AST\Functions\SqrtFunction',

        'mod'       => 'Doctrine\ORM\Query\AST\Functions\ModFunction',

        'size'      => 'Doctrine\ORM\Query\AST\Functions\SizeFunction',

        'date_diff' => 'Doctrine\ORM\Query\AST\Functions\DateDiffFunction',

    );

    /** READ-ONLY: Maps BUILT-IN datetime function names to AST class names. */

    private static $_DATETIME_FUNCTIONS = array(

        'current_date'      => 'Doctrine\ORM\Query\AST\Functions\CurrentDateFunction',

        'current_time'      => 'Doctrine\ORM\Query\AST\Functions\CurrentTimeFunction',

        'current_timestamp' => 'Doctrine\ORM\Query\AST\Functions\CurrentTimestampFunction',

        'date_add'          => 'Doctrine\ORM\Query\AST\Functions\DateAddFunction',

        'date_sub'          => 'Doctrine\ORM\Query\AST\Functions\DateSubFunction',

    );

    /**

     * Expressions that were encountered during parsing of identifiers and expressions

     * and still need to be validated.

     */

    private $_deferredIdentificationVariables = array();

    private $_deferredPartialObjectExpressions = array();

    private $_deferredPathExpressions = array();

    private $_deferredResultVariables = array();

    /**

     * The lexer.

     *

     * @var Doctrine\ORM\Query\Lexer

     */

    private $_lexer;

    /**

     * The parser result.

     *

     * @var Doctrine\ORM\Query\ParserResult

     */

    private $_parserResult;

    /**

     * The EntityManager.

     *

     * @var EnityManager

     */

    private $_em;

    /**

     * The Query to parse.

     *

     * @var Query

     */

    private $_query;

    /**

     * Map of declared query components in the parsed query.

     *

     * @var array

     */

    private $_queryComponents = array();

    /**

     * Keeps the nesting level of defined ResultVariables

     *

     * @var integer

     */

    private $_nestingLevel = 0;

    /**

     * Any additional custom tree walkers that modify the AST.

     *

     * @var array

     */

    private $_customTreeWalkers = array();

    /**

     * The custom last tree walker, if any, that is responsible for producing the output.

     *

     * @var TreeWalker

     */

    private $_customOutputWalker;

    /**

     * @var array

     */

    private $_identVariableExpressions = array();

    /**

     * Creates a new query parser object.

     *

     * @param Query $query The Query to parse.

     */

    public function __construct(Query $query)

    {

        $this->_query = $query;

        $this->_em = $query->getEntityManager();

        $this->_lexer = new Lexer($query->getDql());

        $this->_parserResult = new ParserResult();

    }

    /**

     * Sets a custom tree walker that produces output.

     * This tree walker will be run last over the AST, after any other walkers.

     *

     * @param string $className

     */

    public function setCustomOutputTreeWalker($className)

    {

        $this->_customOutputWalker = $className;

    }

    /**

     * Adds a custom tree walker for modifying the AST.

     *

     * @param string $className

     */

    public function addCustomTreeWalker($className)

    {

        $this->_customTreeWalkers[] = $className;

    }

    /**

     * Gets the lexer used by the parser.

     *

     * @return Doctrine\ORM\Query\Lexer

     */

    public function getLexer()

    {

        return $this->_lexer;

    }

    /**

     * Gets the ParserResult that is being filled with information during parsing.

     *

     * @return Doctrine\ORM\Query\ParserResult

     */

    public function getParserResult()

    {

        return $this->_parserResult;

    }

    /**

     * Gets the EntityManager used by the parser.

     *

     * @return EntityManager

     */

    public function getEntityManager()

    {

        return $this->_em;

    }

    /**

     * Parse and build AST for the given Query.

     *

     * @return \Doctrine\ORM\Query\AST\SelectStatement |

     *         \Doctrine\ORM\Query\AST\UpdateStatement |

     *         \Doctrine\ORM\Query\AST\DeleteStatement

     */

    public function getAST()

    {

        // Parse & build AST

        $AST = $this->QueryLanguage();

        // Process any deferred validations of some nodes in the AST.

        // This also allows post-processing of the AST for modification purposes.

        $this->_processDeferredIdentificationVariables();

        if ($this->_deferredPartialObjectExpressions) {

            $this->_processDeferredPartialObjectExpressions();

        }

        if ($this->_deferredPathExpressions) {

            $this->_processDeferredPathExpressions($AST);

        }

        if ($this->_deferredResultVariables) {

            $this->_processDeferredResultVariables();

        }

        return $AST;

    }

    /**

     * Attempts to match the given token with the current lookahead token.

     *

     * If they match, updates the lookahead token; otherwise raises a syntax

     * error.

     *

     * @param int token type

     * @return void

     * @throws QueryException If the tokens dont match.

     */

    public function match($token)

    {

        // short-circuit on first condition, usually types match

        if ($this->_lexer->lookahead['type'] !== $token &&

                $token !== Lexer::T_IDENTIFIER &&

                $this->_lexer->lookahead['type'] <= Lexer::T_IDENTIFIER

         ) {

            $this->syntaxError($this->_lexer->getLiteral($token));

        }

        $this->_lexer->moveNext();

    }

    /**

     * Free this parser enabling it to be reused

     *

     * @param boolean $deep     Whether to clean peek and reset errors

     * @param integer $position Position to reset

     */

    public function free($deep = false, $position = 0)

    {

        // WARNING! Use this method with care. It resets the scanner!

        $this->_lexer->resetPosition($position);

        // Deep = true cleans peek and also any previously defined errors

        if ($deep) {

            $this->_lexer->resetPeek();

        }

        $this->_lexer->token = null;

        $this->_lexer->lookahead = null;

    }

    /**

     * Parses a query string.

     *

     * @return ParserResult

     */

    public function parse()

    {

        $AST = $this->getAST();

        $this->fixIdentificationVariableOrder($AST);

        $this->assertSelectEntityRootAliasRequirement();

        if (($customWalkers = $this->_query->getHint(Query::HINT_CUSTOM_TREE_WALKERS)) !== false) {

            $this->_customTreeWalkers = $customWalkers;

        }

        if (($customOutputWalker = $this->_query->getHint(Query::HINT_CUSTOM_OUTPUT_WALKER)) !== false) {

            $this->_customOutputWalker = $customOutputWalker;

        }

        // Run any custom tree walkers over the AST

        if ($this->_customTreeWalkers) {

            $treeWalkerChain = new TreeWalkerChain($this->_query, $this->_parserResult, $this->_queryComponents);

            foreach ($this->_customTreeWalkers as $walker) {

                $treeWalkerChain->addTreeWalker($walker);

            }

            if ($AST instanceof AST\SelectStatement) {

                $treeWalkerChain->walkSelectStatement($AST);

            } else if ($AST instanceof AST\UpdateStatement) {

                $treeWalkerChain->walkUpdateStatement($AST);

            } else {

                $treeWalkerChain->walkDeleteStatement($AST);

            }

        }

        if ($this->_customOutputWalker) {

            $outputWalker = new $this->_customOutputWalker(

                $this->_query, $this->_parserResult, $this->_queryComponents

            );

        } else {

            $outputWalker = new SqlWalker(

                $this->_query, $this->_parserResult, $this->_queryComponents

            );

        }

        // Assign an SQL executor to the parser result

        $this->_parserResult->setSqlExecutor($outputWalker->getExecutor($AST));

        return $this->_parserResult;

    }

    private function assertSelectEntityRootAliasRequirement()

    {

        if ( count($this->_identVariableExpressions) > 0) {

            $foundRootEntity = false;

            foreach ($this->_identVariableExpressions AS $dqlAlias => $expr) {

                if (isset($this->_queryComponents[$dqlAlias]) && $this->_queryComponents[$dqlAlias]['parent'] === null) {

                    $foundRootEntity = true;

                }

            }

            if (!$foundRootEntity) {

                $this->semanticalError('Cannot select entity through identification variables without choosing at least one root entity alias.');

            }

        }

    }

    /**

     * Fix order of identification variables.

     * 

     * They have to appear in the select clause in the same order as the

     * declarations (from ... x join ... y join ... z ...) appear in the query

     * as the hydration process relies on that order for proper operation.

     * 

     * @param AST\SelectStatement|AST\DeleteStatement|AST\UpdateStatement $AST

     * @return void

     */

    private function fixIdentificationVariableOrder($AST)

    {

        if ( count($this->_identVariableExpressions) > 1) {

            foreach ($this->_queryComponents as $dqlAlias => $qComp) {

                if (isset($this->_identVariableExpressions[$dqlAlias])) {

                    $expr = $this->_identVariableExpressions[$dqlAlias];

                    $key = array_search($expr, $AST->selectClause->selectExpressions);

                    unset($AST->selectClause->selectExpressions[$key]);

                    $AST->selectClause->selectExpressions[] = $expr;

                }

            }

        }

    }

    /**

     * Generates a new syntax error.

     *

     * @param string $expected Expected string.

     * @param array $token Got token.

     *

     * @throws \Doctrine\ORM\Query\QueryException

     */

    public function syntaxError($expected = '', $token = null)

    {

        if ($token === null) {

            $token = $this->_lexer->lookahead;

        }

        $tokenPos = (isset($token['position'])) ? $token['position'] : '-1';

        $message  = "line 0, col {$tokenPos}: Error: ";

        if ($expected !== '') {

            $message .= "Expected {$expected}, got ";

        } else {

            $message .= 'Unexpected ';

        }

        if ($this->_lexer->lookahead === null) {

            $message .= 'end of string.';

        } else {

            $message .= "'{$token['value']}'";

        }

        throw QueryException::syntaxError($message);

    }

    /**

     * Generates a new semantical error.

     *

     * @param string $message Optional message.

     * @param array $token Optional token.

     *

     * @throws \Doctrine\ORM\Query\QueryException

     */

    public function semanticalError($message = '', $token = null)

    {

        if ($token === null) {

            $token = $this->_lexer->lookahead;

        }

        // Minimum exposed chars ahead of token

        $distance = 12;

        // Find a position of a final word to display in error string

        $dql = $this->_query->getDql();

        $length = strlen($dql);

        $pos = $token['position'] + $distance;

        $pos = strpos($dql, ' ', ($length > $pos) ? $pos : $length);

        $length = ($pos !== false) ? $pos - $token['position'] : $distance;

        // Building informative message

        $message = 'line 0, col ' . (

            (isset($token['position']) && $token['position'] > 0) ? $token['position'] : '-1'

        ) . " near '" . substr($dql, $token['position'], $length) . "': Error: " . $message;

        throw \Doctrine\ORM\Query\QueryException::semanticalError($message);

    }

    /**

     * Peeks beyond the specified token and returns the first token after that one.

     *

     * @param array $token

     * @return array

     */

    private function _peekBeyond($token)

    {

        $peek = $this->_lexer->peek();

        while ($peek['value'] != $token) {

            $peek = $this->_lexer->peek();

        }