Click here to Skip to main content
14,970,700 members
Articles / Programming Languages / Typescript
Article
Posted 4 May 2021

Stats

3K views
13 downloads
1 bookmarked

Non-structural Type Constraints

Rate me:
Please Sign up or sign in to vote.
5.00/5 (1 vote)
5 May 2021CPOL8 min read
Non-structural type constraints and type system tricks.
An overview of a solution to create a pseudo-type-graph that can be used to constrain type parameters and to optionally use type variance in searches of that pseudo-graph. Also covers some basic topics to help understand the solution and some of the tricks used in the solution.

Introduction

Sometimes there are relationships between types that aren't appropriate to model via inheritance. You might see these relationships expressed as ifs or switches on type comparisons. In many languages that's the best you can do. Their type systems aren't "rich" enough to express type-based logic outside of the run-time.

Typescript doesn't have this issue for a number of reasons but the biggest one is support of higher-order logic for types. This let's us solve the relationship issue with no run-time overhead at all! In fact, everything is eraseable so it won't even end up in the transpiled Javascript.

Image 1

Muhahahaha!

Features

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

 

*: The Typescript compiler may have something to say about the extremes of this but theoretically it's entirely arbitrary.

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.

Background

Even if you've used Typescript before this section might be a good refresher. There are a lot of details about the type system that are relevant to understanding the code and at worst a refresher never hurts!

At a glance, the Typescript type system looks something like the following with respect to the extends operator:

Image 2

The relationships are read as "undefined extends void" or equivalently "undefined is assignable to void." The different line-only arrows are for the cases where there is some notable exception. Keep in mind that while these may seem like inheritance relationships, that's not necessarily the case since Typescript uses a structural type system.

TypeScript
class A { A: string; } class B { A: string; }
var a: A extends B ? true : false; //true

The type of a is true despite the fact A and B are hierarchically unrelated. This is because they have the same structure.

A extends B ? T : F - equivalent to a ternary if with the condition being assignment compatibility from A to B. Furthermore in the true-branch, A's type has the type constraint of B. If A is a naked type parameter (just a lone type variable) and is a union, that union is distributed over the extends and the results are unioned together. For example:

TypeScript
class A { A: string; } class B extends A { B: string; } class C extends B { C: string; }
type example<T> = T extends B ? true : false;
var a: example<A|C>; //a has the type boolean (i.e. true | false)

The above happens because after distribution we get (A extends B ? true : false)|(C extends B ? true : false) which simplifies to false | true. Note that this doesn't happen in the case of:

TypeScript
var b: A|C extends B ? true : false; //b has the type false.

Since we no longer have a type parameter, no distribution occurs. Also consider the case of:

TypeScript
type example2<T> = [T] extends [B] ? true : false;
var c: example2<A|C>; //c has the type false.
var d: example2<C>; //d has the type true.

The type parameter is no longer naked since we are using it in a tuple type ([ ]), so no distribution occurs. If distribution did occur, c's type would be boolean like example a above.

Inferred Type Variables

Inferred type variables are temporary type variables similar to type parameters but bound to the scope of the true-branch and are automatically assigned by context. Their types are as narrow as can be safely inferred.

TypeScript
type example<T> = T extends infer U ? U : never;
var a: example<boolean>; //boolean

A more complicated example:

TypeScript
type example<T extends [...any]> = T extends [...infer _, infer A] ? A : T;
var a: example<[boolean, null, undefined, number]>; //number
var b: example<[void]>; //void
var c: example<[]>; //unknown

This uses inferred type variables to return the last type in a tuple. Notice that what we're essentially saying here is "can we successfully infer types for _ and A from T that make sense with the given signature?" It's important to understand that whatever is inferred will be as wide as necessary and as narrow as possible:

TypeScript
type example<T extends [...any]> = T extends (infer A)[] ? A : never;
var a: example<[string, number]>; //string|number

type example2<T extends [...any]> = T extends [...infer A] ? A : never;
var b: example2<[string, number]>; //[string, number]

The key difference between these is that (infer A)[] is a variable-length array signature and [...infer A] is a fixed-length array signature (i.e. a tuple). This shows how the resulting type information is widened into a union in the first instance since it is inferred from a variable-length array signature which has no concept of position for types like a tuple does.

Immediately Indexed Object Definitions (i.e. switch statements for types)

One limitation of extends is it doesn't cleanly allow lots of branching. We can get around this by using the fact that if you index an object definition, what you get back is the associated property's type which effectively turns the object definition into a switch statement:

