Typescript: how to enforce unique keys across nested objects-CodePudding

I have a requirement for an object type to not duplicate keys across nested objects. For example, if foo.bar contains the key hello then foo.baz cannot contain that key. Is there any way to enforce this at the type level?

One simplified formulation might be something like the following:

type NestedUniqueKeys<T extends Object> = any // <- what goes here?

interface Something {
  one: string
  two: string
  three: string
  four: string
}

const good: NestedUniqueKeys<Something> = {
  foo: {
    three: 'hi',
    one: 'hi',
  },
  bar: {
    two: 'hiya',
  },
}

// @ts-expect-error
const bad: NestedUniqueKeys<Something> = {
  foo: {
    two: 'hi', // duplicated
    one: 'hi',
  },
  bar: {
    two: 'hiya', // duplicated
  },
}

So a simpler step might be, how could NestedUniqueKeys be formulated for a single level of nesting?

Then, how to extend it to arbitrary nestings?

const good: NestedUniqueKeys<Something> = {
  foo: {
    three: 'hi',
    baz: {
      one: 'oh',
      bill: {
        four: 'uh',
      },
    },
  },
  bar: {
    two: 'hiya',
  },
}

// @ts-expect-error
const bad: NestedUniqueKeys<Something> = {
  foo: {
    three: 'hi',
    baz: {
      one: 'oh',
      bill: {
        four: 'uh', // duplicated
      },
    },
  },
  bar: {
    two: 'hiya',
    foobar: {
      four: 'hey', // duplicated
    },
  },
}

And in the final formulation, could it be made to infer the full set of keys so no type parameter needs to be passed in?

Edit

I tried an initial sketch of something approaching the solution, but this results in all nested keys being forbidden. I guess this is because K is inferred to be string when it's passed into the recursive NestedUniqueKeys? I'm not sure why...

type NestedUniqueKeys<Keys extends string = never> = {
  [K in string]: K extends Keys
    ? never
    : string | NestedUniqueKeys<K|Keys>
}

Playground

Edit 2

Another attempt, I'm not sure why this isn't allowing any keys in the nested objects...

type NestedUniqueKeys<Keys extends string = never> =
  { [K in string]: K extends Keys ? never : string } extends infer ThisLevel
  ? keyof ThisLevel extends string
  ? ThisLevel & {
    [N in string]: N extends Keys ? never : NestedUniqueKeys<keyof ThisLevel|Keys>
  }
  : never
  : never

CodePudding user response：

Please consider this example:

type Primitives = string | number | symbol;

type Values<T> = T[keyof T]

type UnionToIntersection<U> = (U extends any ? (k: U) => void : never) extends (
    k: infer I
) => void
    ? I
    : never;

type IsUnion<T> = [T] extends [UnionToIntersection<T>] ? false : true

type KeysUnion<Obj, Cache extends Primitives = never> =
    Obj extends Primitives ? Cache : {
        [Prop in keyof Obj]:
        | Cache | Prop // <------ it should be unionized with recursion call
        | KeysUnion<Obj[Prop], Cache | Prop>
    }[keyof Obj]

type Validate<
    Obj,
    Key extends PropertyKey,
    Cache extends Record<string, any> = never,
    Index extends number[] = [],
    Root extends string = ''

> =
    Obj extends Primitives
    ? Exclude<Cache, []>
    : {
        [Prop in keyof Obj]:
        Prop extends Key
        ? Validate<Obj[Prop], Key, Record<Key, `${Root}-${Prop & string}-${Index['length']}`>, [...Index, Index['length']], Root extends '' ? Prop : Root>
        : Validate<Obj[Prop], Key, Cache, [...Index, Index['length']], Root extends '' ? Prop : Root>
    }[keyof Obj]

type Structure = {
    foo: {
        three: 'hi',
        baz: {
            one: 'oh',
            bill: {
                four: 'uh', // duplicated
            },
        },
    },
    bar: {
        two: 'hiya',
        foobar: {
            four: 'hey', // duplicated
        },
    },
}



type Distribute<Data, Keys extends PropertyKey = KeysUnion<Data>> =
    Keys extends any ? IsUnion<Validate<Data, Keys>> extends true ? Record<Keys, 'many'> : Record<Keys, 'one'> : never

type Result = keyof Exclude<Distribute<Structure>, Record<string, 'one'>>

Playground

Will provide explanation later

CodePudding user response：

I have found the following solution for the simple case:

type NestedUniqueKeys<T extends object> = keyof T[keyof T] extends never ? T : never

It is actually pretty neat and small. The more general solution is a tad more complicated:

type Prev = [never, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
    11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ...0[]]
// extracts all keys of the object in the form "A.B.C.D", D limits depth
type AllKeys<T, D extends number = 10> = [D] extends [never] ? never : T extends object ?
    UnionToString<{ [K in keyof T]-?: K extends string | number ?
        `${K}` | AllKeys<T[K], Prev[D]>
        : never
    }[keyof T]> : never

