1 /*
2  * Copyright (c) 2012-2020 The ANTLR Project. All rights reserved.
3  * Use of this file is governed by the BSD 3-clause license that
4  * can be found in the LICENSE.txt file in the project root.
5  */
6 
7 module antlr.v4.runtime.dfa.DFAState;
8 
9 import std.conv;
10 import std.array;
11 import antlr.v4.runtime.misc.MurmurHash;
12 import antlr.v4.runtime.atn.ATNConfig;
13 import antlr.v4.runtime.atn.ATNConfigSet;
14 import antlr.v4.runtime.atn.LexerActionExecutor;
15 import antlr.v4.runtime.dfa.PredPrediction;
16 
17 /**
18  * A DFA state represents a set of possible ATN configurations.
19  * As Aho, Sethi, Ullman p. 117 says "The DFA uses its state
20  * to keep track of all possible states the ATN can be in after
21  * reading each input symbol.  That is to say, after reading
22  * input a1a2..an, the DFA is in a state that represents the
23  * subset T of the states of the ATN that are reachable from the
24  * ATN's start state along some path labeled a1a2..an."
25  * In conventional NFA→DFA conversion, therefore, the subset T
26  * would be a bitset representing the set of states the
27  * ATN could be in.  We need to track the alt predicted by each
28  * state as well, however.  More importantly, we need to maintain
29  * a stack of states, tracking the closure operations as they
30  * jump from rule to rule, emulating rule invocations (method calls).
31  * I have to add a stack to simulate the proper lookahead sequences for
32  * the underlying LL grammar from which the ATN was derived.
33  *
34  * <p>I use a set of ATNConfig objects not simple states.  An ATNConfig
35  * is both a state (ala normal conversion) and a RuleContext describing
36  * the chain of rules (if any) followed to arrive at that state.</p>
37  *
38  * <p>A DFA state may have multiple references to a particular state,
39  * but with different ATN contexts (with same or different alts)
40  * meaning that state was reached via a different set of rule invocations.</p>
41  */
42 class DFAState
43 {
44 
45     public int stateNumber = -1;
46 
47     public ATNConfigSet configs = new ATNConfigSet;
48 
49     /**
50      * {@code edges[symbol]} points to target of symbol. Shift up by 1 so (-1)
51      * {@link Token#EOF} maps to {@code edges[0]}.
52      */
53     public DFAState[] edges;
54 
55     public bool isAcceptState = false;
56 
57     /**
58      * if accept state, what ttype do we match or alt do we predict?
59      * This is set to {@link ATN#INVALID_ALT_NUMBER} when {@link #predicates}{@code !=null} or
60      * {@link #requiresFullContext}.
61      */
62     public int prediction;
63 
64     public LexerActionExecutor lexerActionExecutor;
65 
66     /**
67      * Indicates that this state was created during SLL prediction that
68      * discovered a conflict between the configurations in the state. Future
69      * {@link ParserATNSimulator#execATN} invocations immediately jumped doing
70      * full context prediction if this field is true.
71      */
72     public bool requiresFullContext;
73 
74     /**
75      * During SLL parsing, this is a list of predicates associated with the
76      * ATN configurations of the DFA state. When we have predicates,
77      * {@link #requiresFullContext} is {@code false} since full context prediction evaluates predicates
78      * on-the-fly. If this is not null, then {@link #prediction} is
79      * {@link ATN#INVALID_ALT_NUMBER}.
80      *   *
81      * <p>We only use these for non-{@link #requiresFullContext} but conflicting states. That
82      * means we know from the context (it's $ or we don't dip into outer
83      * context) that it's an ambiguity not a conflict.</p>
84      *
85      * <p>This list is computed by {@link ParserATNSimulator#predicateDFAState}.</p>
86      */
87     public PredPrediction[] predicates;
88 
89     public this()
90     {
91     }
92 
93     public this(int stateNumber)
94     {
95         this.stateNumber = stateNumber;
96     }
97 
98     public this(ATNConfigSet configs)
99     {
100         this.configs = configs;
101     }
102 
103     /**
104      * Get the set of all alts mentioned by all ATN configurations in the
105      * DFA state.
106      */
107     public int[] getAltSet()
108     {
109         int[] alts;
110         if (configs) {
111             foreach (ATNConfig c; configs.configs) {
112                 alts ~= c.alt;
113             }
114         }
115         if (alts.length == 0) return null;
116         return alts;
117     }
118 
119     /**
120      * @uml
121      * @override
122      * @safe
123      * @nothrow
124      */
125     public override size_t toHash() @safe nothrow
126     {
127     size_t hash = MurmurHash.initialize(7);
128         hash = MurmurHash.update(hash, configs.toHash());
129         hash = MurmurHash.finish(hash, 1);
130         return hash;
131     }
132 
133     /**
134      * Two {@link DFAState} instances are equal if their ATN configuration sets
135      * are the same. This method is used to see if a state already exists.
136      *
137      * <p>Because the number of alternatives and number of ATN configurations are
138      * finite, there is a finite number of DFA states that can be processed.
139      * This is necessary to show that the algorithm terminates.</p>
140      *
141      * <p>Cannot test the DFA state numbers here because in
142      * {@link ParserATNSimulator#addDFAState} we need to know if any other state
143      * exists that has this exact set of ATN configurations. The
144      * {@link #stateNumber} is irrelevant.</p>
145      * @uml
146      * @override
147      */
148     public override bool opEquals(Object o)
149     {
150         // compare set of ATN configurations in this set with other
151         if (this is o) {
152             return true;
153         }
154         if (!cast(DFAState)o) {
155              return false;
156         }
157         // compare set of ATN configurations in this set with other
158         DFAState other = cast(DFAState)o;
159         // TODO: what to do when configs==null?
160         bool sameSet = this.configs.configs == other.configs.configs;
161         debug(DFAState)
162         {
163             import std.stdio;
164             writefln!"DFAState.equals: %s%s%s"(configs,
165                      (sameSet?"==":"!="), other.configs);
166         }
167         return sameSet;
168     }
169 
170     /**
171      * @uml
172      * @override
173      */
174     public override string toString()
175     {
176         auto buf = appender!string;
177         buf.put(to!string(stateNumber));
178         buf.put(":");
179         buf.put(configs.toString);
180         if (isAcceptState) {
181             buf.put("=>");
182             if (predicates !is null) {
183                 buf.put(to!string(predicates));
184             }
185             else {
186                 buf.put(to!string(prediction));
187             }
188         }
189         return buf.data;
190     }
191 
192 }