Lazy-evaluated string-literal type

Question

Context

Consider two object types:

type Message = {
  content: string;
  owner: Owner;
};

type Owner = {
  email: string;
  ownedMessages: Message[];
};

Messages points to Owner, which points to Messages.

Goal

I want to create a Path validator.

Valid Paths

Here are examples of valid paths:

"messages" 
"messages.content"
"messages.owner" 
"messages.owner.email"
"messages.owner.ownedMessages"
"messages.owner.ownedMessages.content"
"messages.owner.ownedMessages.owner" // ...

Invalid paths

And invalid paths:

// incorrectly spelled
message 
messages.emaill
messages.foo
messages.ownerr
messages.owner.foo

Constraints

I have two constraints in this problem:

First, there is theoretically no depth limit to this.

It should be possible to write messages.owner.ownedMessages.owner.ownedMessages et al

If absolutely necessary, we could add one, but it would be amazing if it was not needed.

Second, I would love it if the intellisense was lazy

If the user starts typing:

messages.

I would love it if only messages.content and messages.owner showed up as autocomplete suggestions. Similarily if they write:

messages.owner.

Only messages.owner.email and messages.owner.ownedMessages to show up as autocomplete suggestions. This would make the developer e

Best solution I have:

The best solution I was able to come up with unfortunately has a depth, and it eagerly evaluates all possible paths.

Here's the TS playground of the best solution i have

type Message = {
  content: string;
  owner: Owner;
};

type Owner = {
  email: string;
  ownedMessages: Message[];
};

type Prev = [never, 0, 1, 2, 3, 4, 5];

// Problem: have to use depth
type DotNotationPaths<T, MaxDepth extends number = 5> = MaxDepth extends 0
  ? never
  : T extends object
  ? {
      [K in keyof T & string]: T[K] extends Array<infer U>
        ? K | `${K}.${DotNotationPaths<U, Prev[MaxDepth]>}`
        : T[K] extends object
        ? K | `${K}.${DotNotationPaths<T[K], Prev[MaxDepth]>}`
        : K;
    }[keyof T & string]
  : never;


type ValidMessagePath = "messages" |`messages.${DotNotationPaths<Message>}`;

// Problem: all paths eagerly evaluated
const validPath1: ValidMessagePath = "messages.content"; // ✓ 
const validPath2: ValidMessagePath = "messages.owner"; // ✓
const validPath3: ValidMessagePath = "messages.owner.email"; // ✓
const validPath4: ValidMessagePath = "messages.owner.ownedMessages"; // ✓
const validPath5: ValidMessagePath = "messages.owner.ownedMessages.content"; // ✓
const validPath6: ValidMessagePath = "messages.owner.ownedMessages.owner.email"; // ✓
const validPath7: ValidMessagePath = "messages"; // ✓

// These would cause TypeScript errors:
// @ts-expect-error
const invalidPath1: ValidMessagePath = "messages.contentt"; // ✗
// @ts-expect-error
const invalidPath2: ValidMessagePath = "messages.owner.emailll"; // ✗
// @ts-expect-error
const invalidPath3: ValidMessagePath = "messages.ownerr"; // ✗

Related problems

I know that arklang seems to be able to do this kind of validation, in a lazy way. For example they can write string | number | string ... ad infinitum.

I am not sure how they do this though.

Answer 1

TypeScript cannot handle infinite union types, nor does it do well with finite unions that contain many tens of thousands of members. If you find yourself wanting to create infinite unions, or finite-but-very-large unions, you'll probably need to give up on having a specific type.

Instead of a specific type like ValidMessagePath, you can try to write a generic type like ValidMessagePath<P> where the type argument P is a candidate path, and TypeScript will try to validate it. If the path is valid, then ValidMessagePath<P> will be the same as P. If not, then ValidMessagePath<P> should be the "closest" valid path, preferably one which you want to see in an IDE's autosuggestion or autocompletion functionality. You then use it like a constraint; conceptually, if P extends ValidMessagePath<P> then you've got a valid path, and if not, then you don't.

Let's focus on writing ValidPath<T, P> where T is the type you're trying to write paths into. And then you can define

