1324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/*
2324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * [The "BSD license"]
3324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver *  Copyright (c) 2010 Terence Parr
4324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver *  All rights reserved.
5324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver *
6324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver *  Redistribution and use in source and binary forms, with or without
7324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver *  modification, are permitted provided that the following conditions
8324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver *  are met:
9324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver *  1. Redistributions of source code must retain the above copyright
10324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver *      notice, this list of conditions and the following disclaimer.
11324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver *  2. Redistributions in binary form must reproduce the above copyright
12324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver *      notice, this list of conditions and the following disclaimer in the
13324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver *      documentation and/or other materials provided with the distribution.
14324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver *  3. The name of the author may not be used to endorse or promote products
15324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver *      derived from this software without specific prior written permission.
16324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver *
17324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver *  THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver *  IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver *  OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver *  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver *  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver *  NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver *  DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver *  THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver *  (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver *  THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */
28324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverpackage org.antlr.analysis;
29324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver
30324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/** A tree node for tracking the call chains for NFAs that invoke
31324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver *  other NFAs.  These trees only have to point upwards to their parents
32324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver *  so we can walk back up the tree (i.e., pop stuff off the stack).  We
33324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver *  never walk from stack down down through the children.
34324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver *
35324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver *  Each alt predicted in a decision has its own context tree,
36324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver *  representing all possible return nodes.  The initial stack has
37324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver *  EOF ("$") in it.  So, for m alternative productions, the lookahead
38324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver *  DFA will have m NFAContext trees.
39324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver *
40324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver *  To "push" a new context, just do "new NFAContext(context-parent, state)"
41324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver *  which will add itself to the parent.  The root is NFAContext(null, null).
42324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver *
43324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver *  The complete context for an NFA configuration is the set of invoking states
44324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver *  on the path from this node thru the parent pointers to the root.
45324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */
46324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverpublic class NFAContext {
47324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	/** This is similar to Bermudez's m constant in his LAR(m) where
48324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  you bound the stack so your states don't explode.  The main difference
49324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  is that I bound only recursion on the stack, not the simple stack size.
50324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  This looser constraint will let the conversion roam further to find
51324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  lookahead to resolve a decision.
52324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *
53324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  Bermudez's m operates differently as it is his LR stack depth
54324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  I'm pretty sure it therefore includes all stack symbols.  Here I
55324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  restrict the size of an NFA configuration to be finite because a
56324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  stack component may mention the same NFA invocation state at
57324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  most m times.  Hence, the number of DFA states will not grow forever.
58324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  With recursive rules like
59324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *
60324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *    e : '(' e ')' | INT ;
61324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *
62324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  you could chase your tail forever if somebody said "s : e '.' | e ';' ;"
63324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  This constant prevents new states from being created after a stack gets
64324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  "too big".  Actually (12/14/2007) I realize that this example is
65324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  trapped by the non-LL(*) detector for recursion in > 1 alt.  Here is
66324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  an example that trips stack overflow:
67324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *
68324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *	  s : a Y | A A A A A X ; // force recursion past m=4
69324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *	  a : A a | Q;
70324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *
71324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  If that were:
72324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *
73324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *	  s : a Y | A+ X ;
74324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *
75324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  it could loop forever.
76324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *
77324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  Imagine doing a depth-first search on the e DFA...as you chase an input
78324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  sequence you can recurse to same rule such as e above.  You'd have a
79324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  chain of ((((.  When you get do some point, you have to give up.  The
80324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  states in the chain will have longer and longer NFA config stacks.
81324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  Must limit size.
82324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *
83324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  max=0 implies you cannot ever jump to another rule during closure.
84324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  max=1 implies you can make as many calls as you want--you just
85324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *        can't ever visit a state that is on your rule invocation stack.
86324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 * 		  I.e., you cannot ever recurse.
87324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  max=2 implies you are able to recurse once (i.e., call a rule twice
88324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  	  from the same place).
89324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *
90324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  This tracks recursion to a rule specific to an invocation site!
91324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  It does not detect multiple calls to a rule from different rule
92324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  invocation states.  We are guaranteed to terminate because the
93324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  stack can only grow as big as the number of NFA states * max.
94324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *
95324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  I noticed that the Java grammar didn't work with max=1, but did with
96324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  max=4.  Let's set to 4. Recursion is sometimes needed to resolve some
97324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  fixed lookahead decisions.
98324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 */
99324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	public static int MAX_SAME_RULE_INVOCATIONS_PER_NFA_CONFIG_STACK = 4;
100324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver
101324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver    public NFAContext parent;
102324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver
103324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver    /** The NFA state that invoked another rule's start state is recorded
104324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver     *  on the rule invocation context stack.
105324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver     */
106324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver    public NFAState invokingState;
107324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver
108324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver    /** Computing the hashCode is very expensive and closureBusy()
109324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver     *  uses it to track when it's seen a state|ctx before to avoid
110324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver     *  infinite loops.  As we add new contexts, record the hash code
111324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver     *  as this.invokingState + parent.cachedHashCode.  Avoids walking
112324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver     *  up the tree for every hashCode().  Note that this caching works
113324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver     *  because a context is a monotonically growing tree of context nodes
114324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver     *  and nothing on the stack is ever modified...ctx just grows
115324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver     *  or shrinks.
116324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver     */
117324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver    protected int cachedHashCode;
118324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver
119324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver    public NFAContext(NFAContext parent, NFAState invokingState) {
120324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver        this.parent = parent;
121324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver        this.invokingState = invokingState;
122324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver        if ( invokingState!=null ) {
123324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver            this.cachedHashCode = invokingState.stateNumber;
124324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver        }
125324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver        if ( parent!=null ) {
126324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver            this.cachedHashCode += parent.cachedHashCode;
127324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver        }
128324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver    }
129324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver
130324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	/** Two contexts are equals() if both have
131324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  same call stack; walk upwards to the root.
132324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  Recall that the root sentinel node has no invokingStates and no parent.
133324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  Note that you may be comparing contexts in different alt trees.
134324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *
135324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  The hashCode is now cheap as it's computed once upon each context
136324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  push on the stack.  Use it to make equals() more efficient.
137324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 */
138324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	public boolean equals(Object o) {
139324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver		NFAContext other = ((NFAContext)o);
140324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver		if ( this.cachedHashCode != other.cachedHashCode ) {
141324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver			return false; // can't be same if hash is different
142324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver		}
143324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver		if ( this==other ) {
144324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver			return true;
145324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver		}
146324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver		// System.out.println("comparing "+this+" with "+other);
147324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver		NFAContext sp = this;
148324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver		while ( sp.parent!=null && other.parent!=null ) {
149324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver			if ( sp.invokingState != other.invokingState ) {
150324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver				return false;
151324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver			}
152324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver			sp = sp.parent;
153324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver			other = other.parent;
154324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver		}
155324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver		if ( !(sp.parent==null && other.parent==null) ) {
156324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver			return false; // both pointers must be at their roots after walk
157324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver		}
158324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver		return true;
159324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	}
160324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver
161324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	/** Two contexts conflict() if they are equals() or one is a stack suffix
162324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  of the other.  For example, contexts [21 12 $] and [21 9 $] do not
163324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  conflict, but [21 $] and [21 12 $] do conflict.  Note that I should
164324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  probably not show the $ in this case.  There is a dummy node for each
165324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  stack that just means empty; $ is a marker that's all.
166324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *
167324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  This is used in relation to checking conflicts associated with a
168324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  single NFA state's configurations within a single DFA state.
169324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  If there are configurations s and t within a DFA state such that
170324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  s.state=t.state && s.alt != t.alt && s.ctx conflicts t.ctx then
171324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  the DFA state predicts more than a single alt--it's nondeterministic.
172324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  Two contexts conflict if they are the same or if one is a suffix
173324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  of the other.
174324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *
175324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  When comparing contexts, if one context has a stack and the other
176324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  does not then they should be considered the same context.  The only
177324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  way for an NFA state p to have an empty context and a nonempty context
178324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  is the case when closure falls off end of rule without a call stack
179324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  and re-enters the rule with a context.  This resolves the issue I
180324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  discussed with Sriram Srinivasan Feb 28, 2005 about not terminating
181324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  fast enough upon nondeterminism.
182324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 */
183324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	public boolean conflictsWith(NFAContext other) {
184324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver		return this.suffix(other); // || this.equals(other);
185324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	}
186324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver
187324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	/** [$] suffix any context
188324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  [21 $] suffix [21 12 $]
189324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  [21 12 $] suffix [21 $]
190324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  [21 18 $] suffix [21 18 12 9 $]
191324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  [21 18 12 9 $] suffix [21 18 $]
192324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  [21 12 $] not suffix [21 9 $]
193324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *
194324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  Example "[21 $] suffix [21 12 $]" means: rule r invoked current rule
195324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  from state 21.  Rule s invoked rule r from state 12 which then invoked
196324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  current rule also via state 21.  While the context prior to state 21
197324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  is different, the fact that both contexts emanate from state 21 implies
198324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  that they are now going to track perfectly together.  Once they
199324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  converged on state 21, there is no way they can separate.  In other
200324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  words, the prior stack state is not consulted when computing where to
201324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  go in the closure operation.  ?$ and ??$ are considered the same stack.
202324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  If ? is popped off then $ and ?$ remain; they are now an empty and
203324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  nonempty context comparison.  So, if one stack is a suffix of
204324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  another, then it will still degenerate to the simple empty stack
205324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  comparison case.
206324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 */
207324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	protected boolean suffix(NFAContext other) {
208324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver		NFAContext sp = this;
209324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver		// if one of the contexts is empty, it never enters loop and returns true
210324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver		while ( sp.parent!=null && other.parent!=null ) {
211324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver			if ( sp.invokingState != other.invokingState ) {
212324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver				return false;
213324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver			}
214324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver			sp = sp.parent;
215324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver			other = other.parent;
216324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver		}
217324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver		//System.out.println("suffix");
218324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver		return true;
219324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	}
220324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver
221324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver    /** Walk upwards to the root of the call stack context looking
222324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver     *  for a particular invoking state.
223324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	public boolean contains(int state) {
224324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver        NFAContext sp = this;
225324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver		int n = 0; // track recursive invocations of state
226324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver		System.out.println("this.context is "+sp);
227324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver		while ( sp.parent!=null ) {
228324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver            if ( sp.invokingState.stateNumber == state ) {
229324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver				return true;
230324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver            }
231324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver            sp = sp.parent;
232324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver        }
233324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver        return false;
234324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver    }
235324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 */
236324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver
237324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	/** Given an NFA state number, how many times has the NFA-to-DFA
238324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  conversion pushed that state on the stack?  In other words,
239324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  the NFA state must be a rule invocation state and this method
240324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  tells you how many times you've been to this state.  If none,
241324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  then you have not called the target rule from this state before
242324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  (though another NFA state could have called that target rule).
243324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  If n=1, then you've been to this state before during this
244324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  DFA construction and are going to invoke that rule again.
245324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *
246324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  Note that many NFA states can invoke rule r, but we ignore recursion
247324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  unless you hit the same rule invocation state again.
248324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 */
249324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	public int recursionDepthEmanatingFromState(int state) {
250324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver		NFAContext sp = this;
251324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver		int n = 0; // track recursive invocations of target from this state
252324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver		//System.out.println("this.context is "+sp);
253324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver		while ( sp.parent!=null ) {
254324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver			if ( sp.invokingState.stateNumber == state ) {
255324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver				n++;
256324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver			}
257324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver			sp = sp.parent;
258324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver		}
259324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver		return n;
260324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	}
261324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver
262324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver    public int hashCode() {
263324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver        return cachedHashCode;
264324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver        /*
265324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver        int h = 0;
266324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver        NFAContext sp = this;
267324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver        while ( sp.parent!=null ) {
268324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver            h += sp.invokingState.getStateNumber();
269324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver            sp = sp.parent;
270324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver        }
271324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver        return h;
272324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver        */
273324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver    }
274324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver
275324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	/** A context is empty if there is no parent; meaning nobody pushed
276324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 *  anything on the call stack.
277324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	 */
278324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	public boolean isEmpty() {
279324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver		return parent==null;
280324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver	}
281324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver
282324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver    public String toString() {
283324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver        StringBuffer buf = new StringBuffer();
284324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver        NFAContext sp = this;
285324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver        buf.append("[");
286324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver        while ( sp.parent!=null ) {
287324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver            buf.append(sp.invokingState.stateNumber);
288324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver            buf.append(" ");
289324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver            sp = sp.parent;
290324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver        }
291324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver        buf.append("$]");
292324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver        return buf.toString();
293324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver    }
294324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver}
295