Rebuild JSON.stringify in the type system: toJSON, dropped undefined values, arrays that null them instead. Key order is not observable, so every order is an answer.
JSON.stringify has three different ways of making a value disappear, and the type system has none of the ordering guarantees you would like.
Stringify<T> returns the exact string literal that JSON.stringify would produce for a value of type T. Properties typed undefined, functions and symbol keys drop out of objects but become null inside arrays, a toJSON method replaces the whole value, and everything else gets quoted or not depending on what it is. The part that makes this an extreme challenge is the key order: an object type carries no insertion order you can read back, so for an object with more than one ordinary key the honest answer is a union of every possible ordering.
type Result = Stringify<{
0: [ { toJSON: () => 0 }, [[1]], { outer: { inner: 2 } } ],
a: 'a',
b: { bb: false },
c: undefined
}>
type Expected = `{"0":[0,[[1]],{"outer":{"inner":2}}],${'"a":"a","b":{"bb":false}' | '"b":{"bb":false},"a":"a"'}}`Implement a stringifier mimicking JSON.stringify at the type-level.
type Result = Stringify<{
0: [ { toJSON: () => 0 }, [[1]], { outer: { inner: 2 } } ],
a: 'a',
b: { bb: false },
c: undefined
}>;
type Expected = `{"0":[0,[[1]],{"outer":{"inner":2}}],${'"a":"a","b":{"bb":false}' | '"b":{"bb":false},"a":"a"'}}`;View on GitHub: https://tsch.js.org/37505
Change the following code to make the test cases pass (no type check errors).
/* _____________ Your Code Here _____________ */
type Stringify<T> = any
/* _____________ Test Cases _____________ */
import type { Equal, Expect } from '../helpers'
type cases = [
Expect<Equal<Stringify<1>, '1'>>,
Expect<Equal<Stringify<'1'>, '"1"'>>,
Expect<Equal<Stringify<true>, 'true'>>,
Expect<Equal<Stringify<null>, 'null'>>,
Expect<Equal<Stringify<undefined>, undefined>>,
Expect<Equal<Stringify<() => ''>, undefined>>,
Expect<Equal<Stringify<{}>, '{}'>>,
Expect<Equal<Stringify<{a: undefined, b: () => '', c: null} & {[K in symbol]: null}>, '{"c":null}'>>,
Expect<Equal<Get access to all 200+ challenges, including every medium, hard, and extreme one.
One-time payment, lifetime access. 30-day money-back guarantee.
The solution in full:
type Digit = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
type AllDigits<S extends string> = S extends `${infer C}${infer Rest}`
? C extends Digit ? AllDigits<Rest> : false
: true
type IsIndexKey<S extends string> = S extends `${infer C}${infer Rest}`
? C extends Digit
? Rest extends '' ? true : C extends '0' ? false : AllDigits<Rest>
: false
: false
type IndexKeys<K extends string> = K extends K
? IsIndexKey<K> extends true ? K : never
: never
type Comma<A, B> = A extends ''
? B & string
: B extends '' ? A & string : `${A & string},${B & string}`
type At<E, K> = K extends keyof E ? E[K] : never
type Entry<K extends string, V> = Stringify<V> extends infer S extends string
? `"${K}":${S}`
: never
type Entries<T> = {
[K in Extract<keyof T, string | number> as Entry<`${K}`, T[K]> extends never
? never
: `${K}`]: Entry<`${K}`, T[K]>
}
type JoinIndexed<E, K, I extends 0[] = []> = [K] extends [never]
? ''
: `${I['length']}` extends K
? Comma<At<E, `${I['length']}`>, JoinIndexed<E, Exclude<K, `${I['length']}`>, [...I, 0]>>
: JoinIndexed<E, K, [...I, 0]>
type JoinUnordered<E, K, All = K> = [K] extends [never]
? ''
: K extends K ? Comma<At<E, K>, JoinUnordered<E, Exclude<All, K>>> : never
type JoinEntries<E, K extends string = keyof E & string> = Comma<
JoinIndexed<E, Extract<K, IndexKeys<K>>>,
JoinUnordered<E, Exclude<K, IndexKeys<K>>>
>
type Braced<S> = S extends string ? `{${S}}` : never
type StringifyObject<T> = Braced<JoinEntries<Entries<T>>>
type StringifyItem<T> = Stringify<T> extends infer S extends string ? S : 'null'
type StringifyArray<T extends readonly unknown[]> = T extends readonly [infer Head, ...infer Rest]
? Rest extends readonly []
? StringifyItem<Head>
: `${StringifyItem<Head>},${StringifyArray<Rest>}`
: ''
type Stringify<T> = T extends { toJSON: () => infer R }
? Stringify<R>
: T extends undefined | symbol | ((...args: never[]) => unknown)
? undefined
: T extends string
? `"${T}"`
: T extends number | boolean | null
? `${T}`
: T extends readonly unknown[]
? `[${StringifyArray<T>}]`
: T extends object
? StringifyObject<T>
: neverStringify is one conditional chain, and the order of its branches is most of the specification. toJSON is checked first because it wins over everything, including over the object that carries it. The unrepresentable values come next and return the type undefined, not the string 'undefined'. Strings get quotes; numbers, booleans and null go straight into a template literal, which is allowed to interpolate null and produces 'null'. Arrays are checked before objects, because a tuple satisfies extends object too.
// Stringify<1> is '1'
// Stringify<'1'> is '"1"'
// Stringify<() => ''> is undefined
// Stringify<{ toJSON: () => 123 }> is '123'Entry<K, V> builds a single "key":value fragment, and it is also the filter. Stringify<V> extends infer S extends string infers the result and constrains it in the same step. When V is a function or undefined, Stringify<V> is undefined, the constraint extends string fails, and the whole conditional takes its false branch:
// Entry<'a', 1> is '"a":1'
// Entry<'a', undefined> is neverEntries<T> turns the object into a lookup table of those fragments. Two things happen in the key position. The as clause remaps each key, so the numeric key 0 arrives as the string '0' and can be compared against other strings later. And a key remapped to never is deleted, which is how the dropped properties leave:
[object Object]Symbol keys never get that far. Extract<keyof T, string | number> is the source of the mapping, and the symbol index signature from the test does not survive it.
JSON.stringify emits array-index keys first in ascending numeric order, and only then the remaining keys in insertion order. Insertion order is not something a type can observe, so the solution splits the keys and treats the two groups differently.
IsIndexKey accepts a canonical index: all digits, and no leading zero unless the key is exactly '0'. IndexKeys applies it to a union one member at a time. The K extends K looks like a tautology, but a naked type parameter on the left of extends makes the conditional distributive, so the body runs once per member and the results are unioned back together:
// IsIndexKey<'01'> is false
// IndexKeys<'0' | 'a' | '12'> is '0' | '12'JoinIndexed then counts. I is an accumulator tuple whose only job is its length, so ${I['length']} gives the string '0', '1', '2' and so on. Each step either finds that key in the remaining set and emits it, or finds nothing and counts one higher. The recursion stops when the key set is empty, which is why only canonical index keys are allowed into it: a key the counter can never reach would never terminate.
JoinUnordered handles the rest. It distributes over the key union, picks each key as the next one in turn, and recurses on what is left, which produces every ordering as a union:
// JoinUnordered<{ a: '"a":1'; b: '"b":2' }, 'a' | 'b'>
// is '"a":1,"b":2' | '"b":2,"a":1'That union grows as a factorial. Two keys give two orderings, three keys give six. It is the price of being honest about an order the compiler does not track. Comma glues the two halves together and skips the separator when one side is empty, so '{}' comes out with nothing between the braces.
An array keeps its holes. StringifyItem reuses the same constrained inference as Entry, except that a failed constraint becomes 'null' instead of never, and StringifyArray walks the tuple head by head:
[object Object]Writing StringifyObject<T> as a template literal directly, `{${JoinEntries<Entries<T>>}}`, compiles to TS2589: Type instantiation is excessively deep, and it does so before any test runs. Template literal types resolve their placeholders eagerly, so the compiler walks straight back into Stringify while it is still defining it. Moving the braces into Braced<S>, where the check sits on a bare type parameter, defers the work until an actual type arrives. Any time a recursive type alias reports depth problems at the declaration itself, look for an eager position like this one.
Stringify<undefined> and Stringify<() => ''> return the type undefined, not a string. The branch returns undefined itself, which is also what makes those keys vanish from objects.{ a: undefined, b: () => '', c: null } intersected with a symbol index signature returns {"c":null}. Two keys fail the Entry constraint, and the symbol key never enters the mapping.{ a: 1, b: 2 } returns both orderings as a union. A solution that commits to one of them fails the assertion, since the expected type is the union.{ 0: 'a', 1: 'b' } returns a single string. Index keys are sorted by the counter in JoinIndexed, so there is nothing to permute.{ toJSON: () => 123 } returns '123'. The toJSON branch replaces the object instead of describing it.[undefined, () => '', 1] returns [null,null,1], the one place where a value with no JSON form is kept rather than removed.undefined. Only the two string keys at the top level permute, which is why the expected type has exactly two members.This challenge is originally from here.
Track your progress through 200+ hands-on challenges. Free, sign in with GitHub.
Or start solving right away: explore all TypeScript challenges