Interpreter.cs

Go to the documentation of this file.

using Mercury.Nucleus.Trees;
using Mercury.Syntax;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.Caching;
using System.Threading.Tasks;

namespace Mercury.Interpreting
{
//=============================================================================
//  IInterpreter
//=============================================================================

    public interface IInterpreter<T> where T : class
    {
        RewriteRuleCollection<T> RewriteRules { get; }

        InterpreterResult<T> Interpret(Tree<Symbol> tree);


        IReadOnlyList<InterpreterResult<T>> Interpret(IReadOnlyList<Tree<Symbol>> trees);
    }

//=============================================================================
//  Interpreter
//=============================================================================

    public class Interpreter<T> : IInterpreter<T> where T : class
    {
        //--[  Private fields  ]-----------------------------------------------

        private IInterpreterContextFactory contextFactory;
        private bool logging;
        private int  boostlim;

        //--[  Private types  ]------------------------------------------------

        #region [  Wildcard Context     ]

        private struct WildcardContext
        {
            public Wildcard wildcard; // wildcard
            public int      strcix;   // index in structure
            public int      treeix;   // start subtree index
            public int      treecnt;  // subtree count
            public int      instcnt;  // instances count

            public WildcardContext(Wildcard w, int six, int tix, int tc, int ic)
            {
                wildcard = w;
                strcix   = six; treeix   = tix;
                treecnt  = tc;  instcnt  = ic;
            }
        }

        #endregion

        //--[  Private methods  ]----------------------------------------------

        #region [  Structure matching   ]

        // Instantiate wrapper
        private bool Instantiate(IElement element, Tree<Symbol> tree, InstanceList instances)
        {
            switch(element.Type)
            {
                case ElementType.Constant:  return Instantiate(element as Constant,  tree, instances);
                case ElementType.Variable:  return Instantiate(element as Variable,  tree, instances);
                case ElementType.Structure: return Instantiate(element as Structure, tree, instances);
                default:                    return false;
            }
        }

        // Instantiates constant
        private bool Instantiate(Constant constant, Tree<Symbol> tree, InstanceList instances)
        { return constant.MatchesSymbol(tree.Value); }

        // Instantiates variable
        private bool Instantiate(Variable variable, Tree<Symbol> tree, InstanceList instances)
        {
            if (!variable.MatchesSymbol(tree.Value))
                return false;

            instances.Add(new Instance(variable, tree));
            return true;
        }

        // Instantiates structure and all subelemenets recursively
        private bool Instantiate(Structure structure, Tree<Symbol> tree, InstanceList instances)
        {
            int scc = structure.Children.Count;
            int tcc = tree.Children.Count;

            if (!structure.HasWildcard && (scc != tcc)) return false;

            int strcix = 0, treeix = 0;
            Stack<WildcardContext> stack = new Stack<WildcardContext>();

            if ((structure.Value.Type != ElementType.Wildcard) && !Instantiate(structure.Value, tree, instances))
                return false;

            while(true)
            {
                if ((strcix >= scc) && (treeix >= tcc)) break;

                bool status = true;

                Structure strct;
                if ((strcix >= scc) || ((treeix >= tcc) && (structure[strcix].Value.Type != ElementType.Wildcard)))
                    status = false;
                else if ((strct = structure[strcix] as Structure) != null)
                    status = Instantiate(strct, tree[treeix], instances);
                else if (structure[strcix].Value.Type == ElementType.Wildcard)
                {
                    stack.Push(new WildcardContext(
                        structure[strcix].Value as Wildcard,
                        strcix, treeix, 0, instances.Count));
                    instances.Add(new Instance(stack.Peek().wildcard, new Tree<Symbol>[0]));
                    --treeix;
                }
                else
                    status = Instantiate(structure[strcix].Value, tree[treeix], instances);

                if (!status && !Retry(stack, tree, instances, ref strcix, ref treeix))
                    return false;

                ++strcix;
                ++treeix;
            }

            return true;
        }

        // Recovery from wildcard mismatch
        private bool Retry(Stack<WildcardContext> stack, Tree<Symbol> tree, InstanceList instances, ref int sx, ref int tx)
        {
            while(stack.Count != 0)
            {
                WildcardContext context = stack.Pop();
                instances.RemoveLast(instances.Count - context.instcnt);

                sx = context.strcix;
                tx = context.treeix + (context.treecnt++);

                if ((tx >= tree.Children.Count) || !context.wildcard.MatchesSymbol(tree[tx].Value)) 
                    continue;

                var data = new Tree<Symbol>[context.treecnt];
                for (int ix = 0; ix < context.treecnt; ++ix)
                    data[ix] = tree[context.treeix + ix];

                stack.Push(context);
                instances.Add(new Instance(context.wildcard, data));
                return true;
            }

            return false;
        }

