原文：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 個階段，它們是：

1. 語言服務預處理器 - Language server pre-processor

2. 解析器 - Parser

3. 結合器 - Binder

4. 檢查器 - Checker

5. 發射器 - 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",

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/1DWjPk_7rI3-W5EGPAHYMA