PredictionContext::hashCode() - Code Metrics - SetBased/antlr-php-runtime - Measure and Improve Code Quality continuously with Scrutinizer

PredictionContext::hashCode() A
last analyzed 2020-12-10 13:11 UTC

↳ Parent: PredictionContext

Complexity

Conditions	2
Paths	2

Size

Total Lines	7
Code Lines	3

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	4
CRAP Score	2

Importance

Changes	1
Bugs	0	Features	0

Metric	Value
cc	2
eloc	3
c	1
b	0
f	0
nc	2
nop	0
dl	0
loc	7
ccs	4
cts	4
cp	1
crap	2
rs	10

<?php

declare(strict_types=1);

namespace Antlr\Antlr4\Runtime\PredictionContexts;

use Antlr\Antlr4\Runtime\Atn\ATN;
use Antlr\Antlr4\Runtime\Atn\Transitions\RuleTransition;
use Antlr\Antlr4\Runtime\Comparison\Hashable;
use Antlr\Antlr4\Runtime\RuleContext;
use Antlr\Antlr4\Runtime\Utils\DoubleKeyMap;

abstract class PredictionContext implements Hashable
{
    /** @var int */
    private static $globalNodeCount = 1;

    /** @var int */
    public $id;

    /**
     * Represents `$` in an array in full context mode, when `$` doesn't mean
     * wildcard: `$ + x = [$,x]`.
     *
     * Here, `$` = {@see PredictionContext::EMPTY_RETURN_STATE}.
     */
    public const EMPTY_RETURN_STATE = 0x7FFFFFFF;

    /**
     * Stores the computed hash code of this {@see PredictionContext}. The hash
     * code is computed in parts to match the following reference algorithm.
     *
     *     private int referenceHashCode() {
     *         int hash = {@see MurmurHash::initialize}({@see PredictionContext::INITIAL_HASH});
     *
     *         for (int i = 0; i < {@see PredictionContext::size()}; i++) {
     *             hash = {@see MurmurHash::update}(hash, {@see PredictionContext::getParent()});
     *         }
     *
     *         for (int i = 0; i < {@see PredictionContext::size()}; i++) {
     *             hash = {@see MurmurHash::update}(hash, {@see PredictionContext::getReturnState()});
     *         }
     *
     *         hash = {@see MurmurHash::finish}(hash, 2 * {@see PredictionContext::size()});
     *
     *         return hash;
     *     }
     *
     * @var int|null
     */
    public $cachedHashCode;

    public function __construct()
    {
        $this->id = self::$globalNodeCount++;
    }

    public static function empty() : EmptyPredictionContext
    {
        static $empty;

        if ($empty === null) {
            static::$globalNodeCount--;

            $empty = new EmptyPredictionContext();
            $empty->id = 0;
        }

        return $empty;
    }

    /**
     * Convert a {@see RuleContext} tree to a {@see PredictionContext} graph.
     * Return {@see PredictionContext::empty()} if `outerContext` is empty or null.
     */
    public static function fromRuleContext(ATN $atn, ?RuleContext $outerContext) : PredictionContext
    {
        if ($outerContext === null) {
            $outerContext = RuleContext::emptyContext();
        }

        // If we are in RuleContext of start rule, s, then PredictionContext
        // is EMPTY. Nobody called us. (if we are empty, return empty)
        if ($outerContext->getParent() === null || $outerContext === RuleContext::emptyContext()) {
            return self::empty();
        }

        // If we have a parent, convert it to a PredictionContext graph
        $parent = self::fromRuleContext($atn, $outerContext->getParent());
        $state = $atn->states[$outerContext->invokingState];
        $transition = $state->getTransition(0);

        if (!$transition instanceof RuleTransition) {
            throw new \RuntimeException('Unexpected transition type.');
        }

        return SingletonPredictionContext::create($parent, $transition->followState->stateNumber);
    }

    /**
     * This means only the {@see PredictionContext::empty()} (wildcard? not sure)
     * context is in set.
     */
    public function isEmpty() : bool
    {
        return $this === self::empty();
    }

    public function hasEmptyPath() : bool
    {
        return $this->getReturnState($this->getLength() - 1) === self::EMPTY_RETURN_STATE;
    }

    public function hashCode() : int
    {
        if ($this->cachedHashCode === null) {
            $this->cachedHashCode = $this->computeHashCode();
        }

        return $this->cachedHashCode;
    }

    abstract protected function computeHashCode() : int;
    abstract public function getLength() : int;
    abstract public function getParent(int $index) : ?self;
    abstract public function getReturnState(int $index) : int;
    abstract public function __toString() : string;

    public static function merge(
        PredictionContext $a,
        PredictionContext $b,
        bool $rootIsWildcard,
        ?DoubleKeyMap $mergeCache
    ) : PredictionContext {
        // share same graph if both same
        if ($a->equals($b)) {
            return $a;
        }

        if ($a instanceof SingletonPredictionContext && $b instanceof SingletonPredictionContext) {
            return self::mergeSingletons($a, $b, $rootIsWildcard, $mergeCache);
        }

        // At least one of a or b is array
        // If one is $ and rootIsWildcard, return $ as * wildcard
        if ($rootIsWildcard) {
            if ($a instanceof EmptyPredictionContext) {
                return $a;
            }

            if ($b instanceof EmptyPredictionContext) {
                return $b;
            }
        }

        // convert singleton so both are arrays to normalize
        if ($a instanceof SingletonPredictionContext) {
            $a = ArrayPredictionContext::fromOne($a);
        }

        if ($b instanceof SingletonPredictionContext) {
            $b = ArrayPredictionContext::fromOne($b);
        }

        if (!$a instanceof ArrayPredictionContext || !$b instanceof ArrayPredictionContext) {
            throw new \RuntimeException('Unexpected transition type.');
        }

        return self::mergeArrays($a, $b, $rootIsWildcard, $mergeCache);
    }

