TypeScriptにおける配列の共変性

2022/12/15

はんぺんのフリー画像

本記事はRecruit Engineers Advent Calendar 2022の15日目です.

typescript@4.9.4strict: trueです.

突然ですが

ここにAnimal型とDog型があります

type Animal = {
  animal: string;
};

type Dog = {
  animal: string;
  dog: string;
};

それぞれ,次のような値を持ちます.

const animal: Animal = {
  animal: "string",
};

const dog: Dog = {
  animal: "string",
  dog: "string",
};

いま,Dog <: Animalです.

<:という記号は2つの型のあいだに書いて,「左の型が右の型のサブタイプである」と読みます.

TypeScriptの型システムは構造的なので,2つのオブジェクトがサブタイプ関係にあるには,それらに共通するプロパティについてもまた,サブタイプ関係が必要1です

今回の例では,DogAnimalに共通するanimalプロパティについてstring <: stringなのでOKです.

TSでは,S <: TならばT型の変数にS型の値を代入できます.

つまり,Dog <: Animalなので Animal型の変数にDog型の値を代入できます.

// できる
const animalVariable: Animal = dog;

問題

それでは,Animal[]型の変数にDog[]型の値を代入できるでしょうか?

const dogArray: Dog[] = [dog];

// これはできる?
const animalArray: Animal[] = dogArray;

―――――――――

――――――

―――

animalArrayにdogArrayを代入してもエラーが表示されていない様子のスクリーンショット

答え:できます

(配列に共変性がある)

―――

――――――

―――――――――

……できて良いんだっけ…?

いっしょに考えてみましょう.

Animal[]型の変数にDog[]型の値を代入するためには,Dog[] <: Animal[]が必要です.

したがって,先ほどと同じように2つの配列に共通するすべてのプロパティについてもまた,サブタイプ関係が必要です.

配列の型はlib.es5.d.tsによって,以下のように定義されています.

interface Array<T> {
  /**
   * Gets or sets the length of the array. This is a number one higher than the highest index in the array.
   */
  length: number;
  /**
   * Returns a string representation of an array.
   */
  toString(): string;
  /**
   * Returns a string representation of an array. The elements are converted to string using their toLocaleString methods.
   */
  toLocaleString(): string;
  // ...
}

出典: lib.es5.d.ts,TypeScript

つまり,lengthtoStringtoLocalString……すべてについてサブタイプ関係が必要です.

ここでは特にindexOfプロパティに着目してみましょう.

  /**
   * Returns the index of the first occurrence of a value in an array, or -1 if it is not present.
   * @param searchElement The value to locate in the array.
   * @param fromIndex The array index at which to begin the search. If fromIndex is omitted, the search starts at index 0.
   */
  indexOf(searchElement: T, fromIndex?: number): number;

出典: lib.es5.d.ts,TypeScript

ここで,

(searchElement: Dog, fromIndex?: number): number

<:

(searchElement: Animal, fromIndex?: number): number

が必要なのですが,これは一般的には 成り立ちません

Animalの入力を期待する関数Dogの入力を期待する関数 で置き換えられないからです(反変性)

以上を踏まえると,次のような意地悪ができます

const dogArray: Dog[] = [dog];

// dogArrayのindexOfを独自の関数に置き換える
dogArray.indexOf = (dog: Dog) => {
  // Dog型の値を受け取り,Animal型にはないプロパティをわざと触る
  dog.dog.charAt(0);
  // 適当に返す
  return -1;
};
// 以上の置き換え自体は問題ない
// dogArray.indexOfでDogの入力を期待することは正当

// 問題はこの行.dogArrayをanimalArrayに代入できるなら……
const animalArray: Animal[] = dogArray;

// そのあと例のindexOfにanimalを渡せてしまう
animalArray.indexOf(animal);

このコードはtscによる型検査をパスします

$ npx tsc
$ # パス

しかし,ランタイムで落ちます

$ node index.js
/home/sititou70/ts-array-variant/index.js:11
    dog.dog.charAt(0);
            ^

