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

LL1Analyzer::getDecisionLookahead() A
last analyzed 2020-12-10 13:11 UTC

↳ Parent: LL1Analyzer

Complexity

Conditions	5
Paths	4

Size

Total Lines	33
Code Lines	21

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	0
CRAP Score	30

Importance

Changes	1
Bugs	0	Features	0

Metric	Value
cc	5
eloc	21
c	1
b	0
f	0
nc	4
nop	1
dl	0
loc	33
ccs	0
cts	18
cp	0
crap	30
rs	9.2728

<?php

declare(strict_types=1);

namespace Antlr\Antlr4\Runtime;

use Antlr\Antlr4\Runtime\Atn\ATN;
use Antlr\Antlr4\Runtime\Atn\ATNConfig;
use Antlr\Antlr4\Runtime\Atn\States\ATNState;
use Antlr\Antlr4\Runtime\Atn\States\RuleStopState;
use Antlr\Antlr4\Runtime\Atn\Transitions\AbstractPredicateTransition;
use Antlr\Antlr4\Runtime\Atn\Transitions\NotSetTransition;
use Antlr\Antlr4\Runtime\Atn\Transitions\RuleTransition;
use Antlr\Antlr4\Runtime\Atn\Transitions\Transition;
use Antlr\Antlr4\Runtime\Atn\Transitions\WildcardTransition;
use Antlr\Antlr4\Runtime\PredictionContexts\PredictionContext;
use Antlr\Antlr4\Runtime\PredictionContexts\SingletonPredictionContext;
use Antlr\Antlr4\Runtime\Utils\BitSet;
use Antlr\Antlr4\Runtime\Utils\Set;

class LL1Analyzer
{
    /**
     * Special value added to the lookahead sets to indicate that we hit
     * a predicate during analysis if `seeThruPreds === false`.
     */
    public const HIT_PRED = Token::INVALID_TYPE;

    /** @var ATN */
    public $atn;

    public function __construct(ATN $atn)
    {
        $this->atn = $atn;
    }

    /**
     * Calculates the SLL(1) expected lookahead set for each outgoing transition
     * of an {@see ATNState}. The returned array has one element for each
     * outgoing transition in `s`. If the closure from transition
     * `i` leads to a semantic predicate before matching a symbol, the
     * element at index `i` of the result will be `null`.
     *
     * @param ATNState|null $s The ATN state
     *
     * @return array<IntervalSet|null>|null The expected symbols for
     *                                      each outgoing transition of `s`.
     */
    public function getDecisionLookahead(?ATNState $s) : ?array
    {
        if ($s === null) {
            return null;
        }

        $look = [];
        for ($alt = 0; $alt < $s->getNumberOfTransitions(); $alt++) {
            $interval = new IntervalSet();
            $lookBusy = new Set();
            $seeThruPreds = false; // fail to get lookahead upon pred

            $this->lookRecursively(
                $s->getTransition($alt)->target,
                null,
                PredictionContext::empty(),
                $interval,
                $lookBusy,
                new BitSet(),
                $seeThruPreds,
                false
            );

            // Wipe out lookahead for this alternative if we found nothing
            // or we had a predicate when we !seeThruPreds
            if ($interval->length() === 0 || $interval->contains(self::HIT_PRED)) {
                $look[$alt] = null;
            } else {
                $look[$alt] = $interval;
            }
        }

        return $look;
    }

    /**
     * Compute set of tokens that can follow `s` in the ATN in the
     * specified `context`.
     *
     * If `context` is `null` and the end of the rule containing
     * `s` is reached, {@see Token::EPSILON} is added to the result set.
     * If `context` is not `null` and the end of the outermost rule is
     * reached, {@see Token::EOF} is added to the result set.
     *
     * @param ATNState         $s         The ATN state.
     * @param ATNState|null    $stopState The ATN state to stop at. This can be
     *                                    a {@see BlockEndState} to detect
     *                                    epsilon paths through a closure.
     * @param RuleContext|null $context   The complete parser context, or `null`
     *                                    if the context should be ignored.
     *
     * @return IntervalSet The set of tokens that can follow `s` in the ATN
     *                     in the specified `context`.
     */
    public function look(ATNState $s, ?ATNState $stopState, ?RuleContext $context) : IntervalSet
    {
        $r = new IntervalSet();
        $seeThruPreds = true;// ignore preds; get all lookahead

        $lookContext = $context !== null && $s->atn !== null ?
            PredictionContext::fromRuleContext($s->atn, $context) :
            null;

        $this->lookRecursively(
            $s,
            $stopState,
            $lookContext,
            $r,
            new Set(),
            new BitSet(),
            $seeThruPreds,
            true
        );

        return $r;
    }

