// Goldie: GOLD Engine for D
// Grammar Compiler
// Written in the D programming language.

module goldie.grmc.genlalr;

import std.stdio;
import std.string;

import semitwist.util.all;
import goldie.base;

private Symbol[] symbolTable;
private Rule[] ruleTable;
private int startRuleId;
private int startSymbolIndex;
private int eofSymbolIndex;
private int initialLALRState;
private bool goldCompat; // GOLD-Compatibility Mode

private final class _LALRItem
{
	// -- Fields populated by genStates() ------

	int ruleId;
	
	// The value of this is position of the symbol immediately after the marker. Ie:
	//   marker == 0: Marker is at the beginning
	//   marker == theRule.subSymbolIndicies.length: Marker is at the end
	int marker;
	
	_LALRState gotoState;
	
	// -- Fields populated by genLookaheads() ------

	// IDs of the lookahead symbols
	int[] lookaheadIDs;
	
	// The items that directly inherit this item's lookahead symbols
	_LALRItem[] copyLookaheadsTo;

	// -- Funcs ------
	
	string toString(int id, int gotoStateId)
	{
		auto rule = ruleTable[ruleId];
		string str =
			"Item %s: Goto State %s: %s ::=".format(
				id,
				gotoStateId,
				symbolTable[rule.symbolIndex].name
			);

		foreach(index, subSymId; rule.subSymbolIndicies)
		{
			if(index == marker)
				str ~= " {DOT}";
			str ~= " ";
			str ~= symbolTable[subSymId].name;
		}
		
		if(marker == rule.subSymbolIndicies.length)
			str ~= " {DOT}";
		
		if(lookaheadIDs.length != 0)
		{
			str ~= "\n    LA:  ";
			foreach(currID; lookaheadIDs)
			{
				str ~= " ";
				str ~= symbolTable[currID].name;
			}
		}
		
		return str;
	}

	bool isIn(_LALRItem[] haystack)
	{
		foreach(item; haystack)
		{
			if(item.ruleId == ruleId && item.marker == marker)
				return true;
		}
		return false;
	}

	// ie, Immediately after
	@property bool isNonTerminalAfterMarker()
	{
		return
			symbolAfterMarker.id != -1 &&
			symbolAfterMarker.type == SymbolType.NonTerminal;
	}
	
	@property Symbol symbolAfterMarker()
	{
		if(marker >= rightHandSide.length)
			return Symbol("{Symbol Not Found}", SymbolType.Error, -1);
		
		return symbolTable[rightHandSide[marker]];
	}
	
	@property ref int[] rightHandSide()
	{
		return ruleTable[ruleId].subSymbolIndicies;
	}
	
	@property Symbol reducedSymbol()
	{
		return symbolTable[ruleTable[ruleId].symbolIndex];
	}
	
	// Prevents adding duplicates
	// Returns a bool indicating whether or not anything nothing was added
	bool addLookaheadIDs(int[] ids)
	{
		bool added = false;
		foreach(newId; ids)
		{
			if(!contains(lookaheadIDs, newId))
			{
				lookaheadIDs ~= newId;
				added = true;
			}
		}
		return added;
	}
}

private final class _LALRState
{
	// Populated by genStates
	_LALRItem items[];
	
	int id;
	
	string toString(_LALRState[] states)
	{
		string str = "State %s:".format(id);
		foreach(itemId, item; items)
		{
			auto rule = ruleTable[item.ruleId];
			int gotoStateId=-1;
			foreach(stateId, state; states)
			if(state is item.gotoState)
			{
				gotoStateId = stateId;
				break;
			}
			str ~= "\n" ~ indent(item.toString(itemId, gotoStateId), "  ");
		}
		return str;
	}
}

