fuzion icon indicating copy to clipboard operation
fuzion copied to clipboard

Recursive checking of actual generics stops in case of recursion. Is this always correct?

Open fridis opened this issue 8 months ago • 0 comments

AbstractType.genericsAssignable contains the following special handling

        if (
          // NYI check recursive type, e.g.:
          // this  = monad monad.A monad.MA
          // other = monad option.T (option option.T)
          // for now just prevent infinite recursion
            !(g.isGenericArgument() && (g.genericArgument().constraint(context) == this ||
                                        g.genericArgument().constraint(context).constraintAssignableFrom(context, og))))

If removed, i.e., replaced by

        if (
          // NYI check recursive type, e.g.:
          // this  = monad monad.A monad.MA
          // other = monad option.T (option option.T)
          // for now just prevent infinite recursion
            !(g.isGenericArgument() && g.genericArgument().constraint(context).constraintAssignableFrom(context, og)))

Examples like this

m(A type, MA type : m A MA) is
b(T type, v T) : m T (b T) is
ignore <| b 23
ignore <| b 3.14

run into an endless recursion

 > ./build/bin/fz test_rec.fz

error 1: java.lang.StackOverflowError
	at dev.flang.ast.Context.constraintFor(Context.java:195)
	at dev.flang.ast.Context$2.constraintFor(Context.java:156)
	at dev.flang.ast.Context.constraintFor(Context.java:196)
	at dev.flang.ast.Context$2.constraintFor(Context.java:156)
	at dev.flang.ast.Generic.constraint(Generic.java:125)
	at dev.flang.ast.AbstractType.genericsAssignable(AbstractType.java:630)
	at dev.flang.ast.AbstractType.constraintAssignableFrom(AbstractType.java:582)
	at dev.flang.ast.AbstractType.constraintAssignableFrom(AbstractType.java:586)
	at dev.flang.ast.AbstractType.genericsAssignable(AbstractType.java:638)
	at dev.flang.ast.AbstractType.constraintAssignableFrom(AbstractType.java:582)
	at dev.flang.ast.AbstractType.constraintAssignableFrom(AbstractType.java:586)
	at dev.flang.ast.AbstractType.genericsAssignable(AbstractType.java:638)
	at dev.flang.ast.AbstractType.constraintAssignableFrom(AbstractType.java:582)
	at dev.flang.ast.AbstractType.constraintAssignableFrom(AbstractType.java:586)
	at dev.flang.ast.AbstractType.genericsAssignable(AbstractType.java:638)
	at dev.flang.ast.AbstractType.constraintAssignableFrom(AbstractType.java:582)
	at dev.flang.ast.AbstractType.constraintAssignableFrom(AbstractType.java:586)
	at dev.flang.ast.AbstractType.genericsAssignable(AbstractType.java:638)
	at dev.flang.ast.AbstractType.constraintAssignableFrom(AbstractType.java:582)
	at dev.flang.ast.AbstractType.constraintAssignableFrom(AbstractType.java:586)
	at dev.flang.ast.AbstractType.genericsAssignable(AbstractType.java:638)
	at dev.flang.ast.AbstractType.constraintAssignableFrom(AbstractType.java:582)
	at dev.flang.ast.AbstractType.constraintAssignableFrom(AbstractType.java:586)
	at dev.flang.ast.AbstractType.genericsAssignable(AbstractType.java:638)
	at dev.flang.ast.AbstractType.constraintAssignableFrom(AbstractType.java:582)
	at dev.flang.ast.AbstractType.constraintAssignableFrom(AbstractType.java:586)
	at dev.flang.ast.AbstractType.genericsAssignable(AbstractType.java:638)
	at dev.flang.ast.AbstractType.constraintAssignableFrom(AbstractType.java:582)
	at dev.flang.ast.AbstractType.constraintAssignableFrom(AbstractType.java:586)
	[...]

The problem is that the constraint on MA, which is m A MA gets checked by replacing it with the actual generics for A and MA, which is ok of A, but when checking MA; we recurse indefinitely.

The current implementation detects this by comparing the constraint with the current type this and just stopping, but is this enough?

fridis avatar Apr 02 '25 12:04 fridis