14,933,402 members
Articles / Programming Languages / Typescript
Article
Posted 4 May 2021

2.9K views
1 bookmarked

# Non-structural Type Constraints

Rate me:
5.00/5 (1 vote)
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 `if`s or `switch`es 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.

Muhahahaha!

## Features

• 1:1, 1:N, and M:N type parameter linking.
• In-/Non-, co-, contra-, and bi-variant 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.

## 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:

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<
{

If we were just using `extends` this would look like:

TypeScript
```type VarianceHandler<
: 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>;

const enum Variance { None = 0, Co = 1, Contra = 2, Bi = 3 }

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
type map = {
connection: [
Link_O2N<'nick', 431 | 432 | 433 | 436 | 437 | 484>,
Link_O2N<'oper', [461 | 464 | 491, 381]>,
Link_O2N<'mode', [461 | 502 | 501, 221]>,
Link_O2N<'service', [461 | 462 | 432, 383 | 2 | 4]>,
],
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 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<
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': [
'id',
Link_M2N<'requestType1' | 'requestType2', 'responseType1' | 'responseType2'>
>
]
};

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,
IdTails = TailsFrom<map2[Group], Id>
>
{
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,
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>() {
(<IdTails = TailsFrom<map2[Group], Id>>() =>
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 = {
}
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
: 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
: 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.

//But this looks pretty cool.
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.

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

## Share

 Software Developer 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.

 First Prev Next
 what are the practical usages of the techniques shown here ? BillWoodruff6-May-21 10:38 BillWoodruff 6-May-21 10:38
 I appreciate a lot of work has gone into this ! And, as a beginning student of TypeScript, I cannot evaluate your code. Consider adding some content for mere mortals ? «One day it will have to be officially admitted that what we have christened reality is an even greater illusion than the world of dreams.» Salvador Dali
 Re: what are the practical usages of the techniques shown here ? Jon McKee8-May-21 23:15 Jon McKee 8-May-21 23:15
 Re: what are the practical usages of the techniques shown here ? mvonballmo29-May-21 7:34 mvonballmo 29-May-21 7:34
 Re: what are the practical usages of the techniques shown here ? Jon McKee29-May-21 15:13 Jon McKee 29-May-21 15:13
 Message Closed 5-May-21 0:17 Aman Rai 2021 5-May-21 0:17
 Last Visit: 31-Dec-99 18:00     Last Update: 22-Jun-21 4:42 Refresh 1