/// Generate an LALR table
public LALRState[] genLALRTable(
	Symbol[] symbolTable, Rule[] ruleTable,
	int startSymbolIndex, int eofSymbolIndex,
	out int initialLALRState, bool goldCompat=false)
{
	auto rootSymbolId = symbolTable.length;
	startRuleId = ruleTable.length;
	symbolTable ~= Symbol("<S'>", SymbolType.NonTerminal, rootSymbolId);
	ruleTable ~= Rule(rootSymbolId, [startSymbolIndex, eofSymbolIndex]);
	startSymbolIndex = rootSymbolId;
	
	.symbolTable      = symbolTable;
	.ruleTable        = ruleTable;
	.startSymbolIndex = startSymbolIndex;
	.eofSymbolIndex   = eofSymbolIndex;
	.goldCompat       = goldCompat;

	_LALRState[] states = genStates();
	genLookaheads(states);

	//foreach(state; states)
	//	writeln(state.toString(states));

	initialLALRState = .initialLALRState;
	return genFinalTable(states);
}

private _LALRState[] genStates()
{
	_LALRState[] states;
	_LALRState[] statesToProcess;

	bool isStartingItemOfRuleIn(int ruleId, _LALRItem[] items)
	{
		foreach(item; items)
		{
			if(item.marker == 0 && item.ruleId == ruleId)
				return true;
		}
		return false;
	}
	
	// Return all items that belong in the same state as the given starting items.
	// Parsing theory books usually call this the "closure" of the items.
	_LALRItem[] entireStateOf(_LALRItem[] items)
	{
		bool foundNewItems;
		auto updatedItems = items;
		items = [];
		do
		{
			foundNewItems = false;
			auto oldNumItems = items.length;
			items = updatedItems;
			foreach(i, item; items[oldNumItems..$])
			{
				if(item.isNonTerminalAfterMarker)
				foreach(ruleId, rule; ruleTable)
				if(rule.symbolIndex == item.symbolAfterMarker.id)
				if(!isStartingItemOfRuleIn(ruleId, items))
				{
					auto newItem = new _LALRItem();
					newItem.ruleId = ruleId;
					newItem.marker = 0;
					updatedItems ~= newItem;
					
					foundNewItems = true;
				}
			}
		} while(foundNewItems);

		return updatedItems;
	}
	
	bool stateExists(_LALRState state)
	{
		foreach(stateId, currState; states)
		if(currState.items.length >= state.items.length)
		{
			bool matches=true;
			foreach(stateItem; state.items)
			{
				if(!stateItem.isIn(currState.items))
				{
					matches = false;
					break;
				}
			}
			if(matches)
				return true;
		}
		
		return false;
	}
	
	void addState(_LALRState state)
	{
		if(!stateExists(state))
		{
			state.id = states.length;
			states ~= state;
			statesToProcess ~= state;
		}
	}
	
	_LALRState nextStateOf(_LALRState currState, int symId)
	{
		_LALRState newState;
		
		_LALRState getExistingStateFor(_LALRItem currItem)
		{
			foreach(state; states)
			foreach(item; state.items)
			if(item.ruleId == currItem.ruleId && item.marker == currItem.marker+1)
				return state;
			
			return null;
		}
		
		foreach(currItem; currState.items)
		if(currItem.symbolAfterMarker.id == symId)
		{
			// For consitency with GOLD, don't bother making state for:
			//    <S'> ::= {"Start Symbol"} EOF {DOT}
			if(symId == eofSymbolIndex && currItem.ruleId == startRuleId && currItem.marker == 1)
				return null;

			_LALRState existingState = null;
			if(newState is null)
				existingState = getExistingStateFor(currItem);
			
			if(existingState is null)
			{
				auto newItem = new _LALRItem();
				newItem.ruleId = currItem.ruleId;
				newItem.marker = currItem.marker+1;
			
				if(newState is null)
					newState = new _LALRState();
				
				bool itemAlreadyExists=false;
				foreach(nsi; newState.items)
				if(nsi.ruleId == newItem.ruleId && nsi.marker == newItem.marker)
					itemAlreadyExists = true;
				
				if(!itemAlreadyExists)
					newState.items ~= newItem;
			}
			else
				newState = existingState;
			
			currItem.gotoState = newState;
		}
		
		return newState;
	}
	
	auto startState = new _LALRState();
	foreach(ruleId, rule; ruleTable)
	if(rule.symbolIndex == startSymbolIndex)
	{
		startState.items ~= new _LALRItem();
		startState.items[$-1].ruleId = ruleId;
		startState.items[$-1].marker = 0;
	}
	addState(startState);
	initialLALRState = 0;
	
	while(statesToProcess.length > 0)
	{
		auto currState = statesToProcess[0];
		statesToProcess = statesToProcess[1..$];
		
		currState.items = entireStateOf(currState.items);

		foreach(symId, sym; symbolTable)
		{
			auto nextState = nextStateOf(currState, symId);

			if(nextState !is null)
				addState(nextState);
		}
	}

	return states;
}