    /**
     * Merge two {@see SingletonPredictionContext} instances.
     *
     * Stack tops equal, parents merge is same; return left graph.
     *
     * Same stack top, parents differ; merge parents giving array node, then
     * remainders of those graphs. A new root node is created to point to the
     * merged parents.
     *
     * Different stack tops pointing to same parent. Make array node for the
     * root where both element in the root point to the same (original)
     * parent.
     *
     * Different stack tops pointing to different parents. Make array node for
     * the root where each element points to the corresponding original
     * parent.
     *
     * @param SingletonPredictionContext $a              The first {@see SingletonPredictionContext}
     * @param SingletonPredictionContext $b              The second {@see SingletonPredictionContext}
     * @param bool                       $rootIsWildcard `true` if this is a local-context merge,
     *                                                   otherwise false to indicate a full-context merge
     */
    public static function mergeSingletons(
        SingletonPredictionContext $a,
        SingletonPredictionContext $b,
        bool $rootIsWildcard,
        ?DoubleKeyMap $mergeCache
    ) : PredictionContext {
        if ($mergeCache !== null) {
            $previous = $mergeCache->getByTwoKeys($a, $b);

            if ($previous !== null) {
                return $previous;
            }

            $previous = $mergeCache->getByTwoKeys($b, $a);

            if ($previous !== null) {
                return $previous;
            }
        }

        $rootMerge = self::mergeRoot($a, $b, $rootIsWildcard);
class A
{
    function getObject()
    {
        return null;
    }

}

$a = new A();
$object = $a->getObject();

        if ($rootMerge !== null) {

            if ($mergeCache !== null) {
                $mergeCache->set($a, $b, $rootMerge);
            }

            return $rootMerge;
        }

        if ($a->returnState === $b->returnState) {
            if ($a->parent === null || $b->parent === null) {
                throw new \RuntimeException('Unexpected null parents.');
            }

            $parent = self::merge($a->parent, $b->parent, $rootIsWildcard, $mergeCache);

            // If parent is same as existing a or b parent or reduced to a parent, return it
            if ($parent === $a->parent) {
                return $a; // ax + bx = ax, if a=b
            }

            if ($parent === $b->parent) {
                return $b; // ax + bx = bx, if a=b
            }

            // Else: ax + ay = a'[x,y]
            //
            // Merge parents x and y, giving array node with x,y then remainders
            // of those graphs. dup a, a' points at merged array new joined parent
            // so create new singleton pointing to it, a'
            $spc = SingletonPredictionContext::create($parent, $a->returnState);

            if ($mergeCache !== null) {
                $mergeCache->set($a, $b, $spc);
            }
            return $spc;
        } else {
            // a != b payloads differ
            // see if we can collapse parents due to $+x parents if local ctx
            $singleParent = null;

            if ($a === $b || ($a->parent !== null && $a->parent === $b->parent)) {
                // ax +
                // bx =
                // [a,b]x
                $singleParent = $a->parent;
            }

            if ($singleParent !== null) {
                // parents are same
                // sort payloads and use same parent
                $payloads = [$a->returnState, $b->returnState];

                if ($a->returnState > $b->returnState) {
                    $payloads[0] = $b->returnState;
                    $payloads[1] = $a->returnState;
                }

                $parents = [$singleParent, $singleParent];
                $apc = new ArrayPredictionContext($parents, $payloads);

                if ($mergeCache !== null) {
                    $mergeCache->set($a, $b, $apc);
                }

                return $apc;
            }

            // parents differ and can't merge them. Just pack together
            // into array; can't merge.
            // ax + by = [ax,by]
            $payloads = [$a->returnState, $b->returnState];
            $parents = [$a->parent, $b->parent];

            if ($a->returnState > $b->returnState) {
                // sort by payload
                $payloads[0] = $b->returnState;
                $payloads[1] = $a->returnState;
                $parents = [$b->parent, $a->parent];
            }

            $a_ = new ArrayPredictionContext($parents, $payloads);

            if ($mergeCache !== null) {
                $mergeCache->set($a, $b, $a_);
            }

            return $a_;
        }
    }

