using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using miew.Debugging;
namespace agree
{
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public unsafe partial struct Unification
{
#if DEBUG
[DebuggerDisplay("{_corefs_info(),nq}")]
public _corefs corefs;
int id;
#else
public Dictionary<Int64, UnifCoref> corefs;
#endif
[DebuggerBrowsable(DebuggerBrowsableState.Never)]
public readonly TypeMgr tm;
[DebuggerBrowsable(DebuggerBrowsableState.Never)]
readonly int[][] rgrgfix;
[DebuggerBrowsable(DebuggerBrowsableState.Never)]
public bool f_check_only;
[DebuggerBrowsable(DebuggerBrowsableState.Never)]
public int c_coref_hint;
TargetTfs target;
Unification(TypeMgr tm, int c_edge_hint, int c_coref_hint, bool f_check_only)
{
this.tm = tm;
this.rgrgfix = tm.rgrgfix_autotune;
this.f_check_only = f_check_only;
this.c_coref_hint = c_coref_hint == -1 ? def_coref_hint : c_coref_hint;
this.target = new TargetTfs(tm, def_edge_hint);//c_edge_hint == -1 ? 257 : c_edge_hint); maxes ~433/2011
#if DEBUG
this.id = next_id++;
this.corefs = new _corefs(this.c_coref_hint | 1);
target.corefs = corefs;
corefs.AddTfsArgs(target);
#else
this.corefs = null;
#endif
}
public static int def_coref_hint = 277;
public static int def_edge_hint = 277;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
/// UnifCoref :: runtime dynamic unification equivalence class
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
sealed public partial class UnifCoref
{
public UnifCoref()
{
this.next = this;
}
/// current roll-in of all unifications so far
[DebuggerBrowsable(DebuggerBrowsableState.Never)]
public Edge e_cur;
/// linked loop of other UnifCoref objects of this type which have joined the equivalence class (or reference
/// to self if none)
[DebuggerBrowsable(DebuggerBrowsableState.Never)]
public UnifCoref next;
/// indicates that this instance is in a loop for which the other fields in this structure are
/// superseded by the designated loop master
[DebuggerBrowsable(DebuggerBrowsableState.Never)]
public bool f_redirect;
/// the number of source nodes pointing to this equivalence class (valid for loop master only, and includes
/// nodes which are still associated with non-master UnifCorefs)
public int c_fm;
/// opportunistic cache of some node that points to this equivalence class as a hint for when removing
/// vacuous coreferences. If not provided, then the enclosed mark can be zero, but otherwise the field
/// must be correct.
public FeatMark single_fm;
};
/// <summary>
/// Merge two coreference equivalence classes. The subordinate class is joined into a linked loop which
/// has a single designated master, rather than being removed, because we are avoiding the expense of
/// directly keeping track of all the edges which lead to a given class.
/// </summary>
public bool _merge_corefs(UnifCoref _this, UnifCoref other)
{
/// we do keep accurate _count_ of target edges which lead into a class, and this field is
/// defined as being valid only for the loop master. Here, we sum counts of the joined classes.
_this.c_fm += other.c_fm;
other.c_fm = 0;
/// patch the two loops together into a single loop
UnifCoref uc = other;
while (uc.next != other)
uc = uc.next;
uc.next = _this.next;
_this.next = other;
other.f_redirect = true;
target.c_corefs--;
/// do the unification
if (!_unify(false, target, _this.e_cur, target, other.e_cur, out _this.e_cur))
return false;
other.e_cur = _this.e_cur;
return true;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
/// TFS unification
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
bool _unify(bool f_exp, Tfs tfs1, Edge e1, Tfs tfs2, Edge e2, out Edge e)
{
#if DEBUG
Debug.Assert(tfs1 != tfs2 || !e1.Equals(e2));
TfsEdge _arg1, _arg2;
if (Debugger.IsAttached) { _arg1 = tfs1.GetSectionTfsEdge(e1); _arg2 = tfs2.GetSectionTfsEdge(e2); }
else { _arg1 = default(TfsEdge); _arg2 = default(TfsEdge); }
#endif
Edge.Flag nf, f1 = e1.FlagsId, f2 = e2.FlagsId;
if (f1 == 0 || f1 == f2)
nf = f2;
else if (f2 == 0)
nf = f1;
else if ((nf = tm.UnifyTypes(f1, f2)) == Edge.Flag.Bottom)
{
e = default(Edge);
return false;
}
/// find the best mark to recycle if one or both of the input TFSs are within the target TFS.
/// prefer non-bare and coreferenced edges (in that order), or the edge whose type has more
/// appropriate features, if there are still no deciding factors. if it's still zero after all this,
/// and if a mark is needed because the type is non-bare or the edge is coreferenced, generate a new
/// mark. then, create the new edge.
int m, m1, m2;
bool recyc1, recyc2 = recyc1 = false;
bool b1 = (m1 = e1.Mark) != 0 && tfs1 == target;
bool b2 = (m2 = e2.Mark) != 0 && tfs2 == target;
if (b1 && (!b2 || f2 >= 0 || (f1 < 0 && f1 >= f2)))
{
m = m1;
recyc1 = true;
}
else if (b2)
{
m = m2;
recyc2 = true;
}
else if ((nf & (Edge.Flag.Coreference | Edge.Flag.EtmNonBareType)) != 0)
{
/// promote mark if required. the latter part of this condition is most certainly the case, since
/// we now resolve simple unifications inside the feature body, but it is included for correctness
/// when unifying TFSes which are coreferenced or bare at their root.
m = target.next_mark++;
}
else
m = 0;
e = new Edge(nf, m);
if ((nf & Edge.Flag.EtmNonBareType) == 0)
return true;
/// done with source marks which were needed only by coreferencing, so clear marks for bare types to signal
/// that we don't need to attempt to fetch the corresponding onwards edges
if (m1 != 0 && (f1 & Edge.Flag.EtmNonBareType) == 0)
m1 = 0;
if (m2 != 0 && (f2 & Edge.Flag.EtmNonBareType) == 0)
m2 = 0;
/// initialize edges for one of the sides if it won't be fetched
if (m1 == 0)
e1 = default(Edge);
else if (m2 == 0)
e2 = default(Edge);
#if DEBUG
TfsEdgeSpy _cur1, _cur2;
if (Debugger.IsAttached)
{
_cur1 = new TfsEdgeSpy(tfs1, &e1);
_cur2 = new TfsEdgeSpy(tfs2, &e2);
}
#endif
// (??) if both in target and same mark, zero one of the marks...
b1 = b2 = false;
foreach (int i_feat in rgrgfix[(int)(nf & Edge.Flag.MultiIdMask)])
{
if (m1 != 0)
b1 = tfs1.TryGetEdge(i_feat, m1, out e1); // see ArrayTfs; *top* is actually stored for topmost node (only)
if (m2 != 0)
b2 = tfs2.TryGetEdge(i_feat, m2, out e2);
int nm1, nm2;
if (!b1)
{
if (recyc2 || !b2)
continue;
f1 = 0; nm1 = 0;
f2 = e2.FlagsId; nm2 = e2.Mark;
}
else
{
if (b2)
{
f2 = e2.FlagsId; nm2 = e2.Mark;
}
else
{
if (recyc1)
continue;
f2 = 0; nm2 = 0;
}
f1 = e1.FlagsId; nm1 = e1.Mark;
}
Edge ne;
UnifCoref uc = null;
/// some optimizations are possible if the discovered edges are identical in the target, or bare.
if (nm1 == nm2 && (nm1 == 0 || (f1 == f2 && tfs1 == tfs2 && tfs1 == target)))
{
if (nm1 == 0)
{
if (f1 == 0 || f1 == f2)
nf = f2;
else if (f2 == 0)
nf = f1;
else if ((nf = tm.UnifyTypes(f1, f2)) == Edge.Flag.Bottom)
goto record_failed_feat;
ne = new Edge(nf, 0);
}
else if (f1 < 0)
{
Debug.Assert(recyc1 || recyc2);
corefs.TryGetValue(((long)target.id << 32) | (uint)nm1, out uc);
while (uc.f_redirect)
uc = uc.next;
ne = uc.e_cur;
}
else
ne = e1;
}
else if (f1 >= 0 && f2 >= 0)
{
if (!_unify(f_exp, tfs1, e1, tfs2, e2, out ne))
goto record_failed_feat;
}
else
{
/// when at least one of the two edges is coreferenced, it is always possible to resolve the coreference with no
/// more than one binary unification operation. that is, you'd never have to, say, unify both inputs with an
/// existing equivalence class in two separate operations. see the five cases below.
UnifCoref ud = null;
if (corefs == null ||
((f1 < 0 && corefs.TryGetValue(((long)tfs1.id << 32) | (uint)nm1, out uc)) ==
(f2 < 0 && corefs.TryGetValue(((long)tfs2.id << 32) | (uint)nm2, out ud)) &&
uc == null))
{
#if !DEBUG
if (corefs == null)
corefs = c_coref_hint == -1 ? new Dictionary<Int64, UnifCoref>() : new Dictionary<Int64, UnifCoref>(c_coref_hint | 1);
target.corefs = corefs;
#endif
uc = new UnifCoref();
if (f1 < 0)
corefs.Add(((long)tfs1.id << 32) | (uint)nm1, uc);
if (f2 < 0)
corefs.Add(((long)tfs2.id << 32) | (uint)nm2, uc);
if (!_unify(f_exp, tfs1, e1, tfs2, e2, out uc.e_cur))
goto record_failed_feat;
corefs.Add(((long)target.id << 32) | (uint)uc.e_cur.Mark, uc);
target.c_corefs++;
}
else if (ud == null)
{
while (uc.f_redirect)
uc = uc.next;
if (f2 < 0)
corefs.Add(((long)tfs2.id << 32) | (uint)nm2, uc);
if (!_unify(f_exp, target, uc.e_cur, tfs2, e2, out uc.e_cur))
goto record_failed_feat;
}
else if (uc == null)
{
while (ud.f_redirect)
ud = ud.next;
if (f1 < 0)
corefs.Add(((long)tfs1.id << 32) | (uint)nm1, ud);
if (!_unify(f_exp, tfs1, e1, target, ud.e_cur, out ud.e_cur))
goto record_failed_feat;
uc = ud;
}
else
{
while (uc.f_redirect)
uc = uc.next;
while (ud.f_redirect)
ud = ud.next;
if (uc != ud && !_merge_corefs(uc, ud))
goto record_failed_feat;
}
if (!f_check_only && (f1 >= 0 || !recyc1) && (f2 >= 0 || !recyc2))
{
uc.c_fm++;
uc.single_fm = new FeatMark(i_feat, m);
}
ne = uc.e_cur;
}
/// If the result is not one of the input types and it has features (or if we are expanding the type hierarchy),
/// unify with the constraints on the canonical expanded type
if (((nf = ne.FlagsId) & Edge.Flag.EtmNonBareType) != 0)
{
int ntid = (int)(nf & Edge.Flag.MultiIdMask);
if (f_exp || ((int)(f1 & Edge.Flag.MultiIdMask) != ntid && (int)(f2 & Edge.Flag.MultiIdMask) != ntid))
{
/// the following can change the edge (?)
Tfs tfsx = tm.type_arr[ntid].Expanded.Clone();
#if DEBUG
corefs.AddTfsArgs(tfsx);
#endif
if (!_unify(false, target, ne, tfsx, tfsx.Edge, out ne))
goto record_failed_feat;
}
}
/// persist the new edge.
Debug.Assert(nf != 0);
if ((!recyc1 || ne.Mark != nm1 || nf != f1) && (!recyc2 || ne.Mark != nm2 || nf != f2))
{
if ((recyc1 && b1) || (recyc2 && b2))
{
Debug.Assert(target.ContainsFeatMark(i_feat, m));
target.SetEdge(i_feat, m, ne);
}
else
target.AddEdge(i_feat, m, ne);
}
/// if destructive in the target, remove the edge that wasn't retained
if (recyc1)
{
if (b2 && tfs2 == target)
{
if (!f_check_only && f2 < 0)
{
if (uc == null)
{
corefs.TryGetValue(((long)tfs2.id << 32) | (uint)nm2, out uc);
while (uc.f_redirect)
uc = uc.next;
}
uc.c_fm--;
}
if (!target.RemoveEdge(i_feat, m2))
Debug.Assert(false);
}
}
else if (recyc2)
{
if (b1 && tfs1 == target)
{
if (!f_check_only && f1 < 0)
{
if (uc == null)
{
corefs.TryGetValue(((long)tfs1.id << 32) | (uint)nm1, out uc);
while (uc.f_redirect)
uc = uc.next;
}
uc.c_fm--;
}
if (!target.RemoveEdge(i_feat, m1))
Debug.Assert(false);
}
}
continue;
record_failed_feat:
/// not concerned about volatile writing here; just looking for approximate numbers so its
/// not worth invalidating the CPU caches.
tm.feat_arr[i_feat].c_failures++;
return false;
}
return true;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
TargetTfs _expand_type(Type host_type)
{
Debug.Assert((host_type.m_flags & Type.Flags.HasAnyFeatures) != 0);
IEnumerator<Type> iea = host_type.Parents.Where(p => p.HasAnyFeatures).GetEnumerator();
Tfs tfs1 = host_type.Definition;
Tfs tfs2 = !iea.MoveNext() ? tm.TopTfs : iea.Current.Expanded;
#if DEBUG
corefs.AddTfsArgs(tfs1, tfs2);
#endif
while (true)
{
if (!_unify(true, tfs1, tfs1.Edge, tfs2, tfs2.Edge, out target.Edge))
return null;
if (tfs1 != target)
tfs1 = target;
if (!iea.MoveNext())
break;
tfs2 = iea.Current.Expanded;
#if DEBUG
corefs.AddTfsArgs(tfs2);
#endif
}
return target;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
struct Partial
{
public Partial(TypeMgr tm, TfsSection daughter, Tfs candidate)
{
this.mother = daughter.mother;
this.e_daughter_mark = daughter.Edge.Mark;
this.e_partial = default(Edge);
Debug.Assert(mother.Edge.Mark != 0);
int c_edge_hint = daughter.mother.EdgeCount + candidate.EdgeCount;
#if false
if (mother.c_corefs == -1 || candidate.c_corefs == -1)
throw new NotImplementedException();
int c_coref_hint = mother.c_corefs;
if (candidate.c_corefs > c_coref_hint)
c_coref_hint = candidate.c_corefs;
c_coref_hint *= 4;
u = new Unification(tm, c_edge_hint, c_coref_hint, false);
#else
u = new Unification(tm, c_edge_hint, -1, false);
#endif
}
public Unification u;
public int e_daughter_mark;
public Edge e_partial;
public Tfs mother;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
internal MotherDaughterTfs _unify_section(TfsSection daughter, Tfs candidate, int[] rg_feat_delete)
{
#if DEBUG
u.corefs.AddTfsArgs(mother, candidate);
#endif
if (!u._unify(false, mother, daughter.Edge, candidate, candidate.Edge, out e_partial))
return null;
Debug.Assert(u.corefs != null);
u.target.Edge = new Edge(mother.Edge.FlagsId, u.target.next_mark++);
_copy_remainder(mother.Edge, u.target.Edge.Mark);
return u.target.ToMotherDaughterTfs(rg_feat_delete);
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void _copy_remainder(Edge e, int m_dst)
{
int m = e.Mark;
#if DEBUG
Edge e_original;
if (Debugger.IsAttached) e_original = e;
#endif
foreach (int i_feat in u.rgrgfix[(int)(e.FlagsId & Edge.Flag.MultiIdMask)])
{
if (mother.TryGetEdge(i_feat, m, out e))
{
int m_src = e.Mark;
if (e.FlagsId < 0)
{
UnifCoref uc;
long mother_key = ((long)mother.id << 32) | (uint)m_src;
if (u.corefs.TryGetValue(mother_key, out uc))
{
while (uc.f_redirect)
uc = uc.next;
e = uc.e_cur;
}
else
{
if (m_src == e_daughter_mark)
e = e_partial;
else
{
if (m_src != 0)
m_src = u.target.next_mark++;
_copy_remainder(e, m_src);
e = new Edge(e.FlagsId, m_src);
}
uc = new UnifCoref();
u.target.c_corefs++;
uc.e_cur = e;
u.corefs.Add(mother_key, uc);
u.corefs.Add(((long)u.target.id << 32) | (uint)uc.e_cur.Mark, uc);
}
uc.c_fm++;
uc.single_fm = new FeatMark(i_feat, m_dst);
}
else if (m_src == e_daughter_mark)
e = e_partial;
else if (m_src != 0)
{
m_src = u.target.next_mark++;
_copy_remainder(e, m_src);
e = new Edge(e.FlagsId, m_src);
}
u.target.AddEdge(i_feat, m_dst, e);
}
}
}
}
public static TargetTfs UnifyForceExpand(Tfs tfs1, Tfs tfs2)
{
Unification u = new Unification(tfs1.tm, -1, -1, false);
#if DEBUG
u.corefs.AddTfsArgs(tfs1, tfs2);
#endif
return u._unify(true, tfs1, tfs1.Edge, tfs2, tfs2.Edge, out u.target.Edge) ? u.target : null;
}
public static TargetTfs ExpandType(Type host_type)
{
Unification u = new Unification(host_type.tm, -1, -1, false);
return u._expand_type(host_type);
}
public static MotherDaughterTfs UnifySection(
TfsSection daughter,
Tfs candidate,
bool f_pruning,
bool f_pack_restrict,
ParseControl ctrl)
{
TypeMgr tm = daughter.tm;
Partial up = new Partial(tm, daughter, candidate);
return up._unify_section(daughter, candidate, f_pruning ? ctrl.parser_config.DeletedDaughters : null);
}
public static Boolean Check(Tfs tfs1, Tfs tfs2)
{
Debug.Assert(tfs1 != tfs2);
Edge e;
Unification u = new Unification(tfs1.tm, tfs1.EdgeCount + tfs2.EdgeCount, -1, true);
#if DEBUG
u.corefs.AddTfsArgs(tfs1, tfs2);
#endif
return u._unify(false, tfs1, tfs1.Edge, tfs2, tfs2.Edge, out e);
}
};
}