clang/test/Analysis/loop-assumptions.c

// 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}}
}