Index: clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h =================================================================== --- clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h +++ clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h @@ -116,6 +116,7 @@ RangeSet Intersect(BasicValueFactory &BV, Factory &F, const RangeSet &Other) const; RangeSet Negate(BasicValueFactory &BV, Factory &F) const; + RangeSet Invert(BasicValueFactory &BV, Factory &F) const; void print(raw_ostream &os) const; Index: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp =================================================================== --- clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp +++ clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp @@ -222,6 +222,62 @@ return newRanges; } +// Create new RangeSet with ranges between current ranges +// such that union of them equals to [MIN, MAX] +// and intersection equals to `empty` RangeSet. +// Examples: +// [A, B] => [MIN, A-1] U [B+1, MAX] +// [MIN, A] U [B, B] U [C, MAX] => [A+1, B-1] U [B+1, C-1] +RangeSet RangeSet::Invert(BasicValueFactory &BV, Factory &F) const { + PrimRangeSet newRanges = F.getEmptySet(); + + if (isEmpty()) + return newRanges; + + const llvm::APSInt &sampleValue = getMinValue(); + const llvm::APSInt &MIN = BV.getMinValue(sampleValue); + const llvm::APSInt &MAX = BV.getMaxValue(sampleValue); + + iterator i = begin(); + iterator e = end(); + llvm::APSInt from = i->From(); + llvm::APSInt to = i->To(); + + // assume we have [A, B] U [C, D] + + // Handle case when the first ranges starts from non-MIN value + // [A, B] U [C, D] + // ^ + // [MIN, A-1] add new range here + if (from != MIN) { + newRanges = F.add(newRanges, Range(MIN, BV.getValue(--from))); + } + + // Add intermediate ranges. + // [A, B] U [C, D] + // ^ + // [B+1, C-1] add new range here + ++i; + while (i != e) { + from = i->From(); + const llvm::APSInt &newFrom = BV.getValue(++to); + const llvm::APSInt &newTo = BV.getValue(--from); + newRanges = F.add(newRanges, Range(newFrom, newTo)); + to = i->To(); + ++i; + } + + // Handle case when the last ranges ends to non-MAX value + // [A, B] U [C, D] + // ^ + // [D+1, MAX] add new range here + if (to != MAX) { + newRanges = F.add(newRanges, Range(BV.getValue(++to), MAX)); + } + + return newRanges; +} + void RangeSet::print(raw_ostream &os) const { bool isFirst = true; os << "{ "; @@ -305,8 +361,12 @@ RangeSet::Factory F; RangeSet getRange(ProgramStateRef State, SymbolRef Sym); - const RangeSet* getRangeForMinusSymbol(ProgramStateRef State, - SymbolRef Sym); + const SymSymExpr *getAsComparisonSymSymExpr(SymbolRef Sym); + const RangeSet *getRangeForMinusSymbol(ProgramStateRef State, SymbolRef Sym); + const RangeSet *getRangeForOppositeComparisonSymbol(ProgramStateRef State, + SymbolRef Sym); + const RangeSet *getRangeForReversedComparisonSymbol(ProgramStateRef State, + SymbolRef Sym); RangeSet getSymLTRange(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, @@ -480,14 +540,20 @@ SymbolRef Sym) { ConstraintRangeTy::data_type *V = State->get(Sym); + // Find a range for reversed copy of the symbol + // (for operations comparison only). + // E.g. for (x < y) find (y > x) + if (auto R = getRangeForReversedComparisonSymbol(State, Sym)) + return *R; + // If Sym is a difference of symbols A - B, then maybe we have range set // stored for B - A. - BasicValueFactory &BV = getBasicVals(); const RangeSet *R = getRangeForMinusSymbol(State, Sym); // If we have range set stored for both A - B and B - A then calculate the // effective range set by intersecting the range set for A - B and the // negated range set of B - A. + BasicValueFactory &BV = getBasicVals(); if (V && R) return V->Intersect(BV, F, R->Negate(BV, F)); if (V) @@ -495,6 +561,12 @@ if (R) return R->Negate(BV, F); + // Find a range for opposite symbol (for operations comparison only). + // E.g. for (x < y) find any of + // (x > y), (y < x), (x >= y), (y <= x), (x == y), (y == x) + if (auto R = getRangeForOppositeComparisonSymbol(State, Sym)) + return R->Invert(BV, F); + // Lazily generate a new RangeSet representing all possible values for the // given symbol type. QualType T = Sym->getType(); @@ -538,6 +610,104 @@ return nullptr; } +const SymSymExpr * +RangeConstraintManager::getAsComparisonSymSymExpr(SymbolRef Sym) { + if (auto SSE = dyn_cast(Sym)) { + auto OP = SSE->getOpcode(); + // we currently do not support <=> (C++20) + if (BinaryOperator::isComparisonOp(OP) && (OP != BO_Cmp)) + return SSE; + } + return nullptr; +} + +// Returns ranges only for binary comparison operators +// when left and right operands are symbolic values. +// Finds opposite expression in the ConstraintRange map. +// E.g. Conditions (x >= y), (y <= x), (x == y) makes this (x < y) false. +// Then the result should be inverted for futher intersection. +const RangeSet *RangeConstraintManager::getRangeForOppositeComparisonSymbol( + ProgramStateRef State, SymbolRef Sym) { + auto SSE = getAsComparisonSymSymExpr(Sym); + if (!SSE) + return nullptr; + + SmallVector Ops; + + switch (SSE->getOpcode()) { + case BO_LT: + Ops.push_back(BO_GT); + Ops.push_back(BO_GE); + Ops.push_back(BO_EQ); + break; + case BO_LE: + Ops.push_back(BO_GT); + break; + case BO_GT: + Ops.push_back(BO_LT); + Ops.push_back(BO_LE); + Ops.push_back(BO_EQ); + break; + case BO_GE: + Ops.push_back(BO_LT); + break; + case BO_EQ: + Ops.push_back(BO_LT); + Ops.push_back(BO_GT); + Ops.push_back(BO_NE); + break; + case BO_NE: + Ops.push_back(BO_EQ); + break; + default: + llvm_unreachable("Given 'BinaryOperator::Opcode' is not supported here"); + break; + } + + auto LHS = SSE->getLHS(); + auto RHS = SSE->getRHS(); + QualType T = SSE->getType(); + SymbolManager &SymMgr = State->getSymbolManager(); + + // Assume we have (x < y). + const RangeSet *RangeSet = nullptr; + for (auto OP : Ops) { + // Let's find any of (x >= y), (x > y), (x == y). + auto SymSym = SymMgr.getSymSymExpr(LHS, OP, RHS, T); + if (RangeSet = State->get(SymSym)) + break; + + // Or let's find any of (y <= x), (y < x), (y == x). + auto ROP = BinaryOperator::reverseComparisonOp(OP); + SymSym = SymMgr.getSymSymExpr(RHS, ROP, LHS, T); + if (RangeSet = State->get(SymSym)) + break; + } + return RangeSet; +} + +// Gets ranges only for binary comparison operators +// when left and right operands are symbolic values. +// Finds reversed expression in the ConstraintRange map. +// E.g. (x >= y) is reversed to (y <= x) +const RangeSet *RangeConstraintManager::getRangeForReversedComparisonSymbol( + ProgramStateRef State, SymbolRef Sym) { + auto SSE = getAsComparisonSymSymExpr(Sym); + if (!SSE) + return nullptr; + + // Assume we have (x < y). + // Let's find (y > x). + auto LHS = SSE->getLHS(); + auto RHS = SSE->getRHS(); + auto OP = SSE->getOpcode(); + auto ROP = BinaryOperator::reverseComparisonOp(OP); + QualType T = SSE->getType(); + SymbolManager &SymMgr = State->getSymbolManager(); + auto SymSym = SymMgr.getSymSymExpr(RHS, ROP, LHS, T); + return State->get(SymSym); +} + //===------------------------------------------------------------------------=== // assumeSymX methods: protected interface for RangeConstraintManager. //===------------------------------------------------------------------------===/ Index: clang/test/Analysis/constraint_manager_conditions.cpp =================================================================== --- /dev/null +++ clang/test/Analysis/constraint_manager_conditions.cpp @@ -0,0 +1,109 @@ +// RUN: %clang_analyze_cc1 -analyzer-checker=debug.ExprInspection -verify %s + +void clang_analyzer_eval(int); + +//reversed + +void comparison_reversed_gt(int x, int y) { + if (x > y) + clang_analyzer_eval(y < x); // expected-warning{{TRUE}} + else + clang_analyzer_eval(y < x); // expected-warning{{FALSE}} +} + +void comparison_reversed_ge(int x, int y) { + if (x >= y) + clang_analyzer_eval(y <= x); // expected-warning{{TRUE}} + else + clang_analyzer_eval(y <= x); // expected-warning{{FALSE}} +} + +void comparison_reversed_lt(int x, int y) { + if (x < y) + clang_analyzer_eval(y > x); // expected-warning{{TRUE}} + else + clang_analyzer_eval(y > x); // expected-warning{{FALSE}} +} + +void comparison_reversed_le(int x, int y) { + if (x <= y) + clang_analyzer_eval(y >= x); // expected-warning{{TRUE}} + else + clang_analyzer_eval(y >= x); // expected-warning{{FALSE}} +} + +void comparison_reversed_eq(int x, int y) { + if (x == y) + clang_analyzer_eval(y == x); // expected-warning{{TRUE}} + else + clang_analyzer_eval(y == x); // expected-warning{{FALSE}} +} + +void comparison_reversed_ne(int x, int y) { + if (x != y) + clang_analyzer_eval(y != x); // expected-warning{{TRUE}} + else + clang_analyzer_eval(y != x); // expected-warning{{FALSE}} +} + +//opposite + +void comparison_opposite_gt(int x, int y) { + if (x > y) { + clang_analyzer_eval(x <= y); // expected-warning{{FALSE}} + clang_analyzer_eval(y >= x); // expected-warning{{FALSE}} + } else { + clang_analyzer_eval(x <= y); // expected-warning{{TRUE}} + clang_analyzer_eval(y >= x); // expected-warning{{TRUE}} + } +} + +void comparison_opposite_ge(int x, int y) { + if (x >= y) { + clang_analyzer_eval(x < y); // expected-warning{{FALSE}} + clang_analyzer_eval(y > x); // expected-warning{{FALSE}} + } else { + clang_analyzer_eval(x < y); // expected-warning{{TRUE}} + clang_analyzer_eval(y > x); // expected-warning{{TRUE}} + } +} + +void comparison_opposite_lt(int x, int y) { + if (x < y) { + clang_analyzer_eval(x >= y); // expected-warning{{FALSE}} + clang_analyzer_eval(y <= x); // expected-warning{{FALSE}} + } else { + clang_analyzer_eval(x >= y); // expected-warning{{TRUE}} + clang_analyzer_eval(y <= x); // expected-warning{{TRUE}} + } +} + +void comparison_opposite_le(int x, int y) { + if (x <= y) { + clang_analyzer_eval(x > y); // expected-warning{{FALSE}} + clang_analyzer_eval(y < x); // expected-warning{{FALSE}} + } else { + clang_analyzer_eval(x > y); // expected-warning{{TRUE}} + clang_analyzer_eval(y < x); // expected-warning{{TRUE}} + } +} + +void comparison_opposite_eq(int x, int y) { + if (x == y) { + clang_analyzer_eval(x != y); // expected-warning{{FALSE}} + clang_analyzer_eval(y != x); // expected-warning{{FALSE}} + } else { + clang_analyzer_eval(x != y); // expected-warning{{TRUE}} + clang_analyzer_eval(y != x); // expected-warning{{TRUE}} + } +} + +void comparison_opposite_ne(int x, int y) { + if (x != y) { + clang_analyzer_eval(x == y); // expected-warning{{FALSE}} + clang_analyzer_eval(y == x); // expected-warning{{FALSE}} + } else { + clang_analyzer_eval(x == y); // expected-warning{{TRUE}} + clang_analyzer_eval(y == x); // expected-warning{{TRUE}} + } +}