TypeError: Cannot read properties of undefined (reading 'charAt')
    at dogArray.indexOf (/home/sititou70/ts-array-variant/index.js:11:13)
    at Object.<anonymous> (/home/sititou70/ts-array-variant/index.js:15:13)
    at Module._compile (node:internal/modules/cjs/loader:1159:14)
    at Module._extensions..js (node:internal/modules/cjs/loader:1213:10)
    at Module.load (node:internal/modules/cjs/loader:1037:32)
    at Module._load (node:internal/modules/cjs/loader:878:12)
    at Function.executeUserEntryPoint [as runMain] (node:internal/modules/run_main:81:12)
    at node:internal/main/run_main_module:23:47

このような挙動は,TypeScriptが型安全(健全)でないと言われる理由の1つです.

しかし,これはわざとこのような設計になっています.TypeScript Design Goalsによれば,

Non-goals

  1. 健全な、あるいは「証明できるほど正しい」型システムを適用する。その代わり、正しさと生産性のバランスをとること。

出典: TypeScript Design Goals,翻訳はDeepLによる

とあります.この気持ちはよくわかります.

配列の共変性はどう実現されているか

配列が共変扱いなのはわかりました.では,それはTS自身の型システム内でどのように実現されているのでしょうか?

メソッド記法の使用

まず,メソッド記法が一役買っています.

説明の簡単のために,indexOfしかプロパティを持たないMyArrayを作ってみます.

以下の,2種類のMyArrayをみてください

interface MyArray1<T> {
  indexOf(elem: T): number;
}

interface MyArray2<T> {
  indexOf: (elem: T) => number;
}

一方はメソッド記法,他方は関数型の記法で書かれています.書き方は少し違いますが,どちらも同じようなことを書いていますね.

しかし,以下のように挙動が大きく異なります.

// これはできる
const myDogArray1: MyArray1<Dog> = [dog];
const myAnimalArray1: MyArray1<Animal> = myDogArray1;

// これは型エラー
const myDogArray2: MyArray2<Dog> = [dog];
const myAnimalArray2: MyArray2<Animal> = myDogArray2;
//    ^^^^^^^^^^^^^^
// 型 'MyArray2<Dog>' を型 'MyArray2<Animal>' に割り当てることはできません。
//   プロパティ 'dog' は型 'Animal' にありませんが、型 'Dog' では必須です。ts(2322)

このように,メソッド記法では,関数型の記法に比べて引数の扱いがゆるくなります2

(恥ずかしながら,私はこの挙動を半年くらい前まで知りませんでした.そして知った当時はだいぶ驚きました)

さて,思い返してみると,ライブラリの型定義は(配列に限らず)ほとんどメソッド記法で書かれていました.

interface Array<T> {
  /**
   * Gets or sets the length of the array. This is a number one higher than the highest index in the array.
   */
  length: number;
  /**
   * Returns a string representation of an array.
   */
  toString(): string;
  /**
   * Returns a string representation of an array. The elements are converted to string using their toLocaleString methods.
   */
  toLocaleString(): string;
  // ...
}

出典: lib.es5.d.ts,TypeScript

したがって,これらの引数はゆるめに扱われており,配列の共変性にも効果があるというわけです.

配列専用の型付け規則

メソッド記法と変性の関係についてわかったところで,さっそくlib.es5.d.tsを次のように改造してみましょう.

  /**
   * Returns the index of the first occurrence of a value in an array, or -1 if it is not present.
   * @param searchElement The value to locate in the array.
   * @param fromIndex The array index at which to begin the search. If fromIndex is omitted, the search starts at index 0.
   */
-  indexOf(searchElement: T, fromIndex?: number): number;
+  indexOf: (searchElement: T, fromIndex?: number) => number;

これにより,問題のコードは型検査で失敗するようになるはずです.

しかし,

$ npx tsc
$ # パス???

予想に反してパスしてしまいました.これが今回気づいたことです.

原因を確かめるために,TypeScriptのコードを読んでみることにしました.これは初めてのことなので不安もありますが,がんばります.

さて,型検査器のコードはmicrosoft/TypeScriptsrc/compiler/checker.tsにあります.こちらのファイルは,現時点で47,206行(!?)あり,2.6MBもの容量があり,GitHubは表示を拒否します.

checker.tsファイルのプレビューをGitHubが拒否しているスクリーンショット

あくまで念のために繰り返しますが,これは1つの.tsファイルです.

さっそく不安が的中していますが,覚悟 を決めて読んでいきます.

tscコマンドのエントリーポイントからconsole.logconsole.traceを仕込みつつ追っていくと,やがてchecker.tscheckTypeRelatedToという関数にたどり着きました.

