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 */
28
29package org.antlr.analysis;
30
31import org.antlr.misc.IntSet;
32import org.antlr.runtime.CommonToken;
33import org.antlr.runtime.Token;
34import org.antlr.tool.Grammar;
35
36import java.util.ArrayList;
37import java.util.HashSet;
38import java.util.List;
39import java.util.Set;
40
41public class MachineProbe {
42	DFA dfa;
43
44	public MachineProbe(DFA dfa) {
45		this.dfa = dfa;
46	}
47
48	List<DFAState> getAnyDFAPathToTarget(DFAState targetState) {
49		Set<DFAState> visited = new HashSet<DFAState>();
50		return getAnyDFAPathToTarget(dfa.startState, targetState, visited);
51	}
52
53	public List<DFAState> getAnyDFAPathToTarget(DFAState startState,
54			DFAState targetState, Set<DFAState> visited) {
55		List<DFAState> dfaStates = new ArrayList<DFAState>();
56		visited.add(startState);
57		if (startState.equals(targetState)) {
58			dfaStates.add(targetState);
59			return dfaStates;
60		}
61		// for (Edge e : startState.edges) { // walk edges looking for valid
62		// path
63		for (int i = 0; i < startState.getNumberOfTransitions(); i++) {
64			Transition e = startState.getTransition(i);
65			if (!visited.contains(e.target)) {
66				List<DFAState> path = getAnyDFAPathToTarget(
67						(DFAState) e.target, targetState, visited);
68				if (path != null) { // found path, we're done
69					dfaStates.add(startState);
70					dfaStates.addAll(path);
71					return dfaStates;
72				}
73			}
74		}
75		return null;
76	}
77
78	/** Return a list of edge labels from start state to targetState. */
79	public List<IntSet> getEdgeLabels(DFAState targetState) {
80		List<DFAState> dfaStates = getAnyDFAPathToTarget(targetState);
81		List<IntSet> labels = new ArrayList<IntSet>();
82		for (int i = 0; i < dfaStates.size() - 1; i++) {
83			DFAState d = dfaStates.get(i);
84			DFAState nextState = dfaStates.get(i + 1);
85			// walk looking for edge whose target is next dfa state
86			for (int j = 0; j < d.getNumberOfTransitions(); j++) {
87				Transition e = d.getTransition(j);
88				if (e.target.stateNumber == nextState.stateNumber) {
89					labels.add(e.label.getSet());
90				}
91			}
92		}
93		return labels;
94	}
95
96	/**
97	 * Given List<IntSet>, return a String with a useful representation of the
98	 * associated input string. One could show something different for lexers
99	 * and parsers, for example.
100	 */
101	public String getInputSequenceDisplay(Grammar g, List<IntSet> labels) {
102		List<String> tokens = new ArrayList<String>();
103		for (IntSet label : labels)
104			tokens.add(label.toString(g));
105		return tokens.toString();
106	}
107
108	/**
109	 * Given an alternative associated with a DFA state, return the list of
110	 * tokens (from grammar) associated with path through NFA following the
111	 * labels sequence. The nfaStates gives the set of NFA states associated
112	 * with alt that take us from start to stop. One of the NFA states in
113	 * nfaStates[i] will have an edge intersecting with labels[i].
114	 */
115	public List<Token> getGrammarLocationsForInputSequence(
116			List<Set<NFAState>> nfaStates, List<IntSet> labels) {
117		List<Token> tokens = new ArrayList<Token>();
118		for (int i = 0; i < nfaStates.size() - 1; i++) {
119			Set<NFAState> cur = nfaStates.get(i);
120			Set<NFAState> next = nfaStates.get(i + 1);
121			IntSet label = labels.get(i);
122			// find NFA state with edge whose label matches labels[i]
123			nfaConfigLoop:
124
125			for (NFAState p : cur) {
126				// walk p's transitions, looking for label
127				for (int j = 0; j < p.getNumberOfTransitions(); j++) {
128					Transition t = p.transition(j);
129					if (!t.isEpsilon() && !t.label.getSet().and(label).isNil()
130							&& next.contains(t.target)) {
131						if (p.associatedASTNode != null) {
132							Token oldtoken = p.associatedASTNode.token;
133							CommonToken token = new CommonToken(oldtoken
134									.getType(), oldtoken.getText());
135							token.setLine(oldtoken.getLine());
136							token.setCharPositionInLine(oldtoken.getCharPositionInLine());
137							tokens.add(token);
138							break nfaConfigLoop; // found path, move to next
139													// NFAState set
140						}
141					}
142				}
143			}
144		}
145		return tokens;
146	}
147
148	// /** Used to find paths through syntactically ambiguous DFA. If we've
149	// * seen statement number before, what did we learn?
150	// */
151	// protected Map<Integer, Integer> stateReachable;
152	//
153	// public Map<DFAState, Set<DFAState>> getReachSets(Collection<DFAState>
154	// targets) {
155	// Map<DFAState, Set<DFAState>> reaches = new HashMap<DFAState,
156	// Set<DFAState>>();
157	// // targets can reach themselves
158	// for (final DFAState d : targets) {
159	// reaches.put(d,new HashSet<DFAState>() {{add(d);}});
160	// }
161	//
162	// boolean changed = true;
163	// while ( changed ) {
164	// changed = false;
165	// for (DFAState d : dfa.states.values()) {
166	// if ( d.getNumberOfEdges()==0 ) continue;
167	// Set<DFAState> r = reaches.get(d);
168	// if ( r==null ) {
169	// r = new HashSet<DFAState>();
170	// reaches.put(d, r);
171	// }
172	// int before = r.size();
173	// // add all reaches from all edge targets
174	// for (Edge e : d.edges) {
175	// //if ( targets.contains(e.target) ) r.add(e.target);
176	// r.addAll( reaches.get(e.target) );
177	// }
178	// int after = r.size();
179	// if ( after>before) changed = true;
180	// }
181	// }
182	// return reaches;
183	// }
184
185}
186