代码分析和差量计算

在lsp的文档中我简单介绍了差量计算在lsp模块中起到的优化作用，这里我将会详细介绍一下这个过程，希望能帮没接触过差量计算的小伙伴了解为何差量计算对于lsp的计算任务来说如此重要，以及什么情况下适合使用差量计算。

纯函数

差量计算中的基础对象一般是纯函数，纯函数的定义是：对于给定的输入，总是会有相同的输出，而且不会有任何副作用。
请注意其中不会有任何副作用这一点，如果要建立一个正确工作差量计算模型，必须要保证这一点。

带有副作用的函数为什么会影响差量计算正确性？

试想以下场景：我有两个参与差量计算的基础函数A和B，A不是纯函数，它会修改全局变量a，每次运行他会把a加一。 那么在某次计算过程中，A的输入与上次相同，B有变化，这导致B被重新执行了，而A直接使用上次缓存的计算结果，跳过了这次计算。那么这会导致本次计算全局变量a没有被A修改。这导致一个很严重的问题：即使用差量计算之后相比使用之前，相同情况下计算的影响不一样。
假设上方例子中不使用差量计算，那么A会被重新执行一次，这样a相比差量计算情况就会被多加一，正确的差量计算模型不应该对系统状态有影响，所以如果要使用差量计算，应该保证所有参与计算的函数都是没有副作用的纯函数。

一些容易被忽略的副作用情况

尽管纯函数的定义比较简单，上方的例子也比较直观，但是实际生产中其实很多函数都是有副作用的，而且很多初学者可能并不能完全分析出这些函数 的副作用。这里特别说一个容易被忽略的副作用情况：

• 修改被差量计算框架缓存的函数输出结果

在你分析一个函数有没有副作用的时候应该记住：被缓存的纯函数输出也属于全局状态，和全局变量没有本质区别。所以修改这些被缓存值也是有副作用的。修改这些值很可能在无意中发生：比如函数A的输出中有个类型指针，它输出后作为输入传给了函数B，函数B修改了这个类型指针指向的值，这样虽然看起来没有进行和全局变量相关的操作，但是实际上这个类型指针指向的值就是被缓存的函数A的输出，这种行为修改了缓存状态，是有副作用的。

差量计算系统设计原则

有了上方纯函数相关的知识，我们可以总结出一个正确的差量计算系统需要遵循的两条原则：

• 差量计算系统中，一个函数的输出应该是只读的，应该避免在别的函数中修改对应值
• 差量计算函数不能修改任何全局状态

实战举例--lsp引用查找功能设计

lsp引用查找是一个绝大部分语言插件都有的功能，它被使用的也很多，大部分程序员同学应该每天都会用到很多次。这个功能底层实现是比较简单的，如果不考虑差量计算的话：

在符号表中所有能被引用的符号中多存一个refs链表，每次该符号被使用，往链表中加入被使用的位置。最后在接收到find reference请求的时候，查找到对应的符号，返回refs链表即可。

但是这么设计在差量计算的时候会遇到问题：假设我们差量计算的最小单位是compile_file函数，它的意义是编译一个文件，那么这个函数输出的编译结果中就应该包含该文件中定义的所有的符号，自然也包括这些符号的refs信息。然而，很多符号是可以被跨文件使用的，比如全局变量，这些符号的refs信息是跨文件的，所以这些符号的refs信息可能会在对别的文件调用compile_file函数时被修改，这样就违反了差量计算系统的第原则：差量计算函数不能修改任何全局状态。
如果我们直接用这种设计来进行差量计算的话：

假设有文件A和文件B，A中有全局变量a，B中使用了全局变量a，第一次编译是全量编译，生成了正确的refs信息。第二次编译的时候，用户只修改了B，所以A的编译被跳过，复用了上次结果。这时请注意：a的refs链表是包含上次编译产生的完整结果的，而不是只有A文件中的引用信息，这一切都是因为B在编译的时候可能改A的编译结果，往a的refs里加值。

所以我们需要重新设计这个功能，我们需要把refs信息从符号中移除，放到一个与编译文件绑定的refs表中，这个表可以是map[str]vec<Location>类型，他只记录当前文件中符号的引用信息。当lsp收到find reference请求的时候，先找到对应的符号，然后再遍历所有文件的编译输出，找到对应符号在各个refs表中的记录，并且汇总。这样就可以保证差量计算的正确性了。

总结

我不是很擅长写文章，不知道这篇表达的清不清楚，如果能帮助到你就再好不过了。文章篇幅限制，这篇博客里跳过了差量计算框架的使用细节。 如果你对这方面感兴趣，可以参考我们的源代码。