Alvis

跳转定义

发表于更新于阅读时长 3 分钟

以rust-analyzer为例

在当代程序员的开发过程中，几乎已经没有人在使用纯文本编辑器了。对于那些不想使用 IDE 的人来说，最主流的工具莫过于各种语言的 LSP 服务器，而新潮的编辑器如 VSCode NeoVIM Helix 等更是内置了 LSP 协议的支持。本文将以 rust-analyzer （下文简称 r-a）为例，展示如何实现 IDE 最常用的功能之一跳转定义。

rust analyzer 跳转定义功能展示

当用户在编辑器里按下跳转定义（如 F12 或者 Ctrl B）时，作为 LSP 客户端的编辑器会向 LSP 服务端发起请求，具体请求参数可以参考lsp-types，在这个场景下，参数的主要内容是当前文件的 URL 以及当前光标的行列。

pub struct TextDocumentPositionParams {
    pub text_document: TextDocumentIdentifier,
    pub position: Position,
}

pub struct Position {
    pub line: u32,
    pub character: u32,
}

在收到请求之后，r-a 首先要把 URL 转换成具体的文件实例，这样就可以从缓存中找到之前分析时构建的语法树。同时还需要把光标的二维坐标转换一维的文本位置，因为 r-a 在构建语法树时并没有行的概念。

pub struct FilePosition {
    pub file_id: FileId,
    pub offset: TextSize,
}
pub struct TextSize {
    pub(crate) raw: u32,
}

转换完毕之后，就可以开始寻找偏移量所对应的语法元素了。这一功能由 r-a 使用的语法树库 rowan 提供。rowan 提供的结构被称为红绿树，不过这和当前的话题不太相关，我们可以直接把它当作 parse tree（或者叫具体语法树）看待。和常见的用一大堆 Variant/Class 定义出来的抽象语法树不同，具体语法树只是一堆 token 和它们之间的父子关系而已，所以遍历它相对比较简单。这里只要找到偏移量所在的的 token 即可。

下图就是一棵具体语法树，其中叶子节点上的小写字母代表 lexcial token，其他节点上的大写字母表示 syntax node。

parse tree

这里有个小小的优化：编辑器光标指向的并不一定是一个 token，事实上会遇到三种情况：指向空白，指向 token 以及光标正好在两个 token 之间。第三种情况需要进行一些额外的处理，比如对于foo$0(bar)（$0 代表光标位置，现代编辑器可能有多个光标），我们应当选择 foo 而不是左括号。

在拿到了 token 之后，我们就可以通过前述的父子关系获得它所在的 node，就可以知道当前元素具体在语法树的什么结构当中。如果它在声明中，那我们的工作基本上就完成了；而如果它在表达式中，那说明我们还需要找到定义它的地方。自然，下一步就是要找到这个变量所处的环境。同样地，依照父子关系一级一级向上爬，过滤出所有可能引入变量的地方比如 function block module 等等，一直爬到顶就能拿到当前元素所处的环境。

在拿到所处环境之后就可以计算环境中的所有绑定。这一步通常是在初始化的时候就计算好等候查询，r-a 使用salsa来实现这样的缓存。具体的计算过程和一般编译器计算绑定的过程没什么区别，这里就不赘述了。最后可以拿到像这样的结构，其中 scope 存储了所有一个 scope 中所有的绑定信息。此处有个特殊的地方是 rust 允许同一 block 中的变量 shadow，所以要为每个 let 声明引入单独的 scope。在函数式编程语言中这样的做法很常见。

pub struct Resolver {
    scopes: Vec<Scope>,
    module_scope: ModuleItemMap,
}

接下来只要按照父子顺序，遍历所有 scope 中的所有变量，找到和它名字相同的，就能找到它所对应的绑定，大体上是这样的结构。

pub struct Local {
    pub(crate) parent: DefWithBodyId,
    pub(crate) binding_id: BindingId,
}

最后还要要经历一下前面操作的反向操作--从绑定生成编辑器光标位置，这个过程相较之下就简单多了。Local 结构体中的 binding_id 可以找到绑定所对应的声明，通过 parent scope 的 source map 可以找到声明的 AST 节点，通过 AST 节点可以找到它在原文中的位置，进而可以计算出光标位置。把结果包装成 LSP 客户端需要的格式，跳转定义请求的处理就结束了。

© 2016 - 2024Austaras Devas