Trying to define a varargs/array of interrelated types

Question

So, I'm working on a library to manage pipelines of transformations (from a source, through several "gaskets", to sinks)... and running into a problem specifically with recursive types. Supposedly that's been possible since TS 3.7, but I think I've run into an edge case that ain't.

interface Sink<E> { seal():void; send(value:E):void; }
type Gasket<I,O> = (target:Sink<O>) => Sink<I>;

/**
 * The type of arrays of gaskets which go from a source type `I` to a sink type `O`.
 */
type Gaskets<I,O,Via=never> =
    // An array containing a single gasket from I to O.
    | [Gasket<I,O>]
    // A gasket from I to Via, followed by gaskets which go from Via to O.
    | [Gasket<I,Via>, ...Gaskets<Via, O>]
;

/**
 * `Join()` is used to cleanly wrap a single sink, or to assemble a sequence of
 * gaskets which goes from type I to type O and into a Sink<O> at the end.
 */
export function Join<I,O=never>(...arg: [Sink<I>]): Sink<I>;
export function Join<I,O>(...arg: [...Gaskets<I,O>, Sink<O>]): Sink<I>;

// @ts-ignore-error
export function Join<I,O>(...arg) {
  // ...
}

The above... doesn't work. Just Gaskets<Via,O> is wrong, but at least doesn't pitch an error... but when I add the spread-operator ... prefix, it pitches Gaskets is not generic ts(2315) at that token, and Type alias Gaskets circularly references itself ts(2456) on the first line where I declare type Gaskets itself.

I've got a temporary workaround, but it basically means manually unrolling the recursion, and therefore supports a limited number of elements. Here it is unrolled to 7 gaskets...

type Gaskets<I,O,V1=never,V2=never,V3=never,V4=never,V5=never,V6=never> = 
    | [Gasket<I,O>]
    | [Gasket<I,V1>, Gasket<V1, O>]
    | [Gasket<I,V1>, Gasket<V1,V2>, Gasket<V2, O>]
    | [Gasket<I,V1>, Gasket<V1,V2>, Gasket<V2,V3>, Gasket<V3, O>]
    | [Gasket<I,V1>, Gasket<V1,V2>, Gasket<V2,V3>, Gasket<V3, V4>, Gasket<V4,O>]
    | [Gasket<I,V1>, Gasket<V1,V2>, Gasket<V2,V3>, Gasket<V3, V4>, Gasket<V4,V5>, Gasket<V5,O>]
    | [Gasket<I,V1>, Gasket<V1,V2>, Gasket<V2,V3>, Gasket<V3, V4>, Gasket<V4,V5>, Gasket<V5,V6>, Gasket<V6,O>]
;

Here's a simplified example of how it's intended to be used, from my specs...

describe("Join", () => {
    it("builds multi-element transformation chains", () => {
        const receiver = jest.fn((e:string) => {});

        const fromString = (i:string) => parseFloat(i);
        const toString = (i:number) => String(i);
        const increment = (i:number) => i+1;

        const chain = P.Join(
            P.Map(fromString),
            P.Map(increment),
            P.Map(increment),
            P.Map(toString),
            P.CallbackSink(receiver)
        );

        chain.send("5");
        chain.send("-2");
        chain.seal();

        expect(receiver.mock.calls).toMatchObject([
            ["7"], ["0"]
        ]);
    })
});

