探索類型系統(tǒng)的底層 - 自己實現(xiàn)一個 TypeScript(硬核干貨)
原文：https://indepth.dev/under-the-hood-of-type-systems/
DawnL 譯
這篇文章包含兩個部分：
A 部分：類型系統(tǒng)編譯器概述(包括 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 類型系統(tǒng)編譯器職責(zé) Advanced type checker features 高級類型檢查器的功能
B 部分：構(gòu)建我們自己的類型系統(tǒng)編譯器
The parser 解析器 The checker 檢查器 Running our compiler 運行我們的編譯器 What have we missed? 我們遺漏了什么？
A 部分：類型系統(tǒng)編譯器概述
語法 vs 語義
語法和語義之間的區(qū)別對于早期的運行很重要。
語法 - Syntax
語法通常是指 JavaScript 本機代碼。本質(zhì)上是詢問給定的 JavaScript 代碼在運行時是否正確。
例如，下面的語法是正確的：
var foo: number = "not a number";
語義 - Semantics
這是特定于類型系統(tǒng)的代碼。本質(zhì)上是詢問附加到代碼中的給定類型是否正確。
例如，上面的代碼在語法上是正確的，但在語義上是錯誤的(將變量定義為一個數(shù)字類型，但是值是一個字符串)。
接下來是 JavaScript 生態(tài)系統(tǒng)中的 AST 和編譯器。
什么是 AST？
在進一步討論之前，我們需要快速了解一下 JavaScript 編譯器中的一個重要機制 AST。
關(guān)于 AST 詳細介紹請看這篇文章。
AST 的意思是抽象語法樹 ，它是一個表示程序代碼的節(jié)點樹。Node 是最小單元，基本上是一個具有 type 和 location 屬性的 POJO（即普通 JavaScript 對象）。所有節(jié)點都有這兩個屬性，但根據(jù)類型，它們也可以具有其他各種屬性。
在 AST 格式中，代碼非常容易操作，因此可以執(zhí)行添加、刪除甚至替換等操作。
例如下面這段代碼：
function add(number) {
return number + 1;
}
將解析成以下 AST：
編譯器類型
在 JavaScript 生態(tài)系統(tǒng)中有兩種主要的編譯器類型：
1. 原生編譯器（Native compiler）
原生編譯器將代碼轉(zhuǎn)換為可由服務(wù)器或計算機運行的代碼格式(即機器代碼)。類似于 Java 生態(tài)系統(tǒng)中的編譯器 - 將代碼轉(zhuǎn)換為字節(jié)碼，然后將字節(jié)碼轉(zhuǎn)換為本機代碼。
2. 語言編譯器
語言編譯器扮演著不同的角色。TypeScript 和 Flow 的編譯器在將代碼輸出到 JavaScript 時都算作語言編譯器。
語言編譯器與原生編譯器的主要區(qū)別在于，前者的編譯目的是 tooling-sake（例如優(yōu)化代碼性能或添加附加功能），而不是為了生成機器代碼。
語言編譯器是做什么的？
在類型系統(tǒng)編譯器中，總結(jié)的兩個最基本的核心職責(zé)是：
1. 執(zhí)行類型檢查
引入類型（通常是通過顯式注解或隱式推理），以及檢查一種類型是否匹配另一種類型的方法，例如 string 和 number。
2. 運行語言服務(wù)器
對于一個在開發(fā)環(huán)境中工作的類型系統(tǒng)（type system）來說，最好能在 IDE 中運行任何類型檢查，并為用戶提供即時反饋。
語言服務(wù)器將類型系統(tǒng)連接到 IDE，它們可以在后臺運行編譯器，并在用戶保存文件時重新運行。流行的語言，如 TypeScript 和 Flow 都包含一個語言服務(wù)器。
3. 代碼轉(zhuǎn)換
許多類型系統(tǒng)包含原生 JavaScript 不支持的代碼(例如不支持類型注解) ，因此它們必須將不受支持的 JavaScript 轉(zhuǎn)換為受支持的 JavaScript 代碼。
關(guān)于代碼轉(zhuǎn)換更詳細的介紹，可以參考原作者的這兩篇文章 Web Bundler 和 Source Maps。
語言編譯器是如何工作的？
對于大多數(shù)編譯器來說，在某種形式上有三個共同的階段。
1. 將源代碼解析為 AST
詞法分析 -> 將代碼字符串轉(zhuǎn)換為令牌流(即數(shù)組) 語法分析 -> 將令牌流轉(zhuǎn)換為 AST 表示形式
解析器檢查給定代碼的語法。類型系統(tǒng)必須有自己的解析器，通常包含數(shù)千行代碼。
Babel 解析器 中的 2200+ 行代碼，僅用于處理 statement 語句（請參閱此處）。
Hegel 解析器將 typeAnnotation 屬性設(shè)置為具有類型注解的代碼（可以在這里看到）。
TypeScript 的解析器擁有 8900+ 行代碼(這里是它開始遍歷樹的地方)。它包含了一個完整的 JavaScript 超集，所有這些都需要解析器來理解。
2. 在 AST 上轉(zhuǎn)換節(jié)點
操作 AST 節(jié)點
這里將執(zhí)行應(yīng)用于 AST 的任何轉(zhuǎn)換。
3. 生成源代碼
將 AST 轉(zhuǎn)換為 JavaScript 源代碼字符串
類型系統(tǒng)必須將任何非 js 兼容的 AST 映射回原生 JavaScript。
類型系統(tǒng)如何處理這種情況呢？
類型系統(tǒng)編譯器（compiler）職責(zé)
除了上述步驟之外，類型系統(tǒng)編譯器通常還會在解析之后包括一個或兩個額外步驟，其中包括特定于類型的工作。
順便說一下，TypeScript 的編譯器實際上有 5 個階段，它們是：
語言服務(wù)預(yù)處理器 - Language server pre-processor 解析器 - Parser 結(jié)合器 - Binder 檢查器 - Checker 發(fā)射器 - Emitter
正如上面看到的，語言服務(wù)器包含一個預(yù)處理器，它觸發(fā)類型編譯器只在已更改的文件上運行。這會監(jiān)聽任意的 import 語句，來確定還有哪些內(nèi)容可能發(fā)生了更改，并且需要在下次重新運行時攜帶這些內(nèi)容。
此外，編譯器只能重新處理 AST 結(jié)構(gòu)中已更改的分支。關(guān)于更多 lazy compilation，請參閱下文。
類型系統(tǒng)編譯器有兩個常見的職責(zé)：
1. 推導(dǎo) - Inferring
對于沒有注解的代碼需要進行推斷。關(guān)于這點，這里推薦一篇關(guān)于何時使用類型注解和何時讓引擎使用推斷的文章。
使用預(yù)定義的算法，引擎將計算給定變量或者函數(shù)的類型。
TypeScript 在其 Binding 階段（兩次語義傳遞中的第一次）中使用最佳公共類型算法。它考慮每個候選類型并選擇與所有其他候選類型兼容的類型。上下文類型在這里起作用，也會做為最佳通用類型的候選類型。在這里的 TypeScript 規(guī)范中有更多的幫助。
let zoo: Animal[] = [new Rhino(), new Elephant(), new Snake()];
TypeScript 實際上引入了 Symbols（interface）的概念，這些命名聲明將 AST 中的聲明節(jié)點與其他聲明進行連接，從而形成相同的實體。它們是 TypeScript 語義系統(tǒng)的基本構(gòu)成。
2. 檢查 - Checking
現(xiàn)在類型推斷已經(jīng)完成，類型已經(jīng)分配，引擎可以運行它的類型檢查。他們檢查給定代碼的 semantics。這些類型的檢查有很多種，從類型錯誤匹配到類型不存在。
對于 TypeScript 來說，這是 Checker (第二個語義傳遞) ，它有 20000+ 行代碼。
我覺得這給出了一個非常強大的 idea，即在如此多的不同場景中檢查如此多的不同類型是多么的復(fù)雜和困難。
類型檢查器不依賴于調(diào)用代碼，即如果一個文件中的任何代碼被執(zhí)行（例如，在運行時）。類型檢查器將處理給定文件中的每一行，并運行適當(dāng)?shù)臋z查。
高級類型檢查器功能
由于這些概念的復(fù)雜性，我們今天不深入探討以下幾個概念：
懶編譯 - Lazy compilation
現(xiàn)代編譯的一個共同特征是延遲加載。他們不會重新計算或重新編譯文件或 AST 分支，除非絕對需要。
TypeScript 預(yù)處理程序可以使用緩存在內(nèi)存中的前一次運行的 AST 代碼。這將大大提高性能，因為它只需要關(guān)注程序或節(jié)點樹的一小部分已更改的內(nèi)容。
TypeScript 使用不可變的只讀數(shù)據(jù)結(jié)構(gòu)，這些數(shù)據(jù)結(jié)構(gòu)存儲在它所稱的 look aside tables 中。這樣很容易知道什么已經(jīng)改變，什么沒有改變。
穩(wěn)健性
在編譯時，有些操作編譯器不確定是安全的，必須等待運行時。每個編譯器都必須做出困難的選擇，以確定哪些內(nèi)容將被包含，哪些不會被包含。TypeScript 有一些被稱為不健全的區(qū)域（即需要運行時類型檢查）。
我們不會在編譯器中討論上述特性，因為它們增加了額外的復(fù)雜性，對于我們的小 POC 來說不值得。
現(xiàn)在令人興奮的是，我們自己也要實現(xiàn)一個編譯器。
B 部分：構(gòu)建我們自己的類型系統(tǒng)編譯器
我們將構(gòu)建一個編譯器，它可以對三個不同的場景運行類型檢查，并為每個場景拋出特定的信息。
我們將其限制在三個場景中的原因是，我們可以關(guān)注每一個場景中的具體機制，并希望到最后能夠?qū)θ绾我敫鼜?fù)雜的類型檢查有一個更好的構(gòu)思。
我們將在編譯器中使用函數(shù)聲明和表達式(調(diào)用該函數(shù))。
這些場景包括：
1. 字符串與數(shù)字的類型匹配問題
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) {}
實現(xiàn)我們的編譯器，需要兩部分：解析器和檢查器。
解析器 - Parser
前面提到，我們今天不會關(guān)注解析器。我們將遵循 Hegel 的解析方法，假設(shè)一個 typeAnnotation 對象已經(jīng)附加到所有帶注解的 AST 節(jié)點中。我已經(jīng)硬編碼了 AST 對象。
場景 1 將使用以下解析器：
字符串與數(shù)字的類型匹配問題
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",
// 參數(shù)標(biāo)識
typeAnnotation: {
// our only type annotation
type: "TypeAnnotation",
typeAnnotation: {
// 數(shù)字類型
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 對應(yīng) expressionAst，第二行聲明函數(shù)的 AST 對應(yīng) declarationAst。最后返回一個 programmast，它是一個包含兩個 AST 塊的程序。
在AST中，您可以看到參數(shù)標(biāo)識符 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: {
// 參數(shù)類型不同于場景 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。然而，區(qū)別在于 params 內(nèi)部的 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 塊，它負責(zé)保存 InterfaceDeclaration AST。
在declarationAst 塊的 typeAnnotation 節(jié)點上有一個 GenericType，因為它接受一個對象標(biāo)識符，即 Person。在這個場景中，programAst 將返回這三個對象的數(shù)組。
解析器的相似性
從上面可以得知，這三種有共同點， 3 個場景中保存所有的類型注解的主要區(qū)域是 declaration。
檢查器
現(xiàn)在來看編譯器的類型檢查部分。
它需要遍歷所有程序主體的 AST 對象，并根據(jù)節(jié)點類型進行適當(dāng)?shù)念愋蜋z查。我們將把所有錯誤添加到一個數(shù)組中，并返回給調(diào)用者以便打印。
在我們進一步討論之前，對于每種類型，我們將使用的基本邏輯是：
函數(shù)聲明：檢查參數(shù)的類型是否有效，然后檢查函數(shù)體中的每個語句。
表達式：找到被調(diào)用的函數(shù)聲明，獲取聲明上的參數(shù)類型，然后獲取函數(shù)調(diào)用表達式傳入的參數(shù)類型，并進行比較。
代碼
以下代碼中包含 typeChecks 對象（和 errors 數(shù)組) ，它將用于表達式檢查和基本的注解（annotation）檢查。
const errors = [];
// 注解類型
const ANNOTATED_TYPES = {
NumberTypeAnnotation: "number",
GenericTypeAnnotation: true
};
// 類型檢查的邏輯
const typeChecks = {
// 比較形參和實參的類型
expression: (declarationFullType, callerFullArg) => {
switch (declarationFullType.typeAnnotation.type) {
// 注解為 number 類型
case "NumberTypeAnnotation":
// 如果調(diào)用時傳入的是數(shù)字，返回 true
return callerFullArg.type === "NumericLiteral";
// 注解為通用類型
case "GenericTypeAnnotation": // non-native
// 如果是對象，檢查對象的屬性
if (callerFullArg.type === "ObjectExpression") {
// 獲取接口節(jié)點
const interfaceNode = ast.program.body.find(
node => node.type === "InterfaceDeclaration"
);
const properties = interfaceNode.body.properties;
//遍歷檢查調(diào)用時的每個屬性
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;調(diào)用時類型應(yīng)為AnumericTeral（即，如果注解為數(shù)字，則調(diào)用時類型應(yīng)為數(shù)字）。場景1將在此處失敗，但未記錄任何錯誤信息。對于
GenericTypeAnnotation;如果是一個對象，我們將在 AST 中查找InterfaceDeclaration節(jié)點，然后檢查該接口上調(diào)用者的每個屬性。之后將所有錯誤信息都會被存到errors數(shù)組中，場景3將在這里失敗并得到這個錯誤。
我們的處理僅限于這個文件中，大多數(shù)類型檢查器都有作用域的概念，因此它們能夠確定聲明在運行時的準(zhǔn)確位置。我們的工作更簡單，因為它只是一個
POC。
以下代碼包含程序體中每個節(jié)點類型的處理。這就是上面調(diào)用類型檢查邏輯的地方。
// 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。如果找到類型注解，就檢查給定參數(shù)的類型 argType 是否存在。如果不進行錯誤處理，場景 2 會在這里報錯誤。
之后處理函數(shù)體，但是我們知道沒有函數(shù)體需要處理，所以我把它留空了。
stnmt.body.body.map(line => {
// Ours has none
});
ExpressionStatement (即 hello())
首先檢查程序中函數(shù)的聲明。這就是作用域?qū)?yīng)用于實際類型檢查器的地方。如果找不到聲明，就將錯誤信息添加到 errors 數(shù)組中。
接下來，我們針對調(diào)用時傳入的參數(shù)類型（實參類型）檢查每個已定義的參數(shù)類型。如果發(fā)現(xiàn)類型不匹配，則向 errors 數(shù)組中添加一個錯誤。場景 1 和場景 2 在這里都會報錯。
運行我們的編譯器
源碼存放在這里，該文件一次性處理所有三個 AST 節(jié)點對象并記錄錯誤。
運行它時，我得到以下信息：
總而言之：
場景 1：
fn("craig-string"); // throw with string vs number
function fn(a: number) {}
我們定義參數(shù)為 number 的類型，然后用字符串調(diào)用它。
場景 2：
fn("craig-string"); // throw with string vs ?
function fn(a: made_up_type) {} // throw with bad type
我們在函數(shù)參數(shù)上定義了一個不存在的類型，然后調(diào)用我們的函數(shù)，所以我們得到了兩個錯誤(一個是定義的錯誤類型，另一個是類型不匹配的錯誤)。
場景 3：
interface Person {
name: string;
}
fn({ nam: "craig" }); // throw with "nam" vs "name"
function fn(a: Person) {}
我們定義了一個接口，但是使用了一個名為 nam 的屬性，這個屬性不在對象上，錯誤提示我們是否要使用 name。
我們遺漏了什么？
如前所述，類型編譯器還有許多其他部分，我們在編譯器中省略了這些部分。其中包括：
解析器：我們是手動編寫的 AST 代碼，它們實際上是在類型的編譯器上解析生成。 預(yù)處理/語言編譯器: 一個真正的編譯器具有插入 IDE 并在適當(dāng)?shù)臅r候重新運行的機制。 懶編譯：沒有關(guān)于更改或內(nèi)存使用的信息。 轉(zhuǎn)換：我們跳過了編譯器的最后一部分，也就是生成本機 JavaScript 代碼的地方。 作用域：因為我們的 POC 是一個單一的文件，它不需要理解作用域的概念，但是真正的編譯器必須始終知道上下文。
非常感謝您的閱讀和觀看，我從這項研究中了解了大量關(guān)于類型系統(tǒng)的知識，希望對您有所幫助。以上完整代碼您可以在這里找到。（給原作者 start）
備注：
原作者在源碼中使用的 Node 模塊方式為 ESM（ES Module），在將源碼克隆到本地后，如果運行不成功，需要修改 start 指令，添加啟動參數(shù) --experimental-modules。
"start": "node --experimental-modules src/index.mjs",
END
“分享、點贊、在看” 支持一波 