    /**
     * Handle case where at least one of `a` or `b` is
     * {@see PredictionContext::empty()}. In the following diagrams, the symbol
     * `$` is used to represent {@see PredictionContext::empty()}.
     *
     * Local-Context Merges
     *
     * These local-context merge operations are used when `rootIsWildcard`
     * is true.
     *
     * {@see PredictionContext::empty()} is superset of any graph; return
     * {@see PredictionContext::empty()}.
     *
     * [[img src="images/LocalMerge_EmptyRoot.svg" type="image/svg+xml"]]
     *
     * {@see PredictionContext::empty()} and anything is `#EMPTY`, so merged parent is
     * `#EMPTY`; return left graph
     *
     * [[img src="images/LocalMerge_EmptyParent.svg" type="image/svg+xml"]]
     *
     * Special case of last merge if local context.
     *
     * [[img src="images/LocalMerge_DiffRoots.svg" type="image/svg+xml"]]
     *
     * Full-Context Merges
     *
     * These full-context merge operations are used when `rootIsWildcard`
     * is false.
     *
     * Must keep all contexts; {@see PredictionContext::empty()} in array is
     * a special value (and null parent).
     *
     * [[img src="images/FullMerge_EmptyRoot.svg" type="image/svg+xml"]]
     *
     * [[img src="images/FullMerge_SameRoot.svg" type="image/svg+xml"]]
     */
    public static function mergeRoot(
        SingletonPredictionContext $a,
        SingletonPredictionContext $b,
        bool $rootIsWildcard
    ) : ?PredictionContext {
        if ($rootIsWildcard) {
            if ($a === self::empty()) {

                return self::empty();// // + b =//
            }

            if ($b === self::empty()) {

                return self::empty();// a +// =//
            }
        } else {
            if ($a === self::empty() && $b === self::empty()) {

                return self::empty();// $ + $ = $
            }

            if ($a === self::empty()) {

                // $ + x = [$,x]
                $payloads = [$b->returnState, self::EMPTY_RETURN_STATE];
                $parents = [$b->parent, null];

                return new ArrayPredictionContext($parents, $payloads);
            }

            if ($b === self::empty()) {

                // x + $ = [$,x] ($ is always first if present)
                $payloads = [$a->returnState, self::EMPTY_RETURN_STATE];
                $parents = [$a->parent, null];

                return new ArrayPredictionContext($parents, $payloads);
            }
        }

        return null;
    }

    /**
     * Merge two {@see ArrayPredictionContext} instances.
     *
     * Different tops, different parents.
     *
     * [[img src="images/ArrayMerge_DiffTopDiffPar.svg" type="image/svg+xml"]]
     *
     * Shared top, same parents.
     *
     * [[img src="images/ArrayMerge_ShareTopSamePar.svg" type="image/svg+xml"]]
     *
     * Shared top, different parents.
     *
     * [[img src="images/ArrayMerge_ShareTopDiffPar.svg" type="image/svg+xml"]]
     *
     * Shared top, all shared parents.
     *
     * [[img src="images/ArrayMerge_ShareTopSharePar.svg" type="image/svg+xml"]]
     *
     * Equal tops, merge parents and reduce top to
     * {@see SingletonPredictionContext}.
     *
     * [[img src="images/ArrayMerge_EqualTop.svg" type="image/svg+xml"]]
     */
    public static function mergeArrays(
        ArrayPredictionContext $a,
        ArrayPredictionContext $b,
        bool $rootIsWildcard,
        ?DoubleKeyMap $mergeCache
    ) : PredictionContext {
        if ($mergeCache !== null) {
            $previous = $mergeCache->getByTwoKeys($a, $b);

            if ($previous !== null) {
                return $previous;
            }

            $previous = $mergeCache->getByTwoKeys($b, $a);

            if ($previous !== null) {
                return $previous;
            }
        }

        // merge sorted payloads a + b => M
        $i = 0;// walks a
        $j = 0;// walks b
        $k = 0;// walks target M array

        $mergedReturnStates = [];
        $mergedParents = [];

        // walk and merge to yield mergedParents, mergedReturnStates
        while ($i < \count($a->returnStates) && $j < \count($b->returnStates)) {
            $a_parent = $a->parents[$i];
            $b_parent = $b->parents[$j];

            if ($a->returnStates[$i] === $b->returnStates[$j]) {
                // same payload (stack tops are equal), must yield merged singleton
                $payload = $a->returnStates[$i];

                // $+$ = $
                $bothDollars = $payload === self::EMPTY_RETURN_STATE && $a_parent === null && $b_parent === null;
                $ax_ax = ($a_parent !== null && $b_parent !== null && $a_parent->equals($b_parent));// ax+ax
                // ->
                // ax

                if ($bothDollars || $ax_ax) {
                    $mergedParents[$k] = $a_parent;// choose left
                    $mergedReturnStates[$k] = $payload;
                } else {
                    if ($a_parent === null || $b_parent === null) {
                        throw new \RuntimeException('Unexpected null parents.');
                    }

                    // ax+ay -> a'[x,y]
                    $mergedParent = self::merge($a_parent, $b_parent, $rootIsWildcard, $mergeCache);
                    $mergedParents[$k] = $mergedParent;
                    $mergedReturnStates[$k] = $payload;
                }

                $i++;// hop over left one as usual
                $j++;// but also skip one in right side since we merge
            } elseif ($a->returnStates[$i] < $b->returnStates[$j]) {
                // copy a[i] to M
                $mergedParents[$k] = $a_parent;
                $mergedReturnStates[$k] = $a->returnStates[$i];
                $i++;
            } else {
                // b > a, copy b[j] to M
                $mergedParents[$k] = $b_parent;
                $mergedReturnStates[$k] = $b->returnStates[$j];
                $j++;
            }

            $k++;
        }

        // copy over any payloads remaining in either array
        if ($i < \count($a->returnStates)) {
            for ($p = $i, $count = \count($a->returnStates); $p < $count; $p++) {
                $mergedParents[$k] = $a->parents[$p];
                $mergedReturnStates[$k] = $a->returnStates[$p];
                $k++;
            }
        } else {
            for ($p = $j, $count = \count($b->returnStates); $p < $count; $p++) {
                $mergedParents[$k] = $b->parents[$p];
                $mergedReturnStates[$k] = $b->returnStates[$p];
                $k++;
            }
        }

        // trim merged if we combined a few that had same stack tops
        if ($k < \count($mergedParents)) {
            // write index < last position; trim
            if ($k === 1) {
                // for just one merged element, return singleton top
                $a_ = SingletonPredictionContext::create($mergedParents[0], $mergedReturnStates[0]);

                if ($mergeCache !== null) {
                    $mergeCache->set($a, $b, $a_);
                }

                return $a_;
            }

            $mergedParents = \array_slice($mergedParents, 0, $k);
            $mergedReturnStates = \array_slice($mergedReturnStates, 0, $k);
        }

        self::combineCommonParents($mergedParents);

        $M = new ArrayPredictionContext($mergedParents, $mergedReturnStates);

        // if we created same array as a or b, return that instead
        // TODO: track whether this is possible above during merge sort for speed
        if ($M === $a) {
            if ($mergeCache !== null) {
                $mergeCache->set($a, $b, $a);
            }

            return $a;
        }

        if ($M === $b) {
            if ($mergeCache !== null) {
                $mergeCache->set($a, $b, $b);
            }

            return $b;
        }

        if ($mergeCache !== null) {
            $mergeCache->set($a, $b, $M);
        }

        return $M;
    }

