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