/*
 * Bernoulli Compiler
 * Copyright (c) Cornell University
 * Department of Computer Science
 * 
 * Kamen Yotov (kamen@yotov.org)
 * 
 * $Source: C:/CVS/kyotov/kyotov/Research/BC/Core/Parsers/Parser.cs,v $
 * $Revision: 1.26 $
 * $Date: 2003/01/06 07:32:34 $
 */

#define X

using System;
using System.Xml;
using System.Collections;
using System.Diagnostics;

using XTensions.Collections;

namespace BC.Core
{
	using Annotations;
	using ASTs;
	using Lexers;
	using Automatas;
	using Grammars;
	using Grammars.Symbols;
	using Exceptions;

	namespace Parsers
	{
		class ClonableObject: ICloneable
		{
			public object Clone ()
			{
				return MemberwiseClone();
			}
		}

		public enum Statistics
		{
			Ambiguities,
			SyntacticallyResolved,
			SemanticallyResolved,
			CounterCount
		}

		[Serializable]
		public class Parser
		{
			protected Symbol S;
			protected FA a;
			protected bool v;
			protected Set css;
			protected Hashtable cache;
			protected int[] s = new int[(int)Statistics.CounterCount];
			
			public Parser (Symbol S, FA a, bool v)
			{
				this.S = S;
				this.a = a;
				this.v = v;

				css = new Set();
			}

			public Parser (Symbol S, FA a) :
				this(S, a, false)
			{
			}

			static bool NullCheck (object o)
			{
				return o != null;
			}

			public Set CheckSuccessSet
			{
				get
				{
					return css;
				}
			}

			public int this[Statistics x]
			{
				get
				{
					return s[(int)x];
				}
				set
				{
					s[(int)x] = value;
				}
			}

			protected void AnnotateLocation (AbstractNode n, Location l, bool f)
			{
				NodeAnnotation a = new NodeAnnotation(n);

				a["location"]["position"] = l.Position.ToString();
				a["location"]["length"] = l.Length.ToString();

				if (f)
					a["location"]["file"] = l.File;
			}

			protected void Shift (Sequence s, ref int c, ref Sequence x, Node n, int v)
			{
				s[c].Node = n;

				x.Add(s[c++]);
			}

			protected void Reduce (Sequence s, ref int c, ref Sequence x, Item m, int v)
			{
				Sequence r = x.Right(m.P.RHS.Sequence.Count);

				object o = null;

				Location l = null;

				object[] w = new object[r.Count];

				l = ((PhysicalSymbol)r[0]).Location;

				for (int i = 0; i < r.Count; i++)
				{
					w[i] = r[i].Result;
					l = l + ((PhysicalSymbol)r[i]).Location;
				}

				if (m.P.RHS.Reduction != null)
					try
					{
						o = m.P.RHS.Reduction(w);
					}
#if X
					catch (BCException e)
					{
						e.Location = l;

						throw;
					}
#else
					catch (ImpossibleException)
					{
						throw;
					}
#endif
				else
				{
					Console.WriteLine(m.P.ToString());

					throw new BCException(ExceptionType.Unpredicted, UI.Code.bc_unpredicted_001, l);
				}

				NonTerminal t = new NonTerminal(m.P.LHS.ToString(), l, o);

				if (t.Result is AbstractNode)
					AnnotateLocation((AbstractNode)t.Result, l, false);

				x.RemoveRange(x.Count - r.Count, r.Count);

				t.Node = (Node)(x.Count == 0 ? a.S : x.Last.Node)[t].Singleton;

				x.Add(t);
			}

			protected void Step (Sequence s, ref int c, ref Sequence x, object o, int v)
			{
				if (o is Node)
					Shift(s, ref c, ref x, (Node)o, v);
				else if (o is Item)
					Reduce(s, ref c, ref x, (Item)o, v);
				else
					Debug.Assert(false, "invalid step");
			}

