package java_cup;

import java.util.Stack;
import java.util.Enumeration;

/** This class represents an LALR item. Each LALR item consists of 
 *  a production, a "dot" at a position within that production, and
 *  a set of lookahead symbols (terminal).  (The first two of these parts
 *  are provide by the super class).  An item is designed to represent a 
 *  configuration that the parser may be in.  For example, an item of the 
 *  form: <pre>
 *    [A ::= B * C d E  , {a,b,c}]
 *  </pre>
 *  indicates that the parser is in the middle of parsing the production <pre>
 *    A ::= B C d E
 *  </pre>
 *  that B has already been parsed, and that we will expect to see a lookahead 
 *  of either a, b, or c once the complete RHS of this production has been 
 *  found.<p>
 *
 *  Items may initially be missing some items from their lookahead sets.  
 *  Links are maintained from each item to the set of items that would need 
 *  to be updated if symbols are added to its lookahead set.  During 
 *  "lookahead propagation", we add symbols to various lookahead sets and 
 *  propagate these changes across these dependency links as needed. 
 *  
 * @see     java_cup.lalr_item_set
 * @see     java_cup.lalr_state
 * @version last updated: 11/25/95
 * @author  Scott Hudson
 */
public class lalr_item extends lr_item_core {

	/*-----------------------------------------------------------*/
	/*--- Constructor(s) ----------------------------------------*/
	/*-----------------------------------------------------------*/

	/** Full constructor. 
	 * @param prod the production for the item.
	 * @param pos  the position of the "dot" within the production.
	 * @param look the set of lookahead symbols.
	 */
	public lalr_item(production prod, int pos, terminal_set look)
			throws internal_error
	{
		super(prod, pos);
		_lookahead = look;
		_propagate_items = new Stack();
		needs_propagation = true;
	}

	/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/

	/** Constructor with default position (dot at start). 
	 * @param prod the production for the item.
	 * @param look the set of lookahead symbols.
	 */
	public lalr_item(production prod, terminal_set look) throws internal_error
	{
		this(prod, 0, look);
	}

	/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/

	/** Constructor with default position and empty lookahead set. 
	 * @param prod the production for the item.
	 */
	public lalr_item(production prod) throws internal_error
	{
		this(prod, 0, new terminal_set());
	}

	/*-----------------------------------------------------------*/
	/*--- (Access to) Instance Variables ------------------------*/
	/*-----------------------------------------------------------*/

	/** The lookahead symbols of the item. */
	protected terminal_set _lookahead;

	/** The lookahead symbols of the item. */
	public terminal_set lookahead() {
		return _lookahead;
	}

	/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/

	/** Links to items that the lookahead needs to be propagated to. */
	protected Stack _propagate_items;

	/** Links to items that the lookahead needs to be propagated to */
	public Stack propagate_items() {
		return _propagate_items;
	}

	/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/

	/** Flag to indicate that this item needs to propagate its lookahead 
	 *  (whether it has changed or not). 
	 */
	protected boolean needs_propagation;

	/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/

	/** Add a new item to the set of items we propagate to. */
	public void add_propagate(lalr_item prop_to)
	{
		_propagate_items.push(prop_to);
		needs_propagation = true;
	}

	/*-----------------------------------------------------------*/
	/*--- General Methods ---------------------------------------*/
	/*-----------------------------------------------------------*/

	/** Propagate incoming lookaheads through this item to others need to 
	 *  be changed.
	 * @params incoming symbols to potentially be added to lookahead of this item.
	 */
	public void propagate_lookaheads(terminal_set incoming) throws internal_error
	{
		boolean change = false;

		/* if we don't need to propagate, then bail out now */
		if (!needs_propagation && (incoming == null || incoming.empty()))
			return;

		/* if we have null incoming, treat as an empty set */
		if (incoming != null)
		{
			/* add the incoming to the lookahead of this item */
			change = lookahead().add(incoming);
		}

		/* if we changed or need it anyway, propagate across our links */
		if (change || needs_propagation)
		{
			/* don't need to propagate again */
			needs_propagation = false;

			/* propagate our lookahead into each item we are linked to */
			for (int i = 0; i < propagate_items().size(); i++)
				((lalr_item) propagate_items().elementAt(i))
						.propagate_lookaheads(lookahead());
		}
	}

	/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/