/**
 * Checks if 'source' is related to 'target' (e.g.: is a assignable to).
 * @param source The left-hand-side of the relation.
 * @param target The right-hand-side of the relation.
 * @param relation The relation considered. One of 'identityRelation', 'subtypeRelation', 'assignableRelation', or 'comparableRelation'.
 * Used as both to determine which checks are performed and as a cache of previously computed results.
 * @param errorNode The suggested node upon which all errors will be reported, if defined. This may or may not be the actual node used.
 * @param headMessage If the error chain should be prepended by a head message, then headMessage will be used.
 * @param containingMessageChain A chain of errors to prepend any new errors found.
 * @param errorOutputContainer Return the diagnostic. Do not log if 'skipLogging' is truthy.
 */
function checkTypeRelatedTo(
  source: Type,
  target: Type,
  relation: Map<string, RelationComparisonResult>,
  errorNode: Node | undefined,
  headMessage?: DiagnosticMessage,
  containingMessageChain?: () => DiagnosticMessageChain | undefined,
  errorOutputContainer?: { errors?: Diagnostic[]; skipLogging?: boolean }
): boolean {

出典: checker.ts,TypeScript

コイツは,2つの型の関係性をテストするための関数みたいです.今回の例だとDog[]Animal[]assignableRelationにあるかどうかを検査するために呼ばれていました.

ところで,relationが取りうる値としてsubtypeRelationとassignableRelationという2つがありますが,これらは何が違うのでしょうか?

ここまで,サブタイプ関係と代入可能を同じような概念として暗黙的に扱ってきました.しかし,型検査器内ではこれらは区別されているということで,何が違うのか気になりますね.

まぁ結論から言うとコードが長すぎてよくわからなかったのですが(すみません),サッと眺めた感じだとassignableRelationの方がsubtypeRelationに比べてゆるい関係に見えました.基本的には両者に共通の処理が大半を占めつつも,例えば以下のようなコードがあり

if (relation === assignableRelation || relation === comparableRelation) {
  // ...
  // Type number is assignable to any computed numeric enum type or any numeric enum literal type, and
  // a numeric literal type is assignable any computed numeric enum type or any numeric enum literal type
  // with a matching value. These rules exist such that enums can be used for bit-flag purposes.
  if (
    s & TypeFlags.Number &&
    (t & TypeFlags.Enum ||
      (t & TypeFlags.NumberLiteral && t & TypeFlags.EnumLiteral))
  )
    return true;
}

出典: checker.ts,TypeScript

コメントには「number型は,enum型やenumリテラル型に代入可能.enumをフラグのように利用するケースがあるため」とあります.まさにその直後のTypeFlagsはenumで,フラグのように使用されていますね.

サンプルコードでも確認してみます.

enum Flag {
  A = 1,
  B = 2,
}

// numberがenumリテラル型に代入できる
const flag: Flag.A = 123;

おー,代入できます.

このケースはrelation === assignableRelationのif文の中にあるため,assignableRelationでは有効ですがsubtypeRelationでは無効です.

また,今回は見つけられませんでしたが,逆にsubtypeRelationでは有効だけどassignableRelationでは無効なケースもあるかもしれません. これは基本的になさそうです.代入可能関係はサブタイプ関係を拡張しているとドキュメントに記載がありました.

いずれにせよ,確かに123 <: Flag.Aは通常のサブタイプ関係では変な感じがしますから,新たに代入専用の関係を定義したほうが良かったのだろうなと解釈しました.

さて,checkTypeRelatedToに入ってからはとても複雑な条件分岐や関数呼び出しが待ち構えているのですが,今回の場合は最終的にstructuredTypeRelatedToWorker関数の以下の部分に入ります.

// ダンプから始まるコメントはconsole.logで実際の値を確かめた結果です.

// ただし今回のケースに関係のない部分を一部省略しています
// ダンプ:source === Array<Dog>
// ダンプ:target === Array<Animal>
if (
  getObjectFlags(source) & ObjectFlags.Reference &&
  getObjectFlags(target) & ObjectFlags.Reference &&
  (source as TypeReference).target === (target as TypeReference).target &&
  !isTupleType(source) &&
  !(isMarkerType(source) || isMarkerType(target))
) {
  // We have type references to the same generic type, and the type references are not marker
  // type references (which are intended by be compared structurally). Obtain the variance
  // information for the type parameters and relate the type arguments accordingly.
  // 訳すと:
  //   同じジェネリクス型に対する2つの型があり,(Array<Dog>とArray<Animal>,今回はどちらもArrayに対する型)
  //   それらはマーカータイプではなく(? わからん)
  //   構造的に比較されることを意図しています
  //   型パラメタの引数に対する変性の情報を計算し(たぶんArray<T>のTの変性を計算するということ)
  //   それによって型引数を関連付けます(なるほど?)

  // getVariancesが,さっき言っていた「Array<T>のTの変性を計算する」やつと思われる
  // ダンプ:(source as TypeReference).target === Array
  const variances = getVariances((source as TypeReference).target);
  // ダンプ:variances === [VarianceFlags.Covariant]
  // これはおそらくArrayの1つ目の型パラメタTが共変であることを表している

  // relateVariancesは,[Dog]と[Animal]の関係を[VarianceFlags.Covariant]で検査すると思われる
  // したがって結局Dog <: Animalが検査される(共変)
  const varianceResult = relateVariances(
    getTypeArguments(source as TypeReference), // ダンプ:getTypeArguments(sourge) === [Dog]
    getTypeArguments(target as TypeReference), // ダンプ:getTypeArguments(target) === [Animal]
    variances, // [VarianceFlags.Covariant]
    intersectionState // なぞ.たぶん今回関係なし
  );
  if (varianceResult !== undefined) {
    return varianceResult;
  }
}

出典: checker.ts,TypeScript,補足のコメントは筆者による

というわけで,getVariances[VarianceFlags.Covariant]を返す理由が気になります.さっそく定義を見てみると……

function getVariances(type: GenericType): VarianceFlags[] {
  // Arrays and tuples are known to be covariant, no need to spend time computing this.
  return type === globalArrayType ||
    type === globalReadonlyArrayType ||
    type.objectFlags & ObjectFlags.Tuple
    ? arrayVariances
    : getVariancesWorker(type.symbol, type.typeParameters);
}

// ここでarrayVariancesは
const arrayVariances = [VarianceFlags.Covariant];

出典: checker.ts,TypeScript,補足のコメントは筆者による

あーやってる.これはやってますわ.

コメントには「配列やタプルは共変なので変性を計算する必要はない」とあります.先程のダンプでtypeArrayなのは確認済みです.

typeArrayの場合,[VarianceFlags.Covariant]という固定値が返されます.パフォーマンスを意図しての処理とも読めますが,実質的には配列を共変とする型付け規則の実装でもあります.

それ以外の場合はgetVariancesWorkerという関数を呼び出して変性を計算しているようです.

というわけで,node_modules/typescript/lib/tsc.jsを以下のように変更します

function getVariances(type) {
- return type === globalArrayType || type === globalReadonlyArrayType || type.objectFlags & 8 ?
+ return false ?
    arrayVariances :
    getVariancesWorker(type.symbol, type.typeParameters);
}

「配列だろうが頑張って変性を計算しなさい!」と叱っておきました.これで再度型検査してみると……

$ npx tsc
index.ts:20:7 - error TS2322: Type 'Dog[]' is not assignable to type 'Animal[]'.
  Types of property 'indexOf' are incompatible.
    Type '(searchElement: Dog, fromIndex?: number | undefined) => number' is not assignable to type '(searchElement: Animal, fromIndex?: number | undefined) => number'.
      Types of parameters 'searchElement' and 'searchElement' are incompatible.
        Type 'Animal' is not assignable to type 'Dog'.

20 const animalArray: Animal[] = dogArray;
         ~~~~~~~~~~~


Found 1 error in index.ts:20

予想通りちゃんと落ちました!

おまけ:Flowでは

配列は共変ではありません.

今回のようなコードはデフォルトでエラーになります.

// @flow

type Animal = // ...省略...
type Dog = // ...省略...

const animal = // ...省略...
const dog = // ...省略...

const dogArray: Dog[] = [dog];
const animalArray: Animal[] = dogArray;
$ npx flow --version
Flow, a static type checker for JavaScript, version 0.195.1
$ npx flow check
Error ┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈ index.js:22:31

Cannot assign dogArray to animalArray because property dog is missing in Animal [1] but exists in Dog [2] in array
element. [prop-missing]

     19};
     20[2] 21│ const dogArray: Dog[] = [dog];
 [1] 22│ const animalArray: Animal[] = dogArray;
     23│



