Validation error: Recursion #667
Description
Since we don't have conditional execution, any recursion is endless. We should detect this and show an error. Example tests:
package tests.validation.other.expressions.calls.recursion
pipeline p {
// $TEST$ error "Recursive calls are not allowed."
»a«();
// $TEST$ error "Recursive calls are not allowed."
»b«();
// $TEST$ error "Recursive calls are not allowed."
»c«();
// $TEST$ no error "Recursive calls are not allowed."
»d«();
// $TEST$ no error "Recursive calls are not allowed."
»f«();
}
segment a() {
// $TEST$ error "Recursive calls are not allowed."
»a«();
// $TEST$ error "Recursive calls are not allowed."
»b«();
// $TEST$ error "Recursive calls are not allowed."
»c«();
// $TEST$ no error "Recursive calls are not allowed."
»d«();
// $TEST$ no error "Recursive calls are not allowed."
»f«();
() {
// $TEST$ error "Recursive calls are not allowed."
»a«();
// $TEST$ error "Recursive calls are not allowed."
»b«();
// $TEST$ error "Recursive calls are not allowed."
»c«();
// $TEST$ no error "Recursive calls are not allowed."
»d«();
// $TEST$ no error "Recursive calls are not allowed."
»f«();
};
val lambda1 = () {
// $TEST$ no error "Recursive calls are not allowed."
»lambda1«();
};
val lambda2 = () {
// $TEST$ no error "Recursive calls are not allowed."
»lambda3«();
};
val lambda3 = () {
// $TEST$ no error "Recursive calls are not allowed."
»lambda2«();
};
}
segment b() {
// $TEST$ error "Recursive calls are not allowed."
»c«();
}
segment c() {
// $TEST$ error "Recursive calls are not allowed."
»b«();
}
segment d() {}
package tests.staticAnalysis.recursion
// Positive examples -----------------------------------------------------------
annotation CallsShouldBeRecursive
// Direct recursion
@CallsShouldBeRecursive
step directRecursion(a: Any or directRecursion()) {
directRecursion();
1 + directRecursion();
val a = directRecursion();
}
// Transitive recursion
@CallsShouldBeRecursive
step transitiveRecursion1() {
transitiveRecursion2();
val a = transitiveRecursion2();
}
@CallsShouldBeRecursive
step transitiveRecursion2() {
transitiveRecursion3();
val a = transitiveRecursion3();
}
@CallsShouldBeRecursive
step transitiveRecursion3() {
transitiveRecursion2();
val a = transitiveRecursion2();
}
// Deferred recursion in lambda
@CallsShouldBeRecursive
step deferredRecursionInLambda() {
(() { directRecursion(); })();
(() -> directRecursion())();
}
// Negative examples -----------------------------------------------------------
annotation CallsShouldNotBeRecursive
// Normal calls
@CallsShouldNotBeRecursive
step normalCall(f: () -> ()) {
f();
(() {})();
(() -> null)();
MyClass();
MyEnum.Variant();
myFun();
myStep();
}
class MyClass()
enum MyEnum {
Variant()
}
fun myFun()
step myStep() {}
// Uncalled lambda
@CallsShouldNotBeRecursive
step uncalledLambda() {
() { uncalledLambda(); };
() -> uncalledLambda();
}
// Lambda recursion (already handled by scoping)
@CallsShouldNotBeRecursive
step lambdaRecursion() {
val a = () { a(); };
val b = () -> b();
}
// Unresolved callable
@CallsShouldNotBeRecursive
step unresolvedCallable() {
unresolved();
}
Recursion
Functions as parameters can also lead to recursion:
segment a() {
b(a);
}
segment b(f: () -> ()) {
f();
}
This is prevented since function pointers are not allowed. However, it's still possible with lambdas:
segment a() {
b(() -> a());
}
segment b(f: () -> ()) {
f();
}
We could prevent lambdas from calling the containing segment. But it would still be possible to build recursive calls:
segment a() {
b(() -> c());
}
segment c() {
a();
}
segment b(f: () -> ()) {
f();
}
We could generally follow all function pointers, whether they are called or not (or all calls, whether they are contained directly or in a lambda), to detect recursion. Recursion might still happen, however:
segment a() {
b(() -> b());
}
segment b(f: () -> ()) {
f();
}
Thus, it seems like we need to remember for a lambda which callables get called if the lambda gets executed.
Metadata
Metadata
Assignees
Type
Projects
Status