Grammar Composition System

/src/branch/20110407-thread-priority/agree-sys/35-tray.cs

using System;
using System.Diagnostics;
using System.IO;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
using System.Collections.Concurrent;
using System.Runtime.Serialization;

using glue;
using glue.Extensions.String;
using glue.Extensions.String.Builder;
using glue.Debugging;
using glue.Extensions.Enumerable;
using glue.Collections.XSpinLock;
using glue.Collections.LockFreeDictionary;

#pragma warning disable 0649

namespace agree
{
	public interface IFreezableTray
	{
		void Freeze();
	}

	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	/// <summary>
	/// Tray (abstract) : 
	/// An array of ConstraintPools, one for each Feature, ordered according to feature indexes for the owning TypeMgr
	/// </summary>
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	abstract public partial class Tray
	{
		public Tray(int tix, TypeMgr tm, int last_mark_issued, int next_id)
		{
			Nop.X(fsp1, fsp2, fsp3);

			this.TargetTfs = WrapAsTargetTfs(default(Edge));
			this.tix = tix;
			this.tm = tm;
			this.Pools = new ConstraintPool[tm.Features.Count];
			this._unk = new UnknownPoolClass(this, -1);
			this.last_mark_issued = last_mark_issued;
			this.next_id = next_id == -1 ? (TargetId + IdIncrement) : next_id;
		}

		FalseSharing.Padding60 fsp1;
		/// Mark management is global per-tray.
		//protected 
		public
			Int32 last_mark_issued;

		FalseSharing.Padding60 fsp2;

		/// Although less closely coupled to the typical use in the unification helper class, TfsIds are also issued 
		/// by this AtomicSequencer which belongs to this Tray
		int next_id;

		FalseSharing.Padding60 fsp3;

		internal int _protect_mark = 0;

		public void Protect()
		{
			_protect_mark = last_mark_issued;
		}
		public void ResetMark()
		{
			last_mark_issued = Pools.Max(cp => cp.Marks.Max());
		}

		/// A special TfsId is reserved for the unification target
		const int IdIncrement = 1 << 6;
		public const int TargetId = 2 << 6;

		public TfsEdge TargetTfs;

		/// id number for this tray; these are unique across all grammars, i.e. not just unique within a grammar or TypeMgr,
		/// because this is overloaded with the function of allowing an edge to find the grammar it belongs to.
		public readonly int tix;

		/// owning type manager
		public readonly TypeMgr tm;

		/// array of ConstraintPools
		public readonly ConstraintPool[] Pools;

		public int c_truncators = 0;
		public ManualResetEvent/*Slim*/ mre_truncate_ok = new ManualResetEvent/*Slim*/(true);

		/// Allows a ConstratintRef to record this Tray as the one that it will be concerned with, without having to select 
		/// a feature
		readonly ConstraintPool _unk;
		public ConstraintPool UnknownPool { get { return _unk; } }

		/// each Tray provides an registry of (optional) TfsEdge names
		readonly ConcurrentDictionary<TfsEdge, String> names = new ConcurrentDictionary<TfsEdge, String>();

		public void RegisterTfsName(TfsEdge te, String s)
		{
			names[te] = s;
		}

		public String GetTfsName(TfsEdge te)
		{
			String s;
			names.TryGetValue(te, out s);
			return s;
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		///
		/// grammar compiled paths
		///
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

		public void CompileGrammarPaths(GrammarConfig cfg)
		{
			RuleArgsPath = new TrayCompiledFsPath(this, cfg.rule_args_path);
			KeyDaughterPath = new TrayCompiledFsPath(this, cfg.key_daughter_path);
			OrthPath = new TrayCompiledFsPath(this, cfg.orth_path);

			if (cfg.deleted_daughters != null)
				DeletedDaughters = cfg.deleted_daughters.Select(s => Pools[tm.feat_map[s].i_feat]).ToArray();
		}

		public TrayCompiledFsPath RuleArgsPath;
		public TrayCompiledFsPath KeyDaughterPath;
		public TrayCompiledFsPath OrthPath;
		public ConstraintPool[] DeletedDaughters = null;

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// Create an edge which will be used in this tray. The edge is not persisted into the tray.
		/// Caller may not submit a non-bare mark if the requirements for a non-bare mark are not met
		/// But caller can optionally submit a bare mark for any new edge; the current design enforces that non-bare
		/// types will always have a non-bare mark
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public Edge CreateRecycledEdge(Type t, int m, bool f_coref)
		{
			Debug.Assert(t != null && t.mgr == tm);

			Edge.Flag f;
			if (t == tm.StringType)
				f = Edge.Flag.EtmString;
			else
			{
				f = (Edge.Flag)t.m_id;
				if ((t.m_flags & Type.Flags.HasAnyFeatures) > 0)
					f |= Edge.Flag.EtmNonBareType;
			}

			if (f_coref)
				f |= Edge.Flag.Coreference;

			if ((f & (Edge.Flag.Coreference | Edge.Flag.EtmNonBareType)) != 0)
			{
				if (m == 0)
					m = Interlocked.Increment(ref last_mark_issued);
			}
			else
			{
				/// Caller may not submit a non-bare mark if the requirements for a non-bare mark are not met
				Debug.Assert(m == 0);
			}
			return new Edge(f, m);
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// Create an edge with the specified type, coreference status, and mark.
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public Edge CreateRecycledEdge(Edge.Flag f, int m)
		{
			Debug.Assert(tm.GetEdgeType(f).IsBare == ((f & Edge.Flag.EtmNonBareType) == 0));

			if ((f & (Edge.Flag.Coreference | Edge.Flag.EtmNonBareType)) != 0)
			{
				if (m == 0)
					m = Interlocked.Increment(ref last_mark_issued);
			}
			else
			{
				/// Caller may not submit a non-bare mark if the requirements for a non-bare mark are not met
				Debug.Assert(m == 0);
			}

			return new Edge(f, m);
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// Auto-mark based on the bareness of the type
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public Edge CreateEdge(Type t, bool f_coref)
		{
			Debug.Assert(t != null && t.mgr == tm);
			Edge.Flag f;

			if (t == tm.StringType)
				f = Edge.Flag.EtmString;
			else
			{
				f = (Edge.Flag)t.m_id;
				if ((t.m_flags & Type.Flags.HasAnyFeatures) > 0)
					f |= Edge.Flag.EtmNonBareType;
			}

			if (f_coref)
				f |= Edge.Flag.Coreference;

			int m = (f & (Edge.Flag.Coreference | Edge.Flag.EtmNonBareType)) == 0 ? 0 :
							Interlocked.Increment(ref last_mark_issued);

			return new Edge(f, m);
		}


		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// Auto-mark based on the bareness of the type
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public Edge CreateEdge(Edge.Flag f)
		{
			Debug.Assert(tm.GetEdgeType(f).IsBare == ((f & Edge.Flag.EtmNonBareType) == 0));

			return new Edge(f, (f & (Edge.Flag.Coreference | Edge.Flag.EtmNonBareType)) == 0 ? 0 :
							Interlocked.Increment(ref last_mark_issued));
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public void ChangeEdgeCoreference(PoolMark pm, bool f_coref)
		{
			Debug.Assert(pm.in_mark != 0);
			Debug.Assert(pm.Pool.tr == this);

			Edge e = pm.Constraint;
			if (f_coref)
			{
				Debug.Assert(!e.IsCoreferenced);
				if (tm.IsTopId(e))
					e = CreateEdge(tm.TopType, true);
				else
					e = CreateRecycledEdge(e.FlagsId | Edge.Flag.Coreference, e.Mark);
				pm.SetConstraint(e);
			}
			else
			{
				Debug.Assert(e.IsCoreferenced);
				if (tm.IsTopId(e))
					pm.RemoveConstraint();
				else
				{
					Debug.Assert(tm.GetEdgeType(e.FlagsId).IsBare == ((e.FlagsId & Edge.Flag.EtmNonBareType) == 0));
					pm.SetConstraint(new Edge(e.FlagsId & ~Edge.Flag.Coreference, (e.FlagsId & Edge.Flag.EtmNonBareType) == 0 ? 0 : e.Mark));
				}
			}
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// Create a string value edge
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public Edge CreateStringEdge(int sid, bool f_coref)
		{
			Edge.Flag f = Edge.Flag.EtmString | (Edge.Flag)sid;
			int m = 0;
			if (f_coref)
			{
				f |= Edge.Flag.Coreference;
				m = Interlocked.Increment(ref last_mark_issued);
			}
			return new Edge(f, m);
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// Add a unique string value
		/// constrained strings must never use Edge.MarkBare (or you'd lose the ability to distinguish their values, which must
		/// be isolating), but identical strings should share the same (non-bare) mark, when coreferenced. When unconstrained,
		/// the string type itself should use Edge.MarkBare.
		/// </summary>
		/// <remarks>
		/// LKB treats empty string as distinct from unconstrained string type
		///			s1 := *top* & [ X *top* ].
		///			s2 := s1 & [ X "foo" ].
		///			s3 := s1 & [ X "" ].
		///			s4 := s2 & s3.
		/// </remarks>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public Edge CreateStringEdge(String s)
		{
			if (tm.IsPetrified)
				throw new Exception("Type hierarchy has already finished loading, cannot add more strings");

			return CreateStringEdge(tm.strings.GetOrAdd(s), false);
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// Copy an edge, retaining string contents and shareable aspects. If non-shareable, a new mark is given.
		/// Since the entire flags/id is copied, this works for string values too..
		/// This can also prepare an edge from another tray for use in this tray.
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public Edge ShallowCopyEdge(Edge e)
		{
			return new Edge(e.FlagsId, e.Mark == 0 ? 0 : Interlocked.Increment(ref last_mark_issued));
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// A system of incrementing ID numbers is used to ensure that re-uses of a stock TFS within the same unification
		/// operation do not lead to conflated coreferences between the instances, which must remain separate. This can
		/// happen when a large TFS uses, for example, more than one difference list (which has internal coreferencing).
		/// The target TFS has a fixed ID value.
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

		public TfsEdge CreateTfs(Type t, bool f_coref)
		{
			return new TfsEdge(Interlocked.Add(ref next_id, IdIncrement) | tix, CreateEdge(t, f_coref));
		}
		public TfsEdge CreateTfs(Edge e)
		{
			return new TfsEdge(Interlocked.Add(ref next_id, IdIncrement) | tix, e);
		}
		public TfsEdge CloneTfs(TfsEdge te)
		{
			Debug.Assert(!te.IsTarget);
			return new TfsEdge(Interlocked.Add(ref next_id, IdIncrement) | tix, te.Edge);
		}
		public TfsEdge WrapAsTargetTfs(Edge e)
		{
			return new TfsEdge(TargetId | tix, e);
		}
		public void ReleaseTfs(TfsEdge te)
		{
			/// this would be a place to do other housekeeping
			RudeTruncate(te.Edge);

			/// unregister the TFS name, if any
			String name;
			names.TryRemove(te, out name);
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public bool TryGetPool(String f, out ConstraintPool cp)
		{
			TypeMgr.FeatureInfo fi;
			if (!tm.feat_map.TryGetValue(f, out fi))
			{
				cp = null;
				return false;
			}
			cp = Pools[fi.i_feat];
			return true;
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public ConstraintPool this[String feat]
		{
			get
			{
				TypeMgr.FeatureInfo fi;
				return tm.feat_map.TryGetValue(feat, out fi) ? Pools[fi.i_feat] : null;
			}
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// 
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public int PoolMarkCount { get { return Pools.Sum(cp => cp.Count); } }

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// 
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

		ConstraintPool list_head = null;
		ConstraintPool ListHead { get { return list_head = list_head ?? Pools[tm.f_ix_list_head]; } }

		ConstraintPool list_tail = null;
		ConstraintPool ListTail { get { return list_tail = list_tail ?? Pools[tm.f_ix_list_tail]; } }

		ConstraintPool diff_list_list = null;
		ConstraintPool DiffListList { get { return diff_list_list = diff_list_list ?? Pools[tm.f_ix_dlist_list]; } }

		ConstraintPool diff_list_last = null;
		public ConstraintPool DiffListLast { get { return diff_list_last = diff_list_last ?? Pools[tm.f_ix_dlist_last]; } }

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public IEnumerable<Edge> GetListEdges(Edge e)
		{
			/// e.Type must unify down to tt_list_parent, but we don't need to check this separately because the ListHead pool 
			/// is only appropriate for types that are lists, so the Mark won't be found if e.Type is not a list.
			Edge lh_edge;
			while (ListHead.TryGetEdge(e.Mark, out lh_edge))
			{
				yield return lh_edge;

				if (!ListTail.TryGetEdge(e.Mark, out e) || e.Mark == 0)
					yield break;
			}
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public IEnumerable<ConstraintRef> GetListConstraintRefs(Edge e)
		{
			Edge lh_edge;
			while (ListHead.TryGetEdge(e.Mark, out lh_edge))
			{
				yield return new ConstraintRef(e, ListHead);

				if (!ListTail.TryGetEdge(e.Mark, out e))
					yield break;
			}
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public IEnumerable<ConstraintRef> GetDiffListLists(Edge e)
		{
			Edge ll_edge;
			if (!DiffListList.TryGetEdge(e.Mark, out ll_edge))
				yield break;
			foreach (ConstraintRef cr in GetListConstraintRefs(ll_edge))
				yield return cr;
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public bool GetTfsEdgeAtPath(Edge e_start, FsPath p, out TfsEdge te)
		{
			te = CreateTfs(e_start);
			foreach (String f in p)
			{
				if (te.Edge.Mark == 0)
					return false;
				int i_feat = tm.GetFeatureIndex(f);
				if (i_feat == -1 || !Pools[i_feat].TryGetEdge(te.Edge.Mark, out te.Edge))
					return false;
			}
			return true;
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// Similar to the above, but returns a ConstraintRef, which provides access to the next-to-last edge in the path, so
		/// that the end of the path can be manipulated.
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

		public bool GetEdgeAtPath(Edge e_start, FsPath p, out ConstraintRef cref)
		{
			if (p.Count == 0)
			{
				cref = default(ConstraintRef);
				return false;
			}
			Edge e = e_start;
			Edge e_prev;
			ConstraintPool cp;
			for (int i = 0; ; )
			{
				e_prev = e;
				int i_feat = tm.GetFeatureIndex(p[i]);
				if (i_feat == -1 || !(cp = Pools[i_feat]).TryGetEdge(e.Mark, out e))
				{
					cref = default(ConstraintRef);
					return false;
				}
				i++;
				if (i == p.Count)
				{
					cref = new ConstraintRef(e_prev, cp);
					return true;
				}
			}
		}

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

		sealed class PathLister : List<String>
		{
			Tray tr;
			TypeMgr tm;
			ConstraintPool[] Pools;
			Stack<String> stack = new Stack<String>();
			Dictionary<Edge, int> d = null;
			int coref_tag = 0;
			bool f_marks;
			HashSet<PoolMark> reachable = null;

			public PathLister(Tray tr, Edge e, String label, bool f_marks, HashSet<PoolMark> reachable = null)
			{
				this.tr = tr;
				this.tm = tr.tm;
				this.Pools = tr.Pools;
				this.f_marks = f_marks;
				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.IsCoreferenced)
				{
					int cre;
					if (d == null)
						d = new Dictionary<Edge, int> { { e, cre = coref_tag++ } };
					else if (!d.TryGetValue(e, out cre))
						d.Add(e, cre = coref_tag++);
					else
						f_descend = false;
					s += " #" + cre.ToString();
				}
#if DEBUG
				if (f_marks)
					s += "  (" + Edge.FormatMark(e) + ")";
#endif
				if (s_usage != null)
					s += " in-use by " + s_usage;

				this.Add(s);
				if (f_descend && e.IsConstrained)
				{
					/// 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.GetEdgeType(e.FlagsId)._deprec_feat_indexes)
					{
						Edge q;
						ConstraintPool cp = Pools[i_feat];
						String usage = null;
#if DEBUG
						if (reachable != null && reachable.Contains(new PoolMark(cp, e.Mark)))
							usage = tr.Roots.FindRootData(e.Mark).ToString();
#endif

						if (cp.TryGetEdge(e.Mark, out q))
						{
							stack.Push(cp.Feature.ToUpper());
							_list_paths(q, usage);
							stack.Pop();
						}
					}
				}
			}

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

		public int max_truncators = int.MaxValue;
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public void RudeTruncate(Edge e)
		{
			Debug.Assert((e.FlagsId & (Edge.Flag.Coreference | Edge.Flag.EtmNonBareType)) != 0 && e.Mark != 0);

			if (Nop.single_threaded || c_truncators >= max_truncators)
			{
				using (ThreadPriorityRegion q = new ThreadPriorityRegion(ThreadPriority.AboveNormal))
				{
					new RudeTruncator(this, e);
				}
			}
			else
			{
#if false
				rt_top_marks.UnionWith(PoolMarksBelow(e));
#else
				if (Interlocked.Increment(ref c_truncators) == 1)
					mre_truncate_ok.Reset();
				new Task(() =>
					 {
						 using (ThreadPriorityRegion q = new ThreadPriorityRegion(ThreadPriority.AboveNormal))
						 {
							 //var q = Thread.CurrentThread;
							 //ThreadPriority pri_prev = q.Priority;

							 /// add ourselves to a list which allows our thread to be discovered in case we are lagging 
							 /// too much in our work
							 //truncators.Add(q.Thread);

							 new RudeTruncator(this, e);

							 //truncators.Remove(q.Thread);

							 /// restore thread priority in case someone boosted us
							 //q.Priority = pri_prev;

							 if (Interlocked.Decrement(ref c_truncators) == 0)
								 mre_truncate_ok.Set();
						 }
					 }).Start();
#endif
			}
		}

		//public ConcurrentHashSet<Thread> truncators = new ConcurrentHashSet<Thread>();

		//public ConcurrentHashSet<int> rt_top_marks = new ConcurrentHashSet<int>();

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

			public RudeTruncator(Tray tr, Edge e)
			{
				this.tm = tr.tm;
				_rude_truncate(e);
			}

			void _rude_truncate(Edge e)
			{
				foreach (ConstraintPool cp in tm.rgcp_by_type[(int)(e.FlagsId & tm.MultiIdMask)])
				{
					Edge ne;
					if (cp.TryRemoveEdge(e.Mark, out ne))
					{
						bool f_descend = true;
						if ((ne.FlagsId & Edge.Flag.Coreference) != 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);
					}
				}
			}
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public IEnumerable<PoolMark> AllPoolMarks(Edge e)
		{
			foreach (int fix in tm.GetEdgeType(e.FlagsId)._deprec_feat_indexes)
				yield return new PoolMark(Pools[fix], e.Mark);
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public IEnumerable<ConstraintPool> ConstrainedPoolsOnly(Edge e)
		{
			if (!e.IsConstrained)
				yield break;
			foreach (int fix in tm.GetEdgeType(e.FlagsId)._deprec_feat_indexes)
			{
				ConstraintPool cp = Pools[fix];	// 'this[fix]' ?
				if (cp.ContainsInMark(e.Mark))
					yield return cp;
			}
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public IEnumerable<PoolMark> ConstrainedPoolMarksOnly(Edge e)
		{
			if (!e.IsConstrained)
				yield break;
			foreach (int fix in tm.GetEdgeType(e.FlagsId)._deprec_feat_indexes)
			{
				ConstraintPool cp = Pools[fix];
				if (cp.ContainsInMark(e.Mark))
					yield return new PoolMark(cp, e.Mark);
			}
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// Includes coreferences, of course
		/// Constrained means it is has at least one non-top or coreferenced feature. We count on the fact that such edges are 
		/// always vacant from the constraint pool
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public int ConstrainedFeaturesCount(Edge e)
		{
			int c = 0;
			if (e.IsConstrained)
			{
				foreach (int fix in tm.GetEdgeType(e.FlagsId)._deprec_feat_indexes)
					if (Pools[fix].ContainsInMark(e.Mark))
						c++;
			}
			return c;
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public HashSet<PoolMark> PoolMarksBelow(Edge edge)
		{
			return edge.IsConstrained ? new PoolMarkGatherer(this, edge) : PoolMark.EmptyPoolMarkHashSet;
		}

		sealed class PoolMarkGatherer : HashSet<PoolMark>
		{
			ConstraintPool[] Pools;
			TypeMgr tm;

			public PoolMarkGatherer(Tray tr, Edge e)
			{
				this.Pools = tr.Pools;
				this.tm = tr.tm;
				_gather(e);
			}

			void _gather(Edge e)
			{
				foreach (int fix in tm.GetEdgeType(e.FlagsId)._deprec_feat_indexes)
				{
					ConstraintPool cp;
					Edge next_edge;
					if ((cp = Pools[fix]).TryGetEdge(e.Mark, out next_edge))
					{
						PoolMark pm = new PoolMark(cp, e.Mark);
						if (!this.Contains(pm))
						{
							this.Add(pm);
							if (!tm.IsTopId(next_edge))
								_gather(next_edge);
						}
					}
				}
			}
		};

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#if false
		public HashSet<int> MarksBelow(Edge edge)
		{
			return edge.IsConstrained ? new MarkGatherer(this, edge) : MarkGatherer.Empty;
		}

		sealed class MarkGatherer : HashSet<int>
		{
			public static HashSet<int> Empty = new HashSet<int>();
			ConstraintPool[] Pools;
			TypeMgr tm;

			public MarkGatherer(Tray tr, Edge e)
			{
				this.Pools = tr.Pools;
				this.tm = tr.tm;
				_gather(e);
			}

			void _gather(Edge e)
			{
				foreach (int fix in tm.GetEdgeType(e.FlagsId)._deprec_feat_indexes)
				{
					ConstraintPool cp;
					Edge next_edge;
					if ((cp = Pools[fix]).TryGetEdge(e.Mark, out next_edge))
					{
						if (!this.Contains(next_edge.Mark))
						{
							this.Add(pm);
							if (!tm.IsTopId(next_edge))
								_gather(next_edge);
						}
					}
				}
			}

			public IEnumerator<int> GetEnumerator()
			{
				throw new NotImplementedException();
			}

			System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
			{
				throw new NotImplementedException();
			}
		};
#endif

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public bool AnyConstraints(Edge e)
		{
			if (e.IsConstrained)
			{
				foreach (int fix in tm.GetEdgeType(e.FlagsId)._deprec_feat_indexes)
					if (Pools[fix].ContainsInMark(e.Mark))
						return true;
			}
			return false;
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public IEnumerable<ConstraintRef> AllConstraintRefs(Edge e)
		{
			foreach (int fix in tm.GetEdgeType(e.FlagsId)._deprec_feat_indexes)
				yield return new ConstraintRef(e, Pools[fix]);
		}

		public IEnumerable<ConstraintRef> ConstrainedRefsOnly(Edge e)
		{
			if (!e.IsConstrained)
				yield break;
			foreach (int fix in tm.GetEdgeType(e.FlagsId)._deprec_feat_indexes)
			{
				ConstraintPool cp = Pools[fix];
				if (cp.ContainsInMark(e.Mark))
					yield return new ConstraintRef(e, Pools[fix]);
			}
		}
	};

}