Unbounded memory consumption with recursive conditional types causes compilation OOM

[caomingpei]

Steps to reproduce

npx tsgo the following.ts file:

export type NumericProperty = "n1" | "n2" | "n3" | "n4" | "n5" | "n6" | "n7" | "n8" | "n9" | "n10" | "n11" | "n12" | "n13" | "n14" | "n15" | "n16" | "n17" | "n18" | "n19" | "n20" | "n21" | "n22" | "n23" | "n24" | "n25" | "n26" | "n27" | "n28" | "n29" | "n30" | "n31" | "n32" | "n33" | "n34" | "n35" | "n36" | "n37" | "n38" | "n39" | "n40" | "n41" | "n42" | "n43" | "n44" | "n45" | "n46" | "n47" | "n48" | "n49" | "n50" | "n51" | "n52" | "n53" | "n54" | "n55" | "n56" | "n57" | "n58" | "n59" | "n60" | "n61" | "n62" | "n63" | "n64" | "n65" | "n66" | "n67" | "n68" | "n69" | "n70" | "n71" | "n72" | "n73" | "n74" | "n75" | "n76" | "n77" | "n78" | "n79" | "n80" | "n81" | "n82" | "n83" | "n84" | "n85" | "n86" | "n87" | "n88" | "n89" | "n90" | "n91" | "n92" | "n93" | "n94" | "n95" | "n96" | "n97" | "n98" | "n99" | "n100";

export type StringProperty = "s1" | "s2" | "s3" | "s4" | "s5" | "s6" | "s7" | "s8" | "s9" | "s10" | "s11" | "s12" | "s13" | "s14" | "s15" | "s16" | "s17" | "s18" | "s19" | "s20" | "s21" | "s22" | "s23" | "s24" | "s25" | "s26" | "s27" | "s28" | "s29" | "s30" | "s31" | "s32" | "s33" | "s34" | "s35" | "s36" | "s37" | "s38" | "s39" | "s40" | "s41" | "s42" | "s43" | "s44" | "s45" | "s46" | "s47" | "s48" | "s49" | "s50" | "s51" | "s52" | "s53" | "s54" | "s55" | "s56" | "s57" | "s58" | "s59" | "s60" | "s61" | "s62" | "s63" | "s64" | "s65" | "s66" | "s67" | "s68" | "s69" | "s70" | "s71" | "s72" | "s73" | "s74" | "s75" | "s76" | "s77" | "s78" | "s79" | "s80" | "s81" | "s82" | "s83" | "s84" | "s85" | "s86" | "s87" | "s88" | "s89" | "s90" | "s91" | "s92" | "s93" | "s94" | "s95" | "s96" | "s97" | "s98" | "s99" | "s100";

type Seq = { _brand: "Seq" };

// `Branch` to connect Branch<A,B>
type Branch<L1 extends Seq, L2 extends Seq, R1 extends Seq, R2 extends Seq> = Seq & {
  type: "Branch";
  left1: L1;
  left2: L2;
  right1: R1;
  right2: R2;
};

// `A` and `B` are the basic elements of the sequence.
type A = Seq & { type: "A" };
type B = Seq & { type: "B" };
type C = Seq & { type: "C" };
type D = Seq & { type: "D" };

// Recursively rewrite the entire sequence tree.
type Rewrite<T extends Seq> = T extends A
  ? Branch<A, B, C, D>
  : T extends B
  ? Branch<B, C, D, A>
	: T extends C
	? Branch<C, D, A, B>
	: T extends D
	? Branch<D, A, B, C>
  : T extends Branch<infer L1 extends Seq, infer L2 extends Seq, infer R1 extends Seq, infer R2 extends Seq>
  ? Branch<Rewrite<L1>, Rewrite<L2>, Rewrite<R1>, Rewrite<R2>>
  : never;

// `Nat` and `Succ`/`Zero` are used for type-level counting.
// Represents numbers at the type level.
type Nat = { _brand: "nat" };
type Zero = Nat & { type: "Zero" };
type Succ<N extends Nat> = Nat & { type: "Succ"; pred: N };

// Apply rewrite rules N times using recursive conditional types
// TypeScript has recursion depth limits, so large N values will fail
type ApplyRewrite<S extends Seq, N extends Nat> = N extends Zero
  ? S // Base case: 0 iterations returns original
  : N extends Succ<infer P extends Nat> // Recursive case: N = Succ(P)
  ? ApplyRewrite<Rewrite<S>, P> // Apply one rewrite, then recurse with P
  : never;

// Define a more complex type union calculation
type SeqUnion<T extends Seq> = T extends A
  ? StringProperty
  : T extends B
  ? NumericProperty
	: T extends C
	? `${NumericProperty}${StringProperty}`
	: T extends D
	? `${StringProperty}${NumericProperty}`
  : T extends Branch<infer L1 extends Seq, infer L2 extends Seq, infer R1 extends Seq, infer R2 extends Seq> 
  ? `${SeqUnion<L1>}${SeqUnion<R1>}` | `${SeqUnion<L2>}${SeqUnion<R2>}`
  : never;

// trigger the compile-time evaluation.
type InitialState = A;

// Note: the following is harmful. Set iteration count to N=40.
// Complex binary tree
// Result: Compilation bomb! Compilation leads to OOM, takes a very long time, and causes a Denial of Service.
type N40 = Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<
          Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<
          Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<
          Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<
          Zero>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>;

// Generate final result type.
type FinalState = ApplyRewrite<InitialState, N40>;
type FinalUnion = SeqUnion<FinalState>;

const finalUnion = {} as FinalUnion;
console.log("Compilation succeeded! The final type is:", finalUnion);

Behavior with [email protected]

The compilation fails gracefully with a standard Out of Memory (OOM) error. The Node.js runtime (V8 engine) enforces a default heap memory limit (typically ~4GB on 64-bit systems), which prevents the process from consuming all available system resources.

Result: The process terminates immediately, leaving the host operating system responsive.

Ref: https://v8.dev/blog/4gb-wasm-memory https://stackoverflow.com/questions/79250132/how-does-node-v8-determine-its-max-heap-size

Behavior with tsgo

The compiler exhibits unbounded memory consumption. Unlike the Node.js runtime, tsgo lacks a default heap ceiling. It continues to allocate memory until it exhausts both physical RAM and swap space.

Result: The host system hangs or freezes, rendering it unresponsive until the operating system's kernel OOM Killer forcibly terminates the process.

My Point

Suggest evaluating mitigation strategies for this unbounded memory usage. If tsgo is intended for broader use (other than web), the current behavior risks stability. If tsgo targets only web, adopting a V8-like memory limit is an acceptable solution. This choice warrants careful consideration.