这篇随笔的核心是介绍一下 YACEP 所用到的一些技术, 工具, 服务和技巧, 鉴于篇幅原因, 不可能面面俱到, 只能点到为止, 目录如下:
目录:
1. YACEP 简介(上)
2. 技术篇(上)
2.1 利用优先爬山算法解决运算符优先级的问题
2.2 利用 ReadOnlySpan 加速字符串解析
2.3 利用表达式树和 Emit 生成表达式执行代理
3. 工具篇(上)
3.1 测试覆盖率工具 - Coverlet
3.2 覆盖率报表转换工具 - ReportGenerator
3.3 基准测试工具 - BenchmarkDotNet
4. 服务篇(下)
4.1 测试覆盖率服务 - Codecov
4.2 代码质量分析服务 - SonarCloud
4.3 持续集成服务 1 - Travis CI
4.4 持续集成服务 2 - AppVeyor
4.5 持续集成服务 3 - Azure DevOps
5. 技巧篇(下)
5.1 利用 props 文件抽离 csproj 的公共配置
5.2 利用 WSL 跨平台测试代码
5.3 利用持续集成服务检查 PR
5.4 更易写的文档格式 - AsciiDoc
5.5 如何给你的项目添加更多的徽章
5.6 利用 Git message 自动发布 NuGet 包
1. YACEP 简介
YACEP : yet another csharp expression parser, 是一款基于 netstandard2.0 构建的轻量级高性能表达式解析器. 能够将一段有效的字符串并转换成一棵抽象语法树, 同时可以把抽象语法树转换成一段可以执行的代码.
项目使用 MIT 开源协议, 代码托管在 GitHub 上, 更多更详细的信息可以去看官方文档, 随便给个 star 什么的就再好不过了:)
YACEP 的核心是一个轻量级的表达式解析器, 其解析代码不到 500 行, 算上辅助的一些操作, 整个解析器代码不到 600 行. 解析器内部使用了 ReadOnlySpan 来处理字符串, 所以在做长串处理时, 内存消耗可以做到很低, 处理起来也非常快.
YACEP 还附加实现了一个简单编译器, 可以将抽象语法树转换成可执行代码. 编译器的接口申明了两个方法, 一个不带泛型参数, 一个带了泛型参数. 所以在 YACEP 的内部编译器的实现有两个, 第一个是不做运行时类型绑定的实现, 一个是限定运行时类型绑定的实现. 前者有更好的灵活性, 有类似 Python 这种语言的动态能力, 所以无法在编译完成时生成更优化的 IL 指令, 性能一般. 而后者是在编译时就已经限定了具体的类型, 所以能够生成更短的 IL 指令, 性能相对于第一种有非常大的提升.
- public interface ICompiler
- {
- /// 不做运行时类型绑定
- IEvaluator Compile(EvaluableExpression expression);
- /// 做运行时类型绑定
- IEvaluator<TState> Compile<TState>(EvaluableExpression expression);
- }
YACEP 具体的其它特性可以去 GitHub 上查看, 这里就直接从官方复制过来, 如下:
开箱即用, 内置了的字面值, 一元及二元操作符以及统计类与时间类函数可满足大部分使用场景
跨平台, 基于标准构建
轻量级, 只有 500 多行代码实现的轻量级词法分析器
低消耗, 词法分析器使用 ReadOnlySpan 解析字符串
高性能, 使用 EMIT 技术生成 IL 来构建可执行对象(查看基准测试报告)
支持条件表达式
支持索引器
支持 in 表达式
支持自定义字面量
支持自定义一元操作符
支持自定义二元操作符
支持自定义函数
2. 技术篇
2.1 利用优先爬山算法解决运算符优先级的问题
优先爬山算法是一种深度优先的算法, 它采用启发式的方式进行局部择优. 现在的很多人工智能技术也有用到此算法.(后简称爬山算法)
更详细的介绍请点击此链接: https://en.wikibooks.org/wiki/Algorithms/Hill_Climbing
当前有很多种算法可以解决运算符优先级的问题, 比如调度场算法, 递归下降算法, 移进归约算法等.
那为什么 YACEP 会选用优先爬山算法呢?
因为爬山算法是我看过众多的算法中, 理解起来是最快的. 下面讲解一下这个算法的大致思路.
在开始之前我需要先回忆一下小学学到的数学知识, 四则运算法则和结合律.
四则运算法则告诉我们当一个式子有加减乘除的时候, 先算乘除后算加减, 这个是一个原则, 很好理解, 照着做就成.
结合律就稍复杂一点了, 结合律是说在一个包含有二个以上的可结合运算子的表示式, 只要算子的位置没有改变, 其运算的顺序就不会对运算出来的值有影响. 看不懂是吧, 换一种说法就是:
( a + b ) + c = a + ( b + c )
a, b 的和 再与 c 求和的值 一定 等于 a 与 b, c 的和 求和的值. 请务必按照这个断句读, 否则有点拗口.
如果读完还不知道啥意思, 可以回小学去捶一顿你们的体育老师了.
好了, 有了上面的知识储备, 我们开始研究如下数学表达式:
a + b * c * d + e
按照四则运算法则: 先乘除后加减, 对于上述表达式, 我们标记一下运算的优先级
再按照结合律, 对于更高优先级的乘法, 在求 a*b*c 的值的时候, 我们无所谓先算 a*b 再用这个结果去乘 c, 还是先算 b*c 再去乘 a. 按照当前主流的文字阅读规则, 我们选择从左往右, 即先算 b*c, 然后拿到这个结果再乘 d. 我们将 b*c 的结果存储为 m, 于是上述表达式可以简化为:
- // m = b * c
- a + m * d + e
再继续, 我们将 m*d 的结果存储为 n, 于是上述表达式再次简化为:
- // m = b * c
- // n = m * d
- a + n + e
再次按照结合律, 我们将 a+n 的结果存储为 x, 于是上述表达式还可简化为:
- // m = b * c
- // n = m * d
- // x = a + n
- x + e
到这一步只要求 x+e 的结果就好了, 把前面的步骤合并在一起.
- a + b * c * d + e
- -----
- m
- ---------
- n
- ---------------
- x
- ----------------------
去掉字符, 我们把下面的虚线连接起来, 大概是这样:
山顶
- / ----- \
- / \
- / --------- \
- / \
- / ------------- \
- / \
- / ----------------- \
这就是传说中的爬山算法!!!
是不是超好懂!!!
10 秒钟读懂了爬山算法!!!
其实怎么说呢, 理解到这一步基本就离理解完整的爬山算法差的没几百步了. 总共也就几百步, 你再走几百步就完全理解了, 加油, 我们继续.
按照上述的步骤, 我们现在开始理解算法的流程. 我们将表达式中的元素分为两类, 一类我们叫原子值, 比如上面表达式中的 a,b,c,d,e, 另一类我们叫他们为运算符, 比如 + 和 *. 对于带括号的表达式, 我们可以称其为子表达式, 也是一种表达式, 所以我们总是可以将任何一个表达式拆解为只包含原子值或运算符的表达式(对于一个不包含运算符的表达式, 直接拿值就完了).
基于上述的分类, 我们开始描述一下爬山算法的运算步骤:
1. 读取当前一个原子值和它最邻近的运算符
2. 读取下一个原子值和它最邻近的运算符
3. 如果步骤 1 中的运算符的优先级大于步骤 2 中的优先级, 则算法返回当前原子值, 当前原子值最邻近运算符与下一个原子值的子表达式
4. 否则, 从步骤 2 开始构建新的子表达式继续按照上述步骤处理
回到表达式:
a + b * c * d + e
现在按照爬山算法开始处理这个表达式:
读到原子值 a 以及优先级为 1 的运算符 +, a +
读取下一个原子值 b 以及优先级为 2 的运算符 *, b *
优先级 2 大于 1, 所以我们开始从 b 开始构建子表达式
读取下一个原子值 c 以及优先级为 2 的运算符 *, c *
当前的子表达式的 b * 优先级是 2(, 新读到 c * 的优先级也是 2, 得到新表达式 b * c * , 优先级是 2. 上面的步骤的值 m *
读取下一个表达式 d + , + 的优先级是 1, 所以整个子表达式返回值为 m * d , 这两步需要理解结合律. 上面的值 n +
子表达式已经处理完成, 退出子表达式的处理流程, 当前的表达式为的优先级为步骤 1 中, a +
下一个表达式为 n + , 两者的优先级都是 1, 返回子串 a + n 上面的值 x +
下一个表达式为 e , 直接返回
得到最终表达式 x + e
回到之前我们得到的那座山, 再看看这个步骤, 你会发现这个流程还真的就是在爬这座山 .
山顶
- / ----- \
- / \
- / --------- \
- / \
- / ------------- \
- / \
- / ----------------- \
2.2 利用 ReadOnlySpan 加速字符串解析
- C# 中 String 对象是一个只读对象, 一旦创建将不可更改. 所以 C# 中对 String 对象做更改的方法底层都会创建一个新的 String 对象. 比如在如下代码中:
- unsafe
- {
- var random = new Random();
- var str = "";
- for (int i = 0; i <= 5; i++)
- {
- str += Convert.ToChar(random.Next('A', 'Z'));
- fixed (char* p = str)
- Console.WriteLine((int)p);
- }
- Console.WriteLine(str);
- }
上述的代码是在做字符串修改, 你可能会觉得这种修改返回一个新值没问题.
但是下面的这种情况对于解析器来说就是一种致命伤了. 在截取字符串时, 你会发现每一次值都是不一样的, 纵使你截取的位置是相同的, Substring 始终如一的返回一个新对象给你.
- unsafe
- {
- var str = "123456";
- fixed (char* p = str)
- Console.WriteLine((int)p);
- fixed (char* p = str.Substring(1, 2))
- Console.WriteLine((int)p);
- fixed (char* p = str.Substring(1, 2))
- Console.WriteLine((int)p);
- Console.WriteLine(str);
- }
对解析过程而言, 可能会有频繁截串的场景, 比如随时都可能要将表达式中的一段数字转换为一个数值. 这种情况, 每次都返回一个新的字符串对象, 无论性能还是内存都是难以接受的.
你可能有想到 C# 中的 StringBuilder 对象, 它确实是维护一个缓冲区, 可以在做字符串修改的时候保证始终如一的使用同一块地址, 但是这玩意是用来构建字符串的, 读取字符串这货不行的, 所以你看官方连个 Substring 都不给你.
难道必须使用非托管代码了么? 为了保证更快的内存读取以及更低的内存消耗, 难道我要去 PInvoke???
这种问题, 微软的码农肯定已经意识到了, 不然这部分的随笔... 我怎么写下去.
微软提供了 System.Memory 程序集用来帮助我们更方便也更安全的操作内存.
我们可以使用 ReadOnlySpan 来解决上述问题.
ReadOnlySpan 在程序集 System.Memory 中, 是 Span 的只读表示. 将字符串转换为一个 ReadOnlySpan 对象, 接着使用 ReadOnlySpan 来处理字符串, 那么上述的问题都可以被解决.
然后大致说一下 Span,Span 可以用于表达任何一段连续内存空间, 无论是数组, 非托管指针, 可获取到指针值的托管内存等等等等(是不是回忆起当初被指针支配的恐惧感), 其实在它内部的实现就是一个指针. 相对于 C/C++ 里面的指针需要各种小心翼翼, 不敢有一丝怠慢忘记释放, 或访问到离奇的地址, 或因为各种原因变成野指针. Span 会在内部维护这个指针的地址, 在做指针运算时, 会做边界检查, 在更新引用时, 垃圾回收器也能判断出该如何回收内存.
- public interface IEvaluator
- {
- object Evaluate(object state);
- }
- public interface IEvaluator<in TState>
- {
- object Evaluate(TState state);
- }
- Microsoft (R) Test Execution Command Line Tool Version 16.0.1
- Copyright (c) Microsoft Corporation. All rights reserved.
- Starting test execution, please wait...
- Test Run Successful.
- Test execution time: 4.4614 Seconds
- dotnet test ./tests/TupacAmaru.Yacep.Test/TupacAmaru.Yacep.Test.csproj ^
- /p:CollectCoverage=true ^
- /p:Exclude=\"[xunit.*]*,[TupacAmaru.Yacep.Test*]*\"^
- /p:CoverletOutputFormat=\"lcov,opencover\" ^
- /p:CoverletOutput=./../../results/coverage/
- Calculating coverage result...
- Generating report '.\..\..\results\coverage\coverage.info'
- Generating report '.\..\..\results\coverage\coverage.opencover.xml'
- +------------------+------+--------+--------+
- | Module | Line | Branch | Method |
- +------------------+------+--------+--------+
- | TupacAmaru.Yacep | 100% | 98.9% | 100% |
- +------------------+------+--------+--------+
- +---------+------+--------+--------+
- | | Line | Branch | Method |
- +---------+------+--------+--------+
- | Total | 100% | 98.9% | 100% |
- +---------+------+--------+--------+
- | Average | 100% | 98.9% | 100% |
- +---------+------+--------+--------+
- BenchmarkDotNet=v0.11.5, OS=Ubuntu 16.04
- Intel Xeon CPU E5-2673 v3 2.40GHz, 1 CPU, 2 logical and 2 physical cores
- .NET Core SDK=2.2.204
- [Host] : .NET Core 2.2.5 (CoreCLR 4.6.27617.05, CoreFX 4.6.27618.01), 64bit RyuJIT
- Toolchain=InProcessEmitToolchain InvocationCount=8 IterationCount=200
- LaunchCount=1 RunStrategy=Throughput UnrollFactor=4
- WarmupCount=1
来源: https://www.cnblogs.com/wushilonng/p/10933322.html