Grammar Composition System

/src/branch/20110407-thread-priority/tgcs-test/unittests.cs

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;

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

namespace agree.UnitTest
{
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	///
	///
	///
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	public class TypeMgrUnitTests : TypeMgr
	{
		public TypeMgrUnitTests(Globals config, Grammar g)
			: base(g, config)
		{
		}

		public HashSet<String> PathsBetween(String t1, String t2)
		{
			return PathsBetween(type_dict[t1], type_dict[t2]);
		}
		public HashSet<String> PathsBetween(Type t1, Type t2)
		{
			HashSet<String> hs = new HashSet<String>();
			if (t1 == t2)
				return hs;
			if (t1.IsSubtypeOf(t2))
			{
				Type tmp = t1;
				t1 = t2;
				t2 = tmp;
			}
			else if (!t1.IsSupertypeOf(t2))
				return hs;

			Action<String, Type> f = null;
			f = (s, t) =>
			{
				String x = (s.Length == 0 ? String.Empty : s + " -> ") + t.Name;
				if (t == t2)
					hs.Add(x);
				else foreach (Type c in t.Children)
					{
						if (c.IsSupertypeOrEqual(t2))
							f(x, c);
					}
			};
			f("", t1);
			return hs;
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		///
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#if false	// update AndToDest for distilled bitarr
		public void CheckForUnusedGlbs()
		{
			HashSet<Type> visited = new HashSet<Type>();
			BitArr z = new BitArr(code_size);
			foreach (Type n1 in type_dict.Values)
				foreach (Type n2 in type_dict.Values)
				{
					if (n1 == n2)
						continue;
					// this version allows us to reuse 'z'
					if (!BitArr.AndToDest(z, n1.m_code, n2.m_code))
						continue;
					Type glb;
					if (!code_dict.TryGetValue(z, out glb))
						throw new Exception(String.Format("missing GLB for {0} and {1}", n1.Name, n2.Name));
					visited.Add(glb);
				}
			foreach (Type n in type_dict.Values)
				if (n.IsGlb && !visited.Contains(n))
					throw new Exception(String.Format("unreferenced GLB {0}", n.Name));
		}
#endif

#if DEBUG
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		///
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public void CheckGlb()
		{
			int err_count = 0;
			HashSet<BitArr> unique_problems = new HashSet<BitArr>();

			int i;
			Type[] a_t = type_dict.Values.ToArray();
			for (i = 0; i < a_t.Length; i++)
			{
				for (int j = i + 1; j < a_t.Length; j++)
				{
					HashSet<Type> glbs = a_t[i].GlbCheck(a_t[j], TopType);
					if (glbs != null)
					{
						BitArr bc = a_t[i].m_code & a_t[j].m_code;
						unique_problems.Add(bc);
						Type should_use = code_dict[bc];
						Console.WriteLine("greatest lower bound problem between {0} & {1}", a_t[i].Name, a_t[j].Name);
						Console.WriteLine("should use {0} {1}", should_use.Name, bc.OnesPositions().Layout());
						foreach (Type tt in glbs)
							Console.WriteLine("\t{0}\t[level {1} {2}]", tt.Name, tt.m_level, tt.m_code.OnesPositions().Layout());
						err_count++;
					}
				}
			}
			if (unique_problems.Count > 0)
			{
				Console.WriteLine("{0} glb problems, {1} unique", err_count, unique_problems.Count);
				foreach (BitArr bc in unique_problems)
					Console.WriteLine("{0}", code_dict[bc].Name);
			}
		}


		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		///
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public void CheckGlbAlgs()
		{
			foreach (Type t in type_dict.Values)
			{
				HashSet<Type> hs = t.AllAncestors;
				if (hs.Contains(t))
					throw new Exception();
				foreach (Type t2 in type_dict.Values)
				{
					if (hs.Contains(t2))
					{
						if (t2.IsSubtypeOf(t) || t.IsSupertypeOf(t2))
							throw new Exception();
					}
					else
					{
						if (t2.IsSupertypeOf(t) || t.IsSubtypeOf(t2))
							throw new Exception();
					}
				}
				hs = t.AllDescendants;
				if (hs.Contains(t))
					throw new Exception();
				foreach (Type t2 in type_dict.Values)
				{
					if (hs.Contains(t2))
					{
						if (t2.IsSupertypeOf(t) || t.IsSubtypeOf(t2))
							throw new Exception();
					}
					else
					{
						if (t2.IsSubtypeOf(t) || t.IsSupertypeOf(t2))
							throw new Exception();
					}
				}
			}
		}


		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		///
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public void CheckGlbPairForProblems(Type t1, Type t2)
		{
			HashSet<Type> glbs = t1.GlbCheck(t2, TopType);
			if (glbs != null)
			{
				BitArr bc = t1.m_code & t2.m_code;
				Type should_use = code_dict[bc];
				Console.WriteLine("greatest lower bound problem between {0} & {1}", t1.Name, t2.Name);
				Console.WriteLine("should use {0}", should_use.Name);
				foreach (Type tt1 in glbs)
					Console.WriteLine("\t{0}\t[level {1}]", tt1.Name, tt1.m_level);
			}
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		///
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public void DisplayMaximalFeatures()
		{
			foreach (Type tt in type_dict.Values)
			{
				Console.WriteLine(tt.Name);
				foreach (TypeMgr.FeatureInfo fi in tt._dbg_features().Where(cp => cp.maximal_type == tt))
					Console.WriteLine("\t{0}", fi.feature.ToUpper());
			}
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		///
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public void DisplayAllFeatures()
		{
			foreach (Type tt in type_dict.Values)
			{
				Console.WriteLine(tt.Name);
				foreach (TypeMgr.FeatureInfo fi in tt._dbg_features())
				{
					Console.WriteLine("\t{0}", fi.feature.ToUpper());
				}
			}
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		///
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public void DisplayAllTypes()
		{
			foreach (Type tt in type_dict.Values)
			{
				Console.WriteLine(tt.Name);
				foreach (var fi in tt._dbg_features())
				{
					Console.Write("\t{0}", fi.feature.ToUpper());
					if (fi.maximal_type == tt)
						Console.Write("(local)");
					Console.WriteLine();
				}
			}
		}
#endif

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		///
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public void CheckFeaturesFlag()
		{
			foreach (Type t in type_dict.Values)
			{
				if (t.HasAnyFeatures != (t.FeatureIndexes.Length == 0))
					throw new Exception();
			}
		}


		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		///
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public void CheckRedundantLinks()
		{
			Stack<Type> stk = new Stack<Type>();
			Action<Type> f = null;
			f = node =>
			{
				if (!stk.Contains(node))
				{
					stk.Push(node);
					foreach (Type ch in node.Children)
						f(ch);
					stk.Pop();
				}

				IEnumerable<Type> r = stk.Skip(1).Intersect(node.Parents);
				if (r.Any())
					throw new Exception(String.Format("redundant link {0} to {1}", r.First().Name, node.Name));
			};
			f(TopType);
		}


		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		///
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public void CheckForCycle()
		{
			Stack<Type> stk = new Stack<Type>();
			Action<Type> f = null;
			f = node =>
			{
				if (stk.Contains(node))
					throw new Exception("cycle detected");
				stk.Push(node);
				foreach (Type ch in node.Children)
					f(ch);
				stk.Pop();
			};
			f(TopType);
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		///
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public int TypeEdgeCount()
		{
			HashSet<Type> visited = new HashSet<Type>();
			int count = 0;
			Action<Type> f = null;
			f = node =>
			{
				if (!visited.Contains(node))
				{
					visited.Add(node);
					count += node.ChildCount;
					foreach (Type ch in node.Children)
						f(ch);
				}
			};
			f(TopType);
			return count;
		}


		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		///
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public void DisplayTree(bool f_all)
		{
			Console.WriteLine("-------------- Type Hierarchy Display -------------------");
			foreach (Type t in type_dict.Values)
			{
				Console.WriteLine(t.Name + ":");
				if (!f_all)
				{
					if (t.Parents.Any())
					{
						Console.Write("\tparents: { ");
						foreach (String s in t.Parents.Select(e => e.Name))
							Console.Write(s + " ");
						Console.WriteLine("}");
					}
					if (t.Children.Any())
					{
						Console.Write("\tchildren: { ");
						foreach (String s in t.Children.Select(e => e.Name))
							Console.Write(s + " ");
						Console.WriteLine("}");
					}
				}
				else
				{
					foreach (String s in t.AllAncestors.Select(e => e.Name))
						Console.WriteLine("\tP : " + s);
					foreach (String s in t.AllDescendants.Select(e => e.Name))
						Console.WriteLine("\tC : " + s);
				}
			}
			Console.WriteLine("---------------------------------------------------------");
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		///
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public void CheckConjoinedParents(TextWriter tw)
		{
			BitArr ba_conj = new BitArr(code_size);
			foreach (Type tt in type_dict.Values)
			{
				if (tt.Parents.Count > 1)
				{
					ba_conj.SetAll();
					foreach (Type tt_par in tt.Parents)
					{
						if (!ba_conj.AndEq(tt_par.m_code))
							throw new Exception(String.Format("Conjoined parents '{0}' on type {1} do not unify.", tt.Parents.Select(e => e.Name).StringJoin(" "), tt_par.Name));
					}
					if (tw != null)
						tw.WriteLine("{0} := {1}  ... {2}", tt.Name, tt.Parents.Select(e => e.Name).StringJoin(" & "), code_dict[ba_conj].Name);
				}
			}
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		///
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public void DisplayConstraintTokens()
		{
			foreach (Type tt in type_dict.Values.Where(e => e.m_bfc != null))
			{
				Console.WriteLine(tt.Name);
				foreach (var bfc in tt.m_bfc)
				{
					Console.WriteLine("\t{0}", bfc.ToString());
				}
			}
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		///
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public void DisplayNonBareTypes()
		{
			int i = 0;
			foreach (Type tt in type_dict.Values.Where(e => e.HasAnyFeatures))
			{
				i++;
				Console.WriteLine(tt.Name + "\t" + tt.IsSubtypeOf(TopType));
			}
			Console.WriteLine(i);
		}

	};

	static class Extensions
	{
		public static String Layout(this IEnumerable<int> i)
		{
			return "{" + i.StringJoin(" ") + "}";
		}
	};
}