    /**
     * Compute set of tokens that can follow `s` in the ATN in the
     * specified `context`.
     *
     * If `context` is `null` and `stopState` or the end of the
     * rule containing `s` is reached, {@see Token::EPSILON} is added to
     * the result set. If `context` is not `null` and `addEOF` is
     * `true` and `stopState` or the end of the outermost rule is
     * reached, {@see Token::EOF} is added to the result set.
     *
     * @param ATNState               $s               The ATN state.
     * @param ATNState|null          $stopState       The ATN state to stop at.
     *                                                This can be a
     *                                                {@see BlockEndState} to
     *                                                detect epsilon paths
     *                                                through a closure.
     * @param PredictionContext|null $context         The outer context, or `null`
     *                                                if the outer context should
     *                                                not be used.
     * @param IntervalSet            $look            The result lookahead set.
     * @param Set                    $lookBusy        A set used for preventing
     *                                                epsilon closures in the ATN
     *                                                from causing a stack overflow.
     *                                                Outside code should pass
     *                                                `new Set<ATNConfig>}` for
     *                                                this argument.
     * @param BitSet                 $calledRuleStack A set used for preventing
     *                                                left recursion in the ATN
     *                                                from causing a stack overflow.
     *                                                Outside code should pass
     *                                                `new BitSet()` for
     *                                                this argument.
     * @param bool                   $seeThruPreds    `true` to true semantic
     *                                                predicates as implicitly
     *                                                `true` and "see through them",
     *                                                otherwise `false` to treat
     *                                                semantic predicates as
     *                                                opaque and add
     *                                                {@see self::HIT_PRED} to
     *                                                the result if one is
     *                                                encountered.
     * @param bool                   $addEOF          Add {@see Token::EOF} to
     *                                                the result if the end of
     *                                                the outermost context is
     *                                                reached. This parameter
     *                                                has no effect if `context`
     *                                                is `null`.
     */
    protected function lookRecursively(
        ATNState $s,
        ?ATNState $stopState,
        ?PredictionContext $context,
        IntervalSet $look,
        Set $lookBusy,
        BitSet $calledRuleStack,
        bool $seeThruPreds,
        bool $addEOF
    ) : void {
        $c = new ATNConfig(null, $s, $context, null, 0);

        if (!$lookBusy->add($c)) {
            return;
        }

        if ($stopState !== null && $s->equals($stopState)) {
            if ($context === null) {
                $look->addOne(Token::EPSILON);

                return;
            }

            if ($context->isEmpty() && $addEOF) {
                $look->addOne(Token::EOF);

                return;
            }
        }

        if ($s instanceof RuleStopState) {
            if ($context === null) {
                $look->addOne(Token::EPSILON);

                return;
            }

            if ($context->isEmpty() && $addEOF) {
                $look->addOne(Token::EOF);

                return;
            }

            if ($context !== PredictionContext::empty()) {

                // run thru all possible stack tops in ctx
                $removed = $calledRuleStack->contains($s->ruleIndex);

                try {
                    $calledRuleStack->remove($s->ruleIndex);
                    for ($i = 0; $i < $context->getLength(); $i++) {
                        $returnState = $this->atn->states[$context->getReturnState($i)];
                        $this->lookRecursively(
                            $returnState,
                            $stopState,
                            $context->getParent($i),
                            $look,
                            $lookBusy,
                            $calledRuleStack,
                            $seeThruPreds,
                            $addEOF
                        );
                    }
                } finally {
                    if ($removed) {
                        $calledRuleStack->add($s->ruleIndex);
                    }
                }

                return;
            }
        }

        /** @var Transition $t */
        foreach ($s->getTransitions() as $t) {
            if ($t instanceof RuleTransition) {
                if ($calledRuleStack->contains($t->target->ruleIndex)) {
                    continue;
                }

                $newContext = SingletonPredictionContext::create($context, $t->followState->stateNumber);

                try {
                    $calledRuleStack->add($t->target->ruleIndex);
                    $this->lookRecursively(
                        $t->target,
                        $stopState,
                        $newContext,
                        $look,
                        $lookBusy,
                        $calledRuleStack,
                        $seeThruPreds,
                        $addEOF
                    );
                } finally {
                    $calledRuleStack->remove($t->target->ruleIndex);
                }
            } elseif ($t instanceof AbstractPredicateTransition) {
                if ($seeThruPreds) {
                    $this->lookRecursively(
                        $t->target,
                        $stopState,
                        $context,
                        $look,
                        $lookBusy,
                        $calledRuleStack,
                        $seeThruPreds,
                        $addEOF
                    );
                } else {
                    $look->addOne(self::HIT_PRED);
                }
            } elseif ($t->isEpsilon()) {
                $this->lookRecursively(
                    $t->target,
                    $stopState,
                    $context,
                    $look,
                    $lookBusy,
                    $calledRuleStack,
                    $seeThruPreds,
                    $addEOF
                );
            } elseif ($t instanceof WildcardTransition) {
                $look->addRange(Token::MIN_USER_TOKEN_TYPE, $this->atn->maxTokenType);
            } else {
                $set = $t->label();
class A
{
    function getObject()
    {
        return null;
    }

}

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

                if ($set !== null) {
                    if ($t instanceof NotSetTransition) {
                        $set = $set->complement(IntervalSet::fromRange(
                            Token::MIN_USER_TOKEN_TYPE,
                            $this->atn->maxTokenType
                        ));
                    }

                    if ($set !== null) {
                        $look->addSet($set);
                    }
                }
            }
        }
    }
}


