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.tool;
29
30import org.antlr.analysis.*;
31import org.antlr.misc.Utils;
32
33import java.util.*;
34
35/** An aspect of FA (finite automata) that knows how to dump them to serialized
36 *  strings.
37 */
38public class FASerializer {
39    /** To prevent infinite recursion when walking state machines, record
40     *  which states we've visited.  Make a new set every time you start
41     *  walking in case you reuse this object.  Multiple threads will trash
42     *  this shared variable.  Use a different FASerializer per thread.
43     */
44    protected Set markedStates;
45
46    /** Each state we walk will get a new state number for serialization
47     *  purposes.  This is the variable that tracks state numbers.
48     */
49    protected int stateCounter = 0;
50
51    /** Rather than add a new instance variable to NFA and DFA just for
52     *  serializing machines, map old state numbers to new state numbers
53     *  by a State object -> Integer new state number HashMap.
54     */
55    protected Map stateNumberTranslator;
56
57    protected Grammar grammar;
58
59    /** This aspect is associated with a grammar; used to get token names */
60    public FASerializer(Grammar grammar) {
61        this.grammar = grammar;
62    }
63
64	public String serialize(State s) {
65		if ( s==null ) {
66			return "<no automaton>";
67		}
68		return serialize(s, true);
69	}
70
71	/** Return a string representation of a state machine.  Two identical
72     *  NFAs or DFAs will have identical serialized representations.  The
73     *  state numbers inside the state are not used; instead, a new number
74     *  is computed and because the serialization will walk the two
75     *  machines using the same specific algorithm, then the state numbers
76     *  will be identical.  Accept states are distinguished from regular
77     *  states.
78     */
79    public String serialize(State s, boolean renumber) {
80        markedStates = new HashSet();
81        stateCounter = 0;
82		if ( renumber ) {
83			stateNumberTranslator = new HashMap();
84        	walkFANormalizingStateNumbers(s);
85		}
86		List lines = new ArrayList();
87        if ( s.getNumberOfTransitions()>0 ) {
88			walkSerializingFA(lines, s);
89		}
90		else {
91			// special case: s0 is an accept
92			String s0 = getStateString(0, s);
93			lines.add(s0+"\n");
94		}
95        StringBuffer buf = new StringBuffer(0);
96        // sort lines to normalize; makes states come out ordered
97        // and then ordered by edge labels then by target state number :)
98        Collections.sort(lines);
99        for (int i = 0; i < lines.size(); i++) {
100            String line = (String) lines.get(i);
101            buf.append(line);
102        }
103        return buf.toString();
104    }
105
106    /** In stateNumberTranslator, get a map from State to new, normalized
107     *  state number.  Used by walkSerializingFA to make sure any two
108     *  identical state machines will serialize the same way.
109     */
110    protected void walkFANormalizingStateNumbers(State s) {
111		if ( s==null ) {
112			ErrorManager.internalError("null state s");
113			return;
114		}
115        if ( stateNumberTranslator.get(s)!=null ) {
116            return; // already did this state
117        }
118        // assign a new state number for this node if there isn't one
119        stateNumberTranslator.put(s, Utils.integer(stateCounter));
120        stateCounter++;
121
122        // visit nodes pointed to by each transition;
123        for (int i = 0; i < s.getNumberOfTransitions(); i++) {
124            Transition edge = (Transition) s.transition(i);
125            walkFANormalizingStateNumbers(edge.target); // keep walkin'
126            // if this transition is a rule reference, the node "following" this state
127            // will not be found and appear to be not in graph.  Must explicitly jump
128            // to it, but don't "draw" an edge.
129            if ( edge instanceof RuleClosureTransition ) {
130				walkFANormalizingStateNumbers(((RuleClosureTransition) edge).followState);
131            }
132        }
133    }
134
135    protected void walkSerializingFA(List lines, State s) {
136        if ( markedStates.contains(s) ) {
137            return; // already visited this node
138        }
139
140        markedStates.add(s); // mark this node as completed.
141
142		int normalizedStateNumber = s.stateNumber;
143		if ( stateNumberTranslator!=null ) {
144	        Integer normalizedStateNumberI = (Integer)stateNumberTranslator.get(s);
145			normalizedStateNumber = normalizedStateNumberI.intValue();
146		}
147
148		String stateStr = getStateString(normalizedStateNumber, s);
149
150        // depth first walk each transition, printing its edge first
151        for (int i = 0; i < s.getNumberOfTransitions(); i++) {
152            Transition edge = (Transition) s.transition(i);
153            StringBuffer buf = new StringBuffer();
154            buf.append(stateStr);
155			if ( edge.isAction() ) {
156				buf.append("-{}->");
157			}
158			else if ( edge.isEpsilon() ) {
159				buf.append("->");
160			}
161			else if ( edge.isSemanticPredicate() ) {
162				buf.append("-{"+edge.label.getSemanticContext()+"}?->");
163			}
164			else {
165				String predsStr = "";
166				if ( edge.target instanceof DFAState ) {
167					// look for gated predicates; don't add gated to simple sempred edges
168					SemanticContext preds =
169						((DFAState)edge.target).getGatedPredicatesInNFAConfigurations();
170					if ( preds!=null ) {
171						predsStr = "&&{"+
172							preds.genExpr(grammar.generator,
173									   	  grammar.generator.getTemplates(), null).render()
174							+"}?";
175					}
176				}
177				buf.append("-"+edge.label.toString(grammar)+predsStr+"->");
178			}
179
180			int normalizedTargetStateNumber = edge.target.stateNumber;
181			if ( stateNumberTranslator!=null ) {
182				Integer normalizedTargetStateNumberI =
183					(Integer)stateNumberTranslator.get(edge.target);
184				normalizedTargetStateNumber = normalizedTargetStateNumberI.intValue();
185			}
186			buf.append(getStateString(normalizedTargetStateNumber, edge.target));
187            buf.append("\n");
188            lines.add(buf.toString());
189
190            // walk this transition
191            walkSerializingFA(lines, edge.target);
192
193            // if this transition is a rule reference, the node "following" this state
194            // will not be found and appear to be not in graph.  Must explicitly jump
195            // to it, but don't "draw" an edge.
196            if ( edge instanceof RuleClosureTransition ) {
197				walkSerializingFA(lines, ((RuleClosureTransition) edge).followState);
198            }
199        }
200
201    }
202
203    private String getStateString(int n, State s) {
204        String stateStr = ".s"+n;
205        if ( s.isAcceptState() ) {
206            if ( s instanceof DFAState ) {
207                stateStr = ":s"+n+"=>"+((DFAState)s).getUniquelyPredictedAlt();
208            }
209            else {
210                stateStr = ":s"+n;
211            }
212        }
213        return stateStr;
214    }
215
216
217}
218