1:   2:   3:   4:   5:   6:   7:   8:   9:  10:  11:  12:  13:  14:  15:  16:  17:  18:  19:  20:  21:  22:  23:  24:  25:  26:  27:  28:  29:  30:  31:  32:  33:  34:  35:  36:  37:  38:  39:  40:  41:  42:  43:  44:  45:  46:  47:  48:  49:  50:  51:  52:  53:  54:  55:  56:  57:  58:  59:  60:  61:  62:  63:  64:  65:  66:  67:  68:  69:  70:  71:  72:  73:  74:  75:  76:  77:  78:  79:  80:  81:  82:  83:  84:  85:  86:  87:  88:  89:  90:  91:  92:  93:  94:  95:  96:  97:  98:  99: 100: 101: 102: 103: 104: 105: 106: 107: 108: 109: 110: 111: 112: 113: 114: 115: 116: 117: 118: 119: 120: 121: 122: 123: 124: 125: 126: 127: 128: 129: 130: 131: 132: 133: 134: 135: 136: 137: 138: 139: 140: 141: 142: 143: 144: 145: 146: 147: 148: 149: 150: 151: 152: 153: 154: 155: 156: 157: 158: 159: 160: 161: 162: 163: 164: 165: 166: 167: 168: 169: 170: 171: 172: 173: 174: 175: 176: 177: 178: 179: 

<?php

/*
 * This file is part of the webmozart/expression package.
 *
 * (c) Bernhard Schussek <bschussek@gmail.com>
 *
 * For the full copyright and license information, please view the LICENSE
 * file that was distributed with this source code.
 */

namespace Webmozart\Expression\Traversal;

use Webmozart\Expression\Expression;
use Webmozart\Expression\Logic\Conjunction;
use Webmozart\Expression\Logic\Disjunction;
use Webmozart\Expression\Logic\Not;
use Webmozart\Expression\Selector\Key;

/**
 * Traverses {@link Expression} instances.
 *
 * You can attach {@link ExpressionVisitor} instances to the traverse which
 * will be invoked for every node of the expression tree.
 *
 * @since  1.0
 *
 * @author Bernhard Schussek <bschussek@gmail.com>
 */
class ExpressionTraverser
{
    /**
     * @var ExpressionVisitor[]
     */
    private $visitors = array();

    /**
     * Adds a visitor to the traverser.
     *
     * The visitors are invoked in the order in which they are added.
     *
     * @param ExpressionVisitor $visitor The visitor to add.
     */
    public function addVisitor(ExpressionVisitor $visitor)
    {
        $this->visitors[] = $visitor;
    }

    /**
     * Removes a visitor from the traverser.
     *
     * If the visitor was added multiple times, all instances are removed.
     *
     * @param ExpressionVisitor $visitor The visitor to remove.
     */
    public function removeVisitor(ExpressionVisitor $visitor)
    {
        while (false !== ($key = array_search($visitor, $this->visitors, true))) {
            unset($this->visitors[$key]);
        }

        $this->visitors = array_values($this->visitors);
    }

    /**
     * Returns the visitors of the traverser.
     *
     * @return ExpressionVisitor[] The visitors.
     */
    public function getVisitors()
    {
        return $this->visitors;
    }

    /**
     * Traverses an expression.
     *
     * @param Expression $expr The expression to traverse.
     *
     * @return Expression The modified expression. May be `null` if the
     *                    expression was removed entirely.
     */
    public function traverse(Expression $expr)
    {
        // Do one full traversal per visitor. If any of the visitors removes
        // the expression entirely, subsequent visitors are not invoked.
        foreach ($this->visitors as $visitor) {
            $expr = $this->traverseForVisitor($expr, $visitor);

            if (!$expr) {
                return null;
            }
        }

        return $expr;
    }

    private function traverseForVisitor(Expression $expr, ExpressionVisitor $visitor)
    {
        $expr = $visitor->enterExpression($expr);

        if ($expr instanceof Key) {
            $expr = $this->traverseKey($expr);
        } elseif ($expr instanceof Not) {
            $expr = $this->traverseNot($expr);
        } elseif ($expr instanceof Conjunction) {
            $expr = $this->traverseConjunction($expr);
        } elseif ($expr instanceof Disjunction) {
            $expr = $this->traverseDisjunction($expr);
        }

        if ($expr) {
            $expr = $visitor->leaveExpression($expr);
        }

        return $expr;
    }

    private function traverseKey(Key $expr)
    {
        $innerExpr1 = $expr->getExpression();
        $innerExpr2 = $this->traverse($innerExpr1);

        if ($innerExpr1 === $innerExpr2) {
            return $expr;
        }

        return $innerExpr2 ? new Key($expr->getKey(), $innerExpr2) : null;
    }

    private function traverseNot(Not $expr)
    {
        $negatedExpr1 = $expr->getNegatedExpression();
        $negatedExpr2 = $this->traverse($negatedExpr1);

        if ($negatedExpr1 === $negatedExpr2) {
            return $expr;
        }

        return $negatedExpr2 ? new Not($negatedExpr2) : null;
    }

    private function traverseConjunction(Conjunction $expr)
    {
        $conjuncts1 = $expr->getConjuncts();
        $conjuncts2 = array();

        foreach ($conjuncts1 as $conjunct) {
            if ($conjunct = $this->traverse($conjunct)) {
                $conjuncts2[] = $conjunct;
            }
        }

        if ($conjuncts1 === $conjuncts2) {
            return $expr;
        }

        return $conjuncts2 ? new Conjunction($conjuncts2) : null;
    }

    private function traverseDisjunction(Disjunction $expr)
    {
        $disjuncts1 = $expr->getDisjuncts();
        $disjuncts2 = array();

        foreach ($disjuncts1 as $disjunct) {
            if ($disjunct = $this->traverse($disjunct)) {
                $disjuncts2[] = $disjunct;
            }
        }

        if ($disjuncts1 === $disjuncts2) {
            return $expr;
        }

        return $disjuncts2 ? new Disjunction($disjuncts2) : null;
    }
}