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.DFA;
8 
9 import antlr.v4.runtime.IllegalStateException;
10 import antlr.v4.runtime.UnsupportedOperationException;
11 import antlr.v4.runtime.Vocabulary;
12 import antlr.v4.runtime.VocabularyImpl;
13 import antlr.v4.runtime.atn.ATNConfigSet;
14 import antlr.v4.runtime.atn.DecisionState;
15 import antlr.v4.runtime.atn.StarLoopEntryState;
16 import antlr.v4.runtime.dfa.DFASerializer;
17 import antlr.v4.runtime.dfa.DFAState;
18 import antlr.v4.runtime.dfa.LexerDFASerializer;
19 import std.algorithm.sorting;
20 import std.conv;
21 
22 /**
23  * A set of DFA states
24  */
25 class DFA
26 {
27 
28     /**
29      * A set of all DFA states. Use {@link Map} so we can get old state back
30      * ({@link Set} only allows you to see if it's there).
31      */
32     public DFAState[DFAState] states;
33 
34     public DFAState s0;
35 
36     public int decision;
37 
38     /**
39      * From which ATN state did we create this DFA?
40      */
41     public DecisionState atnStartState;
42 
43     /**
44      * {@code true} if this DFA is for a precedence decision; otherwise,
45      *  {@code false}. This is the backing field for {@link #isPrecedenceDfa}.
46      */
47     public bool precedenceDfa;
48 
49     public this(DecisionState atnStartState)
50     {
51         this(atnStartState, 0);
52     }
53 
54     public this(DecisionState atnStartState, int decision)
55     {
56         this.atnStartState = atnStartState;
57         this.decision = decision;
58         bool precedenceDfa = false;
59         if (cast(StarLoopEntryState)atnStartState) {
60             if ((cast(StarLoopEntryState)atnStartState).isPrecedenceDecision) {
61                 precedenceDfa = true;
62                 DFAState precedenceState = new DFAState(new ATNConfigSet());
63                 precedenceState.edges = new DFAState[0];
64                 precedenceState.isAcceptState = false;
65                 precedenceState.requiresFullContext = false;
66                 this.s0 = precedenceState;
67             }
68         }
69         this.precedenceDfa = precedenceDfa;
70     }
71 
72     /**
73      * Gets whether this DFA is a precedence DFA. Precedence DFAs use a special
74      * start state {@link #s0} which is not stored in {@link #states}. The
75      * {@link DFAState#edges} array for this start state contains outgoing edges
76      * supplying individual start states corresponding to specific precedence
77      * values.
78      *
79      *  @return {@code true} if this is a precedence DFA; otherwise,
80      *  {@code false}.
81      *  @see Parser#getPrecedence()
82      */
83     public bool isPrecedenceDfa()
84     {
85         return precedenceDfa;
86     }
87 
88     /**
89      * Get the start state for a specific precedence value.
90      *
91      *  @param precedence The current precedence.
92      *  @return The start state corresponding to the specified precedence, or
93      *  {@code null} if no start state exists for the specified precedence.
94      *
95      *  @throws IllegalStateException if this is not a precedence DFA.
96      *  @see #isPrecedenceDfa()
97      */
98     public DFAState getPrecedenceStartState(int precedence)
99     {
100         if (!isPrecedenceDfa()) {
101             throw new IllegalStateException("Only precedence DFAs may contain a precedence start state.");
102         }
103         // s0.edges is never null for a precedence DFA
104         if (precedence < 0 || precedence >= s0.edges.length) {
105             return null;
106         }
107         return s0.edges[precedence];
108     }
109 
110     /**
111      * Set the start state for a specific precedence value.
112      *
113      * @param precedence The current precedence.
114      * @param startState The start state corresponding to the specified
115      * precedence.
116      *
117      * @throws IllegalStateException if this is not a precedence DFA.
118      * @see #isPrecedenceDfa()
119      * @uml
120      * @final
121      */
122     public final void setPrecedenceStartState(int precedence, DFAState startState)
123     {
124         if (!isPrecedenceDfa()) {
125             throw new IllegalStateException("Only precedence DFAs may contain a precedence start state.");
126         }
127 
128         if (precedence < 0) {
129             return;
130         }
131 
132         // synchronization on s0 here is ok. when the DFA is turned into a
133         // precedence DFA, s0 will be initialized once and not updated again
134         synchronized (s0) {
135             // s0.edges is never null for a precedence DFA
136             if (precedence >= s0.edges.length) {
137                 s0.edges.length = precedence + 1;
138             }
139             s0.edges[precedence] = startState;
140         }
141     }
142 
143     /**
144      * Sets whether this is a precedence DFA.
145      *
146      * @param precedenceDfa {@code true} if this is a precedence DFA; otherwise,
147      * {@code false}
148      *
149      * @throws UnsupportedOperationException if {@code precedenceDfa} does not
150      * match the value of {@link #isPrecedenceDfa} for the current DFA.
151      *
152      * @deprecated This method no longer performs any action.
153      */
154     public void setPrecedenceDfa(bool precedenceDfa)
155     {
156         if (precedenceDfa != isPrecedenceDfa()) {
157             throw new UnsupportedOperationException("The precedenceDfa field cannot change after a DFA is constructed.");
158         }
159     }
160 
161     public DFAState[] getStates()
162     {
163         DFAState[] result = states.keys;
164         result.sort!("a.stateNumber < b.stateNumber");
165         return result;
166     }
167 
168     /**
169      * @uml
170      * @override
171      */
172     public override string toString()
173     {
174         return to!string(new VocabularyImpl(null, null, null));
175     }
176 
177     public string toString(string[] tokenNames)
178     {
179         if (s0 is null)
180             return "";
181         DFASerializer serializer = new DFASerializer(this, tokenNames);
182         return serializer.toString();
183     }
184 
185     public string toString(Vocabulary vocabulary)
186     {
187         if (s0 is null) {
188             return "";
189         }
190 
191         DFASerializer serializer = new DFASerializer(this, vocabulary);
192         return serializer.toString;
193     }
194 
195     public string toLexerString()
196     {
197         if (s0  is null) return "";
198         DFASerializer serializer = new LexerDFASerializer(this);
199         return serializer.toString;
200     }
201 
202 }
203 
204 version(unittest) {
205     import dshould : equal, not, be, should;
206     import std.typecons : tuple;
207     import unit_threaded;
208 
209     @Tags("DFA")
210     @("Construction")
211     unittest
212         {
213             import std.stdio;
214             import antlr.v4.runtime.atn.TokensStartState;
215             DecisionState startState = new TokensStartState;
216             DFA dfa = new DFA(startState);
217             dfa.should.not.be(null);
218         }
219 }