#define EXHAUSTIVE_POOL_SEARCH
using System;
using System.Diagnostics;
using System.Text;
using System.IO;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Threading;

using glue.Extensions.Enumerable;
using glue.Debugging;

namespace agree
{
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	/// <summary>
	/// To abort processing at any point and send up a TFS for examination
	/// </summary>
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	public class DebuggingTfsDisplayException : Exception
	{
		TfsEdge[] rgtfs;

		public DebuggingTfsDisplayException(TfsEdge tfs)
			: base(String.Format("Debugging exception for TFS {0}", tfs.ToString()))
		{
			this.rgtfs = new TfsEdge[] { tfs };
		}

		public DebuggingTfsDisplayException(Tray tr, Edge e)
			: this(tr.CreateTfs(e))
		{
		}

		public DebuggingTfsDisplayException(params TfsEdge[] rgtfs)
		{
			this.rgtfs = rgtfs;
		}

		public TfsEdge[] Tfs { get { return rgtfs; } }
	}

	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	/// <summary>
	/// To abort processing at any point and send up a TFS for examination
	/// </summary>
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	public class DebuggingTfsDisplayExceptionWithHighlighting : DebuggingTfsDisplayException
	{
		TfsEdge tfsHighlight;

		public DebuggingTfsDisplayExceptionWithHighlighting(TfsEdge tfs, TfsEdge highlight)
			: base(tfs)
		{
			this.tfsHighlight = highlight;
		}

		public TfsEdge TfsHighlight { get { return tfsHighlight; } }
	}


#if DEBUG
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	///
	/// debug: E D G E 
	///
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	[DebuggerDisplay("{ToString(),nq}")]
	public partial struct Edge : IEquatable<Edge>
	{
		public override String ToString()
		{
			String s = FormatMark(this) + " " + _FlagsReport(FlagsId, false) + " ";
			if (Debugger.IsAttached || Nop.IsGuiApplication)
				return s;
			return s.Replace("⇌", "%").Replace("⊣", ".").Replace("☐", "_").Replace("☒", "X").Replace("⒮", "(s)");
		}

		public Type _Type { get { return TrayMgr._most_recent_tray.tm.GetEdgeType(FlagsId); } }

		[DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
		[DebuggerHidden]
		public ConstraintRef[] _FEATURES
		{
			get { return TrayMgr._most_recent_tray.AllConstraintRefs(this).ToArray(); }
		}

		static public String _FlagsReport(Flag f_in, bool f_coref)
		{
			Tray tr = TrayMgr._most_recent_tray;
			TypeMgr tm = tr.tm;
			String s = "";

			if (f_coref && (f_in & Flag.Coreference) == Flag.Coreference)
				s += "⇌ ";
			if ((f_in & Flag.PrunedDuringParsing) == Flag.PrunedDuringParsing)
				s += "✗ ";

			Flag etm = f_in & Flag.EtmMask;
			if (etm == Flag.EtmString)
			{
				s += "⒮ ";
				String sv = tm.GetStringValue(f_in);
				if (sv != null)
					s += String.Format("\"{0}\" ", sv);
			}
			else
			{
				int id = (int)(f_in & tm.MultiIdMask);
				if (id == 0)
					s += "(*top*) ";
				else
				{
					//s += "id " + id.ToString() + " ";
					s += "(" + tm.type_arr[id].Name + ") ";
				}

				if (etm == Flag.EtmNonBareType)
					s += "… ";
				else if (etm == Flag.EtmConfigMapped)
					s += "✦ ";
				else
					s += "⊣ ";
			}
			return s;
		}

		public static String FormatMark(Edge e)
		{
			if (e.IsCoreferenced)
				return "⇌" + e.Mark.ToString();
			if (e.Mark > Edge.MarkBare)
				return "@" + e.Mark.ToString();
			if ((e.FlagsId & Edge.Flag.EtmNonBareType) != 0)
				return "☒";
			return "☐";
		}
	};


	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	///
	/// debug: T f s E d g e
	///
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	[DebuggerDisplay("{ToString(),nq}")]
	public partial struct TfsEdge : IEquatable<TfsEdge>, ParseChart.IMotherDaughter
	{
		public bool GetEdgeAtPath(FsPath p, out Edge e)
		{
			return TrayMgr.all_trays[ttid & 0x3F].GetEdgeAtPath(Edge, p, out e);
		}

