using System; using System.Collections.Generic; using System.Diagnostics; using System.Linq; using System.Threading.Tasks; using System.Threading; using agree.Parse; using glue.Debugging; using glue.Extensions.Enumerable; using glue.Tokenization; namespace agree { /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// /// <summary> /// /// </summary> /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// public class ParseChart : UnificationParseChart, IDisposable, ISysObj { readonly GrammarParser gp; readonly Tray tr_target; readonly IEnumerable<IParseChartToken> input; //hack public LexicalAnalysis lah = null; public ParseChart( GrammarParser gp, Tray tr_target, String source_text, IEnumerable<ISysObj> starts, int chart_size, IEnumerable<IParseChartToken> input, TokenSet _ts) : base(gp.Config, gp.Grammar, source_text, starts, chart_size, input) { this.gp = gp; this.tr_target = tr_target; this.input = input; this._TokenSet = _ts; // temp temp } public Grammar Grammar { get { return gp.Grammar; } } public TypeMgr TypeMgr { get { return gp.TypeMgr; } } public IEnumerable<IParseChartToken> InputTokens { get { return input; } } public TokenSet _TokenSet; public int UnificationCount { get { return c_unif + (lah != null ? lah.c_unif : 0); } } /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// /// <summary> /// Generate new activities for the specified ChartEdge /// Match the given chart edge against this chart's set of rules, and generate new active edges as appropriate. After /// creating an active edge corresponding to a rule/positioned passive edge tuple, we instruct it to attempt a match. /// Depending on success or failure, the active edge will either stay alive, or simply pass away. In the former case, /// since active edges are always seeded with a positioned passive edge, the active edge will know which chart position /// it needs to subscribe to, which is what keeps it alive. /// </summary> /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// protected override void GenerateRules(IParseChartEdge ce) { int i_start = ce.ChartSpan.StartIndex; int i_end = ce.ChartSpan.EndIndex; /// Rule pre-check filter "A Bag of Useful Technique for Efficient and Robust Parsing" (Kiefer et al. 1999) IEnumerable<GrammarRule> rules_to_use; Rule new_daughter = ce.License as Rule; if (new_daughter != null) rules_to_use = new_daughter.CompatibleKeyMothers.OfType<GrammarRule>(); else rules_to_use = gp.Grammar._grammar_rules; IParseChartEdge[] rgce_new = null; TfsEdge result; int cu = 0; foreach (GrammarRule r in rules_to_use) { IList<TfsEdge> rd = r.RuleDaughters; TfsEdge daughter; if (rd.Count == 1) { daughter = rd[0]; if (QuickCheck(daughter, ce.Contents)) continue; cu++; if (UnifyPartial(r, daughter, ce.Contents, out result, ce.ChartSpan.Equals(EntireSpan))) { rgce_new = rgce_new ?? new IParseChartEdge[] { ce }; cu += FinishMatchedEdge(r.License, result, ce.ChartSpan, rgce_new); } } else { int i_key = r.KeyDaughterIndex; // if the edge will not fit, don't bother creating the active edge. if (i_start < i_key) continue; if (i_end > ColumnCount - (rd.Count - i_key)) continue; /// The active edge is told whether or not it should only apply itself if a final result would be spanning. /// Furthermore, since active edges only grow in one direction, there's no point in creating a span-only /// active edge which does not abut the beginning or end of the chart. bool f_span_only = r.IsSpanOnly; /// We only have to try one ARGS position and it doesn't matter which one it is as long as that order is /// always used for that rule. Usage of this new edge in some other ARGS position would be handled later, /// when/if the rule succeeds in a neighboring chart position. if (i_key == 0) { if (f_span_only && i_start > 0) continue; daughter = rd[0]; if (QuickCheck(daughter, ce.Contents)) continue; cu++; if (UnifyPartial(r, daughter, ce.Contents, out result, false)) { rgce_new = rgce_new ?? new IParseChartEdge[] { ce }; ActiveEdge ae = new ActiveRightEdge(this, IncorporatePart(r, result), rgce_new); cu += SubscribeRightOf(ce.ChartSpan.EndIndex, ae); } } else { if (f_span_only && i_end < ColumnCount - 1) continue; daughter = rd[rd.Count - 1]; if (QuickCheck(daughter, ce.Contents)) continue; cu++; if (UnifyPartial(r, daughter, ce.Contents, out result, false)) { rgce_new = rgce_new ?? new IParseChartEdge[] { ce }; ActiveEdge ae = new ActiveLeftEdge(this, IncorporatePart(r, result), rgce_new); cu += SubscribeLeftOf(ce.ChartSpan.StartIndex, ae); } } } } if (cu > 0) Interlocked.Add(ref c_unif, cu); } /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// /// <summary> /// Unify a rule daughter /// </summary> /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// public override bool UnifyPartial(IParseChartRule mother, TfsEdge daughter, TfsEdge candidate, out TfsEdge full, bool f_last) { Unification.Pruning u_prun = null; Unification.Partial u_part = f_last ? (u_prun = new Unification.Pruning(tr_target)) : new Unification.Partial(tr_target); if (!u_part.UnifyAndComplete(mother.Contents, daughter, candidate, out full)) return false; if (mother.RuleDaughters.Count > 2) Nop.CodeCoverage(); //full.RegisterName(String.Format("{0}-{1}", this.SysObjName, full.ToString())); /// Optionally delete daughter features from a finished mother rule if (f_last && tr_target.DeletedDaughters != null) { #if TOP_MARKS UnifyHelper.top_marks.Add(e.Mark); #endif foreach (ConstraintPool cp in tr_target.DeletedDaughters) u_prun.PruneBelow(cp, full.Edge.Mark); u_prun._remove_vacuous_corefs(); #if TOP_MARKS UnifyHelper.top_marks.Remove(e.Mark); #endif } return true; } /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// /// <summary> /// /// </summary> /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// public override Task<TfsEdge> UnifyPartialAsync(IParseChartRule mother, TfsEdge daughter, TfsEdge candidate, bool f_last) { Unification.Async.Partial u_part = f_last ? new Unification.Async.Pruning(tr_target) : new Unification.Async.Partial(tr_target); return u_part.UnifyAsync(daughter, candidate).ContinueWith<TfsEdge>(t => { if (t.Result.Equals(default(Edge))) return default(TfsEdge); Edge e; u_part.CompleteSkeleton(mother.Contents, daughter, t.Result, out e); TfsEdge full = tr_target.CreateTfs(e); /// Optionally delete daughter features from a finished mother rule Unification.Async.Pruning u_prun = u_part as Unification.Async.Pruning; if (u_prun != null && tr_target.DeletedDaughters != null) { foreach (ConstraintPool cp in tr_target.DeletedDaughters) u_prun.PruneBelow(cp, full.Edge.Mark); u_prun._remove_vacuous_corefs(); } //full.RegisterName(String.Format("{0}-{1}", this.SysObjName, full.ToString())); return full; }, CancelTok, TaskContinuationOptions.AttachedToParent, TaskScheduler.Default); } /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// /// <summary> /// Unify whole feature structures /// </summary> /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// public override bool CanUnify(ISysObj e1, TfsEdge e2) { #if false UnifyHelper uhx = new UnifyHelper(tm, tm.tray); var q1 = uhx.UnificationCheck(e1, e2); // { // result = default(Edge); // return false; //} #endif Unification.Checker uc = new Unification.Checker(gp.Grammar.loadtray); var q2 = uc.Check(((Entry)e1).Expanded, e2); //if (q1 != UnifyHelper.SubsumptionResult.Bottom && !q2) //Debug.WriteLine("{0} {1}", q1, q2); if (!q2) { return false; } return true; } /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// /// <summary> /// Quick-check: /// /// Robert Malouf, John Carroll, Ann Copestake. 2000. Efficient feature structure operations without compliation. /// Natural Language Engineering 6 (1): 29-46. Cambridge: Cambridge University Press /// </summary> /// <returns>true if the unification can be skipped because it would fail, /// false if the caller should proceed to unify</returns> /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// public override bool QuickCheck(TfsEdge te1, TfsEdge te2) { TypeMgr tm = TypeMgr; if (tm.config.quick_check_paths != null) { int m1 = te1.Edge.Mark; int m2 = te2.Edge.Mark; foreach (TrayCompiledFsPath path in tm.config.quick_check_paths) { Edge.Flag f1, f2; if (path.GetTypeId(m1, out f1) && path.GetTypeId(m2, out f2) && !tm.CanUnify(f1, f2)) return true; } } return false; } /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// /// <summary> /// /// </summary> /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// public override IGrammarRule IncorporatePart(IGrammarRule mother, TfsEdge result) { return new GrammarRuleDaughterCache(this, mother, result); } /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// /// <summary> /// Discard the derived passive edges that this chart owns in the persistent edge store. Do not delete the contents /// of the passive lexical edges because they actually belong to the grammar. /// </summary> /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// public unsafe void Dispose() { Status s = m_status; Thread.MemoryBarrier(); if ((s & Status.Disposing) != 0) return; fixed (Status* ps = &m_status) { Status new_status = (s & Status._StatusMask) | Status.Disposing; if (Interlocked.CompareExchange(ref *(int*)ps, (int)new_status, (int)s) == (int)s) { foreach (IParseChartEdge pe in AllEdges()) pe.Dispose(); if (lah != null) lah.Dispose(); Thread.MemoryBarrier(); m_status = new_status | Status.Disposed; } } } /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// /// /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// [DebuggerDisplay("{ToString(),nq}")] class GrammarRuleDaughterCache : IGrammarRule { TfsEdge tfs; [DebuggerBrowsable(DebuggerBrowsableState.RootHidden)] readonly TfsEdge[] daughters; GrammarRule m_rule; /// <summary> /// Find and cache the TFS entry points for the daughters of the rule. /// Copy the key daughter index from the original rule, since it never changes in subsequent instances. /// </summary> public GrammarRuleDaughterCache(ParseChart c, IGrammarRule m_old, TfsEdge m_new) { this.tfs = m_new; this.daughters = m_new.RuleDaughters.ToArray(); this.m_rule = (GrammarRule)m_old; } public TfsEdge Contents { get { return tfs; } } public void Dispose() { tfs.Dispose(); } public IList<TfsEdge> RuleDaughters { get { return daughters; } } IEnumerable<TfsEdge> IMotherDaughter.RuleDaughters { get { throw new NotImplementedException(); } } public int KeyDaughterIndex { get { return m_rule.KeyDaughterIndex; } } public bool IsSpanOnly { get { return m_rule.IsSpanOnly; } } public bool SpinCompare(TfsEdge other) { throw new NotImplementedException(); } public override string ToString() { return String.Format("{0} {1}", tfs, daughters.Select((d, ix) => String.Format("ARGS{0}[{1}]{2}", ix, d, ix == m_rule.KeyDaughterIndex ? "*" : "")).StringJoin(" ")); } public ISysObj License { get { return m_rule; } } public bool CheckDaughterCompatibility(ISysObj daughter, int i_arg) { return daughter != null && m_rule.CheckDaughterCompatibility(daughter, i_arg); } } }; }