Grammar Composition System

/src/agree-sys/50-subsumption.cs

using System;
using System.Diagnostics;

using miew.Debugging;
using miew.Enumerable;

namespace agree
{
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	/// <summary>
	/// TFS subsumption checking for (e.g.) packing purposes
	/// </summary>
	/// <reference>
	/// Stephan Oepen, John Carroll. 2000. "Ambiguity Packing in Constraint-based Parsing--Practical Results."
	/// In Proceedings of the 1st North American chapter of the Association for Computational Linguistics 
	/// conference. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 162-169. 
	/// </reference>
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	public unsafe struct Subsumption
	{
		TypeMgr tm;
		byte[] restrictor;
		Tfs tfs0, tfs1;
		sbyte subsumption;
		byte* rgb0, rgb1;
		byte b_next;
		ushort*[] rgpfix;

		public Subsumption(Tfs tfs0, Tfs tfs1)
		{
			this.tm = tfs0.tm;
			this.restrictor = tm.config.parser.packing_restrictor_map;
			this.rgpfix = tm.rgpfix_allft;
			this.tfs0 = tfs0;
			this.tfs1 = tfs1;
			this.subsumption = Equivalent;
			this.rgb0 = this.rgb1 = null;
			this.b_next = 0;
		}

		public const sbyte None = 0;
		public const sbyte FirstSubsumesSecond = 1;
		public const sbyte SecondSubsumesFirst = 2;
		public const sbyte Equivalent = 3;
		public const sbyte Bottom = -4;	// note: doesn't interfere with subsumption bit-testing

		public void _check(int tid, int m0, int m1)
		{
			ushort* pfix = rgpfix[tid];
			ushort* pfix_end = *pfix++ + pfix;
			while (pfix < pfix_end)
			{
				int i_feat = *pfix++;
				if (restrictor[i_feat] == 1)
					continue;
				int nm0, nm1;
				Edge.Flag f0 = tfs0.TryGetFlagsMark(i_feat, m0, out nm0);
				Edge.Flag f1 = tfs1.TryGetFlagsMark(i_feat, m1, out nm1);
				if (f0 == 0 && f1 == 0)
					continue;
				else if (f0 == 0)
					subsumption &= unchecked((sbyte)0xFD);
				else if (f1 == 0)
					subsumption &= unchecked((sbyte)0xFE);

				/// check for a re-entrancy that is present in one TFS but not the other
				byte* pb0, pb1;
				if (nm0 < 0 && nm1 < 0)
				{
					byte b0 = *(pb0 = rgb0 + ~nm0), b1 = *(pb1 = rgb1 + ~nm1);
					if (b0 + b1 == 0)
						*pb0 = *pb1 = ++b_next;
					else if (b0 == 0)
					{
						subsumption &= unchecked((sbyte)0xFD);
						*pb0 = b1;
					}
					else if (b1 == 0)
					{
						subsumption &= unchecked((sbyte)0xFE);
						*pb1 = b0;
					}
					else if (b0 != b1)
						subsumption = None;
				}
				else if (nm0 < 0)
				{
					subsumption &= unchecked((sbyte)0xFE);
					if (*(pb0 = rgb0 + ~nm0) == 0)
						*pb0 = ++b_next;
				}
				else if (nm1 < 0)
				{
					subsumption &= unchecked((sbyte)0xFD);
					if (*(pb1 = rgb1 + ~nm1) == 0)
						*pb1 = ++b_next;
				}

				if (subsumption <= 0)
					return;

				/// check type subsumption
				Edge.Flag f;
				f0 &= ~(Edge.Flag.Coreference | Edge.Flag.PrunedDuringParsing);
				f1 &= ~(Edge.Flag.Coreference | Edge.Flag.PrunedDuringParsing);
				if (f0 == f1)
					f = f0;
				else
				{
					if (f1 == 0)
						f = f0;
					else if (f0 == 0)
						f = f1;
					else if ((f = tm.UnifyTypes(f0, f1)) == Edge.Flag.Bottom)
					{
						subsumption = Bottom;
						return;
					}

					if (f == f0)
						subsumption &= unchecked((sbyte)0xFE);
					else if (f == f1)
						subsumption &= unchecked((sbyte)0xFD);
					else
					{
#if DEBUG
						Nop.CodeCoverage((f & Edge.Flag.EtmString) != 0);
#endif
						subsumption = None;
					}

					if (subsumption <= 0)
						return;
				}

				if (nm0 != 0 && nm1 != 0 && (f & Edge.Flag.EtmNonBareType) != 0)
				{
					_check((int)(f & Edge.Flag.MultiIdMask), nm0, nm1);
					if (subsumption <= 0)
						return;
				}
			}
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// -1 : tfs0 ⊓ tfs1 = ⊥
		/// 0 : no subsumption relationship (possibly ⊥)
		/// 1 : tfs0 ⊑ tfs1
		/// 2 : tfs1 ⊑ tfs0
		/// 3 : tfs0 == tfs1
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public sbyte Check()
		{
			Edge.Flag f, f0 = tfs0.Edge.FlagsId, f1 = tfs1.Edge.FlagsId;
			Debug.Assert(((f0 | f1) & (Edge.Flag.Coreference | Edge.Flag.PrunedDuringParsing)) == 0);
			if (f0 == f1)
				f = f0;
			else
			{
				if (f1 == 0)
					f = f0;
				else if (f0 == 0)
					f = f1;
				else if ((f = tm.UnifyTypes(f0, f1)) == Edge.Flag.Bottom)
					return Bottom;

				throw new Exception();
				//Nop.CodeCoverage();
				//if (f == f0)
				//    subsumption &= unchecked((sbyte)0xFE);
				//else if (f == f1)
				//    subsumption &= unchecked((sbyte)0xFD);
				//else
				//{
				//    Nop.CodeCoverage();	// this is wrong I think
				//    return TfsSubsumptionNone;
				//}
			}
			int c = -(tfs0.next_coref_mark + 1);
			byte* _pp = stackalloc byte[c - (tfs1.next_coref_mark + 1)];
			rgb0 = _pp;
			rgb1 = _pp + c;

			int m0 = tfs0.Edge.Mark, m1 = tfs1.Edge.Mark;
			if (m0 != 0 && m1 != 0 && (f & Edge.Flag.EtmNonBareType) != 0)
				_check((int)(f & Edge.Flag.MultiIdMask), m0, m1);

			return subsumption;
		}
	};
}