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
30/** A tree node for tracking the call chains for NFAs that invoke
31 *  other NFAs.  These trees only have to point upwards to their parents
32 *  so we can walk back up the tree (i.e., pop stuff off the stack).  We
33 *  never walk from stack down down through the children.
34 *
35 *  Each alt predicted in a decision has its own context tree,
36 *  representing all possible return nodes.  The initial stack has
37 *  EOF ("$") in it.  So, for m alternative productions, the lookahead
38 *  DFA will have m NFAContext trees.
39 *
40 *  To "push" a new context, just do "new NFAContext(context-parent, state)"
41 *  which will add itself to the parent.  The root is NFAContext(null, null).
42 *
43 *  The complete context for an NFA configuration is the set of invoking states
44 *  on the path from this node thru the parent pointers to the root.
45 */
46public class NFAContext {
47	/** This is similar to Bermudez's m constant in his LAR(m) where
48	 *  you bound the stack so your states don't explode.  The main difference
49	 *  is that I bound only recursion on the stack, not the simple stack size.
50	 *  This looser constraint will let the conversion roam further to find
51	 *  lookahead to resolve a decision.
52	 *
53	 *  Bermudez's m operates differently as it is his LR stack depth
54	 *  I'm pretty sure it therefore includes all stack symbols.  Here I
55	 *  restrict the size of an NFA configuration to be finite because a
56	 *  stack component may mention the same NFA invocation state at
57	 *  most m times.  Hence, the number of DFA states will not grow forever.
58	 *  With recursive rules like
59	 *
60	 *    e : '(' e ')' | INT ;
61	 *
62	 *  you could chase your tail forever if somebody said "s : e '.' | e ';' ;"
63	 *  This constant prevents new states from being created after a stack gets
64	 *  "too big".  Actually (12/14/2007) I realize that this example is
65	 *  trapped by the non-LL(*) detector for recursion in > 1 alt.  Here is
66	 *  an example that trips stack overflow:
67	 *
68	 *	  s : a Y | A A A A A X ; // force recursion past m=4
69	 *	  a : A a | Q;
70	 *
71	 *  If that were:
72	 *
73	 *	  s : a Y | A+ X ;
74	 *
75	 *  it could loop forever.
76	 *
77	 *  Imagine doing a depth-first search on the e DFA...as you chase an input
78	 *  sequence you can recurse to same rule such as e above.  You'd have a
79	 *  chain of ((((.  When you get do some point, you have to give up.  The
80	 *  states in the chain will have longer and longer NFA config stacks.
81	 *  Must limit size.
82	 *
83	 *  max=0 implies you cannot ever jump to another rule during closure.
84	 *  max=1 implies you can make as many calls as you want--you just
85	 *        can't ever visit a state that is on your rule invocation stack.
86	 * 		  I.e., you cannot ever recurse.
87	 *  max=2 implies you are able to recurse once (i.e., call a rule twice
88	 *  	  from the same place).
89	 *
90	 *  This tracks recursion to a rule specific to an invocation site!
91	 *  It does not detect multiple calls to a rule from different rule
92	 *  invocation states.  We are guaranteed to terminate because the
93	 *  stack can only grow as big as the number of NFA states * max.
94	 *
95	 *  I noticed that the Java grammar didn't work with max=1, but did with
96	 *  max=4.  Let's set to 4. Recursion is sometimes needed to resolve some
97	 *  fixed lookahead decisions.
98	 */
99	public static int MAX_SAME_RULE_INVOCATIONS_PER_NFA_CONFIG_STACK = 4;
100
101    public NFAContext parent;
102
103    /** The NFA state that invoked another rule's start state is recorded
104     *  on the rule invocation context stack.
105     */
106    public NFAState invokingState;
107
108    /** Computing the hashCode is very expensive and closureBusy()
109     *  uses it to track when it's seen a state|ctx before to avoid
110     *  infinite loops.  As we add new contexts, record the hash code
111     *  as this.invokingState + parent.cachedHashCode.  Avoids walking
112     *  up the tree for every hashCode().  Note that this caching works
113     *  because a context is a monotonically growing tree of context nodes
114     *  and nothing on the stack is ever modified...ctx just grows
115     *  or shrinks.
116     */
117    protected int cachedHashCode;
118
119    public NFAContext(NFAContext parent, NFAState invokingState) {
120        this.parent = parent;
121        this.invokingState = invokingState;
122        if ( invokingState!=null ) {
123            this.cachedHashCode = invokingState.stateNumber;
124        }
125        if ( parent!=null ) {
126            this.cachedHashCode += parent.cachedHashCode;
127        }
128    }
129
130	/** Two contexts are equals() if both have
131	 *  same call stack; walk upwards to the root.
132	 *  Recall that the root sentinel node has no invokingStates and no parent.
133	 *  Note that you may be comparing contexts in different alt trees.
134	 *
135	 *  The hashCode is now cheap as it's computed once upon each context
136	 *  push on the stack.  Use it to make equals() more efficient.
137	 */
138	public boolean equals(Object o) {
139		NFAContext other = ((NFAContext)o);
140		if ( this.cachedHashCode != other.cachedHashCode ) {
141			return false; // can't be same if hash is different
142		}
143		if ( this==other ) {
144			return true;
145		}
146		// System.out.println("comparing "+this+" with "+other);
147		NFAContext sp = this;
148		while ( sp.parent!=null && other.parent!=null ) {
149			if ( sp.invokingState != other.invokingState ) {
150				return false;
151			}
152			sp = sp.parent;
153			other = other.parent;
154		}
155		if ( !(sp.parent==null && other.parent==null) ) {
156			return false; // both pointers must be at their roots after walk
157		}
158		return true;
159	}
160
161	/** Two contexts conflict() if they are equals() or one is a stack suffix
162	 *  of the other.  For example, contexts [21 12 $] and [21 9 $] do not
163	 *  conflict, but [21 $] and [21 12 $] do conflict.  Note that I should
164	 *  probably not show the $ in this case.  There is a dummy node for each
165	 *  stack that just means empty; $ is a marker that's all.
166	 *
167	 *  This is used in relation to checking conflicts associated with a
168	 *  single NFA state's configurations within a single DFA state.
169	 *  If there are configurations s and t within a DFA state such that
170	 *  s.state=t.state && s.alt != t.alt && s.ctx conflicts t.ctx then
171	 *  the DFA state predicts more than a single alt--it's nondeterministic.
172	 *  Two contexts conflict if they are the same or if one is a suffix
173	 *  of the other.
174	 *
175	 *  When comparing contexts, if one context has a stack and the other
176	 *  does not then they should be considered the same context.  The only
177	 *  way for an NFA state p to have an empty context and a nonempty context
178	 *  is the case when closure falls off end of rule without a call stack
179	 *  and re-enters the rule with a context.  This resolves the issue I
180	 *  discussed with Sriram Srinivasan Feb 28, 2005 about not terminating
181	 *  fast enough upon nondeterminism.
182	 */
183	public boolean conflictsWith(NFAContext other) {
184		return this.suffix(other); // || this.equals(other);
185	}
186
187	/** [$] suffix any context
188	 *  [21 $] suffix [21 12 $]
189	 *  [21 12 $] suffix [21 $]
190	 *  [21 18 $] suffix [21 18 12 9 $]
191	 *  [21 18 12 9 $] suffix [21 18 $]
192	 *  [21 12 $] not suffix [21 9 $]
193	 *
194	 *  Example "[21 $] suffix [21 12 $]" means: rule r invoked current rule
195	 *  from state 21.  Rule s invoked rule r from state 12 which then invoked
196	 *  current rule also via state 21.  While the context prior to state 21
197	 *  is different, the fact that both contexts emanate from state 21 implies
198	 *  that they are now going to track perfectly together.  Once they
199	 *  converged on state 21, there is no way they can separate.  In other
200	 *  words, the prior stack state is not consulted when computing where to
201	 *  go in the closure operation.  ?$ and ??$ are considered the same stack.
202	 *  If ? is popped off then $ and ?$ remain; they are now an empty and
203	 *  nonempty context comparison.  So, if one stack is a suffix of
204	 *  another, then it will still degenerate to the simple empty stack
205	 *  comparison case.
206	 */
207	protected boolean suffix(NFAContext other) {
208		NFAContext sp = this;
209		// if one of the contexts is empty, it never enters loop and returns true
210		while ( sp.parent!=null && other.parent!=null ) {
211			if ( sp.invokingState != other.invokingState ) {
212				return false;
213			}
214			sp = sp.parent;
215			other = other.parent;
216		}
217		//System.out.println("suffix");
218		return true;
219	}
220
221    /** Walk upwards to the root of the call stack context looking
222     *  for a particular invoking state.
223	public boolean contains(int state) {
224        NFAContext sp = this;
225		int n = 0; // track recursive invocations of state
226		System.out.println("this.context is "+sp);
227		while ( sp.parent!=null ) {
228            if ( sp.invokingState.stateNumber == state ) {
229				return true;
230            }
231            sp = sp.parent;
232        }
233        return false;
234    }
235	 */
236
237	/** Given an NFA state number, how many times has the NFA-to-DFA
238	 *  conversion pushed that state on the stack?  In other words,
239	 *  the NFA state must be a rule invocation state and this method
240	 *  tells you how many times you've been to this state.  If none,
241	 *  then you have not called the target rule from this state before
242	 *  (though another NFA state could have called that target rule).
243	 *  If n=1, then you've been to this state before during this
244	 *  DFA construction and are going to invoke that rule again.
245	 *
246	 *  Note that many NFA states can invoke rule r, but we ignore recursion
247	 *  unless you hit the same rule invocation state again.
248	 */
249	public int recursionDepthEmanatingFromState(int state) {
250		NFAContext sp = this;
251		int n = 0; // track recursive invocations of target from this state
252		//System.out.println("this.context is "+sp);
253		while ( sp.parent!=null ) {
254			if ( sp.invokingState.stateNumber == state ) {
255				n++;
256			}
257			sp = sp.parent;
258		}
259		return n;
260	}
261
262    public int hashCode() {
263        return cachedHashCode;
264        /*
265        int h = 0;
266        NFAContext sp = this;
267        while ( sp.parent!=null ) {
268            h += sp.invokingState.getStateNumber();
269            sp = sp.parent;
270        }
271        return h;
272        */
273    }
274
275	/** A context is empty if there is no parent; meaning nobody pushed
276	 *  anything on the call stack.
277	 */
278	public boolean isEmpty() {
279		return parent==null;
280	}
281
282    public String toString() {
283        StringBuffer buf = new StringBuffer();
284        NFAContext sp = this;
285        buf.append("[");
286        while ( sp.parent!=null ) {
287            buf.append(sp.invokingState.stateNumber);
288            buf.append(" ");
289            sp = sp.parent;
290        }
291        buf.append("$]");
292        return buf.toString();
293    }
294}
295