How to Type a Recursive Variadic Tuple

Question

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

Further Reading

• Define a type for an array where the first element is more specific than the rest
• How to create a circularly referenced type in TypeScript?

Answer 1

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

Answer 2

Looking at the description of Recursive Types, variadic tuples aren't explicitly supported. I don't know if it counts as one the three types listed below:

The specific change made by this PR is that type arguments are permitted to make circular references in aliased types of the following kinds:

• Instantiations of generic class and interface types (for example Array<Foo>).
• Array types (for example Foo[]).
• Tuple types (for example [string, Foo?]).

I tested this theory by removing the variadic operator ... from your code:

type IOperator = "AND" | "OR"
type IQuery = [IOperator, Array<string | IQuery>] // NO ERROR

That change resulted in no error, but it doesn't support the syntax you want.

So I reformulated (and simplified) your code as below, and it works! My theory is that using the variadic operator in combination with a generic class instantiation is not supported, whether intentionally or a bug I don't know.

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


// examples from your question
const query1: IQuery = "Hello"
const query2: IQuery = ["AND", "Hello", "World"]
const query3: IQuery = ["OR", ["AND", "Hello", "World"], ["AND", "Hola", "Mundo"]]

// deep nesting
const query4: IQuery = ["OR", ["AND", "Hello", ["AND", "Beautiful", "World"]], ["AND", "Hola", "Mundo"]]


//errors
const query5: IQuery = ["OR", ["NOR", "Hello", ["AND", "Beautiful", "World"]], ["AND", "Hola", "Mundo"]]
const query6: IQuery = ["OR", ["AND", 42, ["AND", "Beautiful", "World"]], ["AND", "Hola", "Mundo"]]