高性能版本的零内存分配LikeString函数（ZeroMemAllocLikeOperator）

继上一篇文章在.NET Core，除了VB的LikeString，还有其它方法吗？(四种LikeString实现分享)分享了四种LikeString的实现方式，笔者对这四种实现方式，不管是执行性能还是内存分配性能上，都不太满意。

那么是否有好的实现方法呢？答案是有的。

今天我们就搬出ReadOnlySpan这个非常好用的结构类型，它是在 .NET Core 2.1 中新引入的类型，与它一同被引入的类型还有：

• System.Span: 这以类型安全和内存安全的方式表示任意内存的连续部分；
• System.ReadOnlySpan: 这表示任意连续内存区域的类型安全和内存安全只读表示形式；
• System.Memory: 这表示一个连续的内存区域；
• System.ReadOnlyMemory: 类似ReadOnlySpan, 此类型表示内存的连续部分ReadOnlySpan, 它不是 ByRef 类型；

  注：ByRef 类型指的是 ref readonly struct。

下面，我们就来看看如何实现高性能和零内存分配的 LikeString 函数吧！

#nullable enable

using System;

namespace AllenCai
{
    /// 

    /// 这是一个模仿Microsoft.VisualBasic.CompilerServices.LikeOperator.LikeString方法，

    /// 实现支持*和?通配符和支持忽略大小写规则以及区域无关性的匹配。

    /// 该实现的目的是为了减少内存分配，提高性能。
    /// 
    public class ZeroMemAllocLikeOperator
    {
        /// 

        /// 对给定的两个字符串执行比较，支持使用*和?通配符。
        /// 
        public static bool LikeString(string? content, string? pattern, bool ignoreCase = true, bool useInvariantCulture = true)
        {
            if (content == null && pattern == null)
                return true;
            if (content == null || pattern == null)
                return false;

            ReadOnlySpan<char> patternSpan = pattern.AsSpan();
            ReadOnlySpan<char> contentSpan = content.AsSpan();

            return LikeString(contentSpan, patternSpan, ignoreCase, useInvariantCulture);
        }

        /// 

        /// 对给定的两个字符Span执行比较，支持使用*和?通配符。
        /// 
        public static bool LikeString(ReadOnlySpan<char> contentSpan, ReadOnlySpan<char> patternSpan, bool ignoreCase = true, bool useInvariantCulture = true)
        {
            char zeroOrMoreChars = '*';
            char oneChar = '?';

            // 如果pattern是由1个星号*组成，那么没必要匹配，直接返回true。
            if (patternSpan.Length == 1)
            {
                ref readonly char patternItem = ref patternSpan[0];
                if (patternItem == zeroOrMoreChars)
                {
                    return true;
                }
            }

            // 如果被匹配内容的长度只有1位，而pattern刚好也是一个问号?，那么没必要匹配，直接返回true。
            if (contentSpan.Length == 1)
            {
                ref readonly char patternItem = ref patternSpan[0];
                if (patternItem == oneChar)
                {
                    return true;
                }
            }

            // 如果pattern是由多个星号*和问号?组成，那么没必要匹配，直接返回true。
            int zeroOrMorePatternCount = 0;
            int onePatternCount = 0;
            for (int i = 0; i < patternSpan.Length; i++)
            {
                ref readonly char patternItem = ref patternSpan[i];
                if (patternItem == zeroOrMoreChars)
                {
                    zeroOrMorePatternCount++;
                }
                else if (patternItem == oneChar)
                {
                    onePatternCount++;
                }
            }
            if (zeroOrMorePatternCount + onePatternCount == patternSpan.Length)
            {
                //只要出现1个或多个星号*，那么就没必要在乎被匹配内容的长度了。
                if (zeroOrMorePatternCount > 0)
                {
                    return true;
                }

                //如果没有星号*，全是问号?，那么就检查是否由问号?组成的pattern长度是否和被匹配内容的长度一致。如果一致，没必要匹配，直接返回true。
                if (patternSpan.Length == contentSpan.Length)
                {
                    return true;
                }
            }

            // 选择合适的EqualsChar方法。
            EqualsCharDelegate equalsChar;
            if (ignoreCase)
            {
                if (useInvariantCulture)
                {
                    equalsChar = EqualsCharInvariantCultureIgnoreCase;
                }
                else
                {
                    equalsChar = EqualsCharCurrentCultureIgnoreCase;
                }
            }
            else
            {
                equalsChar = EqualsChar;
            }

            return LikeStringCore(contentSpan, patternSpan, in zeroOrMoreChars, in oneChar, equalsChar);
        }