		public Edge GetEdgeAtPath(String p)
		{
			Edge e;
			GetEdgeAtPath(new FsPath(p), out e);
			return e;
		}

		public Type GetTypeAtPath(String p)
		{
			Edge e = GetEdgeAtPath(p);
			return Tray.tm.GetEdgeType(e.FlagsId);
		}

		[DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
		[DebuggerHidden]
		public ConstraintRef[] _BELOW
		{
			get
			{
				return Edge._FEATURES;
			}
		}

#if false
		[DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
		[DebuggerHidden]
		public Tfs.CorefTarget[] CorefCounts
		{
			get
			{
				TfsEdge _this = this;	// for lambda
				return GetCorefCounts().Select(ec => new Tfs.CorefTarget(_this, ec.edge, ec.count)).ToArray();
			}
		}
#endif

		//[DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
		//public IEnumerable<Tfs.CorefTarget> CorefCounts
		//{
		//    get
		//    {
		//        int _ttid = ttid;	// for lambda
		//        return GetCorefCounts().Select(ec => new Tfs.CorefTarget(_ttid, ec.edge, ec.count));
		//    }
		//}
	};

	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	/// <summary>
	/// 
	/// </summary>
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	[DebuggerDisplay("{ToString(),nq}")]
	public partial struct EdgeCount
	{
		public override string ToString()
		{
			return String.Format("{0} count: {1}", edge, count);
		}
	};

	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	///
	/// debug: T F S
	///
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	[DebuggerDisplay("{ToString(),nq}")]
	public partial class Tfs
	{
		public override string ToString()
		{
			return String.Format("{0}, {1} corefs", te, corefs.Length);
		}


		[DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
		[DebuggerHidden]
		public CorefTarget[] _corefs
		{
			get
			{
				TfsEdge _this_te = this.te;
				return corefs.Select(c => new CorefTarget(_this_te, c.edge, c.count)).ToArray();
			}
		}

		[DebuggerDisplay("{ToString(),nq}")]
		public struct CorefTarget
		{
			public CorefTarget(TfsEdge tfs, Edge e, int count)
			{
				this.te = tfs;
				this.count = count;
				this.paths = te.Tray.Roots
									.PathInfoStrings(e.Mark, true)
									.Select(tfsp => new FsPathInstance(tfs, tfsp.fsp))
									.ToArray();
			}
			[DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
			public FsPathInstance[] paths;

			[DebuggerBrowsable(DebuggerBrowsableState.Never)]
			public TfsEdge te;

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

			public override string ToString()
			{
				Edge e;
				paths[0].fsp.GetEdge(te, out e);
				return String.Format("   ↳ {0}: {1} in-edges, {2} paths", e, count, paths.Length);
			}
		};


		[DebuggerDisplay("{ToString(),nq}")]
		public sealed class FsPathInstance
		{
			[DebuggerBrowsable(DebuggerBrowsableState.Never)]
			public readonly TfsEdge te_tfs;

			[DebuggerBrowsable(DebuggerBrowsableState.Never)]
			public readonly TrayCompiledFsPath fsp;

			[DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
			public PoolEdge[] _debug_display
			{
				get
				{
					return fsp
						.EnumeratePoolEdges(te_tfs.Edge.Mark)
						.ToArray();
				}
			}

			public FsPathInstance(TfsEdge tfs, IEnumerable<String> rgs)
			{
				this.te_tfs = tfs;
				this.fsp = new TrayCompiledFsPath(tfs.Tray, rgs);
			}

			public override String ToString()
			{
				Edge e;
				fsp.GetEdge(te_tfs, out e);
				return "      ↳ " + fsp.ToString().ToUpper() + ": " + e.ToString();
			}
		};

	};


	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	///
	/// debug: P O O L   M A R K
	///
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	[DebuggerDisplay("{ToString(),nq}")]
	public partial struct PoolMark : IEquatable<PoolMark>, IComparable<PoolMark>
	{
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// Warning: This is probably not what you want. We don't do an expensive and exhaustive search for the actual edge 
		/// that led to this PoolMark (there are other debugging functions for that, see PathInfo()) so we use the pool/feature's 
		/// maximal type to create the host. Also missing will be the coreference bit and I'm not sure what would happen with 
		/// a string type.
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public ConstraintRef _ConstraintRef
		{
			get
			{
				Edge.Flag f = (Edge.Flag)Pool.tm.GetMaximalTypeForFeature(Pool.i_feat).m_id;
				return new ConstraintRef(new Edge(f, in_mark), Pool);
			}
		}


#if true || !EXHAUSTIVE_POOL_SEARCH
		public override String ToString()
		{
			if (Pool == null)
				return "default(PoolMark)";
			return String.Format("({0}-{1})→{2}", Feature.ToUpper(), in_mark, Constraint);
		}
#else
		public override String ToString()
		{
			if (Pool is UnknownPoolClass)
				return " (no feat.)";

			String s = String.Empty;
			switch (GarbageType())
			{
				case 0:
					s += "Ⓧ";
					break;
				case 1:
					s += "ⓓ";
					break;
				case 2:
					s += "ⓔ";
					break;
				case 3:
					s += "ⓤ";
					break;

			}
			s += String.Format("({0}-{1})→{2}", Feature.ToUpper(), in_mark, Constraint);
			if (ConstraintType.IsAtomic)
				s += "•";
			return s;
		}

		PoolMark[] ReachableFrom { get { return _ReachableFrom().ToArray(); } }
		IEnumerable<PoolMark> _ReachableFrom()
		{
			foreach (ConstraintPool pool in this.Pool.tr.Pools)
			{
				foreach (var kvp_src_out in pool.PoolEdges)
				{
					if (kvp_src_out.Value.Mark == this.in_mark /*&& this.cp.AppropriateFor.Contains(kvp_src_out.Value.Type)*/)
						yield return new PoolMark(pool, kvp_src_out.Key);
				}
			}
		}

		int GarbageType()
		{
			if (_ReachableFrom().Any())
				return 4;

			foreach (Type t in Pool.tm.feat_arr[Pool.FeatureIndex].AppropriateFor)
			{
#if TOP_MARKS
				if (UnifyHelper.top_marks.Contains(this.in_mark))
					return 3;
#endif
				if (t.m_flags.HasFlag(Type.Flags.LoadedDefinition) && t.Definition.Mark == this.in_mark)
					return 1;
				if (t.m_flags.HasFlag(Type.Flags.Expanded) && t.Expanded.Mark == this.in_mark)
					return 2;
			}
			return 0;
		}
#endif
	};

	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	///
	/// debug: C O N S T R A I N T   R E F
	///
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	[DebuggerDisplay("{ToString(),nq}")]
	public partial struct ConstraintRef : IEquatable<ConstraintRef>
	{
		public override String ToString()
		{
			String s = Host.ToString();
			if (Pool is UnknownPoolClass)
				s += " (no feat.)";
			else
			{
				s += String.Format("{0} → {1}", Feature.ToUpper(), Constraint);
				if (ConstraintType.IsAtomic)
					s += "•";
			}
			return s;
		}

		[DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
		public ConstraintRef[] _NextConstraint
		{
			get { return TrayMgr._most_recent_tray.AllConstraintRefs(this.Constraint).ToArray(); }
		}
	};

	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	///
	/// debug: G L B   D A G 
	///
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	//[DebuggerDisplay("{m_level} {m_name,nq} {_OnesPositions(),nq}")]
	public abstract partial class GlbDag : Instance
	{
		/// Return a string that lists the integers corresponding to the 'set' bit positions in m_code
		String _OnesPositions()
		{
			int[] rg = m_code.OnesPositions().ToArray();
			if (rg.Length == mgr.code_dict.Count)
				return "[all]";
			return rg.StringJoin(" ");
		}

		Type GreatestLowerBound(Type other)
		{
			if (this.IsLeaf && other.IsLeaf)
				return null;
			HashSet<Type> cln = CommonLowerNodes(other);
			if (cln.Count == 0)
				return null;
			if (cln.Count == 1)
				return cln.First();
			if (cln.Contains(this))
				return this as Type;
			if (cln.Contains(other))
				return other;
			throw new Exception();
		}

		public HashSet<Type> CommonLowerNodes(Type other)
		{
			HashSet<Type> h = AllDescendantsInclusive;
			h.IntersectWith(other.AllDescendantsInclusive);
			return h;
		}

		/// only returns error cases
		public HashSet<Type> GlbCheck(Type other, Type root)
		{
			if (this as Type == other)
				return null;
			if (this.IsLeaf || other.IsLeaf)	// one might be GLB, but there surely won't be a problem
				return null;
			if (this as Type == root || other == root)
				return null;

			HashSet<Type> cln = CommonLowerNodes(other);
			if (cln.Count <= 1 || cln.Contains(this as Type) || cln.Contains(other))
				return null;
			// get rid of deeper extras
			HashSet<Type> h = new HashSet<Type>();
			foreach (Type t in cln)
				h.UnionWith(t.AllDescendants);
			cln.RemoveWhere(e => h.Contains(e));
			if (cln.Count == 0)
				throw new Exception();
			// that might have done the trick
			if (cln.Count == 1)
				return null;
			return cln;
		}
	};

	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	///
	/// debug: T Y P E 
	///
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	[DebuggerDisplay("{Name,nq} {m_id} ({_feature_info(),nq})")]
	public partial class Type : GlbDag
	{
		public TypeMgr.FeatureInfo[] _dbg_features()
		{
			return fc.Select(i_feat => mgr.feat_arr[i_feat]).ToArray();
		}

		[DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
		public ConstraintPool._DbgConstraintPool[] _FEATURES
		{
			get
			{
				if ((m_flags & Flags.LoadedNonLocalFeatures) == 0)
					return new ConstraintPool._DbgConstraintPool[0];
				return _dbg_features().Select(fi => new ConstraintPool._DbgConstraintPool(fi, this)).ToArray();
			}
		}

		String _feature_info()
		{
			int local = 0, total = 0;
			foreach (TypeMgr.FeatureInfo fi in _dbg_features())
			{
				if (fi.maximal_type == this)
					local++;
				total++;
			}
			return String.Format("{0} features: {1} local, {2} inherited.", total, local, total - local);
		}
	};


	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	///
	/// debug: T Y P E   M A N A G E R
	///
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	public partial class TypeMgr
	{
		[DebuggerDisplay("#{i_feat} {feature.ToUpper()} ({maximal_type.Name})")]
		public partial struct FeatureInfo
		{
		};

		public int GlbCount { get { return next_glb_num; } }

		public Instance FindExpanded(TfsEdge e)
		{
			return AllInstances.FirstOrDefault(_e => (_e.m_flags & Type.Flags.Expanded) > 0 && _e.Expanded.Equals(e));
		}

		public Instance FindDefinition(TfsEdge e)
		{
			return AllInstances.FirstOrDefault(_e => _e.Definition.Equals(e));
		}

		public String FindInfo(TfsEdge e)
		{
			foreach (Instance inst in AllInstances)
			{
				if (inst.Definition.Equals(e))
					return "definition: " + inst.Name;
				if ((inst.m_flags & Type.Flags.Expanded) > 0 && inst.Expanded.Equals(e))
					return "expanded: " + inst.Name;
			}
			return "unknown";
		}
	};

	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	///
	/// debug: T R A Y
	///
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	abstract public partial class Tray
	{
#if EXHAUSTIVE_POOL_SEARCH
		public IEnumerable<PoolMark> TreeLeaves(IEnumerable<PoolMark> set)
		{
			return set.Where(pm =>
				{
					Edge e = pm.Constraint;
					if (e.Mark == Edge.MarkBare)
						return true;
					if (e.IsCoreferenced && !_PoolMarksFromInMark(e.Mark).Any())
						return true;
					return false;
				});
		}
#endif
		public IEnumerable<String> _ConstraintPaths(Edge e, String f)
		{
			bool f_any = false;
			foreach (var cp in ConstrainedPoolsOnly(e))
			{
				foreach (var z in _ConstraintPaths(cp.GetEdge(e.Mark), (f != String.Empty ? f + "." : "") + cp.Feature.ToUpper()))
				{
					yield return z;
					f_any = true;
				}
			}
			if (!f_any)
				yield return f + " " + tm.GetEdgeType(e.FlagsId).Name;
		}

		/// used by TfsEdge debug code
		public bool GetEdgeAtPath(Edge e_start, FsPath p, out Edge e)
		{
			e = e_start;
			foreach (String f in p)
			{
				int i_feat = tm.GetFeatureIndex(f);
				if (i_feat == -1 || !Pools[i_feat].TryGetEdge(e.Mark, out e))
					return false;
			}
			return true;
		}

		public void CheckOrphanedEdges(TextWriter tw, HashSet<PoolMark> reachable)
		{
			HashSet<PoolMark> pool_pms = new HashSet<PoolMark>(Pools.SelectMany(cp => cp.Marks.Select(m => new PoolMark(cp, m))));

			//var y = pool_pms.OrderBy(x => x).ToArray();
			//var z = reachable.OrderBy(x => x).ToArray();

#if BAREMARKS
			HashSet<PoolMark> bad_mark = new HashSet<PoolMark>(pool_pms.Where(pm =>
				{
					Edge e = pm.Constraint;
					if (e.AnyConstraints || e.IsCoreferenced)
						return false;
					return e.Mark != 0;
				}));
#endif

			HashSet<PoolMark> garbage = new HashSet<PoolMark>(pool_pms.Except(reachable));

			HashSet<PoolMark> non_bare_garbage = new HashSet<PoolMark>(garbage.Where(pm => pm.Constraint.Mark != Edge.MarkBare));

			HashSet<PoolMark> bare_garbage = new HashSet<PoolMark>(garbage.Where(pm => pm.Constraint.Mark == Edge.MarkBare));

			//HashSet<PoolMark> garbage_trees = new HashSet<PoolMark>(garbage.Except(garbage.SelectMany(pm => pm.Constraint.ConstrainedPoolMarksOnly(this))));
			HashSet<Edge> garbage_trees = TreeTops(garbage).ToHashSet();

			//int garbage_parents = 0;
			//			foreach (Edge ge in garbage)
			//		{
			//		if (ge.Any(ge_child => reachable.Contains(ge_child)))
			//		garbage_parents++;
			//			}

			tw.WriteLine("PoolMark Report:");
			//tw.WriteLine("        in pools: {0,6}\n       reachable: {1,6}\nmark should be 0: {2,6}\n         garbage: {3,6}\n    bare garbage: {4,6}\nnon-bare garbage: {5,6}",
			tw.WriteLine("        in pools: {0,7}\n       reachable: {1,7}\n         garbage: {2,7}\n    bare garbage: {3,7}\nnon-bare garbage: {4,7}\n   garbage trees: {5,7}",
					pool_pms.Count,
					reachable.Count,
				//bad_mark.Count,
					garbage.Count,
					bare_garbage.Count,
					non_bare_garbage.Count,
					garbage_trees.Count);

			int take_gt = int.MaxValue;
			if (garbage_trees.Count > 0)
			{
				tw.WriteLine();
				tw.Write("Garbage Trees");
				if (garbage_trees.Count > take_gt)
					tw.Write(" (first {0} of {1} shown)", take_gt, garbage_trees.Count);
				tw.WriteLine();
				tw.WriteLine("===============================");
				foreach (Edge gedge in garbage_trees.Take(take_gt))
				{
					tw.WriteLine("\"{0}\"? @{1}", tm.GetEdgeType(gedge.FlagsId).Name, gedge.Mark);
					foreach (String pth in new PathLister(this, gedge, null, true, null))//reachable))
						tw.WriteLine("\t{0}", pth);
				}
				tw.WriteLine("===============================");
			}

			int take_g = 100;
			if (garbage.Count > 0)
			{
				tw.WriteLine();
				tw.Write("Garbage PoolMarks:");
				if (garbage.Count > take_g)
					tw.Write(" (first {0} of {1} shown)", take_g, garbage.Count);
				tw.WriteLine();
				tw.WriteLine("===============================");
				foreach (PoolMark gpm in garbage.Take(take_g))
					tw.WriteLine(gpm.ToString());
				tw.WriteLine("===============================");
			}
		}

#if EXHAUSTIVE_POOL_SEARCH
		public PoolMark[] PoolMarksFromOutMark(int m_out)
		{
			return _PoolMarksFromOutMark(m_out).ToArray();
		}

		IEnumerable<PoolMark> _PoolMarksFromOutMark(int m_out)
		{
			foreach (ConstraintPool cp in Pools)
				foreach (var pe in cp.PoolEdges)
					if (pe.Value.Mark == m_out)
						yield return new PoolMark(cp, pe.Key);
		}
		IEnumerable<ConstraintPool> _PoolsFromOutMark(int m_out)
		{
			return Pools.Where(cp => cp.PoolEdges.Any(pe => pe.Value.Mark == m_out));
		}
#endif

		public PoolMark[] PoolMarksFromInMark(int m_in)
		{
			return _PoolMarksFromInMark(m_in).ToArray();
		}

		IEnumerable<PoolMark> _PoolMarksFromInMark(int m_in)
		{
			return Pools.Where(p => p.ContainsInMark(m_in)).Select(cp => new PoolMark(cp, m_in));
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// debugging use only
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public int FindTop(int mark)
		{
			int top_mark = mark;
		restart:
			foreach (var pe in Pools.SelectMany(cp => cp.PoolEdges))
			{
				if (pe.Value.Mark == top_mark)
				{
					top_mark = pe.Key;
					goto restart;
				}
			}
			return top_mark;
		}

		public Edge SynthesizeTopEdge(int mark)
		{
			var rgcp = _PoolsFromOutMark(mark).ToArray();
			if (rgcp.Length == 0)
				return default(Edge);
			Type t = rgcp.Select(cp => cp.IntroducedBy).ArgMax(tt => tt.m_level);
			return CreateRecycledEdge(t, mark, false);
		}
		public Edge SynthesizeTopEdge(Edge edge)
		{
			return SynthesizeTopEdge(FindTop(edge.Mark));
		}

		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		RootAnalysis ra = null;
		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		public RootAnalysis Roots
		{
			get { return ra = ra ?? new RootAnalysis(this); }
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public class RootAnalysis
		{
			Tray tr;
			Dictionary<int, RootEdgeData> roots = new Dictionary<int, RootEdgeData>();

			public RootAnalysis(Tray tr)
			{
				this.tr = tr;
				foreach (Instance t in tr.tm.AllInstances)
				{
					int mx_d;
					mx_d = t.Definition.Edge.Mark;
					if (mx_d != 0)
					{
						int mx_e = 0;
						if ((t.m_flags & Type.Flags.Expanded) > 0)
						{
							if ((mx_e = t.Expanded.Edge.Mark) != 0 && mx_e != mx_d)
								roots.Add(mx_e, new RootEdgeData(t, RootEdgeType.Expanded, mx_e));
						}
						if (mx_d == mx_e)
							roots.Add(mx_d, new RootEdgeData(t, RootEdgeType.ExpandedDefinition, mx_d));
						else
							roots.Add(mx_d, new RootEdgeData(t, RootEdgeType.Definition, mx_d));
					}
				}
			}

			[Flags]
			public enum RootEdgeType
			{
				Unknown = 0,
				Definition = 1,
				Expanded = 2,
				ExpandedDefinition = 3,
				CycleDetected = 4,
			};

			[DebuggerDisplay("{ToString(),nq}")]
			public struct RootEdgeData
			{
				public RootEdgeData(Instance t, RootEdgeType ret, int mark)
				{
					this.t = t;
					this.ret = ret;
					this.mark = mark;
				}
				public Instance t;
				public RootEdgeType ret;
				public int mark;
				public override String ToString()
				{
					if (ret == RootEdgeType.Unknown || ret == RootEdgeType.CycleDetected)
						return ret.ToString();
					return String.Format("{0} {1} {2}", t.Name, ret, Edge.FormatMark(new Edge(0, mark)));
				}
			};

			public Instance FindRoot(int m)
			{
				RootEdgeData red;
				return roots.TryGetValue(tr.FindTop(m), out red) ? red.t : null;
			}

			public RootEdgeData FindRootData(int m)
			{
				RootEdgeData red;
				return roots.TryGetValue(tr.FindTop(m), out red) ? red : default(RootEdgeData);
			}

			[DebuggerDisplay("{ToString(),nq}")]
			public struct TaggedFsPath
			{
				public RootEdgeData red;
				public FsPath fsp;

				public override string ToString()
				{
					return String.Format("{0} {1}", red.ret == RootEdgeType.Unknown ? "???" : red.ToString(), fsp.ToString());
				}
			};

#if EXHAUSTIVE_POOL_SEARCH
			class PathInfoFinder
			{
				RootAnalysis ra;
				int m_in;
				bool f_short;
				List<TaggedFsPath> paths = new List<TaggedFsPath>();

				public PathInfoFinder(RootAnalysis ra, int m_in, bool f_short)
				{
					this.ra = ra;
					this.m_in = m_in;
					this.f_short = f_short;
					_find(m_in, new List<KeyValuePair<int, String>>());
				}

				void _find(int m, List<KeyValuePair<int, String>> path)
				{
					Debug.Assert(m != 0);
					RootEdgeData red;
					if (path.Any(kvp => kvp.Key == m))
					{
						paths.Add(new TaggedFsPath
						{
							fsp = new FsPath(path.Select(kvp => kvp.Value).Reverse()),
							red = new RootEdgeData(null, RootEdgeType.CycleDetected, 0)
						});
						throw new Exception("cyclical path");
						//return;
					}

					//if (ra.roots.TryGetValue(m, out red))
					//{
					//    paths.Add(new TaggedFsPath { fsp = new FsPath(path.Select(kvp => kvp.Value).Reverse()), red = red });
					//    return;
					//}

					bool f_any = false;
					path.Add(default(KeyValuePair<int, string>));
					foreach (var cp in ra.tr.Pools)
					{
						foreach (var pe in cp.PoolEdges)
						{
							Edge e = pe.Value;
							if (e.Mark == m)
							{
								String sx;
								if (f_short)
									sx = cp.Feature;
								else
									sx = String.Format("[{0} {1} {2}]", cp.Feature.ToUpper(), ra.tr.tm.GetEdgeType(e.FlagsId).Name, Edge.FormatMark(e));

								path[path.Count - 1] = new KeyValuePair<int, String>(m, sx);

								if (ra.roots.TryGetValue(m, out red))
									paths.Add(new TaggedFsPath { fsp = new FsPath(path.Select(kvp => kvp.Value).Reverse()), red = red });

								f_any = true;

								_find(pe.Key, new List<KeyValuePair<int, String>>(path));
							}
						}
					}
					if (!f_any)
					{
						path.RemoveAt(path.Count - 1);
						paths.Add(new TaggedFsPath
						{
							fsp = new FsPath(path.Select(kvp => kvp.Value).Reverse()),
							red = new RootEdgeData(null, RootEdgeType.Unknown, 0)
						});
					}
				}

				public List<TaggedFsPath> Result { get { return paths; } }
			};


			public List<TaggedFsPath> PathInfoStrings(int m_in, bool f_short = false)
			{
				if (m_in == 0)
					return new List<TaggedFsPath>();
				var r = new PathInfoFinder(this, m_in, f_short).Result;

				return r;
			}

			public String PathInfo(int m_in)
			{
				return PathInfoStrings(m_in).StringJoin(Environment.NewLine);
			}
#endif
		};
	};

	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	///
	/// debug: U N I F I C A T I O N
	///
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	[DebuggerDisplay("{ToString(),nq}")]
	public abstract partial class Unification
	{
		static int next_id = 0;
		public readonly int id;

		[DebuggerDisplay("{ToString(),nq}")]
		sealed partial class UnifCoref : List<TfsEdge>
		{
			static int next_id = 0xCF00;
			readonly public int id;
			public Unification uh;

			public UnifCoref(Unification uh)
			{
				this.uh = uh;
				this.id = Interlocked.Increment(ref next_id);
			}

			TfsEdge[] DictionaryKeys()
			{
				return uh.corefs.Where(kvp => kvp.Value == this).Select(kvp => kvp.Key).ToArray();
			}

			///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
			/// <summary>
			/// dst_map includes only PoolMarks which refer to the target TFS instance, that is, the one that is currently
			/// currently being constructed by unification.
			/// </summary>
			///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
			IEnumerable<PoolMark> PoolMarks()
			{
				return pmx;
			}

			public override string ToString()
			{
#if true
				return String.Format("{0} — {1} {2} PMs █ {3} █ {4}",
					this.id.ToString("X4"),
					Master.ToString(),
					pmx.Count,
					PoolMarks().Select(z => z.ToString()).StringJoin(" ▎"),
					this.StringJoin(" "));
#else
				var te_keys = uh.corefs.Where(kvp => kvp.Value == this).Select(kvp => kvp.Key).ToArray();

				HashSet<TfsEdge> c = new HashSet<TfsEdge>(this);
				c.IntersectWith(te_keys);

				String a = te_keys.Except(c).Select(te => "[" + te + "]").StringJoin(" ");
				String b = this.Except(c).Select(te => "{" + te + "}").StringJoin(" ");

				return String.Format("{0} — {1} {2} PMs █ {3} █ {4} {5} {6}",
					this.id.ToString("X4"),
					Master.ToString(),
					pmx.Count,
					PoolMarks().Select(z => z.ToString()).StringJoin(" ▎"),
					a,
					c.StringJoin(" "),
					b);
#endif
			}
		};

		public partial class Expander : Unification
		{
			Type _t_exp;
		}
	};



	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	///
	/// debug: G R A M M A R
	///
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	public partial class Grammar : IGrammar
	{
		public String GarbageReport(HashSet<PoolMark> hspm = null)
		{
			hspm = hspm ?? Reachable();
			using (StringWriter sw = new StringWriter())
			{
				loadtray.CheckOrphanedEdges(sw, hspm);
				return sw.ToString();
			}
		}
	};
#else //DEBUG

	public partial class Grammar
	{
		public String GarbageReport(HashSet<PoolMark> hspm = null) { return "release build - no garbage report"; }
	};

#endif // DEBUG
}
Grammar Composition System
