import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

public class Parser {
	private BufferedReader reader;
	private int input;
	private int rowIndex = 0;
	private int columnIndex = -1;
	private String name;
	private DependencyResolver dependencyResolver;
	private Stack<ParserInputSource> sources = new Stack<ParserInputSource>();
	public Parser() {
		//this.startParsing(reader, name);
		this.dependencyResolver = new DependencyResolver(this);
	}
	private void startParsing(BufferedReader reader, String name) {
		pushState();
		this.reader = reader;		
		this.name = name;
		this.rowIndex = 0;
		this.columnIndex = -1;
	}
	protected void pushState() {
		this.sources.push(new ParserInputSource(reader, name, input, rowIndex, columnIndex));
	}
	protected void popState() {
		ParserInputSource source = this.sources.pop();
		reader = source.getReader();
		name = source.getName();
		input = source.getInput();
		rowIndex = source.getRowIndex();
		columnIndex = source.getColumnIndex();
	}
	public Object parse(BufferedReader reader, String name) {
		startParsing(reader, name);
		consume();
		parseOptionalWhitespace();
		Object result = parseRequires1(new HashSet<String>()); // skip requires.
		if(result == null) /* none pending */
			result = parseExpression(); /* get one */
		popState();
		return(result);
	}
	protected Object parseExpression() {
		return isListOpener(input) ? parseList() : 
               isSymbol1Character(input) ? parseSymbol() :
               raiseError("<expression>");
	}
	private Object parseList() {
		int opener = input;
		if(!isListOpener(input))
			return raiseError("<list>");
		consume();
		parseOptionalWhitespace();
		
		Integer closer = (opener == '(') ? ')' :
			             (opener == '[') ? ']' :
			             (Integer) raiseError("<list-opener>");
		
		Object result = parseListBody(closer);
		return processMacros(result);
	}
	public Object processMacros(Object source) {
		if(source == null || !(source instanceof Node))
			return source;
		//System.out.println("processMacros " + source);
		Node sourceNode = (Node) source;
		Object head = sourceNode.getHead();
		Node rest = sourceNode.getRest();
		if(head == null || !(head instanceof Symbol))
			return source;
		return (head == Symbol.intern("subst")) ? processSubstMacro(rest) :
		       (head == Symbol.intern("do")) ? processDoMacro(rest) :
		       (head == Symbol.intern("include")) ? processIncludeMacro(rest) : 
		       (head == Symbol.intern("cond")) ? processCondMacro(rest) :
		       (head == Symbol.intern("make-list")) ? processListMacro(rest) :
		       (head == Symbol.intern("define")) ? processDefineMacro(rest) :
		       (head == Symbol.intern("quote")) ? processQuoteMacro(rest) :
		       (head == Symbol.intern("case")) ? processCaseMacro(rest) :
			   source;
	}
	private Object processCaseMacro(Node rest) { /* (case <comparator> <expression> ((<value> <value-2>) <consequence>) [...]) */
		Object comparator = rest.getHead();
		Object expression = rest.getRest().getHead();
		Node rCases = rest.getRest().getRest();
		Node result = new Node(Symbol.intern("cond"), convertCasesToCond(comparator, expression, rCases));
		//System.out.println("processCaseMacro => " + result.toString());
		return result;
	}
	private static Node convertCasesToCond(Object comparator, Object expression, Node rest) {
		return (rest == null) ? null : new Node(convertCaseToCond(comparator, expression, (Node) rest.getHead()), convertCasesToCond(comparator, expression, rest.getRest()));
	}
	private static Node convertCaseToCond(Object comparator, Object expression, Node rest) {
		Node possibleValues = (Node) rest.getHead();
		Node rConsequence = rest.getRest();
		assert(rConsequence != null);
		Object consequence = rConsequence.getHead();
		return makeList(convertPossibleValuesToLogic(comparator, expression, possibleValues), consequence);
	}
	private static Object convertPossibleValuesToLogic(Object comparator, Object expression, Node possibleValues) {
		if(possibleValues == null)
			return Symbol.intern("#f");
		else {
			Object rest = convertPossibleValuesToLogic(comparator, expression, possibleValues.getRest());
			return (possibleValues.getRest() != null) ? makeList(Symbol.intern("||"), makeList(comparator, expression, possibleValues.getHead()), rest) 
					                                  :                               makeList(comparator, expression, possibleValues.getHead());
		}
	}
	private Object processQuoteMacro(Node rest) {
		assert(rest.getRest() == null);
		return rest.getHead();
	}
	protected boolean symbolInFormP(Symbol needle, Object form) {
		if(form instanceof Node) {
			Node formNode = (Node) form;
			Object head = formNode.getHead();
			if(head instanceof Symbol && head == Symbol.intern("\\")) { // lambda parameter: ignore
				Symbol parameterName = (Symbol) formNode.getRest().getHead();
				if(parameterName == needle)
					return false;
				else
					return symbolInFormP(needle, ((Node) form).getHead()) || symbolInFormP(needle, ((Node) form).getRest());
			} else
				return symbolInFormP(needle, ((Node) form).getHead()) || symbolInFormP(needle, ((Node) form).getRest());
		} else if(form instanceof Symbol) {
			return(form == needle);
		} else if(form == null)
			return false;
		else {
			System.err.println("symbolInFormP: ignoring weird thing " + form);
			return false;
		}
	}
	private Object processDefineMacro(Node rest) {
		Object pattern = rest.getHead();
		Node restRest = rest.getRest();
		Object body = restRest.getHead();
		assert(restRest.getRest() == null);
		
		if(pattern instanceof Node) { /* (define (f x) x) */
			Node patternNode = (Node) pattern;
			Symbol name = (Symbol) patternNode.getHead();
			body = processDefineParameters(body, patternNode.getRest());
			if(symbolInFormP(name, body)) { // self-recursion
				// TODO auto-Y.
				body = makeList(Symbol.intern("Y"), makeList(Symbol.intern("\\"), name, body));
			}
			Node result = makeList(patternNode.getHead(), body);
			//System.out.println("define => " + result);
			return(result);
		} else { /* (define x 3) */
			return rest; /* (x 3) */
		}
	}
	private Object processDefineParameters(Object body, Node pattern) {
		return(pattern == null) ? body : makeList(Symbol.intern("\\"), pattern.getHead(), processDefineParameters(body, pattern.getRest()));
	}
	private Object processListMacro(Node rest) {
		if(rest == null)
			return Symbol.intern("nil");
		else if(!(rest instanceof Node))
			return raiseError("<node>");
		else {
			Object head = rest.getHead();
			Node nextRest = rest.getRest();
			return makeList(Symbol.intern("cons"), head, processListMacro(nextRest));
		}
	}
	private Object processCondMacro(Node rest) {
		if(rest == null)
			return null; // raiseError("<all cases handled>", "<incomplete cond>");
		else if(!(rest instanceof Node))
			return raiseError("<node>");
		else {
			Node entry = (Node) rest.getHead();
			Object condition = entry.getHead();
			Object consequence = entry.getRest().getHead();
			if(entry.getRest().getRest() != null)
				return raiseError("(<condition> <consequence>)");
			return makeList(Symbol.intern("if"), processMacros(condition), processMacros(consequence), processCondMacro(rest.getRest()));
		}
	}
	private Object processSubstMacro(final Node rest) {
		Object source;
		if(!(rest instanceof Node))
			return raiseError("<node>");
		final Object body = processMacros(rest.getHead());
		final Node xvariables = (Node) processMacros(rest.getRest().getHead());
		Node lambdaized = (Node) Node.accumulate(new NodeCallback() {
			@Override
			public Object callback2(Object result, Object item) {
				if(!(item instanceof Node)) {
					System.err.println(String.format("info: variables were: %s", xvariables));
					System.err.println(String.format("info: macro-containing node was: %s", rest.toString()));
					return raiseError("<node>", item.toString());
				} else {
					Node itemNode = (Node) item;
					Object name = itemNode.getHead();
					//Object value = itemNode.getRest().getHead();
					assert(name instanceof Symbol);
					//System.out.println(item);
					return new Node(Symbol.intern("\\"), new Node(name, new Node(result, null)));
				}
			}
		}, body, xvariables);
		source = Node.reverseAccumulate(new NodeCallback() {
			@Override
			public Object callback2(Object result, Object item) {
				if(!(item instanceof Node))
					return raiseError("<node>");
				else {
					Node itemNode = (Node) item;
					//Object name = itemNode.getHead();
					Object value = itemNode.getRest().getHead();
					//assert(name instanceof Symbol);
					//System.out.println(item);
					return new Node(result, new Node(value, null));
				}
			}
		}, lambdaized, xvariables);
		//System.out.println("after macro expansion: " + source);
		return source;
	}
	private Object processDoChain(Node l) { // FIXME test.
        // ((do expr expr* ...)   (do expr (do expr* ...))))) 			 
		if(l.getRest() == null)
			return l.getHead();
		return new Node(Symbol.intern("do"), new Node(l.getHead(), new Node(processDoChain(l.getRest()), null)));
	}
	public static Node makeList(Object a, Object b) {
		return new Node(a, new Node(b, null));
	}
	public static Node makeList(Object a, Object b, Object c) {
		return new Node(a, new Node(b, new Node(c, null)));
	}
	public static Node makeList(Object a, Object b, Object c, Object d) {
		return new Node(a, new Node(b, new Node(c, new Node(d, null))));
	}	
	private Object processDoMacro(Node rest) {
		/*
		  (define-syntax do
		       (syntax-rules (<-)
		         ((do expr)             expr)
		         ((do (v <- expr) rest) (monad1-pipe expr (lambda (v) rest)))
		         ((do expr expr)        (monad1-pipe (monad1-set expr) (lambda (dummy) expr)))
		         ((do expr expr* ...)   (do expr (do expr* ...))))) 			 
					 */
		System.out.println("do " + rest);
		if(!(rest instanceof Node))
			return raiseError("<node>");
		//final Object body = processMacros(rest.getHead());
		//final Node xvariables = (Node) processMacros(rest.getRest().getHead());
		Object a = rest.getHead(); // either expr or (v <- expr). Note that expr can be (v <- foo) accidentially as well. Not sure what should happen then - probably ignore?
		if(rest.getRest() != null && rest.getRest().getRest() != null) { // (do expr expr* ...)
			Object x = processDoChain(rest);
			System.out.println("AFTER CHAIN " + x);
			return processMacros(x);
			//=return (do expr (do expr* ...)); // recursive processMacros.
		} else if(a instanceof Node && ((Node) a).getRest() != null && (((Node) a).getRest().getHead() == Symbol.intern("<-") || ((Node) a).getRest().getHead() == Symbol.intern(":="))) { // arrow expression. TODO mandatory tail "rest".
			Node aNode = (Node) a;
			Object lambdaParameter = aNode.getHead();
			assert(lambdaParameter instanceof Symbol);
			Node expr = aNode.getRest().getRest();
			Node rest2 = rest.getRest();
			Object rest2H = rest2.getHead();
			assert(rest2.getRest() == null);
			Node LAMBDA = makeList(Symbol.intern("\\"), lambdaParameter, processMacros(rest2H));
			Object exprH = expr.getHead();
			assert(expr.getRest() == null);
			Node result = makeList(Symbol.intern("monad1-pipe"), exprH, LAMBDA);
			System.out.println("DO RES " + result);
			return(result);
			//= return (monad1-pipe expr (lambda (lambdaParameter) rest2)));
		} else if(rest.getRest() == null) { // normal expression, end of the line. (do expr)
			return a; // FIXME macro recursion?
		} else if(rest.getRest() instanceof Node) { // normal expression, not end.
			Node restNode = (Node) rest;
			if(restNode.getRest().getRest() == null) { // (do expr expr)
				Object firstArg = restNode.getHead();
				Node restRestNode = (Node) restNode.getRest();
				Object secondArg = restRestNode.getHead();
				// FIXME macro recursion?
				Node setCall = new Node(Symbol.intern("monad1-set"), new Node(firstArg, null));
				Node LAMBDA = new Node(Symbol.intern("\\"), new Node(Symbol.intern("v4711") /* FIXME hygienic (i.e. unmatchable) */, new Node(processMacros(secondArg), null)));
 				return new Node(Symbol.intern("monad1-pipe"), new Node(setCall, new Node(LAMBDA, null)));
				//=return (monad1-pipe (monad1-set expr) (lambda dummy expr)));
			}
		}
		return raiseError("<do-body>");
		//source = ;
	}
	protected Object processIncludeMacro(Node rest) {
		assert(rest.getRest() == null);
		Object fileNameO = rest.getHead();
		Symbol fileNameS = (Symbol) fileNameO;
		return(parseFile(DependencyResolver.processRelativePath(this.name, fileNameS)));
	}
	public static BufferedReader openFile(String fileName) {
		FileReader inputStream;
		BufferedReader reader = null;
		try {
			inputStream = new FileReader(fileName);
			reader = new BufferedReader(inputStream);
		} catch(FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
			System.exit(1); // FIXME
		}
		return(reader);
	}
	public Object parseFileInternal(String fileName) {
		BufferedReader reader = openFile(fileName);
		return(parse(reader, fileName));
	}
	public Object parseFile(String fileName) {
		return(dependencyResolver.generateSubstTree(dependencyResolver.resolve(fileName).iterator()));
	}
	protected void parseOptionalWhitespace() {
		while(isWhitespace(input)) {
			if(input == ';')
				parseLineComment();
			else
				consume();
		}
	}
	private void parseLineComment() {
		while(input != 10)
			consume();
		consume();
		parseOptionalWhitespace();
	}
	protected void parseWhitespace() {
		if(!isWhitespace(input))
			raiseError("<whitespace>");
		parseOptionalWhitespace();
	}
	private boolean isWhitespace(int input) {
		return input == ' ' || input == '\t' || input == '\n' || input == 13 || input == 10 || input == ';';
	}
	private Object parseListBody(int closer) {
		if(input == closer) {
			consume();
			parseOptionalWhitespace();
			return null;
		}
		Object head = parseExpression();
		Object rest = parseListBody(closer);
		if(rest != null && !(rest instanceof Node))
			rest = new Node(rest, null); 
		return new Node(head, (rest != null) ? (Node) rest : null);
	}
	protected static boolean isSymbol1Character(int input) {
		return (input >= 'A' && input <= 'Z') || (input >= 'a' && input <= 'z') || (input == '\\') || (input >= '0' && input <= '9') || (input >= 42 && input < 48) || (input == '#') || (input == '&') || (input == '|') || (input == '<') || (input == '>') || (input == '=') || (input == ':') || (input == '"' /* FIXME extra string parser */) || (input >= 128/*assuming UTF-8*/) || (input == '/');
		// TODO [_a-zA-Z!0&*/:<=>?^][_a-zA-Z!0&*/:<=>?^0-9.+-]*
	}
	protected static boolean isSymbolCharacter(int input) {
		return isSymbol1Character(input) || (input == '_') || isDecimalDigit(input) || (input == '?') || (input == '!') || (input == '"'/*FIXME extra string parser? */) || (input >= 128) || (input == '/') || (input == '-');
		// TODO [_a-zA-Z!0&*/:<=>?^][_a-zA-Z!0&*/:<=>?^0-9.+-]*
	}
	protected static boolean isListOpener(int input) {
		return (input == '(') || (input == '[');
	}
	protected static boolean isDecimalDigit(int input) {
		return (input >= '0') && (input <= '9');
	}
	protected static boolean isLambda(int input) {
		return (input == '\\');
	}
	protected Object parseSymbol() {
		StringBuffer buffer = new StringBuffer();
		if(!isSymbol1Character(input))
			return raiseError("<symbol>");
		if(input == '\\') {
			consume();
			parseOptionalWhitespace();
			return Symbol.intern("\\");
		} else {
			while(isSymbolCharacter(input))
				buffer.append(consume());
			parseOptionalWhitespace();
			return Symbol.intern(buffer.toString());
		}
	}
	private Object raiseError(String expectedString) {
		String s = "";
		s += (char) input;
		return raiseError(expectedString, (input >= 32 && input < 128) ? s : 
		                                  (input == 10) ? "<newline>" : 
		                                  (input == 13) ? "<CR>" :
		                                  (input == -1) ? "<end-of-file>" : 
		                                  Integer.toString(input));
	}
	private Object raiseError(String expectedString, String gotString) {
		System.err.println(String.format("\"%s\": expected %s but got %s near line %d, column %d", name, expectedString, gotString, rowIndex + 1, columnIndex + 1));
		System.exit(1);
		return null;
	}
	public char consume() {
		char oldInput = (char) input;
		++columnIndex;
		if(oldInput == '\n') {
			columnIndex = 0;
			++rowIndex;
		}
		
		try {
			input = reader.read();
		} catch (IOException e) {
			input = -1;
		}
		return oldInput;
	}
	
	/** @return the next pending, unhandled, expression, if any */
	protected Object parseRequires1(Set<String> result) {
		while(input != -1) {
			Object require = parseExpression();
			if(require instanceof Node && ((Node) require).getHead() == Symbol.intern("require")) {
				Node requireNode = (Node) require;
				for(Node args = requireNode.getRest(); args != null; args = args.getRest()) {
					Symbol entry = (Symbol) args.getHead();
					assert(entry != null);
					result.add(DependencyResolver.processRelativePath(this.name, entry));
				}
			} else
				return require;
			parseOptionalWhitespace();
		}
		return null;
	}
	public static String unescapeString(Symbol entry) {
		String entryString = entry.toString();
		assert(entryString.startsWith("\""));
		assert(entryString.endsWith("\""));
		return(entryString.substring(1, entryString.length() - 1)); /* FIXME actually unescape */
	}
	public Set<String> parseRequires(BufferedReader reader, String name) {
		startParsing(reader, name);
		consume();
		Set<String> result = new HashSet<String>();
		parseOptionalWhitespace();
		parseRequires1(result);
		popState();
		return result;
	}
}