        #endregion

        #region [  Argument processing  ]

        private Argument GetArgument(Tree<Symbol> tree, ArgumentType reqtype)
        {
            switch (reqtype & ArgumentType.ParserEntity)
            {
                case ArgumentType.Tree:   return new Argument(ArgumentType.Tree, tree);
                case ArgumentType.Symbol: return new Argument(ArgumentType.Symbol, tree.Value);

                default:
                case ArgumentType.ParserEntity: if (!tree.IsLeaf) goto case ArgumentType.Tree;
                                                else              goto case ArgumentType.Symbol;
            }
        }

        private Argument[] ExpandWildcard(Instance instance, ArgumentType required)
        {
            if (instance.Var == null || !(instance.Var is Wildcard))
                throw new InvalidOperationException("This is not a wildcard");

            var data = instance.Value as Tree<Symbol>[];
            var args = new Argument[data.Length];
            
            for(int ix = 0; ix < data.Length; ++ix)
                args[ix] = GetArgument(data[ix] as Tree<Symbol>, required);

            return args;
        }

        private Argument[] GetArguments(ActionCall<T> call, InstanceList instances, InterpreterContext<T> context)
        {
            List<Argument> args = new List<Argument>();

            for(int ix = 0; ix < call.FormalParameters.Count; ++ix)
            {
                ArgumentType argtype = ArgumentType.TValue;

                switch (call.FormalParameters[ix].Type)
                {
                    case ParameterType.IntegralConstant: argtype = ArgumentType.Integer; goto constant;
                    case ParameterType.RealConstant:     argtype = ArgumentType.Real;    goto constant;
                    case ParameterType.StringConstant:   argtype = ArgumentType.String;  goto constant;
                    case ParameterType.BooleanConstant:  argtype = ArgumentType.Boolean; goto constant;

                    constant:
                        args.Add(new Argument(argtype, (call.FormalParameters[ix] as ConstantParameter).Value));
                        break;

                    case ParameterType.Variable:
                        VariableParameter varparam = call.FormalParameters[ix] as VariableParameter;
                        Instance          instance = instances[varparam.Name];
                        ArgumentType      reqtp    = call.Action.ArgumentTypes.ElementAtOrLast(ix);

                        if (instance.Var.Type == ElementType.Variable)
                            args.Add(GetArgument(instance.Value as Tree<Symbol>, reqtp));
                        else
                            args.AddRange(ExpandWildcard(instance, reqtp));

                        break;

                    case ParameterType.ActionCall:
                        var xcall = call.FormalParameters[ix] as ActionCall<T>;
                        var xargs = GetArguments(xcall, instances, context);
                        var xctp  = call.Action.ArgumentTypes.ElementAtOrLast(ix);

                        args.Add(new Evaluator<T>(xcall.Action, xargs, InterpretTree, context));
                        break;
                }
            }

            return args.ToArray();
        }

        #endregion

        private T ExecuteAction(ActionCall<T> actioncall, InstanceList instances, 
                                InterpreterContext<T> context)
        { return new Evaluator<T>(actioncall.Action, GetArguments(actioncall, instances, context), 
                                  InterpretTree, context).Value as T; }

        private T InterpretTree(Tree<Symbol> tree, InterpreterContext<T> context)
        {
            if (tree == null) return null;

            var tentry = new TreeEntry<T>(tree);

            if (context.hroot == null) context.hroot = tentry;
            else                       context.cnode.Entries.Add(tentry);

            #region [  Caching  ]
            if (context.cache != null)
            {
                var tup = context.cache.Get(tree.CacheKey) as Tuple<T,byte>;
                if (tup != null)
                {
                    tentry.Rules.Add(new MemoEntry<T>() { MemoizedValue = tup.Item1 });
                    tentry.Succeeded = tup.Item1 != null;
                    return tup.Item1;
                }
            }
            #endregion

            var reqtp     = Defaults.TypeToArgType<T, T>();
            var instances = new InstanceList();

            InterpreterContext<T> ctxtcpy = null;
            T result = null;

            foreach (var rule in RewriteRules.RulesFor(tree.Value))
            {
                var rentry = new RuleEntry<T>(rule);
                tentry.Rules.Add(rentry);

                ctxtcpy = context.InternalClone(rentry);
                ctxtcpy.reqtp = reqtp;

                bool match  = Instantiate(rule.LHS, tree, instances);
                if (match && (result = ExecuteAction(rule.RHS, instances, ctxtcpy)) != null)
                    context.InternalCopy(ctxtcpy);

                rentry.Match     = match;
                rentry.Value     = result;
                rentry.Error     = false;
                rentry.Instances = match ? instances : null;

                instances = new InstanceList();

                if (result != null)
                    break;
            }

            #region [  Caching  ]
            if (context.cache != null)
                context.cache.Add(new CacheItem(tree.CacheKey, Tuple.Create(result, (byte)0)),
                   new CacheItemPolicy() { SlidingExpiration = TimeSpan.FromSeconds(20.0) });
            #endregion

            tentry.Succeeded = result != null;
            return result;
        }

