13

I am trying to define a Typescript template literal for a string containing comma-separated values. Can I make this definition truly recursive and general?

See this typescript playground to experiment with the case.

Each comma separated value represents a sort order like height asc. The string should define an order (including primary, secondary, tertiary and so on) which may contain indefinitely many sort levels according to a union of valid field names and two possible orderings "asc" and "desc", separated by commas as per the examples in the sample code.

The implementation below handles up to 4 sort orders, but case 5 reveals that it's not really recursive. The arity of the current expansion (2x2) just includes up to 4 possible values so happened by luck to handle the initial cases I tried.

const FIELD_NAMES = [
  "height",
  "width",
  "depth",
  "time",
  "amaze",
] as const;

const SORT_ORDERS = [
  "asc",
  "desc",
] as const;

type Field = typeof FIELD_NAMES[number];
type Order = typeof SORT_ORDERS[number];

type FieldOrder = `${Field} ${Order}`
type Separated<S extends string> = `${S}${""|`, ${S}`}`;
type Sort = Separated<Separated<FieldOrder>>;

/** SUCCESS CASES */
const sort1:Sort = "height asc"; //compiles
const sort2:Sort = "height asc, depth desc"; //compiles
const sort3:Sort = "height asc, height asc, height asc"; //compiles
const sort4:Sort = "height asc, width asc, depth desc, time asc"; //compiles
const sort5:Sort = "height asc, width asc, depth desc, time asc, amaze desc"; //SHOULD compile but doesn't

/** FAILURE CASES */
const sort6:Sort = "height"; //doesn't compile 
const sort7:Sort = "height asc,"; //doesn't compile
const sort8:Sort = ""; //doesn't compile

I can't increase the 'arity' of this template literal any more, since trying to do 2x2x2 like below leads to Expression produces a union type that is too complex to represent

type Sort = Separated<Separated<Separated<FieldOrder>>>;

Is it possible to define a template literal to handle the general case?

Improve this question

2 Answers 2

Reset to default
16

As you saw, the kind of template literal types you are creating quickly blow out the compiler's ability to represent unions. If you read the pull request that implements template literal types, you'll see that union types can only have up to 100,000 elements. So you could only possibly make Sort accept up to 4 comma-separated values (which would need approx 11,110 members). And you certainly couldn't have it accept an arbitrary number, since that would mean Sort would need to be an infinite union, and infinity is somewhat larger than 100,000. So we have to give up on the impossible task of representing Sort as a specific union type.

Generally, my approach in cases like this is to switch from specific types to generic types which act as recursive constraints. So instead of Sort, we have ValidSort<T>. If T is a valid sort string type, then ValidSort<T> will be equivalent to T. Otherwise, ValidSort<T> will be some reasonable candidate (or union of these) from Sort which is "close" to T.

This means that anywhere you intended to write Sort will now need to write ValidSort<T> and add some generic type parameters to an appropriate scope. Additionally, unless you want to force someone to write const s: ValidSort<"height asc"> = "height asc";, you'll want a helper function called, something like asSort() which checks its input and infers the type. Meaning you get const s = asSort("height asc");.

It might not be perfect, but it's probably the best that we can do.

Let's see the definition:

type ValidSort<T extends string> = T extends FieldOrder ? T :
  T extends `${FieldOrder}, ${infer R}` ? T extends `${infer F}, ${R}` ?
  `${F}, ${ValidSort<R>}` : never : FieldOrder;

const asSort = <T extends string>(t: T extends ValidSort<T> ? T : ValidSort<T>) => t;

ValidSort<T> is a recursive conditional type which inspects a string type T to see if it is a FieldOrder or a string that starts with a FieldOrder followed by a comma and a space. If it's a FieldOrder, then we have a valid sort string and we just return it. If it starts with FieldOrder, then we recursively check the remainder of the string. Otherwise, we have an invalid sort string, and we return FieldOrder.

Let's see it in action. Your success cases now all work as intended:

/** SUCCESS CASES */
const sort1 = asSort("height asc"); //compiles
const sort2 = asSort("height asc, depth desc"); //compiles
const sort3 = asSort("height asc, height asc, height asc"); //compiles
const sort4 = asSort("height asc, width asc, depth desc, time asc"); //compiles
const sort5 = asSort(
  "height asc, width asc, depth desc, time asc, amaze desc"); //compiles

