Wie groß ist meine TypeScript-Union?

Veröffentlicht am 29. September 2020

Achtung: dieser Beitrag ist alt! Es kann gut sein, dass seine Inhalte nicht mehr aktuell sind.

Im Rahmen meiner TypeScript-Hackerei hatte ich schon mehrfach den Wunsch nach einem Hilf-Typ, mit dem sich ermitteln lässt, wie viele Elemente in einem gegebenen Union-Typ stecken. Alles, was sich hierzu ergooglen lässt, ist entweder auf Unions bestimmter Größen limitiert oder Bestandteil irgendwelcher komplizierten Typ-Libraries. Ich wollte aber eine saubere und von mir selbst zu 100% verstandene Standalone-Lösung haben, also beschloss ich Freitag letzter Woche, dem Thema ein für allemal auf den Grund zu gehen. Da ich nur eine extrem vage Idee davon hatte, wie sich dieses Problem lösen lassen könnte, bediente ich mich des zielgerichteten explorativen Programmierens, das ich meist im Rückwärtsgang betreibe.

Exploratives Programmierens im Rückwärtsgang (also bei bekanntem Ziel aber unbekannten Mitteln und Wegen) beginnt für mich immer mit DDD: Dreamcode-Driven Development. Ich schreibe also erst mal ein bisschen Code, der das benutzt, was ich eigentlich überhaupt erst bauen möchte. Mein Dreamcode für SizeOfUnion<T> sieht wie folgt aus:

type Result = SizeOfUnion<23 | 42 | 1337>
// Result ist 3

So weit, so logisch: in der Union befinden sich drei Typen, also ist das Ergebnis der Literal Number Type 3. Nur wie kommen wir an die 3 heran? Am einfachsten geht das über ein Tuple, denn diese haben durch ihre feste Anzahl an Einträgen nicht nur ein length-Feld mit einer readonly number, sondern tatsächlich einen Readonly Literal Type:

type One = [number]["length"]; // One === 1
type Two = [number, string]["length"]; // Two === 2
// Und so weiter

So gesehen ist also die Implementierung von SizeOfUnion<T> ganz einfach: wir brauchen nur einen Hilfs-Typ, der aus einer Union mit N Bestandteilen ein Tuple der Größe N macht, und N fragen wir am Ende ab:

type SizeOfUnion <T> = UnionToTuple<T>["length"];

type Result = SizeOfUnion<23 | 42 | 1337>
// Result ist 3

Jetzt fehlt „nur“ noch UnionToTuple<T> und schon haben wir unser Ziel erreicht. Allerdings ist gerade dieser Schritt nicht ganz so einfach. Wir müssen uns zunächst ein paar Fakten zu Funktionssignaturen vergegegenwärtigen, auch wenn diese zunächst nichts mit unserem Problem zu tun haben scheinen.

Fangen wir mit einer scheinbar trivialen Quizfrage an: wie könnten wir den Typ der folgenden Funktion in TypeScript-Typ-Syntax aufschreiben?

function f (x: number): number;
function f (x: string): string;
function f (x: any): any { return x; };

Da die Funktion f überladen ist, gibt es gleich zwei richtige Antworten:

// Überladungs-Signatur
type F1 = {
    (x: number): number;
    (x: string): string;
};

// Intersection Type
type F2 = ((x: number) => number) & ((x: string) => string);

const f: F1 = (x: any) => x;
const a = f(1);    // Ok, a ist number
const b = f("a");  // Ok, b ist string
const c = f(true); // Fehler

const g: F2 = (x: any) => x;
const x = g(1);    // Ok, x ist number
const y = g("a");  // Ok, y ist string
const z = g(true); // Fehler

Anders formuliert: Das Überladen einer Funktion definiert die Funktionssignatur als aus den einzelnen Funktionssignaturen zusammengesetzten Intersection Type! Daraus ergibt sich natürlich sofort die nächste Frage: wie lässt sich der Parameter-Typ einer solchen Funktionssignatur beschreiben? TypeScripts Antwort sieht wie folgt aus:

type Test = ((x: 23) => void) & ((x: 42) => void);
type Params = Parameters<Test> // [42]

Gar keine Spur von der 23? Warum ist das denn so? Der in TS standardmäßig verbaute Typ-Helfer Parameters<T> ist ein recht simpler Conditional Type …

