Add no-loop-without-fixed-bounds rule

[nfeignon]

In response to Augur bounty : "Prohibit loops without fixed bounds".

I'm not too sure about this one either. This commit checks if a loop (for, while, do while) has a test. If it does and if the test has a value that is equal to "true", it means this loop will be infinite. Otherwise, it's all good.

I feel like I'm missing something here. What do you think?

[beaugunderson]

will this catch a loop like while (a < b) {} where a is never incremented?

[duaraghav8]

IMO enforce-loop-bounds seems like a better name for this rule. Can we do a vote on this?

[duaraghav8]

Also I'll just lay down what I make of this rule for clarity's sake: This rule only ensures that there EXISTS some definitive value present inside the test condition of loop, regardless of whether that value boils down to true or false.

A static analyzer can't deduce the value of the test condition at runtime. EG-

do {
  //blah
} while (notCompleted);

This rule will be satisfied by the existence of notCompleted. But its possible that some function sets notCompleted's value to 1 and so actually this loop will run indefinitely. This is a runtime detail, so beyond the scope of solium to detect.

Is my understanding correct?

[beaugunderson]

@joeykrug suggests that this check may only be possible with something like oyente or the solidity SMT solver... I wonder if there's a simpler subset that we can warn on with solium?

[duaraghav8]

^which is correct. Lets base this rule on this idea:

This rule should flag any loop statement that:

• contains a test condition whose value is obviously true (ie, if we have to deduce the value by evaluating or something, then this rule shouldn't lint over that statement) AND
• there are no top-level break statements inside the loop body

examples:

Code that the rule SHOULD flag

for(;;} { }

do { } while (true)

// the outer loop does have a break stmt inside but that break is not top-level therefore doesn't exit from loop
do {
    do { break; } while (true);
} while (true);

code that rule SHOULDN'T flag

do {
    if (...) { break; }   // there's a possibility that loop will exit, even though this break is also not top-level
} while (true);

while (10 > 9) { ... } // test condition involves evaluation
while (x > 100) { ... } // only a dynamic analyzer can determine whether this does into an inf. loop or not

This technique will not always catch infinite loops but guarantees that any errors that the rule does raise are sure as hell not false positives.

@nfeignon I can see that this can easily get very complex, so you don't need to implement all the functionality. Its fine if you're implementing the rule to only lint for a subset of the above but please make sure there should be no false positives. And whatever cases you do account for, add tests!

[nfeignon]

I have updated my pull request with the requested changes.

So I implemented:

contains a test condition whose value is obviously true (ie, if we have to deduce the value by evaluating or something, then this rule shouldn't lint over that statement)

there are no top-level break statements inside the loop body

I have added more tests to try to cover all corner cases. And I also renamed the rule from no-loop-without-fixed-bounds to enforce-loop-bounds. It is definitely a better name :)