IntegerJumpTable

IntegerJumpTable.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Linq.Expressions;
using System.Reflection;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using System.Text;
using System.Threading.Tasks;

namespace Microsoft.AspNetCore.Routing.Matching
{
    /// <summary>
    /// Case-Sensitive
    /// </summary>
    internal class IntegerJumpTable : JumpTable
    {
        private delegate int LookupDelegate(ReadOnlySpan<char> text, int length);
        private readonly int _defaultDestination;
        private readonly int _exitDestination;
        private readonly LookupDelegate _lookupDelegate;

        public IntegerJumpTable(
            int defaultDestination,
            int exitDestination,
            (string text, int destination)[] entries)
        {
            _defaultDestination = defaultDestination;
            _exitDestination = exitDestination;
            _lookupDelegate = BuildLookupFunctor(entries);
        }

        public override int GetDestination(string path, PathSegment segment)
        {
            if (segment.Length == 0)
            {
                return _exitDestination;
            }
            var text = path.AsSpan(segment.Start, segment.Length);
            return _lookupDelegate(text, segment.Length);
        }

        private LookupDelegate BuildLookupFunctor((string text, int destination)[] entries)
        {
            var nameSpan = Expression.Parameter(typeof(ReadOnlySpan<char>), "nameSpan");
            var lengthParameter = Expression.Variable(typeof(int), "length");
            var endOfBlockLabel = Expression.Label(typeof(int), "end");
            var byteNameSpan = Expression.Variable(typeof(ReadOnlySpan<byte>), "byteNameSpan");
            Expression<Action> functor = () => MemoryMarshal.AsBytes(new ReadOnlySpan<char>());
            var asBytesMethodInfo = (functor.Body as MethodCallExpression).Method;
            var nameSpanAsBytesExpression = Expression.Call(null, asBytesMethodInfo, nameSpan);
            var assignNameSpan = Expression.Assign(byteNameSpan, nameSpanAsBytesExpression);
            var expressions = new List<Expression>
            {
                assignNameSpan,
                Build(entries, 0, lengthParameter, byteNameSpan, endOfBlockLabel),
                Expression.Label(endOfBlockLabel, Expression.Constant(_defaultDestination))
            };
            var parameters = new List<ParameterExpression> {byteNameSpan};
            var block = Expression.Block(parameters, expressions);
            var lambda = Expression.Lambda<LookupDelegate>(block, nameSpan, lengthParameter);
            return lambda.Compile();
        }

        /// <summary>
        /// This method builds a chain of if statements  of the following logic:
        /// if(length == x AND ReadInteger(span) == y AND ...) then assign value
        /// the ReadInteger comparisons are basically constant values of the encoded value
        /// UTF8 -> 8 chars -> 8 bytes
        /// UTF16 -> 4 chars -> 8 bytes
        /// etc.
        /// This is a very fast way to match the correct namespan for e.g assigning members
        /// as it's only a comparison of length (this excludes most of the values) and
        /// comparing the individual integer length parts of the name against constants
        /// This improves the performance in deserialization specifically for UTF8 as byte arrays
        /// are handled differently than strings for comparisons in expression trees
        /// The speed for both is practically the same with this method
        /// It also simplifies the code if the member name is actually multibyte utf8 (e.g. chinese)
        /// </summary>
        public static Expression Build((string text, int destination)[] entries, int index, ParameterExpression lengthParameter,
            ParameterExpression nameSpanExpression, LabelTarget endOfBlockLabel)
        {
            var symbolSize = sizeof(char);
            var grouping = entries.Where(a => GetLength(a.text) >= index).GroupBy(a => CalculateKey(a.text, index))
                .OrderByDescending(a => a.Key.Key).ToList();
            if (!grouping.Any())
            {
                throw new InvalidOperationException(); // should never happen
            }

            var expressions = new List<Expression>();
            foreach (var group in grouping)
            {
                if (group.Count() == 1) // need to check remaining values too 
                {
                    var entry = group.Single();
                    var length = index + group.Key.offset;
                    var matchExpression = Expression.Return(endOfBlockLabel, Expression.Constant(entry.destination));
                    Expression comparisonExpression = null;
                    if (group.Key.Key != 0 || group.Key.offset != 0)
                    {
                        comparisonExpression = Expression.Equal(GetReadMethod(nameSpanExpression, group.Key.intType, Expression.Constant(index * symbolSize)),
                            GetConstantExpressionForGroupKey(group.Key.Key, group.Key.intType));
                        var nameLength = GetLength(entry.text);
                        while (length < nameLength)
                        {
                            var subKey = CalculateKey(entry.text, length);
                            comparisonExpression = Expression.AndAlso(comparisonExpression,
                                Expression.Equal(GetReadMethod(nameSpanExpression, subKey.intType, Expression.Constant(length * symbolSize)),
                                    GetConstantExpressionForGroupKey(subKey.Key, subKey.intType)));
                            length += subKey.offset;
                        }
                    }

                    var lengthExpression = Expression.Equal(lengthParameter, Expression.Constant(length));
                    var ifExpression = comparisonExpression == null ? lengthExpression : Expression.AndAlso(lengthExpression, comparisonExpression);
                    expressions.Add(Expression.IfThen(ifExpression, matchExpression));
                }
                else
                {
                    var nextLength = index + group.Key.offset;
                    var ifExpression = Expression.AndAlso(Expression.GreaterThanOrEqual(lengthParameter, Expression.Constant(nextLength)),
                        Expression.Equal(GetReadMethod(nameSpanExpression, group.Key.intType, Expression.Constant(index * symbolSize)),
                            GetConstantExpressionForGroupKey(group.Key.Key, group.Key.intType)));
                    var subBlock = Build(group.ToArray(), nextLength, lengthParameter, nameSpanExpression,
                        endOfBlockLabel);
                    expressions.Add(Expression.IfThen(ifExpression, subBlock));
                }
            }

            return Expression.Block(expressions);
        }

