using System;
using System.IO;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
using miew.Debugging;
using miew.Enumerable;
using miew.String;

namespace agree
{
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	/// <summary>
	/// 
	/// </summary>
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	public abstract partial class Tfs : ISysObj
	{
		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		public Double MarkDensity
		{
			get
			{
				HashSet<int> in_marks = InMarks;
				if (in_marks.Count == 0)
					return 0;
				int range = in_marks.Max() - in_marks.Min() + 1;
				return (double)in_marks.Count / range;
			}
		}

		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		public HashSet<int> InMarks
		{
			get { return FeatMarkEdges.Select(fme => fme.mark).ToHashSet(); }
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		public HashSet<FeatMark> FeatMarksBelow
		{
			get
			{
				if (Edge.Mark == 0)
					return FeatMark.EmptyHashSet;
				return new FeatMarkGatherer(this, Edge, new HashSet<FeatMark>()).Result;
			}
		}
		public void GatherFeatMarksBelow(HashSet<FeatMark> hs)
		{
			if (Edge.Mark != 0)
				new FeatMarkGatherer(this, Edge, hs);
		}

		sealed class FeatMarkGatherer
		{
			Tfs tfs;
			int[][] rgrgfix;
			HashSet<FeatMark> hs;

			public FeatMarkGatherer(Tfs tfs, Edge e, HashSet<FeatMark> hs)
			{
				this.tfs = tfs;
				this.rgrgfix = tfs.tm.rgrgfix_by_type;
				this.hs = hs ?? new HashSet<FeatMark>();
				_gather(e);
			}

			void _gather(Edge e)
			{
				foreach (int i_feat in rgrgfix[(int)(e.FlagsId & Edge.Flag.MultiIdMask)])
				{
					Edge ne;
					FeatMark fm;
					if (tfs.TryGetEdge(i_feat, e.Mark, out ne) && !hs.Contains(fm = new FeatMark(i_feat, e.Mark)))
					{
						hs.Add(fm);
						if (ne.Mark != 0)
							_gather(ne);
					}
				}
			}

			public HashSet<FeatMark> Result { get { return hs; } }
		};

		public struct FeatMarkEdgeGatherer
		{
			Tfs tfs;
			int[][] rgrgfix;
			HashSet<FeatMark> hs;
			int in_filter, out_filter;

			public FeatMarkEdgeGatherer(Tfs tfs, int in_filter = int.MaxValue, int out_filter = int.MaxValue)
			{
				this.tfs = tfs;
				this.rgrgfix = tfs.tm.rgrgfix_by_type;
				this.in_filter = in_filter;
				this.out_filter = out_filter;
				this.hs = new HashSet<FeatMark>();
			}

			public IEnumerable<FeatMarkEdge> Gather(Edge e)
			{
				foreach (int i_feat in rgrgfix[(int)(e.FlagsId & Edge.Flag.MultiIdMask)])
				{
					Edge ne;
					FeatMark fm;
					if (tfs.TryGetEdge(i_feat, e.Mark, out ne) && !hs.Contains(fm = new FeatMark(i_feat, e.Mark)))
					{
						hs.Add(fm);
						if ((in_filter == int.MaxValue || e.Mark == in_filter) &&
							(out_filter == int.MaxValue || ne.Mark == out_filter))
							yield return new FeatMarkEdge(i_feat, e.Mark, ne);
						if (ne.Mark != 0)
							foreach (var fme in Gather(ne))
								yield return fme;
					}
				}
			}
		};


		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		public HashSet<TfsFeatMark> TfsFeatMarksBelow
		{
			get
			{
				if (Edge.Mark == 0)
					return TfsFeatMark.EmptyHashSet;
				return new TfsFeatMarkGatherer(this, Edge, new HashSet<TfsFeatMark>()).Result;
			}
		}
		public void GatherTfsFeatMarksBelow(HashSet<TfsFeatMark> hs)
		{
			if (Edge.Mark != 0)
				new TfsFeatMarkGatherer(this, Edge, hs);
		}

		sealed class TfsFeatMarkGatherer
		{
			Tfs tfs;
			int[][] rgrgfix;
			HashSet<TfsFeatMark> hs;

			public TfsFeatMarkGatherer(Tfs tfs, Edge e, HashSet<TfsFeatMark> hs)
			{
				this.tfs = tfs;
				this.rgrgfix = tfs.tm.rgrgfix_by_type;
				this.hs = hs ?? new HashSet<TfsFeatMark>();
				_gather(e);
			}

			void _gather(Edge e)
			{
				foreach (int i_feat in rgrgfix[(int)(e.FlagsId & Edge.Flag.MultiIdMask)])
				{
					Edge ne;
					TfsFeatMark tfm;
					if (tfs.TryGetEdge(i_feat, e.Mark, out ne) && !hs.Contains(tfm = new TfsFeatMark(tfs, i_feat, e.Mark)))
					{
						hs.Add(tfm);
						if (ne.Mark != 0)
							_gather(ne);
					}
				}
			}

			public HashSet<TfsFeatMark> Result { get { return hs; } }
		};

		public int GarbageReport(TextWriter tw)
		{
			HashSet<FeatMark> reachable = FeatMarksBelow;
			int ec = EdgeCount;
			if (reachable.Count != ec)
			{
				tw.WriteLine("TFS {0} ({1}):  {2} reachable, {3} items", Name, GetType().Name, reachable.Count, ec);
				HashSet<FeatMark> all = FeatMarkEdges.Select(fme => fme.FeatMark).ToHashSet();
				all.ExceptWith(reachable);

				foreach (FeatMark fm in all)
					tw.WriteLine("\t{0,3} {1,-13}  {2}", fm.m, tm.feat_arr[fm.i_feat].feature.ToUpper(), GetEdge(fm.i_feat, fm.m));
			}
			return reachable.Count;
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#if DEBUG
		long _h = -1;
		public long TfsHash()
		{
			if (_h == -1)
				_h = TfsHash(Edge);
			return _h;
		}
#else
		public long TfsHash()
		{
			return TfsHash(Edge);
		}
#endif
		public long TfsHash(Edge e)
		{
			return e.Mark != 0 ? new TfsHashGatherer(this, e).Result : (long)((int)e.FlagsId ^ 0x12345678);
		}

		sealed class TfsHashGatherer : HashSet<FeatMark>
		{
			Tfs tfs;
			TypeMgr tm;
			long h = 0;

			public TfsHashGatherer(Tfs tfs, Edge e)
			{
				this.tfs = tfs;
				this.tm = tfs.tm;
				_gather(e, 1);
			}

			void _gather(Edge e, int level)
			{
				foreach (int i_feat in tm.rgrgfix_by_type[(int)(e.FlagsId & Edge.Flag.MultiIdMask)])
				{
					Edge ne;
					if (tfs.TryGetEdge(i_feat, e.Mark, out ne))
					{
						h += (((long)(uint)i_feat << 32) | (long)(uint)ne.FlagsId) * level;
						FeatMark fm = new FeatMark(i_feat, e.Mark);
						if (!this.Contains(fm))
						{
							this.Add(fm);
							if ((ne.FlagsId & Edge.Flag.EtmNonBareType) != 0)
								_gather(ne, level + 1);
						}
					}
				}
			}

			public long Result { get { return h; } }
		};

#if RUDE_TRUNCATE
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public void RudeTruncate(Edge e)
		{
			new RudeTruncator(this, e);
		}

		sealed class RudeTruncator
		{
			Tfs tfs;
			TypeMgr tm;
			HashSet<Edge> corefs = null;

			public RudeTruncator(Tfs tfs, Edge e)
			{
				this.tfs = tfs;
				this.tm = tfs.tm;
				_rude_truncate(e);
			}

			void _rude_truncate(Edge e)
			{
				foreach (int i_feat in tm.rgrgfix_by_type[(int)(e.FlagsId & Edge.Flag.MultiIdMask)])
				{
					Edge ne;
					if (tfs.TryGetEdge(i_feat, e.Mark, out ne))
					{
						bool f_descend = true;
						if (ne.FlagsId < 0)
						{
							if (corefs == null)
								corefs = new HashSet<Edge> { ne };
							else if (!corefs.Contains(ne))
								corefs.Add(ne);
							else
								f_descend = false;
						}
						if (f_descend && (ne.FlagsId & Edge.Flag.EtmNonBareType) != 0)
							_rude_truncate(ne);
						tfs.RemoveEdge(i_feat, e.Mark);
					}
				}
			}
		};
#endif

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public String ToPathList(bool f_marks = false)
		{
			return new PathLister(this, Edge, null, f_marks).ToString();
		}
		public String ToPathList(String label, bool f_marks = false)
		{
			return new PathLister(this, Edge, label, f_marks).ToString();
		}
		public String ToPathList(Edge edge, String label, bool f_marks = false)
		{
			return new PathLister(this, edge, label, f_marks).ToString();
		}

		sealed public class PathLister : List<String>
		{
			Tfs tfs;
			TypeMgr tm;
			Stack<String> stack = new Stack<String>();
			Dictionary<Edge, int> d = null;
			int coref_tag = 0;
			bool f_marks;
			bool f_internal;
			HashSet<FeatMark> reachable = null;

			public PathLister(Tfs tfs, Edge e, String label, bool f_marks, HashSet<FeatMark> reachable = null, bool f_internal = false)
			{
				this.tfs = tfs;
				this.tm = tfs.tm;
				this.f_marks = f_marks;
				this.f_internal = f_internal;
				this.reachable = reachable;
				if (label != null)
					this.Add(String.Format(";;;;;;;;; ({0})", label));
				_list_paths(e, null);
			}

			void _list_paths(Edge e, String s_usage)
			{
				bool f_descend = true;
				Type t;
				if (tm.IsTopId(e))
				{
					t = tm.TopType;
					f_descend = false;
				}
				else
					t = tm.GetEdgeType(e.FlagsId);
				String s = String.Format("{0} {1}", stack.Reverse().StringJoin("."), t);
				if (tm.IsStringValue(e.FlagsId))
					s += " “" + tm.GetStringValue(e.FlagsId) + "”";
				if (e.FlagsId < 0)
				{
					if (d == null)
						d = new Dictionary<Edge, int>();
					int cre;
					if (f_internal)
					{
						cre = e.Mark;
						if (!d.ContainsKey(e))
							d.Add(e, 1);
						else
							f_descend = false;
					}
					else
					{
						if (!d.TryGetValue(e, out cre))
							d.Add(e, cre = coref_tag++);
						else
							f_descend = false;
					}
					if (!f_internal)
						s += " #" + cre.ToString();
				}

				if (f_internal)
#if DEBUG
					s += " " + Edge.FormatMark(e);
#else
					s += " " + e.Mark.ToString();
#endif

				if (s_usage != null)
					s += " in-use by " + s_usage;

				this.Add(s);
				if (f_descend && e.Mark != 0)
				{
					/// this determines the order of coref tag numbering. it used to be specified here with 
					/// .OrderBy(cp => cp.IntroducedBy.m_level) but this is not needed so long as the feature index order
					/// in the type is kept this way, as it is at this time.
					foreach (int i_feat in tm.rgrgfix_by_type[(int)(e.FlagsId & Edge.Flag.MultiIdMask)])
					{
						Edge q;
						String usage = null;
#if DEBUG
						if (reachable != null && reachable.Contains(new FeatMark(i_feat, e.Mark)))
							usage = tfs.Roots.FindRootData(e.Mark).ToString();
#endif

						if (tfs.TryGetEdge(i_feat, e.Mark, out q))
						{
							stack.Push(tm.feat_arr[i_feat].feature.ToUpper());
							_list_paths(q, usage);
							stack.Pop();
						}
					}
				}
			}

			public override string ToString() { return this.StringJoin(Environment.NewLine) + Environment.NewLine; }
		};


		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public class MonospaceFormatter
		{
			TypeMgr tm;
			Tfs tfs;
			Dictionary<Edge, int> corefs = new Dictionary<Edge, int>();
			bool f_uncons_top = true;
			bool f_unfill = true;
			int[] feature_order = null;
			IDictionary<String, String> type_name_remapping = null;

			public MonospaceFormatter(TypeMgr tm)
			{
				this.tm = tm;
			}

			public int[] FeatureDisplayOrder
			{
				get { return feature_order; }
				set { feature_order = value; }
			}

			public bool Unfill
			{
				get { return f_unfill; }
				set { f_unfill = value; }
			}

			/// <summary>
			/// Type names can be substituted to account for e.g. different glb number assignments in a comparison
			/// system.
			/// </summary>
			public IDictionary<String, String> TypeNameRemapping
			{
				get { return type_name_remapping; }
				set { type_name_remapping = value; }
			}

			/// <summary>
			/// Note: Single-threaded (use of corefs)
			/// </summary>
			public String FormatEdge(Tfs tfs)
			{
				this.tfs = tfs;
				corefs.Clear();
				String r = tm.GetEdgeType(tfs.Edge.FlagsId).Name;
				String s = _format_edge(0, tfs.Edge);
				if (s != String.Empty)
					r += Environment.NewLine + s;
				return r;
			}

			String _format_edge(int indent, Edge e)
			{
				var rgcr = (f_uncons_top ?
									tfs.AllConstraintRefs(e) :
									tfs.ConstrainedRefsOnly(e))
								.ToArray();
				if (rgcr.Length == 0)
					return String.Empty;

				if (feature_order != null)
					rgcr = rgcr.OrderBy(cr => Array.IndexOf<int>(feature_order, cr.i_feat)).ToArray();

				int feat_max = rgcr.Max(cr => cr.Feature.Length) + 1;

				String s_indent = new String(' ', indent);
				StringBuilder sb = new StringBuilder();

				bool f_first = true;
				foreach (ConstraintRef cr in rgcr)
				{
					Edge ne = cr.Constraint;
					if (f_first)
					{
						sb.Append(s_indent + "[ ");
						f_first = false;
					}
					else
						sb.Append("," + Environment.NewLine + s_indent + "  ");

					sb.Append(cr.Feature.ToUpper().PadRight(feat_max));

					bool f_old_coref = false;
					String coref_text = String.Empty;
					if (ne.IsCoreferenced)
					{
						int i_coref;
						if (!corefs.TryGetValue(ne, out i_coref))
						{
							i_coref = corefs.Count + 1;
							corefs.Add(ne, i_coref);
							coref_text = String.Format("#{0}:", i_coref);
						}
						else
						{
							coref_text = "#" + i_coref.ToString();
							f_old_coref = true;
						}
						sb.Append(coref_text);
					}

					if (!f_old_coref)
					{
						String s_type;
						if (tm.IsStringValue(ne.FlagsId))
							s_type = "\"" + tm.GetStringValue(ne.FlagsId) + "\"";
						else
						{
							s_type = tm.GetEdgeType(ne.FlagsId).Name;
							String s_tmp;
							if (type_name_remapping != null && type_name_remapping.TryGetValue(s_type, out s_tmp))
								s_type = s_tmp;
						}

						sb.Append(s_type);

						if (!f_unfill || !tfs.CanUnfill(cr))
						{
							String cons = _format_edge(indent + feat_max + 2 + coref_text.Length, ne);
							if (cons.Length > 0)
								sb.Append(Environment.NewLine + cons);
						}
					}
				}
				sb.Append(" ]");
				return sb.ToString();
			}
		};


		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public bool CanUnfill(ConstraintRef cr)
		{
			Edge e = cr.Constraint;
			Type t0 = tm.GetEdgeType(e.FlagsId);

			foreach (int fix in t0.fc.rg_fix)
			{
				Edge ne;
				if (TryGetEdge(fix, e.Mark, out ne))
				{
					Edge ne2;
					TryGetEdge(fix, t0.Expanded.Edge.Mark, out ne2);

					Type t3 = tm.GetEdgeType(ne2.FlagsId);


					if (ne.IsCoreferenced)
						return false;

					if (tm.GetEdgeType(ne.FlagsId) != t3)
						return false;

					if (ne.Mark != 0 && !CanUnfill(new ConstraintRef(this, e, fix)))
						return false;
				}
			}
			return true;
		}

		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		RootAnalysis ra;

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

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public class RootAnalysis
		{
			Tfs tfs;
			TypeMgr tm;
			Dictionary<int, RootEdgeData> roots = new Dictionary<int, RootEdgeData>();

			public RootAnalysis(Tfs tfs)
			{
				this.tfs = tfs;
				this.tm = tfs.tm;
				foreach (Instance t in tm.AllInstances)
				{
					int mx_d;
					mx_d = t.Definition.Edge.Mark;
					if (mx_d != 0)
					{
						int mx_e = 0;
						if (t.IsExpanded)
						{
							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;
#if DEBUG
				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)));
				}
#endif
			};

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

			public RootEdgeData FindRootData(int m)
			{
				RootEdgeData red;
				return roots.TryGetValue(tfs.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());
				}
			};
		};

		public int FindTop(int mark)
		{
			int top_mark = mark;
		restart:
			foreach (var fme in this.FeatMarkEdges)
			{
				if (fme.e.Mark == top_mark)
				{
					top_mark = fme.mark;
					goto restart;
				}
			}
			return top_mark;
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public void CleanGarbage(HashSet<FeatMark> reachable)
		{
			//HashSet<FeatMark> pool_pms = new HashSet<FeatMark>(this.FeatMarkEdges.Select(fme => fme.FeatMark));
			//HashSet<FeatMark> garbage = new HashSet<FeatMark>(pool_pms.Except(reachable));

			//foreach (Edge gedge in TreeTops(garbage))
			//    if (gedge.Mark != 0)
			//        RudeTruncate(gedge);
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public IEnumerable<Edge> TreeTops(IEnumerable<FeatMark> set)
		{
			HashSet<FeatMark> hs = new HashSet<FeatMark>(set);
			foreach (FeatMark fm in set)
				hs.ExceptWith(AllFeatMarks(fm.Constraint(this)));

			return hs._GroupBy(fm => fm.m)
				.Select(g =>
				{
					Type tx = tm.GlbOfMany(g.Select(pm => pm.i_feat)) ?? tm.TopType;
					return new Edge((Edge.Flag)tx.m_id, g.Key);
				});
		}


		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		public IDictionary<Edge, ReentrancyFinder.Entry> Reentrancies
		{
			get { return this.GetReentrancies(Edge); }
		}

		public IDictionary<Edge, ReentrancyFinder.Entry> GetReentrancies(Edge e)
		{
			return e.Mark != 0 ? new ReentrancyFinder(this, e).Result : ReentrancyFinder.NoCorefs;
		}

#if DEBUG
		public virtual void CheckCoreferences()
		{
			//var dfe = GetReentrancies(Edge);
			//if (dfe.Count != 0 && this.CorefTallies.Any(kvp => dfe[kvp.Key].Count != kvp.Value))
			//{
			//    if (Debugger.IsAttached)
			//        Debugger.Break();
			//    else
			//        throw new Exception();
			//}
		}
#endif
	};

	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	/// <summary>
	/// 
	/// </summary>
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	public sealed class ReentrancyFinder
	{
		public readonly static IDictionary<Edge, Entry> NoCorefs = new Dictionary<Edge, Entry>();

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// 
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public class Entry : HashSet<ConstraintRef>
		{
			public Entry(ConstraintRef cref_first, int i_tag)
			{
				this.cref_display = cref_first;
				this.i_tag = i_tag;
			}
			readonly public int i_tag;
			public ConstraintRef cref_display;
			public override String ToString() { return String.Format("#{0} in-edges: {1}", i_tag, this.Count); }
		};

		readonly Tfs tfs;
		readonly TypeMgr tm;
		Dictionary<Edge, Entry> dict = null;
		int coref_tag;

		public ReentrancyFinder(Tfs tfs, Edge e)
		{
			Debug.Assert(e.Mark != 0);
			this.tfs = tfs;
			this.tm = tfs.tm;
			this.coref_tag = 0;
			_get_reentrancies(e);
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// 
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		void _get_reentrancies(Edge e)
		{
			/// this determines the order of coref tag numbering. it used to be specified here with 
			/// .OrderBy(cp => cp.IntroducedBy.m_level) but this is not needed so long as the feature index order
			/// in the type is kept this way, as it is at this time.
			foreach (int i_feat in tm.rgrgfix_by_type[(int)(e.FlagsId & Edge.Flag.MultiIdMask)])
			{
				Edge next_edge;
				if (tfs.TryGetEdge(i_feat, e.Mark, out next_edge))
				{
					if (next_edge.FlagsId < 0)
					{
						ConstraintRef cref = new ConstraintRef(tfs, e, i_feat);
						Entry cre;
						if (dict == null)
							dict = new Dictionary<Edge, Entry>();
						else if (dict.TryGetValue(next_edge, out cre))
						{
							cre.Add(cref);
							continue;
						}
						dict.Add(next_edge, cre = new Entry(cref, coref_tag++));
						cre.Add(cref);
					}
					if ((next_edge.FlagsId & Edge.Flag.EtmMask) == Edge.Flag.EtmNonBareType)
						_get_reentrancies(next_edge);
				}
			}
		}

		public IDictionary<Edge, Entry> Result { get { return dict ?? NoCorefs; } }
	};


	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	/// <summary>
	/// 
	/// </summary>
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	public unsafe struct EdgeCounter
	{
		readonly Tfs tfs;
		readonly int[][] rgrgfix;
		readonly byte[] coref_tallies;
		byte* visited;
		int c_coref_actual;
		int c_edge;

		public EdgeCounter(Tfs tfs, Edge e, byte[] coref_tallies)
		{
			Debug.Assert(e.Mark != 0);
			this.tfs = tfs;
			this.rgrgfix = tfs.tm.rgrgfix_by_type;

			this.coref_tallies = coref_tallies;
			byte* pv = stackalloc byte[coref_tallies.Length];
			visited = pv;
			c_coref_actual = 0;
			c_edge = 0;

			_tally_section(&e);
		}

		public int ActualCount { get { return c_coref_actual; } }

		public int EdgeCount { get { return c_edge; } }

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// 
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		void _tally_section(Edge* pe)
		{
			foreach (int i_feat in rgrgfix[(int)(pe->FlagsId & Edge.Flag.MultiIdMask)])
			{
				Edge ne;
				if (tfs.TryGetEdge(i_feat, pe->Mark, out ne))
				{
					if (ne.FlagsId < 0)
					{
						int ix = ~ne.Mark;
						coref_tallies[ix]++;
						if (visited[ix] == 1)
							continue;
						c_coref_actual++;
						visited[ix] = 1;
					}
					c_edge++;
					if ((ne.FlagsId & Edge.Flag.EtmMask) == Edge.Flag.EtmNonBareType)
						_tally_section(&ne);
				}
			}
		}
	};

	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	/// <summary>
	/// 
	/// </summary>
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	public unsafe struct EdgeCounterRestricted
	{
		readonly Tfs tfs;
		readonly int[][] rgrgfix;
		readonly byte[] coref_tallies;
		readonly byte[] restrictor;
		byte* visited;
		int c_coref_actual;
		int c_edge;

		public EdgeCounterRestricted(Tfs tfs, Edge e, byte[] coref_tallies)
		{
			Debug.Assert(e.Mark != 0);
			this.tfs = tfs;
			this.rgrgfix = tfs.tm.rgrgfix_by_type;
			this.restrictor = tfs.tm.config.parser.packing_restrictor_map;

			this.coref_tallies = coref_tallies;
			byte* pv = stackalloc byte[coref_tallies.Length];
			visited = pv;
			c_coref_actual = 0;
			c_edge = 0;

			_tally_section(&e);
		}

		public int ActualCount { get { return c_coref_actual; } }

		public int EdgeCount { get { return c_edge; } }

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// 
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		void _tally_section(Edge* pe)
		{
			foreach (int i_feat in rgrgfix[(int)(pe->FlagsId & Edge.Flag.MultiIdMask)])
			{
				if (restrictor[i_feat] == 1)
					continue;
				Edge ne;
				if (tfs.TryGetEdge(i_feat, pe->Mark, out ne))
				{
					if (ne.FlagsId < 0)
					{
						int ix = ~ne.Mark;
						coref_tallies[ix]++;
						if (visited[ix] == 1)
							continue;
						c_coref_actual++;
						visited[ix] = 1;
					}
					c_edge++;
					if ((ne.FlagsId & Edge.Flag.EtmMask) == Edge.Flag.EtmNonBareType)
						_tally_section(&ne);
				}
			}
		}
	};
}