// convert a union to an intersection: X | Y | Z ==> X & Y & Z
type UnionToIntersection<U> =
  (U extends any ? (k: U) => void : never) extends ((k: infer I) => void) ? I : never

// convert a union to an overloaded function X | Y ==> ((x: X)=>void) & ((y:Y)=>void)     
type UnionToOvlds<U> = UnionToIntersection<U extends any ? (f: U) => void : never>;

// returns true if the type is a union otherwise false
type IsUnion<T> = [T] extends [UnionToIntersection<T>] ? false : true;

// takes last from union
type PopUnion<U> = UnionToOvlds<U> extends ((a: infer A) => void) ? A : never;

// converts "A" | "B" | "C" ==> "C.B.A"
type UnionToString<U> = IsUnion<U> extends false ? (U extends string ? U : never)
: (PopUnion<U> extends infer P extends string ? `${P}.${UnionToString<Exclude<U, P>>}`: "")

// Checks if "A.B.B.C" has any duplicates between the "."
type Unique<T> = T extends `${infer First}.${infer Rest}` ? Contains<First, Rest> extends true ? false : Unique<Rest> : true

// Checks if "A" is contained in "A.B.C"
type Contains<T, STR> = T extends STR ? true : STR extends `${infer First}.${infer Rest}` ? T extends First ? true : Contains<T, Rest> : false

type NestedUniqueKeys<T extends object> = Unique<AllKeys<T>>

I got some of the helper types from various sources. This does not really seem useful to me, but it was a fun challenge.

CodePudding user response：

Here is another approach. I tried to keep it simple.

I created three generic types to do the validation.

type GetLeafPaths<T, K extends keyof T = keyof T> = 
  K extends K
    ? T[K] extends object
      ? `${GetLeafPaths<T[K]> & string}${K & string}.`
      : `${K & string}.`
    : never

GetLeafsPaths takes an object T and computes all the paths to the leafs as strings. The result would look like this for the first object:

// "three.foo." | "one.baz.foo." | "four.bill.baz.foo." | "two.bar." | "four.foobar.bar."

Note that I chose to have the path in reverse order. This makes it easier to get the leaf value later as is it just the first element.

ExtractLeafName takes a path and extracts the LeafName.

type ExtractLeafName<Path extends string> =  
  Path extends `${infer LeafName}.${string}`
    ? LeafName
    : never

type Result1 = ExtractLeafName<"four.bill.baz.foo.">
//   ^? type Result1 = "four"

Now to the main Validation type.

type Validate<T, Paths = GetLeafPaths<T>> = 
    {
      [K in Paths & string]: 
        ExtractLeafName<K> extends ExtractLeafName<Exclude<Paths, K> & string> 
          ? true 
          : false
    } extends Record<string, false>
      ? true
      : false

The idea is simple: First get all the Paths with GetLeafPaths. Then we map over each path P in Paths.

For each path P, we use Exclude<Paths, P> to get all the other paths in Paths which are not P. We use ExtractLeafName to get the leaf names from both P and Exclude<Paths, P> and compare them with extends. If a leaf name is in any other path, we return true and return false if not.

This produces an object type:

{
    "three.foo.": false;
    "one.baz.foo.": false;
    "four.bill.baz.foo.": true;
    "two.bar.": false;
    "four.foobar.bar.": true;
}

Duplicate leaf names have a true type.

All that is left to do is to check if there are any true values in this object type which we can check with extends Record<string, false>.

The Validate type returns false if any leaf name is duplicated.

Now we only need a function to which we can pass a real object.

function nestedUniqueKeys<T>(arg: Validate<T> extends true ? T : never) {
    return arg
}

A simple conditional type in the parameter let's us use Validate to check T for duplicate leafs.

// Error: is not assignable to parameter of type 'never'
nestedUniqueKeys({
    foo: {
        three: 'hi',
        baz: {
            one: 'oh',
            bill: {
                four: 'uh', // duplicated
            },
        },
    },
    bar: {
        two: 'hiya',
        foobar: {
            four: 'hey', // duplicated
        },
    },
})

// OK
nestedUniqueKeys({
  foo: {
    three: 'hi',
    baz: {
      one: 'oh',
      bill: {
        four: 'uh',
      },
    },
  },
  bar: {
    two: 'hiya',
  },
  topLevelLeaf: "asdasd"
})

The error message is not really helpful. But this is as good as I can get it.

Side note: This can also trivially be expanded to not only validate unique leafs, but all properties. All you need to do is change GetLeafPaths to also construct the paths of the other properties:

type GetLeafPaths<T, K extends keyof T = keyof T> = 
  K extends K
    ? T[K] extends object
      ? `${K & string}.` | `${GetLeafPaths<T[K]> & string}${K & string}.`
      : `${K & string}.`
    : never

Playground