Recursive types can depend on presence and source location of unused type declaration

[CraigMacomber]

🔎 Search Terms

recursive type, unused, compile error

🕗 Version & Regression Information

• This changed between versions 3.3 (where this sample never compiles) and 3.5 (where it depends on the magic line). 5.2.2 works the same as 3.5.

⏯ Playground Link

https://www.typescriptlang.org/play?#code/PQKhCgAIUh1AnAhgB2QUwCaQJYDtKKQBmArrgMYAu2A9vpTQQDZM0Duk8aRa88eAc0gNhAT3QBnSACNuNLsIAWaUQQUY05Joi4YAdFBgAVRdikBbRAGs0UruRLwJ2AG5oCuLORoBae4+c3MUlIZBoJZ2kmNANoYHBKcXcjJIAlbl40CncAXkgACgBKSByAPkgjLjQAZXJlSwAeFPR0ni5s0oBucHBQCGhIAGEac2RsaOFsc3dECN5KJUQFgEEcKVnnAVxEKPcRfLQAD0osjAligCFY40YSCTQAGkhnUaZVDSI8GeC0AC5DSAAA0S6EgAH06porCVOGgAI4kbBcZYRbBbHbRIw0JpPACih3QVEwXUBhniIPcXARSLQKM2212WIaYNWRxOnikFyeF3KeUo8BIaG64C0GwqVVq9UQTXKAG9wABIZAkKLYciQby4CT8khUeT5ZWq9VcRAYOhvHC4Ig0X4VYqygC+4CdvWAQxQlEcthkNEoih+HiwAtw1Gmlut8Es1DoxHgIyU7mQOkQ0xO8AMwDd6XMNBcggTQLZpykzTQrUy2UBkEsNikfrMGpoGkbo3Gj0gaDc+GwRALlgEasgTC+MjQrA4De85mmIcwkBoJEoBlIFGj+EsyCaHeOxYqaQy7XIaFK+QpEltRkKF4lkMaRjliq4nvg+FwaA4lTQNVviFPSXO3Qupq2qQAAVhIdCpDQvowkUJTlOBdAAPLSKBmiUMKmZDCMM7ULgQgLgs9ZSMOb7zou87wNWub5tgRGMH67jSL6DDmPOvaMcQbYaogdzesRjbNiIuAwVOYzRBmbomA2DZuPAqhNhgtpcDmeb4ZAZB8VgFKQB8eB0bQWrPIoC5MFgIkLNIJrQmJ4xLIZBg6WC-aDnkVKIsiqLooy2IUjQvaIbgUG+k8pbloex7CsBCyBShaFUDCG75IFwWUIUnRAA

💻 Code

/**
 * Wrapped in a function to allow referring to types before they are declared.
 * This makes recursive and co-recursive types possible.
 */
type TypeReference = () => TreeSchema<TypeReference>;

/**
 * Compile time assert that A is assignable to (extends) B.
 * To use, simply define a type:
 * `type _check = requireAssignableTo<T, Expected>;`
 */
type requireAssignableTo<_A extends B, B> = true;

class TreeSchema<T> {
    public constructor(public readonly info: T) {}
}

// Captures both type and runtime information from the parameter.
// Removing the `extends TypeReference` makes this code compile, even if the magic line below is commented out.
function map<T extends TypeReference>(types: T): TreeSchema<T> {
    return new TreeSchema(types);
}

const jsonRoot = () => jsonObject;

// Commenting out this line out or moving it to the bottom of the file causes this code to not compile.
// This is very odd: removing unused type definitions should not break compilation.
type _magic = requireAssignableTo<typeof jsonRoot, TypeReference>;

const jsonObject = map(jsonRoot);

🙁 Actual behavior

This code fails to compile if the "_magic" line (which declares an unused type) is removed, or moved to the bottom of the file.

🙂 Expected behavior

Ideally this code should compile, regardless of if the "_magic" line is present. Additionally:

1. the presence of an unused type definition should not impact type checking.
2. the location of an type definition should not impact type checking.

Additional information about the issue

This was minified from https://github.com/microsoft/FluidFramework/blob/main/experimental/dds/tree2/src/domains/json/jsonDomainSchema.ts where I discovered that the type assertion I added caused the code to build without having to use the special recursive type workaround methods I added (which avoid using "extends" clauses which seem to break the recursive case). I'd love for cases like this to compile as it would make our API much nicer (the magic type assertion like to fix the build would be needed in our user's code and may require refactoring to add, so it's not a great workaround).

[RyanCavanaugh]

The way to think of this isn't that removing _magic broke your code, it's that adding _magic let you get away with something that would usually be an error.

Probably a simpler bottom three lines is:

