Grammar Composition System

/src/agree-sys/60-chart.cs

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

using miew.ReadOnly;
using miew.Tokenization;
using miew.Concurrency;
using miew.Enumerable;

namespace agree
{
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	/// <summary>
	/// 
	/// </summary>
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	abstract public unsafe partial class ChartBase : ISysObj, IEnumerable<IParseObj>
	{
		static int next_chart_id = 0;

		readonly public ParseControl ctrl;
		readonly int chart_id;
		readonly protected int c_columns;
		protected ChartCell[][] chart;
		Span entire_span;

		//public int g_dseq = 1;

		/// a global interlocking sequence between the edge subscription mechanism (used by active edges) and the chart cell
		/// contents (passive edges). Valid sequence numbers are even numbers; a non-zero LSB indicates that (id-1)
		/// has been claimed and is in the process of being inserted into the respective list, which should be a short
		/// enough duration to spin-wait on.
		int next_edge_id = 2;

		public void StampSequence(IAtomicSequence obj)
		{
			while (true)
			{
				int ci = next_edge_id;
				if ((ci & 1) == 0 && Interlocked.CompareExchange(ref next_edge_id, ci + 1, ci) == ci)
				{
					obj.SetSequenceId(ci);
					/// can rely on the _next_ CMPXCHG of the global sequence counter to ensure that the write we just
					/// did to the object is flushed prior to the possibility of that next counter value being issued and
					/// published. Hence a full fence right here should not be required.
					next_edge_id = ci + 2;
					obj.SetStateNew();
					return;
				}
			}
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		internal ChartBase(ParseControl ctrl)
		{
			this.c_columns = ctrl.la.ChartSize;
			if (c_columns == 0)
			{
				Exception ex_inner = new ArgumentException("Parse chart cannot have zero columns", "c_columns");
				throw new TypeInitializationException(this.GetType().FullName, ex_inner);
			}

			this.ctrl = ctrl;
			this.chart_id = Interlocked.Increment(ref next_chart_id);
			this.entire_span = new Span(0, (uint)c_columns);

			this.chart = new ChartCell[c_columns][];
			for (int i = 0; i < c_columns; i++)
			{
				ChartCell[] cc = chart[i] = new ChartCell[c_columns - i];
				for (int j = 0; j < c_columns - i; j++)
					cc[j] = new ChartCell(this);
			}
		}

		public void ReleaseChart()
		{
			this.chart = null;
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public ChartCell this[Span span]
		{
			get { return chart[span.StartIndex][span.Length - 1]; }
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		//public IEnumerable<IParseObj> GetCellEdges(int i_col, int c_span)
		//{
		//    return chart[i_col][c_span - 1];
		//}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public int ColumnCount { get { return c_columns; } }

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public Span EntireSpan { get { return entire_span; } }

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public String InputText { get { return ctrl.InputText; } }

		internal ConcurrentList<PassiveEdge.Completed> _completed_edges = new ConcurrentList<PassiveEdge.Completed>();
		public IEnumerable<PassiveEdge.Completed> CompletedEdges
		{
			get
			{
				if (ctrl.parser_config.packing == Config.Parser.PackingOpts.None)
					return _completed_edges;
				return _completed_edges.Where(p =>
					{
						int q = p.State;
						if ((q & SequenceControl.stb_Hold) > 0)
							throw new Exception();
						if (q == SequenceControl.ACTIVE)
							return true;
						return false;
					});
			}
		}

		IReadOnlyDictionary<String, ISysObj> _completed_parses_dict = null;
		public IReadOnlyDictionary<String, ISysObj> SysObjChildren
		{
			get
			{
				if (_completed_parses_dict == null)
					_completed_parses_dict = _completed_edges.ToReadOnlyDictionary(p => p.SysObjName, p => (ISysObj)p);
				return _completed_parses_dict;
			}
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// enumerator for all edges in the chart. this is also the type of enumerator for the chart itself.
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

		public IEnumerator<IParseObj> GetEnumerator() { return new ChartCell._enum_all_edges(this); }

		IEnumerator IEnumerable.GetEnumerator() { return new ChartCell._enum_all_edges(this); }

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// each cell of the chart is a concurrent list of objects which implement the IParseObj interface
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public sealed class ChartCell : IEnumerable<IParseObj>
		{
			IParseObj m_first = null;
			IParseObj m_last = null;
			ChartBase m_cb;

			public ChartCell(ChartBase cb)
			{
				m_cb = cb;
			}

			public void Add(IParseObj po)
			{
				Debug.Assert(po.State == default(byte));
				po.SetStateRaw(SequenceControl.PENDING);

				if (m_first != null || Interlocked.CompareExchange(ref m_first, po, null) != null)
				{
					IParseObj ml = m_last ?? m_first;
					while (ml.Next != null || !ml.TrySetTail(po))
						ml = ml.Next;
					m_last = ml;
				}
				m_cb.StampSequence(po);
			}

			public struct _enum : IEnumerator<IParseObj>
			{
				ChartCell cc;
				IParseObj po;

				public _enum(ChartCell cc)
				{
					this.cc = cc;
					this.po = null;
				}

				public bool MoveNext()
				{
					return (po = po == null ? cc.m_first : po.Next) != null;
				}

				public void Reset() { this.po = null; }
				public IParseObj Current
				{
					get { return po; }
					set { po = value; }
				}
				object IEnumerator.Current { get { return po; } }
				public void Dispose() { }
			};

			public struct _enum_all_edges : IEnumerator<IParseObj>
			{
				ChartBase cb;
				IParseObj po;
				int i_col, i_span;

				public _enum_all_edges(ChartBase cb)
				{
					Debug.Assert(cb.ctrl.f_parse_phase_complete);
					this.cb = cb;
					this.po = null;
					this.i_col = this.i_span = 0;
				}

				public void Reset()
				{
					i_col = i_span = 0;
					po = null;
				}

				public bool MoveNext()
				{
					while (true)
					{
						while ((po = po == null ? cb.chart[i_col][i_span].m_first : po.Next) != null)
							if (po.IsActive())
								return true;

						if (++i_span >= cb.c_columns - i_col)
						{
							if (++i_col >= cb.c_columns)
								return false;
							i_span = 0;
						}
					}
				}

				public IParseObj Current { get { return po; } }
				object IEnumerator.Current { get { return Current; } }
				public void Dispose() { }
			};


			public struct _multi_cell_enum : IEnumerator<IParseObj>
			{
				int i, i_incr, j, j_incr;
				ChartCell cc;
				IParseObj po;
				ChartCell[][] rgcc;

				public _multi_cell_enum(ChartBase chart, int i_min, int i_incr, int j_min, int j_incr)
				{
					this.i = i_min;
					this.i_incr = i_incr;
					this.j = j_min;
					this.j_incr = j_incr;
					this.rgcc = chart.chart;
					this.cc = rgcc[i][j];
					this.po = null;
				}

				public bool MoveNext()
				{
					while ((po = po == null ? cc.m_first : po.Next) == null)
					{
						if ((j += j_incr) < 0 || (i += i_incr) < 0 || i >= rgcc.Length)
						{
							this.rgcc = null;
							return false;
						}
						ChartCell[] arr = rgcc[i];
						if (j >= arr.Length)
						{
							this.rgcc = null;
							return false;
						}
						cc = arr[j];
						po = null;
					}
					return true;
				}

				public IParseObj Current { get { return po; } }
				object IEnumerator.Current { get { return po; } }
				public void Reset() { throw new NotImplementedException(); }
				public void Dispose() { }
			};

			public IEnumerator<IParseObj> GetEnumerator() { return new _enum(this); }
			IEnumerator IEnumerable.GetEnumerator() { return new _enum(this); }
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

		public String SysObjName
		{
			get { return String.Format("pc{0}", chart_id); }
		}

		public string SysObjDescription
		{
			get { return InputText ?? SysObjName; }
		}

		public ISysObj SysObjParent
		{
			get { return ctrl.g; }
		}
	};
}