Grammar Composition System

/src/branch/20110407-thread-priority/agree-parse/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
{
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	/// <summary>
	/// 
	/// </summary>
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	public interface ISysObj
	{
		String SysObjName { get; }

		String SysObjDescription { get; }

		IReadOnlyDictionary<String, ISysObj> SysObjChildren { get; }

		ISysObj SysObjParent { get; }
	};

	public class SysObjHelper<T> : KeyedCollection<String, T>, IReadOnlyDictionary<String, ISysObj> where T : class, ISysObj
	{
		public SysObjHelper()
			: base(StringComparer.OrdinalIgnoreCase)
		{
		}

		public static IEnumerable<ISysObj> GetNamePrefixMatches(ISysObj sys_obj, String s_pfx)
		{
			if (s_pfx == "*")
				s_pfx = "";
			foreach (var kvp in sys_obj.SysObjChildren)
			{
				Debug.Assert(kvp.Value.SysObjName == kvp.Key);
				if (kvp.Key.StartsWith(s_pfx))
					yield return kvp.Value;
			}
		}

		static Dictionary<String, T> _ed = null;
		static SysObjHelper<T> _empty = null;
		static public SysObjHelper<T> Empty
		{
			get { return _empty = _empty ?? new SysObjHelper<T>(); }
		}

		protected override String GetKeyForItem(T item)
		{
			return item.SysObjName;
		}

		public new IDictionary<String, T> Dictionary
		{
			get
			{
				if (base.Dictionary == null)
					return _ed = _ed ?? new Dictionary<String, T>();
				return base.Dictionary;
			}
		}

		bool IReadOnlyDictionary<String, ISysObj>.ContainsKey(String key)
		{
			if (base.Dictionary == null)
				return false;
			return base.Dictionary.ContainsKey(key);
		}

		ICollection<String> IReadOnlyDictionary<String, ISysObj>.Keys
		{
			get { return base.Dictionary.Keys; }
		}

		ICollection<ISysObj> IReadOnlyDictionary<String, ISysObj>.Values
		{
			get { return ((IEnumerable<T>)this).Cast<ISysObj>().ToArray(); }
		}

		bool IReadOnlyDictionary<String, ISysObj>.TryGetValue(String key, out ISysObj value)
		{
			T v;
			if (base.Dictionary == null || !base.Dictionary.TryGetValue(key, out v))
			{
				value = null;
				return false;
			}
			value = v;
			return true;
		}

		ISysObj IReadOnlyDictionary<String, ISysObj>.this[String key]
		{
			get
			{
				if (base.Dictionary == null)
					throw new KeyNotFoundException();
				return base.Dictionary[key];
			}
		}

		bool IReadOnlyDictionary<String, ISysObj>.IsReadOnly
		{
			get { return true; }
		}

		int IReadOnlyDictionary<String, ISysObj>.Count
		{
			get { return base.Count; }
		}

		IEnumerator<KeyValuePair<String, ISysObj>> IEnumerable<KeyValuePair<String, ISysObj>>.GetEnumerator()
		{
			if (base.Dictionary == null)
				yield break;
			foreach (var kvp in base.Dictionary)
				yield return new KeyValuePair<String, ISysObj>(kvp.Key, kvp.Value);
		}

		System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
		{
			return GetEnumerator();
		}
	}
}

namespace agree.Parse
{
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	/// <summary>
	/// 
	/// </summary>
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	abstract public partial class ChartBase<T> : ISysObj where T : ChartBase<T>.IMotherDaughter, IEquatable<T>
	{
		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; } }

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		internal ChartBase(ParserConfiguration config, ISysObj so_owner, String source_text, int c_columns)
		{
			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; }
		}
	};
}