        private static bool LikeStringCore(ReadOnlySpan<char> contentSpan, ReadOnlySpan<char> patternSpan, in char zeroOrMoreChars, in char oneChar, EqualsCharDelegate equalsChar)
        {
            // 遍历pattern，逐个字符匹配。
            int contentIndex = 0;
            int patternIndex = 0;
            while (contentIndex < contentSpan.Length && patternIndex < patternSpan.Length)
            {
                ref readonly char patternItem = ref patternSpan[patternIndex];
                if (patternItem == zeroOrMoreChars)
                {
                    // 如果pattern中的下一个字符是星号*，那么就一直往后移动patternIndex，直到找到不是星号*的字符。
                    while (true)
                    {
                        if (patternIndex < patternSpan.Length)
                        {
                            ref readonly char nextPatternItem = ref patternSpan[patternIndex];
                            if (nextPatternItem == zeroOrMoreChars)
                            {
                                patternIndex++;
                                continue;
                            }
                        }
                        break;
                    }

                    // 如果patternIndex已经到了pattern的末尾，那么就没必要再匹配了，直接返回true。
                    if (patternIndex == patternSpan.Length)
                    {
                        return true;
                    }

                    // 如果patternIndex还没到pattern的末尾，那么就从contentIndex开始匹配。
                    while (contentIndex < contentSpan.Length)
                    {
                        if (LikeStringCore(contentSpan.Slice(contentIndex), patternSpan.Slice(patternIndex), in zeroOrMoreChars, in oneChar, equalsChar))
                        {
                            return true;
                        }
                        contentIndex++;
                    }

                    return false;
                }

                if (patternItem == oneChar)
                {
                    // 如果pattern中的下一个字符是问号?，那么就匹配一个字符。
                    contentIndex++;
                    patternIndex++;
                }
                else
                {
                    // 如果pattern中的下一个字符不是星号*，也不是问号?，那么就匹配一个字符。
                    if (contentIndex >= contentSpan.Length)
                    {
                        return false;
                    }

                    ref readonly char contentItem = ref contentSpan[contentIndex];
                    if (!equalsChar(in contentItem, in patternItem))
                    {
                        return false;
                    }

                    //if (ignoreCase)
                    //{
                    //    if (char.ToUpperInvariant(contentItem) != char.ToUpperInvariant(patternItem))
                    //    {
                    //        return false;
                    //    }
                    //}
                    //else
                    //{
                    //    if (contentItem != patternItem)
                    //    {
                    //        return false;
                    //    }
                    //}

                    contentIndex++;
                    patternIndex++;
                }
            }

            // 如果content都匹配完了，而pattern还没遍历完，则检查剩余的patternItem是否都是星号*，如果是就返回true，否则返回false。
            if (contentIndex == contentSpan.Length)
            {
                // 如果pattern中的下一个字符是星号*，那么就一直往后移动patternIndex，直到找到不是星号*的字符。
                while (true)
                {
                    if (patternIndex < patternSpan.Length)
                    {
                        ref readonly char nextPatternItem = ref patternSpan[patternIndex];
                        if (nextPatternItem == zeroOrMoreChars)
                        {
                            patternIndex++;
                            continue;
                        }
                    }
                    break;
                }

                return patternIndex == patternSpan.Length;
            }

            return false;
        }

        private static bool EqualsChar(in char contentItem, in char patternItem)
        {
            return contentItem == patternItem;
        }

        private static bool EqualsCharCurrentCultureIgnoreCase(in char contentItem, in char patternItem)
        {
            return char.ToUpper(contentItem) == char.ToUpper(patternItem);
        }

        private static bool EqualsCharInvariantCultureIgnoreCase(in char contentItem, in char patternItem)
        {
            return char.ToUpperInvariant(contentItem) == char.ToUpperInvariant(patternItem);
        }

        private delegate bool EqualsCharDelegate(in char contentItem, in char patternItem);
    }
}

Benchmark性能测试结果：

PS: 以上代码在 .NET Standard 2.1 项目使用，可直接编译通过。

在 .NET Standard 2.0 项目中，需要额外引入 System.Memory 这个 NuGet 包，且需要将 LangVersion（C#语言版本）更改为 8.0 或更高（通常使用 default 或 latest 也可以）。