Recursively-typed array with nth-element typing

[harrysolovay]

Search Terms

• recursive (tuple|array) of varying length
• differently-typed array elements
• tuple of (generic|unknown) size

Suggestion

Ability to recursively type the elements of varying-length arrays

Use Cases

I'm attempting to create a type for hypertext nodes. Consider the following representation of some HTML:

["div", {"id": "parent"},
  ["div", {"id": "first-child"}, "I'm the first child"],
  ["div", {"id": "second-child"}, "I'm the second child"]
]

This is similar to the arguments of React's createElement. While it's possible to type the arguments array of a function and account for rest spread type... this doesn't seem doable in a standalone array. Meanwhile, tuples must be of fixed length. One solution would be to define this hypertext within call expressions:

h("div", {id: "parent"},
  h("div", {id: "first-child"}, "I'm the first child"),
  h("div", {id: "second-child"}, "I'm the second child"),
)

However, this format is more bloated. It doesn't convey the most minimal format for the data. My sense is that I should––for the time being––make use of any[].

By the way, apologies if this is currently possible and I just did not find it! Looked for quite a while & no approach seemed to do the trick.

Examples

export type HypertextNodeStructure<T, P, C> = [T, P, ...C[]];
export interface HypertextNode
  extends HypertextNodeStructure<string, {[key: string]: any}, HypertextNode> {}

const hypertextNode: HypertextNode =
  ["div", {id: "parent"},
    ["div", {id: "first-child"}, "I'm the first child"],
    ["div", {id: "second-child"}, "I'm the second child"]
  ]

Checklist

My suggestion meets these guidelines:

• This wouldn't be a breaking change in existing TypeScript/JavaScript code
• This wouldn't change the runtime behavior of existing JavaScript code
• This could be implemented without emitting different JS based on the types of the expressions
• This isn't a runtime feature (e.g. library functionality, non-ECMAScript syntax with JavaScript output, etc.)
• This feature would agree with the rest of TypeScript's Design Goals.

[harrysolovay]

@manueliglesias & @mikeparisstuff –– tagging you two in this thread, incase you're interested in watching for the resolution 👍

[dragomirtitian]

@harrysolovay Not ideal, but this could be a workaround:

type Others = 2|3|4|5|6|7|8|9|10|12|13|14|15|16|17|18|19|20; // Up to reasonable number.
type HypertextNodeStructure<T> = unknown[] & {
  0: string,
  1: Record<string, any> 
} & Partial<Record<Others, T | string>>
interface HypertextNode extends  HypertextNodeStructure<HypertextNode>{}

let x: HypertextNode = ["div", { id: "" },
  ["div", {"id": "first-child"}, "I'm the first child"],
  ["div", {"id": "second-child"}, "I'm the second child"]
]

let d0 = x[0] // string
let d1 = x[1] // Record<string, any>
let d2 = x[2]  // string | HypertextNode | undefined

Play

[harrysolovay]

Thanks @dragomirtitian ... but in the case of long lists (1000+ windowed elements), this wouldn't be good :/

Any other idea?

[AnyhowStep]

interface HypertextNode extends Array<string|Record<string, unknown>|HypertextNode> {
    0 : string,
    1 : Record<string, unknown>
}

const node : HypertextNode = ["div", {id: "parent"},
    ["div", {id: "first-child"}, "I'm the first child"],
    ["div", {id: "second-child"}, "I'm the second child"]
];

Playground

[harrysolovay]

YESSS. That did the trick. Thank you @AnyhowStep !!!

[AnyhowStep]

Wait-

But my approach allows Record<string, unknown> for elements at index 2,3,4,etc. though.

Is that what you actually want?

---

@dragomirtitian 's approach is closer to what you want, even if there's a limit

---

How... Deep can these hierarchies get?

---

[Edit]
You should re-open the issue because I think it's a good feature request.
At least until someone has a workaround that is not too hacky, supports deeply nested tuples, supports arbitrarily long tuples, has the behaviour you want for rest params, etc.

