Download TypeLinker.zip - 2.2 KB

Introduction

Sometimes there are relationships between types that aren't appropriate to model via inheritance. The types might be related in the domain of the problem only and not by structure. A common example of this is HTTP requests and responses. They don't intrinsicly have similar state or behavior but they are nonetheless related within the domain of HTTP and whatever protocol may be used on top of HTTP such as IRCv3 or a web API.

Generally speaking, what the TypeLinker allows you to do is specify these non-structural relationships in a clean, concise way which allows those relationships to reside in a single location instead of scattered across your project within complex type constraints, method overloads, duplicate functions, etc.

We can use this information to provide type safety in a way that incurs no runtime overhead, requires no type-based reflection boilerplate, and is completely eraseable so it won't add size or complexity to the transpiled Javascript.

Muhahahaha!

Features

1:1, 1:N, and M:N type linking.
In-, co-, contra-, and bi-variant head searches.
Multi-head searches.
Supports arbitrary nesting depth of links and link groups (both union- and tuple-based).

Terms

Head: a head is a non-unique value associated with one or more tail values. The head can be used to retrieve its tail values.
Tail: a tail is a non-unique value associated with one or more head values. The tail has no knowledge of its head.
- Example: x -> y -> z. In this example y is both the tail of x and the head of z.
- These terms are basically the opposite of their respective definitions in graph theory. The way they're utilized here more closely represents their colloquial meaning in computer science (think linked lists) which I feel is easier to understand as a software engineer.
Link: a link is a 1:1, directed association from a head to a tail.
S-relationship: structural relationship (i.e. inheritance-style/is-a relationships).
NS-relationship: non-structural relationship. These are usually domain-specific such as request- and response-type relationships for messaging.

The Problem

As a quick refresher, Typescript's type system is structural in nature. Even if there is no explicit inheritance defined between two types, if one type's properties are a subset (proper or not) of another's properties then they are considered related.

//A and B are effectively the same type
class A { A: string; }
class B { A: string; }

//D extends C
class C { A: number; }
class D { B: string; A: number; }

class E { E: boolean; }

This begs the question: how would we model non-structural relationships (referred to as NS-relationships from here on) such as R, S, and T if there exists no property that uniquely defines the relationship?

Well, one way we could do this would be to create a unique, surrogate property that represents the relationship within the types. Let's look at how we might do that with R and S:

class A 
{ 
    A: string; 
    R_e56bf097_aa36_4eb7_a0b8_905817b00554: true;
    S_7ad50511_d9ac_4ca7_a7e0_f6bca8fdcdf0: true; 
} 
class B extends A {}
class C { A: number; S_7ad50511_d9ac_4ca7_a7e0_f6bca8fdcdf0: true; } 
class D { B: string; A: number; R_e56bf097_aa36_4eb7_a0b8_905817b00554: true;}

Cleanliness aside, this solution has a couple problems:

Due to the relationship S, we can no longer use an inheritance relationship between C and D if we assume S doesn't transitively apply to D. We could set S_7ad50511_d9ac_4ca7_a7e0_f6bca8fdcdf0 to false explicitly inside D and subsequently check for that but now all subclasses will need to know about this special relationship. Not a great idea.
There's no way to implement directionality without muddying the type structure and compounding the boilerplate we would need to write to check for these relationships.
There's no way to create a NS-relationship between C and D without heavy restrictions. We would need to disambiguate between a genuine NS-relationship between C and D versus D inheriting a NS-relationship from C. This can only be accomplished cleanly by not allowing one of those situations.
We're reducing the cohesion of the types. They now have a property that has no usage within class instances and doesn't represent any data of the static type. We're cramming NS-relationship data where it doesn't belong.
Related to the last point, if a future engineer decides to remove this property during some refactoring since it appears unused, the code could break in very non-obvious ways. For example, if the property is only checked using the extends conditional then removal would not cause any errors or warnings. The extends would simply resolve to the false-branch instead of the true-branch.

