Mutually Exclusive Recursive Types in Typescript

Question

Is it possible to combine mutual exclusivity with recursive typing? I need to build a "Filter" type that will separate AND and OR operations so I can easily bracket the conditions. The conditions can go multiple levels deep but have to switch between AND and OR for each new level

{ or: [{ and: [filter1, filter2] }, { and: [{ or: [filter3, filter 4] }, filter5] }; 

I've managed to make the recursive portion of it but I'm wondering if I can squeeze in the mutual exclusivity of AND and OR for each level as well:

enum Operator {
    AND = 'AND',
    OR = 'OR',
}
type Filter = {
    column: string
    rule: string,
    value: number | string | undefined
}
type OperatorHierarchy = { [key in Operator]?: Array<Filter |  OperatorHierarchy> };

const flower: OperatorHierarchy = {
    [Operator.AND]: [
        {
            column: 'plant',
            rule: 'is',
            value: 'flower'
        },
        {
            [Operator.OR]: [
                {
                    column: 'leaf',
                    rule: 'is',
                    value: 'green'
                },
                {
                   [Operator.AND]: [
                      {
                         column: 'leaf',
                         rule: 'is',
                         value: 'brown'
                      },
                      {
                         column: 'petal',
                         rule: 'is',
                         value: 'yellow'
                      },
                   ]
                },
            ]
        }
    ],
};

Typescript Playground

Maybe something along the lines of this (which doesn't work)

type OperatorHierarchy = 
   { [Operator.AND]: Array<Filter | OperatorHierarchy>, [Operator.OR]: void } | 
   { [Operator.AND]: void, [Operator.OR]: Array<Filter | OperatorHierarchy> }

Answer 1

I'd probably define it like this:

type OperatorAndHierarchy = { 
  [Operator.AND]: Array<Filter | OperatorOrHierarchy>, 
  [Operator.OR]?: never 
};
type OperatorOrHierarchy = { 
  [Operator.OR]: Array<Filter | OperatorAndHierarchy>, 
  [Operator.AND]?: never 
};
type OperatorHierarchy = OperatorAndHierarchy | OperatorOrHierarchy;

I've split your OperatorHierarchy into two union members: there's OperatorAndHierarchy which contains an Operator.AND property, and OperatorOrHierarchy which contains an Operator.OR property. (It looks like you tried to do this, but you got the recursion wrong.)

To make the keys mutually exclusive you want OperatorAndHierarchy to prohibit the Operator.OR key (and you want the OperatorOrHierarchy to prohibit the Operator.AND key). The closest we can get to saying that a property should be prohibited is to make it an optional property whose value type is the impossible never type. That means the property could be missing (which is what we want) or, if it's present, it should be never (which is effectively impossible). Well, it could maybe also be undefined depending on your compiler settings (see --exactOptionalPropertyTypes), but that's still pretty close to what you're going for. (It looks like you tried to do this with a required property of type void, but that doesn't work how you want.)

Note that OperatorAndHierarchy is written in terms of OperatorOrHierarchy and vice versa. That is, the types are mutually recursive. This is what forces you to alternate or switch between the two types as you descend through the tree. (This is the solution to the wrong recursion in your attempt; the two types need to be named and mutually recursive, otherwise there's no way to keep track of which operator the parent object used.)

Playground link to code