const jsonRoot = () => jsonObject;
jsonRoot(); // <- replacement for _magic
const jsonObject = map(jsonRoot);

The circularity in the _magic-less code is:

• What's the type of jsonObject ?
• It's the result of calling map(jsonRoot)
• Is that a legal call?
• It depends, is jsonRoot a valid TypeReference?
• The parameters are OK
• The return type is OK if jsonObject is a valid TreeSchema<TypeReference>
• What's the type of jsonObject ?
• That's a loop from step 1; abort and error

This all starts at jsonObject since the computation of jsonRoot's type is mostly deferred, which is why a call to jsonRoot is the only thing that's needed to do a circularity-free resolution.

the presence of an unused type definition should not impact type checking. the location of an type definition should not impact type checking.

These would certainly be nice invariants to have, but the best-case scenario here would really involve erroring more often rather than erroring less often, which isn't something anyone is really asking for in most cases (indeed, telling someone we introduced an error in their code so that someone else experienced better consistency wouldn't be a well-received strategy).

TL;DR not getting a circularity error in code with a legitimate circularity (even one that could be resolved in a finite number of hypothetical levels of reasoning) is like getting a walk-in table at a restaurant -- it may happen but is not guaranteed to occur again even in facially-similar situations.

[CraigMacomber]

The way to think of this isn't that removing _magic broke your code, it's that adding _magic let you get away with something that would usually be an error.

Probably a simpler bottom three lines is:

const jsonRoot = () => jsonObject;
jsonRoot(); // <- replacement for _magic
const jsonObject = map(jsonRoot);

Personally, I find introducing runtime behavior which accesses a constant before its defined more "complex" then an unused type declaration. That said, this example does provide another perspective which has helped me understand, so thanks for that.

The circularity in the _magic-less code is:

• What's the type of jsonObject ?
• It's the result of calling map(jsonRoot)
• Is that a legal call?
• It depends, is jsonRoot a valid TypeReference?
• The parameters are OK
• The return type is OK if jsonObject is a valid TreeSchema<TypeReference>
• What's the type of jsonObject ?
• That's a loop from step 1; abort and error

This all starts at jsonObject since the computation of jsonRoot's type is mostly deferred, which is why a call to jsonRoot is the only thing that's needed to do a circularity-free resolution.

I'm likely missing something (since I don't know the implementation, and I imagine its complex and has a lot of constraints), but this explanation suggests a possible resolution of this problem:

There is no need to answer "Is that a legal call?" when computing the type of "the result of calling map(jsonRoot)" before you compute the type. If you reverse the order of those, all currently programs will still do the same amount of work type checking (I think) just in a different order, but programs like mine would compile (and some invalid programs would do more work before failing, which might be an issue).

More explicitly if we do: delay checking if the call is valid until after computing the result of the call. Once you have the result (which might be an error), then check if the call is valid, and if thats an error, use that error (to avoid changing which error gets surfaces to users in the case that both were errors).

the presence of an unused type definition should not impact type checking. the location of an type definition should not impact type checking.

These would certainly be nice invariants to have, but the best-case scenario here would really involve erroring more often rather than erroring less often, which isn't something anyone is really asking for in most cases (indeed, telling someone we introduced an error in their code so that someone else experienced better consistency wouldn't be a well-received strategy).