	/** Produce the new lalr_item that results from shifting the dot one position
	 *  to the right. 
	 */
	public lalr_item shift() throws internal_error
	{
		lalr_item result;

		/* can't shift if we have dot already at the end */
		if (dot_at_end())
			throw new internal_error("Attempt to shift past end of an lalr_item");

		/* create the new item w/ the dot shifted by one */
		result = new lalr_item(the_production(), dot_pos() + 1,
				new terminal_set(lookahead()));

		/* change in our lookahead needs to be propagated to this item */
		add_propagate(result);

		return result;
	}

	/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/

	/** Calculate lookahead representing symbols that could appear after the
	 *   symbol that the dot is currently in front of.  Note: this routine must
	 *   not be invoked before first sets and nullability has been calculated
	 *   for all non terminals. 
	 */
	public terminal_set calc_lookahead(terminal_set lookahead_after)
			throws internal_error
	{
		terminal_set result;
		int pos;
		production_part part;
		symbol sym;

		/* sanity check */
		if (dot_at_end())
			throw new internal_error(
					"Attempt to calculate a lookahead set with a completed item");

		/* start with an empty result */
		result = new terminal_set();

		/* consider all nullable symbols after the one to the right of the dot */
		for (pos = dot_pos() + 1; pos < the_production().rhs_length(); pos++)
		{
			part = the_production().rhs(pos);

			/* consider what kind of production part it is -- skip actions */
			if (!part.is_action())
			{
				sym = ((symbol_part) part).the_symbol();

				/* if its a terminal add it in and we are done */
				if (!sym.is_non_term())
				{
					result.add((terminal) sym);
					return result;
				}
				else
				{
					/* otherwise add in first set of the non terminal */
					result.add(((non_terminal) sym).first_set());

					/* if its nullable we continue adding, if not, we are done */
					if (!((non_terminal) sym).nullable())
						return result;
				}
			}
		}

		/* if we get here everything past the dot was nullable 
		   we add in the lookahead for after the production and we are done */
		result.add(lookahead_after);
		return result;
	}

	/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/

	/** Determine if everything from the symbol one beyond the dot all the 
	 *  way to the  end of the right hand side is nullable.  This would indicate
	 *  that the lookahead of this item must be included in the lookaheads of
	 *  all items produced as a closure of this item.  Note: this routine should 
	 *  not be invoked until after first sets and nullability have been 
	 *  calculated for all non terminals. 
	 */
	public boolean lookahead_visible() throws internal_error
	{
		production_part part;
		symbol sym;

		/* if the dot is at the end, we have a problem, but the cleanest thing
		to do is just return true. */
		if (dot_at_end())
			return true;

		/* walk down the rhs and bail if we get a non-nullable symbol */
		for (int pos = dot_pos() + 1; pos < the_production().rhs_length(); pos++)
		{
			part = the_production().rhs(pos);

			/* skip actions */
			if (!part.is_action())
			{
				sym = ((symbol_part) part).the_symbol();

				/* if its a terminal we fail */
				if (!sym.is_non_term())
					return false;

				/* if its not nullable we fail */
				if (!((non_terminal) sym).nullable())
					return false;
			}
		}

		/* if we get here its all nullable */
		return true;
	}

	/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/

	/** Equality comparison -- here we only require the cores to be equal since
	 *   we need to do sets of items based only on core equality (ignoring 
	 *   lookahead sets). 
	 */
	public boolean equals(lalr_item other)
	{
		if (other == null)
			return false;
		return super.equals(other);
	}

	/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/

	/** Generic equality comparison. */
	public boolean equals(Object other)
	{
		if (!(other instanceof lalr_item))
			return false;
		else
			return equals((lalr_item) other);
	}

	/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/

	/** Return a hash code -- here we only hash the core since we only test core
	 *  matching in LALR items. 
	 */
	public int hashCode()
	{
		return super.hashCode();
	}

	/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/

	/** Convert to string. */
	public String toString()
	{
		String result = "";

		// additional output for debugging:
		// result += "(" + obj_hash() + ")"; 
		result += "[";
		result += super.toString();
		result += ", ";
		if (lookahead() != null)
		{
			result += "{";
			for (int t = 0; t < terminal.number(); t++)
				if (lookahead().contains(t))
					result += terminal.find(t).name() + " ";
			result += "}";
		}
		else
			result += "NULL LOOKAHEAD!!";
		result += "]";

		// additional output for debugging:
		// result += " -> ";
		// for (int i = 0; i<propagate_items().size(); i++)
		//   result+=((lalr_item)(propagate_items().elementAt(i))).obj_hash()+" ";
		//
		// if (needs_propagation) result += " NP";

		return result;
	}
	/*-----------------------------------------------------------*/
}
