Truly recursive Template Literal for comma-separated strings in Typescript

Viewed 1581

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?

1 Answers

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

Related