type Parameters<T extends (...args: any) => any> =
  T extends (...args: infer P) => any
    ? P
    : never;

… und zum Gebrauch von infer bei überladenen Funktionen lässt uns das TypeScript-Handbuch wissen:

When inferring from a type with multiple call signatures (such as the type of an overloaded function), inferences are made from the last signature (which, presumably, is the most permissive catch-all case).

Das liest sich auf den ersten Blick wie eine Limitierung, ist aber eigentlich ein ganz großartiges Feature: Wir können mittels infer immer etwas aus der letzten Funktionssignatur extrahieren. Und wann immer wir aus einer „Liste“ von Elementen (in diesem Fall den Einzelteilen eines Intersection Type) den letzten Eintrag greifen können, können wir diesen Eintrag verarbeiten und den Rest der Liste der gleichen Prozedur unterziehen –das Zauberwort heißt Rekursion! Einmal im Kopf durchgedacht könnte der Prozess wie folgt aussehen

Ausgehend von einer Union U = 23 | 42 …
…erzeugen wir (auf welchem Weg auch immer) eine überladene Funktionssignatur ((x: 23) => void) & ((x: 42) => void) …
…von der wir per Conditional Type F extends ((a: infer A) => void) für den Parameter A den Parameter-Typ aus der letzten Funktionssignatur (Literal Number Type 42) extrahieren …
… den wir per Exclude<U, A> aus U ausschließen, so dass nur 23 in der Union verbleibt …
…woraus wir die Funktionssignatur (x: 23) => void erzeugen …
…von der wir per Conditional Type F extends ((a: infer A) => void) für den Parameter A den Parameter-Typ aus der letzten und nun einzigen Funktionssignatur (Literal Number Type 23) extrahieren …
… den wir per Exclude<U, A> aus U ausschließen, so dass die resultierende Union leer ist …
…woraus sich keine weitere Funktionssignatur bauen lässt und wir jeden Wert der Eingangs-Union je einmal in der Hand hatten (um daraus z.B. ein Tuple zu konstruieren, auf welchem Weg auch immer).

Das sollte doch zu machen sein! Kümmern wir uns zunächst darum, aus einer Union einen Intersection Type zu basteln. Wie das genau geht, hat Podcast-Kollege Stefan Baumgartner erst vor kurzem ausführlich aufgeschrieben:

// https://fettblog.eu/typescript-union-to-intersection/
type UnionToIntersection <T> = 
  (T extends any ? (x: T) => any : never) extends 
  (x: infer R) => any ? R : never;

Wie genau diese Hexerei funktioniert hat Stefan so umfassend erklärt, dass es an dieser Stelle keiner weiteren Worte bedarf – wir füttern in sein Werk einfach Funktionssignaturen hinein um diese zu einer überladenen Signatur zu vereinigen:

type Test = UnionToIntersection<((a: 23) => void) | ((a: 42) => void)>
// Test === ((a: 23) => void) & ((a: 42) => void)
// genau was wir brauchen!

Hierfür müssen wir allerdings erst mal aus unserer normalen Union eine Union aus Funktionssignaturen basteln, bei je ein Typ aus der Ausgangs-Union den ersten Parameter in einem Typ in der Endprodukt-Union stellt. Einfach UnionToIntersection<(a: Union) => void> funktioniert nicht, denn hier erhält UnionToIntersection<T> für T nur eine Union der Größe 1, worin sich ein Funktionstyp befindet, der unserer eigentlichen Union Parameter erwartet. Wir kommen nicht umhin, unsere Union einmal durch einen scheinbar nutzlosen Conditional Type zu schleifen:

type UnionToIntersection<T> =
    (T extends any ? (x: T) => any : never) extends
    (x: infer R) => any ? R : never

type UnionToFunction<U> = UnionToIntersection<
    U extends any ? (f: U) => void : never>;

type Test = UnionToFunction<23 | 42>;
// Test === ((f: 23) => void) & ((f: 42) => void)
// genau was wir brauchen!

