0. 引言

TypedSql 是源自某天突如其來的「一點不滿」而開始的專案。

在 .NET 中寫程式碼時，經常會遇到「像查詢一樣的處理」的情況。

例如，當我們希望從已在記憶體中的 List<T> 或陣列中過濾出某些列時，我們通常會面臨以下三種選擇：

• 直接使用 foreach 迴圈 — 雖然快速且明確，但有點冗長
• 使用 LINQ（語言整合查詢） — 寫起來感覺很好，但迭代器和委派的開銷讓人擔心
• 寧可將資料送入資料庫，並撰寫真正的 SQL — 這似乎有點過頭了

正當我希望能有「再好一點的」選擇時，TypedSql 的實驗開始了。

這時產生了這樣的想法：

如果把 C# 的型別系統本身當作查詢計畫來處理，會怎麼樣呢？

一般來說，

• 在執行時組建表達式樹（Expression Tree）
• 然後將其應用到資料上進行解釋

這是一種常見的風格。

但 TypedSql 顛覆了這一點。

• 解析類似 SQL 的字串
• 將結果以「嵌套的泛型型別」來表示
• 接下來完全通過靜態方法來流轉處理

換句話說，將查詢執行計畫完整地壓入型別中，這樣的遊玩方式。

1. 「查詢＝嵌套的泛型型別」

TypedSql 的核心思想非常簡單。

查詢是否可以用 WhereSelect<TRow, …, Stop<...>> 這種 嵌套的泛型型別鏈 來表示？

這不是像 LINQ 那樣「用方法鏈來寫查詢」，而是直接把鏈的結構用「型別參數」來表示。

1.1 將整個管道作為型別

在 TypedSql 中，編譯後的查詢全部是「關閉的泛型型別」。
管道的組件大約是這樣的：

• Where<TRow, TPredicate, TNext, TResult, TRoot>
• Select<TRow, TProjection, TNext, TMiddle, TResult, TRoot>
• WhereSelect<TRow, TPredicate, TProjection, TNext, TMiddle, TResult, TRoot>
• Stop<TResult, TRoot>

這些都實現了下一個介面。

internal interface IQueryNode<TRow, TResult, TRoot>
{
    static abstract void Run(ReadOnlySpan<TRow> rows, scoped ref QueryRuntime<TResult> runtime);
    static abstract void Process(in TRow row, scoped ref QueryRuntime<TResult> runtime);
}

• Run 負責外部的迴圈（遍歷所有行）
• Process 負責逐行處理

這樣分工。

例如，Where 節點長得像這樣。

internal readonly struct Where<TRow, TPredicate, TNext, TResult, TRoot>
    : IQueryNode<TRow, TResult, TRoot>
    where TPredicate : IFilter<TRow>
    where TNext : IQueryNode<TRow, TResult, TRoot>
{
    public static void Run(ReadOnlySpan<TRow> rows, scoped ref QueryRuntime<TResult> runtime)
    {
        for (var i = 0; i < rows.Length; i++)
        {
            Process(in rows[i], ref runtime);
        }
    }

    public static void Process(in TRow row, scoped ref QueryRuntime<TResult> runtime)
    {
        if (TPredicate.Evaluate(in row))
        {
            TNext.Process(in row, ref runtime);
        }
    }
}

這裡重要的是，

• 管道的「形狀」全部由型別參數封閉
• 每個節點都是 struct，不會產生實例
• 所有操作都只用靜態方法調用完成

這樣的設計。

從 JIT（即時編譯）來看，「一旦泛型參數被決定，其後就是靜態調用圖」。這表示有很大的優化空間。

1.2 將列（欄位）與投影統一為值型

查詢運行需要的信息有：

• 有哪些列
• 取出什麼值
• 如何過濾

TypedSql 在這方面也徹底地提供「值型 + 靜態方法」。

行是用戶自定義的任意型別（可以是類別也可以是記錄）。在此之上，添加一個 IColumn 來表示「如何從該行中提取值」。

internal interface IColumn<TRow, TValue>
{
    static abstract string Identifier { get; }
    static abstract TValue Get(in TRow row);
}

例如 Person.Name 列可以這樣實現。

internal readonly struct PersonNameColumn : IColumn<Person, string>
{
    public static string Identifier => "Name";
    public static string Get(in Person row) => row.Name;
}