The core issue here is really a conceptual one. We're overloading the concept of a S-relationship to include NS-relationships. We're forcing something inherently non-structural into a structural paradigm. We've got a circular hole and we're trying to shove a square peg into it.

So let's think about the problem a bit more abstractly and get to the root of what we're actually trying to do. Looking at the types from a type-domain perspective, we get something that looks like this:

These are all of the relationships between the two type domains - head (A, B, E) and tail (D, C). The domains can represent anything that uses a type - generic type parameter, variable, etc. We can infer some general statements from this picture and our problem description already:

This is not a function in the mathematic sense since all elements in a domain can map to multiple elements in the other.
All elements in a domain map to at least one element in the other.
There is a directionality to the relationships between domain elements. The direction goes from head-domain to tail-domain.

Now let's analyze existing techniques for mapping types and see whether they can achieve the properties above. First, we'll look at basic functions.

type example1 = (x: A | B | E) => D | C;

type example2 = (x: A | B | E, y: D | C) => void;

This doesn't work because it allows E => D and (E, D) => void which are invalid relationships since they don't appear in the previous graphic.

type example1 = (x: A | B) => D | C;
type example1_2 = (x: E) => C;

type example2 = (x: A | B, y: D | C) => void;
type example2_2 = (x: E, y: C) => void;

This works but requires separate function signatures. It could create code duplication depending on the context. It's only appropriate if different NS-relationships also imply different behaviors. So then what about using generics?

type example1 = 
    <
        T extends A | B | E, 
        U extends (T extends A | B ? D | C : C)
    >(x: T) => U;

type example2 = 
    <
        T extends A | B | E, 
        U extends (T extends A | B ? D | C : C)
    >(x: T, y: U) => void;

This works! It has some rather hefty downsides though. The most notable being that the constraints needs to be carefully maintained across all use-cases as new NS-relationships are added, removed, or modified. Complexity can also start to spiral out of control inside the U constraint.

We've now identified two primary issues we need to solve. We need to store the NS-relationships in a way that is easily maintainable and extendable, and we need a generic constraint solution that ensures the NS-relationships are respected.

Important Note: While functions are used as examples throughout most of the article, the general usage of NS-relationships applies between any type use-cases - functions, classes, and even variables - though its usefulness in some cases hasn't been properly explored yet.

The Solution

The initial solution is to store the NS-relationship data where it belongs - somewhere not inside the types. We'll create a table indexed by the NS-relationship's identifier where the value is a tuple of tuples of the related types.

type ns_relationships = {
    'R': [[A,D], [B,D]],
    'S': [[A,C], [B,C]],
    'T': [[E,C]]
};

We're done now with the NS-relationship storage, right? Well, yes and no. We've solved all the previously mentioned storage problems listed in The Problem but we've introduced a few more in doing so:

Instead of just a property, we now have a more complex object we have to index and extract information from to determine whether a NS-relationship exists for a given type.
Not really a problem per se, but it would be nice if we could treat NS-relationships as an all-encompassing "bag" of relationships similar to how the type system treats normal S-relationships.

Issue #2 is solved easily enough. We can collapse the object into just a tuple of all the NS-relationships.

type ns_relationships = [[A,D], [B,D], [A,C], [B,C], [E,C]];

The identifiers such as R or S we give to a NS-relationship don't really provide any useful functionality unless we want to explicitly include or ignore certain NS-relationships. It's mostly a documentation feature. It would therefore be nice if we could still arbitrarily group NS-relationships together to identify them without losing the ability to still treat them as one big bag of NS-relationships.

type ns_relationships = [
    [[A,D], [B,D]], //R
    [[A,C], [B,C]], //S
    [E,C]           //T
];

This cleanly accomplishes our goal but we now have to support arbitrary nesting of tuples. So we've solved issue #2 while swapping our original issue #1 with a new "complex tuple" issue. However, this new tuple issue is much easier to solve; we can flatten the tuple when we want to use it.

