1<?php
2
3declare(strict_types=1);
4
5namespace Antlr\Antlr4\Runtime\Dfa;
6
7use Antlr\Antlr4\Runtime\Atn\ATNConfigSet;
8use Antlr\Antlr4\Runtime\Atn\LexerActionExecutor;
9use Antlr\Antlr4\Runtime\Comparison\Equality;
10use Antlr\Antlr4\Runtime\Comparison\Hashable;
11use Antlr\Antlr4\Runtime\Comparison\Hasher;
12
13/**
14 * A DFA state represents a set of possible ATN configurations.
15 * As Aho, Sethi, Ullman p. 117 says "The DFA uses its state
16 * to keep track of all possible states the ATN can be in after
17 * reading each input symbol. That is to say, after reading
18 * input a1a2..an, the DFA is in a state that represents the
19 * subset T of the states of the ATN that are reachable from the
20 * ATN's start state along some path labeled a1a2..an."
21 * In conventional NFA&rarr;DFA conversion, therefore, the subset T
22 * would be a bitset representing the set of states the
23 * ATN could be in. We need to track the alt predicted by each
24 * state as well, however. More importantly, we need to maintain
25 * a stack of states, tracking the closure operations as they
26 * jump from rule to rule, emulating rule invocations (method calls).
27 * I have to add a stack to simulate the proper lookahead sequences for
28 * the underlying LL grammar from which the ATN was derived.
29 *
30 * I use a set of ATNConfig objects not simple states. An ATNConfig
31 * is both a state (ala normal conversion) and a RuleContext describing
32 * the chain of rules (if any) followed to arrive at that state.
33 *
34 * A DFA state may have multiple references to a particular state,
35 * but with different ATN contexts (with same or different alts)
36 * meaning that state was reached via a different set of rule invocations.
37 */
38final class DFAState implements Hashable
39{
40    /** @var int */
41    public $stateNumber;
42
43    /** @var ATNConfigSet */
44    public $configs;
45
46    /**
47     * `edges[symbol]` points to target of symbol. Shift up by 1 so (-1)
48     * {@see Token::EOF} maps to `edges[0]`.
49     *
50     * @var \SplFixedArray<DFAState>|null
51     */
52    public $edges;
53
54    /** @var bool */
55    public $isAcceptState = false;
56
57    /**
58     * If accept state, what ttype do we match or alt do we predict?
59     * This is set to {@see ATN::INVALID_ALT_NUMBER)} when
60     * `{@see DFAState::$predicates} !== null` or {@see DFAState::$requiresFullContext}.
61     *
62     * @var int
63     */
64    public $prediction = 0;
65
66    /** @var LexerActionExecutor|null */
67    public $lexerActionExecutor;
68
69    /**
70     * Indicates that this state was created during SLL prediction that
71     * discovered a conflict between the configurations in the state. Future
72     * {@see ParserATNSimulator::execATN()} invocations immediately jumped doing
73     * full context prediction if this field is true.
74     *
75     * @var bool
76     */
77    public $requiresFullContext = false;
78
79    /**
80     * During SLL parsing, this is a list of predicates associated with the
81     * ATN configurations of the DFA state. When we have predicates,
82     * {@see DFAState::$requiresFullContext} is `false` since full context
83     * prediction evaluates predicates on-the-fly. If this is not null, then
84     * {@see DFAState::$prediction} is {@see ATN::INVALID_ALT_NUMBER}.
85     *
86     * We only use these for non-{@see DFAState::$requiresFullContext} bu
87     * conflicting states. That means we know from the context (it's $ or we
88     * don't dip into outer context) that it's an ambiguity not a conflict.
89     *
90     * This list is computed by {@see ParserATNSimulator::predicateDFAState()}.
91     *
92     * @var array<PredPrediction>|null
93     */
94    public $predicates;
95
96    public function __construct(?ATNConfigSet $configs = null, int $stateNumber = -1)
97    {
98        $this->configs = $configs ?? new ATNConfigSet();
99        $this->stateNumber = $stateNumber;
100    }
101
102    /**
103     * Two {@see DFAState} instances are equal if their ATN configuration sets
104     * are the same. This method is used to see if a state already exists.
105     *
106     * Because the number of alternatives and number of ATN configurations are
107     * finite, there is a finite number of DFA states that can be processed.
108     * This is necessary to show that the algorithm terminates.
109     *
110     * Cannot test the DFA state numbers here because in
111     * {@see ParserATNSimulator::addDFAState()} we need to know if any other state
112     * exists that has this exact set of ATN configurations. The
113     * {@see DFAState::$stateNumber} is irrelevant.
114     */
115    public function equals(object $other) : bool
116    {
117        if ($this === $other) {
118            return true;
119        }
120
121        if (!$other instanceof self) {
122            return false;
123        }
124
125        // Compare set of ATN configurations in this set with other
126        return Equality::equals($this->configs, $other->configs);
127    }
128
129    public function __toString() : string
130    {
131        $s = \sprintf('%d:%s', $this->stateNumber, (string) $this->configs);
132
133        if ($this->isAcceptState) {
134            $s .= '=>';
135
136            if ($this->predicates !== null) {
137                $s .= \sprintf('[%s]', \implode(', ', $this->predicates));
138            } else {
139                $s .= $this->prediction;
140            }
141        }
142
143        return $s;
144    }
145
146    public function hashCode() : int
147    {
148        return Hasher::hash($this->configs);
149    }
150}
151