private void genLookaheads(_LALRState[] states)
{
	_LALRItem[] findItems(int ruleId, int marker)
	{
		_LALRItem[]	ret;
		
		foreach(state; states)
		foreach(item; state.items)
		if(item.ruleId == ruleId && item.marker == marker)
			ret ~= item;

		return ret;
	}
	
	// Implementation for allFirstTerminals() below
	int[] allFirstTerminalsImpl(
		int[] symbolIDs, out bool canDeriveEmpty,
		int[] initFirstIDs=[], int[] recursionPath=[] )
	{
		int[] firstIDs = initFirstIDs;
		canDeriveEmpty = false;
		
		void addFirst(int id)
		{
			foreach(existingId; firstIDs)
			if(existingId == id)
				return;
			
			firstIDs ~= id;
		}
		
		void addFirsts(int[] ids)
		{
			foreach(id; ids)
				addFirst(id);
		}
		
		foreach(symId; symbolIDs)
		{
			auto sym = symbolTable[symId];
			if(sym.type == SymbolType.NonTerminal)
			{
				bool symDerivesEmpty = false;
				
				foreach(rule; ruleTable) if(rule.symbolIndex == sym.id)
				{
					bool ruleDerivesEmpty = true;
					if(!contains(recursionPath, sym.id))
					{
						firstIDs =
							allFirstTerminalsImpl(
								rule.subSymbolIndicies, ruleDerivesEmpty,
								firstIDs, recursionPath ~ sym.id
							);
					}

					if(ruleDerivesEmpty)
						symDerivesEmpty = true;
				}

				if(!symDerivesEmpty)
					return firstIDs;
			}
			else
			{
				addFirst(sym.id);
				return firstIDs;
			}
		}

		canDeriveEmpty = true;
		return firstIDs;
	}
	
	// Returns all the terminals that could possibly be first
	// in the derivation of the sequence provided.
	int[] allFirstTerminals(int[] symbolIDs)
	{
		bool canDeriveEmpty;
		return allFirstTerminalsImpl(symbolIDs, canDeriveEmpty);
	}

	bool canDeriveNothing(int symbolId)
	{
		bool ret;
		allFirstTerminalsImpl([symbolId], ret);
		return ret;
		
		// This is flawed, doesn't take into account when
		// each of rule.subSymbolIndicies can derive nothing (recursively)
		/+auto sym = symbolTable[symbolId];
		if(sym.type != SymbolType.NonTerminal)
			return false;
		
		foreach(rule; ruleTable)
		if(rule.symbolIndex == symbolId && rule.subSymbolIndicies.length == 0)
			return true;
		
		return false;+/
	}
	
	// Can all of the provided symbols derive nothing?
	bool allCanDeriveNothing(int[] symbolIDs)
	{
		bool ret;
		allFirstTerminalsImpl(symbolIDs, ret);
		return ret;
	
		/+foreach(symId; symbolIDs)
		if(!canDeriveNothing(symId))
			return false;
		
		return true;+/
	}
	
	/+auto initialState = states[initialLALRState];
	foreach(item; initialState.items)
		item.addLookaheadIDs([eofSymbolIndex]);+/
	
	// "Spontaneously generated" lookaheads
	foreach(state; states)
	foreach(item; state.items)
	{
		auto rhs = ruleTable[item.ruleId].subSymbolIndicies;

		if(item.symbolAfterMarker.id != -1)
		{
			if(item.gotoState !is null)
			foreach(item2; item.gotoState.items)
			if(item.ruleId == item2.ruleId && item.marker+1 == item2.marker)
				item.copyLookaheadsTo ~= item2;
			
			if(item.isNonTerminalAfterMarker)
			foreach(item2; state.items)
			if(item2.marker == 0 && item2.reducedSymbol == item.symbolAfterMarker)
			{
				auto rhsTail = rhs[item.marker+1..$];
				item2.addLookaheadIDs(allFirstTerminals(rhsTail));
				if(allCanDeriveNothing(rhsTail))
					item.copyLookaheadsTo ~= item2;
			}
		}
	}
	
	// "Propagated" lookaheads
	bool didPropagation = true;
	while(didPropagation)
	{
		didPropagation = false;
		foreach(state; states)
		foreach(item; state.items)
		foreach(targetItem; item.copyLookaheadsTo)
		{
			auto added = targetItem.addLookaheadIDs(item.lookaheadIDs);
			if(added)
				didPropagation = true;
		}
	}
}