			protected object Parse (ref ICloneable t, Sequence s, int c, Sequence x, int v, int xc)
			{
				do
				{
					Node n = x.Count == 0 ? a.S : x.Last.Node;

					ArrayList p = new ArrayList();

					bool shift = false;

					foreach (Item i in n.Items)
					{
						Sequence r = i.P.RHS.Sequence;

						if (r != null && Sequence.Match(x.Right(i.Dot), r.Left(i.Dot)))
							if (i.IsReduction)
							{
								if (i.LookAhead(new Sequence(s[c])))
									p.Add(i);
							}
							else
								shift = shift | Symbol.Match((Symbol)s[c], r[i.Dot]);
					}

					if (shift)
						foreach (Symbol q in n.Edges)
							if (Symbol.Match(s[c], q))
							{
								Node nn = (Node)n[q].Singleton;

								p.Add(nn);
							}

					if (this.v)
						Console.WriteLine("{0}{1}", new string('\t', v), x);

					Location l = ((Terminal)s[c]).Location;

					switch (p.Count)
					{
						case 0:
						{
							throw new SyntacticException(UI.Code.bc_syntactic_000, l, x);
						}
						case 1:
						{
							if (this.v)
							{
								if (p[0] is Node)
									Console.WriteLine("{0}doing {1}", new string('\t', v), "shifting");
								else
									Console.WriteLine("{0}doing {1}", new string('\t', v), ((Item)p[0]).P);
							}

							Step(s, ref c, ref x, p[0], v);
							
							if (v > 0 && (x.Count < xc || CheckSuccessSet.Contains(x.Last)))
								return null;

							break;
						}
						default:
						{
							ArrayList np = new ArrayList();
							ArrayList ne = new ArrayList();

							int ri = -1;

							if (cache[c] == null)
							{
								for (int pi = 0; pi < p.Count; pi++)
								{
									object o = p[pi];

									Sequence nx = (Sequence)x.Clone();

									int nc = c;
									ICloneable ot = (ICloneable)t.Clone();

									try
									{
										if (this.v)
										{
											if (o is Node)
												Console.WriteLine("{0}trying {1}", new string('\t', v), "shifting");
											else
												Console.WriteLine("{0}trying {1}", new string('\t', v), ((Item)o).P);
										}

										Step(s, ref nc, ref nx, o, v + 1);

										Parse(ref t, s, nc, nx, v + 1, x.Count);

										np.Add(o);

										ri = pi;
									}
									catch (BCException e)
									{
										switch (e.Type)
										{
											case ExceptionType.Syntactic:
												this[Statistics.SyntacticallyResolved]++;
												break;
											case ExceptionType.Semantic:
												this[Statistics.SemanticallyResolved]++;
												break;
										}

										if (this.v)
										{
											Console.WriteLine("{0}failed: {1}!", new string('\t', v), e.ToString());
											Console.WriteLine();
										}

										ne.Add(e);
									}
									catch (System.Exception e)
									{
										if (this.v)
										{
											Console.WriteLine("{0}unexpected exception: {1}!!!", new string('\t', v), e.GetType().ToString());
											Console.WriteLine();
										}

										ne.Add(e);
									}
									finally
									{
										this[Statistics.Ambiguities]++;
									}

									t = ot;
								}

								this[Statistics.Ambiguities]--;
							}
							else
							{
								np = new ArrayList();

								np.Add(p[ri = (int)cache[c]]);
							}


							switch (np.Count)
							{
								case 0:
								{
									if (this.v)
									{
										Console.WriteLine("{0}unable to resolve (no match)!", new string('\t', v));
										Console.WriteLine();
									}

									throw new CompositeException(UI.Code.bc_syntactic_001, l, x, ne);
								}
								case 1:
								{
									if (this.v)
									{
										if (np[0] is Node)
											Console.WriteLine("{0}resolved to {1}", new string('\t', v), "shifting");
										else
											Console.WriteLine("{0}resolved to {1}", new string('\t', v), ((Item)np[0]).P);
									}

									cache[c] = ri;

									Step(s, ref c, ref x, np[0], v);

									break;
								}
								default:
								{
									if (this.v)
									{
										Console.WriteLine("{0}unable to resolve (too many matches)!", new string('\t', v));
										Console.WriteLine();
									}

									throw new CompositeException(UI.Code.bc_syntactic_002, l, x, ne);
								}
							}

							break;
						}
					}
				} while (!(x.Count == 1 && x[0].Equals(S) && c == s.Count - 1));

				AnnotateLocation((AbstractNode)x[0].Result, ((PhysicalSymbol)x[0]).Location, true);

				return x[0].Result;
			}

			public object Parse (Sequence s, ref ICloneable o)
			{
				cache = new Hashtable();

				s.Add(new EndOfFile());

				return Parse(ref o, s, 0, new Sequence(), 0, 0);
			}

			public object Parse (Sequence s)
			{
				ICloneable o = new ClonableObject();

				return Parse(ref o, s, 0, new Sequence(), 0, 0);
			}
		}
	}
}