//Supporting type aliases not included for brevity.
//They do what it says on the tin:
// ToUnion: returns a union given a tuple or union.
// IsTuple: returns true given a tuple.
// IsUnion: returns true given a union.
type Flatten<Set> =
    [Set] extends [never[]] ?           //if the set is empty
        never                           //then ignore it
        : Flatten_Helper<ToUnion<Set>>; //else convert to union and call helper

type Flatten_Helper<Set> =
    Set extends LinkBase  ?             //foreach union item, if this is a base-case set
        Set                             //then we can't break it down anymore, return it
        : true extends IsTuple<Set> | IsUnion<Set> ? //else if it's a union or tuple
            Flatten<Set>                             //then flatten it
            : Set;                                   //else return it

This is a similar process to how you would flatten a nested array. Two parts require specific mention: LinkBase and the final Set return of Flatten_Helper. One could argue that the final Set return should instead be never since if an item reaches that branch it is neither a base-case, tuple, or union, so therefore shouldn't even be in the original set. This is precisely why it's left in though - to not ignore an improperly formed set and instead let it propogate so that the developer can identify the error. LinkBase is a simple object with a single property that provides an identity to our base-case tuples to distinguish them from normal tuples used for grouping. This is to prevent Flatten from flattening our NS-relationship tuples into individual elements.

type LinkBase = { _isLink_2723ae78_ad67_11eb_8529_0242ac130003: true };

//Just a tuple with the LinkBase property mixed in.
type Link<T1, T2> = [T1, T2] & LinkBase;

type ns_relationships = [
    [Link<A,D>, Link<B,D>], //R
    [Link<A,C>, Link<B,C>], //S
    Link<E,C> //T
];

type result = Flatten<ns_relationships>;
//result: Link<A,D> | Link<B,D> | Link<A,C> | Link<B,C> | Link<E,C>
//result without using LinkBase would be: A | D | B | C | E  <- this is why LinkBase is needed.

Unions are easier to deal with when checking for existence of an element which is why we don't convert the result back into a tuple. We can now check whether a link is valid:

//Checks whether a given link exists in ns_relationships
type exists<T extends LinkBase> = T extends Flatten<ns_relationships> ? true : false;

The final step to solve issue #1 expands on this idea to check whether a single type, not a link, has associations within the set of NS-relationships. Since we already have the ability to flatten our set down to a set of links, this is fairly straightforward.

type heads = Flatten<ns_relationships> extends Link<infer Head, any> ? Head : never;
type exists<T> = T extends heads ? true : false;

Now all our listed issues are solved. We just need to define the last meaningful operation - retrieving tails associated with a head. This will allow us to ensure that the NS-relationships are respected. We'll make this an invariant association by default.

type tailsOf<T extends heads> = 
    Flatten<ns_relationships> extends infer R ?
        R extends Link<T, infer Tail> ? //infer Tails associated with T or its derivatives,
                                        //also filters R down to these links which we use below.
            Link<T, Tail> extends R ? //filter out Tails associated with derivatives
                Tail                  //return Tails related to exactly T
                : never
            : never
        : never;

Now we have both a maintainable, extendable storage solution and a generic constraint solution for ensuring the NS-relationships are respected. This is the basic idea behind the TypeLinker which expands on this naive solution to handle edge/error cases, allow associations of any variance, and generally be a bit more flexible in its usage such as allowing multi-head searches.

For an example of error cases, consider that never doesn't conceptually make sense as a link head. never is a type that should never "exist" therefore is generally indicative of an error. Since type aliases like HeadsOf and TailsOf cannot reject themselves after accepting parameters and our parameters are complex enough that we would have to effectively process them using the type alias to generate meaningful constraints, we can use this property to resolve type aliases with invalid parameter input to never. Since no type can extend or be assigned to never except never, this causes the rejection to occur in the context of where the invalid input originated. By rendering that origin unusable we call attention to it indicating something is wrong.

type Map = unknown;

