context: using System;
  using System.Collections.Generic;
  using System.Linq;
  using System.Text;
  using System.Diagnostics;
  using Loyc.Utilities;
  using Loyc.Syntax;
  using Loyc.Collections;
  
  namespace Loyc.LLParserGenerator
  {
  	using Ecs;
  	using S = CodeSymbols;
  
  	/// <summary>
  	/// Parses <see cref="LNode"/>s such as <c>(x | ("foo", y)) / z</c>
  	/// into <see cref="Pred"/> objects.
  	/// </summary>
  	internal class StageTwoParser
  	{
  		IPGCodeGenHelper _helper;
  		IMessageSink _sink;
  		Dictionary<Symbol, Rule> _rules;
  		public Dictionary<Symbol, Rule> Rules { get { return _rules; } }
  		public bool _ruleChangesInRecognizer;
  		public bool _parsingRecognizerVersion;
  		public bool _insideRecognizerSequence = false;
  
  		public StageTwoParser(IPGCodeGenHelper helper, IMessageSink sink)
  		{
  			_helper = helper;
  			_sink = sink;
  		}
  
  		HashSet<Symbol> any_in_HashLabels = new HashSet<Symbol> { (Symbol)"#token" };
  
  		/// <summary>Given Rules paired with LNodes produced by <see cref="StageOneParser"/>,
  		/// this method translates each LNode into a <see cref="Pred"/> and updates
  		/// <see cref="Rule.Pred"/> to point to the new Pred.</summary>
  		public void Parse(IEnumerable<Pair<Rule,LNode>> rules)
  		{
  			_rules = LLParserGenerator.AddRulesToDict(rules.Select(p => p.A));
  			foreach (var pair in rules)
  			{
  				Debug.Assert(pair.A.Pred == null);
  
  				_parsingRecognizerVersion = _ruleChangesInRecognizer = false;
  				pair.A.Pred = NodeToPred(pair.B);
  
  				if (_ruleChangesInRecognizer) {
  					_parsingRecognizerVersion = true;
  					pair.A.GetOrMakeRecognizerVersion().Pred = NodeToPred(pair.B);
  				} else if (pair.A.HasRecognizerVersion) {
  					pair.A.Recognizer.Pred = pair.A.Pred;
  				}
  			}
  
  			Remove_any_in_Labels();
  		}
  
  		static LNodeFactory F = new LNodeFactory(new EmptySourceFile("LLLPG parser"));
  		static readonly Symbol _Gate = S.Lambda;
  		static readonly Symbol _EqGate = GSymbol.Get("'<=>");
  		static readonly Symbol _AddColon = GSymbol.Get("'+:");
  		static readonly Symbol _Star = GSymbol.Get("'suf*");
  		static readonly Symbol _Plus = GSymbol.Get("'suf+");
  		static readonly Symbol _Opt = GSymbol.Get("'suf?");
  		static readonly Symbol _And = S.AndBits;
  		static readonly Symbol _AndNot = GSymbol.Get("'&!");
  		static readonly Symbol _nongreedy = GSymbol.Get("nongreedy");
  		static readonly Symbol _greedy = GSymbol.Get("greedy");
  		static readonly Symbol _default = GSymbol.Get("default");
  		static readonly Symbol _default2 = GSymbol.Get("'default");
  		static readonly Symbol _inline = GSymbol.Get("inline");
  		static readonly Symbol _inline2 = GSymbol.Get("#inline");
  		static readonly Symbol _noinline = GSymbol.Get("noinline");
  		static readonly Symbol _error = GSymbol.Get("error");
  		static readonly Symbol _DefaultError = GSymbol.Get("default_error");
  		static readonly Symbol _Local = GSymbol.Get("Local");
  		static readonly Symbol _Hoist = GSymbol.Get("Hoist");
  		static readonly Symbol _any = GSymbol.Get("any");
  		static readonly Symbol _recognizer = GSymbol.Get("recognizer");
  		static readonly Symbol _nonrecognizer = GSymbol.Get("nonrecognizer");
  
  		enum Context { Rule, GateLeft, GateRight, And };
  
  		Pred NodeToPred(LNode expr, Context ctx = Context.Rule)
  		{
  			try {
  				return NodeToPredCore(expr, ctx);
  			} catch (Exception ex) {
  				_sink.Error(expr, ex.ExceptionMessageAndType());
  				return new TerminalPred(expr, _helper.EmptySet);
  			}
  		}
  		Pred NodeToPredCore(LNode expr, Context ctx = Context.Rule)
  		{
  			if (expr.IsCall)
  			{
  				bool slash = false, not;
  				var name = expr.Name;
  				if (name == S.Tuple)
  				{
  					// sequence: (a, b, c)
  					if (expr.Calls(S.Tuple, 1))
  						return NodeToPred(expr.Args[0], ctx);
  					return TranslateToSeq(expr, ctx);
  				}
  				else if (name == S.Braces)
  				{
  					// User action {block}
  					if (ctx == Context.And || ctx == Context.GateLeft) {
  						_sink.Error(expr, ctx == Context.And ?
  							"Cannot use an action block inside an '&' or '&!' predicate; these predicates are for prediction only." :
  							"Cannot use an action block on the left side of a '=>' gate; the left side is for prediction only.");
  					}
  					return new ActionPred(expr, expr.Args) { AllowInRecognizer = _insideRecognizerSequence };
  				}
  				else if (expr.Calls(S.OrBits, 2) || (slash = expr.Calls(S.Div, 2)))
  				{
  					// alternatives: a | b, a || b, a / b
  					LNode lhs = expr.Args[0], rhs = expr.Args[1];
  					BranchMode lhsMode, rhsMode;
  					Pred left = BranchToPred(lhs, out lhsMode, ctx);
  					Pred right = BranchToPred(rhs, out rhsMode, ctx);
  					return Pred.Or(left, right, slash, expr, lhsMode, rhsMode, _sink);
  				}
  				else if (expr.Calls(_Star, 1) || expr.Calls(_Plus, 1) || expr.Calls(_Opt, 1))
  				{
  					// loop (a+, a*) or optional (a?)
  					return TranslateLoopExpr(expr, ctx);
  				}
  				else if (expr.Calls(_Gate, 1) || expr.Calls(_EqGate, 1))
  				{
  					// => foo (LES-based parser artifact)
  					return new Gate(expr, new Seq(F.Missing),
  					                      NodeToPred(expr.Args[0], Context.GateRight))
  					                      { IsEquivalency = expr.Calls(_EqGate) };
  				}
  				else if (expr.Calls(_Gate, 2) || expr.Calls(_EqGate, 2))
  				{
  					if (ctx == Context.GateLeft)
  						_sink.Error(expr, "Cannot use a gate in the left-hand side of another gate");
  
  					return new Gate(expr, NodeToPred(expr.Args[0], Context.GateLeft),
  					                      NodeToPred(expr.Args[1], Context.GateRight)) 
  					                      { IsEquivalency = expr.Calls(_EqGate) };
  				}
  				else if ((not = expr.Calls(_AndNot, 1)) || expr.Calls(_And, 1))
  				{
  					return TranslateAndPred(expr, not);
  				}
  				else if (expr.Calls(S.NotBits, 1))
  				{
  					var subpred = NodeToPred(expr.Args[0], ctx);
  					if (subpred is TerminalPred) {
  						var term = (TerminalPred)subpred;
  						term.Set = term.Set.Inverted().WithoutEOF();
  						return term;
  					} else {
  						_sink.Error(expr, 
  							"The set-inversion operator ~ can only be applied to a single terminal, not a '{0}'", subpred.GetType().Name);
  						return subpred;
  					}
  				}
  				else if ((name.Name.EndsWith(":") || name.Name.EndsWith("=")) && expr.ArgCount == 2)
  				{
  					return TranslateLabeledExpr(expr, ctx);
  				}
  				else if (expr.Calls(_any, 2) && expr.Args[0].IsId) 
  				{
  					return Translate_any_in_Expr(expr, ctx);
  				}
  				else if (expr.Calls(_recognizer, 1) || expr.Calls(_nonrecognizer, 1))
  				{
  					_ruleChangesInRecognizer = true;
  
  					var saved = _insideRecognizerSequence;
  					try {
  						_insideRecognizerSequence = expr.Calls(_recognizer, 1);
  
  						if (_insideRecognizerSequence == _parsingRecognizerVersion)
  							return NodeToPred(expr[0]);
  						else
  							return new Seq(expr.Target); // empty sequence
  
  					} finally {
  						_insideRecognizerSequence = saved;
  					}
  				}
  			}
  			
  			// expr is an Id, literal, or non-special call
  			Rule rule = TryGetRule(expr);
  			if (rule != null)
  			{
  				LNode _, args;
  				if (EcsValidators.MethodDefinitionKind(rule.Basis, out _, out _, out args, out _, false) == S.Fn) {
  					if (expr.ArgCount > args.ArgCount) // don't complain about too few args, in case there are default args (I'm too lazy to check)
  						_sink.Error(expr, "Rule '{0}' takes {1} arguments ({2} given)", rule.Name, args.ArgCount, expr.ArgCount);
  				}
  
  				return new RuleRef(expr, rule) { Params = expr.Args };
  			}
  
  			string errorMsg = null;
  			Pred terminal = _helper.CodeToTerminalPred(expr, ref errorMsg);
  			if (terminal == null) {
  
gt: 				errorMsg = errorMsg ?? "LLLPG: unrecognized expression";