Die Schlüsselzeile ist U extends any ? (f: U) => void : never. Indem wir die Union U durch ein Conditional schleifen (auch wenn es mit der Bedingung extends any nichts ausschließt), wird jeder Typ in der Union einzeln verarbeitet – das Stichwort lautet Distributive Conditional Types. Ausgehend von unserer Union 23 | 42 wird also zunächst 23 für sich allein an der Bedingung extends any geprüft und, da 23 diese natürlich erfüllt, in einer Funktion verpackt. Danach passiert das Gleiche mit 42 und die beiden Funktionen bilden die Endprodukt-Union, die von UnionToIntersection<T> in eine Intersection verwandelt werden.

Kurzes Zwischenfazit: aus einer beliebigen Union machen wir eine Union aus Funktionstypen, bei der für jedes Element in der Ausgangs-Union ein Funktions-Typ in der Funktions-Union existiert, der das Element aus der Ausgangs-Union als Parameter erwartet. Diese Union aus Funktionstypen schweißen wir zu einem Intersection Type zusammen, der dem Typ einer überladenen Funktion entspricht. Und diesem rücken wir nun rekursiv zu Leibe, um endlich aus einer Union ein Tuple zu konstruieren! Im Prinzip ist dieser letzte Schritt ganz einfach:

type UnionToTuple<U> = UnionToFunction<U> extends ((a: infer A) => void)
    ? [...UnionToTuple<Exclude<U, A>>, A]
    : [];

Dieser Typ funktioniert ganz wie besprochen:

Aus der Input-Union U mit N Elementen wird ein Intersection Type aus N Funktionssignaturen konstruiert …
…woraus wir mittels infer den Parameter-Typ A des letzten Elements in der Intersection herauspicken …
…woraufhin wir A an die letzte Stelle des Output-Tuples setzen und den Rest des Tuples via Variadic Tuple Types mit UnionToTuple<Exclude<U, A>> auffüllen (d.h. UnionToTuple arbeitet mit N-1 Elementen).

Wenn die Union komplett durchgearbeitet wurde, liefert UnionToTuple<T> ein leeres Tuple und die Rekursion ist beendet.

Der einzige Haken an dieser Lösung ist, dass TypeScript 4.0 keine Rekursion in Conditional Types erlaubt, doch die kommende Version 4.1 hat bereits einen Patch für dieses Feature erhalten. Mit der aktuellen Vorab-Version von 4.1 funktioniert schon alles wie es soll:

type UnionToIntersection<T> =
    (T extends any ? (x: T) => any : never) extends
    (x: infer R) => any ? R : never;

type UnionToFunction<U> = UnionToIntersection<
    U extends any
        ? (f: U) => void
        : never>;

type UnionToTuple<U> =
    UnionToFunction<U> extends ((a: infer A) => void)
        ? [...UnionToTuple<Exclude<U, A>>, A]
        : [];

type SizeOfUnion <T> = UnionToTuple<T>["length"];

type Result = SizeOfUnion<23 | 42 | 1337>
// Result ist 3

Link zum TypeScript-Playground mit diesem Beispiel.

Der Vollständigkeit halber sei noch erwähnt, dass sich die Transformation, die die Kombination aus UnionToFunction<T> und UnionToIntersection<T> vollzieht, auch in einem Schritt abfrühstücken ließe:

type UnionToFunction<T> =
    (T extends any ? ((f: (a: T) => any) => any) : never) extends
    (a: infer R) => any ? R : never

Da das allerdings an die Grenzen der Verständlichkeit geht und UnionToIntersection<T> für sich genommen schon ein wertvolles Tool ist, würde ich das nicht so machen.

Jenseits von allem, das uns dieses Ergebnis über TypeScript lehrt, finde ich es auch ein schönes Beispiel für Dreamcode Driven Development. Wenn man ein Ziel, aber wirklich gar keine Ahnung hat, wie man es erreichen könnte, lohnt es sich fast immer, einfach mal vom Ziel aus rückwärts drauflos zu hacken – so lange, bis man auf etwas stößt, mit dem man sich auskennt und auf das man dann auch von der anderen Seite aus hinarbeiten kann. Nachdem ich kapiert hatte, dass infer mit überladenen Funktionstypen die Tür zur Rekursion öffnet und mich dabei obendrein dunkel an Stefans Artikel über Union-Intersection-Umwandlungen erinnerte, war mir recht klar wie sich mein Problem lösen lassen würde.

Wenn ich jetzt noch wüsste, wofür ich am Freitagmorgen das Problem eigentlich lösen wollte …