Found 1 error

おまけ2:Javaでは

配列は共変です

以下のコードは型検査に成功しますが実行時に失敗します3

class Animal {}
class Dog extends Animal {}

class Main {
  public static void main(String[] args) {
    Animal animalArray[] = new Dog[1];
    animalArray[0] = new Animal();
  }
}
$ java --version
openjdk 17.0.5 2022-10-18
OpenJDK Runtime Environment Temurin-17.0.5+8 (build 17.0.5+8)
OpenJDK 64-Bit Server VM Temurin-17.0.5+8 (build 17.0.5+8, mixed mode, sharing)
$ javac main.java
$ # 型検査をパスするが
$ java Main
Exception in thread "main" java.lang.ArrayStoreException: Animal
        at Main.main(main.java:7)
$ # ランタイムエラーになる

なんでこうなっているのか?というのがTAPLに書いてありました.

元々この機能が導入されたのは、配列の一部分を複製するなどの一部の基本的な操作の型付けにおいて、パラメータ多相がないことを補うためであった。しかし現在、一般的には、これは言語設計の欠陥であると考えられている。

出典: 型システム入門 プログラミング言語と型の理論,p.155

はえー.

まとめ

TypeScriptの配列には共変性があります.これは,配列の型定義がメソッド記法で書かれていることと,配列専用の型付け規則によって実現されるようです.