And the failure cases fail, with error messages that show "close enough" types you should have used instead:

/** FAILURE CASES */
const sort6 = asSort("height"); // error!
/* Argument of type '"height"' is not assignable to parameter of type 
'"height asc" | "height desc" | "width asc" | "width desc" | "depth asc" | 
"depth desc" | "time asc" | "time desc" | "amaze asc" | "amaze desc"'. */

const sort7 = asSort("height asc,"); // error!
/* Argument of type '"height asc,"' is not assignable to parameter of type 
'"height asc" | "height desc" | "width asc" | "width desc" | "depth asc" | 
"depth desc" | "time asc" | "time desc" | "amaze asc" | "amaze desc"'. */

const sort8 = asSort(""); // error!
/* Argument of type '""' is not assignable to parameter of type 
'"height asc" | "height desc" | "width asc" | "width desc" | "depth asc" | 
"depth desc" | "time asc" | "time desc" | "amaze asc" | "amaze desc"'. */

const sort9 = asSort("height asc, death desc"); // error!
/* Argument of type '"height asc, death desc"' is not assignable to parameter of type 
'"height asc, depth desc" | "height asc, height asc" | "height asc, time asc" |
 "height asc, amaze desc" | "height asc, height desc" | "height asc, width asc" | 
 "height asc, width desc" | "height asc, depth asc" | "height asc, time desc" | 
 "height asc, amaze asc"'. */

I added sort9 to show you how the error message shows you not just FieldOrder, but strings that start with "height asc, " followed by FieldOrder.

Playground link to code

Improve this answer
Sign up to request clarification or add additional context in comments.

8 Comments

Thanks, @jcalz. I speculate that the same approach might be used to address also stackoverflow.com/questions/66298024/… It's really interesting to see how runtime code paths can be used to solve a typing problem!
Why T extends `${FieldOrder}, ${infer R}`? Is it possible to do a T extends `${FieldOrder}, ${ValidSort<infer R>}` instead?
I imagine that would hit recursion limits, but you could always try it yourself.
@jcalz Thanks for this! Any idea if this would work to validate strings which are nested deeper within an object. Eg. validating that foo.bar.baz is an array of strings that have a recursive definition? Best I can think of is to require that each element of that array gets passed through a function like the one above to ensure it's valid, but can't think of a way to do eg. validatedObject({foo: {bar: {baz: ['height asc, death desc', 'width desc', ...]}}})
I would need to see a minimal reproducible example of what you're talking about ("any given type" isn't really enough information for me to proceed), and the comments section of an answer from several years ago really is not an appropriate place to delve into it. If you can't figure it out you should post a question and get fresh eyes on it. Good luck.
|
1

As @jcalz noted, you can make a generic. But you should make sure to return never in the right cases. In my example code I've used a Percentage instead of a FieldOrder because percentages are more concise and let us focus on the TypeScript, but you can plug in FieldOrder instead of Percentage to get your code working.

type Percentage = `${number}%`

type List<Of extends string, Source extends string> = Source extends Of 
? Source 
: Source extends `${Of}, ${infer Rest}` 
? Source extends `${infer First}, ${Rest}` 
  ? `${First}, ${List<Of, Rest>}` 
  : never 
: never;

type PercentageList<Source extends string> = List<Percentage, Source>

const listOne: PercentageList<"100%, 50%"> = "100%, 50%"; // this one is OK, as expected
// const listTwo: PercentageList<"100%, 50%"> = "100%, 50"; // this one is not OK, as expected
// const listThree: PercentageList<"100%, 50%"> = "100%, 100%" // this one is not OK, as expected
// const ListFour: PercentageList<"100%"> = "100%, 50%"; // this one is not OK, as expected
// const listFive: PercentageList<"100%, 50"> = "100%, 50%"; // this one is not OK, as expected (!)

@jcalz's answer, while very good, returns FieldOrder, equivalent to Of, where it should return a final never. As a result it will process listFive type examples incorrectly as valid, when they are actually invalid.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.