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);
}
}
};
}