這裡不需要實例。
「列名」和「提取值的方法」都是通過靜態方式來完成。

投影（SELECT 子句回傳的值）使用 IProjection。

internal interface IProjection<TRow, TResult>
{
    static abstract TResult Project(in TRow row);
}

對於「僅返回某一列」的投影，則可以這樣寫。

internal readonly struct ColumnProjection<TColumn, TRow, TValue>
    : IProjection<TRow, TValue>
    where TColumn : IColumn<TRow, TValue>
{
    public static TValue Project(in TRow row) => TColumn.Get(row);
}

當需要返回多列時，可以準備幾個專用的投影來組合 ValueTuple（值元組）。

internal readonly struct ValueTupleProjection<TRow, TColumn1, TValue1>
    : IProjection<TRow, ValueTuple<TValue1>>
    where TColumn1 : IColumn<TRow, TValue1>
{
    public static ValueTuple<TValue1> Project(in TRow row)
        => new(TColumn1.Get(row));
}

// … 提供專用類型至最多 7 列，然後使用 Rest 進行遞迴

在這裡也同樣適用，

• 全部都是 struct
• 全部都是靜態方法

這種統一規則。

1.3 用類型表示過濾（WHERE 子句）

過濾器是 IFilter<TRow>。

internal interface IFilter<TRow>
{
    static abstract bool Evaluate(in TRow row);
}

列與文字常數的比較則可以用 struct 來表示，例如：

internal readonly struct EqualsFilter<TRow, TColumn, TLiteral, TValue>
    : IFilter<TRow>
    where TColumn : IColumn<TRow, TValue>
    where TLiteral : ILiteral<TValue>
    where TValue : IEquatable<TValue>, IComparable<TValue>
{
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static bool Evaluate(in TRow row)
    {
        if (typeof(TValue).IsValueType)
        {
            return TColumn.Get(row).Equals(TLiteral.Value);
        }
        else
        {
            var left = TColumn.Get(row);
            var right = TLiteral.Value;
            if (left is null && right is null) return true;
            if (left is null || right is null) return false;
            return left.Equals(right);
        }
    }
}

這裡 TValue 無論是值型還是參考型都需要區分，從而處理 null 的情形。 .NET 的 JIT 支援這種模式，實際上，不會因為分支而產生額外的開銷。

>, <, != 等運算子也都是類似的方式用 struct 實現。

AND / OR / NOT 則以型別層級的邏輯運算符來堆疊。

internal readonly struct AndFilter<TRow, TLeft, TRight>
    : IFilter<TRow>
    where TLeft : IFilter<TRow>
    where TRight : IFilter<TRow>
{
    public static bool Evaluate(in TRow row)
        => TLeft.Evaluate(in row) && TRight.Evaluate(in row);
}

internal readonly struct OrFilter<TRow, TLeft, TRight>
    : IFilter<TRow>
    where TLeft : IFilter<TRow>
    where TRight : IFilter<TRow>
{
    public static bool Evaluate(in TRow row)
        => TLeft.Evaluate(in row) || TRight.Evaluate(in row);
}

internal readonly struct NotFilter<TRow, TPredicate>
    : IFilter<TRow>
    where TPredicate : IFilter<TRow>
{
    public static bool Evaluate(in TRow row)
        => !TPredicate.Evaluate(in row);
}

結果，WHERE 子句整體會形成 過濾型別的樹狀結構。這不是表達式樹，而是「型別樹」。

1.4 字串特別處理──ValueString

在 .NET 中，string 是參考型別。
這對於泛型世界來說，略顯麻煩。

• 參考型別會進行「泛型共享」
• 其結果是，內部會增加類似字典查詢的開銷

出於「熱路徑盡可能使用值型運行」的願望，TypedSql 將 string 包裝了一次。

internal readonly struct ValueString(string? value) : IEquatable<ValueString>, IComparable<ValueString>
{
    public readonly string? Value = value;

    public int CompareTo(ValueString other)
        => string.Compare(Value, other.Value, StringComparison.Ordinal);

    public bool Equals(ValueString other)
        => string.Equals(Value, other.Value, StringComparison.Ordinal);

    public override string? ToString() => Value;

    public static implicit operator ValueString(string value) => new(value);
    public static implicit operator string?(ValueString value) => value.Value;
}

