探索类型系统的底层 - 自己实现一个 TypeScript(硬核干货)
共 28350字，需浏览 57分钟
·
2021-06-25 07:30
原文：https://indepth.dev/under-the-hood-of-type-systems/
DawnL 译
这篇文章包含两个部分：
A 部分：类型系统编译器概述(包括 TypeScript)
Syntax vs Semantics 语法 vs 语义 What is AST? 什么是 AST？ Types of compilers 编译器的类型 What does a language compiler do? 语言编译器是做什么的？ How does a language compiler work? 语言编译器是如何工作的？ Type system compiler jobs 类型系统编译器职责 Advanced type checker features 高级类型检查器的功能
B 部分：构建我们自己的类型系统编译器
The parser 解析器 The checker 检查器 Running our compiler 运行我们的编译器 What have we missed? 我们遗漏了什么？
A 部分：类型系统编译器概述
语法 vs 语义
语法和语义之间的区别对于早期的运行很重要。
语法 - Syntax
语法通常是指 JavaScript 本机代码。本质上是询问给定的 JavaScript 代码在运行时是否正确。
例如，下面的语法是正确的：
var foo: number = "not a number";
语义 - Semantics
这是特定于类型系统的代码。本质上是询问附加到代码中的给定类型是否正确。
例如，上面的代码在语法上是正确的，但在语义上是错误的(将变量定义为一个数字类型，但是值是一个字符串)。
接下来是 JavaScript 生态系统中的 AST 和编译器。
什么是 AST？
在进一步讨论之前，我们需要快速了解一下 JavaScript 编译器中的一个重要机制 AST。
关于 AST 详细介绍请看这篇文章。
AST 的意思是抽象语法树 ，它是一个表示程序代码的节点树。Node 是最小单元，基本上是一个具有 type 和 location 属性的 POJO（即普通 JavaScript 对象）。所有节点都有这两个属性，但根据类型，它们也可以具有其他各种属性。
在 AST 格式中，代码非常容易操作，因此可以执行添加、删除甚至替换等操作。
例如下面这段代码：
function add(number) {
return number + 1;
}
将解析成以下 AST：
编译器类型
在 JavaScript 生态系统中有两种主要的编译器类型：
1. 原生编译器（Native compiler）
原生编译器将代码转换为可由服务器或计算机运行的代码格式(即机器代码)。类似于 Java 生态系统中的编译器 - 将代码转换为字节码，然后将字节码转换为本机代码。
2. 语言编译器
语言编译器扮演着不同的角色。TypeScript 和 Flow 的编译器在将代码输出到 JavaScript 时都算作语言编译器。
语言编译器与原生编译器的主要区别在于，前者的编译目的是 tooling-sake（例如优化代码性能或添加附加功能），而不是为了生成机器代码。
语言编译器是做什么的？
在类型系统编译器中，总结的两个最基本的核心职责是：
1. 执行类型检查
引入类型（通常是通过显式注解或隐式推理），以及检查一种类型是否匹配另一种类型的方法，例如 string 和 number。
2. 运行语言服务器
对于一个在开发环境中工作的类型系统（type system）来说，最好能在 IDE 中运行任何类型检查，并为用户提供即时反馈。
语言服务器将类型系统连接到 IDE，它们可以在后台运行编译器，并在用户保存文件时重新运行。流行的语言，如 TypeScript 和 Flow 都包含一个语言服务器。
3. 代码转换
许多类型系统包含原生 JavaScript 不支持的代码(例如不支持类型注解) ，因此它们必须将不受支持的 JavaScript 转换为受支持的 JavaScript 代码。
关于代码转换更详细的介绍，可以参考原作者的这两篇文章 Web Bundler 和 Source Maps。
语言编译器是如何工作的？
对于大多数编译器来说，在某种形式上有三个共同的阶段。
1. 将源代码解析为 AST
词法分析 -> 将代码字符串转换为令牌流(即数组) 语法分析 -> 将令牌流转换为 AST 表示形式
解析器检查给定代码的语法。类型系统必须有自己的解析器，通常包含数千行代码。
Babel 解析器 中的 2200+ 行代码，仅用于处理 statement 语句（请参阅此处）。
Hegel 解析器将 typeAnnotation 属性设置为具有类型注解的代码（可以在这里看到）。
TypeScript 的解析器拥有 8900+ 行代码(这里是它开始遍历树的地方)。它包含了一个完整的 JavaScript 超集，所有这些都需要解析器来理解。
2. 在 AST 上转换节点
操作 AST 节点
这里将执行应用于 AST 的任何转换。
3. 生成源代码
将 AST 转换为 JavaScript 源代码字符串
类型系统必须将任何非 js 兼容的 AST 映射回原生 JavaScript。
类型系统如何处理这种情况呢？
类型系统编译器（compiler）职责
除了上述步骤之外，类型系统编译器通常还会在解析之后包括一个或两个额外步骤，其中包括特定于类型的工作。
顺便说一下，TypeScript 的编译器实际上有 5 个阶段，它们是：
语言服务预处理器 - Language server pre-processor 解析器 - Parser 结合器 - Binder 检查器 - Checker 发射器 - Emitter
正如上面看到的，语言服务器包含一个预处理器，它触发类型编译器只在已更改的文件上运行。这会监听任意的 import 语句，来确定还有哪些内容可能发生了更改，并且需要在下次重新运行时携带这些内容。
此外，编译器只能重新处理 AST 结构中已更改的分支。关于更多 lazy compilation，请参阅下文。
类型系统编译器有两个常见的职责：
1. 推导 - Inferring
对于没有注解的代码需要进行推断。关于这点，这里推荐一篇关于何时使用类型注解和何时让引擎使用推断的文章。
使用预定义的算法，引擎将计算给定变量或者函数的类型。
TypeScript 在其 Binding 阶段（两次语义传递中的第一次）中使用最佳公共类型算法。它考虑每个候选类型并选择与所有其他候选类型兼容的类型。上下文类型在这里起作用，也会做为最佳通用类型的候选类型。在这里的 TypeScript 规范中有更多的帮助。
let zoo: Animal[] = [new Rhino(), new Elephant(), new Snake()];
TypeScript 实际上引入了 Symbols（interface）的概念，这些命名声明将 AST 中的声明节点与其他声明进行连接，从而形成相同的实体。它们是 TypeScript 语义系统的基本构成。
2. 检查 - Checking
现在类型推断已经完成，类型已经分配，引擎可以运行它的类型检查。他们检查给定代码的 semantics。这些类型的检查有很多种，从类型错误匹配到类型不存在。
对于 TypeScript 来说，这是 Checker (第二个语义传递) ，它有 20000+ 行代码。
我觉得这给出了一个非常强大的 idea，即在如此多的不同场景中检查如此多的不同类型是多么的复杂和困难。
类型检查器不依赖于调用代码，即如果一个文件中的任何代码被执行（例如，在运行时）。类型检查器将处理给定文件中的每一行，并运行适当的检查。
高级类型检查器功能
由于这些概念的复杂性，我们今天不深入探讨以下几个概念：
懒编译 - Lazy compilation
现代编译的一个共同特征是延迟加载。他们不会重新计算或重新编译文件或 AST 分支，除非绝对需要。
TypeScript 预处理程序可以使用缓存在内存中的前一次运行的 AST 代码。这将大大提高性能，因为它只需要关注程序或节点树的一小部分已更改的内容。
TypeScript 使用不可变的只读数据结构，这些数据结构存储在它所称的 look aside tables 中。这样很容易知道什么已经改变，什么没有改变。
稳健性
在编译时，有些操作编译器不确定是安全的，必须等待运行时。每个编译器都必须做出困难的选择，以确定哪些内容将被包含，哪些不会被包含。TypeScript 有一些被称为不健全的区域（即需要运行时类型检查）。
我们不会在编译器中讨论上述特性，因为它们增加了额外的复杂性，对于我们的小 POC 来说不值得。
现在令人兴奋的是，我们自己也要实现一个编译器。
B 部分：构建我们自己的类型系统编译器
我们将构建一个编译器，它可以对三个不同的场景运行类型检查，并为每个场景抛出特定的信息。
我们将其限制在三个场景中的原因是，我们可以关注每一个场景中的具体机制，并希望到最后能够对如何引入更复杂的类型检查有一个更好的构思。
我们将在编译器中使用函数声明和表达式(调用该函数)。
这些场景包括：
1. 字符串与数字的类型匹配问题
fn("craig-string"); // throw with string vs number
function fn(a: number) {}
2. 使用未定义的未知类型
fn("craig-string"); // throw with string vs ?
function fn(a: made_up_type) {} // throw with bad type
3. 使用代码中未定义的属性名
interface Person {
name: string;
}
fn({ nam: "craig" }); // throw with "nam" vs "name"
function fn(a: Person) {}
实现我们的编译器，需要两部分：解析器和检查器。
解析器 - Parser
前面提到，我们今天不会关注解析器。我们将遵循 Hegel 的解析方法，假设一个 typeAnnotation 对象已经附加到所有带注解的 AST 节点中。我已经硬编码了 AST 对象。
场景 1 将使用以下解析器：
字符串与数字的类型匹配问题
function parser(code) {
// fn("craig-string");
const expressionAst = {
type: "ExpressionStatement",
expression: {
type: "CallExpression",
callee: {
type: "Identifier",
name: "fn"
},
arguments: [
{
type: "StringLiteral", // Parser "Inference" for type.
value: "craig-string"
}
]
}
};
// function fn(a: number) {}
const declarationAst = {
type: "FunctionDeclaration",
id: {
type: "Identifier",
name: "fn"
},
params: [
{
type: "Identifier",
name: "a",
// 参数标识
typeAnnotation: {
// our only type annotation
type: "TypeAnnotation",
typeAnnotation: {
// 数字类型
type: "NumberTypeAnnotation"
}
}
}
],
body: {
type: "BlockStatement",
body: [] // "body" === block/line of code. Ours is empty
}
};
const programAst = {
type: "File",
program: {
type: "Program",
body: [expressionAst, declarationAst]
}
};
// normal AST except with typeAnnotations on
return programAst;
}
可以看到场景 1 中，第一行 fn("craig-string") 语句的 AST 对应 expressionAst，第二行声明函数的 AST 对应 declarationAst。最后返回一个 programmast，它是一个包含两个 AST 块的程序。
在AST中，您可以看到参数标识符 a 上的 typeAnnotation，与它在代码中的位置相匹配。
场景 2 将使用以下解析器：
使用未定义的未知类型
function parser(code) {
// fn("craig-string");
const expressionAst = {
type: "ExpressionStatement",
expression: {
type: "CallExpression",
callee: {
type: "Identifier",
name: "fn"
},
arguments: [
{
type: "StringLiteral", // Parser "Inference" for type.
value: "craig-string"
}
]
}
};
// function fn(a: made_up_type) {}
const declarationAst = {
type: "FunctionDeclaration",
id: {
type: "Identifier",
name: "fn"
},
params: [
{
type: "Identifier",
name: "a",
typeAnnotation: {
// our only type annotation
type: "TypeAnnotation",
typeAnnotation: {
// 参数类型不同于场景 1
type: "made_up_type" // BREAKS
}
}
}
],
body: {
type: "BlockStatement",
body: [] // "body" === block/line of code. Ours is empty
}
};
const programAst = {
type: "File",
program: {
type: "Program",
body: [expressionAst, declarationAst]
}
};
// normal AST except with typeAnnotations on
return programAst;
}
场景 2 的解析器的表达式、声明和程序 AST 块非常类似于场景 1。然而，区别在于 params 内部的 typeAnnotation 是 made_up_type，而不是场景 1 中的 NumberTypeAnnotation。
typeAnnotation: {
type: "made_up_type" // BREAKS
}
场景 3 使用以下解析器：
使用代码中未定义的属性名
function parser(code) {
// interface Person {
// name: string;
// }
const interfaceAst = {
type: "InterfaceDeclaration",
id: {
type: "Identifier",
name: "Person",
},
body: {
type: "ObjectTypeAnnotation",
properties: [
{
type: "ObjectTypeProperty",
key: {
type: "Identifier",
name: "name",
},
kind: "init",
method: false,
value: {
type: "StringTypeAnnotation",
},
},
],
},
};
// fn({nam: "craig"});
const expressionAst = {
type: "ExpressionStatement",
expression: {
type: "CallExpression",
callee: {
type: "Identifier",
name: "fn",
},
arguments: [
{
type: "ObjectExpression",
properties: [
{
type: "ObjectProperty",
method: false,
key: {
type: "Identifier",
name: "nam",
},
value: {
type: "StringLiteral",
value: "craig",
},
},
],
},
],
},
};
// function fn(a: Person) {}
const declarationAst = {
type: "FunctionDeclaration",
id: {
type: "Identifier",
name: "fn",
},
params: [
{
type: "Identifier",
name: "a",
//
typeAnnotation: {
type: "TypeAnnotation",
typeAnnotation: {
type: "GenericTypeAnnotation",
id: {
type: "Identifier",
name: "Person",
},
},
},
},
],
body: {
type: "BlockStatement",
body: [], // Empty function
},
};
const programAst = {
type: "File",
program: {
type: "Program",
body: [interfaceAst, expressionAst, declarationAst],
},
};
// normal AST except with typeAnnotations on
return programAst;
}
除了表达式、声明和程序 AST 块之外，还有一个 interfaceAst 块，它负责保存 InterfaceDeclaration AST。
在declarationAst 块的 typeAnnotation 节点上有一个 GenericType，因为它接受一个对象标识符，即 Person。在这个场景中，programAst 将返回这三个对象的数组。
解析器的相似性
从上面可以得知，这三种有共同点， 3 个场景中保存所有的类型注解的主要区域是 declaration。
检查器
现在来看编译器的类型检查部分。
它需要遍历所有程序主体的 AST 对象，并根据节点类型进行适当的类型检查。我们将把所有错误添加到一个数组中，并返回给调用者以便打印。
在我们进一步讨论之前，对于每种类型，我们将使用的基本逻辑是：
函数声明：检查参数的类型是否有效，然后检查函数体中的每个语句。
表达式：找到被调用的函数声明，获取声明上的参数类型，然后获取函数调用表达式传入的参数类型，并进行比较。
代码
以下代码中包含 typeChecks 对象（和 errors 数组) ，它将用于表达式检查和基本的注解（annotation）检查。
const errors = [];
// 注解类型
const ANNOTATED_TYPES = {
NumberTypeAnnotation: "number",
GenericTypeAnnotation: true
};
// 类型检查的逻辑
const typeChecks = {
// 比较形参和实参的类型
expression: (declarationFullType, callerFullArg) => {
switch (declarationFullType.typeAnnotation.type) {
// 注解为 number 类型
case "NumberTypeAnnotation":
// 如果调用时传入的是数字，返回 true
return callerFullArg.type === "NumericLiteral";
// 注解为通用类型
case "GenericTypeAnnotation": // non-native
// 如果是对象，检查对象的属性
if (callerFullArg.type === "ObjectExpression") {
// 获取接口节点
const interfaceNode = ast.program.body.find(
node => node.type === "InterfaceDeclaration"
);
const properties = interfaceNode.body.properties;
//遍历检查调用时的每个属性
properties.map((prop, index) => {
const name = prop.key.name;
const associatedName = callerFullArg.properties[index].key.name;
// 没有匹配，将错误信息存入 errors
if (name !== associatedName) {
errors.push(
`Property "${associatedName}" does not exist on interface "${interfaceNode.id.name}". Did you mean Property "${name}"?`
);
}
});
}
return true; // as already logged
}
},
annotationCheck: arg => {
return !!ANNOTATED_TYPES[arg];
}
};
让我们来看一下代码，我们的 expression 有两种类型的检查：
对于
NumberTypeAnnotation;调用时类型应为AnumericTeral（即，如果注解为数字，则调用时类型应为数字）。场景1将在此处失败，但未记录任何错误信息。对于
GenericTypeAnnotation;如果是一个对象，我们将在 AST 中查找InterfaceDeclaration节点，然后检查该接口上调用者的每个属性。之后将所有错误信息都会被存到errors数组中，场景3将在这里失败并得到这个错误。
我们的处理仅限于这个文件中，大多数类型检查器都有作用域的概念，因此它们能够确定声明在运行时的准确位置。我们的工作更简单，因为它只是一个
POC。
以下代码包含程序体中每个节点类型的处理。这就是上面调用类型检查逻辑的地方。
// Process program
ast.program.body.map(stnmt => {
switch (stnmt.type) {
case "FunctionDeclaration":
stnmt.params.map(arg => {
// Does arg has a type annotation?
if (arg.typeAnnotation) {
const argType = arg.typeAnnotation.typeAnnotation.type;
// Is type annotation valid
const isValid = typeChecks.annotationCheck(argType);
if (!isValid) {
errors.push(
`Type "${argType}" for argument "${arg.name}" does not exist`
);
}
}
});
// Process function "block" code here
stnmt.body.body.map(line => {
// Ours has none
});
return;
case "ExpressionStatement":
const functionCalled = stnmt.expression.callee.name;
const declationForName = ast.program.body.find(
node =>
node.type === "FunctionDeclaration" &&
node.id.name === functionCalled
);
// Get declaration
if (!declationForName) {
errors.push(`Function "${functionCalled}" does not exist`);
return;
}
// Array of arg-to-type. e.g. 0 = NumberTypeAnnotation
const argTypeMap = declationForName.params.map(param => {
if (param.typeAnnotation) {
return param.typeAnnotation;
}
});
// Check exp caller "arg type" with declaration "arg type"
stnmt.expression.arguments.map((arg, index) => {
const declarationType = argTypeMap[index].typeAnnotation.type;
const callerType = arg.type;
const callerValue = arg.value;
// Declaration annotation more important here
const isValid = typeChecks.expression(
argTypeMap[index], // declaration details
arg // caller details
);
if (!isValid) {
const annotatedType = ANNOTATED_TYPES[declarationType];
// Show values to user, more explanatory than types
errors.push(
`Type "${callerValue}" is incompatible with "${annotatedType}"`
);
}
});
return;
}
});
让我们再次遍历代码，按类型对其进行分解。
FunctionDeclaration (即 function hello(){})
首先处理 arguments/params。如果找到类型注解，就检查给定参数的类型 argType 是否存在。如果不进行错误处理，场景 2 会在这里报错误。
之后处理函数体，但是我们知道没有函数体需要处理，所以我把它留空了。
stnmt.body.body.map(line => {
// Ours has none
});
ExpressionStatement (即 hello())
首先检查程序中函数的声明。这就是作用域将应用于实际类型检查器的地方。如果找不到声明，就将错误信息添加到 errors 数组中。
接下来，我们针对调用时传入的参数类型（实参类型）检查每个已定义的参数类型。如果发现类型不匹配，则向 errors 数组中添加一个错误。场景 1 和场景 2 在这里都会报错。
运行我们的编译器
源码存放在这里，该文件一次性处理所有三个 AST 节点对象并记录错误。
运行它时，我得到以下信息：
总而言之：
场景 1：
fn("craig-string"); // throw with string vs number
function fn(a: number) {}
我们定义参数为 number 的类型，然后用字符串调用它。
场景 2：
fn("craig-string"); // throw with string vs ?
function fn(a: made_up_type) {} // throw with bad type
我们在函数参数上定义了一个不存在的类型，然后调用我们的函数，所以我们得到了两个错误(一个是定义的错误类型，另一个是类型不匹配的错误)。
场景 3：
interface Person {
name: string;
}
fn({ nam: "craig" }); // throw with "nam" vs "name"
function fn(a: Person) {}
我们定义了一个接口，但是使用了一个名为 nam 的属性，这个属性不在对象上，错误提示我们是否要使用 name。
我们遗漏了什么？
如前所述，类型编译器还有许多其他部分，我们在编译器中省略了这些部分。其中包括：
解析器：我们是手动编写的 AST 代码，它们实际上是在类型的编译器上解析生成。 预处理/语言编译器: 一个真正的编译器具有插入 IDE 并在适当的时候重新运行的机制。 懒编译：没有关于更改或内存使用的信息。 转换：我们跳过了编译器的最后一部分，也就是生成本机 JavaScript 代码的地方。 作用域：因为我们的 POC 是一个单一的文件，它不需要理解作用域的概念，但是真正的编译器必须始终知道上下文。
非常感谢您的阅读和观看，我从这项研究中了解了大量关于类型系统的知识，希望对您有所帮助。以上完整代码您可以在这里找到。（给原作者 start）
备注：
原作者在源码中使用的 Node 模块方式为 ESM（ES Module），在将源码克隆到本地后，如果运行不成功，需要修改 start 指令，添加启动参数 --experimental-modules。
"start": "node --experimental-modules src/index.mjs",
END
“分享、点赞、在看” 支持一波 