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.misc.Utils;
31
32/** An NFA state, predicted alt, and syntactic/semantic context.
33 *  The syntactic context is a pointer into the rule invocation
34 *  chain used to arrive at the state.  The semantic context is
35 *  the unordered set semantic predicates encountered before reaching
36 *  an NFA state.
37 */
38public class NFAConfiguration {
39    /** The NFA state associated with this configuration */
40    public int state;
41
42    /** What alt is predicted by this configuration */
43    public int alt;
44
45    /** What is the stack of rule invocations that got us to state? */
46    public NFAContext context;
47
48    /** The set of semantic predicates associated with this NFA
49     *  configuration.  The predicates were found on the way to
50     *  the associated NFA state in this syntactic context.
51     *  Set<AST>: track nodes in grammar containing the predicate
52     *  for error messages and such (nice to know where the predicate
53     *  came from in case of duplicates etc...).  By using a set,
54     *  the equals() method will correctly show {pred1,pred2} as equals()
55     *  to {pred2,pred1}.
56     */
57    public SemanticContext semanticContext = SemanticContext.EMPTY_SEMANTIC_CONTEXT;
58
59    /** Indicate that this configuration has been resolved and no further
60     *  DFA processing should occur with it.  Essentially, this is used
61     *  as an "ignore" bit so that upon a set of nondeterministic configurations
62     *  such as (s|2) and (s|3), I can set (s|3) to resolved=true (and any
63     *  other configuration associated with alt 3).
64     */
65    protected boolean resolved;
66
67    /** This bit is used to indicate a semantic predicate will be
68     *  used to resolve the conflict.  Method
69     *  DFA.findNewDFAStatesAndAddDFATransitions will add edges for
70     *  the predicates after it performs the reach operation.  The
71     *  nondeterminism resolver sets this when it finds a set of
72     *  nondeterministic configurations (as it does for "resolved" field)
73     *  that have enough predicates to resolve the conflit.
74     */
75    protected boolean resolveWithPredicate;
76
77    /** Lots of NFA states have only epsilon edges (1 or 2).  We can
78     *  safely consider only n>0 during closure.
79     */
80    protected int numberEpsilonTransitionsEmanatingFromState;
81
82    /** Indicates that the NFA state associated with this configuration
83     *  has exactly one transition and it's an atom (not epsilon etc...).
84     */
85    protected boolean singleAtomTransitionEmanating;
86
87	//protected boolean addedDuringClosure = true;
88
89	public NFAConfiguration(int state,
90                            int alt,
91                            NFAContext context,
92                            SemanticContext semanticContext)
93    {
94        this.state = state;
95        this.alt = alt;
96        this.context = context;
97        this.semanticContext = semanticContext;
98    }
99
100    /** An NFA configuration is equal to another if both have
101     *  the same state, the predict the same alternative, and
102     *  syntactic/semantic contexts are the same.  I don't think
103     *  the state|alt|ctx could be the same and have two different
104     *  semantic contexts, but might as well define equals to be
105     *  everything.
106     */
107    public boolean equals(Object o) {
108		if ( o==null ) {
109			return false;
110		}
111        NFAConfiguration other = (NFAConfiguration)o;
112        return this.state==other.state &&
113               this.alt==other.alt &&
114               this.context.equals(other.context)&&
115               this.semanticContext.equals(other.semanticContext);
116    }
117
118    public int hashCode() {
119        int h = state + alt + context.hashCode();
120        return h;
121    }
122
123	public String toString() {
124		return toString(true);
125	}
126
127	public String toString(boolean showAlt) {
128		StringBuffer buf = new StringBuffer();
129		buf.append(state);
130		if ( showAlt ) {
131			buf.append("|");
132			buf.append(alt);
133		}
134		if ( context.parent!=null ) {
135            buf.append("|");
136            buf.append(context);
137        }
138        if ( semanticContext!=null &&
139             semanticContext!=SemanticContext.EMPTY_SEMANTIC_CONTEXT ) {
140            buf.append("|");
141			String escQuote = Utils.replace(semanticContext.toString(), "\"", "\\\"");
142			buf.append(escQuote);
143        }
144        if ( resolved ) {
145            buf.append("|resolved");
146        }
147		if ( resolveWithPredicate ) {
148			buf.append("|resolveWithPredicate");
149		}
150		return buf.toString();
151    }
152}
153