string 列會自動轉換為 ValueStringColumn。

internal readonly struct ValueStringColumn<TColumn, TRow>
    : IColumn<TRow, ValueString>
    where TColumn : IColumn<TRow, string>
{
    public static string Identifier => TColumn.Identifier;

    public static ValueString Get(in TRow row)
        => new(TColumn.Get(row));
}

這樣的做法使得：

• 熱路徑儘可能僅用值型完成
• 字串比較始終統一為 ordinal
• 調用方的 API 仍為 string（透過隱式轉換完成）

獲得較為理想的平衡。

2. 解析小型 SQL 方言

TypedSql 不是針對全面功能的 SQL。
它的目標是「針對單一表格，在記憶體中的陣列進行簡單的查詢」。

支持的語法大致如下：

• SELECT * FROM $
• SELECT col FROM $
• SELECT col1, col2, ... FROM $
• WHERE 子句
  • 比較運算子：=, !=, >, <, >=, <=
  • 邏輯運算子：AND, OR, NOT
  • 括號
• 文字常數
  • 整數 (42)
  • 浮點數 (123.45)
  • 布林值 (true, false)
  • 單引號字串 ('Seattle'，用 '' 進行轉義)
  • null
• 列名不區分大小寫
• $ 是表示「當前來源（行的集合）」的佔位符

解析器的步驟分為兩個階段。

1. 將輸入的 SQL 進行分詞（切成單詞）
2. 構建小型抽象語法樹（AST）
   • ParsedQuery — SELECT 和可選的 WHERE
   • Selection — SelectAll 或列名列表
   • WhereExpression — 其中之一
     • ComparisonExpression
     • AndExpression
     • OrExpression
     • NotExpression
   • LiteralValue — 類型與實際值
     • LiteralKind.Integer + IntValue
     • LiteralKind.Float + FloatValue
     • LiteralKind.Boolean + BoolValue
     • LiteralKind.String + StringValue
     • LiteralKind.Null

在這個階段，仍然沒有 C# 的型別出現。
僅僅是在表達「語法結構」。

「那一列真的 int 嗎？」「那個文字常數可以轉換為 float 嗎？」這類型的一致性檢查將在後面的編譯階段進行。

3. 將文字常數表示為「型別」

TypedSql 中最“變態（好意義）”的部分，可能就在這裡。

將整數、浮點數、字符、字串和布林值等文字常數，統一表示為「型別」

所有的文字型別實現 ILiteral<T>。

internal interface ILiteral<T>
{
    static abstract T Value { get; }
}

• 整數（int）
• 浮點數（float）
• 字符（char）
• 布林值（bool）
• 字串（透過 ValueString）

等都遵循這個介面。

3.1 將數值文字分解為 16 進制的位

數值文字表達的型別被視作「分解為 16 進制的位」。

首先有表示一位的 IHex 及 Hex0 到 HexF 的 struct。

internal interface IHex
{
    static abstract int Value { get; }
}

internal readonly struct Hex0 : IHex { public static int Value => 0; }
// ...
internal readonly struct HexF : IHex { public static int Value => 15; }

整數文字被表示為由 8 位組成的 Int<H7, ..., H0> 型別。

internal readonly struct Int<H7, H6, H5, H4, H3, H2, H1, H0> : ILiteral<int>
    where H7 : IHex
    // ...
    where H0 : IHex
{
    public static int Value
        => (H7.Value << 28) | (H6.Value << 24) | (H5.Value << 20) | (H4.Value << 16)
        | (H3.Value << 12) | (H2.Value << 8) | (H1.Value << 4) | H0.Value;
}

浮點數（float）也有 8 位的位元組模式，並藉由 Unsafe.BitCast 轉換為 float。

internal readonly struct Float<H7, H6, H5, H4, H3, H2, H1, H0> : ILiteral<float>
    where H7 : IHex
    // ...
{
    public static float Value
        => Unsafe.BitCast<int, float>((H7.Value << 28) | (H6.Value << 24) | (H5.Value << 20)
            | (H4.Value << 16) | (H3.Value << 12) | (H2.Value << 8) | (H1.Value << 4) | H0.Value);
}

字符（char）則是 4 位的 16 進制。

