/*
 * [The "BSD license"]
 *  Copyright (c) 2010 Terence Parr
 *  All rights reserved.
 *
 *  Redistribution and use in source and binary forms, with or without
 *  modification, are permitted provided that the following conditions
 *  are met:
 *  1. Redistributions of source code must retain the above copyright
 *      notice, this list of conditions and the following disclaimer.
 *  2. Redistributions in binary form must reproduce the above copyright
 *      notice, this list of conditions and the following disclaimer in the
 *      documentation and/or other materials provided with the distribution.
 *  3. The name of the author may not be used to endorse or promote products
 *      derived from this software without specific prior written permission.
 *
 *  THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 *  IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 *  OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 *  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 *  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 *  NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 *  DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 *  THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 *  (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 *  THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

package org.antlr.analysis;

import org.antlr.misc.IntSet;
import org.antlr.runtime.CommonToken;
import org.antlr.runtime.Token;
import org.antlr.tool.Grammar;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class MachineProbe {
	DFA dfa;

	public MachineProbe(DFA dfa) {
		this.dfa = dfa;
	}

	List<DFAState> getAnyDFAPathToTarget(DFAState targetState) {
		Set<DFAState> visited = new HashSet<DFAState>();
		return getAnyDFAPathToTarget(dfa.startState, targetState, visited);
	}

	public List<DFAState> getAnyDFAPathToTarget(DFAState startState,
			DFAState targetState, Set<DFAState> visited) {
		List<DFAState> dfaStates = new ArrayList<DFAState>();
		visited.add(startState);
		if (startState.equals(targetState)) {
			dfaStates.add(targetState);
			return dfaStates;
		}
		// for (Edge e : startState.edges) { // walk edges looking for valid
		// path
		for (int i = 0; i < startState.getNumberOfTransitions(); i++) {
			Transition e = startState.getTransition(i);
			if (!visited.contains(e.target)) {
				List<DFAState> path = getAnyDFAPathToTarget(
						(DFAState) e.target, targetState, visited);
				if (path != null) { // found path, we're done
					dfaStates.add(startState);
					dfaStates.addAll(path);
					return dfaStates;
				}
			}
		}
		return null;
	}

	
Return a list of edge labels from start state to targetState. /** Return a list of edge labels from start state to targetState. */
	public List<IntSet> getEdgeLabels(DFAState targetState) {
		List<DFAState> dfaStates = getAnyDFAPathToTarget(targetState);
		List<IntSet> labels = new ArrayList<IntSet>();
		for (int i = 0; i < dfaStates.size() - 1; i++) {
			DFAState d = dfaStates.get(i);
			DFAState nextState = dfaStates.get(i + 1);
			// walk looking for edge whose target is next dfa state
			for (int j = 0; j < d.getNumberOfTransitions(); j++) {
				Transition e = d.getTransition(j);
				if (e.target.stateNumber == nextState.stateNumber) {
					labels.add(e.label.getSet());
				}
			}
		}
		return labels;
	}

	
Given List<IntSet>, return a String with a useful representation of the
associated input string. One could show something different for lexers
and parsers, for example.
/**
	 * Given List&lt;IntSet&gt;, return a String with a useful representation of the
	 * associated input string. One could show something different for lexers
	 * and parsers, for example.
	 */
	public String getInputSequenceDisplay(Grammar g, List<IntSet> labels) {
		List<String> tokens = new ArrayList<String>();
		for (IntSet label : labels)
			tokens.add(label.toString(g));
		return tokens.toString();
	}

	
Given an alternative associated with a DFA state, return the list of
tokens (from grammar) associated with path through NFA following the
labels sequence. The nfaStates gives the set of NFA states associated
with alt that take us from start to stop. One of the NFA states in
nfaStates[i] will have an edge intersecting with labels[i].
/**
	 * Given an alternative associated with a DFA state, return the list of
	 * tokens (from grammar) associated with path through NFA following the
	 * labels sequence. The nfaStates gives the set of NFA states associated
	 * with alt that take us from start to stop. One of the NFA states in
	 * nfaStates[i] will have an edge intersecting with labels[i].
	 */
	public List<Token> getGrammarLocationsForInputSequence(
			List<Set<NFAState>> nfaStates, List<IntSet> labels) {
		List<Token> tokens = new ArrayList<Token>();
		for (int i = 0; i < nfaStates.size() - 1; i++) {
			Set<NFAState> cur = nfaStates.get(i);
			Set<NFAState> next = nfaStates.get(i + 1);
			IntSet label = labels.get(i);
			// find NFA state with edge whose label matches labels[i]
			nfaConfigLoop: 
			
			for (NFAState p : cur) {
				// walk p's transitions, looking for label
				for (int j = 0; j < p.getNumberOfTransitions(); j++) {
					Transition t = p.transition(j);
					if (!t.isEpsilon() && !t.label.getSet().and(label).isNil()
							&& next.contains(t.target)) {
						if (p.associatedASTNode != null) {
							Token oldtoken = p.associatedASTNode.token;
							CommonToken token = new CommonToken(oldtoken
									.getType(), oldtoken.getText());
							token.setLine(oldtoken.getLine());
							token.setCharPositionInLine(oldtoken.getCharPositionInLine());
							tokens.add(token);
							break nfaConfigLoop; // found path, move to next
													// NFAState set
						}
					}
				}
			}
		}
		return tokens;
	}

	// /** Used to find paths through syntactically ambiguous DFA. If we've
	// * seen statement number before, what did we learn?
	// */
	// protected Map<Integer, Integer> stateReachable;
	//
	// public Map<DFAState, Set<DFAState>> getReachSets(Collection<DFAState>
	// targets) {
	// Map<DFAState, Set<DFAState>> reaches = new HashMap<DFAState,
	// Set<DFAState>>();
	// // targets can reach themselves
	// for (final DFAState d : targets) {
	// reaches.put(d,new HashSet<DFAState>() {{add(d);}});
	// }
	//
	// boolean changed = true;
	// while ( changed ) {
	// changed = false;
	// for (DFAState d : dfa.states.values()) {
	// if ( d.getNumberOfEdges()==0 ) continue;
	// Set<DFAState> r = reaches.get(d);
	// if ( r==null ) {
	// r = new HashSet<DFAState>();
	// reaches.put(d, r);
	// }
	// int before = r.size();
	// // add all reaches from all edge targets
	// for (Edge e : d.edges) {
	// //if ( targets.contains(e.target) ) r.add(e.target);
	// r.addAll( reaches.get(e.target) );
	// }
	// int after = r.size();
	// if ( after>before) changed = true;
	// }
	// }
	// return reaches;
	// }

}