基于Tree-sitter解析树实现DSL语言服务器的类型推断与自动补全

针对你开发强类型DSL语言服务器的需求，结合Tree-sitter的特性，这里提供一套无需依赖Hindly-Milner类型理论的高效实现方案，重点解决嵌套成员表达式的类型推断与补全问题：

一、前置准备：构建增量式类型符号表 #

核心思路是提前扫描代码，将所有类型信息（自定义struct、变量类型等）存入哈希表结构的符号表，避免每次补全时遍历整个AST。

1. 用Tree-sitter查询提取类型信息 #

通过Tree-sitter的查询语法，一次性扫描并提取关键类型数据：

• 提取struct定义：

  (struct_statement
    name: (identifier) @struct-name
    body: (struct_body
      (field_definition
        name: (identifier) @field-name
        type: (type) @field-type
      )*
    )
  )
  

  执行该查询后，可将结果整理为：

  const structSymbols = {
    Datum: { deadline: "Int" }
  };
  

• 提取变量类型：

  (const_statement
    name: (identifier) @var-name
    type: (type) @var-type
  )
  

  结果整理为：

  const varSymbols = {
    d: "Datum",
    x: "Int"
  };
  

2. 增量更新符号表 #

利用Tree-sitter的增量解析能力，仅在代码局部修改时，重新解析对应区域并更新符号表的相关条目，而非全量扫描，大幅提升效率。

二、嵌套成员表达式的类型推断与补全流程 #

当用户在d.deadline.后触发补全时，按以下步骤处理：

1. 定位并拆解成员链
   用Tree-sitter查询定位当前的member_expression节点，递归拆解出完整的成员标识符链（如[d, deadline]）：

   (member_expression
     base: (member_expression) @nested-base
     "."
     member: (identifier) @member
   )
   (member_expression
     base: (identifier) @root-base
     "."
     member: (identifier) @member
   )
   

2. 链式查询符号表
   基于符号表逐步推导最终类型：

   function getFinalType(memberChain) {
     let currentType = varSymbols[memberChain[0]];
     for (let i = 1; i < memberChain.length; i++) {
       const structDef = structSymbols[currentType];
       if (!structDef || !structDef[memberChain[i]]) return null;
       currentType = structDef[memberChain[i]];
     }
     return currentType;
   }
   

3. 生成补全列表
   根据最终类型，匹配预定义的内置类型方法（如Int对应的show()）或自定义类型的字段/方法，返回补全结果。

三、效率优化要点 #

• 缓存推断结果：对频繁访问的成员链（如d.deadline）缓存其最终类型，避免重复查询符号表。
• 预加载内置类型：将Int、String等内置类型的方法提前存入固定映射表，直接查询即可。
• 延迟查询：仅在用户触发补全时才执行成员链的类型推导，而非实时监控所有节点。

优化后的伪算法 #

1. 从光标位置定位member_expression节点，拆解出完整成员链（如[d, deadline]）
2. 从varSymbols获取链首元素的类型（d → Datum）
3. 遍历剩余成员：
   a. 从structSymbols中查询当前类型对应的成员类型（Datum → deadline的类型为Int）
   b. 若查询失败，返回空补全列表
   c. 更新当前类型为查询到的类型
4. 根据当前类型（Int）获取对应的方法/字段，生成补全列表

内容的提问来源于stack exchange，提问作者et97