// RUN: %clang_analyze_cc1 -analyzer-checker=debug.ExprInspection \ // RUN: -verify=expected,noassumeone,eagerlyassume,combo %s // RUN: %clang_analyze_cc1 -analyzer-checker=debug.ExprInspection \ // RUN: -analyzer-config eagerly-assume=false \ // RUN: -verify=expected,noassumeone,noeagerlyassume,combo %s // RUN: %clang_analyze_cc1 -analyzer-checker=debug.ExprInspection \ // RUN: -analyzer-config assume-at-least-one-iteration=true \ // RUN: -verify=expected,eagerlyassume,combo %s // RUN: %clang_analyze_cc1 -analyzer-checker=debug.ExprInspection \ // RUN: -analyzer-config assume-at-least-one-iteration=true,eagerly-assume=false \ // RUN: -verify=expected,noeagerlyassume %s // The verify tag "combo" is used for one unique warning which is produced in three // of the four RUN combinations. // These tests validate the logic within `ExprEngine::processBranch` which // ensures that in loops with opaque conditions we don't assume execution paths // if the code does not imply that they are possible. // In particular, if two (or more) iterations are already completed in a loop, // we don't assume that there can be another iteration. Moreover, if the // analyzer option `assume-at-least-one-iteration` is enabled, then we don't // assume that a loop can be skipped completely. void clang_analyzer_numTimesReached(void); void clang_analyzer_dump(int); void clearTrueCondition(void) { // If the analyzer can definitely determine that the loop condition is true, // then this corrective logic doesn't activate and the engine executes // `-analyzer-max-loop` iterations (by default, 4). int i; for (i = 0; i < 10; i++) clang_analyzer_numTimesReached(); // expected-warning {{4}} clang_analyzer_dump(i); // Unreachable, no reports. } void clearFalseCondition(void) { // If the analyzer can definitely determine that the loop condition is false, // then the loop is skipped, even in `assume-at-least-one-iteration` mode. int i; for (i = 0; i > 10; i++) clang_analyzer_numTimesReached(); // Unreachable, no report. clang_analyzer_dump(i); // expected-warning {{0}} } void opaqueCondition(int arg) { // If the loop condition is opaque, don't assume more than two iterations, // because the presence of a loop does not imply that the programmer thought // that more than two iterations are possible. (It _does_ imply that two // iterations may be possible at least in some cases, because otherwise an // `if` would've been enough.) // Moreover, if `assume-at-least-one-iteration` is enabled, then assume at // least one iteration. int i; for (i = 0; i < arg; i++) clang_analyzer_numTimesReached(); // expected-warning {{2}} clang_analyzer_dump(i); // noassumeone-warning {{0}} expected-warning {{1}} expected-warning {{2}} } int check(void); void opaqueConditionCall(int arg) { // Same situation as `opaqueCondition()` but with a `while ()` loop. This // is also an example for a situation where the programmer cannot easily // insert an assertion to guide the analyzer and rule out more than two // iterations (so the analyzer needs to proactively avoid those unjustified // branches). int i = 0; // Helper to distinguish the the branches after the loop. while (check()) { clang_analyzer_numTimesReached(); // expected-warning {{2}} i++; } clang_analyzer_dump(i); // noassumeone-warning {{0}} expected-warning {{1}} expected-warning {{2}} } void opaqueConditionDoWhile(int arg) { // Same situation as `opaqueCondition()` but with a `do {} while ()` loop. // This is tested separately because this loop type is a special case in the // iteration count calculation. // Obviously, this loop guarantees that at least one iteration will happen. int i = 0; do { clang_analyzer_numTimesReached(); // expected-warning {{2}} } while (i++ < arg); clang_analyzer_dump(i); // expected-warning {{1}} expected-warning {{2}} } void dontRememberOldBifurcation(int arg) { // In this (slightly contrived) test case the analyzer performs an assumption // at the first iteration of the loop, but does not make any new assumptions // in the subsequent iterations, so the analyzer should continue evaluating // the loop. // Previously this was mishandled in `eagerly-assume` mode (which is enabled // by default), because the code remembered that there was a bifurcation on // the first iteration of the loop and didn't realize that this is obsolete. // NOTE: The variable `i` is significant to ensure that the iterations of the // loop change the state -- otherwise the analyzer stops iterating because it // returns to the same `ExplodedNode`. int i = 0; while (arg > 3) { clang_analyzer_numTimesReached(); // expected-warning {{4}} i++; } clang_analyzer_dump(i); // noassumeone-warning {{0}} } void dontAssumeFourthIterartion(int arg) { int i; if (arg == 2) return; // In this function the analyzer cannot leave the loop after exactly two // iterations (because it knows that `arg != 2` at that point), so it // performs a third iteration, but it does not assume that a fourth iteration // is also possible. for (i = 0; i < arg; i++) clang_analyzer_numTimesReached(); // expected-warning {{3}} clang_analyzer_dump(i); // noassumeone-warning {{0}} expected-warning {{1}} expected-warning {{3}} } #define TRUE 1 void shortCircuitInLoopCondition(int arg) { // When the loop condition expression contains short-circuiting operators, it // performs "inner" bifurcations for those operators and only considers the // last (rightmost) operand as the branch condition that is associated with // the loop itself (as its loop condition). // This means that assumptions taken in the left-hand side of a short-circuiting // operator are not recognized as "opaque" loop condition, so the loop in // this test case is allowed to finish four iterations. // FIXME: This corner case is responsible for at least one out-of-bounds // false positive on the ffmpeg codebase. Eventually we should properly // recognize the full syntactical loop condition expression as "the loop // condition", but this will be complicated to implement. int i; for (i = 0; i < arg && TRUE; i++) { clang_analyzer_numTimesReached(); // expected-warning {{4}} } clang_analyzer_dump(i); // expected-warning {{0}} expected-warning {{1}} expected-warning {{2}} expected-warning {{3}} } void shortCircuitInLoopConditionRHS(int arg) { // Unlike `shortCircuitInLoopCondition()`, this case is handled properly // because the analyzer thinks that the right hand side of the `&&` is the // loop condition. int i; for (i = 0; TRUE && i < arg; i++) { clang_analyzer_numTimesReached(); // expected-warning {{2}} } clang_analyzer_dump(i); // noassumeone-warning {{0}} expected-warning {{1}} expected-warning {{2}} } void eagerlyAssumeInSubexpression(int arg) { // The `EagerlyAssume` logic is another complication that can "split the // state" within the loop condition, but before the `processBranch()` call // which would be "naturally" responsible for evaluating the loop condition. // The current implementation tries to handle this by noticing the // cases where the loop condition is targeted by `EagerlyAssume`, but does // not handle the (fortunately rare) case when `EagerlyAssume` hits a // sub-expression of the loop condition (as in this contrived test case). // FIXME: It would be good to eventually eliminate this inconsistency, but // I don't know a realistic example that could appear in real-world code, so // this seems to be a low-priority goal. int i; for (i = 0; (i >= arg) - 1; i++) { clang_analyzer_numTimesReached(); // eagerlyassume-warning {{4}} noeagerlyassume-warning {{2}} } // The 'combo' note intentionally appears if `assume-at-least-one-iteration` // is disabled, but also appears as a bug when `eagerly-assume` and // `assume-at-least-one-iteration` are both enabled. clang_analyzer_dump(i); // combo-warning {{0}} expected-warning {{1}} expected-warning {{2}} eagerlyassume-warning {{3}} } void calledTwice(int arg, int isFirstCall) { // This function is called twice (with two different unknown 'arg' values) to // check the iteration count handling in this situation. int i; for (i = 0; i < arg; i++) { if (isFirstCall) { clang_analyzer_numTimesReached(); // expected-warning {{2}} } else { clang_analyzer_numTimesReached(); // expected-warning {{2}} } } } void caller(int arg, int arg2) { // Entry point for `calledTwice()`. calledTwice(arg, 1); calledTwice(arg2, 0); } void innerLoopClearCondition(void) { // A "control group" test case for the behavior of an inner loop. Notice that // although the (default) value of `-analyzer-max-loop` is 4, we only see 3 iterations // of the inner loop, because `-analyzer-max-loop` limits the number of // evaluations of _the loop condition of the inner loop_ and in addition to // the 3 evaluations before the 3 iterations, there is also a step where it // evaluates to false (in the first iteration of the outer loop). for (int outer = 0; outer < 2; outer++) { int limit = 0; if (outer) limit = 10; clang_analyzer_dump(limit); // expected-warning {{0}} expected-warning {{10}} for (int i = 0; i < limit; i++) { clang_analyzer_numTimesReached(); // expected-warning {{3}} } } } void innerLoopOpaqueCondition(int arg) { // In this test case the engine doesn't assume a second iteration within the // inner loop (in the second iteration of the outer loop, when the limit is // opaque) because `CoreEngine::getCompletedIterationCount()` is based on the // `BlockCount` values queried from the `BlockCounter` which count _all_ // evaluations of a given `CFGBlock` (in our case, the loop condition) and // not just the evaluations within the current iteration of the outer loop. // FIXME: This inaccurate iteration count could in theory cause some false // negatives, although I think this would be unusual in practice, as the // small default value of `-analyzer-max-loop` means that this is only // relevant if the analyzer can deduce that the inner loop performs 0 or 1 // iterations within the first iteration of the outer loop (and then the // condition of the inner loop is opaque within the second iteration of the // outer loop). for (int outer = 0; outer < 2; outer++) { int limit = 0; if (outer) limit = arg; clang_analyzer_dump(limit); // expected-warning {{0}} expected-warning {{reg_$}} for (int i = 0; i < limit; i++) { clang_analyzer_numTimesReached(); // expected-warning {{1}} } } } void onlyLoopConditions(int arg) { // This "don't assume third iteration" logic only examines the conditions of // loop statements and does not affect the analysis of code that implements // similar behavior with different language features like if + break, goto, // recursive functions, ... int i = 0; while (1) { clang_analyzer_numTimesReached(); // expected-warning {{4}} // This is not a loop condition. if (i++ > arg) break; } clang_analyzer_dump(i); // expected-warning {{1}} expected-warning {{2}} expected-warning {{3}} expected-warning {{4}} }