private LALRState[] genFinalTable(_LALRState[] states)
{
	LALRState[] lalrTable;
	lalrTable.length = states.length;
	
	void addAction(int stateId, LALRAction newAction)
	{
		foreach(action; lalrTable[stateId].actions)
		if(action == newAction)
			return;
		
		lalrTable[stateId].actions ~= newAction;
	}
	
	foreach(stateId, state; states)
	foreach(item; state.items)
	{
		// Accept
		if(item.ruleId == startRuleId && item.marker == 1)
		{
			addAction(stateId, LALRAction(eofSymbolIndex, LALRAction.Type.Accept, 0));
			continue;
		}

		// Reduce
		if(item.gotoState is null)
		{
			foreach(lookaheadID; item.lookaheadIDs)
				addAction(stateId, LALRAction(lookaheadID, LALRAction.Type.Reduce, item.ruleId));

			continue;
		}
		
		auto sym = item.symbolAfterMarker;
		
		// Goto
		if(sym.type == SymbolType.NonTerminal)
		{
			addAction(stateId, LALRAction(sym.id, LALRAction.Type.Goto, item.gotoState.id));
			continue;
		}

		// Shift
		addAction(stateId, LALRAction(sym.id, LALRAction.Type.Shift, item.gotoState.id));
	}

	if(goldCompat)
		sortFinalTable(lalrTable);

	return lalrTable;
}

// For GOLD compatibility mode
private void sortFinalTable(ref LALRState[] lalrTable)
{
	int[] findActions(LALRAction[] actions, LALRAction.Type type)
	{
		int[] ret;
		
		foreach(index, action; actions)
		if(action.type == type)
			ret ~= index;
		
		return ret;
	}
	
	int[] sortActions(LALRAction[] actions, int[] oldOrder)
	{
		int[] newOrder;
		while(oldOrder.length > 0)
		{
			int firstSymId = int.max;
			int firstValue;
			int firstIndex;
			foreach(index, value; oldOrder)
			{
				auto symId = actions[value].symbolId;
				if(symId < firstSymId)
				{
					firstSymId = symId;
					firstValue = value;
					firstIndex = index;
				}
			}
			
			newOrder ~= firstValue;
			oldOrder =
				oldOrder[0..firstIndex] ~
				(firstIndex < oldOrder.length-1 ? oldOrder[firstIndex+1..$] : []);
		}
		return newOrder;
	}
	
	// Order: Accept, Shift, Goto, Reduce
	foreach(stateId; 0..lalrTable.length)
	{
		auto oldActions = lalrTable[stateId].actions.dup;
		int[] newAccepts = sortActions( oldActions, findActions(oldActions, LALRAction.Type.Accept) );
		int[] newShifts  = sortActions( oldActions, findActions(oldActions, LALRAction.Type.Shift ) );
		int[] newGotos   = sortActions( oldActions, findActions(oldActions, LALRAction.Type.Goto  ) );
		int[] newReduces = sortActions( oldActions, findActions(oldActions, LALRAction.Type.Reduce) );
		
		auto newOrder = newAccepts ~ newShifts ~ newGotos ~ newReduces;
		lalrTable[stateId].actions.length = 0;
		foreach(index; newOrder)
			lalrTable[stateId].actions ~= oldActions[index];
	}
}