    /**
     * @param array<PredictionContext> $parents
     */
    protected static function combineCommonParents(array &$parents) : void
    {
        $uniqueParents = new \SplObjectStorage();

        foreach ($parents as $parent) {
            if (!$uniqueParents->contains($parent)) {
                $uniqueParents[$parent] = $parent;
            }
        }

        foreach ($parents as $i => $parent) {
            $parents[$i] = $uniqueParents[$parent];
        }
    }

    /**
     * @param array<PredictionContext|null> $visited
     */
    public static function getCachedPredictionContext(
        PredictionContext $context,
        PredictionContextCache $contextCache,
        array &$visited
    ) : self {
        if ($context->isEmpty()) {
            return $context;
        }

        $existing = $visited[\spl_object_id($context)] ?? null;

        if ($existing !== null) {
            return $existing;
        }

        $existing = $contextCache->get($context);

        if ($existing !== null) {
            $visited[\spl_object_id($context)] = $existing;

            return $existing;
        }

        $changed = false;
        $parents = [];
        for ($i = 0; $i < $context->getLength(); $i++) {
            $parentContext = $context->getParent($i);

            if ($parentContext === null) {
                continue;
            }

            $parent = self::getCachedPredictionContext($parentContext, $contextCache, $visited);

            if ($changed || ($parentContext !== null && !$parent->equals($parentContext))) {
                if (!$changed) {
                    $parents = [];

                    for ($j = 0; $j < $context->getLength(); $j++) {
                        $parents[$j] = $context->getParent($j);
                    }

                    $changed = true;
                }

                $parents[$i] = $parent;
            }
        }

        if (!$changed) {

            $contextCache->add($context);

            $visited[\spl_object_id($context)] = $context;

            return $context;
        }

        $updated = null;

        if (\count($parents) === 0) {
            $updated = self::empty();
        } elseif (\count($parents) === 1) {
            $updated = SingletonPredictionContext::create($parents[0], $context->getReturnState(0));
        } else {
            if (!$context instanceof ArrayPredictionContext) {
                throw new \RuntimeException('Unexpected context type.');
            }

            $updated = new ArrayPredictionContext($parents, $context->returnStates);
        }

        $contextCache->add($updated);
        $visited[\spl_object_id($updated)] = $updated;
        $visited[\spl_object_id($context)] = $updated;

        return $updated;
    }

    public function __clone()
    {
        $this->cachedHashCode = null;
    }
}


