263 lines · c
1// RUN: %clang_analyze_cc1 -analyzer-checker=debug.ExprInspection \2// RUN: -verify=expected,noassumeone,eagerlyassume,combo %s3// RUN: %clang_analyze_cc1 -analyzer-checker=debug.ExprInspection \4// RUN: -analyzer-config eagerly-assume=false \5// RUN: -verify=expected,noassumeone,noeagerlyassume,combo %s6// RUN: %clang_analyze_cc1 -analyzer-checker=debug.ExprInspection \7// RUN: -analyzer-config assume-at-least-one-iteration=true \8// RUN: -verify=expected,eagerlyassume,combo %s9// RUN: %clang_analyze_cc1 -analyzer-checker=debug.ExprInspection \10// RUN: -analyzer-config assume-at-least-one-iteration=true,eagerly-assume=false \11// RUN: -verify=expected,noeagerlyassume %s12 13// The verify tag "combo" is used for one unique warning which is produced in three14// of the four RUN combinations.15 16// These tests validate the logic within `ExprEngine::processBranch` which17// ensures that in loops with opaque conditions we don't assume execution paths18// if the code does not imply that they are possible.19// In particular, if two (or more) iterations are already completed in a loop,20// we don't assume that there can be another iteration. Moreover, if the21// analyzer option `assume-at-least-one-iteration` is enabled, then we don't22// assume that a loop can be skipped completely.23 24void clang_analyzer_numTimesReached(void);25void clang_analyzer_dump(int);26 27void clearTrueCondition(void) {28 // If the analyzer can definitely determine that the loop condition is true,29 // then this corrective logic doesn't activate and the engine executes30 // `-analyzer-max-loop` iterations (by default, 4).31 int i;32 for (i = 0; i < 10; i++)33 clang_analyzer_numTimesReached(); // expected-warning {{4}}34 35 clang_analyzer_dump(i); // Unreachable, no reports.36}37 38void clearFalseCondition(void) {39 // If the analyzer can definitely determine that the loop condition is false,40 // then the loop is skipped, even in `assume-at-least-one-iteration` mode.41 int i;42 for (i = 0; i > 10; i++)43 clang_analyzer_numTimesReached(); // Unreachable, no report.44 45 clang_analyzer_dump(i); // expected-warning {{0}}46}47 48void opaqueCondition(int arg) {49 // If the loop condition is opaque, don't assume more than two iterations,50 // because the presence of a loop does not imply that the programmer thought51 // that more than two iterations are possible. (It _does_ imply that two52 // iterations may be possible at least in some cases, because otherwise an53 // `if` would've been enough.)54 // Moreover, if `assume-at-least-one-iteration` is enabled, then assume at55 // least one iteration.56 int i;57 for (i = 0; i < arg; i++)58 clang_analyzer_numTimesReached(); // expected-warning {{2}}59 60 clang_analyzer_dump(i); // noassumeone-warning {{0}} expected-warning {{1}} expected-warning {{2}}61}62 63int check(void);64 65void opaqueConditionCall(int arg) {66 // Same situation as `opaqueCondition()` but with a `while ()` loop. This67 // is also an example for a situation where the programmer cannot easily68 // insert an assertion to guide the analyzer and rule out more than two69 // iterations (so the analyzer needs to proactively avoid those unjustified70 // branches).71 int i = 0; // Helper to distinguish the the branches after the loop.72 while (check()) {73 clang_analyzer_numTimesReached(); // expected-warning {{2}}74 i++;75 }76 77 clang_analyzer_dump(i); // noassumeone-warning {{0}} expected-warning {{1}} expected-warning {{2}}78}79 80void opaqueConditionDoWhile(int arg) {81 // Same situation as `opaqueCondition()` but with a `do {} while ()` loop.82 // This is tested separately because this loop type is a special case in the83 // iteration count calculation.84 // Obviously, this loop guarantees that at least one iteration will happen.85 int i = 0;86 do {87 clang_analyzer_numTimesReached(); // expected-warning {{2}}88 } while (i++ < arg);89 90 clang_analyzer_dump(i); // expected-warning {{1}} expected-warning {{2}}91}92 93void dontRememberOldBifurcation(int arg) {94 // In this (slightly contrived) test case the analyzer performs an assumption95 // at the first iteration of the loop, but does not make any new assumptions96 // in the subsequent iterations, so the analyzer should continue evaluating97 // the loop.98 // Previously this was mishandled in `eagerly-assume` mode (which is enabled99 // by default), because the code remembered that there was a bifurcation on100 // the first iteration of the loop and didn't realize that this is obsolete.101 102 // NOTE: The variable `i` is significant to ensure that the iterations of the103 // loop change the state -- otherwise the analyzer stops iterating because it104 // returns to the same `ExplodedNode`.105 int i = 0;106 while (arg > 3) {107 clang_analyzer_numTimesReached(); // expected-warning {{4}}108 i++;109 }110 111 clang_analyzer_dump(i); // noassumeone-warning {{0}}112}113 114void dontAssumeFourthIterartion(int arg) {115 int i;116 117 if (arg == 2)118 return;119 120 // In this function the analyzer cannot leave the loop after exactly two121 // iterations (because it knows that `arg != 2` at that point), so it122 // performs a third iteration, but it does not assume that a fourth iteration123 // is also possible.124 for (i = 0; i < arg; i++)125 clang_analyzer_numTimesReached(); // expected-warning {{3}}126 127 clang_analyzer_dump(i); // noassumeone-warning {{0}} expected-warning {{1}} expected-warning {{3}}128}129 130#define TRUE 1131void shortCircuitInLoopCondition(int arg) {132 // When the loop condition expression contains short-circuiting operators, it133 // performs "inner" bifurcations for those operators and only considers the134 // last (rightmost) operand as the branch condition that is associated with135 // the loop itself (as its loop condition).136 // This means that assumptions taken in the left-hand side of a short-circuiting137 // operator are not recognized as "opaque" loop condition, so the loop in138 // this test case is allowed to finish four iterations.139 // FIXME: This corner case is responsible for at least one out-of-bounds140 // false positive on the ffmpeg codebase. Eventually we should properly141 // recognize the full syntactical loop condition expression as "the loop142 // condition", but this will be complicated to implement.143 int i;144 for (i = 0; i < arg && TRUE; i++) {145 clang_analyzer_numTimesReached(); // expected-warning {{4}}146 }147 148 clang_analyzer_dump(i); // expected-warning {{0}} expected-warning {{1}} expected-warning {{2}} expected-warning {{3}}149}150 151void shortCircuitInLoopConditionRHS(int arg) {152 // Unlike `shortCircuitInLoopCondition()`, this case is handled properly153 // because the analyzer thinks that the right hand side of the `&&` is the154 // loop condition.155 int i;156 for (i = 0; TRUE && i < arg; i++) {157 clang_analyzer_numTimesReached(); // expected-warning {{2}}158 }159 160 clang_analyzer_dump(i); // noassumeone-warning {{0}} expected-warning {{1}} expected-warning {{2}}161}162 163void eagerlyAssumeInSubexpression(int arg) {164 // The `EagerlyAssume` logic is another complication that can "split the165 // state" within the loop condition, but before the `processBranch()` call166 // which would be "naturally" responsible for evaluating the loop condition.167 // The current implementation tries to handle this by noticing the168 // cases where the loop condition is targeted by `EagerlyAssume`, but does169 // not handle the (fortunately rare) case when `EagerlyAssume` hits a170 // sub-expression of the loop condition (as in this contrived test case).171 // FIXME: It would be good to eventually eliminate this inconsistency, but172 // I don't know a realistic example that could appear in real-world code, so173 // this seems to be a low-priority goal.174 int i;175 for (i = 0; (i >= arg) - 1; i++) {176 clang_analyzer_numTimesReached(); // eagerlyassume-warning {{4}} noeagerlyassume-warning {{2}}177 }178 179 // The 'combo' note intentionally appears if `assume-at-least-one-iteration`180 // is disabled, but also appears as a bug when `eagerly-assume` and181 // `assume-at-least-one-iteration` are both enabled.182 clang_analyzer_dump(i); // combo-warning {{0}} expected-warning {{1}} expected-warning {{2}} eagerlyassume-warning {{3}}183}184 185void calledTwice(int arg, int isFirstCall) {186 // This function is called twice (with two different unknown 'arg' values) to187 // check the iteration count handling in this situation.188 int i;189 for (i = 0; i < arg; i++) {190 if (isFirstCall) {191 clang_analyzer_numTimesReached(); // expected-warning {{2}}192 } else {193 clang_analyzer_numTimesReached(); // expected-warning {{2}}194 }195 }196}197 198void caller(int arg, int arg2) {199 // Entry point for `calledTwice()`.200 calledTwice(arg, 1);201 calledTwice(arg2, 0);202}203 204void innerLoopClearCondition(void) {205 // A "control group" test case for the behavior of an inner loop. Notice that206 // although the (default) value of `-analyzer-max-loop` is 4, we only see 3 iterations207 // of the inner loop, because `-analyzer-max-loop` limits the number of208 // evaluations of _the loop condition of the inner loop_ and in addition to209 // the 3 evaluations before the 3 iterations, there is also a step where it210 // evaluates to false (in the first iteration of the outer loop).211 for (int outer = 0; outer < 2; outer++) {212 int limit = 0;213 if (outer)214 limit = 10;215 clang_analyzer_dump(limit); // expected-warning {{0}} expected-warning {{10}}216 for (int i = 0; i < limit; i++) {217 clang_analyzer_numTimesReached(); // expected-warning {{3}}218 }219 }220}221 222void innerLoopOpaqueCondition(int arg) {223 // In this test case the engine doesn't assume a second iteration within the224 // inner loop (in the second iteration of the outer loop, when the limit is225 // opaque) because `CoreEngine::getCompletedIterationCount()` is based on the226 // `BlockCount` values queried from the `BlockCounter` which count _all_227 // evaluations of a given `CFGBlock` (in our case, the loop condition) and228 // not just the evaluations within the current iteration of the outer loop.229 // FIXME: This inaccurate iteration count could in theory cause some false230 // negatives, although I think this would be unusual in practice, as the231 // small default value of `-analyzer-max-loop` means that this is only232 // relevant if the analyzer can deduce that the inner loop performs 0 or 1233 // iterations within the first iteration of the outer loop (and then the234 // condition of the inner loop is opaque within the second iteration of the235 // outer loop).236 for (int outer = 0; outer < 2; outer++) {237 int limit = 0;238 if (outer)239 limit = arg;240 clang_analyzer_dump(limit); // expected-warning {{0}} expected-warning {{reg_$}}241 for (int i = 0; i < limit; i++) {242 clang_analyzer_numTimesReached(); // expected-warning {{1}}243 }244 }245}246 247void onlyLoopConditions(int arg) {248 // This "don't assume third iteration" logic only examines the conditions of249 // loop statements and does not affect the analysis of code that implements250 // similar behavior with different language features like if + break, goto,251 // recursive functions, ...252 int i = 0;253 while (1) {254 clang_analyzer_numTimesReached(); // expected-warning {{4}}255 256 // This is not a loop condition.257 if (i++ > arg)258 break;259 }260 261 clang_analyzer_dump(i); // expected-warning {{1}} expected-warning {{2}} expected-warning {{3}} expected-warning {{4}}262}263