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.