using System;
using System.Collections.Generic;
using System.Text;
using System.Reflection;
using System.Reflection.Emit;

namespace ParserJitting
{
    public class Program
    {
        // a few sample predicates, we will use these in a loop to simulate more of them
        private static string[] predicates = {
                "fact1",
                "fact2",
                "fact3",
                "fact2 & fact1",
                "fact3 & fact2",
                "fact4 | fact5",
                "!fact4 & fact5",
                "!(fact1 & fact2) | !fact5",
            };

        // it ain't object oriented but it's only a benchmark :)
        private static int ichInput = 0;
        private static string strInput = null;
        private static string strLookaheadToken = null;
        private static Dictionary<String, int> dictFacts = new Dictionary<String,int>();
       
        public static bool[] truthTable = null;

        static void Main(string[] args)
        {
            int len = predicates.Length;

            int i;

            List<BooleanDelegate> compList = new List<BooleanDelegate>();

            // compile the predicates
            for (i = 0; i< len; i++)
            {
                compList.Add(CompilePredicate(predicates[i]));
            }

            BooleanDelegate[] compiledPredicates = compList.ToArray();

            truthTable = new bool[dictFacts.Count];

            // these few prime numbered facts are in the fact table
            // therefore they are "true"
            SetFact("fact2");
            SetFact("fact3");
            SetFact("fact5");
            SetFact("fact7");
            SetFact("fact11");
            SetFact("fact13");
            SetFact("fact17");
            SetFact("fact19");

            // dump some test evaluations so we can be sure things are working ok
            for (i = 0; i< len; i++)
                Console.WriteLine("{0} => {1}", predicates[i], compiledPredicates[i]());

            System.Diagnostics.Stopwatch clock = new System.Diagnostics.Stopwatch();

            clock.Start();

            // the real benchmark
            for (int j = 0; j < 1000000; j++)
                for (i = 0; i< len; i++)
                    compiledPredicates[i]();

            clock.Stop();

            Console.WriteLine("time {0:n0}ms", clock.ElapsedMilliseconds);
        }

        // ultra lame exception class, please do better than this in your code :)
        class ParseException : Exception
        {
            public ParseException() : base("Syntax Error")
            {
            }
        }

        static int predCount = 0;
        static ILGenerator il;
        delegate bool BooleanDelegate();

        // Compile a simple boolean predicate
        static BooleanDelegate CompilePredicate(string predicate)
        {
            strInput = predicate;
            ichInput = 0;
            strLookaheadToken = null;

            string strName = String.Format("pred{0}", predCount++);

            DynamicMethod dm = new DynamicMethod(strName , typeof(bool), new Type[] {}, typeof(Program), true);
            il = dm.GetILGenerator();

            CompileOr();
            il.Emit(OpCodes.Ret);
            return (BooleanDelegate)dm.CreateDelegate(typeof(BooleanDelegate));
        }

        // this starts the recursive descent parser -- or is the outer clause
        // the other clauses happen in the natural order (outermost first)
        static void CompileOr()
        {
            CompileAnd();

            for (; ;)
            {
                string s = PeekToken();
                if (s == null)
                    break;

                if (s != "|")
                    break;

                ReadToken();

                CompileAnd();

                il.Emit(OpCodes.Or);
            }
        }

        static void CompileAnd()
        {
            CompileOptionalNot();

            for (; ; )
            {
                string s = PeekToken();
                if (s == null)
                    break;

                if (s != "&")
                    break;

                ReadToken();

                CompileOptionalNot();

                il.Emit(OpCodes.And);
            }
        }

        static void CompileOptionalNot()
        {
            bool invert = false;
            string s = PeekToken();

            while (s == "!")
            {
                invert = !invert;
                ReadToken();
                s = PeekToken();
            }

            CompileFact();

            if (invert)
                il.Emit(OpCodes.Not);
        }

        static void CompileFact()
        {
            string s = ReadToken();

            if (s == null)
                throw new ParseException();

            if (s == "(")
            {
                CompileOr();
                s = ReadToken();
                if (s != ")")
                    throw new ParseException();
            }
            else
            {
                string fact = s;
                if (fact == null)
                    throw new ParseException();

                int ifact = GetFactNumber(fact);

                il.Emit(OpCodes.Ldsfld, typeof(Program).GetField("truthTable"));
                il.Emit(OpCodes.Ldc_I4, ifact);
                il.Emit(OpCodes.Ldelem_I1);
            }
        }

        // reuse the lookahead if there is one, this consumes a token
        static string ReadToken()
        {
            if (strLookaheadToken == null)
            {
                PeekToken();
            }

            string ret = strLookaheadToken;
            strLookaheadToken = null;
            return ret;
        }

        // this sets up the lookahead token without actually consuming it
        static string PeekToken()
        {
            // give back the lookahead token again if we already computed it
            if (strLookaheadToken != null)
                return strLookaheadToken;

            strLookaheadToken = GetToken();

            return strLookaheadToken;
        }

        // this reads a token from the input stream and is unaware of lookahead concerns
        static string GetToken()
        {
            if (ichInput >= strInput.Length)
                return null;

            char ch = '\0';

            for (; ; )
            {
                ch = getc();
                if (ch != ' ' && ch != '\t')
                    break;
            }

            int idx = ichInput - 1;

            if (ch >= 'a' && ch <= 'z' ||
              ch >= 'A' && ch <= 'Z' ||
              ch == '_')
            {

                while ('\0' != (ch = getc()))
                    if (ch >= 'a' && ch <= 'z' ||
                      ch >= 'A' && ch <= 'Z' ||
                      ch >= '0' && ch <= '9' ||
                      ch == '_')
                        continue;
                    else
                        break;

                if (ch != '\0') ichInput--;
                return strInput.Substring(idx, ichInput - idx);
            }

            // the single character tokens for valid operators
            switch (ch)
            {
                case '!': case '&': case '|': case '(': case ')':
                    return strInput.Substring(idx, 1);
            }

            // error token
            return null;
        }

        // fetch the next character from the input stream
        static char getc()
        {
            if (ichInput >= strInput.Length)
                return '\0';

            return strInput[ichInput++];
        }

        // fixed size stack -- we could do better if we needed to but
        // this is good enough for this test
        static bool[] evalStack = new bool[16];
        static int GetFactNumber(string fact)
        {
            if (!dictFacts.ContainsKey(fact))
                dictFacts.Add(fact, dictFacts.Count);

            return dictFacts[fact];
        }

        static void SetFact(string fact)
        {
            // facts that are mentioned in no predicates may be disregarded
            if (!dictFacts.ContainsKey(fact))
                return;

            truthTable[dictFacts[fact]] = true;
        }
   }
}