//#define CHECK_COUNTS
#define FEATURE_PATH
//#define COUNTING
using System;
using System.IO;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Runtime.InteropServices;
using miew.Debugging;
using miew.Enumerable;
namespace agree
{
public unsafe partial class UnificationQd
{
ParseControl ctrl;
TypeMgr tm;
const int TopmostMark = 1;
const int WellFormedSlots = 400;
const int MaxParticipants = 16;
ArrayTfs[] participants;
int c_participants;
Scratch* ps_base, next_base;
Scratch** bases;
bool f_args_delete;
bool f_restrict;
ushort*[] rgpfix;
int c_slot_alloc, c_edges, next_mark, next_coref_mark, i_ate;
arr_tfs_entry* _pate;
ushort* _hidx, _rgn;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public UnificationQd(TypeMgr tm)
{
#if DEBUG
_singleton = this;
#if FEATURE_PATH
if (Debugger.IsAttached)
this.stk = new Stack<int>();
#endif
#endif
this.tm = tm;
this.participants = new ArrayTfs[MaxParticipants + 1];
this.rgpfix = tm.rgpfix_allft;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public UnificationQd(ParseControl ctrl, bool f_args_delete, bool f_restrict)
: this(ctrl.tm)
{
this.ctrl = ctrl;
this.next_coref_mark = -1;
this.next_mark = TopmostMark + 1;
this.f_args_delete = f_args_delete;
this.f_restrict = f_restrict;
if (f_restrict && f_args_delete)
this.rgpfix = tm.rgpfix_da_rs;
else if (f_restrict)
this.rgpfix = tm.rgpfix_restr;
else if (f_args_delete)
this.rgpfix = tm.rgpfix_dargs;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void _init_node(Scratch* ps, int tfsix, Edge e)
{
#if DEBUG
Debug.Assert(ps->tfsix == 0 && tfsix != 0);
//Debug.Assert(true_bases(tfsix) <= ps && ps < true_bases(tfsix + 1));
#endif
ps->f = e.FlagsId & ~Edge.Flag.Coreference;
ps->m_src = e.Mark;
ps->tfsix = (short)tfsix;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Scratch* _fallback_fetch(ArrayTfs tfs, Scratch* ps, int i_feat)
{
Debug.Assert(ps->m_src != 0 && ps->forward >= 0);
arr_tfs_entry* pe;
int mix, mark, tfsix = ps->tfsix, fwd = ps->forward;
fallback:
if ((mix = tfs.hidx[(byte)(i_feat + (mark = ps->m_src))]) != 0)
fixed (arr_tfs_entry* _pe = tfs.entries)
do
if ((pe = _pe + mix - 1)->i_feat == i_feat && pe->mark == mark)
{
if (pe->e_FlagsId == Edge.Flag.PrunedDuringParsing)
break;
if ((ps = bases[tfsix] + ((mark = pe->e_Mark) < 0 ? mark : mix))->tfsix == 0)
{
ps->f = pe->e_FlagsId & ~Edge.Flag.Coreference;
ps->m_src = mark;
ps->tfsix = (short)tfsix;
}
else
while ((fwd = ps->forward) < 0)
ps = ps_base - fwd;
return ps;
}
while ((mix = tfs.rg_next[mix - 1]) != 0);
if (fwd <= 0)
return null;
fwd = -(ps = ps_base + fwd)->forward;
tfs = participants[tfsix = ps->tfsix];
goto fallback;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
bool _duplex_node(Scratch* ps0, Scratch* ps1)
{
Edge.Flag f0, f1, nf;
if ((f0 = ps0->f) == (f1 = ps1->f) || f1 == 0)
nf = f0;
else if (f0 == 0)
nf = f1;
else if ((nf = tm.UnifyTypesNoCoref(f0, f1)) == Edge.Flag.Bottom)
return false;
if ((nf & Edge.Flag.EtmNonBareType) == 0)
_forward(ps1, ps0, nf, false);
else
{
if (ps0->m_src != 0 && ps1->m_src != 0)
{
int missing0 = 0, missing1 = 0;
ArrayTfs tfs0 = participants[ps0->tfsix];
ArrayTfs tfs1 = participants[ps1->tfsix];
ushort* pfix = rgpfix[(int)(nf & Edge.Flag.MultiIdMask)], pfix_end = *pfix++ + pfix;
do
{
Scratch* nps0 = _fallback_fetch(tfs0, ps0, *pfix);
Scratch* nps1 = _fallback_fetch(tfs1, ps1, *pfix);
#if DEBUG
_debug_nps(ps0, ps1, nps0, nps1);
#endif
if (nps0 == null)
{
if (nps1 != null)
missing0++;
}
else if (nps1 == null)
missing1++;
else if (nps0 != nps1 && !_duplex_node(nps0, nps1))
return false;
}
while (++pfix < pfix_end);
if (missing0 <= missing1)
_forward(ps1, ps0, nf, missing0 != 0);
else
_forward(ps0, ps1, nf, missing1 != 0);
}
else if (ps0->m_src != 0)
_forward(ps1, ps0, 0, false);
else
_forward(ps0, ps1, 0, false);
if (nf != f0 && nf != f1)
{
_dereference(ref ps0);
return _duplex_node(ps0, _init_tfs_node(tm.type_arr[(int)(nf & Edge.Flag.MultiIdMask)].Expanded));
}
}
return true;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
bool _duplex_node_count(Scratch* ps0, Scratch* ps1, int suppress)
{
Edge.Flag f0, f1, nf;
if ((f0 = ps0->f) == (f1 = ps1->f) || f1 == 0)
nf = f0;
else if (f0 == 0)
nf = f1;
else if ((nf = tm.UnifyTypesNoCoref(f0, f1)) == Edge.Flag.Bottom)
return false;
if ((nf & Edge.Flag.EtmNonBareType) == 0)
{
_join_counts(ps1, ps0, suppress);
_forward(ps1, ps0, nf, false);
}
else
{
if (ps0->m_src != 0 && ps1->m_src != 0)
{
#if DEBUG
Debug.Assert(ps0 != ps1);
_check_args(nf, ps0, ps1);
#endif
int missing0 = 0, missing1 = 0;
int suppress0 = ps0->c_visits == 0 ? 0 : 1;
int suppress1 = ps1->c_visits == 0 ? 0 : 1;
ArrayTfs tfs0 = participants[ps0->tfsix];
ArrayTfs tfs1 = participants[ps1->tfsix];
ushort* pfix = rgpfix[(int)(nf & Edge.Flag.MultiIdMask)], pfix_end = *pfix++ + pfix;
do
{
#if DEBUG && FEATURE_PATH
_change_stack_top(*pfix);
#endif
Scratch* nps0 = _fallback_fetch(tfs0, ps0, *pfix);
Scratch* nps1 = _fallback_fetch(tfs1, ps1, *pfix);
#if DEBUG
_debug_nps(ps0, ps1, nps0, nps1);
#endif
if (nps0 == nps1)
{
if (nps0 != null)
_register_count(nps0, suppress0 + suppress1);
}
else if (nps0 == null)
{
missing0++;
if (nps1->c_visits == 0 && (nps1->f & Edge.Flag.EtmNonBareType) != 0)
_unpaired_body_count(nps1);
_register_count(nps1, suppress1);
}
else if (nps1 == null)
{
missing1++;
if (nps0->c_visits == 0 && (nps0->f & Edge.Flag.EtmNonBareType) != 0)
_unpaired_body_count(nps0);
_register_count(nps0, suppress0);
}
else if (!_duplex_node_count(nps0, nps1, suppress0 + suppress1))
return false;
}
while (++pfix < pfix_end);
#if DEBUG && FEATURE_PATH
if (stk != null) stk.Pop();
#endif
if (missing0 <= missing1)
{
_join_counts(ps1, ps0, suppress);
_forward(ps1, ps0, nf, missing0 != 0);
}
else
{
_join_counts(ps0, ps1, suppress);
_forward(ps0, ps1, nf, missing1 != 0);
}
}
else if (ps0->m_src != 0)
{
if (ps0->c_visits == 0)
_unpaired_body_count(ps0);
_join_counts(ps1, ps0, suppress);
_forward(ps1, ps0, 0, false);
}
else
{
if (ps1->c_visits == 0)
_unpaired_body_count(ps1);
_join_counts(ps0, ps1, suppress);
_forward(ps0, ps1, 0, false);
}
if (nf != f0 && nf != f1)
{
_dereference(ref ps0);
return _duplex_node_count(ps0, _init_tfs_node(tm.type_arr[(int)(nf & Edge.Flag.MultiIdMask)].Expanded), 1);
}
}
return true;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void _unpaired_body_count(Scratch* ps)
{
int suppress = ps->c_visits != 0 ? 1 : 0;
ArrayTfs tfs = participants[ps->tfsix];
ushort* pfix = rgpfix[(int)(ps->f & Edge.Flag.MultiIdMask)], pfix_end = *pfix++ + pfix;
do
{
#if DEBUG && FEATURE_PATH
if (stk != null) stk.Push(*pfix);
#endif
Scratch* nps;
if ((nps = _fallback_fetch(tfs, ps, *pfix)) != null)
{
#if DEBUG
_debug_nps_single(ps, nps);
#endif
if (nps->c_visits == 0)
{
if ((nps->f & Edge.Flag.EtmNonBareType) != 0)
_unpaired_body_count(nps);
}
else if (nps->c_visits < 0)
nps->c_visits = 0;
_register_count(nps, suppress);
}
#if DEBUG && FEATURE_PATH
if (stk != null) stk.Pop();
#endif
}
while (++pfix < pfix_end);
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void _forward(Scratch* ps_src, Scratch* ps_dst, Edge.Flag f_dst, bool f_cross)
{
Debug.Assert(ps_src != ps_dst && ps_src->forward >= 0 && ps_dst->forward >= 0);
Debug.Assert(!f_cross || ps_src->m_src != 0);
int src_fw, dst_fw;
if ((dst_fw = ps_dst->forward) == 0)
dst_fw = (int)(ps_dst - ps_base);
if (f_cross)
{
if ((src_fw = ps_src->forward) == 0)
src_fw = (int)(ps_src - ps_base);
ps_dst->forward = (short)src_fw; /// O O -> OO -> O
}
ps_src->forward = (short)-dst_fw; /// O O -> __O
if (f_dst != 0)
ps_dst->f = f_dst;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void _register_count(Scratch* ps, int suppress)
{
Debug.Assert(ps->c_visits >= 0);
if (--suppress == 0)
return;
if (ps->f == 0)
{
int n, o;
ps->c_visits = (short)(n = (o = ps->c_visits) - suppress);
if (o > 1 && n <= 1)
c_edges += suppress;
else if (o <= 1 && n > 1)
c_edges -= suppress - 1;
else
c_edges -= suppress;
}
else
{
ps->c_visits -= (short)suppress;
c_edges -= suppress;
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void _join_counts(Scratch* ps_src, Scratch* ps_dst, int suppress)
{
int c_src;
if ((c_src = ps_src->c_visits) != 0 && ps_src->f != 0)
c_edges -= c_src;
if (ps_src->f == 0)
suppress--;
_register_count(ps_dst, suppress - c_src);
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void _dereference(ref Scratch* ps)
{
while (ps->forward < 0)
ps = ps_base - ps->forward;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Scratch* _init_tfs_node(Tfs tfs)
{
TfsSection ts = tfs as TfsSection;
int tfsix = _add_tfs(ts != null ? (ArrayTfs)ts.mother : (ArrayTfs)tfs);
Scratch* ps = bases[tfsix];
_init_node(ps, tfsix, tfs.Edge);
return ps;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
int _add_tfs(ArrayTfs atfs)
{
Debug.Assert(c_participants <= MaxParticipants);
int tfsix, offs, c;
participants[tfsix = ++c_participants] = atfs;
c = _slot_count(atfs, &offs);
bases[tfsix] = next_base + offs;
next_base += c;
#if DEBUG
if ((int)(next_base - ps_base) >= c_slot_alloc)
throw new Exception();
#endif
return tfsix;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
static int _slot_count(Tfs tfs, int* offs_out)
{
TfsSection ts = tfs as TfsSection;
if (ts != null)
tfs = ts.mother;
ArrayTfs atfs = (ArrayTfs)tfs;
int offs = -(atfs.next_coref_mark + 1);
if (offs_out != null)
*offs_out = offs;
return offs + 1 + atfs.ScratchAlloc;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public MotherDaughterTfs UnifySections(MotherDaughterTfs mother, int i_first_arg, Tfs[] candidates)
{
Debug.Assert(mother.Edge.Mark == TopmostMark);
Debug.Assert((mother.Edge.FlagsId & Edge.Flag.EtmNonBareType) != 0);
Debug.Assert(mother.RuleDaughters.Length == 2); // temp
c_slot_alloc = 1 + _slot_count(mother, null) +
_slot_count(candidates[0], null) +
_slot_count(candidates[1], null) +
WellFormedSlots;
Scratch** _pp = stackalloc Scratch*[MaxParticipants];
bases = _pp - 1;
Scratch* _ps = stackalloc Scratch[c_slot_alloc];
ps_base = _ps;
next_base = ps_base + 1; // don't use global slot zero
#if DEBUG
for (int i = 0; i < c_slot_alloc; i++, ps_base++)
ps_base->_this = ps_base;
ps_base = _ps;
#endif
c_edges = -1;
Scratch* ps_m = _init_tfs_node(mother);
for (int i = 0; i < candidates.Length; i++)
{
TfsSection daughter = mother.RuleDaughters[i_first_arg++];
Scratch* ps_d = ps_m + (daughter.Edge.Mark < 0 ? daughter.Edge.Mark : daughter.MotherSlotIndex);
_init_node(ps_d, ps_m->tfsix, daughter.Edge);
Scratch* ps_c = _init_tfs_node(candidates[i]);
if (f_args_delete)
{
if (!_duplex_node(ps_d, ps_c))
return null;
}
else
{
if (!_duplex_node_count(ps_d, ps_c, 0))
return null;
}
/// adjust counts for daughter repetition
_dereference(ref ps_d);
if (f_args_delete)
{
if (ps_d->c_visits < 0)
c_edges -= ps_d->c_visits;
}
else
{
Debug.Assert(ps_d->c_visits > 0);
ps_d->c_visits--;
}
}
/// mother completion
_unpaired_body_count(ps_m);
_register_count(ps_m, 0);
return _write_tfs(ps_m);
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public MotherDaughterTfs UnifySection(TfsSection daughter, Tfs candidate)
{
MotherDaughterTfs mother = (MotherDaughterTfs)daughter.mother;
Debug.Assert(mother.Edge.Mark == TopmostMark);
Debug.Assert(daughter.Edge.Mark != TopmostMark);
Debug.Assert((mother.Edge.FlagsId & Edge.Flag.EtmNonBareType) != 0);
c_slot_alloc = 1 + _slot_count(mother, null) + _slot_count(candidate, null) + WellFormedSlots;
Scratch** _pp = stackalloc Scratch*[MaxParticipants];
bases = _pp - 1;
Scratch* _ps = stackalloc Scratch[c_slot_alloc];
ps_base = _ps;
next_base = ps_base + 1; // don't use global slot zero
#if DEBUG
for (int i = 0; i < c_slot_alloc; i++, ps_base++)
ps_base->_this = ps_base;
ps_base = _ps;
#endif
/// initialization
int dm = daughter.Edge.Mark;
Scratch* ps_m = _init_tfs_node(mother);
Scratch* ps_c = _init_tfs_node(candidate);
Scratch* ps_d = ps_m + (dm < 0 ? dm : daughter.MotherSlotIndex);
_init_node(ps_d, ps_m->tfsix, daughter.Edge);
/// forwarding pass
c_edges = -1;
if (f_args_delete)
{
if (!_duplex_node(ps_d, ps_c))
return null;
}
else
{
if (!_duplex_node_count(ps_d, ps_c, 0))
return null;
}
/// mother completion
_unpaired_body_count(ps_m);
_register_count(ps_m, 0);
/// adjust counts for daughter repetition
_dereference(ref ps_d);
if (f_args_delete)
{
if (ps_d->c_visits < 0)
c_edges -= ps_d->c_visits;
}
else
{
Debug.Assert(ps_d->c_visits > 0);
ps_d->c_visits--;
}
//Debug.Assert(c_edges >= i_ate, "Count failed", "c_edges: {0} actual: {1} Input: {2}", c_edges, i_ate, ctrl.ts_input.Source.Text);
//if (c_edges < i_ate)
// Nop.X();
//if (c_edges - i_ate > 1)
// Nop.X();
////Debug.Assert(i_ate == c_edges);
//if (i_ate != c_edges)
// Nop.X();
//else
// Console.Write(".");
#if CHECK_COUNTS
_check_counts(entries, ps_m);
#endif
return _write_tfs(ps_m);
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
MotherDaughterTfs _write_tfs(Scratch* ps_m)
{
arr_tfs_entry[] entries = new arr_tfs_entry[c_edges];
ushort[] hidx = new ushort[256];
ushort[] rgn = new ushort[c_edges];
fixed (arr_tfs_entry* __pate = entries)
fixed (ushort* __hidx = hidx)
fixed (ushort* __rgn = rgn)
{
i_ate = 0;
_pate = __pate;
_hidx = __hidx;
_rgn = __rgn;
_write_node(ps_m, TopmostMark);
}
return new MotherDaughterTfs(ctrl,
new Edge(ps_m->f, TopmostMark),
entries,
hidx,
rgn,
next_mark,
next_coref_mark,
f_restrict);
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void _write_node(Scratch* ps, int m_dst)
{
ArrayTfs tfs = participants[ps->tfsix];
ushort* pfix = rgpfix[(int)(ps->f & Edge.Flag.MultiIdMask)], pfix_end = *pfix++ + pfix;
do
{
Scratch* nps = _fallback_fetch(tfs, ps, *pfix);
if (nps != null)
{
int m, c = nps->c_visits;
Debug.Assert(c > 0 || (c < 0 && f_args_delete));
if (c < 0)
c = 1;
if ((m = nps->m_copy) == 0)
{
bool non_bare = (nps->f & Edge.Flag.EtmNonBareType) != 0;
if (c > 1)
{
m = nps->m_copy = (short)next_coref_mark--;
nps->f |= Edge.Flag.Coreference;
}
else if (nps->f == 0)
continue;
else if (non_bare)
m = nps->m_copy = (short)next_mark++;
if (non_bare)
_write_node(nps, m);
}
_pate->i_feat = *pfix;
_pate->mark = m_dst;
_pate->e_FlagsId = nps->f;
_pate->e_Mark = m;
_pate++;
if (++i_ate > c_edges)
throw new Exception("internal error counting edges. input: " + ctrl.ts_input.Source.Text);
ushort* pus = _hidx + (byte)(*pfix + m_dst);
*_rgn++ = *pus;
*pus = (ushort)i_ate;
}
}
while (++pfix < pfix_end);
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public bool Check(Tfs tfs0, Tfs tfs1)
{
c_slot_alloc = 1 + _slot_count(tfs0, null) + _slot_count(tfs1, null) + WellFormedSlots;
Scratch** _pp = stackalloc Scratch*[MaxParticipants];
bases = _pp - 1;
Scratch* _ps = stackalloc Scratch[c_slot_alloc];
ps_base = _ps;
next_base = ps_base + 1; // don't use global slot zero
#if DEBUG
for (int i = 0; i < c_slot_alloc; i++, ps_base++)
ps_base->_this = ps_base;
ps_base = _ps;
#endif
return _duplex_node(_init_tfs_node(tfs0), _init_tfs_node(tfs1));
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
partial struct Scratch
{
[DebuggerBrowsable(DebuggerBrowsableState.Never)]
public Edge.Flag f;
[DebuggerBrowsable(DebuggerBrowsableState.Never)]
public int m_src;
[DebuggerBrowsable(DebuggerBrowsableState.Never)]
public short forward;
[DebuggerBrowsable(DebuggerBrowsableState.Never)]
public short tfsix;
[DebuggerBrowsable(DebuggerBrowsableState.Never)]
public short c_visits;
[DebuggerBrowsable(DebuggerBrowsableState.Never)]
public short m_copy;
#if DEBUG
[DebuggerBrowsable(DebuggerBrowsableState.Never)]
public Scratch* _this;
#endif
};
};
}