//HeadsOf can't reject all possible invalid inputs like unknown, never, [], void, 
//null, undefined, etc with just a constraint on its type parameter.
declare const example: <T extends HeadsOf<Map>, U extends TailsOf<Map, T>>(x: T) => U;

//So instead we resolve it to never which makes example unusable until the invalid input is fixed.
example(1); //error; example is of type <never, never>(x: never)=>never

How to use it

Now that we understand the conceptual problem and how its issues are handled in our solution, let's explore how to use our solution to solve practical problems. But first, let's quickly go back and solve our initial problem statement:

//S-relationships
class A { A: string; } 
class B { A: string; }
class C { A: number; } 
class D { B: string; A: number; }
class E { E: boolean; }

//NS-relationships
//R+S: A | B -> D | C
//T: E -> C

//M2N is a convenience alias that performs the cartesian product of the arguments.
type Map = [ Link_M2N<A | B, D | C>, Link<E, C> ];

type example1 =
    <
        T extends HeadsOf<Map>, 
        U extends TailsOf<Map, T>
    >(x:T) => U;

type example2 =
    < 
        T extends HeadsOf<Map>, 
        U extends TailsOf<Map, T>
    >(x:T, y:U) => void;

declare const ex1: example1;
ex1(new A()); //A => D | C
ex1(new B()); //B => D | C

declare const ex2: example2;
ex2(new E()); //E => C

We've successfully mapped the relationships without duplicating code, lots of overload signatures, or allowing invalid type combinations. The two primary TypeLinker type aliases used above are:

HeadsOf<map>: given a map, returns a union of all heads of links within the map.

TailsOf<map, head, variance?>: given a map and a head, returns a union of all tails of links with the given head within the map. An optional parameter variance allows specifying which links should be considered based on the variance between the given head and the heads of links within the map. The default is none/invariant but covariant, contravariant, and bivariant are also supported.

Now that we've covered the basics, let's move on to more concrete scenarios.

Scenario #1:

We have an application that makes API calls. We want a request/response solution that:

Ensures proper request types are used.
Ensures a proper validator of the response types is supplied given a specific request type.
Is a single point of entry and exit for these calls.
Doesn't need modification when additional request and/or response objects are added.
Provides version consistency for the API calls.

Shared Solution Data:

//version 1
class WhoIsRequest extends Request { user: string }
interface InvalidRequestResponse { responseType: 1 }
interface UserInfoResponse { responseType: 2 }

//version 2
class WhoAreRequest extends Request { users: string[] }
interface UsersInfoResponse { responseType: 3 }

//validators
function validateWhoIs(resp: any): resp is InvalidRequestResponse | UserInfoResponse {
    return ('responseType' in resp && (resp.responseType == 1 || resp.responseType == 2));
}

function validateWhoAre(resp: any): resp is InvalidRequestResponse | UsersInfoResponse {
    return ('responseType' in resp && (resp.responseType == 1 || resp.responseType == 3));
}

Solution #1:

This solution uses traditional hard-coding of the NS-relationships.

async function whoIsMessage(
    req: WhoIsRequest, 
    isValidResponse: (resp:any) => resp is InvalidRequestResponse | UserInfoResponse
): InvalidRequestResponse | UserInfoResponse {
    let response = await fetch(req as Request).then(resp => resp.json());
    if (isValidResponse(response))
        return response;
    throw new Error("Invalid response.");
}

async function whoAreMessage(
    req: WhoAreRequest, 
    isValidResponse: (resp:any) => resp is InvalidRequestResponse | UsersInfoResponse
): InvalidRequestResponse | UsersInfoResponse {
    let response = await fetch(req as Request).then(resp => resp.json());
    if (isValidResponse(response))
        return response;
    throw new Error("Invalid response.");
}

let success1 = await whoIsMessage(new WhoIsRequest('https://someapi'), validateWhoIs);
let success2 = await whoAreMessage(new WhoAreRequest('https://someapi'), validateWhoAre);

There are a couple drawbacks to this approach:

