clang/test/Analysis/loop-assumptions.c

   1 // RUN: %clang_analyze_cc1 -analyzer-checker=debug.ExprInspection \
   2 // RUN:     -verify=expected,eagerlyassume %s
   3 // RUN: %clang_analyze_cc1 -analyzer-checker=debug.ExprInspection \
   4 // RUN:     -analyzer-config eagerly-assume=false \
   5 // RUN:     -verify=expected,noeagerlyassume %s
   6
   7 // These tests validate the logic within `ExprEngine::processBranch` which
   8 // ensures that in loops with opaque conditions we don't assume execution paths
   9 // if the code does not imply that they are possible.
  10
  11 void clang_analyzer_numTimesReached(void);
  12 void clang_analyzer_warnIfReached(void);
  13 void clang_analyzer_dump(int);
  14
  15 void clearCondition(void) {
  16   // If the analyzer can definitely determine the value of the loop condition,
  17   // then this corrective logic doesn't activate and the engine executes
  18   // `-analyzer-max-loop` iterations (by default, 4).
  19   for (int i = 0; i < 10; i++)
  20     clang_analyzer_numTimesReached(); // expected-warning {{4}}
  21
  22   clang_analyzer_warnIfReached(); // unreachable
  23 }
  24
  25 void opaqueCondition(int arg) {
  26   // If the loop condition is opaque, don't assume more than two iterations,
  27   // because the presence of a loop does not imply that the programmer thought
  28   // that more than two iterations are possible. (It _does_ imply that two
  29   // iterations may be possible at least in some cases, because otherwise an
  30   // `if` would've been enough.)
  31   for (int i = 0; i < arg; i++)
  32     clang_analyzer_numTimesReached(); // expected-warning {{2}}
  33
  34   clang_analyzer_warnIfReached(); // expected-warning {{REACHABLE}}
  35 }
  36
  37 int check(void);
  38
  39 void opaqueConditionCall(int arg) {
  40   // Same situation as `opaqueCondition()` but with a `while ()` loop. This
  41   // is also an example for a situation where the programmer cannot easily
  42   // insert an assertion to guide the analyzer and rule out more than two
  43   // iterations (so the analyzer needs to proactively avoid those unjustified
  44   // branches).
  45   while (check())
  46     clang_analyzer_numTimesReached(); // expected-warning {{2}}
  47
  48   clang_analyzer_warnIfReached(); // expected-warning {{REACHABLE}}
  49 }
  50
  51 void opaqueConditionDoWhile(int arg) {
  52   // Same situation as `opaqueCondition()` but with a `do {} while ()` loop.
  53   // This is tested separately because this loop type is a special case in the
  54   // iteration count calculation.
  55   int i = 0;
  56   do {
  57     clang_analyzer_numTimesReached(); // expected-warning {{2}}
  58   } while (i++ < arg);
  59
  60   clang_analyzer_warnIfReached(); // expected-warning {{REACHABLE}}
  61 }
  62
  63 void dontRememberOldBifurcation(int arg) {
  64   // In this (slightly contrived) test case the analyzer performs an assumption
  65   // at the first iteration of the loop, but does not make any new assumptions
  66   // in the subsequent iterations, so the analyzer should continue evaluating
  67   // the loop.
  68   // Previously this was mishandled in `eagerly-assume` mode (which is enabled
  69   // by default), because the code remembered that there was a bifurcation on
  70   // the first iteration of the loop and didn't realize that this is obsolete.
  71
  72   // NOTE: The variable `i` is introduced to ensure that the iterations of the
  73   // loop change the state -- otherwise the analyzer stops iterating because it
  74   // returns to the same `ExplodedNode`.
  75   int i = 0;
  76   while (arg > 3) {
  77     clang_analyzer_numTimesReached(); // expected-warning {{4}}
  78     i++;
  79   }
  80
  81   clang_analyzer_warnIfReached(); // expected-warning {{REACHABLE}}
  82 }
  83
  84 void dontAssumeFourthIterartion(int arg) {
  85   if (arg == 2)
  86     return;
  87
  88   // In this function the analyzer cannot leave the loop after exactly two
  89   // iterations (because it knows that `arg != 2` at that point), so it
  90   // performs a third iteration, but it does not assume that a fourth iteration
  91   // is also possible.
  92   for (int i = 0; i < arg; i++)
  93     clang_analyzer_numTimesReached(); // expected-warning {{3}}
  94
  95   clang_analyzer_warnIfReached(); // expected-warning {{REACHABLE}}
  96 }
  97
  98 #define TRUE 1
  99 void shortCircuitInLoopCondition(int arg) {
 100   // When the loop condition expression contains short-circuiting operators, it
 101   // performs "inner" bifurcations for those operators and only considers the
 102   // last (rightmost) operand as the branch condition that is associated with
 103   // the loop itself (as its loop condition).
 104   // This means that assumptions taken in the left-hand side of a short-circuiting
 105   // operator are not recognized as "opaque" loop condition, so the loop in
 106   // this test case is allowed to finish four iterations.
 107   // FIXME: This corner case is responsible for at least one out-of-bounds
 108   // false positive on the ffmpeg codebase. Eventually we should properly
 109   // recognize the full syntactical loop condition expression as "the loop
 110   // condition", but this will be complicated to implement.
 111   for (int i = 0; i < arg && TRUE; i++) {
 112     clang_analyzer_numTimesReached(); // expected-warning {{4}}
 113   }
 114   clang_analyzer_warnIfReached(); // expected-warning {{REACHABLE}}
 115 }
 116
 117 void shortCircuitInLoopConditionRHS(int arg) {
 118   // Unlike `shortCircuitInLoopCondition()`, this case is handled properly
 119   // because the analyzer thinks that the right hand side of the `&&` is the
 120   // loop condition.
 121   for (int i = 0; TRUE && i < arg; i++) {
 122     clang_analyzer_numTimesReached(); // expected-warning {{2}}
 123   }
 124   clang_analyzer_warnIfReached(); // expected-warning {{REACHABLE}}
 125 }
 126
 127 void eagerlyAssumeInSubexpression(int arg) {
 128   // The `EagerlyAssume` logic is another complication that can "split the
 129   // state" within the loop condition, but before the `processBranch()` call
 130   // which is (in theory) responsible for evaluating the loop condition.
 131   // The current implementation partially compensates this by noticing the
 132   // cases where the loop condition is targeted by `EagerlyAssume`, but does
 133   // not handle the (fortunately rare) case when `EagerlyAssume` hits a
 134   // sub-expression of the loop condition (as in this contrived test case).
 135   // FIXME: I don't know a real-world example for this inconsistency, but it
 136   // would be good to eliminate it eventually.
 137   for (int i = 0; (i >= arg) - 1; i++) {
 138     clang_analyzer_numTimesReached(); // eagerlyassume-warning {{4}} noeagerlyassume-warning {{2}}
 139   }
 140   clang_analyzer_warnIfReached(); // expected-warning {{REACHABLE}}
 141 }
 142
 143 void calledTwice(int arg, int isFirstCall) {
 144   // This function is called twice (with two different unknown 'arg' values) to
 145   // check the iteration count handling in this situation.
 146   for (int i = 0; i < arg; i++) {
 147     if (isFirstCall) {
 148       clang_analyzer_numTimesReached(); // expected-warning {{2}}
 149     } else {
 150       clang_analyzer_numTimesReached(); // expected-warning {{2}}
 151     }
 152   }
 153 }
 154
 155 void caller(int arg, int arg2) {
 156   // Entry point for `calledTwice()`.
 157   calledTwice(arg, 1);
 158   calledTwice(arg2, 0);
 159 }
 160
 161 void innerLoopClearCondition(void) {
 162   // A "control group" test case for the behavior of an inner loop. Notice that
 163   // although the (default) value of `-analyzer-max-loop` is 4, we only see 3 iterations
 164   // of the inner loop, because `-analyzer-max-loop` limits the number of
 165   // evaluations of _the loop condition of the inner loop_ and in addition to
 166   // the 3 evaluations before the 3 iterations, there is also a step where it
 167   // evaluates to false (in the first iteration of the outer loop).
 168   for (int outer = 0; outer < 2; outer++) {
 169     int limit = 0;
 170     if (outer)
 171       limit = 10;
 172     clang_analyzer_dump(limit); // expected-warning {{0}} expected-warning {{10}}
 173     for (int i = 0; i < limit; i++) {
 174       clang_analyzer_numTimesReached(); // expected-warning {{3}}
 175     }
 176   }
 177 }
 178
 179 void innerLoopOpaqueCondition(int arg) {
 180   // In this test case the engine doesn't assume a second iteration within the
 181   // inner loop (in the second iteration of the outer loop, when the limit is
 182   // opaque) because `CoreEngine::getCompletedIterationCount()` is based on the
 183   // `BlockCount` values queried from the `BlockCounter` which count _all_
 184   // evaluations of a given `CFGBlock` (in our case, the loop condition) and
 185   // not just the evaluations within the current iteration of the outer loop.
 186   // FIXME: This inaccurate iteration count could in theory cause some false
 187   // negatives, although I think this would be unusual in practice, as the
 188   // small default value of `-analyzer-max-loop` means that this is only
 189   // relevant if the analyzer can deduce that the inner loop performs 0 or 1
 190   // iterations within the first iteration of the outer loop (and then the
 191   // condition of the inner loop is opaque within the second iteration of the
 192   // outer loop).
 193   for (int outer = 0; outer < 2; outer++) {
 194     int limit = 0;
 195     if (outer)
 196       limit = arg;
 197     clang_analyzer_dump(limit); // expected-warning {{0}} expected-warning {{reg_$}}
 198     for (int i = 0; i < limit; i++) {
 199       clang_analyzer_numTimesReached(); // expected-warning {{1}}
 200     }
 201   }
 202 }
 203
 204 void onlyLoopConditions(int arg) {
 205   // This "don't assume third iteration" logic only examines the conditions of
 206   // loop statements and does not affect the analysis of code that implements
 207   // similar behavior with different language features like if + break, goto,
 208   // recursive functions, ...
 209   int i = 0;
 210   while (1) {
 211     clang_analyzer_numTimesReached(); // expected-warning {{4}}
 212
 213     // This is not a loop condition.
 214     if (i++ > arg)
 215       break;
 216   }
 217
 218   clang_analyzer_warnIfReached(); // expected-warning {{REACHABLE}}
 219 }