xref: /freebsd-src/contrib/llvm-project/clang/lib/StaticAnalyzer/Checkers/BitwiseShiftChecker.cpp (revision 5f757f3ff9144b609b3c433dfd370cc6bdc191ad)
1*5f757f3fSDimitry Andric //== BitwiseShiftChecker.cpp ------------------------------------*- C++ -*--==//
2*5f757f3fSDimitry Andric //
3*5f757f3fSDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4*5f757f3fSDimitry Andric // See https://llvm.org/LICENSE.txt for license information.
5*5f757f3fSDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6*5f757f3fSDimitry Andric //
7*5f757f3fSDimitry Andric //===----------------------------------------------------------------------===//
8*5f757f3fSDimitry Andric //
9*5f757f3fSDimitry Andric // This file defines BitwiseShiftChecker, which is a path-sensitive checker
10*5f757f3fSDimitry Andric // that looks for undefined behavior when the operands of the bitwise shift
11*5f757f3fSDimitry Andric // operators '<<' and '>>' are invalid (negative or too large).
12*5f757f3fSDimitry Andric //
13*5f757f3fSDimitry Andric //===----------------------------------------------------------------------===//
14*5f757f3fSDimitry Andric 
15*5f757f3fSDimitry Andric #include "clang/AST/ASTContext.h"
16*5f757f3fSDimitry Andric #include "clang/AST/CharUnits.h"
17*5f757f3fSDimitry Andric #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
18*5f757f3fSDimitry Andric #include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
19*5f757f3fSDimitry Andric #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
20*5f757f3fSDimitry Andric #include "clang/StaticAnalyzer/Core/Checker.h"
21*5f757f3fSDimitry Andric #include "clang/StaticAnalyzer/Core/CheckerManager.h"
22*5f757f3fSDimitry Andric #include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h"
23*5f757f3fSDimitry Andric #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
24*5f757f3fSDimitry Andric #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
25*5f757f3fSDimitry Andric #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
26*5f757f3fSDimitry Andric #include "llvm/Support/FormatVariadic.h"
27*5f757f3fSDimitry Andric #include <memory>
28*5f757f3fSDimitry Andric 
29*5f757f3fSDimitry Andric using namespace clang;
30*5f757f3fSDimitry Andric using namespace ento;
31*5f757f3fSDimitry Andric using llvm::formatv;
32*5f757f3fSDimitry Andric 
33*5f757f3fSDimitry Andric namespace {
34*5f757f3fSDimitry Andric enum class OperandSide { Left, Right };
35*5f757f3fSDimitry Andric 
36*5f757f3fSDimitry Andric using BugReportPtr = std::unique_ptr<PathSensitiveBugReport>;
37*5f757f3fSDimitry Andric 
38*5f757f3fSDimitry Andric struct NoteTagTemplate {
39*5f757f3fSDimitry Andric   llvm::StringLiteral SignInfo;
40*5f757f3fSDimitry Andric   llvm::StringLiteral UpperBoundIntro;
41*5f757f3fSDimitry Andric };
42*5f757f3fSDimitry Andric 
43*5f757f3fSDimitry Andric constexpr NoteTagTemplate NoteTagTemplates[] = {
44*5f757f3fSDimitry Andric   {"", "right operand of bit shift is less than "},
45*5f757f3fSDimitry Andric   {"left operand of bit shift is non-negative", " and right operand is less than "},
46*5f757f3fSDimitry Andric   {"right operand of bit shift is non-negative", " but less than "},
47*5f757f3fSDimitry Andric   {"both operands of bit shift are non-negative", " and right operand is less than "}
48*5f757f3fSDimitry Andric };
49*5f757f3fSDimitry Andric 
50*5f757f3fSDimitry Andric /// An implementation detail class which is introduced to split the checker
51*5f757f3fSDimitry Andric /// logic into several methods while maintaining a consistently updated state
52*5f757f3fSDimitry Andric /// and access to other contextual data.
53*5f757f3fSDimitry Andric class BitwiseShiftValidator {
54*5f757f3fSDimitry Andric   CheckerContext &Ctx;
55*5f757f3fSDimitry Andric   ProgramStateRef FoldedState;
56*5f757f3fSDimitry Andric   const BinaryOperator *const Op;
57*5f757f3fSDimitry Andric   const BugType &BT;
58*5f757f3fSDimitry Andric   const bool PedanticFlag;
59*5f757f3fSDimitry Andric 
60*5f757f3fSDimitry Andric   // The following data members are only used for note tag creation:
61*5f757f3fSDimitry Andric   enum { NonNegLeft = 1, NonNegRight = 2 };
62*5f757f3fSDimitry Andric   unsigned NonNegOperands = 0;
63*5f757f3fSDimitry Andric 
64*5f757f3fSDimitry Andric   std::optional<unsigned> UpperBoundBitCount = std::nullopt;
65*5f757f3fSDimitry Andric 
66*5f757f3fSDimitry Andric public:
BitwiseShiftValidator(const BinaryOperator * O,CheckerContext & C,const BugType & B,bool P)67*5f757f3fSDimitry Andric   BitwiseShiftValidator(const BinaryOperator *O, CheckerContext &C,
68*5f757f3fSDimitry Andric                         const BugType &B, bool P)
69*5f757f3fSDimitry Andric       : Ctx(C), FoldedState(C.getState()), Op(O), BT(B), PedanticFlag(P) {}
70*5f757f3fSDimitry Andric   void run();
71*5f757f3fSDimitry Andric 
72*5f757f3fSDimitry Andric private:
operandExpr(OperandSide Side) const73*5f757f3fSDimitry Andric   const Expr *operandExpr(OperandSide Side) const {
74*5f757f3fSDimitry Andric     return Side == OperandSide::Left ? Op->getLHS() : Op->getRHS();
75*5f757f3fSDimitry Andric   }
76*5f757f3fSDimitry Andric 
shouldPerformPedanticChecks() const77*5f757f3fSDimitry Andric   bool shouldPerformPedanticChecks() const {
78*5f757f3fSDimitry Andric     // The pedantic flag has no effect under C++20 because the affected issues
79*5f757f3fSDimitry Andric     // are no longer undefined under that version of the standard.
80*5f757f3fSDimitry Andric     return PedanticFlag && !Ctx.getASTContext().getLangOpts().CPlusPlus20;
81*5f757f3fSDimitry Andric   }
82*5f757f3fSDimitry Andric 
83*5f757f3fSDimitry Andric   bool assumeRequirement(OperandSide Side, BinaryOperator::Opcode Cmp, unsigned Limit);
84*5f757f3fSDimitry Andric 
85*5f757f3fSDimitry Andric   void recordAssumption(OperandSide Side, BinaryOperator::Opcode Cmp, unsigned Limit);
86*5f757f3fSDimitry Andric   const NoteTag *createNoteTag() const;
87*5f757f3fSDimitry Andric 
88*5f757f3fSDimitry Andric   BugReportPtr createBugReport(StringRef ShortMsg, StringRef Msg) const;
89*5f757f3fSDimitry Andric 
90*5f757f3fSDimitry Andric   BugReportPtr checkOvershift();
91*5f757f3fSDimitry Andric   BugReportPtr checkOperandNegative(OperandSide Side);
92*5f757f3fSDimitry Andric   BugReportPtr checkLeftShiftOverflow();
93*5f757f3fSDimitry Andric 
isLeftShift() const94*5f757f3fSDimitry Andric   bool isLeftShift() const { return Op->getOpcode() == BO_Shl; }
shiftDir() const95*5f757f3fSDimitry Andric   StringRef shiftDir() const { return isLeftShift() ? "left" : "right"; }
pluralSuffix(unsigned n)96*5f757f3fSDimitry Andric   static StringRef pluralSuffix(unsigned n) { return n <= 1 ? "" : "s"; }
verbSuffix(unsigned n)97*5f757f3fSDimitry Andric   static StringRef verbSuffix(unsigned n) { return n <= 1 ? "s" : ""; }
98*5f757f3fSDimitry Andric };
99*5f757f3fSDimitry Andric 
run()100*5f757f3fSDimitry Andric void BitwiseShiftValidator::run() {
101*5f757f3fSDimitry Andric   // Report a bug if the right operand is >= the bit width of the type of the
102*5f757f3fSDimitry Andric   // left operand:
103*5f757f3fSDimitry Andric   if (BugReportPtr BR = checkOvershift()) {
104*5f757f3fSDimitry Andric     Ctx.emitReport(std::move(BR));
105*5f757f3fSDimitry Andric     return;
106*5f757f3fSDimitry Andric   }
107*5f757f3fSDimitry Andric 
108*5f757f3fSDimitry Andric   // Report a bug if the right operand is negative:
109*5f757f3fSDimitry Andric   if (BugReportPtr BR = checkOperandNegative(OperandSide::Right)) {
110*5f757f3fSDimitry Andric     Ctx.emitReport(std::move(BR));
111*5f757f3fSDimitry Andric     return;
112*5f757f3fSDimitry Andric   }
113*5f757f3fSDimitry Andric 
114*5f757f3fSDimitry Andric   if (shouldPerformPedanticChecks()) {
115*5f757f3fSDimitry Andric     // Report a bug if the left operand is negative:
116*5f757f3fSDimitry Andric     if (BugReportPtr BR = checkOperandNegative(OperandSide::Left)) {
117*5f757f3fSDimitry Andric       Ctx.emitReport(std::move(BR));
118*5f757f3fSDimitry Andric       return;
119*5f757f3fSDimitry Andric     }
120*5f757f3fSDimitry Andric 
121*5f757f3fSDimitry Andric     // Report a bug when left shift of a concrete signed value overflows:
122*5f757f3fSDimitry Andric     if (BugReportPtr BR = checkLeftShiftOverflow()) {
123*5f757f3fSDimitry Andric       Ctx.emitReport(std::move(BR));
124*5f757f3fSDimitry Andric       return;
125*5f757f3fSDimitry Andric     }
126*5f757f3fSDimitry Andric   }
127*5f757f3fSDimitry Andric 
128*5f757f3fSDimitry Andric   // No bugs detected, update the state and add a single note tag which
129*5f757f3fSDimitry Andric   // summarizes the new assumptions.
130*5f757f3fSDimitry Andric   Ctx.addTransition(FoldedState, createNoteTag());
131*5f757f3fSDimitry Andric }
132*5f757f3fSDimitry Andric 
133*5f757f3fSDimitry Andric /// This method checks a requirement that must be satisfied by the value on the
134*5f757f3fSDimitry Andric /// given Side of a bitwise shift operator in well-defined code. If the
135*5f757f3fSDimitry Andric /// requirement is incompatible with prior knowledge, this method reports
136*5f757f3fSDimitry Andric /// failure by returning false.
assumeRequirement(OperandSide Side,BinaryOperator::Opcode Comparison,unsigned Limit)137*5f757f3fSDimitry Andric bool BitwiseShiftValidator::assumeRequirement(OperandSide Side,
138*5f757f3fSDimitry Andric                                               BinaryOperator::Opcode Comparison,
139*5f757f3fSDimitry Andric                                               unsigned Limit) {
140*5f757f3fSDimitry Andric   SValBuilder &SVB = Ctx.getSValBuilder();
141*5f757f3fSDimitry Andric 
142*5f757f3fSDimitry Andric   const SVal OperandVal = Ctx.getSVal(operandExpr(Side));
143*5f757f3fSDimitry Andric   const auto LimitVal = SVB.makeIntVal(Limit, Ctx.getASTContext().IntTy);
144*5f757f3fSDimitry Andric   // Note that the type of `LimitVal` must be a signed, because otherwise a
145*5f757f3fSDimitry Andric   // negative `Val` could be converted to a large positive value.
146*5f757f3fSDimitry Andric 
147*5f757f3fSDimitry Andric   auto ResultVal = SVB.evalBinOp(FoldedState, Comparison, OperandVal, LimitVal,
148*5f757f3fSDimitry Andric                                  SVB.getConditionType());
149*5f757f3fSDimitry Andric   if (auto DURes = ResultVal.getAs<DefinedOrUnknownSVal>()) {
150*5f757f3fSDimitry Andric     auto [StTrue, StFalse] = FoldedState->assume(DURes.value());
151*5f757f3fSDimitry Andric     if (!StTrue) {
152*5f757f3fSDimitry Andric       // We detected undefined behavior (the caller will report it).
153*5f757f3fSDimitry Andric       FoldedState = StFalse;
154*5f757f3fSDimitry Andric       return false;
155*5f757f3fSDimitry Andric     }
156*5f757f3fSDimitry Andric     // The code may be valid, so let's assume that it's valid:
157*5f757f3fSDimitry Andric     FoldedState = StTrue;
158*5f757f3fSDimitry Andric     if (StFalse) {
159*5f757f3fSDimitry Andric       // Record note tag data for the assumption that we made
160*5f757f3fSDimitry Andric       recordAssumption(Side, Comparison, Limit);
161*5f757f3fSDimitry Andric     }
162*5f757f3fSDimitry Andric   }
163*5f757f3fSDimitry Andric   return true;
164*5f757f3fSDimitry Andric }
165*5f757f3fSDimitry Andric 
checkOvershift()166*5f757f3fSDimitry Andric BugReportPtr BitwiseShiftValidator::checkOvershift() {
167*5f757f3fSDimitry Andric   const QualType LHSTy = Op->getLHS()->getType();
168*5f757f3fSDimitry Andric   const unsigned LHSBitWidth = Ctx.getASTContext().getIntWidth(LHSTy);
169*5f757f3fSDimitry Andric 
170*5f757f3fSDimitry Andric   if (assumeRequirement(OperandSide::Right, BO_LT, LHSBitWidth))
171*5f757f3fSDimitry Andric     return nullptr;
172*5f757f3fSDimitry Andric 
173*5f757f3fSDimitry Andric   const SVal Right = Ctx.getSVal(operandExpr(OperandSide::Right));
174*5f757f3fSDimitry Andric 
175*5f757f3fSDimitry Andric   std::string RightOpStr = "", LowerBoundStr = "";
176*5f757f3fSDimitry Andric   if (auto ConcreteRight = Right.getAs<nonloc::ConcreteInt>())
177*5f757f3fSDimitry Andric     RightOpStr = formatv(" '{0}'", ConcreteRight->getValue());
178*5f757f3fSDimitry Andric   else {
179*5f757f3fSDimitry Andric     SValBuilder &SVB = Ctx.getSValBuilder();
180*5f757f3fSDimitry Andric     if (const llvm::APSInt *MinRight = SVB.getMinValue(FoldedState, Right)) {
181*5f757f3fSDimitry Andric       LowerBoundStr = formatv(" >= {0},", MinRight->getExtValue());
182*5f757f3fSDimitry Andric     }
183*5f757f3fSDimitry Andric   }
184*5f757f3fSDimitry Andric 
185*5f757f3fSDimitry Andric   std::string ShortMsg = formatv(
186*5f757f3fSDimitry Andric       "{0} shift{1}{2} overflows the capacity of '{3}'",
187*5f757f3fSDimitry Andric       isLeftShift() ? "Left" : "Right", RightOpStr.empty() ? "" : " by",
188*5f757f3fSDimitry Andric       RightOpStr, LHSTy.getAsString());
189*5f757f3fSDimitry Andric   std::string Msg = formatv(
190*5f757f3fSDimitry Andric       "The result of {0} shift is undefined because the right "
191*5f757f3fSDimitry Andric       "operand{1} is{2} not smaller than {3}, the capacity of '{4}'",
192*5f757f3fSDimitry Andric       shiftDir(), RightOpStr, LowerBoundStr, LHSBitWidth, LHSTy.getAsString());
193*5f757f3fSDimitry Andric   return createBugReport(ShortMsg, Msg);
194*5f757f3fSDimitry Andric }
195*5f757f3fSDimitry Andric 
196*5f757f3fSDimitry Andric // Before C++20, at 5.8 [expr.shift] (N4296, 2014-11-19) the standard says
197*5f757f3fSDimitry Andric // 1. "... The behaviour is undefined if the right operand is negative..."
198*5f757f3fSDimitry Andric // 2. "The value of E1 << E2 ...
199*5f757f3fSDimitry Andric //     if E1 has a signed type and non-negative value ...
200*5f757f3fSDimitry Andric //     otherwise, the behavior is undefined."
201*5f757f3fSDimitry Andric // 3. "The value of E1 >> E2 ...
202*5f757f3fSDimitry Andric //     If E1 has a signed type and a negative value,
203*5f757f3fSDimitry Andric //     the resulting value is implementation-defined."
204*5f757f3fSDimitry Andric // However, negative left arguments work in practice and the C++20 standard
205*5f757f3fSDimitry Andric // eliminates conditions 2 and 3.
checkOperandNegative(OperandSide Side)206*5f757f3fSDimitry Andric BugReportPtr BitwiseShiftValidator::checkOperandNegative(OperandSide Side) {
207*5f757f3fSDimitry Andric   // If the type is unsigned, it cannot be negative
208*5f757f3fSDimitry Andric   if (!operandExpr(Side)->getType()->isSignedIntegerType())
209*5f757f3fSDimitry Andric     return nullptr;
210*5f757f3fSDimitry Andric 
211*5f757f3fSDimitry Andric   // Main check: determine whether the operand is constrained to be negative
212*5f757f3fSDimitry Andric   if (assumeRequirement(Side, BO_GE, 0))
213*5f757f3fSDimitry Andric     return nullptr;
214*5f757f3fSDimitry Andric 
215*5f757f3fSDimitry Andric   std::string ShortMsg = formatv("{0} operand is negative in {1} shift",
216*5f757f3fSDimitry Andric                                  Side == OperandSide::Left ? "Left" : "Right",
217*5f757f3fSDimitry Andric                                  shiftDir())
218*5f757f3fSDimitry Andric                              .str();
219*5f757f3fSDimitry Andric   std::string Msg = formatv("The result of {0} shift is undefined "
220*5f757f3fSDimitry Andric                             "because the {1} operand is negative",
221*5f757f3fSDimitry Andric                             shiftDir(),
222*5f757f3fSDimitry Andric                             Side == OperandSide::Left ? "left" : "right")
223*5f757f3fSDimitry Andric                         .str();
224*5f757f3fSDimitry Andric 
225*5f757f3fSDimitry Andric   return createBugReport(ShortMsg, Msg);
226*5f757f3fSDimitry Andric }
227*5f757f3fSDimitry Andric 
checkLeftShiftOverflow()228*5f757f3fSDimitry Andric BugReportPtr BitwiseShiftValidator::checkLeftShiftOverflow() {
229*5f757f3fSDimitry Andric   // A right shift cannot be an overflowing left shift...
230*5f757f3fSDimitry Andric   if (!isLeftShift())
231*5f757f3fSDimitry Andric     return nullptr;
232*5f757f3fSDimitry Andric 
233*5f757f3fSDimitry Andric   // In C++ it's well-defined to shift to the sign bit. In C however, it's UB.
234*5f757f3fSDimitry Andric   // 5.8.2 [expr.shift] (N4296, 2014-11-19)
235*5f757f3fSDimitry Andric   const bool ShouldPreserveSignBit = !Ctx.getLangOpts().CPlusPlus;
236*5f757f3fSDimitry Andric 
237*5f757f3fSDimitry Andric   const Expr *LHS = operandExpr(OperandSide::Left);
238*5f757f3fSDimitry Andric   const QualType LHSTy = LHS->getType();
239*5f757f3fSDimitry Andric   const unsigned LeftBitWidth = Ctx.getASTContext().getIntWidth(LHSTy);
240*5f757f3fSDimitry Andric   assert(LeftBitWidth > 0);
241*5f757f3fSDimitry Andric 
242*5f757f3fSDimitry Andric   // Quote "For unsigned lhs, the value of LHS << RHS is the value of LHS *
243*5f757f3fSDimitry Andric   // 2^RHS, reduced modulo maximum value of the return type plus 1."
244*5f757f3fSDimitry Andric   if (LHSTy->isUnsignedIntegerType())
245*5f757f3fSDimitry Andric     return nullptr;
246*5f757f3fSDimitry Andric 
247*5f757f3fSDimitry Andric   // We only support concrete integers as left operand.
248*5f757f3fSDimitry Andric   const auto Left = Ctx.getSVal(LHS).getAs<nonloc::ConcreteInt>();
249*5f757f3fSDimitry Andric   if (!Left.has_value())
250*5f757f3fSDimitry Andric     return nullptr;
251*5f757f3fSDimitry Andric 
252*5f757f3fSDimitry Andric   // We should have already reported a bug if the left operand of the shift was
253*5f757f3fSDimitry Andric   // negative, so it cannot be negative here.
254*5f757f3fSDimitry Andric   assert(Left->getValue().isNonNegative());
255*5f757f3fSDimitry Andric 
256*5f757f3fSDimitry Andric   const unsigned LeftAvailableBitWidth =
257*5f757f3fSDimitry Andric       LeftBitWidth - static_cast<unsigned>(ShouldPreserveSignBit);
258*5f757f3fSDimitry Andric   const unsigned UsedBitsInLeftOperand = Left->getValue().getActiveBits();
259*5f757f3fSDimitry Andric   assert(LeftBitWidth >= UsedBitsInLeftOperand);
260*5f757f3fSDimitry Andric   const unsigned MaximalAllowedShift =
261*5f757f3fSDimitry Andric       LeftAvailableBitWidth - UsedBitsInLeftOperand;
262*5f757f3fSDimitry Andric 
263*5f757f3fSDimitry Andric   if (assumeRequirement(OperandSide::Right, BO_LT, MaximalAllowedShift + 1))
264*5f757f3fSDimitry Andric     return nullptr;
265*5f757f3fSDimitry Andric 
266*5f757f3fSDimitry Andric   const std::string CapacityMsg =
267*5f757f3fSDimitry Andric       formatv("because '{0}' can hold only {1} bits ({2} the sign bit)",
268*5f757f3fSDimitry Andric                     LHSTy.getAsString(), LeftAvailableBitWidth,
269*5f757f3fSDimitry Andric                     ShouldPreserveSignBit ? "excluding" : "including");
270*5f757f3fSDimitry Andric 
271*5f757f3fSDimitry Andric   const SVal Right = Ctx.getSVal(Op->getRHS());
272*5f757f3fSDimitry Andric 
273*5f757f3fSDimitry Andric   std::string ShortMsg, Msg;
274*5f757f3fSDimitry Andric   if (const auto ConcreteRight = Right.getAs<nonloc::ConcreteInt>()) {
275*5f757f3fSDimitry Andric     // Here ConcreteRight must contain a small non-negative integer, because
276*5f757f3fSDimitry Andric     // otherwise one of the earlier checks should've reported a bug.
277*5f757f3fSDimitry Andric     const unsigned RHS = ConcreteRight->getValue().getExtValue();
278*5f757f3fSDimitry Andric     assert(RHS > MaximalAllowedShift);
279*5f757f3fSDimitry Andric     const unsigned OverflownBits = RHS - MaximalAllowedShift;
280*5f757f3fSDimitry Andric     ShortMsg = formatv(
281*5f757f3fSDimitry Andric         "The shift '{0} << {1}' overflows the capacity of '{2}'",
282*5f757f3fSDimitry Andric         Left->getValue(), ConcreteRight->getValue(), LHSTy.getAsString());
283*5f757f3fSDimitry Andric     Msg = formatv(
284*5f757f3fSDimitry Andric         "The shift '{0} << {1}' is undefined {2}, so {3} bit{4} overflow{5}",
285*5f757f3fSDimitry Andric         Left->getValue(), ConcreteRight->getValue(), CapacityMsg, OverflownBits,
286*5f757f3fSDimitry Andric         pluralSuffix(OverflownBits), verbSuffix(OverflownBits));
287*5f757f3fSDimitry Andric   } else {
288*5f757f3fSDimitry Andric     ShortMsg = formatv("Left shift of '{0}' overflows the capacity of '{1}'",
289*5f757f3fSDimitry Andric                        Left->getValue(), LHSTy.getAsString());
290*5f757f3fSDimitry Andric     Msg = formatv(
291*5f757f3fSDimitry Andric         "Left shift of '{0}' is undefined {1}, so some bits overflow",
292*5f757f3fSDimitry Andric         Left->getValue(), CapacityMsg);
293*5f757f3fSDimitry Andric   }
294*5f757f3fSDimitry Andric 
295*5f757f3fSDimitry Andric   return createBugReport(ShortMsg, Msg);
296*5f757f3fSDimitry Andric }
297*5f757f3fSDimitry Andric 
recordAssumption(OperandSide Side,BinaryOperator::Opcode Comparison,unsigned Limit)298*5f757f3fSDimitry Andric void BitwiseShiftValidator::recordAssumption(OperandSide Side,
299*5f757f3fSDimitry Andric                                              BinaryOperator::Opcode Comparison,
300*5f757f3fSDimitry Andric                                              unsigned Limit) {
301*5f757f3fSDimitry Andric   switch (Comparison)  {
302*5f757f3fSDimitry Andric     case BO_GE:
303*5f757f3fSDimitry Andric       assert(Limit == 0);
304*5f757f3fSDimitry Andric       NonNegOperands |= (Side == OperandSide::Left ? NonNegLeft : NonNegRight);
305*5f757f3fSDimitry Andric       break;
306*5f757f3fSDimitry Andric     case BO_LT:
307*5f757f3fSDimitry Andric       assert(Side == OperandSide::Right);
308*5f757f3fSDimitry Andric       if (!UpperBoundBitCount || Limit < UpperBoundBitCount.value())
309*5f757f3fSDimitry Andric         UpperBoundBitCount = Limit;
310*5f757f3fSDimitry Andric       break;
311*5f757f3fSDimitry Andric     default:
312*5f757f3fSDimitry Andric       llvm_unreachable("this checker does not use other comparison operators");
313*5f757f3fSDimitry Andric   }
314*5f757f3fSDimitry Andric }
315*5f757f3fSDimitry Andric 
createNoteTag() const316*5f757f3fSDimitry Andric const NoteTag *BitwiseShiftValidator::createNoteTag() const {
317*5f757f3fSDimitry Andric   if (!NonNegOperands && !UpperBoundBitCount)
318*5f757f3fSDimitry Andric     return nullptr;
319*5f757f3fSDimitry Andric 
320*5f757f3fSDimitry Andric   SmallString<128> Buf;
321*5f757f3fSDimitry Andric   llvm::raw_svector_ostream Out(Buf);
322*5f757f3fSDimitry Andric   Out << "Assuming ";
323*5f757f3fSDimitry Andric   NoteTagTemplate Templ = NoteTagTemplates[NonNegOperands];
324*5f757f3fSDimitry Andric   Out << Templ.SignInfo;
325*5f757f3fSDimitry Andric   if (UpperBoundBitCount)
326*5f757f3fSDimitry Andric     Out << Templ.UpperBoundIntro << UpperBoundBitCount.value();
327*5f757f3fSDimitry Andric   const std::string Msg(Out.str());
328*5f757f3fSDimitry Andric 
329*5f757f3fSDimitry Andric   return Ctx.getNoteTag(Msg, /*isPrunable=*/true);
330*5f757f3fSDimitry Andric }
331*5f757f3fSDimitry Andric 
332*5f757f3fSDimitry Andric std::unique_ptr<PathSensitiveBugReport>
createBugReport(StringRef ShortMsg,StringRef Msg) const333*5f757f3fSDimitry Andric BitwiseShiftValidator::createBugReport(StringRef ShortMsg, StringRef Msg) const {
334*5f757f3fSDimitry Andric   ProgramStateRef State = Ctx.getState();
335*5f757f3fSDimitry Andric   if (ExplodedNode *ErrNode = Ctx.generateErrorNode(State)) {
336*5f757f3fSDimitry Andric     auto BR =
337*5f757f3fSDimitry Andric         std::make_unique<PathSensitiveBugReport>(BT, ShortMsg, Msg, ErrNode);
338*5f757f3fSDimitry Andric     bugreporter::trackExpressionValue(ErrNode, Op->getLHS(), *BR);
339*5f757f3fSDimitry Andric     bugreporter::trackExpressionValue(ErrNode, Op->getRHS(), *BR);
340*5f757f3fSDimitry Andric     return BR;
341*5f757f3fSDimitry Andric   }
342*5f757f3fSDimitry Andric   return nullptr;
343*5f757f3fSDimitry Andric }
344*5f757f3fSDimitry Andric } // anonymous namespace
345*5f757f3fSDimitry Andric 
346*5f757f3fSDimitry Andric class BitwiseShiftChecker : public Checker<check::PreStmt<BinaryOperator>> {
347*5f757f3fSDimitry Andric   BugType BT{this, "Bitwise shift", "Suspicious operation"};
348*5f757f3fSDimitry Andric 
349*5f757f3fSDimitry Andric public:
checkPreStmt(const BinaryOperator * B,CheckerContext & Ctx) const350*5f757f3fSDimitry Andric   void checkPreStmt(const BinaryOperator *B, CheckerContext &Ctx) const {
351*5f757f3fSDimitry Andric     BinaryOperator::Opcode Op = B->getOpcode();
352*5f757f3fSDimitry Andric 
353*5f757f3fSDimitry Andric     if (Op != BO_Shl && Op != BO_Shr)
354*5f757f3fSDimitry Andric       return;
355*5f757f3fSDimitry Andric 
356*5f757f3fSDimitry Andric     BitwiseShiftValidator(B, Ctx, BT, Pedantic).run();
357*5f757f3fSDimitry Andric   }
358*5f757f3fSDimitry Andric 
359*5f757f3fSDimitry Andric   bool Pedantic = false;
360*5f757f3fSDimitry Andric };
361*5f757f3fSDimitry Andric 
registerBitwiseShiftChecker(CheckerManager & Mgr)362*5f757f3fSDimitry Andric void ento::registerBitwiseShiftChecker(CheckerManager &Mgr) {
363*5f757f3fSDimitry Andric   auto *Chk = Mgr.registerChecker<BitwiseShiftChecker>();
364*5f757f3fSDimitry Andric   const AnalyzerOptions &Opts = Mgr.getAnalyzerOptions();
365*5f757f3fSDimitry Andric   Chk->Pedantic = Opts.getCheckerBooleanOption(Chk, "Pedantic");
366*5f757f3fSDimitry Andric }
367*5f757f3fSDimitry Andric 
shouldRegisterBitwiseShiftChecker(const CheckerManager & mgr)368*5f757f3fSDimitry Andric bool ento::shouldRegisterBitwiseShiftChecker(const CheckerManager &mgr) {
369*5f757f3fSDimitry Andric   return true;
370*5f757f3fSDimitry Andric }
371