TypeScript
type VarianceHandler<
    Links,
    Head extends HeadsOf<Links>,
    HeadVariance extends Variance> =
    {
        0: InvariantHead<Links, Head>,
        1: CovariantHead<Links, Head>,
        2: ContravariantHead<Links, Head>,
        3: BivariantHead<Links, Head>
    } [HeadVariance];

If we were just using extends this would look like:

TypeScript
type VarianceHandler<
    Links,
    Head extends HeadsOf<Links>,
    HeadVariance extends Variance> =
    HeadVariance extends 0 ?
        InvariantHead<Links, Head>
        : HeadVariance extends 1 ?
            CovariantHead<Links, Head>
            : HeadVariance extends 2 ?
                ContravariantHead<Links, Head>
                : HeadVariance extends 3 ?
                    BivariantHead<Links, Head>
                    : never;

Ugly, right? Consider an even more complex example:

TypeScript
type Choices = 0 | 1 | 2;
type obj<SomeType, SomeOtherType, Choice extends Choices> = 
{
    0: number,
    1: string,
    2: obj<SomeType, SomeOtherType, 1> | null
} [SomeType extends SomeOtherType ? Choice : 0];

Any type expression that evaluates to a legal index is allowed in the indexer. You can also recursively call a type as long as it can't infinitely recurse (you'll get either an error when using the type or on the recursive property). It's possible to do this with extends but it isn't pretty.

Using the code

These are the core type aliases the TypeLinker exposes:

TypeScript
type Link<Head, Tail>;
type Link_O2N<Head, Tails>;
type Link_M2N<Heads, Tails>;

const enum Variance { None = 0, Co = 1, Contra = 2, Bi = 3 }
type HeadsOf<Links>;
type TailsFrom<Links, Head, HeadVariance>;

The first three are for defining links. The O2N and M2N variants are convenience types for one-to-many and many-to-many mappings, respectively. There's nothing special that you couldn't do manually by defining the links explicitly using Link but it may save you quite a bit of typing.

HeadsOf, TailsFrom, and Variance are the meat and potatoes of the tool. HeadsOf returns a union of all head values from the set of links given. TailsFrom returns a union of all tail values from the set of links given that are associated with the given head value using the variance behavior specified (default is non-variant). Despite the link sets being more of a directed graph structure by nature, it may be easier to think of HeadsOf as returning the keys of the set and TailsFrom returning values associated with a given key. This is a very loose metaphor, however, since heads are not required to be unique like a key is commonly assumed to be.

TypeScript
//As long as the top-level of a set of links is a union or tuple,
//the links/data inside can be organized however you'd like. All of the
//O2N second parameter sets below are valid. Empty elements like in
//'notice' are discarded.
type map = {
    connection: [
        Link_O2N<'pass', 461 | 462>,
        Link_O2N<'nick', 431 | 432 | 433 | 436 | 437 | 484>,
        Link_O2N<'user', 461 | 462>,
        Link_O2N<'oper', [461 | 464 | 491, 381]>,
        Link_O2N<'mode', [461 | 502 | 501, 221]>,
        Link_O2N<'service', [461 | 462 | 432, 383 | 2 | 4]>,
        Link<'quit', never>,
    ],
    messaging: [
        Link_O2N<'privmsg', [[411, 412, 404, 413, 414, 407, 401], [301]]>,
        Link_O2N<'notice', [[411, 412, 404, 413, 414, 407, 401], []]>
    ]
}

//Showing what HeadsOf and TailsFrom return given the above
var headCheck: HeadsOf<map['messaging']>; //privmsg | notice
var tailCheck: TailsFrom<map['connection'], 'mode'>; //461 | 502 | 501 | 221

//Example of using HeadsOf and TailsFrom to constrain type parameters.
//By setting V equal to its constraint, you make this parameter optional which
//is demonstrated in the second e2 example below.
class example<CommandType extends keyof map> {
    send<
        K extends HeadsOf<map[CommandType]>,
        V extends TailsFrom<map[CommandType], K> = TailsFrom<map[CommandType], K>
    >(packet: object): V | null {
        return null;
    }
}

var e1: example<'connection'> = new example();
e1.send<'user', 461>({});
e1.send<'privmsg'>({}); //Error, does not satisfy constraint. There's no privmsg in connection.

var e2: example<'messaging'> = new example();
e2.send<'privmsg', 303>({}); //Error, does not satisfy constraint. There's no 303 for privmsg.

//This is like saying "I'll accept all the values associated with privmsg" instead of specifying
//a specific one like the first e1 example above.
e2.send<'privmsg'>({});