Changing relationships requires manually altering the affected functions.
Adding a relationship requires adding another function.
The code inside each function is duplicated.

The issues are the same type of issues we identified earlier in the section The Problem.

Solution #2:

This solution uses the TypeLinker to express the NS-relationships using a generic function.

type SomeApiMapping = {
    v1: Link_O2N<WhoIsRequest, InvalidRequestResponse | UserInfoResponse>,
    v2: Link_O2N<WhoAreRequest, InvalidRequestResponse | UsersInfoResponse>
};

async function message<
    Map extends keyof SomeApiMapping = never,
    T extends HeadsOf<SomeApiMapping[Map]> = HeadsOf<SomeApiMapping[Map]>,
    U extends TailsOf<SomeApiMapping[Map], T> = TailsOf<SomeApiMapping[Map], T>
>(req: T, isValidResponse: (resp: any) => resp is U): Promise<U> {
    let response = await fetch(req as Request).then(resp => resp.json());
    if (isValidResponse(response))
        return response;
    throw new Error("Invalid response.");
}

let success1 = await message<'v1'>(new WhoIsRequest('https://someapi'), validateWhoIs);
//Error, incorrect request type
let error1 = await message<'v1'>(new WhoAreRequest('https://someapi'), validateWhoIs);

let success2 = await message<'v2'>(new WhoAreRequest('https://someapi'), validateWhoAre);
//Error, incorrect validator
let error2 = await message<'v2'>(new WhoAreRequest('https://someapi'), validateWhoIs);

At a glance we can tell that this suffers from none of the drawbacks of solution #1. The main downside is it's more complex. Another minor downside is someone could explicitly set T and U which could overly narrow the types such as setting U to UserInfoResponse which would then lose the InvalidRequestResponse type. Depending on the intent and the specific circumstances, this may or may not be desirable.

To fix this if needed, another way to structure message is to create an inner captured type parameter context for T and U to ensure that they can only be defined by Map.

function message_alt<Map extends keyof SomeApiMapping = never>() {
    return (
        <
            T extends HeadsOf<SomeApiMapping[Map]>,
            U extends TailsOf<SomeApiMapping[Map], T>
        >() => {
            return (
                async (
                    req: T,
                    isValidResponse: (resp: any) => resp is U
                ): Promise<U> => {
                    let response = await fetch(req as Request).then(resp => resp.json());
                    if (isValidResponse(response))
                        return response;
                    throw new Error("Invalid response.");
                }
            );
        }
    )(); //Execute T and U's lambda, the key point that makes this all work.
};

let attempt3 = await message_alt<'v1'>()(new WhoIsRequest('https://someapi'), validateWhoIs);

//This approach also lets you create a re-usable message_alt pre-bound with Map, T, and U
//which can be useful in some circumstances.

let v2Message = message_alt<'v2'>();
let success4 = await v2Message(new WhoAreRequest('https://someapi'), validateWhoAre);
let success5 = await v2Message(new WhoAreRequest('https://backup.someapi'), validateWhoAre);

Conclusion:

For this scenario, using the TypeLinker allows us to create a solution with no duplicated code that's easier to maintain, extend, and is more concisely self-documenting. The only cost we incur is an increase in complexity of the implementation. The usage remains the same though.

Scenario #2:

We want to make a generic data structure domain-aware so it only allows legitimate values. Specifically, we want a dictionary-like data structure that only allows certain types of key/value pairs.

Solution #1:

//Valid type relationships:
// A->C, B->D, E->F

class DADictionary
{
    private dictionary: any[] = [];

    add(key: E, val: F): void;
    add(key: B, val: D): void;
    add(key: A, val: C): void;
    add(key: unknown, val: unknown): void {
        this.dictionary.push([key, val]);
    };

    get(key: E): F | undefined;
    get(key: B): D | undefined;
    get(key: A): C | undefined;
    get(key: unknown): unknown | undefined {
        return this.dictionary.find(tuple => tuple[0] === key)?.[1];
    }
};

