<commit_before>﻿using Jil.Common;
using Sigil;
using Sigil.NonGeneric;
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Text;
using System.Threading.Tasks;

namespace Jil.Deserialize
{
    internal static class NameAutomata<T>
    {
        static class Helper
        {
            static void Consume(TextReader tr, int ch)
            {
                while (ch != '\"' && ch != -1)
                {
                    ch = tr.Read();
                }
            }

            static char ExpectUnicodeHexQuad(TextReader reader)
            {
                var c = reader.Read();
                if (c != 'u')
                {
                    throw new DeserializationException("Escape sequence expected unicode hex quad", reader);
                }

                return (char)Methods.ReadHexQuad(reader);
            }
        }

        static MethodInfo TextReader_Read = typeof(TextReader).GetMethod("Read", Type.EmptyTypes);
        static MethodInfo Helper_Consume = typeof(Helper).GetMethod("Consume", BindingFlags.Static | BindingFlags.NonPublic);
        static MethodInfo Helper_ExpectUnicodeHexQuad = typeof(Helper).GetMethod("ExpectUnicodeHexQuad", BindingFlags.Static | BindingFlags.NonPublic);

        class Data
        {
            public readonly Action<Action> AddAction;
            public readonly Emit<Func<TextReader, T>> Emit;
            public readonly Action<Emit<Func<TextReader, T>>> DoReturn;
            public readonly Label Start;
            public readonly Label Failure;
            public readonly Local Local_ch;
            public readonly bool SkipWhitespace;
            public readonly bool FoldMultipleValues;
            public readonly bool CaseSensitive;

            public Data
                (Action<Action> addAction
                , Emit<Func<TextReader, T>> emit
                , Action<Emit<Func<TextReader, T>>> doReturn
                , Label start
                , Label failure
                , Local local_ch
                , bool skipWhitespace
                , bool foldMultipleValues
                , bool caseSensitive
                )
            {
                AddAction = addAction;
                Emit = emit;
                DoReturn = doReturn;
                Start = start;
                Failure = failure;
                Local_ch = local_ch;
                SkipWhitespace = skipWhitespace;
                FoldMultipleValues = foldMultipleValues;
                CaseSensitive = caseSensitive;
            }
        }

        [DebuggerDisplay("{Name}")]
        public class AutomataName
        {
            public readonly string Name;
            public readonly Action<Emit<Func<TextReader, T>>> OnFound;

            public AutomataName(string name, Action<Emit<Func<TextReader, T>>> onFound)
            {
                Name = name;
                OnFound = onFound;
            }
        }

        static void FinishName(Data d, AutomataName nameValue, Label onMatchChar)
        {
            d.AddAction(() =>
            {
                d.Emit.MarkLabel(onMatchChar);
                nameValue.OnFound(d.Emit);
                d.DoReturn(d.Emit);
            });
        }

        private static void FoldName(Data d, AutomataName nameValue, Label foldName)
        {
            d.AddAction(() =>
            {
                d.Emit.MarkLabel(foldName);
                nameValue.OnFound(d.Emit);
                d.Emit.Branch(d.Start);
            });
        }

