Grammar Composition System

/src/agree-sys/69-chart-edge-derived.cs

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

using miew.ReadOnly;
using miew.Enumerable;
using miew.Debugging;
using miew.BitArray;

namespace agree
{
	public abstract partial class PassiveEdge : ArrayTfs, IParseObj
	{
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// </summary>
		/// <remarks>
		/// initial lexical edges are now directly (polymorphically) introduced into the chart as AnalysisStack objects via 
		/// their implementation of the IParseObj interface
		/// </remarks>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		[DebuggerDisplay("{ToString(),nq}")]
		public partial class Derived : PassiveEdge
		{
			[DebuggerBrowsable(DebuggerBrowsableState.Never)]
			ParseObjs rgo;

			public Derived(ParseControl ctrl, GrammarRule rule, Tfs tfs, ref ParseObjs rgo)
				: base(ctrl, rgo.Span, rule, tfs)
			{
				this.rgo = rgo;
		//		this.m_dseq = -1;

				ctrl.stats.Parsing.Chart.PassiveEdge();
			}

//			public int m_dseq;

	//		public static int qc = 0;

#if false
			public void DirectCancel()
			{
				int _tmp = ctrl.chart.g_dseq;
				if (Interlocked.Exchange(ref m_dseq, _tmp) == _tmp)
					return;

				for (int j = 0; j < rgo.Count; j++)
				{
					Derived dtr = rgo[j] as Derived;
					if (dtr != null)
					{
						if (dtr.IsHold())
							dtr.DirectCancel();
						else if (!dtr.IsRemove())
							continue;
						this.s_state = SequenceControl.REMOVE;
						Interlocked.Increment(ref qc);
						break;
					}
				}
			}
#endif

			public ParseObjs ChartDaughters { get { return rgo; } }

			[DebuggerBrowsable(DebuggerBrowsableState.Never)]
			public IEnumerable<IParseObj> Descendants
			{
				get
				{
					Derived dpe;
					foreach (IParseObj ipce in rgo)
					{
						yield return ipce;
						if ((dpe = ipce as Derived) != null)
							foreach (IParseObj ipce_d in dpe.Descendants)
								yield return ipce_d;
					}
				}
			}

			[DebuggerBrowsable(DebuggerBrowsableState.Never)]
			public IEnumerable<IParseObj> DescendantsAndSelf
			{
				get
				{
					yield return this;
					foreach (IParseObj ipce in Descendants)
						yield return ipce;
				}
			}

			/// <summary>
			/// when initiated with 'i_arg==0', enumerates the fixed-arity cross product of the packed trees 
			/// across each of this edge's chart daughters
			/// </summary>
			IEnumerable<IEnumerable<IDerivation>> _rightwards(int i_arg)
			{
				Debug.Assert(!this.IsRemove());
				IParseObj unary = rgo[i_arg];
				Debug.Assert(unary.IsActive());

				foreach (var d in unary.Derivations)
				{
					if (i_arg == rgo.Count - 1)
						yield return new IDerivation[] { d };
					else
					{
						IParseObj po = rgo[i_arg + 1];
						if (po.IsActive())
							foreach (var tree_xp in _rightwards(i_arg + 1))
								yield return tree_xp.Prepend(d);
					}
				}
			}

			[DebuggerBrowsable(DebuggerBrowsableState.Never)]
			IEnumerable<IDerivation> _packed_trees
			{
				get
				{
					Debug.Assert(!this.IsRemove());

					/// trees postulated by the cross product of this item's daughters...
					if (rgo[0].IsActive())
					{
						if (rgo.Count == 1)
							foreach (var e in rgo[0].Derivations)
								yield return new ParseTree(this.ctrl, this, new IDerivation[] { e });
						else
							foreach (var e in _rightwards(0))
								yield return new ParseTree(this.ctrl, this, e);
					}

					/// ...plus subsumed structures packed into this item itself (and their subsumptions...)
					if (this.IsActive())
						foreach (var e in _peer_packed())
							yield return e;
				}
			}

			static public readonly IDerivation[] NoDerivations = new IDerivation[0];

			/// <summary>
			/// exhaustive unpacking of trees which are packed into this item with thread-safe cache
			/// </summary>
			[DebuggerBrowsable(DebuggerBrowsableState.Never)]
			IDerivation[] _parse_trees = null;
			[DebuggerBrowsable(DebuggerBrowsableState.Never)]
			public override IList<IDerivation> Derivations
			{
				get
				{
					Debug.Assert(!this.IsRemove());
					Debug.Assert(ctrl.f_parse_phase_complete);

					IDerivation[] _tmp;
					return _parse_trees ??
							Interlocked.CompareExchange(ref _parse_trees, _tmp = _packed_trees.ToArray(), null) ??
							_tmp;
				}
			}

			///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
			/// <summary>
			/// 
			/// </summary>
			///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
			public override string ToString()
			{
				return String.Format("{0} {1}", TokenSpan, base.ToString());
			}
		};

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// a derived passive chart edge which has been matched against one or more start symbols
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public class Completed : Derived
		{
			static bool[][] singleton_maps;

			static bool[] GetSingletonMap(ParseControl ctrl, int i_ss)
			{
				if (singleton_maps == null)
					Interlocked.CompareExchange(ref singleton_maps, new bool[ctrl.g.StartSymbols.Length][], null);

				bool[] _tmp = singleton_maps[i_ss];
				if (_tmp == null)
				{
					_tmp = new bool[i_ss + 1];
					_tmp[i_ss] = true;
					singleton_maps[i_ss] = _tmp;
				}
				return _tmp;
			}

			readonly bool[] start_symbol_map;

			public Completed(ParseControl ctrl,
									GrammarRule rule,
									Tfs tfs,
									bool[] rgss_map,
									ref ParseObjs rgo)
				: base(ctrl, rule, tfs, ref rgo)
			{
				this.start_symbol_map = rgss_map;
				ctrl.chart._completed_edges.Add(this);
				ctrl.stats.Parsing.Chart.RootEdge();
			}

			public Completed(ParseControl ctrl,
									GrammarRule rule,
									Tfs tfs,
									int i_ss,
									ref ParseObjs rgo)
				: this(ctrl, rule, tfs, GetSingletonMap(ctrl, i_ss), ref rgo)
			{
			}

			public bool[] MatchedStartSymbolsMap { get { return start_symbol_map; } }

			public IEnumerable<StartSymbol> MatchedStartSymbols
			{
				get
				{
					for (int i = 0; i < start_symbol_map.Length; i++)
						if (start_symbol_map[i])
							yield return ctrl.g.StartSymbols[i];
				}
			}

			public new String SysObjName
			{
				get { return String.Format("parse{0}", i_seq >> 1); }
			}

			public new ISysObj SysObjParent
			{
				get { return ctrl; }
			}

			public new IReadOnlyDictionary<string, ISysObj> SysObjChildren
			{
				get { return SysObjHelper<ISysObj>.Empty; }
			}

			//public string SysObjDescription
			//{
			//    get { return String.Format("{0} ({1})", License != null ? License.SysObjName : "null license", start_symbol.SysObjName); }
			//}
		}
	};
}