using System; using System.Diagnostics; using System.IO; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading; using System.Threading.Tasks; using System.Collections.Concurrent; using System.Runtime.Serialization; using glue; using glue.Extensions.String; using glue.Extensions.String.Builder; using glue.Debugging; using glue.Extensions.Enumerable; using glue.Collections.XSpinLock; using glue.Collections.LockFreeDictionary; #pragma warning disable 0649 namespace agree { /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// /// <summary> /// Trays are allocated globally, not per-grammar. The system supports a maximum of 64 trays. Each tray is a complete set /// of ConstraintPools for some grammar. A grammar might use multiple trays in order to (a.) use a higher-performance /// read-only tray for the invariant parts of the grammar (b.) for isolation or experimental purposes (c.) for parsing /// or unification results, allowing the entire result to be instantly discarded and cleaned up. /// </summary> /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// public static class TrayMgr { const int MaxTrays = 64; static int next_tix = 0; static public Tray[] all_trays = new Tray[MaxTrays]; static public Tray _most_recent_tray = null; public static Tray Allocate<T>(TypeMgr tm, int next_mark, int next_id) where T : Tray { int tix = Interlocked.Increment(ref next_tix) - 1; if (tix == MaxTrays) throw new Exception(String.Format("The number of pool trays has exceeded the limit of {0}", MaxTrays)); Tray tr = null; if (Nop.single_threaded) { tr = new SingleUserTray(tix, tm, next_mark, next_id); } else if (typeof(T) == typeof(ConcurrentTray)) { tr = new ConcurrentTray(tix, tm, next_mark, next_id); //tr = new SpinLockTray(tix, tm, next_mark, next_id); //tr = new HybridSpinLockTray(tix, tm, next_mark, next_id); //tr = new LockFreeTray(tix, tm, next_mark, next_id); //tr = new HybridSpinLockRwTray(tix, tm, next_mark, next_id); //tr = new HybridTray<ConcurrentDictionary<Int32, Edge>>(tix, tm, next_mark, next_id); //tr = new HybridTray<SpinlockDictionary<Int32, Edge>>(tix, tm, next_mark, next_id); //tr = new HybridTray<LockFreeDictionary<Int32, Edge>>(tix, tm, next_mark, next_id); //tr = new HybridTray<ReaderWriterDictionary<Int32, Edge>>(tix, tm, next_mark, next_id); //tr = new HybridTray<SpinlockRwDictionary<Int32, Edge>>(tix, tm, next_mark, next_id); } else Debugger.Break(); if (Console.Out != null) { String s_tray_type = tr.GetType().Name; if (tr.GetType().IsGenericType) s_tray_type += "<" + tr.GetType().GetGenericArguments()[0].Name + ">"; Console.Out.WriteLine(s_tray_type); } all_trays[tix] = tr; _most_recent_tray = tr; return tr; } public static IEnumerable<Tray> GetTypeMgrTrays(TypeMgr tm) { foreach (Tray tr in all_trays) if (tr != null && tr.tm == tm) yield return tr; } }; /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// /// <summary> /// TRAY UTILITIES /// </summary> /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// abstract public partial class Tray { /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// /// <summary> /// /// </summary> /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// public void CleanGarbage(HashSet<PoolMark> reachable) { HashSet<PoolMark> pool_pms = new HashSet<PoolMark>(Pools.SelectMany(cp => cp.Marks.Select(m => new PoolMark(cp, m)))); HashSet<PoolMark> garbage = new HashSet<PoolMark>(pool_pms.Except(reachable)); foreach (Edge gedge in TreeTops(garbage)) RudeTruncate(gedge); } /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// /// <summary> /// /// </summary> /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// public IEnumerable<Edge> TreeTops(IEnumerable<PoolMark> set) { HashSet<PoolMark> hs = new HashSet<PoolMark>(set); foreach (PoolMark pm in set) hs.ExceptWith(AllPoolMarks(pm.Constraint)); return hs._GroupBy(pm => pm.in_mark) .Select(g => { Type tx = tm.GetGlbOfMany(g.Select(pm => pm.Pool.IntroducedBy)) ?? tm.TopType; return new Edge((Edge.Flag)tx.m_id, g.Key); }); } /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// /// <summary> /// /// </summary> /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// public bool CanUnfill(ConstraintRef cr) { Edge e = cr.Constraint; Type t0 = tm.GetEdgeType(e.FlagsId); //if (t0.Name == "0-dlist" && // tm.GetEdgeType(Pools[tm.feat_map["list"].i_feat].GetEdge(e.Mark).FlagsId).Name == "0-1-list" && // tm.GetEdgeType(Pools[tm.feat_map["last"].i_feat].GetEdge(e.Mark).FlagsId).Name == "0-1-list") // return true; foreach (int fix in t0._deprec_feat_indexes) { ConstraintPool cp = Pools[fix]; Edge ne; if (cp.TryGetEdge(e.Mark, out ne)) { Edge ne2; cp.TryGetEdge(t0.Expanded.Edge.Mark, out ne2); Type t3 = tm.GetEdgeType(ne2.FlagsId); if (ne.IsCoreferenced) return false; if (tm.GetEdgeType(ne.FlagsId) != t3) return false; if (ne.Mark != Edge.MarkBare && !CanUnfill(new ConstraintRef(e, cp))) return false; } } return true; //!rgcr.Any(cr => cr.Constraint.IsConstrained) && //tr.tm.GetEdgeType(e.FlagsId).FeatureIndexes.SequenceEqual(rgcr.Select(cr => cr.FeatureIndex))) } /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// /// <summary> /// /// </summary> /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// public class MonospaceFormatter { Tray tr; TypeMgr tm; Dictionary<Edge, int> corefs = new Dictionary<Edge, int>(); bool f_uncons_top = true; bool f_unfill = true; int[] feature_order = null; IDictionary<String, String> type_name_remapping = null; public MonospaceFormatter(Tray tr) { this.tr = tr; this.tm = tr.tm; } public int[] FeatureDisplayOrder { get { return feature_order; } set { feature_order = value; } } public bool Unfill { get { return f_unfill; } set { f_unfill = value; } } /// <summary> /// Type names can be substituted to account for e.g. different glb number assignments in a comparison /// system. /// </summary> public IDictionary<String, String> TypeNameRemapping { get { return type_name_remapping; } set { type_name_remapping = value; } } /// <summary> /// Note: Single-threaded (use of corefs) /// </summary> public String FormatEdge(Edge edge) { corefs.Clear(); String r = tm.GetEdgeType(edge.FlagsId).Name; String s = _format_edge(0, edge); if (s != String.Empty) r += Environment.NewLine + s; return r; } String _format_edge(int indent, Edge e) { var rgcr = (f_uncons_top ? tr.AllConstraintRefs(e) : tr.ConstrainedRefsOnly(e)) .ToArray(); if (rgcr.Length == 0) return String.Empty; if (feature_order != null) rgcr = rgcr.OrderBy(cr => Array.IndexOf<int>(feature_order, cr.Pool.i_feat)).ToArray(); int feat_max = rgcr.Max(cr => cr.Pool.Feature.Length) + 1; String s_indent = new String(' ', indent); StringBuilder sb = new StringBuilder(); bool f_first = true; foreach (ConstraintRef cr in rgcr) { Edge ne = cr.Constraint; if (f_first) { sb.Append(s_indent + "[ "); f_first = false; } else sb.Append("," + Environment.NewLine + s_indent + " "); sb.Append(cr.Pool.Feature.ToUpper().PadRight(feat_max)); bool f_old_coref = false; String coref_text = String.Empty; if (ne.IsCoreferenced) { int i_coref; if (!corefs.TryGetValue(ne, out i_coref)) { i_coref = corefs.Count + 1; corefs.Add(ne, i_coref); coref_text = String.Format("#{0}:", i_coref); } else { coref_text = "#" + i_coref.ToString(); f_old_coref = true; } sb.Append(coref_text); } if (!f_old_coref) { String s_type; if (tm.IsStringValue(ne.FlagsId)) s_type = "\"" + tm.GetStringValue(ne.FlagsId) + "\""; else { s_type = tm.GetEdgeType(ne.FlagsId).Name; String s_tmp; if (type_name_remapping != null && type_name_remapping.TryGetValue(s_type, out s_tmp)) s_type = s_tmp; } sb.Append(s_type); if (!f_unfill || !tr.CanUnfill(cr)) { String cons = _format_edge(indent + feat_max + 2 + coref_text.Length, ne); if (cons.Length > 0) sb.Append(Environment.NewLine + cons); } } } sb.Append(" ]"); return sb.ToString(); } }; /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// /// <summary> /// /// </summary> /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// public class SubsumptionComparer : IComparer<Edge>, IEqualityComparer<Edge> { public SubsumptionComparer(Tray tr) { } public int Compare(Edge x, Edge y) { throw new NotImplementedException(); } public bool Equals(Edge x, Edge y) { return Compare(x, y) == 0; } public int GetHashCode(Edge obj) { throw new NotImplementedException(); } }; /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// /// <summary> /// /// </summary> /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// public IDictionary<Edge, CorefFinder.Entry> GetCoreferences(Edge e) { if ((e.FlagsId & Edge.Flag.EtmNonBareType) == 0) return CorefFinder.NoCorefs; return new CorefFinder(this, e).Result; } }; /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// /// <summary> /// /// </summary> /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// public sealed class CorefFinder { public readonly static IDictionary<Edge, Entry> NoCorefs = new Dictionary<Edge, Entry>(); /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// /// /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// public class Entry : HashSet<ConstraintRef> { public Entry(ConstraintRef cref_first, int i_tag) { this.cref_display = cref_first; this.i_tag = i_tag; } readonly public int i_tag; public ConstraintRef cref_display; public override String ToString() { return String.Format("#{0} in-edges: {1}", i_tag, this.Count); } }; readonly Tray tr; readonly TypeMgr tm; readonly ConstraintPool[] Pools; Dictionary<Edge, Entry> dict = null; int coref_tag; public CorefFinder(Tray tr, Edge e) { this.tr = tr; this.tm = tr.tm; this.Pools = tr.Pools; this.coref_tag = 0; _get_coreferences(e); } /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// /// /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// void _get_coreferences(Edge e) { /// this determines the order of coref tag numbering. it used to be specified here with /// .OrderBy(cp => cp.IntroducedBy.m_level) but this is not needed so long as the feature index order /// in the type is kept this way, as it is at this time. foreach (int i_feat in tm.GetEdgeType(e.FlagsId)._deprec_feat_indexes) { ConstraintPool cp; Edge next_edge; bool f_descend = true; if ((cp = Pools[i_feat]).TryGetEdge(e.Mark, out next_edge) && (next_edge.FlagsId & Edge.Flag.Coreference) > 0) { ConstraintRef cref = new ConstraintRef(e, cp); Entry cre; if (dict == null) dict = new Dictionary<Edge, Entry> { { next_edge, cre = new Entry(cref, coref_tag++) } }; else if (!dict.TryGetValue(next_edge, out cre)) dict.Add(next_edge, cre = new Entry(cref, coref_tag++)); else f_descend = false; cre.Add(cref); } if (f_descend && (next_edge.FlagsId & Edge.Flag.EtmMask) == Edge.Flag.EtmNonBareType) _get_coreferences(next_edge); } } public IDictionary<Edge, Entry> Result { get { return dict ?? NoCorefs; } } }; }