Now, I could just offer 2-argument or 1-to-N-argument forms of Join that only connects two nodes at a time, and write it up as Join(gasket, Join(gasket, Join(gasket, sink)) and so on... but I'd really like to improve the signal-to-noise ratio.

Am I missing a trick, or this is fundamentally impossible presently?

EDIT: here is an error-free TS playground demonstrating the unrolled-type version of the code. The other definition for type Gaskets<I,O> can be substituted in to see the problem.

EDIT: here's a refactoring using @jcalz example code, which works the way I expect, but with some unexpected errors inside the Join() implementation. type OGaskets is utter witchcraft, and while I can follow everything else going on, that bit, and how it contributes to the whole, is incomprehensible to me at this moment.

Answer 1

I'm going to give Gasket and Sink some default generic type parameters so that I can just write Gasket to mean "anything that might be assignable to a Gasket<I, O> for any I and any O". If you don't want to do this, you can give names like AnySink and AnyGasket to these types and use those instead. These are mostly used for constraints.

interface Sink<T = any> { seal(): void; send(value: T): void; }
interface Gasket<I = any, O = any> { (target: Sink<O>): Sink<I> }

---

So the main problem with trying to write Gaskets<I, O> as any kind of specific type is that it would end up being sort of an infinite union of every possible set of types between I and O in your chain of gaskets. This cannot be written directly in TypeScript (there are no direct existentially quantified generics as requested in microsoft/TypeScript#14466).

Instead, the closest we'll be able to get is to write a type that acts as a check on a candidate chain of gaskets that ends in a sink. If this candidate is G, then AsChain<G> will represent something like the "closest" valid chain to G. If Gs is valid chain, then AsChain<G> should be a supertype of G. That is, G extends AsChain<G> will hold when G is a valid chain. On the other hand, if G is an invalid chain, then AsChain<G> should not be a supertype of G. So G extends AsChain<G> will not hold when G is an invalid chain.

This is necessarily more complex then any straightforward representation of Gaskets you were imagining, and is likely to be fragile and have strange edge cases. Really, TypeScript isn't quite able to handle these kinds of recursive chains in an elegant manner.

---

Anyway the call signature for Join will look like this:

function Join<G extends [...Gasket[], Sink]>(
  ...arg: G extends AsChain<G> ? G : AsChain<G>
): any // return type to come

So if you call Join(...arg) then the type parameter G will be inferred as the type of arg. If G is a valid chain, then the conditional type G extends AsChain<G> ? G : AsChain<G> evaluates to G and everything is fine. Otherwise, if G is invalid, the conditional type evaluates to AsChain<G> and since G is not assignable to AsChain<G>, the compiler will complain about some element of G that doesn't fit the corresponding element of AsChain<G>.

By the way, it would be great if we could just write

// won't work
function Join<G extends AsChain<G>>(...arg: G ): any 

or

// also won't work
function Join<G extends [...Gasket[], Sink]>(...arg: AsChain<G> ): any 

since both of those would logically be the same. But neither of those work well with the compiler's type inference. The compiler will fail to infer G to be the same type as arg and will end up complaining about even valid chains. The conditional type above with G extends AsChain<G> ? G : AsChain<G> is the only thing I've found that seems to behave well.

---

So now the big issue is how to define Aschain<G>. The idea here would be to look at a candidate chain like [Gasket<I1, O1>, Gasket<I2, O2>, Gasket<I3, O3>, Sink<T>] and move the type parameters around to ensure that they link up as a chain properly. For example, [Gasket<any, O1>, Gasket<O1, O2>, Gasket<O2, O3>, Sink<O3>]. If the former is assignable to the latter, it's because I2 is assignable to O1, and I3 is assignable to O2, and T is assignable to O3. If one of those assignments fails, then the chain isn't valid.

Unfortunately it's quite a lot of tuple type shuffling to do that. Here are some helper types with brief explanations for what they do.

Init<T> and Last<T> take a tuple type T and split off the final element. Init<[1,2,3]> is the initial part, [1,2], while Last<[1,2,3]> is the final element which is 3:

type Init<T extends any[]> = T extends [...infer R, any] ? R : never;
type Last<T extends any[]> = T extends [...infer F, infer L] ? L : never;

The OGasket<G> type takes takes a Gasket<I,O> and returns O:

type OGasket<G> = G extends Gasket<any, infer O> ? O : never;

The OGaskets<G> type extracts the O part of every Gasket<I, O> in a chain, and moves it to the next element of the tuple. So OGaskets<[Gasket<I1, O1>, Gasket<I2, O2>, Gasket<I3, O3>, Sink<T>]> should become [any, O1, O2, O3]. We will then use these to become the I elements of the final AsChain<G> tuple. Here's the implementation:

type OGaskets<G extends [...Gasket[], Sink]> =
  Init<G> extends infer F ? 
    [any, ...Extract<{ [K in keyof F]: OGasket<F[K]> }, any[]>] : 
  never;

I'm taking G and chopping off the last element that we don't need (Init<G>) and copying that to a new type parameter F via conditional type inference with infer. Then, after the initial any, I am mapping the tuple type F to another tuple of the same length where we are pulling out the O part of every Gasket<I, O>. The Extract< , any> wrapper is just to make the compiler understand that the mapped tuple will be something spreadable via the variadic tuple spread operator.

Finally, AsChain<G> maps the tuple G to a new version of itself where each I in Gasket<I, O> is replaced with the corresponding entry from OGaskets<G>, and the T in the final Sink<T> is replaced with the last entry from OGaskets<G>.

type AsChain<G extends [...Gasket[], Sink]> = 
  { [K in keyof G]: G[K] extends Gasket<any, infer O> ?
    Gasket<OGaskets<G>[K], O> : Sink<Last<OGaskets<G>>> }

There you go.

---

Now Join has the parameter types from before. Since it seems you plan to return a Sink from the first element of G, we can write out that return type:

function Join<G extends [...Gasket[], Sink]>(
  ...arg: G extends AsChain<G> ? G : AsChain<G>
): G[0] extends Gasket<infer I, any> ? Sink<I> : G[0];

Note that it will be impossible for the compiler to understand that any function implementation will conform to that complicated generic conditional type. So you should probably not try. The easiest way to proceed is to make Join an overloaded function with a single call signature as above,

And then make the implementation non-generic:

function Join(...arg: [...Gasket[], Sink]): Gasket | Sink {
  return null!; // impl
}

It should be easier to implement, since the compiler will only check against the looser, non-generic type above. Or you can make the implementation even less strongly typed as function Join(...arg: any[]): any { /**/ }. Anything you need to do to stop the compiler warning is fair game as long as you are reasonably certain the implementation is safe.

---

So let's test it:

declare const strToNum: Gasket<string, number>;
declare const numToBool: Gasket<number, boolean>;
declare const boolSink: Sink<boolean>;

const stringSink = Join(strToNum, numToBool, boolSink);
//const stringSink: Sink<string>

Join(strToNum, strToNum, boolSink); // error!   Type 'string' is not assignable to type 'number'.

Join(strToNum, boolSink); // error!   Type 'boolean' is not assignable to type 'number'.

const anotherBoolSink = Join(boolSink); // okay
// const anotherBoolSink: Sink<boolean>

This all looks good. The compiler is happy with valid calls to Join, unhappy with invalid calls, and when it's unhappy it complains with reasonable error messages that point to the problem.

Playground link to code