1<?php
2
3declare(strict_types=1);
4
5namespace Antlr\Antlr4\Runtime\PredictionContexts;
6
7use Antlr\Antlr4\Runtime\Atn\ATN;
8use Antlr\Antlr4\Runtime\Atn\Transitions\RuleTransition;
9use Antlr\Antlr4\Runtime\Comparison\Hashable;
10use Antlr\Antlr4\Runtime\RuleContext;
11use Antlr\Antlr4\Runtime\Utils\DoubleKeyMap;
12
13abstract 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    public function __construct()
54    {
55        $this->id = self::$globalNodeCount++;
56    }
57
58    public static function empty() : EmptyPredictionContext
59    {
60        static $empty;
61
62        if ($empty === null) {
63            static::$globalNodeCount--;
64            $empty = new EmptyPredictionContext();
65            $empty->id = 0;
66        }
67
68        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    public static function fromRuleContext(ATN $atn, ?RuleContext $outerContext) : PredictionContext
76    {
77        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        if ($outerContext->getParent() === null || $outerContext === RuleContext::emptyContext()) {
84            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    public function isEmpty() : bool
104    {
105        return $this === self::empty();
106    }
107
108    public function hasEmptyPath() : bool
109    {
110        return $this->getReturnState($this->getLength() - 1) === self::EMPTY_RETURN_STATE;
111    }
112
113    public function hashCode() : int
114    {
115        if ($this->cachedHashCode === null) {
116            $this->cachedHashCode = $this->computeHashCode();
117        }
118
119        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);
214
215        if ($rootMerge !== null) {
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()) {
348                return self::empty();// // + b =//
349            }
350
351            if ($b === self::empty()) {
352                return self::empty();// a +// =//
353            }
354        } else {
355            if ($a === self::empty() && $b === self::empty()) {
356                return self::empty();// $ + $ = $
357            }
358
359            if ($a === self::empty()) {
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()) {
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    public static function getCachedPredictionContext(
561        PredictionContext $context,
562        PredictionContextCache $contextCache,
563        array &$visited
564    ) : self {
565        if ($context->isEmpty()) {
566            return $context;
567        }
568
569        $existing = $visited[\spl_object_id($context)] ?? null;
570
571        if ($existing !== null) {
572            return $existing;
573        }
574
575        $existing = $contextCache->get($context);
576
577        if ($existing !== null) {
578            $visited[\spl_object_id($context)] = $existing;
579
580            return $existing;
581        }
582
583        $changed = false;
584        $parents = [];
585        for ($i = 0; $i < $context->getLength(); $i++) {
586            $parentContext = $context->getParent($i);
587
588            if ($parentContext === null) {
589                continue;
590            }
591
592            $parent = self::getCachedPredictionContext($parentContext, $contextCache, $visited);
593
594            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        if (!$changed) {
610            $contextCache->add($context);
611
612            $visited[\spl_object_id($context)] = $context;
613
614            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