using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

using miew.Debugging;

namespace agree
{
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	/// <summary>
	/// 
	/// </summary>
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	public unsafe partial struct Unification
	{
#if DEBUG
		[DebuggerDisplay("{_corefs_info(),nq}")]
		public _corefs corefs;
		int id;
#else
		public Dictionary<Int64, UnifCoref> corefs;
#endif

		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		public readonly TypeMgr tm;

		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		readonly int[][] rgrgfix;

		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		public bool f_check_only;

		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		public int c_coref_hint;

		TargetTfs target;

		Unification(TypeMgr tm, int c_edge_hint, int c_coref_hint, bool f_check_only)
		{
			this.tm = tm;
			this.rgrgfix = tm.rgrgfix_autotune;
			this.f_check_only = f_check_only;
			this.c_coref_hint = c_coref_hint == -1 ? def_coref_hint : c_coref_hint;
			this.target = new TargetTfs(tm, def_edge_hint);//c_edge_hint == -1 ? 257 : c_edge_hint);   maxes ~433/2011
#if DEBUG
			this.id = next_id++;
			this.corefs = new _corefs(this.c_coref_hint | 1);
			target.corefs = corefs;
			corefs.AddTfsArgs(target);
#else
			this.corefs = null;
#endif
		}

		public static int def_coref_hint = 277;
		public static int def_edge_hint = 277;

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// UnifCoref :: runtime dynamic unification equivalence class
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		sealed public partial class UnifCoref
		{
			public UnifCoref()
			{
				this.next = this;
			}

			/// current roll-in of all unifications so far
			[DebuggerBrowsable(DebuggerBrowsableState.Never)]
			public Edge e_cur;

			/// linked loop of other UnifCoref objects of this type which have joined the equivalence class (or reference 
			/// to self if none)
			[DebuggerBrowsable(DebuggerBrowsableState.Never)]
			public UnifCoref next;

			/// indicates that this instance is in a loop for which the other fields in this structure are
			/// superseded by the designated loop master
			[DebuggerBrowsable(DebuggerBrowsableState.Never)]
			public bool f_redirect;

			/// the number of source nodes pointing to this equivalence class (valid for loop master only, and includes
			/// nodes which are still associated with non-master UnifCorefs)
			public int c_fm;

			/// opportunistic cache of some node that points to this equivalence class as a hint for when removing
			/// vacuous coreferences. If not provided, then the enclosed mark can be zero, but otherwise the field 
			/// must be correct.
			public FeatMark single_fm;
		};

		/// <summary>
		/// Merge two coreference equivalence classes. The subordinate class is joined into a linked loop which
		/// has a single designated master, rather than being removed, because we are avoiding the expense of 
		/// directly keeping track of all the edges which lead to a given class.
		/// </summary>
		public bool _merge_corefs(UnifCoref _this, UnifCoref other)
		{
			/// we do keep accurate _count_ of target edges which lead into a class, and this field is
			/// defined as being valid only for the loop master. Here, we sum counts of the joined classes.
			_this.c_fm += other.c_fm;
			other.c_fm = 0;

			/// patch the two loops together into a single loop
			UnifCoref uc = other;
			while (uc.next != other)
				uc = uc.next;
			uc.next = _this.next;
			_this.next = other;
			other.f_redirect = true;

			target.c_corefs--;

			/// do the unification
			if (!_unify(false, target, _this.e_cur, target, other.e_cur, out _this.e_cur))
				return false;
			other.e_cur = _this.e_cur;
			return true;
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// TFS unification
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		bool _unify(bool f_exp, Tfs tfs1, Edge e1, Tfs tfs2, Edge e2, out Edge e)
		{
#if DEBUG
			Debug.Assert(tfs1 != tfs2 || !e1.Equals(e2));
			TfsEdge _arg1, _arg2;
			if (Debugger.IsAttached) { _arg1 = tfs1.GetSectionTfsEdge(e1); _arg2 = tfs2.GetSectionTfsEdge(e2); }
			else { _arg1 = default(TfsEdge); _arg2 = default(TfsEdge); }
#endif

			Edge.Flag nf, f1 = e1.FlagsId, f2 = e2.FlagsId;
			if (f1 == 0 || f1 == f2)
				nf = f2;
			else if (f2 == 0)
				nf = f1;
			else if ((nf = tm.UnifyTypes(f1, f2)) == Edge.Flag.Bottom)
			{
				e = default(Edge);
				return false;
			}

			/// find the best mark to recycle if one or both of the input TFSs are within the target TFS.
			/// prefer non-bare and coreferenced edges (in that order), or the edge whose type has more 
			/// appropriate features, if there are still no deciding factors. if it's still zero after all this, 
			/// and if a mark is needed because the type is non-bare or the edge is coreferenced, generate a new 
			/// mark. then, create the new edge.

			int m, m1, m2;
			bool recyc1, recyc2 = recyc1 = false;
			bool b1 = (m1 = e1.Mark) != 0 && tfs1 == target;
			bool b2 = (m2 = e2.Mark) != 0 && tfs2 == target;
			if (b1 && (!b2 || f2 >= 0 || (f1 < 0 && f1 >= f2)))
			{
				m = m1;
				recyc1 = true;
			}
			else if (b2)
			{
				m = m2;
				recyc2 = true;
			}
			else if ((nf & (Edge.Flag.Coreference | Edge.Flag.EtmNonBareType)) != 0)
			{
				/// promote mark if required. the latter part of this condition is most certainly the case, since 
				/// we now resolve simple unifications inside the feature body, but it is included for correctness 
				/// when unifying TFSes which are coreferenced or bare at their root.
				m = target.next_mark++;
			}
			else
				m = 0;

			e = new Edge(nf, m);
			if ((nf & Edge.Flag.EtmNonBareType) == 0)
				return true;

			/// done with source marks which were needed only by coreferencing, so clear marks for bare types to signal 
			/// that we don't need to attempt to fetch the corresponding onwards edges
			if (m1 != 0 && (f1 & Edge.Flag.EtmNonBareType) == 0)
				m1 = 0;
			if (m2 != 0 && (f2 & Edge.Flag.EtmNonBareType) == 0)
				m2 = 0;

			/// initialize edges for one of the sides if it won't be fetched
			if (m1 == 0)
				e1 = default(Edge);
			else if (m2 == 0)
				e2 = default(Edge);

#if DEBUG
			TfsEdgeSpy _cur1, _cur2;
			if (Debugger.IsAttached)
			{
				_cur1 = new TfsEdgeSpy(tfs1, &e1);
				_cur2 = new TfsEdgeSpy(tfs2, &e2);
			}
#endif
			// (??) if both in target and same mark, zero one of the marks...

			b1 = b2 = false;
			foreach (int i_feat in rgrgfix[(int)(nf & Edge.Flag.MultiIdMask)])
			{
				if (m1 != 0)
					b1 = tfs1.TryGetEdge(i_feat, m1, out e1);	// see ArrayTfs; *top* is actually stored for topmost node (only)
				if (m2 != 0)
					b2 = tfs2.TryGetEdge(i_feat, m2, out e2);

				int nm1, nm2;
				if (!b1)
				{
					if (recyc2 || !b2)
						continue;
					f1 = 0; nm1 = 0;
					f2 = e2.FlagsId; nm2 = e2.Mark;
				}
				else
				{
					if (b2)
					{
						f2 = e2.FlagsId; nm2 = e2.Mark;
					}
					else
					{
						if (recyc1)
							continue;
						f2 = 0; nm2 = 0;
					}
					f1 = e1.FlagsId; nm1 = e1.Mark;
				}

				Edge ne;
				UnifCoref uc = null;

				/// some optimizations are possible if the discovered edges are identical in the target, or bare.
				if (nm1 == nm2 && (nm1 == 0 || (f1 == f2 && tfs1 == tfs2 && tfs1 == target)))
				{
					if (nm1 == 0)
					{
						if (f1 == 0 || f1 == f2)
							nf = f2;
						else if (f2 == 0)
							nf = f1;
						else if ((nf = tm.UnifyTypes(f1, f2)) == Edge.Flag.Bottom)
							goto record_failed_feat;
						ne = new Edge(nf, 0);
					}
					else if (f1 < 0)
					{
						Debug.Assert(recyc1 || recyc2);
						corefs.TryGetValue(((long)target.id << 32) | (uint)nm1, out uc);
						while (uc.f_redirect)
							uc = uc.next;
						ne = uc.e_cur;
					}
					else
						ne = e1;
				}
				else if (f1 >= 0 && f2 >= 0)
				{
					if (!_unify(f_exp, tfs1, e1, tfs2, e2, out ne))
						goto record_failed_feat;
				}
				else
				{
					/// when at least one of the two edges is coreferenced, it is always possible to resolve the coreference with no
					/// more than one binary unification operation. that is, you'd never have to, say, unify both inputs with an
					/// existing equivalence class in two separate operations. see the five cases below.
					UnifCoref ud = null;
					if (corefs == null ||
						((f1 < 0 && corefs.TryGetValue(((long)tfs1.id << 32) | (uint)nm1, out uc)) ==
						 (f2 < 0 && corefs.TryGetValue(((long)tfs2.id << 32) | (uint)nm2, out ud)) &&
							uc == null))
					{
#if !DEBUG
						if (corefs == null)
							corefs = c_coref_hint == -1 ? new Dictionary<Int64, UnifCoref>() : new Dictionary<Int64, UnifCoref>(c_coref_hint | 1);
						target.corefs = corefs;
#endif
						uc = new UnifCoref();
						if (f1 < 0)
							corefs.Add(((long)tfs1.id << 32) | (uint)nm1, uc);
						if (f2 < 0)
							corefs.Add(((long)tfs2.id << 32) | (uint)nm2, uc);

						if (!_unify(f_exp, tfs1, e1, tfs2, e2, out uc.e_cur))
							goto record_failed_feat;

						corefs.Add(((long)target.id << 32) | (uint)uc.e_cur.Mark, uc);
						target.c_corefs++;
					}
					else if (ud == null)
					{
						while (uc.f_redirect)
							uc = uc.next;
						if (f2 < 0)
							corefs.Add(((long)tfs2.id << 32) | (uint)nm2, uc);
						if (!_unify(f_exp, target, uc.e_cur, tfs2, e2, out uc.e_cur))
							goto record_failed_feat;
					}
					else if (uc == null)
					{
						while (ud.f_redirect)
							ud = ud.next;
						if (f1 < 0)
							corefs.Add(((long)tfs1.id << 32) | (uint)nm1, ud);
						if (!_unify(f_exp, tfs1, e1, target, ud.e_cur, out ud.e_cur))
							goto record_failed_feat;
						uc = ud;
					}
					else
					{
						while (uc.f_redirect)
							uc = uc.next;
						while (ud.f_redirect)
							ud = ud.next;
						if (uc != ud && !_merge_corefs(uc, ud))
							goto record_failed_feat;
					}

					if (!f_check_only && (f1 >= 0 || !recyc1) && (f2 >= 0 || !recyc2))
					{
						uc.c_fm++;
						uc.single_fm = new FeatMark(i_feat, m);
					}
					ne = uc.e_cur;
				}

				/// If the result is not one of the input types and it has features (or if we are expanding the type hierarchy),
				/// unify with the constraints on the canonical expanded type
				if (((nf = ne.FlagsId) & Edge.Flag.EtmNonBareType) != 0)
				{
					int ntid = (int)(nf & Edge.Flag.MultiIdMask);
					if (f_exp || ((int)(f1 & Edge.Flag.MultiIdMask) != ntid && (int)(f2 & Edge.Flag.MultiIdMask) != ntid))
					{
						/// the following can change the edge (?)
						Tfs tfsx = tm.type_arr[ntid].Expanded.Clone();
#if DEBUG
						corefs.AddTfsArgs(tfsx);
#endif
						if (!_unify(false, target, ne, tfsx, tfsx.Edge, out ne))
							goto record_failed_feat;
					}
				}

				/// persist the new edge.
				Debug.Assert(nf != 0);
				if ((!recyc1 || ne.Mark != nm1 || nf != f1) && (!recyc2 || ne.Mark != nm2 || nf != f2))
				{
					if ((recyc1 && b1) || (recyc2 && b2))
					{
						Debug.Assert(target.ContainsFeatMark(i_feat, m));
						target.SetEdge(i_feat, m, ne);
					}
					else
						target.AddEdge(i_feat, m, ne);
				}

				/// if destructive in the target, remove the edge that wasn't retained
				if (recyc1)
				{
					if (b2 && tfs2 == target)
					{
						if (!f_check_only && f2 < 0)
						{
							if (uc == null)
							{
								corefs.TryGetValue(((long)tfs2.id << 32) | (uint)nm2, out uc);
								while (uc.f_redirect)
									uc = uc.next;
							}
							uc.c_fm--;
						}
						if (!target.RemoveEdge(i_feat, m2))
							Debug.Assert(false);
					}
				}
				else if (recyc2)
				{
					if (b1 && tfs1 == target)
					{
						if (!f_check_only && f1 < 0)
						{
							if (uc == null)
							{
								corefs.TryGetValue(((long)tfs1.id << 32) | (uint)nm1, out uc);
								while (uc.f_redirect)
									uc = uc.next;
							}
							uc.c_fm--;
						}
						if (!target.RemoveEdge(i_feat, m1))
							Debug.Assert(false);
					}
				}
				continue;

			record_failed_feat:
				/// not concerned about volatile writing here; just looking for approximate numbers so its
				/// not worth invalidating the CPU caches.
				tm.feat_arr[i_feat].c_failures++;
				return false;
			}
			return true;
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		///
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		TargetTfs _expand_type(Type host_type)
		{
			Debug.Assert((host_type.m_flags & Type.Flags.HasAnyFeatures) != 0);

			IEnumerator<Type> iea = host_type.Parents.Where(p => p.HasAnyFeatures).GetEnumerator();
			Tfs tfs1 = host_type.Definition;
			Tfs tfs2 = !iea.MoveNext() ? tm.TopTfs : iea.Current.Expanded;
#if DEBUG
			corefs.AddTfsArgs(tfs1, tfs2);
#endif

			while (true)
			{
				if (!_unify(true, tfs1, tfs1.Edge, tfs2, tfs2.Edge, out target.Edge))
					return null;

				if (tfs1 != target)
					tfs1 = target;

				if (!iea.MoveNext())
					break;

				tfs2 = iea.Current.Expanded;
#if DEBUG
				corefs.AddTfsArgs(tfs2);
#endif
			}
			return target;
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		struct Partial
		{
			public Partial(TypeMgr tm, TfsSection daughter, Tfs candidate)
			{
				this.mother = daughter.mother;
				this.e_daughter_mark = daughter.Edge.Mark;
				this.e_partial = default(Edge);

				Debug.Assert(mother.Edge.Mark != 0);
				int c_edge_hint = daughter.mother.EdgeCount + candidate.EdgeCount;
#if false
				if (mother.c_corefs == -1 || candidate.c_corefs == -1)
					throw new NotImplementedException();

				int c_coref_hint = mother.c_corefs;
				if (candidate.c_corefs > c_coref_hint)
					c_coref_hint = candidate.c_corefs;
				c_coref_hint *= 4;
				u = new Unification(tm, c_edge_hint, c_coref_hint, false);
#else
				u = new Unification(tm, c_edge_hint, -1, false);
#endif
			}

			public Unification u;
			public int e_daughter_mark;
			public Edge e_partial;
			public Tfs mother;

			///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
			/// <summary>
			///
			/// </summary>
			///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
			internal MotherDaughterTfs _unify_section(TfsSection daughter, Tfs candidate, int[] rg_feat_delete)
			{
#if DEBUG
				u.corefs.AddTfsArgs(mother, candidate);
#endif
				if (!u._unify(false, mother, daughter.Edge, candidate, candidate.Edge, out e_partial))
					return null;

				Debug.Assert(u.corefs != null);

				u.target.Edge = new Edge(mother.Edge.FlagsId, u.target.next_mark++);
				_copy_remainder(mother.Edge, u.target.Edge.Mark);

				return u.target.ToMotherDaughterTfs(rg_feat_delete);
			}

			///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
			/// <summary>
			/// 
			/// </summary>
			///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
			void _copy_remainder(Edge e, int m_dst)
			{
				int m = e.Mark;
#if DEBUG
				Edge e_original;
				if (Debugger.IsAttached) e_original = e;
#endif
				foreach (int i_feat in u.rgrgfix[(int)(e.FlagsId & Edge.Flag.MultiIdMask)])
				{
					if (mother.TryGetEdge(i_feat, m, out e))
					{
						int m_src = e.Mark;
						if (e.FlagsId < 0)
						{
							UnifCoref uc;
							long mother_key = ((long)mother.id << 32) | (uint)m_src;
							if (u.corefs.TryGetValue(mother_key, out uc))
							{
								while (uc.f_redirect)
									uc = uc.next;
								e = uc.e_cur;
							}
							else
							{
								if (m_src == e_daughter_mark)
									e = e_partial;
								else
								{
									if (m_src != 0)
										m_src = u.target.next_mark++;
									_copy_remainder(e, m_src);
									e = new Edge(e.FlagsId, m_src);
								}
								uc = new UnifCoref();
								u.target.c_corefs++;

								uc.e_cur = e;

								u.corefs.Add(mother_key, uc);
								u.corefs.Add(((long)u.target.id << 32) | (uint)uc.e_cur.Mark, uc);
							}
							uc.c_fm++;
							uc.single_fm = new FeatMark(i_feat, m_dst);
						}
						else if (m_src == e_daughter_mark)
							e = e_partial;
						else if (m_src != 0)
						{
							m_src = u.target.next_mark++;
							_copy_remainder(e, m_src);
							e = new Edge(e.FlagsId, m_src);
						}

						u.target.AddEdge(i_feat, m_dst, e);
					}
				}
			}
		}

		public static TargetTfs UnifyForceExpand(Tfs tfs1, Tfs tfs2)
		{
			Unification u = new Unification(tfs1.tm, -1, -1, false);
#if DEBUG
			u.corefs.AddTfsArgs(tfs1, tfs2);
#endif
			return u._unify(true, tfs1, tfs1.Edge, tfs2, tfs2.Edge, out u.target.Edge) ? u.target : null;
		}

		public static TargetTfs ExpandType(Type host_type)
		{
			Unification u = new Unification(host_type.tm, -1, -1, false);
			return u._expand_type(host_type);
		}

		public static MotherDaughterTfs UnifySection(
						TfsSection daughter,
						Tfs candidate,
						bool f_pruning,
						bool f_pack_restrict,
						ParseControl ctrl)
		{
			TypeMgr tm = daughter.tm;
			Partial up = new Partial(tm, daughter, candidate);
			return up._unify_section(daughter, candidate, f_pruning ? ctrl.parser_config.DeletedDaughters : null);
		}

		public static Boolean Check(Tfs tfs1, Tfs tfs2)
		{
			Debug.Assert(tfs1 != tfs2);
			Edge e;

			Unification u = new Unification(tfs1.tm, tfs1.EdgeCount + tfs2.EdgeCount, -1, true);
#if DEBUG
			u.corefs.AddTfsArgs(tfs1, tfs2);
#endif
			return u._unify(false, tfs1, tfs1.Edge, tfs2, tfs2.Edge, out e);
		}
	};
}