        static void NextChar(Data d, IList<AutomataName> nameValues, int pos, Label onMatchChar)
        {
            var chars =
                nameValues
                .GroupBy(nv => pos >= nv.Name.Length ? -1 : nv.Name[pos])
                .ToList();

            var namesToFinish = new List<Tuple<char, Label>>();
            foreach (var charGroup in chars)
            {
                var ch = charGroup.Key;
                var items = charGroup.ToList();
                if (ch == -1)
                {
                    if (charGroup.Count() != 1)
                    {
                        throw new ApplicationException("");
                    }

                    var completeName = d.Emit.DefineLabel("complete_" + items[0].Name);
                    FinishName(d, items[0], completeName);
                    namesToFinish.Add(Tuple.Create('"', completeName));

                    if (d.SkipWhitespace)
                        namesToFinish.Add(Tuple.Create(' ', onMatchChar));

                    if (d.FoldMultipleValues)
                    {
                        var foldName = d.Emit.DefineLabel("fold_" + items[0].Name);
                        FoldName(d, items[0], foldName);
                        namesToFinish.Add(Tuple.Create(',', foldName));
                    }
                }
                else
                {
                    if (d.SkipWhitespace && pos == 0)
                        namesToFinish.Add(Tuple.Create(' ', onMatchChar));

                    var next = d.Emit.DefineLabel("_" + items[0].Name.Substring(0, pos + 1));
                    if (d.CaseSensitive)
                    {
                        namesToFinish.Add(Tuple.Create((char)ch, next));
                    }
                    else
                    {
                        var lower = char.ToLower((char)ch);
                        var upper = char.ToUpper((char)ch);
                        namesToFinish.Add(Tuple.Create(lower, next));
                        namesToFinish.Add(Tuple.Create(upper, next));
                    }
                    NextChar(d, items, pos + 1, next);
                }
            }

            d.AddAction(() =>
            {
                d.Emit.MarkLabel(onMatchChar);

                d.Emit.LoadArgument(0);
                d.Emit.CallVirtual(TextReader_Read);
                d.Emit.StoreLocal(d.Local_ch);

                DoBranches(d, namesToFinish);

                d.Emit.LoadLocal(d.Local_ch);               // char
                d.Emit.LoadConstant('\\');                  // char char
                d.Emit.UnsignedBranchIfNotEqual(d.Failure); // 
                d.Emit.LoadArgument(0);                     // TextReader
                d.Emit.Call(Helper_ExpectUnicodeHexQuad);   // char
                d.Emit.StoreLocal(d.Local_ch);              //

                DoBranches(d, namesToFinish);

                d.Emit.Branch(d.Failure);
            });
        }

