Compilation fails to terminate for polymorphic recursion on value types

[zvmsbackend]

When compiling a polymorphically recursive function on a value type, the compiler neither yields a erroneous result nor reports abnormality, but instead loops forever.

Repro steps

For example, try compiling the following code:

[<Struct>] type Nested<'a> = Cons of 'a * Nested<'a list> | Nil

let rec length<'a> : Nested<'a> -> int= function
  | Cons (_, xs) -> 1 + length xs
  | Nil -> 0

Expected behavior

The compiler should raise an error if such divergence is predictable.

Actual behavior

The compiler fails to terminate.

[vzarytovskii]

Why does the F# compiler refuse to compile that polymorphically recursive function?
Because it's still trying to decide if it will ever stop.

In all seriousness though, it looks like a regression. @zvmsbackend Can you by any chance do a dotnet-dump while it's spinning and attach it here? Will be easy to see whether it's deadlocked or spinning infinitely.

[vzarytovskii]

It is there from at least since .NET6: https://godbolt.org/z/M1W8Mrfx9

[brianrourkeboll]

It's the type definition that is the problem here, no? Such a recursively-defined struct type should just not be allowed at all:

A struct type must be valid according to the CLI rules for structs; in particular, recursively
constructed structs are not permitted. For example, the following type definition is not permitted,
because the size of BadStruct2 would be infinite:

[<Struct>]
type BadStruct2 =
    val data : float;
    val rest : BadStruct2
    new (data, rest) = { data = data; rest = rest }

Likewise, the implied size of the following struct would be infinite:

[<Struct>]
type BadStruct3 (data : float, rest : BadStruct3) =
    member s.Data = data
    member s.Rest = rest

The compiler still correctly emits explicit error messages for those two examples, for what it's worth.

[zvmsbackend]

It's the type definition that is the problem here, no? Such a recursively-defined struct type should just not be allowed at all:

A struct type must be valid according to the CLI rules for structs; in particular, recursively
constructed structs are not permitted. For example, the following type definition is not permitted,
because the size of BadStruct2 would be infinite:
[]
type BadStruct2 =
val data : float;
val rest : BadStruct2
new (data, rest) = { data = data; rest = rest }

Likewise, the implied size of the following struct would be infinite:
[]
type BadStruct3 (data : float, rest : BadStruct3) =
member s.Data = data
member s.Rest = rest

The compiler still correctly emits explicit error messages for those two examples, for what it's worth.

Yes, the real problem stems from the recursive value type definition, not the polymorphic recursion on it.

[<Struct>] type Nested<'a> = Cons of 'a * Nested<'a list> | Nil;;

It turned out that the line of type definition is enough to make compiler diverge.

Usually the compiler does raise an error for cycle layout of a structure:

[<Struct>] type Nested<'a> = Cons of 'a * Nested<'a> | Nil

// stdin(1,17): error FS0954: 此类型定义涉及一个经由结构字段或继承关系的直接循环引用

But in this case where the embedded struct has a different type parameter, the compiler just strays.

On the other hand, C# successfully diagnoses such kind of cyclic struct:

struct Nested<T> { Nested<List<T>> xs; }

// error CS0523: Struct member 'Nested<T>.xs' of type 'Nested<List<T>>' causes a cycle in the struct layout

Thus, I still think this is a bug, but a more appropriate caption would be "Compilation fails to terminate for recursive generic struct".

[T-Gro]

It's definitely a mistake in not raising a regular FSxxx error on that fast ;; we just need to find out (e.g. via the dotnet dump Vlad mentioned) what part of the compilation tries to do infinite work on it - the check must be placed before that.

[vzarytovskii]

Oh, I completely blanked on the fact that it's a struct. Yes, it should raise an error

[brianrourkeboll]

Looks like it's here:

fsharp/src/Compiler/Checking/CheckDeclarations.fs

Lines 3962 to 3969 in bd346da

	// collect edges from the fields of a given struct type.
	and accStructFields includeStaticFields ty (structTycon: Tycon) tinst (doneTypes, acc) =
	if List.exists (typeEquiv g ty) doneTypes then
	// This type (type instance) has been seen before, so no need to collect the same edges again (and avoid loops!)
	doneTypes, acc
	else
	// Only collect once from each type instance.
	let doneTypes = ty :: doneTypes