How to Type a Recursive Variadic Tuple

I have an array of query elements, where each element can be a term or a subquery containing starting with either "AND" or "OR", and followed by an array of legal query elements, terms or nested subqueries, and so on.

For example, these should all be legal input:

const query1 = "Hello"
const query2 = ["AND", "Hello", "World"]
const query3 = ["OR", ["AND", "Hello", "World"], ["AND", "Hola", "Mundo"]]

Variadric Tuples in TS 4.0 should allow you to type the first element of an array and another type for the rest:

type IQuery = ["AND" | "OR", ...Array<string>]
const query = ["AND", "Hello", "World"]  // valid

Recursive Types in TS 3.7 should allow you to define an type that uses itself:

type IQueryOps = string | Array<IQueryOps>
const query: IQueryOps = ["Hello", "World", ["Hola", "Mundo"]]  // valid

But I can't seem to combine the two when the circular type is spread. In this case, each query begins with an operator, and is followed up by either a string or another valid query like this:

type IOperator = "AND" | "OR"
type IQuery = [IOperator, ...Array<string | IQuery>]

In this case, I get the error:

Type alias 'IQuery' circularly references itself.(2456)

Is there anyway to type this, even with workarounds, or do I have to unwrap it to the desired level of depth I'd like to support from a types perspective?

Demo in TS Playground

Answer

October 31, 2021

jcalz

I think this might be an instance of the TypeScript design limitation reported in microsoft/TypeScript#41164. As mentioned there,

Certain circularities are allowed [...] but other circularities aren't, e.g.
type Identity<T> = T;
type T3 = Identity<T3>;
Generic instantiation is deferred, so at the point TS analyzes [a] declaration, it can't tell if it's in the Record case (would be allowed) or the Identity case (would not be allowed). It's only later in the process that we could tell that this is actually OK, but if it wasn't OK, it's "too late" to go back and start complaining about it.

If that's the issue, then while the following should be "okay", it seems that the compiler cannot tell early enough to allow it:

// type IQuery = string | ["AND" | "OR", ...Array<IQuery>] error

(I changed your definition slightly to allow the const query1 = "Hello" line).

Luckily, Array<T> has an alternative built-in syntax T[] which does not seem to be deferred in that manner:

type IQuery = string | ["AND" | "OR", ...IQuery[]] // okay

And this works:

const query1: IQuery = "Hello"
const query2: IQuery = ["AND", "Hello", "World"]
const query3: IQuery = ["OR", ["AND", "Hello", "World"], ["AND", "Hola", "Mundo"]]
const query4: IQuery = ["AND", ["OR", ["AND"]]]; 

const badQuery1: IQuery = 3; // error
// Type 'number' is not assignable to type 'IQuery'
const badQuery2: IQuery = ["AND", "Hello", 123]; // error
// Type 'number' is not assignable to type 'IQuery'
const badQuery3: IQuery = 
  ["OR", query1, query2, "then", query3, query4, "if", []]; // error
// Type '[]' is not assignable to type 'IQuery'.

Playground link to code

Demo in TS Playground

Further Reading

Answer