Implementation aside, the main drawback to this approach is you will have to maintain the overload signatures on every domain-aware data structure individually. With a static domain of NS-relationships this may not be an issue but if relationships are modified, added, or removed every affected overload signature across the entire project will need to reflect those changes.

Solution #2:

//Valid type relationships:
// A->C, B->D, E->F

type DictMap = [ Link<A, C>, Link<B, D>, Link<E, F> ];

class DADictionary<DictMap>
{
    private dictionary: any[] = [];

    add<
        Key extends HeadsOf<DictMap>,
        Value extends TailsOf<DictMap, Key>
    >(key: Key, val: Value): void {
        this.dictionary.push([key, val]);
    };

    get<
        Key extends HeadsOf<DictMap>,
        Value extends TailsOf<DictMap, Key>
    >(key: Key): Value | undefined {
        return this.dictionary.find(tuple => tuple[0] === key)?.[1];
    }
};

This solution, however, can be maintained entirely through the DictMap type alias. If this map is used for other domain-aware data structures, they will also automatically reflect any changes made to the map.

Conclusion:

The TypeLinker here allows us to avoid duplicating NS-relationships between types across method overloads. It provides a single point of reference for these relationships which again makes them easier to maintain, extend, and document.

Additional Info

When dealing with generics, sometimes it may be desirable to prevent type inference from occuring. For example, if you have a complex map and want the user to be explicit about the specific NS-relationship they want. This can be accomplished using the type alias NoInfer:

type NoInfer<T> = [T][T extends any ? 0 : never];

type Map = [ Link<string, number> ];

declare function example<
    T extends HeadsOf<Map> = never, 
    U extends TailsOf<Map, T> = TailsOf<Map, T>
>(x: NoInfer<T>, y: U): void;

example('x' as string, 1); //Error due to NoInfer preventing T = never from being overwritten.
example<string, number>('x', 1); //Works correctly.

The optional variance parameter of TailsOf also let's you better model NS-relationships that compound based on the S-relationships between heads. For example:

//Requests
class MessageRequest { requestId: number; }
class PingRequest extends MessageRequest { requestId: 1; }
class PrivmsgRequest extends MessageRequest { requestId: 2; user: string; msg: string; }

//Responses
class InvalidRequestResponse { responseId: 0; }
class PongResponse { responseId: 1; }
class MsgReceivedResponse { responseId: 2; }

type Map = [
    Link<MessageRequest, InvalidRequestResponse>,
    Link<PingRequest, PongResponse>,
    Link<PrivmsgRequest, MsgReceivedResponse>
];

//PongResponse
let pingOnlyResponses: TailsOf<Map, PingRequest>;
 
//PongResponse | InvalidRequestResponse
let allPingResponses: TailsOf<Map, PingRequest, Variance.Contra>;

//MsgReceivedResponse | PongResponse | InvalidRequestResponse
let allResponses: TailsOf<Map, MessageRequest, Variance.Co>;

This makes it easy to model these situations instead of needing to explicitly specify all NS-relationships for each head. Here with allPingResponses it lets PingRequest inherit the NS-relationships of its ancestors resulting in the inclusion of the InvalidRequestResponse type.

Thanks for reading!

History

5/5/21: Initial release.

5/5/21: Fixes to some of the example code; updated source code with a fix for bivariance sometimes not fully resolving during static analysis (see comment in TypeLinker.ts).

9/2/21: Complete rewrite of the article. The original article focused too much on the technical information and fell short in explaining what the linker does or why it's useful in a more conceptual sense. Technical type system information has been moved to Type System Features while this article was rewritten to include more conceptual information and a rework of the technical description to hopefully be less confusing.

This also includes an update to the TypeLinker code to provide more consistent handling of invalid input.

HeadsOf resolves to never when [], void, null, undefined, or never are used as a map.
TailsOf resolves to never when [], void, null, undefined, or never are used as a map.
never is invalid as a link head.
[], void, null, and undefined are valid link elements.

Non-structural Type Constraints