        static void DoBranches(Data d, List<Tuple<char, Label>> namesToFinish)
        {
            // TODO: optimize this; use 'switch' and/or binary split depending on number/layout of characters
            foreach (var item in namesToFinish)
            {
                d.Emit.LoadLocal(d.Local_ch);
                d.Emit.LoadConstant((int)item.Item1);
                d.Emit.BranchIfEqual(item.Item2);
            }<commit_msg>get started on smarter individual character matching in NameAutomata<commit_after>﻿using Jil.Common;
using Sigil;
using Sigil.NonGeneric;
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Text;
using System.Threading.Tasks;

namespace Jil.Deserialize
{
    internal static class NameAutomata<T>
    {
        static class Helper
        {
            static void Consume(TextReader tr, int ch)
            {
                while (ch != '\"' && ch != -1)
                {
                    ch = tr.Read();
                }
            }

            static char ExpectUnicodeHexQuad(TextReader reader)
            {
                var c = reader.Read();
                if (c != 'u')
                {
                    throw new DeserializationException("Escape sequence expected unicode hex quad", reader);
                }

                return (char)Methods.ReadHexQuad(reader);
            }
        }

        static MethodInfo TextReader_Read = typeof(TextReader).GetMethod("Read", Type.EmptyTypes);
        static MethodInfo Helper_Consume = typeof(Helper).GetMethod("Consume", BindingFlags.Static | BindingFlags.NonPublic);
        static MethodInfo Helper_ExpectUnicodeHexQuad = typeof(Helper).GetMethod("ExpectUnicodeHexQuad", BindingFlags.Static | BindingFlags.NonPublic);

        class Data
        {
            public readonly Action<Action> AddAction;
            public readonly Emit<Func<TextReader, T>> Emit;
            public readonly Action<Emit<Func<TextReader, T>>> DoReturn;
            public readonly Label Start;
            public readonly Label Failure;
            public readonly Local Local_ch;
            public readonly bool SkipWhitespace;
            public readonly bool FoldMultipleValues;
            public readonly bool CaseSensitive;

            public Data
                (Action<Action> addAction
                , Emit<Func<TextReader, T>> emit
                , Action<Emit<Func<TextReader, T>>> doReturn
                , Label start
                , Label failure
                , Local local_ch
                , bool skipWhitespace
                , bool foldMultipleValues
                , bool caseSensitive
                )
            {
                AddAction = addAction;
                Emit = emit;
                DoReturn = doReturn;
                Start = start;
                Failure = failure;
                Local_ch = local_ch;
                SkipWhitespace = skipWhitespace;
                FoldMultipleValues = foldMultipleValues;
                CaseSensitive = caseSensitive;
            }
        }

        [DebuggerDisplay("{Name}")]
        public class AutomataName
        {
            public readonly string Name;
            public readonly Action<Emit<Func<TextReader, T>>> OnFound;

            public AutomataName(string name, Action<Emit<Func<TextReader, T>>> onFound)
            {
                Name = name;
                OnFound = onFound;
            }
        }

        static void FinishName(Data d, AutomataName nameValue, Label onMatchChar)
        {
            d.AddAction(() =>
            {
                d.Emit.MarkLabel(onMatchChar);
                nameValue.OnFound(d.Emit);
                d.DoReturn(d.Emit);
            });
        }

        private static void FoldName(Data d, AutomataName nameValue, Label foldName)
        {
            d.AddAction(() =>
            {
                d.Emit.MarkLabel(foldName);
                nameValue.OnFound(d.Emit);
                d.Emit.Branch(d.Start);
            });
        }

        static void NextChar(Data d, IList<AutomataName> nameValues, int pos, Label onMatchChar)
        {
            var chars =
                nameValues
                .GroupBy(nv => pos >= nv.Name.Length ? -1 : nv.Name[pos])
                .ToList();

            var namesToFinish = new List<Tuple<char, Label>>();
            foreach (var charGroup in chars)
            {
                var ch = charGroup.Key;
                var items = charGroup.ToList();
                if (ch == -1)
                {
                    if (charGroup.Count() != 1)
                    {
                        throw new ApplicationException("");
                    }

                    var completeName = d.Emit.DefineLabel("complete_" + items[0].Name);
                    FinishName(d, items[0], completeName);
                    namesToFinish.Add(Tuple.Create('"', completeName));

                    if (d.SkipWhitespace)
                        namesToFinish.Add(Tuple.Create(' ', onMatchChar));

                    if (d.FoldMultipleValues)
                    {
                        var foldName = d.Emit.DefineLabel("fold_" + items[0].Name);
                        FoldName(d, items[0], foldName);
                        namesToFinish.Add(Tuple.Create(',', foldName));
                    }
                }
                else
                {
                    if (d.SkipWhitespace && pos == 0)
                        namesToFinish.Add(Tuple.Create(' ', onMatchChar));

                    var next = d.Emit.DefineLabel("_" + items[0].Name.Substring(0, pos + 1));
                    if (d.CaseSensitive)
                    {
                        namesToFinish.Add(Tuple.Create((char)ch, next));
                    }
                    else
                    {
                        var lower = char.ToLower((char)ch);
                        var upper = char.ToUpper((char)ch);
                        namesToFinish.Add(Tuple.Create(lower, next));
                        namesToFinish.Add(Tuple.Create(upper, next));
                    }
                    NextChar(d, items, pos + 1, next);
                }
            }

            d.AddAction(() =>
            {
                d.Emit.MarkLabel(onMatchChar);

                d.Emit.LoadArgument(0);
                d.Emit.CallVirtual(TextReader_Read);
                d.Emit.StoreLocal(d.Local_ch);

                DoCharBranches(d, namesToFinish);

                d.Emit.LoadLocal(d.Local_ch);               // char
                d.Emit.LoadConstant('\\');                  // char char
                d.Emit.UnsignedBranchIfNotEqual(d.Failure); // 
                d.Emit.LoadArgument(0);                     // TextReader
                d.Emit.Call(Helper_ExpectUnicodeHexQuad);   // char
                d.Emit.StoreLocal(d.Local_ch);              //

                DoCharBranches(d, namesToFinish);

                d.Emit.Branch(d.Failure);
            });
        }

        static void DoCharBranches(Data d, List<Tuple<char, Label>> namesToFinish)
        {
            // TODO: these different approaches start at random constants
            //       actually get some rigor behind when we decide to do either

            var groups = SplitIntoContiguousGroups(namesToFinish);

            var switches = groups.Where(g => g.Count >= 5).ToList();

            foreach (var needsSwitch in switches)
            {
                DoCharSwitch(d, needsSwitch);
            }

            var remainingNamesToFinish = namesToFinish.Where(t => !switches.Any(s => s.Any(x => x.Item1 == t.Item1))).ToList();

            if (remainingNamesToFinish.Count >= 5)
            {
                DoCharBinarySearch(d, remainingNamesToFinish);
            }
            else
            {
                foreach (var item in remainingNamesToFinish)
                {
                    d.Emit.LoadLocal(d.Local_ch);
                    d.Emit.LoadConstant((int)item.Item1);
                    d.Emit.BranchIfEqual(item.Item2);
                }
            }
        }

        static void DoCharSwitch(Data d, List<Tuple<char, Label>> namesToFinish)
        {
            var minVal = namesToFinish.OrderBy(_ => _.Item1).First().Item1;

            var allLabels = namesToFinish.OrderBy(_ => _.Item1).Select(_ => _.Item2).ToArray();

            d.Emit.LoadLocal(d.Local_ch);       // int
            d.Emit.LoadConstant((int)minVal);   // int int
            d.Emit.Subtract();                  // int
            d.Emit.Switch(allLabels);           // --empty--
        }

        static void DoCharBinarySearch(Data d, List<Tuple<char, Label>> namesToFinish)
        {
            var noMatch = d.Emit.DefineLabel();

            var inOrder = namesToFinish.OrderBy(_ => _.Item1).ToList();

            Action<List<Tuple<char, Label>>> match = null;
            match =
                charsLeft =>
                {
                    if (charsLeft.Count == 0)
                    {
                        d.Emit.Branch(noMatch);                 // --empty--
                        return;
                    }

                    if (charsLeft.Count == 1)
                    {
                        var exact = charsLeft[0];

                        d.Emit.LoadLocal(d.Local_ch);           // int
                        d.Emit.LoadConstant((int)exact.Item1);  // int int
                        d.Emit.BranchIfEqual(exact.Item2);      // --empty--
                        d.Emit.Branch(noMatch);                 // --empty--
                        return;
                    }

                    var midPoint = charsLeft.Count / 2;
                    var midVal = charsLeft[midPoint];

                    var left = charsLeft.Take(midPoint).ToList();
                    var right = charsLeft.Skip(midPoint).ToList();

                    var leftLabel = d.Emit.DefineLabel();

                    d.Emit.LoadLocal(d.Local_ch);           // int
                    d.Emit.LoadConstant((int)midVal.Item1); // int int
                    d.Emit.BranchIfLess(leftLabel);         // --empty--
                    match(right);                           // --empty--

                    d.Emit.MarkLabel(leftLabel);            // --empty--
                    match(left);                            // --empty
                };

            match(inOrder);

            d.Emit.MarkLabel(noMatch);
        }

        static List<List<Tuple<char, Label>>> SplitIntoContiguousGroups(List<Tuple<char, Label>> chars)
        {
            var inOrder = chars.OrderBy(t => t.Item1).ToList();

            var ret = new List<List<Tuple<char, Label>>>();

            var runningGroup = new List<Tuple<char, Label>>();

            foreach (var t in inOrder)
            {
                if (runningGroup.Count == 0 || (runningGroup[runningGroup.Count - 1].Item1 + 1) == t.Item1)
                {
                    runningGroup.Add(t);
                }
                else
                {
                    ret.Add(runningGroup);
                    runningGroup = new List<Tuple<char, Label>>();
                    runningGroup.Add(t);
                }
            }

            if (runningGroup.Count > 0)
            {
                ret.Add(runningGroup);
            }

            return ret;
{'fraction_non_alphanumeric': 0.09872770709483861, 'fraction_numerical': 0.003166842602366798, 'mean_word_length': 1.2332506203473945, 'pattern_counts': {'":': 0, '<': 70, '<?xml version=': 0, '>': 93, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7125855', 'n_tokens_mistral': 4746, 'n_tokens_neox': 4429, 'n_words': 904}