Ensure a list of objects have unique keys in TypeScript at compile-time

Issue

I have a list of objects in TypeScript and I'd like to ensure that their keys are unique at compile-time.

For instance:

const obj1 = { a: 1, b: 2 };
const obj2 = { c: 3, d: 4 };
const obj3 = { e: 5, f: 6 };
const obj4 = { a: 7, g: 8 }; // 'a' is duplicated

I'm able to write a TS function that ensures uniqueness between any two objects:

declare function ensureUniqueKeys<
  A,
  B extends { [K in keyof B]: K extends keyof A ? never : B[K] },
>(a: A, b: B): unknown;

ensureUniqueKeys(obj1, obj2); // no issues
ensureUniqueKeys(obj1, obj4); // Error: Types of property 'a' are incompatible.

But I can't figure out a way to make this work with an arbitrary list of objects.

I've been trying to write some sort of recursive checker, but it never reports any error:

type EnsureUniqueKeys<T extends string[], PreviousKeys = never> = T extends [
  infer First,
  ...infer Rest,
]
  ? First extends object
    ? Rest extends string[]
      ? keyof First extends PreviousKeys
        ? never // Overlap detected, trigger a compile-time error
        : EnsureUniqueKeys<Rest, PreviousKeys | keyof First>
      : never
    : never
  : unknown;

declare function ensureUniqueKeysRecursive<T extends string[]>(...objects: EnsureUniqueKeys<T>[]): unknown;

ensureUniqueKeysRecursive(obj1, obj2, obj3, obj4); // No errors :(

Again: I'm aware that this could be done at run-time easily, but I need it to check uniqueness at compile-time.

TS Playground

Solution

The goal is to write ensureUniqueKeys() so that it accepts a variadic number of object arguments, so that no key of any of argument is known to exist in any other argument.

The approach I'd take is to make a mapped type over the array of inputs T, iterating over the numberlike keys I.

For each element T[I], we can construct the union of keys of every element of T except the one at index I. We can map over T again, this time iterating over the numberlike keys J. The set of keys we're looking for is { [J in keyof T]: J extends I ? never : keyof T[J] }[number].

If T[I] has any key K in that set of keys, then it's a duplicated key and will set the property to never. Otherwise we will leave it as T[I][K].

The whole thing looks like:

declare function ensureUniqueKeys<T extends object[] & {
  [I in keyof T]: {
    [K in keyof T[I]]: K extends {
      [J in keyof T]: J extends I ? never : keyof T[J]
    }[number] ? never : T[I][K]
  }
}>(...args: T): void;

Let's test it:

const obj1 = { a: 1, b: 2 };
const obj2 = { c: 3, d: 4 };
const obj3 = { e: 5, f: 6 };
const obj4 = { a: 7, g: 8 }; // 'a' is duplicated
ensureUniqueKeys(obj1, obj2, obj3); // okay
ensureUniqueKeys(obj1, obj2, obj3, obj4); // error
//               ~~~~~~~~~~~~~~~~~~~~~~
// The types of 'a' are incompatible between these types.

Looks good.

---

For clarity, let's walk through the types a bit.

In the first call, T is inferred as [{a: number, b: number}, {c: number, d: number}, {e: number, f: number}]. I iterates over the numberlike keys "0", "1", and "2". When I is "0", then { [J in keyof T]: J extends I ? never : keyof T[J] } is [never, "c" | "d", "e" | "f"]; the first element is never because J extends I is true there. Indexing into this with number gives "c" | "d" | "e" | "f". Since T[0] has no keys in that set, then { [K in keyof T[0]]: K extends "c" | "d" | "e" | "f" ? never : T[0][K] } is just {a: number, b: number}. Meaning that the first element of T is acceptable because it's assignable to itself. You can show that the other two elements are also acceptable.

In the second call, T is inferred as [{a: number, b: number}, {c: number, d: number}, {e: number, f: number}, {a: number, g: number}]. Now when I is "0", the type { [J in keyof T]: J extends I ? never : keyof T[J] } is [never, "c" | "d", "e" | "f", "a" | "g"], and indexing with number gives "c" | "d" | "e" | "f" | "a" | "g"]. Since T[0] does have a key in that set, then { [K in keyof T[0]]: K extends "c" | "d" | "e" | "f" | "a" | "g" ? never : T[0][K] } is equivalent to {a: never, b: number}. That means the first element of T is not acceptable, because {a: number, b: number} is not assignable to {a: never, b: number}. And we get an error message saying there's a problem with the a key.

Playground link to code

Answered By - jcalz