Better support for typing tree traversals

[harrysolovay]

Search Terms

pipe, generic, function, return, type, into, arguments, self, mutative, visitor, tree, traversal

Suggestion

In the description below, this is the Visitor type to which I refer:

interface Visitor<
  PreNodeIn,
  PreNodeOut,
  PostNodeIn,
  PostNodeOut,
> {
  pre: (node: PreNodeIn) => PreNodeOut;
  post: (node: PostNodeIn) => PostNodeOut;
}

It doesn't seem that many (or really any) utility types exist for easily writing typed, (potentially-mutative) traversal of objects whose types are known. A visitor's pre could mutate a node, which could be later encountered by the visitor's post. Multiple visitors results in another type-safety problem: the order in which visitors mutate a given node.

To start out with, the PreNodeIn should probably be a union of all nodes of the given object. To get this type, we can do something along the following lines, passing the given object as Root:

type NodeOf<Root> = Root extends object
  ? ({[K in keyof Root]: NodeOf<Root[K]>}[keyof Root] | Root)
  : Root;

PostNodeIn, on the other hand, needs to account for visitors' pre and should therefore be a union of PreNodeIn and PreNodeOut.

I'm not sure if this would be possible... but the given utility should also account for the order in which visitors are to be executed. As the pre and post visitors––amongst themselves––could fire off sequentially to alter the same node (and should therefore have a different PreNodeIn or PostNodeIn argument relative to one another:

traverse({_: "a"}, [{
  pre: (node: {_: "a"}) => ({_: "b"}),
  post: (node: {_: "c"}) => ({_: "d"}),
}, {
  pre: (node: {_: "b"}) => ({_: "c"}),
  post: (node: {_: "d"}) => ({_: "TSConf was AWESOME"}),
}])

One last complication: visitors could return a falsy value, indicating to the traversal function that the node is to be left unchanged. If we adjust the example above to the following...

traverse({_: "a"}, [{
  pre: (node: {_: "a"}) => ({_: "b"}),
- post: (node: {_: "c"}) => ({_: "d"}),
+ post: (node: {_: "c"}) => someCondition ? {_: "d"} : undefined,
}, {
  pre: (node: {_: "b"}) => ({_: "c"}),
  post: (node: {_: "d"}) => ({_: "TSConf was AWESOME"}),
}])

... we should then get an error, as the 2nd visitor's post function doesn't accept {_: "d"} | {_: "c"}... it only accepts {_: "d"}.

Ideally we could scrap the annotations and let traverse infer the correct constraints for visitor arguments (or reject incompatibly-typed visitors):

traverse({_: "a"}, [{
  // knows `node` is `{_: "a"}`
  pre: (node) => ({_: "b"}),
  // knows `node` is `{_: "c"}`
  post: (node) => someCondition ? {_: "d"} : undefined,
}, {
  // knows `node` is `{_: "b"}`
  pre: (node) => ({_: "c"}),
  // knows `node` is `{_: "c"} | {_: "d"}`
  post: (node) => ({_: "TSConf was AWESOME"}),
}])

Use Cases

Any traversal of an object whose type is known. For pluggable APIs which allow users to write visitors, this feature would enable a level of type-safety that could prove useful to both the plugin developer and end developer, who could observe conflict between traversals (which incompatibly mutate the same node).

Examples

I've attempted to do some of this (piping visitor return types back into visitor node type arguments)... I don't get an error... but it does not work as is expected:

interface Visitor<Node> {
  pre(node: Node): unknown;
  post(node: Node): unknown;
}

function traverse<
  Tree extends object,
  Visitors extends Visitor<NodeOf<Tree> | VisitorReturns>[],
  VisitorReturns = ReturnType<Visitors[number]["pre" | "post"]>
>(
  tree: Tree,
  visitor: Visitors,
) { }

traverse({
  a: {
    b: {
      c: {
        d: "e"
      }
    }
  }
}, [{
  // node is NOT inferred
  pre: (node): "f" => "f",
  post: (node): "g" => "g"
}])

If there's a way to support safer traversals, that would be so so sweet.

Checklist

My suggestion meets these guidelines:

• [uncertain] 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.)
• [perhaps fails to meet # 5 (easy to reason about)] This feature would agree with the rest of TypeScript's Design Goals.

[harrysolovay]

Hi TypeScript team & community. I'm so so curious whether the above is doable. Any thoughts would be greatly appreciated! Thank you!!!

[andrewbranch]

Is this a suggestion to add utility types to the core lib? If so, what you’re looking for is probably too specific. There’s no reason those types couldn’t be published to npm or DefinitelyTyped, though. The utility types that ship with the language are extremely general-purpose and tend toward low-level, preferring people to compose them into larger utilities in user-land or 3rd-party-lib-land (just look how long we went before caving to requests for Omit 😄).

If this is a question on how to write those types (or why the ones you’ve got so far aren’t working), you’ll probably have better luck on StackOverflow.

[harrysolovay]

@andrewbranch this question is more so about whether this kind of typing is possible... which it very well might not be. I appreciate how often you must get “how do I type this” questions... I don’t believe this to be one of them.

[andrewbranch]

At some point the problem space becomes complex enough that the only way to answer “is such a type possible” is to try to answer “how do I type this.” I gave it a shot; this is as close as I could get. (I inlined the Visitor type for quicker development but that’s inconsequential to the result.)

It seems like it might not be possible, because you need to infer PreNodeOut in the return type position of pre, and then use PreNodeOut in the parameter type position of post without inferring to that position. #14829 tracks a suggestion to explicitly opt into such behavior. There are some workaround discussed but none of them got me anywhere. I think #32540 may also be the same problem (cc @AnyhowStep).

By the way, the suggestion to go to StackOverflow isn’t dismissive to the question or the complexity of the question. We have community members who are much better than I am at writing crazy complex types, and you’re more likely to get their attention there than here.

[AnyhowStep]

You can represent anything in the type system and have it checked. (As long as it's computable)

The problem is that you may not be able to get the kind of type inference you want, and that the representation may not be convenient.

For example, you can technically have type-level arithmetic and range checks for numbers above the quadrillion range. The representation, however, isn't as easy as type Big = 1,000,000,000,000,000n + 1,234,567,890,123,456n.

It's more like, type Big = Add<[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0], [1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6]>, and you get back a tuple of digits.

In your case, without trying it yet, my intuition is that you can get TS to check it with recursive types, but you will not be able to get inference, as @andrewbranch pointed out.

---

So, when answering the question, "Can TS check this complex thing?" The answer is almost always, "Yes, but maybe not the exact representation you want, and you may not get inference"

---

That said, if you're willing to use overloads, this should be an easier problem. I'm not too sure yet, though. I'll have to find some time to play with it.

[andrewbranch]

That’s a good point of clarification—when I said “might not be possible,” I was referring specifically to getting inference on those node parameters, since that seemed to be the main thing @harrysolovay was struggling with.

[harrysolovay]

@andrewbranch @AnyhowStep thank you both for taking the time to think through this problem and provide feedback. I'm glad to hear that representing this type is possible, even if I can't get the kind of inference behavior that I'd like. Your help is much appreciated!