1/*
2 * [The "BSD license"]
3 *  Copyright (c) 2010 Terence Parr
4 *  All rights reserved.
5 *
6 *  Redistribution and use in source and binary forms, with or without
7 *  modification, are permitted provided that the following conditions
8 *  are met:
9 *  1. Redistributions of source code must retain the above copyright
10 *      notice, this list of conditions and the following disclaimer.
11 *  2. Redistributions in binary form must reproduce the above copyright
12 *      notice, this list of conditions and the following disclaimer in the
13 *      documentation and/or other materials provided with the distribution.
14 *  3. The name of the author may not be used to endorse or promote products
15 *      derived from this software without specific prior written permission.
16 *
17 *  THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 *  IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 *  OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 *  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 *  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 *  NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 *  DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 *  THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 *  (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 *  THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28package org.antlr.analysis;
29
30import org.antlr.tool.ErrorManager;
31import org.antlr.tool.GrammarAST;
32import org.antlr.tool.Rule;
33
34/** A state within an NFA. At most 2 transitions emanate from any NFA state. */
35public class NFAState extends State {
36	// I need to distinguish between NFA decision states for (...)* and (...)+
37	// during NFA interpretation.
38	public static final int LOOPBACK = 1;
39	public static final int BLOCK_START = 2;
40	public static final int OPTIONAL_BLOCK_START = 3;
41	public static final int BYPASS = 4;
42	public static final int RIGHT_EDGE_OF_BLOCK = 5;
43
44	public static final int MAX_TRANSITIONS = 2;
45
46	/** How many transitions; 0, 1, or 2 transitions */
47	int numTransitions = 0;
48	public Transition[] transition = new Transition[MAX_TRANSITIONS];
49
50	/** For o-A->o type NFA tranitions, record the label that leads to this
51	 *  state.  Useful for creating rich error messages when we find
52	 *  insufficiently (with preds) covered states.
53	 */
54	public Label incidentEdgeLabel;
55
56	/** Which NFA are we in? */
57	public NFA nfa = null;
58
59	/** What's its decision number from 1..n? */
60	protected int decisionNumber = 0;
61
62	/** Subrules (...)* and (...)+ have more than one decision point in
63	 *  the NFA created for them.  They both have a loop-exit-or-stay-in
64	 *  decision node (the loop back node).  They both have a normal
65	 *  alternative block decision node at the left edge.  The (...)* is
66	 *  worse as it even has a bypass decision (2 alts: stay in or bypass)
67	 *  node at the extreme left edge.  This is not how they get generated
68	 *  in code as a while-loop or whatever deals nicely with either.  For
69	 *  error messages (where I need to print the nondeterministic alts)
70	 *  and for interpretation, I need to use the single DFA that is created
71	 *  (for efficiency) but interpret the results differently depending
72	 *  on which of the 2 or 3 decision states uses the DFA.  For example,
73	 *  the DFA will always report alt n+1 as the exit branch for n real
74	 *  alts, so I need to translate that depending on the decision state.
75	 *
76	 *  If decisionNumber>0 then this var tells you what kind of decision
77	 *  state it is.
78	 */
79	public int decisionStateType;
80
81	/** What rule do we live in? */
82	public Rule enclosingRule;
83
84	/** During debugging and for nondeterminism warnings, it's useful
85	 *  to know what relationship this node has to the original grammar.
86	 *  For example, "start of alt 1 of rule a".
87	 */
88	protected String description;
89
90	/** Associate this NFAState with the corresponding GrammarAST node
91	 *  from which this node was created.  This is useful not only for
92	 *  associating the eventual lookahead DFA with the associated
93	 *  Grammar position, but also for providing users with
94	 *  nondeterminism warnings.  Mainly used by decision states to
95	 *  report line:col info.  Could also be used to track line:col
96	 *  for elements such as token refs.
97	 */
98	public GrammarAST associatedASTNode;
99
100	/** Is this state the sole target of an EOT transition? */
101	protected boolean EOTTargetState = false;
102
103	/** Jean Bovet needs in the GUI to know which state pairs correspond
104	 *  to the start/stop of a block.
105	  */
106	public int endOfBlockStateNumber = State.INVALID_STATE_NUMBER;
107
108	public NFAState(NFA nfa) {
109		this.nfa = nfa;
110	}
111
112	public int getNumberOfTransitions() {
113		return numTransitions;
114	}
115
116	public void addTransition(Transition e) {
117		if ( e==null ) {
118			throw new IllegalArgumentException("You can't add a null transition");
119		}
120		if ( numTransitions>transition.length ) {
121			throw new IllegalArgumentException("You can only have "+transition.length+" transitions");
122		}
123		if ( e!=null ) {
124			transition[numTransitions] = e;
125			numTransitions++;
126			// Set the "back pointer" of the target state so that it
127			// knows about the label of the incoming edge.
128			Label label = e.label;
129			if ( label.isAtom() || label.isSet() ) {
130				if ( ((NFAState)e.target).incidentEdgeLabel!=null ) {
131					ErrorManager.internalError("Clobbered incident edge");
132				}
133				((NFAState)e.target).incidentEdgeLabel = e.label;
134			}
135		}
136	}
137
138	/** Used during optimization to reset a state to have the (single)
139	 *  transition another state has.
140	 */
141	public void setTransition0(Transition e) {
142		if ( e==null ) {
143			throw new IllegalArgumentException("You can't use a solitary null transition");
144		}
145		transition[0] = e;
146		transition[1] = null;
147		numTransitions = 1;
148	}
149
150	public Transition transition(int i) {
151		return transition[i];
152	}
153
154	/** The DFA decision for this NFA decision state always has
155	 *  an exit path for loops as n+1 for n alts in the loop.
156	 *  That is really useful for displaying nondeterministic alts
157	 *  and so on, but for walking the NFA to get a sequence of edge
158	 *  labels or for actually parsing, we need to get the real alt
159	 *  number.  The real alt number for exiting a loop is always 1
160	 *  as transition 0 points at the exit branch (we compute DFAs
161	 *  always for loops at the loopback state).
162	 *
163	 *  For walking/parsing the loopback state:
164	 * 		1 2 3 display alt (for human consumption)
165	 * 		2 3 1 walk alt
166	 *
167	 *  For walking the block start:
168	 * 		1 2 3 display alt
169	 * 		1 2 3
170	 *
171	 *  For walking the bypass state of a (...)* loop:
172	 * 		1 2 3 display alt
173	 * 		1 1 2 all block alts map to entering loop exit means take bypass
174	 *
175	 *  Non loop EBNF do not need to be translated; they are ignored by
176	 *  this method as decisionStateType==0.
177	 *
178	 *  Return same alt if we can't translate.
179	 */
180	public int translateDisplayAltToWalkAlt(int displayAlt) {
181		NFAState nfaStart = this;
182		if ( decisionNumber==0 || decisionStateType==0 ) {
183			return displayAlt;
184		}
185		int walkAlt = 0;
186		// find the NFA loopback state associated with this DFA
187		// and count number of alts (all alt numbers are computed
188		// based upon the loopback's NFA state.
189		/*
190		DFA dfa = nfa.grammar.getLookaheadDFA(decisionNumber);
191		if ( dfa==null ) {
192			ErrorManager.internalError("can't get DFA for decision "+decisionNumber);
193		}
194		*/
195		int nAlts = nfa.grammar.getNumberOfAltsForDecisionNFA(nfaStart);
196		switch ( nfaStart.decisionStateType ) {
197			case LOOPBACK :
198				walkAlt = displayAlt % nAlts + 1; // rotate right mod 1..3
199				break;
200			case BLOCK_START :
201			case OPTIONAL_BLOCK_START :
202				walkAlt = displayAlt; // identity transformation
203				break;
204			case BYPASS :
205				if ( displayAlt == nAlts ) {
206					walkAlt = 2; // bypass
207				}
208				else {
209					walkAlt = 1; // any non exit branch alt predicts entering
210				}
211				break;
212		}
213		return walkAlt;
214	}
215
216	// Setter/Getters
217
218	/** What AST node is associated with this NFAState?  When you
219	 *  set the AST node, I set the node to point back to this NFA state.
220	 */
221	public void setDecisionASTNode(GrammarAST decisionASTNode) {
222		decisionASTNode.setNFAStartState(this);
223		this.associatedASTNode = decisionASTNode;
224	}
225
226	public String getDescription() {
227		return description;
228	}
229
230	public void setDescription(String description) {
231		this.description = description;
232	}
233
234	public int getDecisionNumber() {
235		return decisionNumber;
236	}
237
238	public void setDecisionNumber(int decisionNumber) {
239		this.decisionNumber = decisionNumber;
240	}
241
242	public boolean isEOTTargetState() {
243		return EOTTargetState;
244	}
245
246	public void setEOTTargetState(boolean eot) {
247		EOTTargetState = eot;
248	}
249
250	public boolean isDecisionState() {
251		return decisionStateType>0;
252	}
253
254	public String toString() {
255		return String.valueOf(stateNumber);
256	}
257
258}
259
260