#37505•Extreme

JSON Stringifier

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"'}}`

Challenge Instructions: JSON Stringifier

Extreme

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).

ChallengeSolution
/* _____________ 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<

Pro Challenge

Get access to all 200+ challenges, including every medium, hard, and extreme one.

One-time payment, lifetime access. 30-day money-back guarantee.

Detailed Explanation

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>
            : never

The branch order is the spec

Stringify 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'

One entry per key

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 never

Entries<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.

Two kinds of keys

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.

Arrays null what objects drop

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]

Why the braces get their own type

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.

Edge cases the tests cover

This challenge is originally from here.

Share this challenge

Related Challenges

Learn the Concepts

Become a TypeScript Pro

Track your progress through 200+ hands-on challenges. Free, sign in with GitHub.

Or start solving right away: explore all TypeScript challenges