type ValidMessagePath<P extends string> = ValidPath<{ messages: Message }, P>

So let's write ValidPath<T, P>. Your requirements are a little strange, in that you decide to turn arrays into their elements (e.g., {x: {y: string}[]} has a path like x.y and not like x.0.y), so we need to handle that. And if T is not an object you want to terminate the path, so you don't get x.y.charAt.length.toFixed as suggested paths.

Here's one approach:

type ValidPath<T, P extends string> =
  T extends object ?
  (T extends readonly (infer U)[] ? U : T) extends infer T ?
  P extends keyof T ? P :
  P extends `${infer K}.${infer R}` ?
  K extends keyof T ? `${K}.${ValidPath<T[K], R>}` : (string & keyof T)
  : (string & keyof T) : never : never

The T extends object ? ⋯ : never on the outside handles non-objects. Then (T extends readonly (infer U)[] ? U : T) extends infer T ? ⋯ handles turning arrays into just their elements (and reuses the T name).

The meat of the type is checking P extends keyof T ? P : ⋯, where we check if the whole string is a non-dotted key of T. If so, great. If not, we then check P extends `${infer K}.${infer R}` ? ⋯ : (string & keyof T)`, splitting the path the first dotted path segment K, and the rest R. If that doesn't work, then we don't have a usable path, and we replace it with (the string portion of) keyof T, which is the "closest" valid path. If the splitting works then we finally hit the recursive case: K extends keyof T ? `${K}.${ValidPath<T[K], R>}` : (string & keyof T); if K is a key of T then we recurse where we use K as the beginning of the path, and ValidPath<T[K], R> as the rest of it. If K is not a valid key then again, the string portion of keyof T is the "closest" valid path.

Now we have ValidPath<T, P> and therefore ValidMessagePath<P>, but it's hard to use such a type directly. You can't write const validMessagePath: ValidMessagePath<infer> = "messages.content"; inference doesn't work like that. And writing const validMessagePath: ValidMessagePath<"messages.content"> = "messages.content" works but is redundant.

Instead we can write a generic helper identity function validMessagePath() which returns its input at runtime, purely so that TypeScript's generic function type argument inference will give us the equivalent of ValidMessagePath<infer>:

const validMessagePath = <P extends string>(
  path: P extends ValidMessagePath<P> ? P : ValidMessagePath<P>) => path;

So you can't write const p: ValidMessagePath = "⋯" but you can write const p = validMessagePath("⋯"). Like this:

const validPath1 = validMessagePath("messages.content"); // ✓ 
const validPath2 = validMessagePath("messages.owner"); // ✓
const validPath3 = validMessagePath("messages.owner.email"); // ✓
const validPath4 = validMessagePath("messages.owner.ownedMessages"); // ✓
const validPath5 = validMessagePath("messages.owner.ownedMessages.content"); // ✓
const validPath6 = validMessagePath("messages.owner.ownedMessages.owner.email"); // ✓
const validPath7 = validMessagePath("messages"); // ✓

const invalidPath1 = validMessagePath("messages.contentt"); // ✗ error!
// Argument of type '"messages.contentt"' is not assignable to parameter of 
// type '"messages.content" | "messages.owner"'.
const invalidPath2 = validMessagePath("messages.owner.emailll"); // ✗ error!
// Argument of type '"messages.owner.emailll"' is not assignable to parameter of type
// '"messages.owner.email" | "messages.owner.ownedMessages"'.
const invalidPath3 = validMessagePath("messages.ownerr"); // ✗ error!
// Argument of type '"messages.ownerr"' is not assignable to parameter of type
// '"messages.content" | "messages.owner"'.

This works exactly how you want, and when you make typos, you are given error messages that give you a hint about what you should have done instead. This is also useful for autosuggest/autocomplete:

validMessagePath("") 
// suggests: validMessagePath(path: "messages")
validMessagePath("messages.");
// suggests: validMessagePath(path: "messages.content" | "messages.owner"):
validMessagePath("messages.owner.")
// suggests: validMessagePath(path: "messages.owner.email" | "messages.owner.ownedMessages"

Playground link to code