1		<?php
2
3		declare(strict_types=1);
4
5		namespace Antlr\Antlr4\Runtime\PredictionContexts;
6
7		use Antlr\Antlr4\Runtime\Atn\ATN;
8		use Antlr\Antlr4\Runtime\Atn\Transitions\RuleTransition;
9		use Antlr\Antlr4\Runtime\Comparison\Hashable;
10		use Antlr\Antlr4\Runtime\RuleContext;
11		use Antlr\Antlr4\Runtime\Utils\DoubleKeyMap;
12
13		abstract class PredictionContext implements Hashable
14		{
15		/** @var int */
16		private static $globalNodeCount = 1;
17
18		/** @var int */
19		public $id;
20
21		/**
22		* Represents `$` in an array in full context mode, when `$` doesn't mean
23		* wildcard: `$ + x = [$,x]`.
24		*
25		* Here, `$` = {@see PredictionContext::EMPTY_RETURN_STATE}.
26		*/
27		public const EMPTY_RETURN_STATE = 0x7FFFFFFF;
28
29		/**
30		* Stores the computed hash code of this {@see PredictionContext}. The hash
31		* code is computed in parts to match the following reference algorithm.
32		*
33		* private int referenceHashCode() {
34		* int hash = {@see MurmurHash::initialize}({@see PredictionContext::INITIAL_HASH});
35		*
36		* for (int i = 0; i < {@see PredictionContext::size()}; i++) {
37		* hash = {@see MurmurHash::update}(hash, {@see PredictionContext::getParent()});
38		* }
39		*
40		* for (int i = 0; i < {@see PredictionContext::size()}; i++) {
41		* hash = {@see MurmurHash::update}(hash, {@see PredictionContext::getReturnState()});
42		* }
43		*
44		* hash = {@see MurmurHash::finish}(hash, 2 * {@see PredictionContext::size()});
45		*
46		* return hash;
47		* }
48		*
49		* @var int\|null
50		*/
51		public $cachedHashCode;
52
53	2	public function __construct()
54		{
55	2	$this->id = self::$globalNodeCount++;
56	2	}
57
58	3	public static function empty() : EmptyPredictionContext
59		{
60	3	static $empty;
61
62	3	if ($empty === null) {
63	1	static::$globalNodeCount--;
		0 ignored issues – show Bug introduced 2020-12-10 12:02 UTC by Report Bug Copy Issue Report Since `$globalNodeCount` is declared private, accessing it with `static` will lead to errors in possible sub-classes; you can either use `self`, or increase the visibility of `$globalNodeCount` to at least protected. Loading history...
64	1	$empty = new EmptyPredictionContext();
65	1	$empty->id = 0;
66		}
67
68	3	return $empty;
69		}
70
71		/**
72		* Convert a {@see RuleContext} tree to a {@see PredictionContext} graph.
73		* Return {@see PredictionContext::empty()} if `outerContext` is empty or null.
74		*/
75	2	public static function fromRuleContext(ATN $atn, ?RuleContext $outerContext) : PredictionContext
76		{
77	2	if ($outerContext === null) {
78		$outerContext = RuleContext::emptyContext();
79		}
80
81		// If we are in RuleContext of start rule, s, then PredictionContext
82		// is EMPTY. Nobody called us. (if we are empty, return empty)
83	2	if ($outerContext->getParent() === null \|\| $outerContext === RuleContext::emptyContext()) {
84	2	return self::empty();
85		}
86
87		// If we have a parent, convert it to a PredictionContext graph
88		$parent = self::fromRuleContext($atn, $outerContext->getParent());
89		$state = $atn->states[$outerContext->invokingState];
90		$transition = $state->getTransition(0);
91
92		if (!$transition instanceof RuleTransition) {
93		throw new \RuntimeException('Unexpected transition type.');
94		}
95
96		return SingletonPredictionContext::create($parent, $transition->followState->stateNumber);
97		}
98
99		/**
100		* This means only the {@see PredictionContext::empty()} (wildcard? not sure)
101		* context is in set.
102		*/
103	2	public function isEmpty() : bool
104		{
105	2	return $this === self::empty();
106		}
107
108	4	public function hasEmptyPath() : bool
109		{
110	4	return $this->getReturnState($this->getLength() - 1) === self::EMPTY_RETURN_STATE;
111		}
112
113	5	public function hashCode() : int
114		{
115	5	if ($this->cachedHashCode === null) {
116	2	$this->cachedHashCode = $this->computeHashCode();
117		}
118
119	5	return $this->cachedHashCode;
120		}
121
122		abstract protected function computeHashCode() : int;
123		abstract public function getLength() : int;
124		abstract public function getParent(int $index) : ?self;
125		abstract public function getReturnState(int $index) : int;
126		abstract public function __toString() : string;
127
128		public static function merge(
129		PredictionContext $a,
130		PredictionContext $b,
131		bool $rootIsWildcard,
132		?DoubleKeyMap $mergeCache
133		) : PredictionContext {
134		// share same graph if both same
135		if ($a->equals($b)) {
136		return $a;
137		}
138
139		if ($a instanceof SingletonPredictionContext && $b instanceof SingletonPredictionContext) {
140		return self::mergeSingletons($a, $b, $rootIsWildcard, $mergeCache);
141		}
142
143		// At least one of a or b is array
144		// If one is $ and rootIsWildcard, return $ as * wildcard
145		if ($rootIsWildcard) {
146		if ($a instanceof EmptyPredictionContext) {
147		return $a;
148		}
149
150		if ($b instanceof EmptyPredictionContext) {
151		return $b;
152		}
153		}
154
155		// convert singleton so both are arrays to normalize
156		if ($a instanceof SingletonPredictionContext) {
157		$a = ArrayPredictionContext::fromOne($a);
158		}
159
160		if ($b instanceof SingletonPredictionContext) {
161		$b = ArrayPredictionContext::fromOne($b);
162		}
163
164		if (!$a instanceof ArrayPredictionContext \|\| !$b instanceof ArrayPredictionContext) {
165		throw new \RuntimeException('Unexpected transition type.');
166		}
167
168		return self::mergeArrays($a, $b, $rootIsWildcard, $mergeCache);
169		}
170
171		/**
172		* Merge two {@see SingletonPredictionContext} instances.
173		*
174		* Stack tops equal, parents merge is same; return left graph.
175		*
176		* Same stack top, parents differ; merge parents giving array node, then
177		* remainders of those graphs. A new root node is created to point to the
178		* merged parents.
179		*
180		* Different stack tops pointing to same parent. Make array node for the
181		* root where both element in the root point to the same (original)
182		* parent.
183		*
184		* Different stack tops pointing to different parents. Make array node for
185		* the root where each element points to the corresponding original
186		* parent.
187		*
188		* @param SingletonPredictionContext $a The first {@see SingletonPredictionContext}
189		* @param SingletonPredictionContext $b The second {@see SingletonPredictionContext}
190		* @param bool $rootIsWildcard `true` if this is a local-context merge,
191		* otherwise false to indicate a full-context merge
192		*/
193		public static function mergeSingletons(
194		SingletonPredictionContext $a,
195		SingletonPredictionContext $b,
196		bool $rootIsWildcard,
197		?DoubleKeyMap $mergeCache
198		) : PredictionContext {
199		if ($mergeCache !== null) {
200		$previous = $mergeCache->getByTwoKeys($a, $b);
201
202		if ($previous !== null) {
203		return $previous;
204		}
205
206		$previous = $mergeCache->getByTwoKeys($b, $a);
207
208		if ($previous !== null) {
209		return $previous;
210		}
211		}
212
213		$rootMerge = self::mergeRoot($a, $b, $rootIsWildcard);
		0 ignored issues – show Bug introduced 2020-12-10 12:02 UTC by Report Bug Copy Issue Report Are you sure the assignment to `$rootMerge` is correct as `self::mergeRoot($a, $b, $rootIsWildcard)` targeting `Antlr\Antlr4\Runtime\Pre...ionContext::mergeRoot()` seems to always return null. This check looks for function or method calls that always return null and whose return value is assigned to a variable. class A { function getObject() { return null; } } $a = new A(); $object = $a->getObject(); The method `getObject()` can return nothing but null, so it makes no sense to assign that value to a variable. The reason is most likely that a function or method is imcomplete or has been reduced for debug purposes. Loading history...
214
215		if ($rootMerge !== null) {
		0 ignored issues – show introduced 2020-12-10 12:02 UTC by Report Bug Copy Issue Report The condition `$rootMerge !== null` is always `false`. Loading history...
216		if ($mergeCache !== null) {
217		$mergeCache->set($a, $b, $rootMerge);
218		}
219
220		return $rootMerge;
221		}
222
223		if ($a->returnState === $b->returnState) {
224		if ($a->parent === null \|\| $b->parent === null) {
225		throw new \RuntimeException('Unexpected null parents.');
226		}
227
228		$parent = self::merge($a->parent, $b->parent, $rootIsWildcard, $mergeCache);
229
230		// If parent is same as existing a or b parent or reduced to a parent, return it
231		if ($parent === $a->parent) {
232		return $a; // ax + bx = ax, if a=b
233		}
234
235		if ($parent === $b->parent) {
236		return $b; // ax + bx = bx, if a=b
237		}
238
239		// Else: ax + ay = a'[x,y]
240		//
241		// Merge parents x and y, giving array node with x,y then remainders
242		// of those graphs. dup a, a' points at merged array new joined parent
243		// so create new singleton pointing to it, a'
244		$spc = SingletonPredictionContext::create($parent, $a->returnState);
245
246		if ($mergeCache !== null) {
247		$mergeCache->set($a, $b, $spc);
248		}
249		return $spc;
250		} else {
251		// a != b payloads differ
252		// see if we can collapse parents due to $+x parents if local ctx
253		$singleParent = null;
254
255		if ($a === $b \|\| ($a->parent !== null && $a->parent === $b->parent)) {
256		// ax +
257		// bx =
258		// [a,b]x
259		$singleParent = $a->parent;
260		}
261
262		if ($singleParent !== null) {
263		// parents are same
264		// sort payloads and use same parent
265		$payloads = [$a->returnState, $b->returnState];
266
267		if ($a->returnState > $b->returnState) {
268		$payloads[0] = $b->returnState;
269		$payloads[1] = $a->returnState;
270		}
271
272		$parents = [$singleParent, $singleParent];
273		$apc = new ArrayPredictionContext($parents, $payloads);
274
275		if ($mergeCache !== null) {
276		$mergeCache->set($a, $b, $apc);
277		}
278
279		return $apc;
280		}
281
282		// parents differ and can't merge them. Just pack together
283		// into array; can't merge.
284		// ax + by = [ax,by]
285		$payloads = [$a->returnState, $b->returnState];
286		$parents = [$a->parent, $b->parent];
287
288		if ($a->returnState > $b->returnState) {
289		// sort by payload
290		$payloads[0] = $b->returnState;
291		$payloads[1] = $a->returnState;
292		$parents = [$b->parent, $a->parent];
293		}
294
295		$a_ = new ArrayPredictionContext($parents, $payloads);
296
297		if ($mergeCache !== null) {
298		$mergeCache->set($a, $b, $a_);
299		}
300
301		return $a_;
302		}
303		}
304
305		/**
306		* Handle case where at least one of `a` or `b` is
307		* {@see PredictionContext::empty()}. In the following diagrams, the symbol
308		* `$` is used to represent {@see PredictionContext::empty()}.
309		*
310		* Local-Context Merges
311		*
312		* These local-context merge operations are used when `rootIsWildcard`
313		* is true.
314		*
315		* {@see PredictionContext::empty()} is superset of any graph; return
316		* {@see PredictionContext::empty()}.
317		*
318		* [[img src="images/LocalMerge_EmptyRoot.svg" type="image/svg+xml"]]
319		*
320		* {@see PredictionContext::empty()} and anything is `#EMPTY`, so merged parent is
321		* `#EMPTY`; return left graph
322		*
323		* [[img src="images/LocalMerge_EmptyParent.svg" type="image/svg+xml"]]
324		*
325		* Special case of last merge if local context.
326		*
327		* [[img src="images/LocalMerge_DiffRoots.svg" type="image/svg+xml"]]
328		*
329		* Full-Context Merges
330		*
331		* These full-context merge operations are used when `rootIsWildcard`
332		* is false.
333		*
334		* Must keep all contexts; {@see PredictionContext::empty()} in array is
335		* a special value (and null parent).
336		*
337		* [[img src="images/FullMerge_EmptyRoot.svg" type="image/svg+xml"]]
338		*
339		* [[img src="images/FullMerge_SameRoot.svg" type="image/svg+xml"]]
340		*/
341		public static function mergeRoot(
342		SingletonPredictionContext $a,
343		SingletonPredictionContext $b,
344		bool $rootIsWildcard
345		) : ?PredictionContext {
346		if ($rootIsWildcard) {
347		if ($a === self::empty()) {
		0 ignored issues – show introduced 2020-12-10 12:02 UTC by Report Bug Copy Issue Report The condition `$a === self::empty()` is always `false`. Loading history...
348		return self::empty();// // + b =//
349		}
350
351		if ($b === self::empty()) {
		0 ignored issues – show introduced 2020-12-10 12:02 UTC by Report Bug Copy Issue Report The condition `$b === self::empty()` is always `false`. Loading history...
352		return self::empty();// a +// =//
353		}
354		} else {
355		if ($a === self::empty() && $b === self::empty()) {
		0 ignored issues – show introduced 2020-12-10 12:02 UTC by Report Bug Copy Issue Report The condition `$a === self::empty()` is always `false`. Loading history...
356		return self::empty();// $ + $ = $
357		}
358
359		if ($a === self::empty()) {
		0 ignored issues – show introduced 2020-12-10 12:02 UTC by Report Bug Copy Issue Report The condition `$a === self::empty()` is always `false`. Loading history...
360		// $ + x = [$,x]
361		$payloads = [$b->returnState, self::EMPTY_RETURN_STATE];
362		$parents = [$b->parent, null];
363
364		return new ArrayPredictionContext($parents, $payloads);
365		}
366
367		if ($b === self::empty()) {
		0 ignored issues – show introduced 2020-12-10 12:02 UTC by Report Bug Copy Issue Report The condition `$b === self::empty()` is always `false`. Loading history...
368		// x + $ = [$,x] ($ is always first if present)
369		$payloads = [$a->returnState, self::EMPTY_RETURN_STATE];
370		$parents = [$a->parent, null];
371
372		return new ArrayPredictionContext($parents, $payloads);
373		}
374		}
375
376		return null;
377		}
378
379		/**
380		* Merge two {@see ArrayPredictionContext} instances.
381		*
382		* Different tops, different parents.
383		*
384		* [[img src="images/ArrayMerge_DiffTopDiffPar.svg" type="image/svg+xml"]]
385		*
386		* Shared top, same parents.
387		*
388		* [[img src="images/ArrayMerge_ShareTopSamePar.svg" type="image/svg+xml"]]
389		*
390		* Shared top, different parents.
391		*
392		* [[img src="images/ArrayMerge_ShareTopDiffPar.svg" type="image/svg+xml"]]
393		*
394		* Shared top, all shared parents.
395		*
396		* [[img src="images/ArrayMerge_ShareTopSharePar.svg" type="image/svg+xml"]]
397		*
398		* Equal tops, merge parents and reduce top to
399		* {@see SingletonPredictionContext}.
400		*
401		* [[img src="images/ArrayMerge_EqualTop.svg" type="image/svg+xml"]]
402		*/
403		public static function mergeArrays(
404		ArrayPredictionContext $a,
405		ArrayPredictionContext $b,
406		bool $rootIsWildcard,
407		?DoubleKeyMap $mergeCache
408		) : PredictionContext {
409		if ($mergeCache !== null) {
410		$previous = $mergeCache->getByTwoKeys($a, $b);
411
412		if ($previous !== null) {
413		return $previous;
414		}
415
416		$previous = $mergeCache->getByTwoKeys($b, $a);
417
418		if ($previous !== null) {
419		return $previous;
420		}
421		}
422
423		// merge sorted payloads a + b => M
424		$i = 0;// walks a
425		$j = 0;// walks b
426		$k = 0;// walks target M array
427
428		$mergedReturnStates = [];
429		$mergedParents = [];
430
431		// walk and merge to yield mergedParents, mergedReturnStates
432		while ($i < \count($a->returnStates) && $j < \count($b->returnStates)) {
433		$a_parent = $a->parents[$i];
434		$b_parent = $b->parents[$j];
435
436		if ($a->returnStates[$i] === $b->returnStates[$j]) {
437		// same payload (stack tops are equal), must yield merged singleton
438		$payload = $a->returnStates[$i];
439
440		// $+$ = $
441		$bothDollars = $payload === self::EMPTY_RETURN_STATE && $a_parent === null && $b_parent === null;
442		$ax_ax = ($a_parent !== null && $b_parent !== null && $a_parent->equals($b_parent));// ax+ax
443		// ->
444		// ax
445
446		if ($bothDollars \|\| $ax_ax) {
447		$mergedParents[$k] = $a_parent;// choose left
448		$mergedReturnStates[$k] = $payload;
449		} else {
450		if ($a_parent === null \|\| $b_parent === null) {
451		throw new \RuntimeException('Unexpected null parents.');
452		}
453
454		// ax+ay -> a'[x,y]
455		$mergedParent = self::merge($a_parent, $b_parent, $rootIsWildcard, $mergeCache);
456		$mergedParents[$k] = $mergedParent;
457		$mergedReturnStates[$k] = $payload;
458		}
459
460		$i++;// hop over left one as usual
461		$j++;// but also skip one in right side since we merge
462		} elseif ($a->returnStates[$i] < $b->returnStates[$j]) {
463		// copy a[i] to M
464		$mergedParents[$k] = $a_parent;
465		$mergedReturnStates[$k] = $a->returnStates[$i];
466		$i++;
467		} else {
468		// b > a, copy b[j] to M
469		$mergedParents[$k] = $b_parent;
470		$mergedReturnStates[$k] = $b->returnStates[$j];
471		$j++;
472		}
473
474		$k++;
475		}
476
477		// copy over any payloads remaining in either array
478		if ($i < \count($a->returnStates)) {
479		for ($p = $i, $count = \count($a->returnStates); $p < $count; $p++) {
480		$mergedParents[$k] = $a->parents[$p];
481		$mergedReturnStates[$k] = $a->returnStates[$p];
482		$k++;
483		}
484		} else {
485		for ($p = $j, $count = \count($b->returnStates); $p < $count; $p++) {
486		$mergedParents[$k] = $b->parents[$p];
487		$mergedReturnStates[$k] = $b->returnStates[$p];
488		$k++;
489		}
490		}
491
492		// trim merged if we combined a few that had same stack tops
493		if ($k < \count($mergedParents)) {
494		// write index < last position; trim
495		if ($k === 1) {
496		// for just one merged element, return singleton top
497		$a_ = SingletonPredictionContext::create($mergedParents[0], $mergedReturnStates[0]);
498
499		if ($mergeCache !== null) {
500		$mergeCache->set($a, $b, $a_);
501		}
502
503		return $a_;
504		}
505
506		$mergedParents = \array_slice($mergedParents, 0, $k);
507		$mergedReturnStates = \array_slice($mergedReturnStates, 0, $k);
508		}
509
510		self::combineCommonParents($mergedParents);
511
512		$M = new ArrayPredictionContext($mergedParents, $mergedReturnStates);
513
514		// if we created same array as a or b, return that instead
515		// TODO: track whether this is possible above during merge sort for speed
516		if ($M === $a) {
517		if ($mergeCache !== null) {
518		$mergeCache->set($a, $b, $a);
519		}
520
521		return $a;
522		}
523
524		if ($M === $b) {
525		if ($mergeCache !== null) {
526		$mergeCache->set($a, $b, $b);
527		}
528
529		return $b;
530		}
531
532		if ($mergeCache !== null) {
533		$mergeCache->set($a, $b, $M);
534		}
535
536		return $M;
537		}
538
539		/**
540		* @param array<PredictionContext> $parents
541		*/
542		protected static function combineCommonParents(array &$parents) : void
543		{
544		$uniqueParents = new \SplObjectStorage();
545
546		foreach ($parents as $parent) {
547		if (!$uniqueParents->contains($parent)) {
548		$uniqueParents[$parent] = $parent;
549		}
550		}
551
552		foreach ($parents as $i => $parent) {
553		$parents[$i] = $uniqueParents[$parent];
554		}
555		}
556
557		/**
558		* @param array<PredictionContext\|null> $visited
559		*/
560	3	public static function getCachedPredictionContext(
561		PredictionContext $context,
562		PredictionContextCache $contextCache,
563		array &$visited
564		) : self {
565	3	if ($context->isEmpty()) {
566	2	return $context;
567		}
568
569	2	$existing = $visited[\spl_object_id($context)] ?? null;
570
571	2	if ($existing !== null) {
572		return $existing;
573		}
574
575	2	$existing = $contextCache->get($context);
576
577	2	if ($existing !== null) {
578	2	$visited[\spl_object_id($context)] = $existing;
579
580	2	return $existing;
581		}
582
583	1	$changed = false;
584	1	$parents = [];
585	1	for ($i = 0; $i < $context->getLength(); $i++) {
586	1	$parentContext = $context->getParent($i);
587
588	1	if ($parentContext === null) {
589		continue;
590		}
591
592	1	$parent = self::getCachedPredictionContext($parentContext, $contextCache, $visited);
593
594	1	if ($changed \|\| ($parentContext !== null && !$parent->equals($parentContext))) {
595		if (!$changed) {
596		$parents = [];
597
598		for ($j = 0; $j < $context->getLength(); $j++) {
599		$parents[$j] = $context->getParent($j);
600		}
601
602		$changed = true;
603		}
604
605		$parents[$i] = $parent;
606		}
607		}
608
609	1	if (!$changed) {
		0 ignored issues – show introduced 2020-12-10 12:02 UTC by Report Bug Copy Issue Report The condition `$changed` is always `false`. Loading history...
610	1	$contextCache->add($context);
611
612	1	$visited[\spl_object_id($context)] = $context;
613
614	1	return $context;
615		}
616
617		$updated = null;
618
619		if (\count($parents) === 0) {
620		$updated = self::empty();
621		} elseif (\count($parents) === 1) {
622		$updated = SingletonPredictionContext::create($parents[0], $context->getReturnState(0));
623		} else {
624		if (!$context instanceof ArrayPredictionContext) {
625		throw new \RuntimeException('Unexpected context type.');
626		}
627
628		$updated = new ArrayPredictionContext($parents, $context->returnStates);
629		}
630
631		$contextCache->add($updated);
632		$visited[\spl_object_id($updated)] = $updated;
633		$visited[\spl_object_id($context)] = $updated;
634
635		return $updated;
636		}
637
638		public function __clone()
639		{
640		$this->cachedHashCode = null;
641		}
642		}
643

SetBased / antlr-php-runtime

PredictionContext::hashCode() A last analyzed 2020-12-10 13:11 UTC

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like

PredictionContext::hashCode() A
last analyzed 2020-12-10 13:11 UTC