This example maps some response codes to their associated request type from the modern IRCv3 protocol. It demonstrates how type linking could be used to show proper response codes to be handled/expected for a given request despite there being no structural relationship between the request and response types. Given that the full protocol has dozens of request types and hundreds of reply/error types, would you prefer to have your IDE tell you what to expect or to consult an enormous documentation page?

For the next examples we'll be using a simple but nested linking. Heads and tails of links nested within links won't be caught in a HeadsOf or TailsFrom search of the outer link's set. To retrieve those you need to extract the nested links using a TailsFrom, then you can use HeadsOf and TailsFrom on the nested links.

TypeScript
type map2 = {
    'group': [
        Link_O2N<
            'id',
            Link_M2N<'requestType1' | 'requestType2', 'responseType1' | 'responseType2'>
            | Link<'requestType3', 'responseType3'>
        >
    ]
};

let nestedLinks: TailsFrom<map2['group'], 'id'>;
let headsOfNestedLinks: HeadsOf<nestedLinks>;
let tailsOfNestedLinks: TailsFrom<nestedLinks, headsOfNestedLinks>;

The following example shows how traversing each nested level of links needs a HeadsOf/TailsFrom combination. To make it visually obvious, the first level is traversed in the class's type parameters while the second is in the function's type parameters. Note that Group is just an object property, not part of the link traversal. You could get rid of it by not using an object to represent map2.

TypeScript
class Example1<
    Group extends keyof map2,
    Id extends HeadsOf<map2[Group]>,
    IdTails = TailsFrom<map2[Group], Id>
>
{
    send<Req extends HeadsOf<IdTails>, 
         Resp extends TailsFrom<IdTails, Req>
    >(packet: Req): Resp | null
    {
        return null;
    }
}

new Example1<'group','id'>().send('requestType3'); //return type is 'responseType3'

If we don't have any state to handle, it might be tempting to go for a more functional-style approach without instances.

TypeScript
class Example2
{
    static for<
        Group extends keyof map2,
        Id extends HeadsOf<map2[Group]>,
        IdTails = TailsFrom<map2[Group], Id>
    >() : Example2_Impl<IdTails>
    {
        return new Example2_Impl<IdTails>();
    }
}

class Example2_Impl<Tails> {
    send<Req extends HeadsOf<Tails>, Resp extends TailsFrom<Tails, Req>>(packet: Req): Resp | null
    {
        return null;
    }
}

Example2.for<'group','id'>().send('requestType1'); //return type is 'responseType1'|'responseType2'
Example2.for<'group', 'id'>().send('requestType3'); //return type is 'responseType3'

As you can see, this gets kind of ugly if we want to retain the separation of specifying the id and the request/response. Class type parameters are only associated with instances of the class, so if we don't want to specify all the parameters on the static for function, we need to make another class to capture the relevant details (IdTails) from the for call that need to be used to constrain the request/response.

It's not hard to imagine how ugly this can get if you need heavily nested linking. Thankfully, type parameters are capturable which means using a functional approach we can make Example2 much cleaner:

TypeScript
function using<Group extends keyof map2>() {
    return <Id extends HeadsOf<map2[Group]>>() =>
        (<IdTails = TailsFrom<map2[Group], Id>>() =>
            <Req extends HeadsOf<IdTails>, 
             Resp extends TailsFrom<IdTails, Req>
            >(packet: Req): Resp | null =>
                null           
        )();
};

let send = using<'group'>()<'id'>();
send('requestType3');

This approach lets us have total control over when and how type parameters are specified in a compact, flexible way. It also allows us to do something the OOP solution doesn't - have true intermediate values. Notice the lambda with IdTails as a type parameter is immediately invoked. This ensures the user will never be able to overwrite the IdTails value manually like they can in Example2. IdTails only exists as a capture for its inner returned lambdas like was originally intended.

Finally, I believe variance is easiest to show rather than explain. These are examples from my test file:

TypeScript
class A { A:string; }
class B extends A { B:string; }
class C extends B { C:string; }
class D { D:string; }

//All these maps are equivalent. This shows arbitrary nesting of groups doesn't
//matter due to flattening. Only nesting within links requires unique handling.
type TypeMaps = {
    tuple: [ Link<A, C>, Link<B, A>, Link<C, D>, Link<D, null>],
    union: Link<A, C> | Link<B, A> | Link<C, D> | Link<D, null>,
    nested: [ Link<A, C>, [[Link<B, A>] | Link<C, D>], [[[Link<D, null>]]]],
    default: [ Link<never, never> ]
}
type ActiveMap = TypeMaps['nested'];

