Grammar Composition System

/src/agree-sys/70-parse-quick-check.cs

//#define DUMP
//#define CIL
//#define DEREFERENCE_VTABLE

#if DEREFERENCE_VTABLE && !CIL
#error 'DEREFERENCE_VTABLE' requires 'CIL'
#endif

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Reflection;
using System.Reflection.Emit;
using System.Threading.Tasks;
using System.Threading;
using System.Runtime.InteropServices;

using miew.Debugging;
using miew.Enumerable;
using miew.Tokenization;

using SysType = System.Type;

namespace agree
{
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	/// <summary>
	/// Planning a quick-check strategy in advance preserves a specified order for checking (the ends of) multiple 
	/// quick-check paths, yet without unneccesarily re-traversing any part of the TFS.
	/// </summary>
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	public sealed class QuickCheckStrategy
	{
		static readonly Char[] dot_space = { '.', ' ' };
		static readonly Char[] outer_trim = { '\"', '\'', '(', ')', '[', ']' };

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// opcodes for the quick-check strategy steps
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public enum Op
		{
			Top = 1,
			Feature = 2,
			Check = 3,
			ContinueFrom = 4,
		};

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// a step in a quick-check strategy
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		[DebuggerDisplay("{ToString(),nq}")]
		public struct Entry
		{
			public Entry(Op op, int arg)
			{
				this.op = op;
				this.arg = arg;
				this.next_section = 0;
				this.ix_slot = 0;
			}
			public Entry(Op op, int arg, int next_section, int ix_slot)
			{
				this.op = op;
				this.arg = arg;
				this.next_section = next_section;
				this.ix_slot = ix_slot;
			}
			public Op op;
			public int arg;
			public int next_section;
			public int ix_slot;

#if DEBUG
			public override string ToString()
			{
				String s = String.Format("{0,6} -> {1:0000}", ix_slot == -1 ? "" : "[" + ix_slot.ToString("0000") + "]", next_section);
				switch (op)
				{
					case Op.ContinueFrom:
						s += String.Format("{0,13} {1:0000}", op, arg);
						break;
					case Op.Top:
					case Op.Check:
						s += String.Format("{0,13}", op);
						break;
					case Op.Feature:
						s += String.Format("{0,13} {1,4} ({2})",
							op,
							arg,
							Grammar._singleton.tm.feat_arr[arg].feature.ToUpper());
						break;
				}
				return s;
			}
#endif
		};

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// 
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

		TypeMgr tm;
		Entry[] entries;
		int c_slots;

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// Constructor. Analyzes the specified paths to develop the strategy.
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public QuickCheckStrategy(TypeMgr tm, IEnumerable<String> paths)
		{
			this.tm = tm;

			List<Entry> ent = new List<Entry>();
			Dictionary<String, int> path_map = new Dictionary<String, int>();
			Dictionary<int, int> slot_map = new Dictionary<int, int>();
			IList<String> rap = tm.config.grammar.rule_args_path;

			foreach (String _p in paths)
			{
				String[] path = _p.Trim(outer_trim).ToLower().Split(dot_space, StringSplitOptions.RemoveEmptyEntries);

				if (path.Take(rap.Count).SequenceEqual(rap))
					path = path.Skip(rap.Count).ToArray();

				int ix_continue;
				int j;
				for (j = path.Length; j > 0; j--)
				{
					if (path_map.TryGetValue(path.Take(j).StringJoin("."), out ix_continue))
					{
						if (!slot_map.ContainsKey(ix_continue))
							slot_map.Add(ix_continue, slot_map.Count);
						ent.Add(new Entry(Op.ContinueFrom, ix_continue));
						goto emit_start;
					}
				}
				ent.Add(new Entry(Op.Top, 0));
				ix_continue = -1;

			emit_start:
				for (; j < path.Length; j++)
				{
					if (ix_continue != -1)
						ix_continue = -1;
					else
					{
						String s_p = path.Take(j + 1).StringJoin(".");
						//Console.WriteLine("{0,3} {1}", ent.Count, s_p);
						path_map.Add(s_p, ent.Count);
					}
					ent.Add(new Entry(Op.Feature, tm.feat_map[path[j]].i_feat));
				}
				ent.Add(new Entry(Op.Check, 0));
			}

			c_slots = slot_map.Count;
			entries = new Entry[ent.Count];

			int next = ent.Count;
			for (int i = ent.Count - 1; i >= 0; i--)
			{
				Entry e = ent[i];

				int i_slot;
				if (!slot_map.TryGetValue(i, out i_slot))
					i_slot = -1;

				int arg = e.arg;
				if (e.op == Op.ContinueFrom)
					arg = slot_map[arg];

				entries[i] = new Entry(e.op, arg, next, i_slot);
				if (e.op == Op.ContinueFrom || e.op == Op.Top)
					next = i;
			}

#if DUMP
			int ix = 0;
			foreach (Entry e in entries)
				Console.WriteLine("{0:0000} {1}", ix++, e.ToString());
#endif
#if CIL
			/// Generate a customized, unrolled CIL function for this quick-check strategy.
			CanSkip = emit_CanSkip();
#endif
		}

#if CIL
		public delegate bool D(Tfs tfs1, Tfs tfs2);

		readonly public D CanSkip;

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// Emit unrolled code which executes the strategy on the given TFSes at runtime.
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public D emit_CanSkip()
		{
			const BindingFlags bf = BindingFlags.Instance | BindingFlags.Public | BindingFlags.NonPublic;

			DynamicMethod dm = new DynamicMethod(
									String.Empty,
									typeof(bool),
									new SysType[]
										{
											typeof(QuickCheckStrategy),	// arg.0 'this'
											typeof(Tfs),				// arg.1 'tfs1'
											typeof(Tfs)					// arg.2 'tfs2'
										},
									typeof(QuickCheckStrategy),
									false);
			ILGenerator il = dm.GetILGenerator();

			Dictionary<int, Label> section_labels = entries
													.Select(ent => ent.next_section)
													.Distinct()
													.ToDictionary(eix => eix, eix => il.DefineLabel());
			Retrolabel _ret_true = default(Retrolabel);

			/// v===================== begin emiited code =====================v
			il.DeclareLocal(typeof(Edge*));						// loc.0 'rge1'
			il.DeclareLocal(typeof(Edge*));						// loc.1 'rge2'
			il.DeclareLocal(typeof(Edge));						// loc.2 'e1'
			il.DeclareLocal(typeof(Edge));						// loc.3 'e2'

#if DEREFERENCE_VTABLE
			il.DeclareLocal(typeof(IntPtr));					// loc.4 'Tfs.TryGetEdge'
			il.DeclareLocal(typeof(IntPtr));					// loc.5 'Tfs.TryGetEdge'

			/// loc.4 = &tfs1.TryGetEdge;
			il.Emit(OpCodes.Ldarg_1);
			il.Emit(OpCodes.Ldvirtftn, typeof(Tfs).GetMethod("TryGetEdge"));
			il.Emit(OpCodes.Stloc_S, (sbyte)4);

			/// loc.5 = &tfs2.TryGetEdge;
			il.Emit(OpCodes.Ldarg_2);
			il.Emit(OpCodes.Ldvirtftn, typeof(Tfs).GetMethod("TryGetEdge"));
			il.Emit(OpCodes.Stloc_S, (sbyte)5);

			String call_type = "calli";
#else
			String call_type = "callvirt";
#endif

			/// Edge* rge1 = stackalloc Edge[c_slots];
			il.EmitLdcI4(Marshal.SizeOf(typeof(Edge)) * c_slots);
			il.Emit(OpCodes.Localloc);
			il.Emit(OpCodes.Stloc_0);

			/// Edge* rge2 = stackalloc Edge[c_slots];
			il.EmitLdcI4(Marshal.SizeOf(typeof(Edge)) * c_slots);
			il.Emit(OpCodes.Localloc);
			il.Emit(OpCodes.Stloc_1);

			Debug.Assert(entries[0].op == Op.Top);
			int i_feat, i_slot, ix = 0;
			do
			{
				Label _sect_label;
				if (section_labels.TryGetValue(ix, out _sect_label))
					il.MarkLabel(_sect_label);

				switch (entries[ix].op)
				{
					case Op.Top:
						/// e1 = tfs1.Edge;
						il.Emit(OpCodes.Ldarg_1);
						il.Emit(OpCodes.Ldfld, typeof(Tfs).GetField("Edge", bf));
						il.Emit(OpCodes.Stloc_2);

						/// e2 = tfs2.Edge;
						il.Emit(OpCodes.Ldarg_2);
						il.Emit(OpCodes.Ldfld, typeof(Tfs).GetField("Edge", bf));
						il.Emit(OpCodes.Stloc_3);
						break;

					case Op.ContinueFrom:
						i_slot = entries[ix].arg;

						/// e1 = rge1[i_slot];
						il.Emit(OpCodes.Ldloc_0);
						il.EmitLdcI4(i_slot * Marshal.SizeOf(typeof(Edge)));
						il.Emit(OpCodes.Add);
						il.Emit(OpCodes.Ldobj, typeof(Edge));
						il.Emit(OpCodes.Stloc_2);

						/// e2 = rge2[i_slot];
						il.Emit(OpCodes.Ldloc_1);
						il.EmitLdcI4(i_slot * Marshal.SizeOf(typeof(Edge)));
						il.Emit(OpCodes.Add);
						il.Emit(OpCodes.Ldobj, typeof(Edge));
						il.Emit(OpCodes.Stloc_3);
						break;

					case Op.Feature:
						i_feat = entries[ix].arg;

						/// if ((e1.FlagsId & Edge.Flag.EtmNonBareType) == 0 || ...
						il.Emit(OpCodes.Ldloca_S, (sbyte)2);
						il.Emit(OpCodes.Ldfld, typeof(Edge).GetField("FlagsId", bf));
						il.EmitLdcI4((int)Edge.Flag.EtmNonBareType);
						il.Emit(OpCodes.And);
						il.Emit(OpCodes.Brfalse, section_labels[entries[ix].next_section]);

						/// ... (e2.FlagsId & Edge.Flag.EtmNonBareType) == 0 ...
						il.Emit(OpCodes.Ldloca_S, (sbyte)3);
						il.Emit(OpCodes.Ldfld, typeof(Edge).GetField("FlagsId", bf));
						il.EmitLdcI4((int)Edge.Flag.EtmNonBareType);
						il.Emit(OpCodes.And);
						il.Emit(OpCodes.Brfalse, section_labels[entries[ix].next_section]);

						/// ... !tfs1.TryGetEdge(arg, e1.Mark, out e1) ...
						il.Emit(OpCodes.Ldarg_1);
						il.EmitLdcI4(i_feat);
						il.Emit(OpCodes.Ldloca_S, (sbyte)2);
						il.Emit(OpCodes.Ldfld, typeof(Edge).GetField("Mark", bf));
						il.Emit(OpCodes.Ldloca_S, (sbyte)2);
#if DEREFERENCE_VTABLE
						il.Emit(OpCodes.Ldloc_S, (sbyte)4);
						il.EmitCalli(OpCodes.Calli,
									CallingConventions.HasThis,
									typeof(bool),
									new SysType[] { typeof(int), typeof(int), typeof(Edge).MakeByRefType() },
									null);
#else
						il.Emit(OpCodes.Callvirt, typeof(Tfs).GetMethod("TryGetEdge"));
#endif
						il.Emit(OpCodes.Brfalse, section_labels[entries[ix].next_section]);

						/// ... !tfs2.TryGetEdge(arg, e2.Mark, out e2)) ...
						il.Emit(OpCodes.Ldarg_2);
						il.EmitLdcI4(i_feat);
						il.Emit(OpCodes.Ldloca_S, (sbyte)3);
						il.Emit(OpCodes.Ldfld, typeof(Edge).GetField("Mark", bf));
						il.Emit(OpCodes.Ldloca_S, (sbyte)3);
#if DEREFERENCE_VTABLE
						il.Emit(OpCodes.Ldloc_S, (sbyte)5);
						il.EmitCalli(OpCodes.Calli,
									CallingConventions.HasThis,
									typeof(bool),
									new SysType[] { typeof(int), typeof(int), typeof(Edge).MakeByRefType() },
									null);
#else
						il.Emit(OpCodes.Callvirt, typeof(Tfs).GetMethod("TryGetEdge"));
#endif
						il.Emit(OpCodes.Brfalse, section_labels[entries[ix].next_section]);

						i_slot = entries[ix].ix_slot;
						if (i_slot != -1)
						{
							/// rge1[i_slot] = e1;
							il.Emit(OpCodes.Ldloc_0);
							il.EmitLdcI4(i_slot * Marshal.SizeOf(typeof(Edge)));
							il.Emit(OpCodes.Add);
							il.Emit(OpCodes.Ldloc_2);
							il.Emit(OpCodes.Stobj, typeof(Edge));

							/// rge2[i_slot] = e2;
							il.Emit(OpCodes.Ldloc_1);
							il.EmitLdcI4(i_slot * Marshal.SizeOf(typeof(Edge)));
							il.Emit(OpCodes.Add);
							il.Emit(OpCodes.Ldloc_3);
							il.Emit(OpCodes.Stobj, typeof(Edge));
						}
						break;

					case Op.Check:
						/// if (!tm.CanUnify(e1.FlagsId, e2.FlagsId)) ...
						il.Emit(OpCodes.Ldarg_0);
						il.Emit(OpCodes.Ldfld, typeof(QuickCheckStrategy).GetField("tm", bf));
						il.Emit(OpCodes.Ldloca_S, (sbyte)2);
						il.Emit(OpCodes.Ldfld, typeof(Edge).GetField("FlagsId", bf));
						il.Emit(OpCodes.Ldloca_S, (sbyte)3);
						il.Emit(OpCodes.Ldfld, typeof(Edge).GetField("FlagsId", bf));
						il.Emit(OpCodes.Call, typeof(TypeMgr)
												.GetMethod("CanUnify",
															bf,
															null,
															new SysType[] { typeof(Edge.Flag), typeof(Edge.Flag) },
															null));

						/// emit 'true' return code the first time it's needed
						if (_ret_true.Equals(default(Retrolabel)))
						{
							Label _skip = il.DefineLabel();
							il.Emit(OpCodes.Brtrue_S, _skip);

							/// return true;
							_ret_true = new Retrolabel(il);
							il.EmitLdcI4(1);
							il.Emit(OpCodes.Ret);
							il.MarkLabel(_skip);
						}
						else
							il.Emit(OpCodes.Brfalse, _ret_true);
						break;
				}
				ix++;
			}
			while (ix < entries.Length);

			/// return false;
			il.EmitLdcI4(0);
			il.Emit(OpCodes.Ret);
			/// ^===================== end emiited code =====================^

			Console.WriteLine("Compiled quick-check strategy to CIL (using '{0}'): {1} bytes", call_type, il.ILOffset);
			return (D)dm.CreateDelegate(typeof(D), this);
		}

#else
		struct EdgePair
		{
			public Edge e1;
			public Edge e2;
		};

		struct EdgePair2
		{
			public Edge.Flag e1_f;
			public int e1_m;
			public Edge.Flag e2_f;
			public int e2_m;
		};

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// Execute the strategy on the given TFSes at runtime.
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public unsafe bool CanSkip(Tfs tfs1, Tfs tfs2)
		{
			EdgePair* _rge = stackalloc EdgePair[c_slots + 1];
			EdgePair* rge = _rge + 1;

			EdgePair _ep_top;
			_ep_top.e1 = tfs1.Edge;
			_ep_top.e2 = tfs2.Edge;
			if (tfs2 is TfsSection)
				tfs2 = ((TfsSection)tfs2).mother;

			Debug.Assert(entries[0].op == Op.Top);
			EdgePair* ep = &_ep_top;

			fixed (Entry* _pent = entries)
			{
				for (Entry* pent_cur = _pent + 1, pent_end = pent_cur + entries.Length; pent_cur < pent_end; )
				{
					switch (pent_cur->op)
					{
						case Op.Top:
							ep = &_ep_top;
							break;
						case Op.ContinueFrom:
							ep = rge + pent_cur->arg;
							break;
						case Op.Feature:
							if ((ep->e1.FlagsId & ep->e2.FlagsId & Edge.Flag.EtmNonBareType) != 0)
							{
								int i_feat;
								EdgePair2* ep_next = (EdgePair2*)(rge + pent_cur->ix_slot);		// -1 is ok ix_slot here
								if ((ep_next->e1_f = tfs1.TryGetFlagsMark((i_feat = pent_cur->arg), ep->e1.Mark, out ep_next->e1_m)) != 0 &&
									(ep_next->e2_f = tfs2.TryGetFlagsMark(i_feat, ep->e2.Mark, out ep_next->e2_m)) != 0)
								{
									ep = (EdgePair*)ep_next;
									break;
								}
							}
							pent_cur = _pent + pent_cur->next_section;
							continue;	// note: not incrementing 'pent_cur'
						case Op.Check:
							Edge.Flag f1, f2;
							if ((f1 = ep->e1.FlagsId) != 0 && f1 != (f2 = ep->e2.FlagsId) && f2 != 0 && !tm.CanUnify(f1, f2))
								return true;
							break;
					}
					pent_cur++;
				}
			}
			return false;
		}
#endif
	};
}