Grammar Composition System

/src/branch/20110407-thread-priority/agree-sys/20-types-glb.cs

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

using glue.Collections.XSpinLock;
using glue.Collections.BitArray;
using glue.Extensions.Enumerable;
using glue;

#pragma warning disable 0649

namespace agree
{
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	///
	///
	///
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	public partial class TypeMgr
	{
		public const int GLB_CACHE_ENTRIES = 143483;	// a prime number

		public GlbCacheEntry[][] glb_cache = new GlbCacheEntry[GLB_CACHE_ENTRIES][];

		public Dictionary<BitArr, Type> code_dict;

		public struct GlbCacheEntry
		{
			public GlbCacheEntry(int k, Edge.Flag f)
			{
				this.k = k;
				this.f = f;
			}
			public int k;
			public Edge.Flag f;
		};

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		///
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		void UpdateGlbCacheBareTypes()
		{
			foreach (GlbCacheEntry[] rge in glb_cache)
				if (rge != null)
					for (int i = 0; i < rge.Length; i++)
						if (!type_arr[(int)(rge[i].f & MultiIdMask)].IsBare)
							rge[i].f |= Edge.Flag.EtmNonBareType;
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		///
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		void AddGlb(int id1, int id2, Edge.Flag f)
		{
			Debug.Assert(c_t_bits != -1);
			Debug.Assert(id1 != 0 && id2 != 0 && id1 != id2);

			int k, hash = (k = id1 > id2 ? (id2 << c_t_bits) + id1 : (id1 << c_t_bits) + id2) % GLB_CACHE_ENTRIES;
			GlbCacheEntry gce = new GlbCacheEntry(k, f);
			GlbCacheEntry[] rge = glb_cache[hash];

			/// atomic publishing. don't care about rare case of lost entries due to (CPU) cache incoherence
			glb_cache[hash] = rge == null ? new GlbCacheEntry[] { gce } : rge.Append(gce).OrderBy(g => g.k).ToArray();
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public bool ComputeAndCacheGlb(int id1, int id2, out Edge.Flag glb_id)
		{
			Type t_glb;
			if (!code_dict.TryGetValue(type_arr[id1].m_code & type_arr[id2].m_code, out t_glb))
			{
				glb_id = Edge.Flag.CachedBottom;
				//System.Threading.Tasks.Task.Factory.StartNew(() =>
				//{
				//    foreach (Type c in t1.AllDescendants)
				//        AddGlb(id2, c.m_id, BottomId);
				//    foreach (Type c in t2.AllDescendants)
				//        AddGlb(id1, c.m_id, BottomId);
				//});
				AddGlb(id1, id2, glb_id);
				return false;
			}
			else
			{
				if (t_glb == StringType)
					glb_id = Edge.Flag.EtmString;
				else
				{
					glb_id = (Edge.Flag)t_glb.m_id;
					if (!t_glb.IsBare)
						glb_id |= Edge.Flag.EtmNonBareType;
				}
				AddGlb(id1, id2, glb_id);
				Debug.Assert(GetEdgeType(glb_id).IsBare == ((glb_id & Edge.Flag.EtmNonBareType) == 0));
				return true;
			}
		}


		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public int GetGlbCheckTopAndIdentity(int id1, int id2)
		{
			if (id1 == 0 || id1 == id2)
			{
				return id2;
			}
			if (id2 == 0)
			{
				return id1;
			}
			Edge.Flag glb_id;
			int k = id1 > id2 ? (id2 << c_t_bits) + id1 : (id1 << c_t_bits) + id2;
			GlbCacheEntry[] rge = glb_cache[k % GLB_CACHE_ENTRIES];
			if (rge != null)
			{
				int gk, i = 0;
				do
				{
					GlbCacheEntry gce = rge[i];
					if ((gk = gce.k) == k)
					{
						glb_id = gce.f;
						goto found;
					}
				}
				while (gk < k && ++i < rge.Length);
			}
			if (!ComputeAndCacheGlb(id1, id2, out glb_id))
				return -1;
		found:
			if ((glb_id & Edge.Flag.EtmString) != 0)
				return StringId;
			return (int)(glb_id & MultiIdMask);
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public bool GetGlbFeatureConfig(Edge.Flag f1, Edge.Flag f2, out Edge.Flag glb_id)
		{
			Debug.Assert(fcix_by_type != null);

			int id1 = (f1 & Edge.Flag.EtmString) != 0 ? StringId : (int)(f1 & MultiIdMask);
			int id2 = (f2 & Edge.Flag.EtmString) != 0 ? StringId : (int)(f2 & MultiIdMask);

			Debug.Assert(id1 != id2 && id1 != 0 && id2 != 0);

			int k = id1 > id2 ? (id2 << c_t_bits) + id1 : (id1 << c_t_bits) + id2;
			GlbCacheEntry[] rge = glb_cache[k % GLB_CACHE_ENTRIES];
			if (rge != null)
			{
				int gk, i = 0;
				do
				{
					GlbCacheEntry gce = rge[i];
					if ((gk = gce.k) == k)
						return (glb_id = gce.f) != Edge.Flag.CachedBottom;
				}
				while (gk < k && ++i < rge.Length);
			}
			return ComputeAndCacheGlb(id1, id2, out glb_id);
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public bool CanUnify(int id1, int id2)
		{
			//Debug.Assert(id1 != BottomId && id2 != BottomId);

			if (id1 == 0 || id2 == 0 || id1 == id2)
				return true;

			Edge.Flag glb_id;
			int k = id1 > id2 ? (id2 << c_t_bits) + id1 : (id1 << c_t_bits) + id2;
			GlbCacheEntry[] rge = glb_cache[k % GLB_CACHE_ENTRIES];
			if (rge != null)
			{
				int gk, i = 0;
				do
				{
					GlbCacheEntry gce = rge[i];
					if ((gk = gce.k) == k)
						return gce.f != Edge.Flag.CachedBottom;
				}
				while (gk < k && ++i < rge.Length);
			}
			return ComputeAndCacheGlb(id1, id2, out glb_id);
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public bool CanUnify(Edge.Flag f1, Edge.Flag f2)
		{
			int id1 = (int)(f1 & MultiIdMask);
			int id2 = (int)(f2 & MultiIdMask);

			if ((f1 & Edge.Flag.EtmMask) == Edge.Flag.EtmString)
			{
				if ((f2 & Edge.Flag.EtmMask) == Edge.Flag.EtmString)
					return id1 == id2;
				id1 = StringId;
			}
			else if ((f2 & Edge.Flag.EtmMask) == Edge.Flag.EtmString)
				id2 = StringId;
			else if (id1 == 0 || id2 == 0 || id1 == id2)
				return true;

			Edge.Flag glb_id;
			int k = id1 > id2 ? (id2 << c_t_bits) + id1 : (id1 << c_t_bits) + id2;
			GlbCacheEntry[] rge = glb_cache[k % GLB_CACHE_ENTRIES];
			if (rge != null)
			{
				int gk, i = 0;
				do
				{
					GlbCacheEntry gce = rge[i];
					if ((gk = gce.k) == k)
						return gce.f != Edge.Flag.CachedBottom;
				}
				while (gk < k && ++i < rge.Length);
			}
			return ComputeAndCacheGlb(id1, id2, out glb_id);
		}


		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// Works correctly for string values, hence the boolean return value
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public bool GetGlbCheckStr(Edge.Flag f1, Edge.Flag f2, out int id_out)
		{
			int id1 = (int)(f1 & MultiIdMask);
			int id2 = (int)(f2 & MultiIdMask);

			if ((f1 & Edge.Flag.EtmMask) == Edge.Flag.EtmString)
			{
				if ((f2 & Edge.Flag.EtmMask) == Edge.Flag.EtmString)
				{
					id_out = StringId;
					return id1 == id2;
				}
				id1 = StringId;
			}
			else if ((f2 & Edge.Flag.EtmMask) == Edge.Flag.EtmString)
				id2 = StringId;
			else if (id1 == id2)
			{
				id_out = id1;
				return id_out != (int)MultiIdMask;
			}

			if (id1 == 0)
			{
				id_out = id2;
				return true;
			}
			else if (id2 == 0)
			{
				id_out = id1;
				return true;
			}
			Edge.Flag glb_id;
			int k = id1 > id2 ? (id2 << c_t_bits) + id1 : (id1 << c_t_bits) + id2;
			GlbCacheEntry[] rge = glb_cache[k % GLB_CACHE_ENTRIES];
			if (rge != null)
			{
				int gk, i = 0;
				do
				{
					GlbCacheEntry gce = rge[i];
					if ((gk = gce.k) == k)
					{
						glb_id = gce.f;
						break;
					}
				}
				while (gk < k && ++i < rge.Length);
			}
			if (!ComputeAndCacheGlb(id1, id2, out glb_id))
				Debugger.Break();
			id_out = (int)(glb_id & MultiIdMask);
			return glb_id != Edge.Flag.CachedBottom;
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		///
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public Type GlbOfMany(IEnumerable<ConstraintPool> iecp)
		{
			return GetGlbOfMany(iecp.Select(cp => cp.IntroducedBy));
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// Consider other options for highly spun code
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public Type GetGlbOfMany(IEnumerable<Type> _ie)
		{
			using (IEnumerator<Type> ie = _ie.GetEnumerator())
			{
				if (!ie.MoveNext())
					return null;
				int tid = ie.Current.m_id;
				while (ie.MoveNext())
					if ((tid = GetGlbCheckTopAndIdentity(tid, ie.Current.m_id)) == -1)
						return null;
				return type_arr[tid];
			}
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		///
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public String GlbCacheInfo()
		{
			int c = 0;
			int min = int.MaxValue;
			int max = int.MinValue;
			foreach (TypeMgr.GlbCacheEntry[] rge in g.tm.glb_cache)
				if (rge != null)
				{
					int l = rge.Length;
					c += l;
					if (l < min)
						min = l;
					if (l > max)
						max = l;
				}

			return String.Format("glb-cache: slots: {0}  tot: {1}  min {2} max {3} avg {4}",
				GLB_CACHE_ENTRIES, c, min, max, (double)c / GLB_CACHE_ENTRIES);
		}
	};
}