It seems to me like the reordering suggested above might fix a third invariant (that I didn't list) but would like to have:

1. Removing an "extends" clause (that is not required by the implementation and is itself not using any cyclic types) should not "fix" recursive types.

If we defer evaluating of usages against the extends clauses, then their presence no longer changes the evaluation order of recursive types in a way that is sometimes causes them to not compile.

TL;DR not getting a circularity error in code with a legitimate circularity (even one that could be resolved in a finite number of hypothetical levels of reasoning) is like getting a walk-in table at a restaurant -- it may happen but is not guaranteed to occur again even in facially-similar situations.

I am aware of this. My hope is this specific case seems like it might be improvable since there are so many different small tweaks that a programmer can to into tricking it to work that it seems like some tweaking in the compiler could do those automatically. If you can trick the compiler into imagining the extra type declaration that fixes things always exists even when you don't code it, or that the extends clause that breaks things doesn't exist until after the type is figured out (or is replaced by a second type check afterwards), it would just work.

Edit: I guess simpler phrasing of my suggestion is solve what types could be before checking if that meets all the constraints (like extends clauses). I believe that strictly increases which types will build, but I understand that might not be practical, but at least in this case the extends check seems practical to defer.

[CraigMacomber]

Slightly more general version in the playground

[CraigMacomber]

A different approach to mitigating the error, this time using "satisfies" in the playground.

I think this one is worth highlighting since what it doing is just checking that the typeof a value satisfies the extends constraint it's about to be used with. This really seems equivalent to just reordering the checks the compiler does slightly, and seems like something the compiler should be able to do automatically. I understand if this is intractable since doing it in this order would add to much overhead or break other things, but it really seems like it should be possible to make cases like these compile in the compiler without requiring these source level tweaks.

[CraigMacomber]

Another interesting find: when these types to work correctly (type check properly, and compile with out inferring "any"), the generated d.ts files include "any" instead of the recursive type reference. This happens even in the cleanest example: playground with d.ts issue

Should that be considered part of this issue (and a design limitation), or is the fact that the d.ts generation is diverged from the normal type checking (and infers any) a separate issue which I should fine independently? I think that is a pretty serious bug since when working with no-implicit-any, generating implicit any, with no error, and it only shows up for users of the library (which will also not get an error if using no-implicit any) is pretty likely to cause actual bugs.

[CraigMacomber]

Here is a simpler example of the d.ts issue:

const a = () => a;

Produces the d.ts of:

declare const a: () => any;

It should instead produce:

declare const a: () => typeof a;

Given this trivial reproduction, and what seems like a clear violation of no-implicit-any without a compile error, I'll file a separate bug to track that.

playground

[CraigMacomber]

I have file 55832 to track the issue with any showing up in the d.ts file in these cases.

[CraigMacomber]

I think the order dependent nature of this type checking causes intelisense in VSCode to not work correctly. It can show the recursive type as type checking properly, then if you modify the code to introduce an error, and undo your change, it claims the type is self dependent and typed as "any". This bad state persists until I reload the TypeScript project.

[andrewbranch]

The thing that makes it work when you add the intervening jsonRoot() call is that while doing the signature assignability checks, we can determine that pulling on its return type will trigger a circularity by looking at the pushTypeResolution stack, because it stores the info to say that we were already in the process of resolving the return type of the same signature () => jsonObject.

Without the call, pretty much everything is the same, except the info in the pushTypeResolution stack says we're trying to resolve the type jsonObject instead of the return type of () => jsonObject, so we don't detect that we're about to trigger a circularity.

It might be easy to make an overly-targeted fix for cases where the return type of some function can be trivially determined to be the type of some other symbol so the circularity stack can support some comparisons between resolving return types and resolving variable types, but I don't know how valuable that would be. The other theoretical approach I can think of is the kind of speculative checking we often wish we had but have found too challenging to roll back all affected state—if we had the ability to attempt to get a type inside a closure that rewound all state upon a circularity error, it seems like we would just use that instead of isResolvingReturnTypeOfSignature in this case.

In short, I couldn’t find a good way around this.

[ahejlsberg]

@weswigham Looks to me like this issue was caused by this commit some four years ago. That commit was part of #30416, but I don't really understand how it relates to the issue that PR is fixing. The commit causes us to silently ignore circularities when we detect them during signature relations, and that in turn leads to strange effects such as the issue reported here. If I remove the commit, the repro in this issue consistently errors (as expected). It also causes a circularity error in this test added by #30416, but I don't see how that test relates to the issue fixed by the PR and I'm not sure there's really anything wrong with the error in the test.

[weswigham]

but I don't really understand how it relates to the issue that PR is fixing.

Adding the Unmeasurable variance kind made many relationships dip back into structural checking, which uncovered some issues in the wild that variance checking had previously masked that needed to be fixed to make the addition less immediately breaky, iirc. That test case is a simplified example of something from DT, if I'm remembering correctly. Definitely possible there's better way to handle the issue - I'm working from vague memory and the comments in the test, but I think the issue was that resolving a this for an extends conditional check inside a class method return caused reentrancy when resolving the signature (since resolving the signature's return type requires resolving the signature's return type (to evaluate the conditional)), which somewhat definitionally means that signature return type can't meaningfully contribute to the check (so shouldn't be meaningful when comparing this to C). So you do want to just get any of the reentrance in that situation (or... not quite any but the hybrid unknown-in-intersections-but-never-in-unions type I've mentioned before, were it available), but you don't really want to issue a circularity error (mostly since there wasn't one before when the reentrance was hidden by a variance check, but also because in that case the reentrance does just mean "don't consider this member", like raising a Maybe in relationship checking does).

So I don't think that test should be disregarded - if it gets an error, some stuff in the wild likely will, too. Considering this issue, I think the reentrant any result aughta to be scoped to the context of the this extends C relationship check, rather than cached forever, like how a circular structural dependence in relationship checking should just turn up a Maybe, and thus defer the result to other members participating in the check. Maybe doable with some CheckMode work.

[ahejlsberg]

@weswigham My preference would be to just accept the circularity error in the test from https://github.com/microsoft/TypeScript/pull/30416, but feel free to explore other solutions. I'll assign the issue to you for now.