using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Threading;
using System.Threading.Tasks;
using miew.Enumerable;
using miew.String;
using miew.Debugging;
using miew.Concurrency;
namespace agree
{
public abstract partial class PassiveEdge : ArrayTfs, IParseObj
{
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#if !DEBUG
sealed
#endif
public partial class ParseTree : IDerivation, IList<IDerivation>
{
[DebuggerBrowsable(DebuggerBrowsableState.Never)]
static readonly ParseTree[] _leaf = new ParseTree[0];
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public ParseTree(ParseControl ctrl, IParseObj po, IEnumerable<IDerivation> q)
{
if (po.IsRemove())
throw new Exception();
this.ctrl = ctrl;
this.mother = po;
this.daughters = q == null ? _leaf : q as IDerivation[] ?? q.ToArray();
#if DEBUG
this.id = next_id++;
#endif
}
[DebuggerBrowsable(DebuggerBrowsableState.Never)]
ParseControl ctrl;
[DebuggerBrowsable(DebuggerBrowsableState.Never)]
IParseObj mother;
public IParseObj Source { get { return mother; } }
[DebuggerBrowsable(DebuggerBrowsableState.Never)]
readonly IDerivation[] daughters;
[DebuggerBrowsable(DebuggerBrowsableState.Never)]
Task<Tfs> unpack_task;
Tfs _tfs;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
MotherDaughterTfs Unpack()
{
Derived dpe = mother as Derived;
Debug.Assert(dpe != null);
GrammarRule r = (GrammarRule)dpe.License;
int c = daughters.Length;
Debug.Assert(r.RuleDaughters.Length == c);
if (c > 1 && ctrl.TryEnterMultithread())
{
for (int i = 0; i < c; i++)
if (daughters[i] is ParseTree)
((ParseTree)daughters[i]).UnpackTask();
ctrl.LeaveMultithread();
}
MotherDaughterTfs mdtfs;
if (c > 1)// && ctrl.parser_config.f_variadic_unpack)
{
var rgd = new Tfs[c];
for (int i = 0; i < c; i++)
if ((rgd[i] = daughters[i].UnpackedTfs) == null)
return null;
mdtfs = ctrl.UnifySections(r.RuleTfs, 0, rgd, true, false, ref ctrl.stats.Parsing.Unpacking.Unification);
if (mdtfs == null)
return null;
}
else
{
mdtfs = r.RuleTfs;
for (int i = 0; i < c; i++)
{
Tfs candidate = daughters[i].UnpackedTfs;
if (candidate == null)
return null;
mdtfs = ctrl.UnifySection(mdtfs.RuleDaughters[i], candidate, i == c - 1, false, ref ctrl.stats.Parsing.Unpacking.Unification);
if (mdtfs == null)
return null;
}
}
/// done if the mother wasn't tagged as Completed
Completed cp = mother as Completed;
if (cp == null)
return mdtfs;
#if CHECK_ALL_SS
foreach (StartSymbol ss in ctrl.g.StartSymbols)
if (ctrl.UnifyCheck((ss.Expanded, mdtfs))
return mdtfs;
#else
/// only need to validate against start symbols that the mother unified with.
bool[] rgss_map = cp.MatchedStartSymbolsMap;
for (int i = 0; i < rgss_map.Length; i++)
if (rgss_map[i])
if (ctrl.UnifyCheck(ctrl.g.StartSymbols[i].Expanded, mdtfs))
return mdtfs;
#endif
/// didn't match any of the eligible start symbols
return null;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
/// the pervasive 'avoiding double work' task pattern: having captured the necessary work
/// for the as-yet unstarted task in the above closure, now only start it if we are the
/// thread that wins a race to publish the Task (closure). Otherwise, our version is
/// discarded and we'll return the (result of) the victor's task.
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Task<Tfs> UnpackTask()
{
if (unpack_task == null)
{
Task<Tfs> _tmp = new Task<Tfs>(Unpack);
if (Interlocked.CompareExchange(ref unpack_task, _tmp, null) == null)
_tmp.Start();
}
return unpack_task;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
[DebuggerBrowsable(DebuggerBrowsableState.Never)]
public Tfs UnpackedTfs
{
get
{
if (_tfs == null)
{
if (ctrl.TryEnterMultithread())
{
_tfs = (unpack_task ?? UnpackTask()).Result;
ctrl.LeaveMultithread();
}
else
_tfs = Unpack();
}
return _tfs;
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
/// Turns out it's not so trivial to get a reliable hash that is fixed for a given subtree, but maintains
/// positional distinctness of sub-derivations when nested recursively in any/all arbitrary future
/// (unforeseen) contexts. The solution here is progressively change the rotation of the daughter
/// hashes (i.e. by argument position) while stamping the hash of the mother rule ('z') into a fixed
/// position (relative to the daughter) every time.
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
[DebuggerBrowsable(DebuggerBrowsableState.Never)]
ulong _dh;
[DebuggerBrowsable(DebuggerBrowsableState.Never)]
public ulong DerivationHash
{
get
{
if (_dh == 0)
{
ulong z, ul = z = (ulong)mother.License.Name.GetHashCode() << 16;
for (int i = 0; i < daughters.Length; i++)
{
int rot = i + 23;
ul = (ul << rot) | (ul >> (64 - rot));
ul += daughters[i].DerivationHash ^ z;
}
_dh = ul;
}
return _dh;
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public String TreeDisplay()
{
Debug.Assert(daughters.Length > 0);
int id = 0;
var uptfs = UnpackedTfs == null ? "**NULL**" : UnpackedTfs.id.ToString("X");
String s = String.Format("{0} {{{1}}} {{{2}}}{3} {4} {{{5}}}",// {6:X}",
mother.TokenSpan,
id.ToString("X"),
mother.Tfs.id.ToString("X"),
mother.Tfs.IsRestricted ? " R" : "",
mother.Tfs.Type.Name,
uptfs
/*, DerivationHash*/) + Environment.NewLine;
foreach (var pt in daughters)
s += pt.TreeDisplay().Indent(4) + Environment.NewLine;
return s;
}
[DebuggerBrowsable(DebuggerBrowsableState.Never)]
public IEnumerable<IDerivation> Descendants
{
get
{
ParseTree dpe;
foreach (IDerivation ipce in this)
{
yield return ipce;
if ((dpe = ipce as ParseTree) != null)
foreach (IDerivation ipce_d in dpe.Descendants)
yield return ipce_d;
}
}
}
[DebuggerBrowsable(DebuggerBrowsableState.Never)]
public IEnumerable<IDerivation> DescendantsAndSelf
{
get
{
yield return this;
foreach (IDerivation ipce in Descendants)
yield return ipce;
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// <summary>
///
/// </summary>
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public IDerivation this[int index]
{
get
{
if (index >= daughters.Length)
throw new ArgumentException();
return daughters[index];
}
set { throw new InvalidOperationException(); }
}
public int IndexOf(IDerivation item) { return Array.IndexOf<IDerivation>(daughters, item); }
public bool Contains(IDerivation item) { return Array.IndexOf<IDerivation>(daughters, item) != -1; }
[DebuggerBrowsable(DebuggerBrowsableState.Never)]
public int Count { get { return daughters.Length; } }
[DebuggerBrowsable(DebuggerBrowsableState.Never)]
public bool IsReadOnly { get { return true; } }
public void CopyTo(IDerivation[] array, int arrayIndex)
{
foreach (var idrv in daughters)
array[arrayIndex++] = idrv;
}
public void Insert(int index, IDerivation item) { throw new InvalidOperationException(); }
public void RemoveAt(int index) { throw new InvalidOperationException(); }
public bool Remove(IDerivation item) { throw new InvalidOperationException(); }
public void Add(IDerivation item) { throw new InvalidOperationException(); }
public void Clear() { throw new InvalidOperationException(); }
public IEnumerator<IDerivation> GetEnumerator()
{
return daughters.AsEnumerable<IDerivation>().GetEnumerator();
}
IEnumerator IEnumerable.GetEnumerator() { return daughters.GetEnumerator(); }
};
};
}