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

module /+S:PACKAGE+/goldie/+E:PACKAGE+/.parser;

/+P:SET_VERSION+/

import std.stdio;
import std.string;

import semitwist.util.all;

import goldie.base;
import goldie.exception;
import goldie.lang;
import goldie.lexer;
import goldie.token;

version(GoldieStaticLang) import goldie.parser;
version(GoldieStaticLang) import /+P:PACKAGE+/DUMMY.token;

//TODO? Optionally generate recording of steps taken
//TODO: Make parser steppable
/+S:PARSER_INHERIT+/class Parser/+E:PARSER_INHERIT+/
{
	/+S:REM+/
	int[] rulesUsed;
	Token[] tokenStack;
	int[] stateStack;
	
	Token parseTreeX;
	Lexer lexer;
	Language lang;
	string filename;
	
	Token currTok;

	int tokIndex;
	int state;

	protected LALRState[] lalrTable;
	protected Rule[]      ruleTable;
	protected Symbol[]    symbolTable;
	protected void getTables(Language lang)
	{
		lalrTable   = lang.lalrTable;
		ruleTable   = lang.ruleTable;
		symbolTable = lang.symbolTable;
	}
	/+E:REM+/

	version(GoldieStaticLang)
		/+P:TOKEN_CLASSNAME_TOPNODE+/DUMMY parseTree;
	
	/+P:OVERRIDE+/ Token process(Token[] tokens, Language lang, string filename="", Lexer lexer=null)
	{
		tokenStack.length = 0;
		stateStack.length = 0;
		rulesUsed.length = 0;
		parseTreeX = null;
		currTok = null;
		this.lexer = lexer;
		this.lang = lang;
		this.filename = filename;
		
		tokIndex=0;
		state=lang.initialLALRState;

		bool done=false;
		
		getTables(lang);
		
		Token getPendingToken()
		{
			Token tok;
			bool inComment=false;
			bool lineComment;
			do
			{
				if(tokIndex >= tokens.length)
					throw new UnexpectedEofException(this);

				tok = tokens[tokIndex];
				currTok = tok;
				tokIndex++;
				
				// Handle comments
				if(!inComment)
				{
					switch(tok.type)
					{
					case SymbolType.CommentLine:
						inComment = true;
						lineComment = true;
						break;
					case SymbolType.CommentStart:
						inComment = true;
						lineComment = false;
						break;
					default:
						break;
					}
				}
				else
				{
					if(lineComment)
					{
						auto tokContent = tok.toString(TokenToStringMode.Full);
						if(contains(tokContent, "\n"[0]) || contains(tokContent, "\r"[0]))
							inComment = false;
					}
					else
					{
						if(tok.type == SymbolType.CommentEnd)
							inComment = false;
					}
				}
			} while(inComment || // End of do-while
			         (
				         tok.type != SymbolType.Terminal &&
			             tok.type != SymbolType.EOF
			         )
			     );
				 
			tokIndex--;
			return tok;
		}

		void shift()
		{
			tokenStack ~= getPendingToken();
			stateStack ~= state;
			tokIndex++;
		}
		
		LALRAction chosenAction;
		int chosenActionId;
		bool actionFound;

		void lookupAction(Token tok)
		{
			actionFound=false;
			foreach(int id, LALRAction action; lalrTable[state].actions)
			{
				if(tok.id == action.symbolId)
				{
					chosenAction = action;
					chosenActionId = id;
					actionFound = true;
					break;
				}
			}
			//mixin(traceVal!("tok", "tok.id", "actionFound", "chosenActionId", "chosenAction"));
			//mixin(traceVal!("actionFound", "chosenAction.type"));
		}
		
		void displayStack()
		{
			foreach(Token tok; tokenStack)
			{
				writefln(
					"    %s(%s): %-25s '%s'",
					tok.file, tok.line+1,
					tok.fullName ~ ":",
					tok.toString(TokenToStringMode.Full)
				);
			}
		}
		
		while(!done)
		{
			auto tok = getPendingToken();
			lookupAction(tok);
			
			if(actionFound)
			{
				switch(chosenAction.type)
				{
				case LALRAction.Type.Shift:
					shift();
					state = chosenAction.target;
					//mixin(traceVal!("chosenActionId"));
					//writefln(`Shift:  %-10s new state: %s`,
					//         `"`~tok.toStringRaw()~`"`, state);
					//displayStack();
					break;

				case LALRAction.Type.Reduce:
					auto rule = ruleTable[chosenAction.target];
					auto reductionSize = rule.subSymbolIndicies.length;
					if(tokenStack.length < reductionSize)
						throw new InternalException(
							this, 
							"Tried to reduce more tokens than exist on the stack. Have %s, need %s, rule #%s"
								.format(tokenStack.length, reductionSize, chosenAction.target)
						);
					rulesUsed ~= chosenAction.target;
					
					// Perform Reduction
					Token[] reducedTokens;
					if(reductionSize > 0)
					{
						auto reductionStart = tokenStack.length - reductionSize;
						reducedTokens = tokenStack[reductionStart..$].dup;
						tokenStack = tokenStack[0..reductionStart];
						state = stateStack[reductionStart];
						stateStack = stateStack[0..reductionStart];
					}

					Token reducedToken;
					/+S:REM+/
					reducedToken = new Token
						(symbolTable[rule.symbolIndex], reducedTokens, lang, chosenAction.target);
					/+E:REM+/

					version(GoldieStaticLang)
					{
						/+S:REDUCE:STORE+/
							reducedToken = new /+P:REDUCE:TOKEN_CLASSNAME+/DUMMY(reducedTokens, lang);
						/+E:REDUCE:STORE+/
						/+P:REDUCE+/
					}
					
					tokenStack ~= reducedToken;
					stateStack ~= state;
					
					// Ensure reduced tokens symbols match the rule's right-side
					if(reducedTokens.length != reductionSize)
						throw new InternalException(
							this,
							"Reduced an incorrent number of tokens. Expected %s, Actual %s"
								.format(reductionSize, reducedTokens.length)
						);
						
					foreach(int i, Token t; reducedTokens)
					{
						if(t.id() != rule.subSymbolIndicies[i])
							throw new InternalException(
								this,
								`Reduced token #%s does not match rule. Expected "%s", Actual "%s"`
									.format(i, symbolTable[rule.subSymbolIndicies[i]].name, t.name)
							);
					}
					//mixin(traceVal!("chosenActionId"));
					//writef(`Reduce: %-15s (next: "%s") new state: %s`,
					//       `"`~reducedToken.name~`"`, tok.toStringRaw(), state);
					
					// Find and perform goto
					lookupAction(reducedToken);
					if(!actionFound)
						throw new ParseException(this, "Couldn't find appropriate goto after reduction.");
					if(chosenAction.type != LALRAction.Type.Goto)
						throw new InternalException(
							this,
							"After reduction, found action type #%s instead of goto."
								.format(chosenAction.type)
						);
					
					state = chosenAction.target;
					//writefln(`, %s`, state);
					//displayStack();
					break;

				case LALRAction.Type.Goto:
/*					
					state = chosenAction.target;
					writefln(`Goto: "%s", state -> %s`,
					         tok.name, state);
*/
					throw new InternalException(this, "Unexpected Goto");

				case LALRAction.Type.Accept:
					if(tokIndex < tokens.length-1)
						throw new InternalException(
							this,
							"Extra tokens exist beyond end of parsing. Current token: #%s of %s"
								.format(tokIndex, tokens.length)
						);
					done = true;
					//Stdout.formatln(`Accept!`);
					break;

				default:
					throw new InternalException(
						this,
						"Unknown action type (#%s) found when parsing. LALR state #%s"
							.format(chosenAction.type, state)
					);
				}
			}
			else
			{
				throw new UnexpectedTokenException(this);
			}
			
			if(tokenStack.length != stateStack.length)
				throw new InternalException(
					this,
					"tokenStack[%s] and stateStack[%s] sizes out of sync."
						.format(tokenStack.length, stateStack.length)
				);
		}
		
		if(tokenStack.length == 1)
		{
			if(!tokenStack[0])
				throw new InternalException("At end of parsing, parse tree root is null");

			if(tokenStack[0].id != lang.startSymbolIndex)
			{
				throw new InternalException(
					"At end of parsing, parse tree root is wrong symbol: '%s', expected '%s'"
						.format(
							symbolTable[tokenStack[0].id],
							symbolTable[lang.startSymbolIndex]
						)
				);
			}
			parseTreeX = tokenStack[0];
			version(GoldieStaticLang)
			{
				parseTree = cast(typeof(parseTree))parseTreeX;
			}
		}
		else
			throw new InternalException("At end of parsing, length of token stack is %s, expected 1.".format(tokenStack.length));

		return parseTreeX;
	}
}
