1<?php
2
3declare(strict_types=1);
4
5namespace Antlr\Antlr4\Runtime\Atn;
6
7use Antlr\Antlr4\Runtime\Atn\Actions\LexerAction;
8use Antlr\Antlr4\Runtime\Atn\States\ATNState;
9use Antlr\Antlr4\Runtime\Atn\States\DecisionState;
10use Antlr\Antlr4\Runtime\Atn\States\RuleStartState;
11use Antlr\Antlr4\Runtime\Atn\States\RuleStopState;
12use Antlr\Antlr4\Runtime\Atn\States\TokensStartState;
13use Antlr\Antlr4\Runtime\Atn\Transitions\RuleTransition;
14use Antlr\Antlr4\Runtime\IntervalSet;
15use Antlr\Antlr4\Runtime\LL1Analyzer;
16use Antlr\Antlr4\Runtime\ParserRuleContext;
17use Antlr\Antlr4\Runtime\RuleContext;
18use Antlr\Antlr4\Runtime\Token;
19
20final class ATN
21{
22    public const INVALID_ALT_NUMBER = 0;
23    public const ATN_TYPE_LEXER = 0;
24    public const ATN_TYPE_PARSER = 1;
25
26    /** @var array<ATNState> */
27    public $states = [];
28
29    /**
30     * Each subrule/rule is a decision point and we must track them so we
31     * can go back later and build DFA predictors for them. This includes
32     * all the rules, subrules, optional blocks, ()+, ()* etc...
33     *
34     * @var array<DecisionState>
35     */
36    public $decisionToState = [];
37
38    /**
39     * Maps from rule index to starting state number.
40     *
41     * @var array<RuleStartState>
42     */
43    public $ruleToStartState = [];
44
45    /**
46     * Maps from rule index to stop state number.
47     *
48     * @var array<RuleStopState>
49     */
50    public $ruleToStopState = [];
51
52    /** @var array<TokensStartState> */
53    public $modeNameToStartState = [];
54
55    /**
56     * The type of the ATN.
57     *
58     * @var int
59     */
60    public $grammarType;
61
62    /**
63     * The maximum value for any symbol recognized by a transition in the ATN.
64     *
65     * @var int
66     */
67    public $maxTokenType;
68
69    /**
70     * For lexer ATNs, this maps the rule index to the resulting token type.
71     * For parser ATNs, this maps the rule index to the generated bypass token
72     * type if the
73     * {@see ATNDeserializationOptions::isGenerateRuleBypassTransitions()}
74     * deserialization option was specified; otherwise, this is `null`.
75     *
76     * @var array<int|null>
77     */
78    public $ruleToTokenType = [];
79
80    /**
81     * For lexer ATNs, this is an array of {@see LexerAction} objects which may
82     * be referenced by action transitions in the ATN.
83     *
84     * @var array<LexerAction>
85     */
86    public $lexerActions = [];
87
88    /** @var array<TokensStartState> */
89    public $modeToStartState = [];
90
91    /**
92     * Used for runtime deserialization of ATNs from strings
93     */
94    public function __construct(int $grammarType, int $maxTokenType)
95    {
96        $this->grammarType = $grammarType;
97        $this->maxTokenType = $maxTokenType;
98    }
99
100    /**
101     * Compute the set of valid tokens that can occur starting in state `state`.
102     * If `context` is null, the set of tokens will not include what can follow
103     * the rule surrounding `state`. In other words, the set will be
104     * restricted to tokens reachable staying within `state`'s rule.
105     */
106    public function nextTokensInContext(ATNState $state, ?RuleContext $context) : IntervalSet
107    {
108        return (new LL1Analyzer($this))->look($state, null, $context);
109    }
110
111    /**
112     * Compute the set of valid tokens that can occur starting in `state` and
113     * staying in same rule. {@see Token::EPSILON} is in set if we reach end of
114     * rule.
115     */
116    public function nextTokens(ATNState $state) : IntervalSet
117    {
118        if ($state->nextTokenWithinRule !== null) {
119            return $state->nextTokenWithinRule;
120        }
121
122        $state->nextTokenWithinRule = $this->nextTokensInContext($state, null);
123        $state->nextTokenWithinRule->setReadOnly(true);
124
125        return $state->nextTokenWithinRule;
126    }
127
128    public function addState(?ATNState $state) : void
129    {
130        if ($state === null) {
131            return;
132        }
133
134        $state->atn = $this;
135        $state->stateNumber = \count($this->states);
136
137        $this->states[] = $state;
138    }
139
140    public function removeState(ATNState $state) : void
141    {
142        // just free mem, don't shift states in list
143        unset($this->states[$state->stateNumber]);
144    }
145
146    public function defineDecisionState(DecisionState $s) : int
147    {
148        $this->decisionToState[] = $s;
149
150        $s->decision = \count($this->decisionToState) - 1;
151
152        return $s->decision;
153    }
154
155    public function getDecisionState(int $decision) : ?DecisionState
156    {
157        if (\count($this->decisionToState) === 0) {
158            return null;
159        }
160
161        return $this->decisionToState[$decision];
162    }
163
164    public function getNumberOfDecisions() : int
165    {
166        return \count($this->decisionToState);
167    }
168
169    /**
170     * Computes the set of input symbols which could follow ATN state number
171     * `stateNumber` in the specified full `context`. This method
172     * considers the complete parser context, but does not evaluate semantic
173     * predicates (i.e. all predicates encountered during the calculation are
174     * assumed true). If a path in the ATN exists from the starting state to the
175     * {@see RuleStopState} of the outermost context without matching any
176     * symbols, {@see Token::EOF} is added to the returned set.
177     *
178     * If `context` is `null`, it is treated as {@see ParserRuleContext::EMPTY}.
179     *
180     * @param int         $stateNumber The ATN state number
181     * @param RuleContext $context     The full parse context
182     *
183     * @return IntervalSet The set of potentially valid input symbols which could
184     *                     follow the specified state in the specified context.
185     *
186     * @throws \RuntimeException
187     */
188    public function getExpectedTokens(int $stateNumber, ?RuleContext $context) : IntervalSet
189    {
190        if ($stateNumber < 0 || $stateNumber >= \count($this->states)) {
191            throw new \InvalidArgumentException('Invalid state number.');
192        }
193
194        $s = $this->states[$stateNumber];
195        $following = $this->nextTokens($s);
196
197        if (!$following->contains(Token::EPSILON)) {
198            return $following;
199        }
200
201        $expected = new IntervalSet();
202
203        $expected->addSet($following);
204        $expected->removeOne(Token::EPSILON);
205
206        if ($context === null) {
207            $context = ParserRuleContext::emptyContext();
208        }
209
210        while ($context !== null && $context->invokingState >= 0 && $following->contains(Token::EPSILON)) {
211            $invokingState = $this->states[$context->invokingState];
212            $transition = $invokingState->getTransition(0);
213
214            if (!$transition instanceof RuleTransition) {
215                throw new \RuntimeException('Unexpected transition type.');
216            }
217
218            $following = $this->nextTokens($transition->followState);
219
220            $expected->addSet($following);
221            $expected->removeOne(Token::EPSILON);
222
223            $context = $context->getParent();
224        }
225
226        if ($following->contains(Token::EPSILON)) {
227            $expected->addOne(Token::EOF);
228        }
229
230        return $expected;
231    }
232}
233