        private InterpreterResult<T> Interpret(Tree<Symbol> tree, MemoryCache cache)
        {
            var val     = default(T);
            var ex      = null as Exception;
            var context = contextFactory.CreateContext<T>();
            context.cache = cache;

            try
            { 
                val = InterpretTree(tree, context);
                if (!logging) 
                    context.hroot = null; // GC will take care of that
            }
            catch (Exception e)
            { ex = e; }
            finally
            { context.cache = null; }

            return new InterpreterResult<T>() { Input = tree, Result = val, Exception = ex, Context = context };
        }

        //--[  Constructors  ]-------------------------------------------------

        public Interpreter(RewriteRuleCollection<T> rules, IInterpreterContextFactory factory,
            bool logging = true, int boostlim = 4)
        {
            if (rules == null) throw new ArgumentNullException("rules");

            RewriteRules   = rules;
            contextFactory = factory ?? new EmptyContextFactory();

            this.logging  = logging;
            this.boostlim = boostlim;
        }

        //--[  Properties  ]---------------------------------------------------

        public RewriteRuleCollection<T> RewriteRules { get; private set; }

        //--[  Interface implementation  ]-------------------------------------

        #region [  IInterpreter  ]

        public InterpreterResult<T> Interpret(Tree<Symbol> tree)
        { return Interpret(tree, null); }

        public IReadOnlyList<InterpreterResult<T>> Interpret(IReadOnlyList<Tree<Symbol>> trees)
        {
            var res = new InterpreterResult<T>[trees.Count];

            if (trees.Count >= boostlim)
                using(var cache = new MemoryCache(Extensions.RandomString("TreeCache%*")))
                    Parallel.For(0, trees.Count, x => { res[x] = Interpret(trees[x], cache); });
            else
                for (int ix = 0; ix < res.Length; ++ix)
                    res[ix] = Interpret(trees[ix], null);

            return res;
        }

        #endregion

    }

//=============================================================================
//  SemanticInterpreter
//=============================================================================

    public class SemanticInterpreter<T> : IInterpreter<T>
        where T : class
    {
        //--[  Private fields  ]-----------------------------------------------

        private IInterpreter<Tree<Symbol>> semintr;
        private IInterpreter<T>            finintr;

        //--[  Constructors  ]-------------------------------------------------

        public SemanticInterpreter(IInterpreter<Tree<Symbol>> semintr,
            IInterpreter<T> finintr)
        {
            if (semintr == null) throw new ArgumentNullException("semintr");
            if (finintr == null) throw new ArgumentNullException("finintr");

            this.semintr = semintr;
            this.finintr = finintr;
        }

        //--[  Properties  ]---------------------------------------------------

        public RewriteRuleCollection<Tree<Symbol>> SemanticRules { get { return semintr.RewriteRules; } }

        public RewriteRuleCollection<T> RewriteRules { get { return finintr.RewriteRules; } }

        //--[  Interface implementation  ]-------------------------------------

        #region [  IInterpreter  ]

        public InterpreterResult<T> Interpret(Tree<Symbol> tree)
        {
            try
            {
                var    tmp = semintr.Interpret(tree);
                return tmp.Success ? finintr.Interpret(tmp.Result) : null;
            }
            catch (Exception ex)
            {
                return new InterpreterResult<T>()
                {
                    Context = null,
                    Exception = ex,
                    Input = tree,
                    Result = null
                };
            }
        }

        public IReadOnlyList<InterpreterResult<T>> Interpret(IReadOnlyList<Tree<Symbol>> trees)
        {
            var temp = semintr.Interpret(trees);
            var fin  = finintr.Interpret(temp.Where(x => x.Success).Select(x => x.Result).ToArray());

            var res = new InterpreterResult<T>[trees.Count];
            int loc = 0;
            for(int ix = 0; ix < temp.Count; ++ix)
            {
                if (temp[ix].Success)
                    res[ix] = fin[loc++];
                else
                    res[ix] = new InterpreterResult<T>() 
                    { Context = null, Exception = null, Input = trees[ix], Result = null };
            }

            return res;
        }

        #endregion

    }

}