Validation error: Recursion

[lars-reimann]

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.

[lars-reimann]

🎉 This issue has been resolved in version 0.4.0 🎉

The release is available on:

• npm package (@latest dist-tag)
• npm package (@latest dist-tag)
• v0.4.0
• GitHub release

Your semantic-release bot 📦🚀