今回,TypeScriptの型検査器を初めて読んでみました.VS Codeでchecker.tsを開いただけなのに,PCのファンが回りだし,メモリを700MB持っていかれました.ヤバいです.

TypeScriptでは,健全性をある程度犠牲にして利便性とのバランスを取っています.それに比べてFlowは,より健全性を重視しているように感じました.

TAPLによれば

型検査を考慮して設計されていない言語に型システムを組み込むのは困難な問題である。

出典: 型システム入門 プログラミング言語と型の理論,p.7

とあります.TypeScriptやFlowは,そもそも難しいことに挑戦してくれているんですね.後から型システムを導入しているわけですから,その方向性にバリエーションが生まれるのは,まぁあたりまえだよねという感じです.

あとどうでもいいのですが,「反変」ってなんて読むのが正しいんですかね? 私は過去「はんぺん」と読んでいたのですが,ある日知り合いから「おでんかよwww」とバカにされたのが悔しくて「はんへん」に矯正したという事情があります.だけどさっきWikipediaを見たら「はんぺん」って書いてあるじゃないですか.もう何がなんだか…….4

最後に,本記事はRecruit Engineers Advent Calendar 2022の15日目の記事でした.あまりぱっとしたネタが思いつかず,n番煎じみたいな記事になってしまいすみません.昨日は@Takepepeさんによる「Next.js の Zod 活用術」でした.明日は加納さんがなにかを書いてくれます.楽しみですね!

参考資料

フリー画像の出典


  1. TAPL p.143で言うところの深さ部分型付け,S-RcdDepth規則のことです.他にも幅部分型付けなどもあるので逆は成り立ちません.
  2. 正確には双変となり,共変または反変を許すといったかんじになるのだそうですが詳しい説明は割愛します.気になる方は「bivarianceHack」と検索してみてください.また,この挙動はstrictFunctionTypesオプションとはあまり関係ありません.今回の環境はstrict: trueであり,strictFunctionTypesも有効化されています.
  3. ちなみにこれは,TAPLにおける演習 15.5.3の解答でもあります.TAPLではこの演習は解答略とされているので,正確に著者が意図したものという保証はありませんが.
  4. TAPLに読み方は載っていませんでしたし,検索してもWikipedia以外の情報が出てこないので詰んでいます.もしご存知でしたら助けてください.

続けて読む…

よわよわエンジニアがTAPL(型システム入門)を読んだら

2022/05/02

TypeScriptの型で素数を求めたい

2021/01/19

TypeScriptで型レベルScheme

2024/01/02

TypeScriptにおける代入可能関係の推移性

2023/08/10

Idrisでふんわり眺める依存型

2022/07/04

TypeScriptの型で全加算器から浮動小数点数,そして√2

2021/06/07

書いた人

sititou70のアイコン画像
sititou70

都内の社会人エンジニア4年生。Web技術、3DCG、映像制作が好き。