1 /*
2  * Copyright (c) 2012-2018 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.atn.ATN;
8 
9 import std.conv;
10 import antlr.v4.runtime.IllegalArgumentException;
11 import antlr.v4.runtime.RuleContext;
12 import antlr.v4.runtime.atn.ATNState;
13 import antlr.v4.runtime.atn.ATNType;
14 import antlr.v4.runtime.atn.DecisionState;
15 import antlr.v4.runtime.atn.RuleStartState;
16 import antlr.v4.runtime.atn.RuleStopState;
17 import antlr.v4.runtime.atn.LL1Analyzer;
18 import antlr.v4.runtime.atn.RuleTransition;
19 import antlr.v4.runtime.Token;
20 import antlr.v4.runtime.TokenConstantDefinition;
21 import antlr.v4.runtime.atn.TokensStartState;
22 import antlr.v4.runtime.atn.LexerAction;
23 import antlr.v4.runtime.misc.IntervalSet;
24 
25 /**
26  * Class implementation adapted from Java code
27  */
28 class ATN
29 {
30 
31     public static immutable int INVALID_ALT_NUMBER = 0;
32 
33     public ATNState[] states;
34 
35     /**
36      * Each subrule/rule is a decision point and we must track them so we
37      * can go back later and build DFA predictors for them.  This includes
38      * all the rules, subrules, optional blocks, ()+, ()* etc...
39      */
40     public DecisionState[] decisionToState;
41 
42     /**
43      * Maps from rule index to starting state number.
44      */
45     public RuleStartState[] ruleToStartState;
46 
47     /**
48      * Maps from rule index to stop state number.
49      */
50     public RuleStopState[] ruleToStopState;
51 
52     public TokensStartState[string] modeNameToStartState;
53 
54     /**
55      * The type of the ATN.
56      */
57     public ATNType grammarType;
58 
59     /**
60      * The maximum value for any symbol recognized by a transition in the ATN.
61      */
62     public int maxTokenType;
63 
64     /**
65      * For lexer ATNs, this maps the rule index to the resulting token type.
66      * For parser ATNs, this maps the rule index to the generated bypass token
67      * type if the
68      * {@link ATNDeserializationOptions#isGenerateRuleBypassTransitions}
69      * deserialization option was specified; otherwise, this is {@code null}.
70      */
71     public int[] ruleToTokenType;
72 
73     /**
74      * For lexer ATNs, this is an array of {@link LexerAction} objects which may
75      * be referenced by action transitions in the ATN.
76      */
77     public LexerAction[] lexerActions;
78 
79     public TokensStartState[] modeToStartState;
80 
81     /**
82      * Used for runtime deserialization of ATNs from strings
83      */
84     public this(ATNType grammarType, int maxTokenType)
85     {
86         this.grammarType = grammarType;
87         this.maxTokenType = maxTokenType;
88     }
89 
90     /**
91      * Compute the set of valid tokens that can occur starting in state {@code s}.
92      * If {@code ctx} is null, the set of tokens will not include what can follow
93      * the rule surrounding {@code s}. In other words, the set will be
94      * restricted to tokens reachable staying within {@code s}'s rule.
95      */
96     public IntervalSet nextTokens(ATNState s, RuleContext ctx)
97     {
98         LL1Analyzer anal = new LL1Analyzer(this);
99         IntervalSet next = anal.LOOK(s, ctx);
100         return next;
101     }
102 
103     /**
104      * Compute the set of valid tokens that can occur starting in {@code s} and
105      * staying in same rule. {@link Token#EPSILON} is in set if we reach end of
106      * rule.
107      */
108     public IntervalSet nextTokens(ATNState s)
109     {
110         debug {
111             import std.stdio;
112             writefln("ATN: nextTokens(ATNState s) %s", s);
113         }
114         if (s.nextTokenWithinRule !is null ) {
115             return s.nextTokenWithinRule;
116         }
117         s.nextTokenWithinRule = nextTokens(s, null);
118         s.nextTokenWithinRule.setReadonly(true);
119         return s.nextTokenWithinRule;
120     }
121 
122     public void addState(ATNState state)
123     {
124         if (state) {
125             state.atn = this;
126             state.stateNumber = to!int(states.length);
127         }
128         states ~= state;
129     }
130 
131     public void removeState(ATNState state)
132     {
133         states[state.stateNumber] = null; // just free mem, don't shift states in list
134     }
135 
136     public int defineDecisionState(DecisionState s)
137     {
138         decisionToState ~= s;
139         s.decision = to!int(decisionToState.length)-1;
140         return s.decision;
141     }
142 
143     public DecisionState getDecisionState(int decision)
144     {
145         if (decisionToState.length > 0) {
146             return decisionToState[decision];
147         }
148         return null;
149     }
150 
151     public int getNumberOfDecisions()
152     {
153         return to!int(decisionToState.length);
154     }
155 
156     /**
157      * Computes the set of input symbols which could follow ATN state number
158      * {@code stateNumber} in the specified full {@code context}. This method
159      * considers the complete parser context, but does not evaluate semantic
160      * predicates (i.e. all predicates encountered during the calculation are
161      * assumed true). If a path in the ATN exists from the starting state to the
162      * {@link RuleStopState} of the outermost context without matching any
163      * symbols, {@link Token#EOF} is added to the returned set.
164      *
165      * <p>If {@code context} is {@code null}, it is treated as
166      * {@link ParserRuleContext#EMPTY}.</p>
167      *
168      *  @param stateNumber the ATN state number
169      *  @param context the full parse context
170      *  @return The set of potentially valid input symbols which could follow the
171      *  specified state in the specified context.
172      *  @throws IllegalArgumentException if the ATN does not contain a state with
173      *  number {@code stateNumber}
174      */
175     public IntervalSet getExpectedTokens(int stateNumber, RuleContext context)
176     {
177         if (stateNumber < 0 || stateNumber >= states.length) {
178             throw new IllegalArgumentException("Invalid state number.");
179         }
180 
181         RuleContext ctx = context;
182         ATNState s = states[stateNumber];
183         IntervalSet following = nextTokens(s);
184         if (!following.contains(TokenConstantDefinition.EPSILON)) {
185             return following;
186         }
187 
188         IntervalSet expected = new IntervalSet();
189         expected.addAll(following);
190         expected.remove(TokenConstantDefinition.EPSILON);
191         while (ctx !is null && ctx.invokingState >= 0 && following.contains(TokenConstantDefinition.EPSILON)) {
192             ATNState invokingState = states[ctx.invokingState];
193             RuleTransition rt = cast(RuleTransition)invokingState.transition(0);
194             following = nextTokens(rt.followState);
195             expected.addAll(following);
196             expected.remove(TokenConstantDefinition.EPSILON);
197             ctx = ctx.parent;
198         }
199 
200         if (following.contains(TokenConstantDefinition.EPSILON)) {
201             expected.add(TokenConstantDefinition.EOF);
202         }
203 
204         return expected;
205     }
206 
207 }