internal readonly struct Char<H3, H2, H1, H0> : ILiteral<char>
    where H3 : IHex
    // ...
{
    public static char Value
        => (char)((H3.Value << 12) | (H2.Value << 8) | (H1.Value << 4) | H0.Value);
}

到這裡，我們可以僅用「作為型別參數傳遞的位元組模式」來表示文字常數。

例如，文字常數 42 會表示為 Int<Hex0, Hex0, Hex0, Hex0, Hex0, Hex0, Hex2, HexA> 的型別。'A' 這個字符字面量則可表示為 Char<Hex0, Hex0, Hex4, Hex1>。

3.2 字串文字：型別層級的鏈接列表

字串則要再複雜一層。

TypedSql 將字串表示為「串接每一個字符的文字型別形成的 型別層級的鏈接列表」。

其所需的介面為 IStringNode。

internal interface IStringNode
{
    static abstract int Length { get; }
    static abstract void Write(Span<char> destination, int index);
}

實作可分為三種。

• StringEnd — 終端（長度 0）
• StringNull — 表示 null 的特別節點（長度 -1）
• StringNode<TChar, TNext> — 表示一個字符加上剩餘部分

internal readonly struct StringEnd : IStringNode
{
    public static int Length => 0;
    public static void Write(Span<char> destination, int index) { }
}

internal readonly struct StringNull : IStringNode
{
    public static int Length => -1;
    public static void Write(Span<char> destination, int index) { }
}

internal readonly struct StringNode<TChar, TNext> : IStringNode
    where TChar : ILiteral<char>
    where TNext : IStringNode
{
    public static int Length => 1 + TNext.Length;

    public static void Write(Span<char> destination, int index)
    {
        destination[index] = TChar.Value;
        TNext.Write(destination, index + 1);
    }
}

透過這個「型別層級的列表」，將實際的 ValueString 組裝成 StringLiteral<TString>。

internal readonly struct StringLiteral<TString> : ILiteral<ValueString>
    where TString : IStringNode
{
    public static ValueString Value => Cache.Value;

    private static class Cache
    {
        public static readonly ValueString Value = Build();

        private static ValueString Build()
        {
            var length = TString.Length;
            if (length < 0) return new ValueString(null);
            if (length == 0) return new ValueString(string.Empty);

            var chars = new char[length];
            TString.Write(chars.AsSpan(), 0);
            return new string(chars, 0, length);
        }
    }
}

這樣的設計使得「型別只需一次組裝字串並緩存」。

3.2.1 'Seattle' 是怎麼成為型別的？

以 SQL WHERE City = 'Seattle' 為例。

1. 解析器發現 'Seattle'，然後，
   • Kind = LiteralKind.String
   • StringValue = "Seattle"
     生成此文字的常數信息。
2. 編譯器判斷對應的列為字串（實際上是 ValueString）。
3. 呼叫 LiteralTypeFactory.CreateStringLiteral("Seattle")。

在該方法內，大致執行以下處理：

• 起初 type = StringEnd
• 反向查看字串中的每個字符
• 將各字符轉換為 Char<...> 型別
• 逐步在前面串接形成 StringNode<Char<'e'>, StringEnd> 這樣的結構

最終型別大致如下。

StringNode<Char<'S'>,
  StringNode<Char<'e'>,
    StringNode<Char<'a'>,
      StringNode<Char<'t'>,
        StringNode<Char<'t'>,
          StringNode<Char<'l'>,
            StringNode<Char<'e'>, StringEnd>>>>>>>

這一個關閉的泛型型別完整地代表了 「字串文字 'Seattle'」。

EqualsFilter 将根据 TLiteral.Value 提取 ValueString("Seattle")。

3.2.2 null 字串亦可由型別區別

null 也會被妥善地作為型別處理。

• 如果是 WHERE Team != null 這類條件，解析器會記錄 Kind = LiteralKind.Null。
• 字串列中，則使用 StringLiteral<StringNull> 這類型。
• 由於 StringNull.Length = -1，因此 Value 返回 new ValueString(null)。

這就使得 null 和 "" 在型別層次與執行時都可以明確地區分。

3.3 文字常數工廠

這些文字型別由 LiteralTypeFactory 一次性生成。

