(硬核干貨)探索類型系統(tǒng)的底層 - 自己實現(xiàn)一個 TS
點擊上方關(guān)注 前端技術(shù)江湖，一起學習，天天進步
原文：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)編譯器職責 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)換為可由服務器或計算機運行的代碼格式(即機器代碼)。類似于 Java 生態(tài)系統(tǒng)中的編譯器 - 將代碼轉(zhuǎn)換為字節(jié)碼，然后將字節(jié)碼轉(zhuǎn)換為本機代碼。
2. 語言編譯器
語言編譯器扮演著不同的角色。TypeScript 和 Flow 的編譯器在將代碼輸出到 JavaScript 時都算作語言編譯器。
語言編譯器與原生編譯器的主要區(qū)別在于，前者的編譯目的是 tooling-sake（例如優(yōu)化代碼性能或添加附加功能），而不是為了生成機器代碼。
語言編譯器是做什么的？
在類型系統(tǒng)編譯器中，總結(jié)的兩個最基本的核心職責是：
1. 執(zhí)行類型檢查
引入類型（通常是通過顯式注解或隱式推理），以及檢查一種類型是否匹配另一種類型的方法，例如 string 和 number。
2. 運行語言服務器
對于一個在開發(fā)環(huán)境中工作的類型系統(tǒng)（type system）來說，最好能在 IDE 中運行任何類型檢查，并為用戶提供即時反饋。
語言服務器將類型系統(tǒng)連接到 IDE，它們可以在后臺運行編譯器，并在用戶保存文件時重新運行。流行的語言，如 TypeScript 和 Flow 都包含一個語言服務器。
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í)行應用于 AST 的任何轉(zhuǎn)換。
3. 生成源代碼
將 AST 轉(zhuǎn)換為 JavaScript 源代碼字符串
類型系統(tǒng)必須將任何非 js 兼容的 AST 映射回原生 JavaScript。
類型系統(tǒng)如何處理這種情況呢？
類型系統(tǒng)編譯器（compiler）職責
除了上述步驟之外，類型系統(tǒng)編譯器通常還會在解析之后包括一個或兩個額外步驟，其中包括特定于類型的工作。
順便說一下，TypeScript 的編譯器實際上有 5 個階段，它們是：
語言服務預處理器 - Language server pre-processor 解析器 - Parser 結(jié)合器 - Binder 檢查器 - Checker 發(fā)射器 - Emitter
正如上面看到的，語言服務器包含一個預處理器，它觸發(fā)類型編譯器只在已更改的文件上運行。這會監(jiān)聽任意的 import 語句，來確定還有哪些內(nèi)容可能發(fā)生了更改，并且需要在下次重新運行時攜帶這些內(nèi)容。
此外，編譯器只能重新處理 AST 結(jié)構(gòu)中已更改的分支。關(guān)于更多 lazy compilation，請參閱下文。
類型系統(tǒng)編譯器有兩個常見的職責：
1. 推導 - Inferring
對于沒有注解的代碼需要進行推斷。關(guān)于這點，這里推薦一篇關(guān)于何時使用類型注解和何時讓引擎使用推斷的文章。
使用預定義的算法，引擎將計算給定變量或者函數(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，即在如此多的不同場景中檢查如此多的不同類型是多么的復雜和困難。
類型檢查器不依賴于調(diào)用代碼，即如果一個文件中的任何代碼被執(zhí)行（例如，在運行時）。類型檢查器將處理給定文件中的每一行，并運行適當?shù)臋z查。
高級類型檢查器功能
由于這些概念的復雜性，我們今天不深入探討以下幾個概念：
懶編譯 - Lazy compilation
現(xiàn)代編譯的一個共同特征是延遲加載。他們不會重新計算或重新編譯文件或 AST 分支，除非絕對需要。
TypeScript 預處理程序可以使用緩存在內(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ū)域（即需要運行時類型檢查）。
我們不會在編譯器中討論上述特性，因為它們增加了額外的復雜性，對于我們的小 POC 來說不值得。
現(xiàn)在令人興奮的是，我們自己也要實現(xiàn)一個編譯器。
B 部分：構(gòu)建我們自己的類型系統(tǒng)編譯器
我們將構(gòu)建一個編譯器，它可以對三個不同的場景運行類型檢查，并為每個場景拋出特定的信息。
我們將其限制在三個場景中的原因是，我們可以關(guān)注每一個場景中的具體機制，并希望到最后能夠?qū)θ绾我敫鼜碗s的類型檢查有一個更好的構(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ù)標識
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 對應 expressionAst，第二行聲明函數(shù)的 AST 對應 declarationAst。最后返回一個 programmast，它是一個包含兩個 AST 塊的程序。
在AST中，您可以看到參數(shù)標識符 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 塊，它負責保存 InterfaceDeclaration AST。
在declarationAst 塊的 typeAnnotation 節(jié)點上有一個 GenericType，因為它接受一個對象標識符，即 Person。在這個場景中，programAst 將返回這三個對象的數(shù)組。
解析器的相似性
從上面可以得知，這三種有共同點， 3 個場景中保存所有的類型注解的主要區(qū)域是 declaration。
檢查器
現(xiàn)在來看編譯器的類型檢查部分。
它需要遍歷所有程序主體的 AST 對象，并根據(jù)節(jié)點類型進行適當?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)用時類型應為AnumericTeral（即，如果注解為數(shù)字，則調(diào)用時類型應為數(shù)字）。場景1將在此處失敗，但未記錄任何錯誤信息。對于
GenericTypeAnnotation;如果是一個對象，我們將在 AST 中查找InterfaceDeclaration節(jié)點，然后檢查該接口上調(diào)用者的每個屬性。之后將所有錯誤信息都會被存到errors數(shù)組中，場景3將在這里失敗并得到這個錯誤。
我們的處理僅限于這個文件中，大多數(shù)類型檢查器都有作用域的概念，因此它們能夠確定聲明在運行時的準確位置。我們的工作更簡單，因為它只是一個
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ū)糜趯嶋H類型檢查器的地方。如果找不到聲明，就將錯誤信息添加到 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 代碼，它們實際上是在類型的編譯器上解析生成。 預處理/語言編譯器: 一個真正的編譯器具有插入 IDE 并在適當?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",The End
歡迎自薦投稿到《前端技術(shù)江湖》，如果你覺得這篇內(nèi)容對你挺有啟發(fā)，記得點個 「在看」哦
點個『在看』支持下 