[harrysolovay]

Good catch. It also allows string for those indices :/

Is it possible to give the right index signatures for 0 and 1? This might let us do the following:

type Base<T> = Array<T>;
export interface H extends Base<H> {
  0: string;
  1: Record<string, unknown>;
}

Currently it throws Property '1' of type 'Record<string, unknown>' is not assignable to numeric index type 'H'.ts(2412)

[dragomirtitian]

@harrysolovay The limitation here is that an index signature must be consistent with all defined properties, and there is no way to exclude a subset of properties from the index.

@weswigham has an interesting combo of PRs that address this negated types and Allow any key type as an index signature parameter type that might allow us to write something like this in the future:

export interface H {
  0: string;
  1: Record<string, unknown>;
  [index: not 0 & not 1 & number]: H
}

[harrysolovay]

@dragomirtitian that is fantastic! Would that work when extending Arrays? It'd be nice to see a shorthand for rest type as well. Something like this:

export interface H {
  0: string;
  1: Record<string, unknown>;
  [...indices: number[]]: H;
}

[fatcerberus]

In my experience a lot of people already tend to expect the index signature to act as a "rest type" and are surprised when it doesn't, so having that actually in the language would be great.

[weswigham]

FYI for everyone here: Tuples are pretty great - [string, Record<string, unknown>, ...number[]]

[AnyhowStep]

The recursive part is the only problem... =(

[dragomirtitian]

@weswigham Yeah, we know about those, the problem is the spread at the end can't be number[] it is the same type. So it would have to look something like:

type X = [string, Record<string, unknown>, ...X[]]

which is ilegal

[ahejlsberg]

You can manually unroll up to some maximum nesting depth, e.g.

type HypertextNode =
    [string, Record<string, unknown>, ...Array<string |
    [string, Record<string, unknown>, ...Array<string |
    [string, Record<string, unknown>, ...Array<string |
    [string, Record<string, unknown>, ...Array<string |
    [string, Record<string, unknown>, ...Array<string |
    [string, Record<string, unknown>, ...Array<string |
    [string, Record<string, unknown>, ...Array<string |
    [string, Record<string, unknown>, ...Array<string>]>]>]>]>]>]>]>];

Obviously has limitations and I'll readily admit it makes error messages look scary.

[harrysolovay]

Hi @ahejlsberg –– I'm a big fan of your team's work. Catering to as many use cases as does TypeScript seems difficult (to say the least). I believe this one is worth addressing. My sense is that there are two main reasons to do so:

1. This is the structure of both React's createElement and Stencil's h's arguments.
2. Spreading children does slightly reduce the overall size.

I'm curious if you see this typing as something that "should" be possible? And if so, do you see it making its way into TypeScript anytime soon?

[ahejlsberg]

@harrysolovay I agree it would be nice to support this somehow. The path of least resistance would probably be to permit

type HypertextTuple = [string, Record<string, unknown>, ...HypertextNode[]];
interface HypertextNode extends HypertextTuple {}

but this would require some non-trivial work to support extracting rest element types from "tuple-like" types (such as HypertextNode above).

[harrysolovay]

@ahejlsberg, thanks for the feedback :)

While typing unknown-length tuples would be a cool feature, I doubt it's urgent; please let me know if I should close this issue or leave open.

One last (semi-related) note: it could be worthwhile to revisit the self-referencing type discussion, as this would allow for a more intuitive end state for this type:

type HypertextNode = [string, Record<string, unknown>, ...HypertextNode[]];

Using an interface for self-referencing gets the job done, but absolutely feels bloated.

[ahejlsberg]

Using an interface for self-referencing gets the job done, but absolutely feels bloated.

I share the sentiment, but there are much deeper architectural assumptions that would have to be revisited in order to support generalized recursive type aliases.

[weswigham]