//Covariant
var a: TailsFrom<ActiveMap, A, Variance.Co>; //A | C | D
var b: TailsFrom<ActiveMap, B, Variance.Co>; //A | D
var h: TailsFrom<ActiveMap, C, Variance.Co>; //D
var j: TailsFrom<ActiveMap, D, Variance.Co>; //null

//Contravariant
var c: TailsFrom<ActiveMap, A, Variance.Contra>; //C
var d: TailsFrom<ActiveMap, B, Variance.Contra>; //A | C
var i: TailsFrom<ActiveMap, C, Variance.Contra>; //A | C | D
var k: TailsFrom<ActiveMap, D, Variance.Contra>; //null

//Invariant
var e: TailsFrom<ActiveMap, A>; //C
var f: TailsFrom<ActiveMap, B>; //A
var g: TailsFrom<ActiveMap, C, Variance.None>; //D
var l: TailsFrom<ActiveMap, D, Variance.None>; //null

//Bivariant
var m: TailsFrom<ActiveMap, A, Variance.Bi>; //A | C | D
var n: TailsFrom<ActiveMap, B, Variance.Bi>; //A | C | D
var o: TailsFrom<ActiveMap, C, Variance.Bi>; //A | C | D
var p: TailsFrom<ActiveMap, D, Variance.Bi>; //null

//Multi-key
var q: TailsFrom<ActiveMap, A|D>; //C | null
var r: TailsFrom<ActiveMap, A|D, Variance.Co>; //A | C | D | null

It's also possible to search for multiple keys like in examples q and r. This is equivalent to searching for each key individually and unioning the results.

Points of Interest

The helper aliases below could be useful outside of this project with some adaptation. LinkBase is just a unique property added onto a Link tuple to distinguish it from normal tuples used to group and organize links. This ensures we don't lose the associative information (head, tail) by converting the tuple into a union accidentally or by flattening the link itself when flattening the overall structure.

TypeScript
type ToUnion<Set> =
    Set extends LinkBase ?
        Set
        : Set extends [...infer U] ?
            U[number]
            : Set;
type IsSet<T> = T extends [...any] ? true : false;
type IsUnion_Helper<T1, T2> =
    T1 extends any ?
        [T2] extends [T1] ?
            false
            : true
        : false;
type IsUnion<T> = IsUnion_Helper<T, T>;
type Flatten_Helper<Set> =
    Set extends LinkBase  ?
        Set
        : true extends IsSet<Set> | IsUnion<Set> ?
            Flatten<Set>
            : Set;
type Flatten<Set> =
    [Set] extends [never[]] ?
        never
        : Flatten_Helper<ToUnion<Set>>;

The bivariant solution used in this project is a boring union of the co- and contra- results so that the implementation doesn't break when using the "strictFuncTypes":true typescript compiler option. This option makes function signature assignability with respect to parameters behave like you'd probably expect - contravariantly. The default behavior is actually bivariant though. This means with "strictFuncTypes": false bivariance in our solution could be implemented like this:

TypeScript
//This works even if strictFuncTypes is true.
type BivariantHead<Links, Head extends HeadsOf<Links>> =
    CovariantHead<Links, Head> | ContravariantHead<Links, Head>;

//But this looks pretty cool.
type BivariantHead<Links, Head extends HeadsOf<Links>> =
    Head extends any ?
        Links extends any ?
            ((a:Links)=>void) extends ((a:Link<Head, infer Tail>)=>void) ?
                Tail
                : never
            : never
        : never;

Both work, and since these are all design-time computations efficiency doesn't really matter, but it is neat. Function signatures can also be used for decomposition similarly to the tuple decomposition example earlier when discussing inferred types.

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).

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Jon McKee
Software Developer
United States United States
Software engineer dedicated to constantly learning and improving with a focus on self-documenting code and informed design decisions. Interested in most everything.

Comments and Discussions

 
QuestionNeeds more clarity Pin
Qwertie4-Jul-21 13:39
MemberQwertie4-Jul-21 13:39 
Questionwhat are the practical usages of the techniques shown here ? Pin
BillWoodruff6-May-21 10:38
mveBillWoodruff6-May-21 10:38 
AnswerRe: what are the practical usages of the techniques shown here ? Pin
Jon McKee8-May-21 23:15
professionalJon McKee8-May-21 23:15 
GeneralRe: what are the practical usages of the techniques shown here ? Pin
mvonballmo29-May-21 7:34
Membermvonballmo29-May-21 7:34 
AnswerRe: what are the practical usages of the techniques shown here ? Pin
Jon McKee29-May-21 15:13
professionalJon McKee29-May-21 15:13 
GeneralMessage Closed Pin
5-May-21 0:17
MemberAman Rai 20215-May-21 0:17 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.