# kdts

A TypeScript compiler with type-driven optimizations

kdts is an optimization-first TypeScript compiler. Instead of erasing types as early as possible, it uses them throughout the compilation to direct optimizations, achieving transformations that would not have been possible were the types not known.

In our codebase, this produces frontend output that is about 40% smaller than the best type-unaware alternative. kdts gets its best results when your code is fully and accurately typed.

#### **Install**

```shellscript
bun add -g @kimlikdao/kdts
```

Currently, kdts is Bun only. If you don't have Bun, install it using `npm i -g bun` (or see bun.com for other ways to install).

#### **Two modes**

To make gradual onboarding possible, kdts has two modes: `opt` and `fast`.

* The `fast` mode is a wrapper around `bun build`, providing the same set of command line parameters as `opt` mode. It is fast and works with any codebase. It doesn't check types and produces a larger output.
* The `opt` mode uses a special fork of Google Closure Compiler (gcc) as a backend. Currently, `opt` mode supports only a subset of TypeScript, and more features and fixes are being added actively. There are also intentional differences from `tsc` and even TypeScript itself: in kdts `class`es and `interface`s are nominal types whereas object types are structural; see [Types and declarations](/types-and-declarations#nominal-and-structural-types).

#### **Usage**

Compile any program with

```shellscript
kdts entry.ts --fast
```

This will crawl all transitive dependencies (up to the npm package boundary), compile them into a single es6 module and write it to `entry.out.js` (for other output file names `-o other.js`). By default, the npm packages are not bundled but left as es6 imports (corresponds to `--packages external` mode of common bundlers).

To compile a fully typed program in the `opt` mode, use

```shellscript
kdts entry.ts
```

Even though npm packages are not bundled, in the `opt` mode, kdts still needs to discover type declarations for the used packages for the compilation to succeed (by contrast, no type information is needed in `fast` mode)

To compile and then run a program, test or benchmark,

```shellscript
kdts run entry.ts # --fast mode available
kdts test some.test.ts # --fast mode available
kdts bench some.bench.ts # --fast mode available
```

For more info about the CLI, use `kdts --help`.

#### **Experimental status & other caveats**

kdts was built to compile our own codebase as efficiently as possible; and in particular our TypeScript library [kimlikdao-lib](https://github.com/KimlikDAO/lib). While we used it on our code for a while now, it has not been fuzzed on any test suites yet. The `fast` mode should work on virtually on any valid TypeScript, however the `opt` mode very likely doesn't support large parts of TypeScript and even some parts of JavaScript. While we keep adding missing pieces and improving kdts actively, some parts of TypeScript will likely be never supported. **kdts is not a drop-in replacement for tsc and being so is a non-goal.**

In `opt` mode, each npm package used in the program should export its own types that kdts is able to parse, or you need to provide declaration shims by creating a directory `@types/` in the working directory or by adding to [kdts/@types](https://github.com/KimlikDAO/kdts/tree/main/kdts/%40types). We currently have declaration shims for a very limited set of npm packages that we use; see [#contributing](#contributing "mention").

kdts is under active development, and implementation coverage does not yet match this document in every case, particularly for `opt` mode. When in doubt, check our library code at [kimlikdao-lib](https://github.com/KimlikDAO/lib) which is built and tested in kdts `opt` mode with the `--strict` flag. Every feature of kdts is used somewhere in [kimlikdao-lib](https://github.com/KimlikDAO/lib).

For a showcase of examples, see [showcase](https://github.com/KimlikDAO/kdts/tree/main/showcase). For a real library built using kdts opt mode, see [kimlikdao-lib](https://github.com/KimlikDAO/lib).

#### **Contributing**

Feel free to file issues, send PRs, add declaration shims at <https://github.com/KimlikDAO/kdts>.


# Annotations

In kdts, compiler directives are provided via `satisfies` expressions, or when it's more convenient, through the `@satisfies {}` jsdoc tags.

### Overridable

Constant variable declarations can be annotated as `Overridable`. For such variables, the default initializer can be overridden with values supplied from the command line:

{% code title="worker.ts" %}

```typescript
import { Overridable } from "@kimlikdao/kdts";

const Status = 404 satisfies Overridable;
const HostUrl = "https://example.com" satisfies Overridable;

export default () => Response.redirect(HostUrl, Status);
```

{% endcode %}

When compiled with `kdts worker.ts --override HostUrl="test.com" --override Status=405`, we get

{% code title="worker.out.js" %}

```javascript
export default()=>Response.redirect("test.com",405);
```

{% endcode %}

### Function classes

In kdts, to achieve better optimizations, functions can be annotated as belonging to certain function classes. For example:

```typescript
/** @satisfies {PureFn} */
const greet = (name: string) => `Hi, ${name}!`;
```

Here, `greet` is annotated as being `PureFn` , which promises to the compiler that the function has no side effects, does not depend on mutable external state (hence deterministic) and returns a fresh value (we will introduce this formally later; primitives are always fresh).

If the function depended on external mutable state but is side-effect free, we can use the weaker marker `SideEffectFreeFn`:

```typescript
/** @satisfies {SideEffectFreeFn} */
const rand = (a: number, b: number) => a + Math.random() * (b - a);
```

An `InlineFn` is inlined to each call site and the function body is compiled away completely:

```typescript
/** @satisfies {InlineFn} */
const ensureArray = <T>(x: T | T[]): T[] => Array.isArray(x) ? x : [x];
```

Now, each time `ensureArray(x)` is called, we will see the expression `Array.isArray(x) ? x : [x]` inlined, unless kdts can prove x to be an array or not an array from the declared or inferred types. In such cases, the function call is compiled to `x` or `[x]` .

#### FreshValue

Before we go over all function classes, let us define `FreshValue` first. A `FreshValue` is defined recursively as a primitive (such as `string`, `number`, `bigint` etc) or a fresh object containing `FreshValue` s. For instance the following are all `FreshValue`s

```typescript
"Abc",
{ name: "Abc", age: 1 },
new Uint8Array([1, 2, 3]),
Uint8Array.fromHex("abcd").buffer,
```

The following is not a `FreshValue`

```typescript
const person = { name: "Abc", age: 1 };
{ person }
```

since `person` is not a fresh object.

#### List of function classes

Here is the full list of function annotations `kdts` currently optimizes with:

<table><thead><tr><th width="244.0078125">Annotation</th><th>Meaning</th></tr></thead><tbody><tr><td><code>DeterministicFn</code></td><td>A function which doesn't read external mutable state</td></tr><tr><td><code>SideEffectFreeFn</code></td><td>A function which doesn't change its argument or any external state</td></tr><tr><td><code>MethodFn</code></td><td>A class method which can only change state reachable from `this`. Further, it cannot read external mutable state.</td></tr><tr><td><code>InPlaceFn</code></td><td>A function which mutates only state reachable from its arguments. Further, it cannot read external mutable state.</td></tr><tr><td><code>InPlaceRandFn</code></td><td>A function which mutates only state reachable from its arguments. It can read external mutable state.</td></tr><tr><td><code>PureAliasFn</code></td><td>A function which doesn't read external mutable state and is side-effect free.</td></tr><tr><td><code>PureFn</code></td><td>A <code>PureAliasFn</code> which also returns a <code>FreshValue</code></td></tr><tr><td><code>InlineFn</code></td><td>A function which will be inlined to each call site and the function body will be compiled away.</td></tr><tr><td><code>NoInlineFn</code></td><td>A function which cannot be inlined and calls to it must be preserved as-is.</td></tr><tr><td><code>InlineFriendlyFn</code></td><td>A function the compiler is encouraged to inline when profitable, but unlike <code>InlineFn</code> it is not required to inline every call site.</td></tr></tbody></table>

#### Examples

```typescript
/**
 * Partitions the array into chunks of size n, except for the last chunk which
 * can be smaller, but not empty.
 *
 * For n ≤ 0, returns []
 *
 * @satisfies {PureFn}
 */
const chunk = <T>(arr: T[], n: number): T[][] => {
  if (n <= 0) return [];
  const result: T[][] = [];
  for (let i = 0; i < arr.length; i += n)
    result.push(arr.slice(i, i + n));
  return result;
};

/**
 * Shuffles the array uniformly at random in place.
 * @satisfies {InPlaceRandFn}
 */
const shuffle = <T>(arr: T[]): T[] => {
  for (let i = arr.length - 1; i > 0; --i) {
    const j = (Math.random() * (i + 1)) | 0;
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
  return arr;
};

/** @satisfies {SideEffectFreeFn & NoInlineFn} */
const byId = (id: string): HTMLElement =>
  document.getElementById(id) as HTMLElement;
```

### LargeConstant

A constant variable declaration can be marked as a large constant; this will prevent it from being inlined to each use of it.

```typescript
import { LargeConstant } from "@kimlikdao/kdts";
import { arfCurve } from "@kimlikdao/lib/crypto/arfCurve";

const P = (1n << 254n) + 0x224698fc094cf91b992d30ed00000001n satisfies LargeConstant;
const Pallas: Curve = arfCurve(P, 5n);
```

### PureExpr

Marks an expression as side-effect free and deterministic.

```typescript
import { Overridable, PureExpr } from "@kimlikdao/kdts";
import { f, g } from "./util";

const KeepConsole = true satisfies Overridable;

const x = f(100 + g(5)) + f(g(2)) satisfies PureExpr;

if (KeepConsole)
  console.log(x);
```

Now kdts is free to eliminate the entire initializer expression of x. If \`KeepConsole=true\`, kdts is free to replace x with the evaluated result in `console.log(x)`.


# Types and declarations

### Declaration files

In kdts, `.d.ts` files retain their usual TypeScript role as declaration files, but they also carry an additional optimization meaning: types declared in `.d.ts` files are treated as external types, so their property names are preserved rather than minified.

This extension lets kdts aggressively minify property names on internal types while keeping externally visible data shapes stable. In practice, that means smaller JavaScript and lower download and parse costs.

As an example, consider

{% code title="user.d.ts" %}

```typescript
interface UserDto {
  firstName: string,
  age: number,
}

export { UserDto };
```

{% endcode %}

{% code title="user.ts" %}

```typescript
import { UserDto } from "./user.d";

interface User {
  firstName: string
  age: number
}

const serialize = (user: User): string => {
  const userDto: UserDto = {
    firstName: user.firstName,
    age: user.age,
  };
  return JSON.stringify(userDto);
}

const user: User = {
  firstName: "Abc",
  age: 20,
};

console.log(user);
console.log(serialize(user));
```

{% endcode %}

When compiled with `kdts user.ts`, we get

{% code title="user.out.js" %}

```javascript
var g={h:"Abc",g:20};console.log(g),console.log(JSON.stringify({firstName:g.h,age:g.g}));
```

{% endcode %}

Note that the properties of the `User` interface got minified as `firstName->h` and `age->g` however the properties of `UserDto` interface are preserved since it is defined in a d.ts file.

In kdts each type that needs to have its properties preserved should be defined in a d.ts file.

### Nominal and structural types

In kdts two object types having the same shape are assignable to each other, just like in regular TypeScript.

```typescript
type User = { name: string, age: number }
const user: User = { name: "Abc", age: 20 };
type Person = { name: string, age: number }
const person: Person = user;
```

By contrast, `class`es and `interface`s are nominal in kdts, so assignability requires an explicit subtype-supertype relationship.

```typescript
interface Animal {
  name: string;
  makeSound(): void;
}

interface Dog extends Animal {
  breed: string;
}

const dog: Dog = {
  name: "Buddy",
  breed: "Golden Retriever",
  makeSound() {
    console.log("Woof!");
  },
};

console.log(dog.name); // "Buddy"
const animal: Animal = dog;
animal.makeSound();    // "Woof!"
```

Two nominal types that would be assignable to each other in regular TypeScript can still be assigned, though an explicit cast is required in kdts:

```typescript
interface A { a: string }
interface B { a: string }
const a: A = { a: "a" };
const b: B = a as B;
```

Making `class`es and `interface`s nominal gives `kdts` more room to perform type-driven optimizations.

### Object literals

In kdts, interfaces are nominal rather than structural, so a value with the same shape is not automatically considered to be of an interface type. There is one important convenience rule, though: when an object literal is used as the initializer of a binding with an explicit type annotation, kdts treats that object literal as having the declared type of the binding. For example, in

```typescript
interface User { id: string }
const user: User = { id: "id" };
```

the expression `{ id: "id" }` starts out as a plain object literal, but because it initializes a binding declared as `User`, it is automatically treated as a `User`. This makes nominal interfaces ergonomic to construct without requiring an explicit cast at each declaration.

The same rule applies to return values in a function with a declared return type:

```typescript
function getUser(): User {
  return { id: "id" };
}
```


# Testing & benching

### Tests

Use `kdts test` to compile matching test files and then run them with Bun's test runner, which has a jest-like interface. See <https://bun.com/docs/test> for Bun's test API.

```sh
kdts test # --fast param available in all variants
kdts test crypto
kdts test path/some.test.ts
```

With no target, kdts test discovers `**/*.test.{js,ts}`. If the target is a directory, it runs matching test files under that directory.

Because the files are compiled first, `kdts test` is the right command when you want to validate kdts-specific transforms or the same compiled path you ship.

If you only want to run a test directly under Bun, without kdts compilation, use:

```shellscript
bun test path/some.test.ts
```

This is useful for quick iteration, but it does not validate kdts's compiled output.

### Benchmarks

Use `kdts bench` to compile matching benchmark files and then run the compiled output.

```shellscript
kdts bench # --fast param avilable in all variants
kdts bench util/hex
kdts bench exp.bench.ts
```

With no target, `kdts bench` discovers `**/*.bech.{js,ts}`.

For benchmarks, kdts also provides a correctness-checked harness:

{% code title="exp.bench.ts" %}

```typescript
import { bench } from "@kimlikdao/kdts/bench";
import { exp, exp2 } from "@kimlikdao/lib/crypto/modular";

const Q = 0xDAD19B08F618992D3A5367F0E730B97C6DD113B6A2A493C9EDB0B68DBB1AEC020FB2A64C9644397AB016ABA5B40FA22655060824D9F308984D6734E2439BA08Fn;

bench("512-bit exp(2, x, M) vs exp2(x, M)", {
  "exp": (x: bigint) => exp(2n, x, Q),
  "exp2": (x: bigint) => exp2(x, Q),
}, {
  repeat: 1000,
  dataset: [{ input: Q - 1n, output: 1n }]
});
```

{% endcode %}

It can be run with

```shellscript
kdts bench exp.bench.ts
```

It prints an output like:

```
512-bit exp(2, x, M) vs exp2(x, M)
  exp2  95.95 ms       (fastest)
  exp   99.31 ms    3.5% slower
```

The benchmark harness has the following signature:

```typescript
const bench = <I, O>(
  description: string,
  fns: Record<string, (input: I) => O>,
  options: { repeat: number, dataset: { input: I, output: O }[] },
): void;
```

In particular, the `bench()` harness takes a description, a record of functions to benchmark (each with the same signature), a repeat count and a dataset of input-output pairs.

Each candidate is run repeat times for every dataset item. Its result is checked against the expected output, and candidate order is shuffled per dataset item to reduce order bias.

Useful options: `--fast`, `--filter`, `--buildConcurrency`, and `--runConcurrency`. Run `kdts --help` for the full CLI reference.


# The gcc backend

In the `opt` mode, kdts uses a fork of Google Closure Compiler (gcc) as a backend. This fork, which is called kdts-gcc in this document, is hosted at <https://github.com/KimlikDAO/gcc>.

Compared to stock gcc, this fork performs more aggressive optimizations; which often means making more assumptions about the accuracy of user provided types.

Some differences between kdts-gcc and stock gcc:

#### Constant folding of type predicates

In kdts-gcc, type predicates such as `Array.isArray(x)`, `typeof x == y`, `x instanceof y` are constant-folded if the declared or inferred type of the expression is enough the conclude the value of the expression.

See the [commit](https://github.com/google/closure-compiler/commit/95bd88c1ae26bea5f1e6c5a0f96a9470e844842a)

#### Color narrowing after a function inline

Stock gcc has advanced function inlining capabilities. If a function is inlined in the block mode, the body preserves the colors (types) of the original function. kdts-gcc tries to narrow the colors to ones implied by the specific parameters at the call site. This narrowing can lead to cascaded folds in the following passes.

See the [commit](https://github.com/google/closure-compiler/commit/7e6a1546d04802ac286a25525534599476371673)


# evm

Built-in typed evm assembler

Our ethereum module comes with an end to end integrated, fully typed EVM assembler. Using `kimlikdao-lib` one can interact deeply with the ethereum network:

* synthesize and execute one-off EVM scripts (init code) on the fly
* synthesize contracts and deploy them on the fly
* interact with preexisting or freshly deployed contracts

Just like regular programs are composed of functions, in our assembler, programs are composed of `Fragment`s. `Fragment`s are pieces of code which start with some type prerequisites on the EVM stack and provides detailed guarantees on the effects of it on the stack.

For instance the `gas()` method has no prerequisites on the stack, emits a single `Word` without consuming anything from the stack. In our assembler, this is denoted with the type signature

```typescript
gas(): () → Word|0
```

Here are signatures of a few other built-ins:

```typescript
ret(offset, size): (Locn, Size) → |2
sload(key): (Word) → Word|1
sstore(key, value): (Word, Word) → |2
call(gas, address, value, argsOffset, argsSize, retOffset, retSize):
  (Word, Addr, Word, Locn, Size, Locn, Size) → Bool|7
```

So far `Fragment`s may be looking just like functions. The differences start when we start composing `Fragment`s. For instance `call` may behave like the following:

```typescript
call(gas, address, value, 0, 32, retOffset, retSize):
  (Word, Addr, Word, , , Locn, Size) → Bool, Locn|7
```