I share the sentiment, but there are much deeper architectural assumptions that would have to be revisited in order to support generalized recursive type aliases.

🤔

So as it happens, we already broke those assumptions when we added substitutions in conditionals (which are already types-whose-flags-we-dont-know-yet - the substitute could be never, unknown, a union, an intersection, a type variable... we just don't know until we unwrap it). It's just a matter of picking up the pieces and fixing all the holes. My quick experiment of deferred substitutions (creating a substitution whose substitute is not eagerly created) is broadly successful in enabling this usecase, but quite a bit is broken when enabling it generally for all type alias references because of the places we still don't handle a substitution correctly (For example, in inference we unwrap substitutes last, which means inference priorities can get messed up, compared to the eager insertions of today). The core change isn't even that large.

I think we already started down the path towards having the tools in place to do this, we just haven't acknowledged it yet.

[fatcerberus]

type Rec = [string, Rec?]

Being able to do stuff like this would make representing inductive types in TypeScript so much more ergonomic. Right now for an inductive ADT you have to do this:

type Node =
	| { type: 'identifier', name: string }
	| { type: 'assignment', lhs: Node, rhs: Node }
	| { type: 'call', target: Node, args: Node[] };

Which is pretty awkward to construct on-demand (object literals aren't exactly compact--especially if you're nesting them) and I really want to be able to do it like this instead:

type Node =
	| [ 'identifier', string ]
	| [ 'assignment', Node, Node ]
	| [ 'call', Node, Node[] ];

[ahejlsberg]

@weswigham Right now substitution types are a narrow mechanism we use to substitute intersection types in place of type parameters. There's quite a bit of ground between that and a general mechanism for deferred type aliases, particularly as type aliases are currently always eagerly resolved. Ultimately I think it means getting rid of the flags property on types and turning into a deferred resolution, plus some soul searching on what type ids mean since we'd now have intermediaries with their own ids. And some further soul searching on the difference between type aliases and type references. That's what I meant when I said there are much deeper architectural assumptions that would have to be revisited in order to support generalized recursive type aliases.

[weswigham]

Right now substitution types are a narrow mechanism we use to substitute intersection types in place of type parameters.

Aside: If we're actually assuming the substitute is an intersection anywhere, we're mistaken - a substitute of T & U and easily become T & (A | B) which is T & A | T & B. Substitutes are also hiding our already extant ability to have unsimplified unions-within-unions in this way. I think the original intent is maybe slightly different from what they're actually capable of doing today? In any case, I'm only using them as a template since almost every problem one could have with a deferred type alias, we already have with substitutions and are attempting to deal with, so utilizing that seems like a great way to cut down on work.

Anyways, I don't think type IDs meaningfully change - they're just a serializable proxy for a pointer to a (type) object. A | B | C's composite key is still a list of it's component keys, even if any or all of them are substitutes (as it is today).

On type alias vs "type reference types" - the later are, imo, just unfortunately named. They're really just instantiated/declared object types whose members are resolved late... They're better than aliases or deferred substitutes because you can assume they're object types without resolving them (since you looked up that info from the target symbol). I think just renaming them to something like "InstantiatedObjectType" or "LazyObjectType" would be ok.

And while in my super simple example code linked above, I always make a deferred substitute, the cost and potential observable change in behavior can be significantly lowered by only bothering to make one when a circular ref is detected (so if push type would fail (peek type?) return a deferral which doesn't peek (this way if we still need to inspect the type earlier we can still error)).

[ahejlsberg]

I've been giving the issue some thought. First I think it is important to identify the exact problem we're trying to solve: Allowing type aliases to be circularly referenced as type arguments in type references. There may well be other constructs in which we could consider permitting circularities, but I specifically want to exclude those here. I think it is key that we understand and scope the problem. If history is any guide we'll otherwise find ourselves chasing infinite recursion stack overflows all over the place.

Currently we eagerly resolve type arguments in type references. This has the advantage type references with identical type arguments end up referencing the same type identity. Technically it wouldn't be that hard to defer resolution of type arguments in type references: Every reference to the typeArguments property would instead become a call to a function that lazily resolves the type arguments. However, we would then have to give every type reference a unique type identity, and two Array<string> references would end up having distinct type objects (just like two distinct { foo: string } object type literals have distinct type objects). The additional type identities would definitely create more work (i.e. more structural type comparisons), though we already have logic in place that efficiently relates two type references to the same generic type and that might actually catch the majority of it.

Regarding using substitution types for circular type aliases, my biggest worry is they give you the ability to introduce circularities anywhere, e.g. in union types, intersection types, indexed access types, etc. We really don't want that. Also, creating them based on peeking the type resolution stack makes it very hard to reason about when they get created.

[weswigham]

Actually, the eager resolution of type arguments isn't the issue at all (speaking firsthand here), it's the eager lookup of the declared type of the alias that's the issue, since for aliases today we're forced to resolve it early. (Please note, in type Rec = [string, Rec?], there is no type reference with type arguments (there's a tuple type, which is distinct)) That's how references to aliases are currently different than other type references - type references don't attempt to resolve their declared type until you query their structure.

While peeking the resolution stack is admittedly opaque, I do think it reduces the potential change surface area significantly and also keeps the new type identity count very low. The other option, imo, would be during resolution, saying that a reference to a lexically containing type alias always produces a deferred type, but doing that lexicially is going to heavily affect what works as an alias vs inline (and potentially have visible change to types which are today allowed, like recurring object types), which is much more opaque, imo.

[ahejlsberg]

Let me explain what I mean. In

type Rec = [string, Rec?];

we do indeed have a type reference: [string, Rec?] is simply syntax for a type reference __Txxx__<string, Rec> where __Txxx__ is the synthetic generic interface type we generate for the tuple. So, it's resolved in the same manner as for example Array<Rec> would be resolved. What I'm proposing is that we look at lazily resolving the type arguments in these type references. Specifically, instead of eagerly calling getTypeFromTypeNode for each type argument, wait until someone calls getTypeArguments for the type reference and lazily defer the calls to getTypeFromTypeNode until that point.

Nothing would change with respect to type aliases. I'm specifically not proposing we defer resolution of those (because they can be anything and we don't want all the potential circularities and stack overflows that comes along with that).

[weswigham]

@ahejlsberg I don't think doing it at argument positions only makes much sense. It'd be amazingly inconsistent, since you could just defer a thing (anywhere) by wrapping it in a

type Defer<T> = T;

which is silly, imo.

[ahejlsberg]

@weswigham @RyanCavanaugh See #33050 for a proof of concept implementation of what I discussed above.

[harrysolovay]

@ahejlsberg @dragomirtitian @AnyhowStep –– I came up with a solution! And I'd love to hear your thoughts on it (do you foresee situations where it might get me into trouble?). Any feedback would be greatly appreciated:

class StencilHypertextNode extends Array<
  string | Record<string, unknown> | null | StencilHypertextNode
> {
  constructor(
    tag: string,
    props: Record<string, unknown>,
    ...args: StencilHypertextNode[]
  ) {
    super(...arguments);
    this[0] = tag;
    this[1] = props;

    for (const i in args) {
      this[i] = args[i];
    }
  }
}

[AnyhowStep]

You can't use tuple literals with that, though.

const x2 : StencilHypertextNode = [
    null, //Expected error
    {},
    ["", {}]
]

[harrysolovay]

@AnyhowStep true :/ that's too bad. Especially considering the following:

function acceptHypertextNode(h: StencilHypertextNode) {
  console.log(h);
}

const badInput = [null, {}, ["", {}]];

acceptHypertextNode(badInput); // should be a type-error... but there is none

... I'm surprised there doesn't exist a way to define this type of data structure. Any other workaround ideas?

[ahejlsberg]

Recursive type references for array and tuple types are now implemented in #33050.