using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Threading;
using System.Threading.Tasks;
using miew.Concurrency;
using miew.Debugging;
#pragma warning disable 0649
namespace agree
{
using unif_stats = ParseControl.Stats._unification;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///
/// S U B S C R I P T I O N C H A R T
///
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
abstract public partial class SubscriptionChart : ChartBase
{
internal SubscriptionChart(ParseControl ctrl)
: base(ctrl)
{
this.srcs_leftof = new NotificationSource[c_columns - 1];
this.srcs_rightof = new NotificationSource[c_columns - 1];
for (int i = 0; i < c_columns - 1; i++)
{
srcs_leftof[i] = new NotificationSource(this, LEFT, i + 1);
srcs_rightof[i] = new NotificationSource(this, RIGHT, i);
}
}
NotificationSource[] srcs_leftof, srcs_rightof;
protected const bool LEFT = true, RIGHT = false;
protected abstract void GenerateActiveEdges(IParseObj pce);
protected abstract bool SubsumptionPacking(IParseObj pce);
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
internal void Subscribe(bool f_left, ActiveEdge ace, ref unif_stats u_stats)
{
if (f_left)
srcs_leftof[ace.CompletedSpan.StartIndex - 1].Subscribe(ace, ref u_stats);
else
srcs_rightof[ace.CompletedSpan.EndIndex].Subscribe(ace, ref u_stats);
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
/// Accept new edges into the chart. Atomically with insertion into the chart, stamp the edge with an interlocking
/// sequence barrier in order to separate interested parties into two groups: those who registered previously--and
/// who will receive the edge now, versus those who register at any point afterwards, who will receive the edge via
/// the retroactive edge delivery mechanism which is part of the subscription process.
/// </summary>
/// <remarks>
/// We check subsumption before making the new passive edge visible ('active'), because if proactive packing is
/// performed we don't want to deal with the complications of having the edge ever having been published. The
/// purpose of putting the edge in the chart at all, however, as we just did, is so that anyone who tries to determine
/// sequencing relative to this edge will be blocked from proceeding further up the chart cell until this
/// subsumption check is complete. The bloking ensures deterministic correctness of maximal packing: the global
/// sequencing system is used to partition edges within a cell for the purposes of evaluating
/// subsumption. In this case, since the objects under comparison are within the same list (unlike the passive-to-
/// active edge subscription mechanism), and the operation (subsumption checking) is commutative, we only need to
/// evaluate within the lower partition.
/// </remarks>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public void AddParseObj(IParseObj ce)
{
if (ctrl.IsParseCancelled)
return;
/// add passive edge to chart
this[ce.TokenSpan].Add(ce);
/// now that there's a sequence ID, print out some stuff
if (ctrl.config.system.tw_debug != null)
ChartEdgeReport(ce);
/// see notes above
if (ctrl.parser_config.packing != Config.Parser.PackingOpts.None && SubsumptionPacking(ce))
return;
/// make the new edge visible
ce.SetStateActive();
/// a task for generating new rules
ctrl.StartAttachedChildTask(GenerateActiveEdges, ce);
unif_stats u_stats = new unif_stats(ParseControl.Stats.Visibility.Private);
/// send the edge to interested parties:
/// 1. parties for which this item is to the right
int i_start = ce.TokenSpan.StartIndex;
if (i_start > 0)
srcs_rightof[i_start - 1].SendToAllSubscribers(ce, ref u_stats);
/// 2. parties for which this item is to the left
int i_end = ce.TokenSpan.EndIndex;
if (i_end < ColumnCount - 1)
srcs_leftof[(i_end - 1) + 1].SendToAllSubscribers(ce, ref u_stats);
ctrl.stats.Parsing.Unification.Add(u_stats);
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
/// Clearing subscribers allows references to active edges which were not productive during the parse to be released
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public void ClearSubscribers()
{
for (int i = 0; i < c_columns - 1; i++)
{
srcs_leftof[i].Clear();
srcs_rightof[i].Clear();
}
srcs_leftof = null;
srcs_rightof = null;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///
/// N O T I F I C A T I O N S O U R C E
///
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
internal struct NotificationSource
{
readonly SubscriptionChart m_chart;
readonly int i_col;
readonly bool f_left;
ActiveEdge m_first;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public NotificationSource(SubscriptionChart chart, bool f_left, int i_col)
{
this.f_left = f_left;
this.m_chart = chart;
this.i_col = i_col;
this.m_first = null;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
/// This is the normal (non-retroactive) subscription delivery mechanism which sends new edges to existing
/// active edges. Also opportunistically try to patch over defunct active edges that we might encounter. Do not
/// send to active edges with a higher sequence number than the new edge. Also try not to forward to subscribers
/// who are on packing hold although this can't be guaranteed because active objects are subject to asynchronous
/// entry of that state, causing them to possibly switch to inactive after we observe them. On the other
/// hand, regarding visible objects, the 'pending' state is only exited, never entered, so it will be successfully
/// banned but possibly missed, this latter condition being handled by the atomic sequence, which ensures
/// that anything missed is sent retroactively.
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
internal void SendToAllSubscribers(IParseObj ce, ref unif_stats u_stats)
{
int i_seq = ce.SequenceId;
for (ActiveEdge ae = m_first; ae != null; ae = ae.m_next)
{
if ((ae.State & SequenceControl.stb_Remove) > 0)
continue;
if (!ae.SeqIdBelow(i_seq))
continue;
#if false
var pe = ce as PassiveEdge.Derived;
if (pe != null && pe.IsHold())
pe.DirectCancel();
#endif
if (ce.IsActive())
ae.TryMatchEdge(ce, ref u_stats);
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
/// Subscribe an active edge to this notification list.
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public void Add(ActiveEdge ae_new)
{
Debug.Assert(ae_new.State == default(byte));
ae_new.SetStateRaw(SequenceControl.PENDING);
ActiveEdge _tmp;
do
_tmp = ae_new.m_next = m_first;
while (Interlocked.CompareExchange(ref m_first, ae_new, _tmp) != _tmp);
m_chart.StampSequence(ae_new);
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
/// Add the target to the list of subscribers. Because rule_targets is a list that is interlocked with the
/// ChartEdge stamping sequence, Add() atomically imposes an (arbitrary) partition upon all past (and future)
/// ChartEdges such that those which arrive prior to the sequencing point are sent by the retroactive mechanism,
/// and ChartEdges sent afterwards will be posted to the target via the subscription delivery mechanism.
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public void Subscribe(ActiveEdge ace, ref unif_stats u_stats)
{
/// add to a linked list and set a sequence barrier
this.Add(ace);
ace.SetStateActive();
int i_seq = ace.SequenceId;
ChartCell._multi_cell_enum e = f_left ?
new ChartCell._multi_cell_enum(m_chart, 0, 1, i_col - 1, -1) :
new ChartCell._multi_cell_enum(m_chart, i_col + 1, 0, 0, 1);
/// partitioning according to the sequence stamp, only send ChartEdges with a lower
/// sequence number to the newly connected target.
for (IParseObj ce, ce_prev = null; e.MoveNext(); ce_prev = ce)
{
if (((ce = e.Current).State & (SequenceControl.stb_Remove | SequenceControl.stb_Hold)) > 0)
continue;
if (ce.SeqIdAbove(i_seq))
continue;
#if false
var pe = ce as PassiveEdge.Derived;
if (pe != null && pe.IsHold())
pe.DirectCancel();
#endif
if (ce.IsActive())
ace.TryMatchEdge(ce, ref u_stats);
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
/// release ActiveEdge references in the linked-list so the objects can be collected
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public void Clear()
{
ActiveEdge ae = m_first;
while (ae != null)
{
ActiveEdge _tmp = ae.m_next;
ae.m_next = null;
ae = _tmp;
}
m_first = null;
}
};
};
}