1<?php
2
3declare(strict_types=1);
4
5namespace Antlr\Antlr4\Runtime;
6
7use Antlr\Antlr4\Runtime\Atn\ATN;
8use Antlr\Antlr4\Runtime\Atn\ATNConfig;
9use Antlr\Antlr4\Runtime\Atn\States\ATNState;
10use Antlr\Antlr4\Runtime\Atn\States\RuleStopState;
11use Antlr\Antlr4\Runtime\Atn\Transitions\AbstractPredicateTransition;
12use Antlr\Antlr4\Runtime\Atn\Transitions\NotSetTransition;
13use Antlr\Antlr4\Runtime\Atn\Transitions\RuleTransition;
14use Antlr\Antlr4\Runtime\Atn\Transitions\Transition;
15use Antlr\Antlr4\Runtime\Atn\Transitions\WildcardTransition;
16use Antlr\Antlr4\Runtime\PredictionContexts\PredictionContext;
17use Antlr\Antlr4\Runtime\PredictionContexts\SingletonPredictionContext;
18use Antlr\Antlr4\Runtime\Utils\BitSet;
19use Antlr\Antlr4\Runtime\Utils\Set;
20
21class 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    public function __construct(ATN $atn)
33    {
34        $this->atn = $atn;
35    }
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    public function look(ATNState $s, ?ATNState $stopState, ?RuleContext $context) : IntervalSet
104    {
105        $r = new IntervalSet();
106        $seeThruPreds = true;// ignore preds; get all lookahead
107
108        $lookContext = $context !== null && $s->atn !== null ?
109            PredictionContext::fromRuleContext($s->atn, $context) :
110            null;
111
112        $this->lookRecursively(
113            $s,
114            $stopState,
115            $lookContext,
116            $r,
117            new Set(),
118            new BitSet(),
119            $seeThruPreds,
120            true
121        );
122
123        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    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        $c = new ATNConfig(null, $s, $context, null, 0);
185
186        if (!$lookBusy->add($c)) {
187            return;
188        }
189
190        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        if ($s instanceof RuleStopState) {
205            if ($context === null) {
206                $look->addOne(Token::EPSILON);
207
208                return;
209            }
210
211            if ($context->isEmpty() && $addEOF) {
212                $look->addOne(Token::EOF);
213
214                return;
215            }
216
217            if ($context !== PredictionContext::empty()) {
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        foreach ($s->getTransitions() as $t) {
248            if ($t instanceof RuleTransition) {
249                if ($calledRuleStack->contains($t->target->ruleIndex)) {
250                    continue;
251                }
252
253                $newContext = SingletonPredictionContext::create($context, $t->followState->stateNumber);
254
255                try {
256                    $calledRuleStack->add($t->target->ruleIndex);
257                    $this->lookRecursively(
258                        $t->target,
259                        $stopState,
260                        $newContext,
261                        $look,
262                        $lookBusy,
263                        $calledRuleStack,
264                        $seeThruPreds,
265                        $addEOF
266                    );
267                } finally {
268                    $calledRuleStack->remove($t->target->ruleIndex);
269                }
270            } elseif ($t instanceof AbstractPredicateTransition) {
271                if ($seeThruPreds) {
272                    $this->lookRecursively(
273                        $t->target,
274                        $stopState,
275                        $context,
276                        $look,
277                        $lookBusy,
278                        $calledRuleStack,
279                        $seeThruPreds,
280                        $addEOF
281                    );
282                } else {
283                    $look->addOne(self::HIT_PRED);
284                }
285            } elseif ($t->isEpsilon()) {
286                $this->lookRecursively(
287                    $t->target,
288                    $stopState,
289                    $context,
290                    $look,
291                    $lookBusy,
292                    $calledRuleStack,
293                    $seeThruPreds,
294                    $addEOF
295                );
296            } elseif ($t instanceof WildcardTransition) {
297                $look->addRange(Token::MIN_USER_TOKEN_TYPE, $this->atn->maxTokenType);
298            } else {
299                $set = $t->label();
300
301                if ($set !== null) {
302                    if ($t instanceof NotSetTransition) {
303                        $set = $set->complement(IntervalSet::fromRange(
304                            Token::MIN_USER_TOKEN_TYPE,
305                            $this->atn->maxTokenType
306                        ));
307                    }
308
309                    if ($set !== null) {
310                        $look->addSet($set);
311                    }
312                }
313            }
314        }
315    }
316}
317