Grammar Composition System

/src/branch/20110407-thread-priority/agree-sys/parser/chart-base.cs

using System;
using System.Diagnostics;
using System.IO;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Linq;
using System.Threading;
using System.Threading.Tasks;

using glue.Collections.XSpinLock;
using glue.Collections.ReadOnly;
using glue.Tokenization;

namespace agree.Parse
{
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	/// <summary>
	/// 
	/// </summary>
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	abstract public partial class ChartBase : ISysObj
	{
		static int i_next_id = 0;

		readonly protected ParserConfiguration config;
		readonly ISysObj so_owner;
		readonly int id;
		readonly int c_columns;
		readonly AtomicSequenceList<IParseChartEdge>[][] chart;
		readonly Span entire_span;
		readonly String source_text;
		AtomicSequencer ast = new AtomicSequencer();

		internal AtomicSequencer AtomicStamp { get { return ast; } }

		static public ParseChart active_chart = null; // temp
		public int manual_gcs = 0; // temp

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		internal ChartBase(ParserConfiguration config, ISysObj so_owner, String source_text, int c_columns)
		{
			active_chart = this as ParseChart;	// temp

			this.config = config;
			this.so_owner = so_owner;
			this.source_text = source_text;
			this.id = Interlocked.Increment(ref i_next_id);
			if (c_columns == 0)
			{
				Exception ex_inner = new ArgumentException("Value cannot be zero", "c_columns");
				throw new TypeInitializationException(this.GetType().FullName, ex_inner);
			}
			this.c_columns = c_columns;
			this.entire_span = new Span(0, (uint)c_columns);
			this.chart = new AtomicSequenceList<IParseChartEdge>[c_columns][];

			for (int i = 0; i < c_columns; i++)
				this.chart[i] = new AtomicSequenceList<IParseChartEdge>[c_columns - i];
		}

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

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

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public String SourceText { get { return source_text; } }

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// insertion of the interlocking list upon first use is lock-free
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		internal void AddEdge(IParseChartEdge e)
		{
			AtomicSequenceList<IParseChartEdge> lce = chart[e.ChartSpan.StartIndex][e.ChartSpan.Length - 1];
			if (lce == null)
			{
				lce = new AtomicSequenceList<IParseChartEdge>(ast);
				lce = Interlocked.CompareExchange(ref chart[e.ChartSpan.StartIndex][e.ChartSpan.Length - 1], lce, null) ?? lce;
			}
#if false && DEBUG
			T nc = e.Contents;
			if (lce.EnumerateSeq(int.MaxValue).Count(pe => pe.Contents.SpinCompare(nc)) > 2000)
			{
				String msg = String.Format("spin limit exceeded for '{0}' in span {1}", e.Contents, e.Span);
				throw new Exception(msg);
			}
#endif
			lce.Add(e);
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// Edges which end <b>at</b> the given zero-based column index
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		protected IEnumerable<IParseChartEdge> GetLeftAlignedEdges(int i_col, uint i_seq)
		{
			AtomicSequenceList<IParseChartEdge> lce;
			for (int i = 0, j = i_col; j >= 0; j--)
				if ((lce = chart[i++][j]) != null)
					foreach (IParseChartEdge ce in lce.EnumerateSeq(i_seq))
						yield return ce;
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// Edges which start <b>at</b> the given zero-based column index
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		protected IEnumerable<IParseChartEdge> GetRightAlignedEdges(int i_col, uint i_seq)
		{
			AtomicSequenceList<IParseChartEdge> lce;
			for (int span = 1; span <= c_columns - i_col; span++)
				if ((lce = chart[i_col][span - 1]) != null)
					foreach (IParseChartEdge ce in lce.EnumerateSeq(i_seq))
						yield return ce;
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		protected int GetEmptyColumnIndex()
		{
			for (int i = 0; i < c_columns; i++)
				if (!GetRightAlignedEdges(i, int.MaxValue).Any() && !GetLeftAlignedEdges(i, int.MaxValue).Any())
					return i;
			return -1;
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public IEnumerable<IParseChartEdge> AllEdges(uint i_seq = uint.MaxValue)
		{
			AtomicSequenceList<IParseChartEdge> lce;
			for (int i_col = 0; i_col < c_columns; i_col++)
				for (int span = 1; span <= c_columns - i_col; span++)
					if ((lce = chart[i_col][span - 1]) != null)
						foreach (IParseChartEdge ce in lce.EnumerateSeq(i_seq))
							yield return ce;
		}

		public IEnumerable<DerivedPassiveEdge> AllDerivedEdges(uint i_seq = uint.MaxValue)
		{
			return AllEdges(i_seq).OfType<DerivedPassiveEdge>();
		}

		internal IEnumerable<DerivedPassiveEdge> OrphanEdges(uint i_seq)
		{
			var ade = AllDerivedEdges(i_seq);
			return ade.Except(ade.SelectMany(dce => dce.Daughters.OfType<DerivedPassiveEdge>()));
		}

		public IEnumerable<DerivedPassiveEdge> DerivationTopEdges(uint i_seq = uint.MaxValue)
		{
			return OrphanEdges(i_seq).OfType<DerivedPassiveEdge>();
		}

		public IEnumerable<DerivedPassiveEdge> SpanningDerivedEdges()
		{
			return AllDerivedEdges(ast.InertValue).Where(dce => dce.ChartSpan == EntireSpan);
		}

		SysObjHelper<CompletedParse> completed_parses = null;

		internal SysObjHelper<CompletedParse> CompletedParsesKeyedCollection
		{
			get
			{
				SysObjHelper<CompletedParse> d = completed_parses;
				if (d == null)
				{
					AtomicSequenceList<IParseChartEdge> lce = chart[0][c_columns - 1];
					if (lce == null)
						d = SysObjHelper<CompletedParse>.Empty;
					else
					{
						d = new SysObjHelper<CompletedParse>();
						int i = 0;
						foreach (var x in lce.EnumerateSeq(uint.MaxValue).OfType<CompletedParse>())
						{
							x.ix = i++;
							d.Add(x);
						}
					}
					d = Interlocked.CompareExchange(ref completed_parses, d, null) ?? d;
				}
				return d;
			}
		}

		public ICollection<CompletedParse> CompletedParses
		{
			get { return CompletedParsesKeyedCollection; }
		}

		public IReadOnlyDictionary<String, ISysObj> SysObjChildren
		{
			get { return CompletedParsesKeyedCollection; }
		}

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

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

		public ISysObj SysObjParent
		{
			get { return so_owner; }
		}
	};
}