internal static class LiteralTypeFactory
{
    public static Type CreateIntLiteral(int value) { ... }
    public static Type CreateFloatLiteral(float value) { ... }
    public static Type CreateBoolLiteral(bool value) { ... }
    public static Type CreateStringLiteral(string? value) { ... }
}

SQL 編譯器會根據：

• 執行時列的型別（int、float、bool、ValueString 等）
• 文字常數的類型（整數、浮點數、布林值、字串、null）

從這裡獲得相應的 ILiteral<T> 型別。

最終結果是 WHERE 子句中出現的所有文字常數，都成為「將常數嵌入型別參數的 ILiteral<T> 型別」。

4. 建構管道型別

到目前為止，以下內容已經收集完成。

• 解析完成的查詢（SELECT 和 WHERE 的結構）
• 從列名到 IColumn<TRow, TValue> 實作的映射
• 文字常數表示的 ILiteral<T> 型別

編譯器的工作是利用這些資料來生成以下三種。

• 管道本體 TPipeline（實現 IQueryNode<TRow, TRuntimeResult, TRoot> 的關閉泛型型別）
• 執行時結果型別 TRuntimeResult
• 公開結果型別 TPublicResult

4.1 SELECT 的處理

首先是 SELECT。

SELECT *

對於最簡單的 SELECT * FROM $，

• 執行時結果型別與公開結果型別都為 TRow
• 管道尾部為 Stop<TRow, TRow>

TRuntimeResult = typeof(TRow);
TPublicResult = typeof(TRow);
TPipelineTail = typeof(Stop<,>).MakeGenericType(TRuntimeResult, typeof(TRow));

SELECT col / SELECT col1, col2, ...

當存在投影（選擇列）時，步驟會稍微增多。

• SELECT col 的情況

  • 從列名解析 ColumnMetadata
  • 確定執行時的值型別
  • 若非 string 則直接使用
  • 若是 string 則轉換為 ValueString
  • 構建 ColumnProjection<TRuntimeColumn, TRow, TRuntimeValue>

• SELECT col1, col2, ... 的情況

  • 解決每列
  • 實行時使用 ValueTuple<...>（內容可能是 ValueString）
  • 公開類型則使用用戶指定的 ValueTuple<...>（內容可為 string）

最終在所有情況下，Select 節點將在 Stop 之前插入。

Select<TRow, TProjection, Stop<...>, TMiddle, TRuntimeResult, TRoot> → Stop<...>

這個節點負責將 Project 的結果傳遞給 Stop.Process。

4.2 WHERE 的處理

WHERE 子句會基於語法樹遞迴地構建過濾型別。

邏輯運算子（AND / OR / NOT）

將 WhereExpression 的樹狀結構映射到相應的過濾型別。

• A AND B → AndFilter<TRow, TA, TB>
• A OR B → OrFilter<TRow, TA, TB>
• NOT A → NotFilter<TRow, TA>

Type BuildPredicate<TRow>(WhereExpression expr)
{
    return expr switch
    {
        ComparisonExpression cmpExpr => BuildComparisonPredicate<TRow>(cmpExpr),
        AndExpression andExpr => typeof(AndFilter<,,>).MakeGenericType(
            typeof(TRow),
            BuildPredicate<TRow>(andExpr.Left),
            BuildPredicate<TRow>(andExpr.Right)),
        OrExpression orExpr => typeof(OrFilter<,,>).MakeGenericType(
            typeof(TRow),
            BuildPredicate<TRow>(orExpr.Left),
            BuildPredicate<TRow>(orExpr.Right)),
        NotExpression notExpr => typeof(NotFilter<,>).MakeGenericType(
            typeof(TRow),
            BuildPredicate<TRow>(notExpr.Expression)),
        _ => throw ...
    };
}

比較運算子（=、!=、> 等）

葉節點則為「列與常數的比較」。

City = 'Seattle'
Salary >= 180000
Team != null

最終形成以下型別（例如：對於字串列的 City = 'Seattle'）。

• 執行時的列型別為 ValueStringColumn<PersonCityColumn, Person>
• 執行時的值型別為 ValueString
• 文字常數型別為 StringLiteral<SomeStringNode<…>>

因此，最終組成：

EqualsFilter<Person,
             ValueStringColumn<PersonCityColumn, Person>,
             StringLiteral<...>,
             ValueString>

