How do we deal with recursive structures?

[simolus3]

In the existing macro implementation from the SDK, objects sent between the client and the executor are remembered, allowing only an id to be sent if these objects are serialized multiple times.

I assume this was done for performance reasons, but it's also required to describe recursive structures. If we model types for instance, a typical example is class num extends Comparable<num> - a resolved type sent to the client likely needs to include direct supertypes so that a hierarchy can be built. It's also possible to construct recursive elements with type parameters, e.g. in void Function<A extends List<B>, B extends A>(). These structures will have to be serialized somehow, as the analyzer/CFE is responsible for resolving identifiers to types and then needs to send the computed types to the macro.

One way to break the recursion in the serialized format is to refer recursive types by their index within a message, e.g. #0: num extends #1<#0>; #1: Comparable. But this will require a more complicated serializer than the current approach based on stateless extension types. So I wonder if there may be other workarounds or what we should best do here.

[davidmorgan]

Great question, thanks :)

I think the key piece here is referring to types by URI and name. You can go and look up a simple type for more information about it; the reference breaks the cycle. Currently we use QualifiedName for that but we use that for other things besides types, we may want something like SimpleType that always refers to a type.

So num can be represented as SimpleType('dart:core#num'), to get the extends list you have to look that up in the full data model, it can refer to itself with another SimpleType('dart:core#num').

void Function<A extends List<B>, B extends A> would be represented something like:

FunctionType(
  returnType: SimpleType('dart:core#void'),
  params: [
    TypeVariable(
      name: 'A',
      extends: GenericType(
        simpleType: SimpleType('dart:core#List'),
        params: [TypeVariable(name: 'B']],
    ),
    TypeVariable(
      name: 'B',
      extends: TypeVariable(name: 'A'),
    ),
  ],
)

Handling TypeVariable will be a little complicated as of course scope matters and there is maybe a case to be made for canonicalizing them...

We might still want to do some deduping for performance, the plan is there will be a binary wire format that is a transformation of the JSON wire format to be faster + more efficient, if needed I think we can do it there.

[simolus3]

I think the key piece here is referring to types by URI and name. You can go and look up a simple type for more information about it; the reference breaks the cycle.

One thing to be aware of is that this would require an additional wrapper around the stateless schema types to implement a synchronous type system. For instance, if we want to have a bool isSubtype(StaticType left, StaticType right), we can't do that with SimpleTypes because we need to ask the macro host to resolve them as we encounter them. That may be fine (e.g. we could have Future<ResolvedType> resolveType(StaticTypeDescription)) and then guarantee that anything involving a ResolvedType is synchronous.