        private static Expression GetConstantExpressionForGroupKey(ulong key, Type intType)
        {
            if (intType == typeof(byte))
            {
                return Expression.Constant((byte)key);
            }

            if (intType == typeof(ushort))
            {
                return Expression.Constant((ushort)key);
            }

            if (intType == typeof(uint))
            {
                return Expression.Constant((uint)key);
            }

            if (intType == typeof(ulong))
            {
                return Expression.Constant(key);
            }

            throw new NotSupportedException();
        }

        private static Expression GetReadMethod(ParameterExpression nameSpanExpression, Type intType, Expression offsetParameter)
        {
            string methodName;
            if (intType == typeof(byte))
            {
                methodName = nameof(ReadByte);
            }

            else if (intType == typeof(ushort))
            {
                methodName = nameof(ReadUInt16);
            }

            else if (intType == typeof(uint))
            {
                methodName = nameof(ReadUInt32);
            }

            else if (intType == typeof(ulong))
            {
                methodName = nameof(ReadUInt64);
            }
            else
            {
                throw new NotSupportedException();
            }

            var methodInfo = typeof(IntegerJumpTable).GetMethod(methodName, BindingFlags.Static | BindingFlags.NonPublic);
            return Expression.Call(methodInfo, nameSpanExpression, offsetParameter);
        }

        private static int GetLength(string name)
        {
            return name.Length;
        }


        private static (ulong Key, Type intType, int offset) CalculateKey(string memberName, int index)
        {
            int remaining = memberName.Length - index;
            if (remaining >= 4)
            {
                return (BitConverter.ToUInt64(Encoding.Unicode.GetBytes(memberName), index * 2), typeof(ulong), 4);
            }

            if (remaining >= 2)
            {
                return (BitConverter.ToUInt32(Encoding.Unicode.GetBytes(memberName), index * 2), typeof(uint), 2);
            }

            if (remaining >= 1)
            {
                return (BitConverter.ToUInt16(Encoding.Unicode.GetBytes(memberName), index * 2), typeof(ushort), 1);
            }

            return (0, typeof(uint), 0);
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private static byte ReadByte(in ReadOnlySpan<byte> span, int offset)
        {
            return span[offset];
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private static ushort ReadUInt16(in ReadOnlySpan<byte> span, int offset)
        {
            return Unsafe.ReadUnaligned<ushort>(ref Unsafe.Add(ref MemoryMarshal.GetReference(span), offset));
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private static uint ReadUInt32(in ReadOnlySpan<byte> span, int offset)
        {
            return Unsafe.ReadUnaligned<uint>(ref Unsafe.Add(ref MemoryMarshal.GetReference(span), offset));
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private static ulong ReadUInt64(in ReadOnlySpan<byte> span, int offset)
        {
            return Unsafe.ReadUnaligned<ulong>(ref Unsafe.Add(ref MemoryMarshal.GetReference(span), offset));
        }
    }
}