1		<?php
2
3		declare(strict_types=1);
4
5		namespace Antlr\Antlr4\Runtime;
6
7		use Antlr\Antlr4\Runtime\Atn\ATN;
8		use Antlr\Antlr4\Runtime\Atn\ATNConfig;
9		use Antlr\Antlr4\Runtime\Atn\States\ATNState;
10		use Antlr\Antlr4\Runtime\Atn\States\RuleStopState;
11		use Antlr\Antlr4\Runtime\Atn\Transitions\AbstractPredicateTransition;
12		use Antlr\Antlr4\Runtime\Atn\Transitions\NotSetTransition;
13		use Antlr\Antlr4\Runtime\Atn\Transitions\RuleTransition;
14		use Antlr\Antlr4\Runtime\Atn\Transitions\Transition;
15		use Antlr\Antlr4\Runtime\Atn\Transitions\WildcardTransition;
16		use Antlr\Antlr4\Runtime\PredictionContexts\PredictionContext;
17		use Antlr\Antlr4\Runtime\PredictionContexts\SingletonPredictionContext;
18		use Antlr\Antlr4\Runtime\Utils\BitSet;
19		use Antlr\Antlr4\Runtime\Utils\Set;
20
21		class LL1Analyzer
22		{
23		/**
24		* Special value added to the lookahead sets to indicate that we hit
25		* a predicate during analysis if `seeThruPreds === false`.
26		*/
27		public const HIT_PRED = Token::INVALID_TYPE;
28
29		/** @var ATN */
30		public $atn;
31
32	2	public function __construct(ATN $atn)
33		{
34	2	$this->atn = $atn;
35	2	}
36
37		/**
38		* Calculates the SLL(1) expected lookahead set for each outgoing transition
39		* of an {@see ATNState}. The returned array has one element for each
40		* outgoing transition in `s`. If the closure from transition
41		* `i` leads to a semantic predicate before matching a symbol, the
42		* element at index `i` of the result will be `null`.
43		*
44		* @param ATNState\|null $s The ATN state
45		*
46		* @return array<IntervalSet\|null>\|null The expected symbols for
47		* each outgoing transition of `s`.
48		*/
49		public function getDecisionLookahead(?ATNState $s) : ?array
50		{
51		if ($s === null) {
52		return null;
53		}
54
55		$look = [];
56		for ($alt = 0; $alt < $s->getNumberOfTransitions(); $alt++) {
57		$interval = new IntervalSet();
58		$lookBusy = new Set();
59		$seeThruPreds = false; // fail to get lookahead upon pred
60
61		$this->lookRecursively(
62		$s->getTransition($alt)->target,
63		null,
64		PredictionContext::empty(),
65		$interval,
66		$lookBusy,
67		new BitSet(),
68		$seeThruPreds,
69		false
70		);
71
72		// Wipe out lookahead for this alternative if we found nothing
73		// or we had a predicate when we !seeThruPreds
74		if ($interval->length() === 0 \|\| $interval->contains(self::HIT_PRED)) {
75		$look[$alt] = null;
76		} else {
77		$look[$alt] = $interval;
78		}
79		}
80
81		return $look;
82		}
83
84		/**
85		* Compute set of tokens that can follow `s` in the ATN in the
86		* specified `context`.
87		*
88		* If `context` is `null` and the end of the rule containing
89		* `s` is reached, {@see Token::EPSILON} is added to the result set.
90		* If `context` is not `null` and the end of the outermost rule is
91		* reached, {@see Token::EOF} is added to the result set.
92		*
93		* @param ATNState $s The ATN state.
94		* @param ATNState\|null $stopState The ATN state to stop at. This can be
95		* a {@see BlockEndState} to detect
96		* epsilon paths through a closure.
97		* @param RuleContext\|null $context The complete parser context, or `null`
98		* if the context should be ignored.
99		*
100		* @return IntervalSet The set of tokens that can follow `s` in the ATN
101		* in the specified `context`.
102		*/
103	2	public function look(ATNState $s, ?ATNState $stopState, ?RuleContext $context) : IntervalSet
104		{
105	2	$r = new IntervalSet();
106	2	$seeThruPreds = true;// ignore preds; get all lookahead
107
108	2	$lookContext = $context !== null && $s->atn !== null ?
109	1	PredictionContext::fromRuleContext($s->atn, $context) :
110	2	null;
111
112	2	$this->lookRecursively(
113	2	$s,
114		$stopState,
115		$lookContext,
116		$r,
117	2	new Set(),
118	2	new BitSet(),
119		$seeThruPreds,
120	2	true
121		);
122
123	2	return $r;
124		}
125
126		/**
127		* Compute set of tokens that can follow `s` in the ATN in the
128		* specified `context`.
129		*
130		* If `context` is `null` and `stopState` or the end of the
131		* rule containing `s` is reached, {@see Token::EPSILON} is added to
132		* the result set. If `context` is not `null` and `addEOF` is
133		* `true` and `stopState` or the end of the outermost rule is
134		* reached, {@see Token::EOF} is added to the result set.
135		*
136		* @param ATNState $s The ATN state.
137		* @param ATNState\|null $stopState The ATN state to stop at.
138		* This can be a
139		* {@see BlockEndState} to
140		* detect epsilon paths
141		* through a closure.
142		* @param PredictionContext\|null $context The outer context, or `null`
143		* if the outer context should
144		* not be used.
145		* @param IntervalSet $look The result lookahead set.
146		* @param Set $lookBusy A set used for preventing
147		* epsilon closures in the ATN
148		* from causing a stack overflow.
149		* Outside code should pass
150		* `new Set<ATNConfig>}` for
151		* this argument.
152		* @param BitSet $calledRuleStack A set used for preventing
153		* left recursion in the ATN
154		* from causing a stack overflow.
155		* Outside code should pass
156		* `new BitSet()` for
157		* this argument.
158		* @param bool $seeThruPreds `true` to true semantic
159		* predicates as implicitly
160		* `true` and "see through them",
161		* otherwise `false` to treat
162		* semantic predicates as
163		* opaque and add
164		* {@see self::HIT_PRED} to
165		* the result if one is
166		* encountered.
167		* @param bool $addEOF Add {@see Token::EOF} to
168		* the result if the end of
169		* the outermost context is
170		* reached. This parameter
171		* has no effect if `context`
172		* is `null`.
173		*/
174	2	protected function lookRecursively(
175		ATNState $s,
176		?ATNState $stopState,
177		?PredictionContext $context,
178		IntervalSet $look,
179		Set $lookBusy,
180		BitSet $calledRuleStack,
181		bool $seeThruPreds,
182		bool $addEOF
183		) : void {
184	2	$c = new ATNConfig(null, $s, $context, null, 0);
185
186	2	if (!$lookBusy->add($c)) {
187		return;
188		}
189
190	2	if ($stopState !== null && $s->equals($stopState)) {
191		if ($context === null) {
192		$look->addOne(Token::EPSILON);
193
194		return;
195		}
196
197		if ($context->isEmpty() && $addEOF) {
198		$look->addOne(Token::EOF);
199
200		return;
201		}
202		}
203
204	2	if ($s instanceof RuleStopState) {
205	2	if ($context === null) {
206	2	$look->addOne(Token::EPSILON);
207
208	2	return;
209		}
210
211		if ($context->isEmpty() && $addEOF) {
212		$look->addOne(Token::EOF);
213
214		return;
215		}
216
217		if ($context !== PredictionContext::empty()) {
		0 ignored issues – show introduced 2020-12-10 12:02 UTC by Report Bug Copy Issue Report The condition `$context !== Antlr\Antlr...dictionContext::empty()` is always `true`. Loading history...
218		// run thru all possible stack tops in ctx
219		$removed = $calledRuleStack->contains($s->ruleIndex);
220
221		try {
222		$calledRuleStack->remove($s->ruleIndex);
223		for ($i = 0; $i < $context->getLength(); $i++) {
224		$returnState = $this->atn->states[$context->getReturnState($i)];
225		$this->lookRecursively(
226		$returnState,
227		$stopState,
228		$context->getParent($i),
229		$look,
230		$lookBusy,
231		$calledRuleStack,
232		$seeThruPreds,
233		$addEOF
234		);
235		}
236		} finally {
237		if ($removed) {
238		$calledRuleStack->add($s->ruleIndex);
239		}
240		}
241
242		return;
243		}
244		}
245
246		/** @var Transition $t */
247	2	foreach ($s->getTransitions() as $t) {
248	2	if ($t instanceof RuleTransition) {
249	2	if ($calledRuleStack->contains($t->target->ruleIndex)) {
250		continue;
251		}
252
253	2	$newContext = SingletonPredictionContext::create($context, $t->followState->stateNumber);
254
255		try {
256	2	$calledRuleStack->add($t->target->ruleIndex);
257	2	$this->lookRecursively(
258	2	$t->target,
259		$stopState,
260		$newContext,
261		$look,
262		$lookBusy,
263		$calledRuleStack,
264		$seeThruPreds,
265		$addEOF
266		);
267	2	} finally {
268	2	$calledRuleStack->remove($t->target->ruleIndex);
269		}
270	2	} elseif ($t instanceof AbstractPredicateTransition) {
271	2	if ($seeThruPreds) {
272	2	$this->lookRecursively(
273	2	$t->target,
274		$stopState,
275		$context,
276		$look,
277		$lookBusy,
278		$calledRuleStack,
279		$seeThruPreds,
280		$addEOF
281		);
282		} else {
283	2	$look->addOne(self::HIT_PRED);
284		}
285	2	} elseif ($t->isEpsilon()) {
286	2	$this->lookRecursively(
287	2	$t->target,
288		$stopState,
289		$context,
290		$look,
291		$lookBusy,
292		$calledRuleStack,
293		$seeThruPreds,
294		$addEOF
295		);
296	2	} elseif ($t instanceof WildcardTransition) {
297		$look->addRange(Token::MIN_USER_TOKEN_TYPE, $this->atn->maxTokenType);
298		} else {
299	2	$set = $t->label();
		0 ignored issues – show Bug introduced 2020-12-10 12:02 UTC by Report Bug Copy Issue Report Are you sure the assignment to `$set` is correct as `$t->label()` targeting `Antlr\Antlr4\Runtime\Atn...ons\Transition::label()` 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...
300
301	2	if ($set !== null) {
302	2	if ($t instanceof NotSetTransition) {
303		$set = $set->complement(IntervalSet::fromRange(
304		Token::MIN_USER_TOKEN_TYPE,
305		$this->atn->maxTokenType
306		));
307		}
308
309	2	if ($set !== null) {
310	2	$look->addSet($set);
311		}
312		}
313		}
314		}
315	2	}
316		}
317

SetBased / antlr-php-runtime

LL1Analyzer::getDecisionLookahead() A last analyzed 2020-12-10 13:11 UTC

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like

LL1Analyzer::getDecisionLookahead() A
last analyzed 2020-12-10 13:11 UTC