Fsharp: Immediate cyclic reference is not detected

[vasily-kirichenko]

This code raises error at compile time (good)

[<Struct>]
type Tree =
    | Empty
    | Children of Tree * Tree

```
Program.fs(7, 6): [FS0954] This type definition involves an immediate cyclic reference through a struct field or inheritance relation

This code does not (bad, bad, bad)

```fsharp
[<Struct>]
type Tree =
    | Empty
    | Children of struct (Tree * Tree)

but it fails at runtime:

Unhandled Exception: System.TypeLoadException: Could not load type 'Program+Tree' from assembly 'Test, Version=0.0.0.0, Culture=neutral, PublicKeyToken=null'.
   at Program.main(String[] args)

[dsyme]

Yes, thanks, this should be detected. The fix will be to account for struct tuples somewhere around
https://github.com/Microsoft/visualfsharp/blob/cea9284349e6ecc803cc39b67096b83010f0416d/src/fsharp/TypeChecker.fs#L15537

[ScottHutchinson]

I have determined that when it fails to detect, it fails to match this case:

/// TType_app(tyconRef, typeInstantiation).
///
/// Indicates the type is built from a named type and a number of type arguments
| TType_app of TyconRef * TypeInst

at this line (and it's not the when clause that's the problem; even without the when clause, it still does not match):
https://github.com/Microsoft/visualfsharp/blob/cea9284349e6ecc803cc39b67096b83010f0416d/src/fsharp/TypeChecker.fs#L15540

But it will match this, so maybe a new rule like this can fix the issue:
| TType_tuple (tupInfo, _) ->

[ScottHutchinson]

Or maybe upstream, the struct (Tree * Tree) should be coerced to match the TType_app (tcref2 , tinst2) rule like Tree * Tree does.

[ScottHutchinson]

Also @vasily-kirichenko , why do we need the offending syntax of struct (Tree * Tree)?

That should probably be documented at https://docs.microsoft.com/en-us/dotnet/fsharp/language-reference/discriminated-unions#using-discriminated-unions-for-tree-data-structures

EDIT: I guess I found the answer here: https://docs.microsoft.com/en-us/dotnet/fsharp/language-reference/tuples#interoperation-with-c-tuples

If not for the need to interop with C#, surely a struct tuple would not be worth the trouble. Just use a struct record instead.

[enricosada]

should this code raise the error at all?

[<Struct>]
type Tree =
    | Empty
    | Children of struct (Tree * Tree)

Children is a struct tuple. that mean i can do

let f () =
    let e = Tree.Empty
    let x = struct (e,e)
    let d = Tree.Children x
    d

or not? this compile, but like before, fails at runtime with

Unhandled Exception: System.TypeLoadException: Could not load type 'Test+Tree' from assembly 'err1, Version=0.0.0.0, Culture=neutral, PublicKeyToken=null'.
   at Test.run(String[] _arg1)

should be similar to

type Tree =
    | Empty
    | Children of (Tree * Tree)

who use a Tuple, because in the first example is Children(Tree, Tree) (not valid), in the second with struct (Tree, Tree), the method is Children(ValueTuple<Tree,Tree>)

[ScottHutchinson]

@smoothdeveloper @enricosada @vasily-kirichenko Adding this new case (https://github.com/ScottHutchinson/visualfsharp/commit/d0713daa32b5d6891c7ca1cda8971493e51f0741#diff-5b9ab9dd9d7133aaf23add1048742031) fixes the issue for the original test case (https://github.com/Microsoft/visualfsharp/issues/3916#issue-272496610) | Children of struct (Tree * Tree), but it does not fix the case of | Children of struct (int * Tree), because it only checks the head of the list (tuple), and throws away the tail. So a bit more work is needed to check the tail as well. Any help is appreciated.

[smoothdeveloper]

@ScottHutchinson it looks like you may need to fold over the t2 list in place, or maybe pass tuples until it is only one remaining element instead of just passing the head in your current fix; you are not far from correct fix.

[ScottHutchinson]

@smoothdeveloper This fold might do it. https://github.com/ScottHutchinson/visualfsharp/commit/467f5294a9730f31e9094b8f771c5c5c64dd4b99#diff-5b9ab9dd9d7133aaf23add1048742031

[cartermp]

Fixed by https://github.com/dotnet/fsharp/pull/10645