編譯器將這附加至 Where<TRow, TPredicate, TNext, TRuntimeResult, TRoot> 節點，並將其納入管道中。

4.3 將 Where 和 Select「融合」為一個步驟

目前為止組建的管道在正確性上沒有問題，但略顯優化空間。

典型查詢大致如下形式。

SELECT Name FROM $ WHERE City = 'Seattle'

如果直接組裝起來的話，

Where<...> → Select<...> → Stop<...>

這樣的兩階段結構可以進行合併。

TypedSql 擁有小型的優化器，當發現以下模式時：

Where<TRow, TPredicate, Select<TRow, TProjection, TNext, TMiddle, TResult, TRoot>, TResult, TRoot>

將其替換為：

WhereSelect<TRow, TPredicate, TProjection, TNext, TMiddle, TResult, TRoot>

WhereSelect 節點的工作是，於同一迴圈中：

• 首先透過 TPredicate.Evaluate 進行過濾
• 僅對通過的行進行 TProjection.Project 投影
• 將結果傳遞給下一個節點

最終，對於 SELECT Name FROM $ WHERE City = 'Seattle' 的查詢，將轉化為：

WhereSelect<...> → Stop<...>

這是一個 單次迴圈的處理。

此外，這個優化器能夠識別更複雜的嵌套結構，力求將 Where 和 Select 儘可能融合。在這裡所做的並不是複雜的優化算法，而是「將現有的泛型型別參數拆解，並重組為新融合節點的型別參數」，所以實現實際上相當簡單。

5. 將執行結果轉換為「外部型別」

管道內部使用的型別，與用戶想要的型別不一定相同。

例如，

• 內部型別為 ValueString
• 但用戶希望返回 string

這樣的差距由 QueryProgram<TRow, ...> 來彌補。

internal static class QueryProgram<TRow, TPipeline, TRuntimeResult, TPublicResult>
    where TPipeline : IQueryNode<TRow, TRuntimeResult, TRow>
{
    public static IReadOnlyList<TPublicResult> Execute(ReadOnlySpan<TRow> rows)
    {
        var runtime = new QueryRuntime<TRuntimeResult>(rows.Length);
        TPipeline.Run(rows, ref runtime);

        return ConvertResult(ref runtime);
    }

    private static IReadOnlyList<TPublicResult> ConvertResult(ref QueryRuntime<TRuntimeResult> runtime)
    {
        if (typeof(IReadOnlyList<TRuntimeResult>) == typeof(IReadOnlyList<TPublicResult>))
        {
            return (IReadOnlyList<TPublicResult>)(object)runtime.Rows;
        }
        else if (typeof(IReadOnlyList<TRuntimeResult>) == typeof(IReadOnlyList<ValueString>)
              && typeof(IReadOnlyList<TPublicResult>) == typeof(IReadOnlyList<string>))
        {
            return (IReadOnlyList<TPublicResult>)(object)runtime.AsStringRows();
        }
        else if (RuntimeFeature.IsDynamicCodeSupported
              && typeof(TRuntimeResult).IsGenericType
              && typeof(TPublicResult).IsGenericType)
        {
            return runtime.AsValueTupleRows<TPublicResult>();
        }

        throw new InvalidOperationException($"無法將查詢結果從 '{typeof(TRuntimeResult)}' 轉換為 '{typeof(TPublicResult)}'。");
    }
}

大致分為三種情況：

1. 執行時結果型別與公開型別相同
   → 直接返回 Rows。

2. 執行時型別為 ValueString，公開型別為 string
   → 透過 AsStringRows 包裝，將 ValueString[] 隱式轉換為 string? 並返回。

3. 兩者均為 ValueTuple，形狀相符
   → 通過 AsValueTupleRows<TPublicResult>() 將值元組間複製過去。

5.1 ValueTupleConvertHelper：動態 IL 進行欄位拷貝

ValueTupleConvertHelper<TPublicResult, TRuntimeResult> 的工作是：

• 從執行時的值元組拷貝到公開用值元組
• 必要時進行 string 與 ValueString 的相互轉換
• 遞迴處理嵌套的 Rest 欄位

原文出處：https://qiita.com/hez2010/items/2936d7441c61df5a628a