Force return statement check

[jacqueswww]

What's your issue about?

Currently you can have a return type set on a function, yet omit the return statement. Add a exception when this happens forcing the programming to add a return, if specified.

e.g.

@public
def foo() -> num:
        pass

How can it be fixed?

Off the top of my head, check parse_func.

Cute Animal Picture

[fubuloubu]

As I think @yzhang90 has noted, this is actually subtletly very hard (but I'd argue still necessary) because of blocks, for example the following would pass your check but still fail to return anything:

def Foo(a: bool) -> num:
    if a:
         return 1

[DavidKnott]

I think we could track each path and make sure each one has a return. That being said, a good first step would be to check for the existence of any return.

[fubuloubu]

Agreed. And I think currently viper programs will probably be simple enough that most if branches in methods would be nested only once or twice (e.g. if: if: ... else: ... else: if: ... else: ...), so the number of total branches to keep track of should be fairly managable. I think the right upper bound is 2^n branches where n is the amount of nesting. The gas limit should impose an economic upper bound on this I would think.

[jacqueswww]

Actually it's probably much simpler than that, we have a checker that check correct return statements by type. And we just then need to make sure each function has at minimum one return. All those in the ifs will be handled by the return type checker, ie. Not None. ;)

[jacqueswww]

I will tackle this one next, it's just building a map of functions that have return and erroring if any are missing (my gut feel says just populating a map in parse_return) , will show you :)

[fubuloubu]

@jacqueswww How does your proposal deal with this:

def foo(a: bool) -> num:
    if a:
        return 1

[jacqueswww]

Ah I see, now. I have a few ideas. Looking forward to challenge ;)

[fubuloubu]

or this (this should pass):

def foo(a: bool) -> num:
    b: num = 0
    if a:
        b = 1
    else:
        return 0
    return b

[fubuloubu]

It shouldn't be too hard, my point is it is a harder algorithm because you have to explore 2**n branches

[fubuloubu]

And also the result if no return is taken in some subset of branches (and deferred to the end)

[fubuloubu]

P.S. I think this is actually a formal verification problem lol

[jacqueswww]

Yes you are right, one will have to figure out a way for the branches to take the default else into account, hmmm let me research it some more. 😂

[fubuloubu]

Yeah, I think there are standard FV algorithms for doing this, I think it usually involves holding an additional bookkeping variables while you're parsing a given function, then testing those instead.

[jacqueswww]

@fubuloubu @DavidKnott consider this rule set:

1.) There must be at least one return statement in every function.
2.) If there is a nested return statement a default return must be set OR trace all other nested returns and ensure they exist.

The problem with a nested return comes in that all paths have to be considered as you mentioned, however if we force the rule of a default return statement. Are we perhaps gaining clarity in the program ? And thereby simplifying this check. I personally always read default returns better than nested ones:

def a() -> num:
    if ...:
        return 1
    else:
        return 2

Is more difficult for me to read than:

def a() -> num:
    if ...:
        return 1
    return 2

Maybe I am the exception ;) But the one thing we can agree on to implement so long, is the check for rule 1. I will proceed with the partial PR so long that does that check.

[fubuloubu]

1 is a good start and get's us halfway there, I think that is okay to add.

2 requires that much more advanced check, and since checking for a default return is a special case of the general problem of branched returns, I don't think we want to arbitrarily disallow a certain type of style as a first step, so I think we need to leave 2 to when both parts of the check can be performed. Which means really just the general case check of branched returns, since default return is simply a special case.

2 will override 1 when it is complete.

[yzhang90]

@fubuloubu @jacqueswww
After @daejunpark and I think about this issue twice, I think a sound and complete analysis (both in general and specific to this) is not decidable. So, you need to be conservative, and there is a very simple but reasonable conservative algorithm for this, similar to that of Java ( the complexity is linear to the number of statement in a program, not 2**n).

Let me first start with an example(just some pseudo code):

def foo(n:num)->num:
for i in range(10):
    if i == f(n):
        return 0

This is valid in case f(n) < 10 for any n, but it may be involving, if not undecidable, to fully automatically analyze this. Also, in many cases, this style of coding is not best practice. So, it is reasonable to force users to conservatively add return statements even in places that are not reachable (e.g., outside of the loop in the example), which allows us to have a very simple and efficient analysis as outlined below. Note that Java compiler does the same thing.

With this in mind, let me describe the algorithm:

1. You can think of if ... as if ... else pass, so you only need to consider about if...else... case.
2. Just a sketch of the code:

// return true means the function pass the return check.
def check_return(statements){ 
    for st in statements{
        if(st is return){
            return true
         }
        if(statement is if...else...) {
            then_br_return = check_return(then_stmts)
            else_br_return = check_return(else_stmts)
            if(then_br_return && else_br_return) {
                return true
            }
       }
    }
    return false
}

You just need to call check_return on the the function body.
P.S., this function can also be slightly modified to check dead code as well.

[DavidKnott]

@yzhang90 The idea would be adding a return at the end even without for loops correct?
The trigger being lone if or if..elif statements because a return from them cannot easily (or not at all if based on input) be guaranteed.

[yzhang90]

@DavidKnott I'm not sure I fully got your questions. What we propose here is an simple algorithm to conservatively check whether a function has return statement on all possible path. If the check_return function returns false, the compiler should simply reject the program (even though the program is actually correct/valid, e.g., you change f(n) to 8 in my previous example). I'm NOT proposing adding return at the end (or do any transformation of the program). I think it is better to let programmers know that they're missing some cases instead of return some default values for them.

[fubuloubu]

@DavidKnott Kind of. You can say that an end return statement is a special case of this algorithm, and given it's existence you can just skip the check because the answer is trivial.

The if in for loop is the real problem, you cannot gain insight into whether a return is possible without simulating all possibilities of the code, which is infeasible. I think a good shortcut for that case is to basically skip checking inside a for loop block.

[yzhang90]

The following program should be rejected:

def foo()->num:
    for i in range(10):
        return 0

People should instead write:

def foo()->num:
    for i in range(10):
        return 0
    return 0

Though the second return is never reachable.

[fubuloubu]

Summarize:

REJECT

for i in list:
    if i == n:
        return i

ACCEPT

for i in list:
    if i == n:
        return i
return 0 # Accept because "End return statement" exists

REJECT

for i in list:
    if i == n:
        return i
if n > len(list):
    return 0

[fubuloubu]

So slight modification to their algorithm:

def check_return(statements):
    if statements[-1] is 'return' and statements[-1] is at base indentation:
        return True # Trivial case, probably 60% of all cases
    for st in statements:
        if(st is 'return'):
            return True
        if(statement is 'if then_stmts else else_stmts'):
            then_br_return = check_return(then_stmts)
            else_br_return = check_return(else_stmts)
            if(then_br_return and else_br_return):
                return True
    return False

[charles-cooper]

The if in for loop is the real problem, you cannot gain insight into whether a return is possible without simulating all possibilities of the code, which is infeasible. I think a good shortcut for that case is to basically skip checking inside a for loop block.

i revisited this today while working on a fix for #3223. i think the issue is actually not that ifs inside of for loops are not analyseable. you can apply the same branching analysis -- that is,

    # valid return
    for i in range(10):
        if n == i:
            return 1
        else:
            return 0
    # do not need to add return statement here, for loop is guaranteed to terminate

the issue now is that we now have for loops which might have 0 iterations, for example:

    xs: DynArray[uint256, 3] = []
    for i: uint256 in xs:  # never executes
        return 1
    # reachable!

we could maybe apply one of two analyses depending on if we can prove the loop iterates at least 1 time.