| 1 |
//===-- ContainerModeling.cpp -------------------------------------*- C++ -*--// |
| 2 |
// |
| 3 |
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| 4 |
// See https://llvm.org/LICENSE.txt for license information. |
| 5 |
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| 6 |
// |
| 7 |
//===----------------------------------------------------------------------===// |
| 8 |
// |
| 9 |
// Defines a modeling-checker for modeling STL container-like containers. |
| 10 |
// |
| 11 |
//===----------------------------------------------------------------------===// |
| 12 |
|
| 13 |
#include "clang/AST/DeclTemplate.h" |
| 14 |
#include "clang/Driver/DriverDiagnostic.h" |
| 15 |
#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h" |
| 16 |
#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" |
| 17 |
#include "clang/StaticAnalyzer/Core/Checker.h" |
| 18 |
#include "clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h" |
| 19 |
#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" |
| 20 |
#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" |
| 21 |
#include "clang/StaticAnalyzer/Core/PathSensitive/DynamicType.h" |
| 22 |
|
| 23 |
#include "Iterator.h" |
| 24 |
|
| 25 |
#include <utility> |
| 26 |
|
| 27 |
using namespace clang; |
| 28 |
using namespace ento; |
| 29 |
using namespace iterator; |
| 30 |
|
| 31 |
namespace { |
| 32 |
|
| 33 |
class ContainerModeling |
| 34 |
: public Checker<check::PostCall, check::LiveSymbols, check::DeadSymbols> { |
| 35 |
|
| 36 |
void handleBegin(CheckerContext &C, const Expr *CE, SVal RetVal, |
| 37 |
SVal Cont) const; |
| 38 |
void handleEnd(CheckerContext &C, const Expr *CE, SVal RetVal, |
| 39 |
SVal Cont) const; |
| 40 |
void handleAssignment(CheckerContext &C, SVal Cont, const Expr *CE = nullptr, |
| 41 |
SVal OldCont = UndefinedVal()) const; |
| 42 |
void handleAssign(CheckerContext &C, SVal Cont, const Expr *ContE) const; |
| 43 |
void handleClear(CheckerContext &C, SVal Cont, const Expr *ContE) const; |
| 44 |
void handlePushBack(CheckerContext &C, SVal Cont, const Expr *ContE) const; |
| 45 |
void handlePopBack(CheckerContext &C, SVal Cont, const Expr *ContE) const; |
| 46 |
void handlePushFront(CheckerContext &C, SVal Cont, const Expr *ContE) const; |
| 47 |
void handlePopFront(CheckerContext &C, SVal Cont, const Expr *ContE) const; |
| 48 |
void handleInsert(CheckerContext &C, SVal Cont, SVal Iter) const; |
| 49 |
void handleErase(CheckerContext &C, SVal Cont, SVal Iter) const; |
| 50 |
void handleErase(CheckerContext &C, SVal Cont, SVal Iter1, SVal Iter2) const; |
| 51 |
void handleEraseAfter(CheckerContext &C, SVal Cont, SVal Iter) const; |
| 52 |
void handleEraseAfter(CheckerContext &C, SVal Cont, SVal Iter1, |
| 53 |
SVal Iter2) const; |
| 54 |
const NoteTag *getChangeTag(CheckerContext &C, StringRef Text, |
| 55 |
const MemRegion *ContReg, |
| 56 |
const Expr *ContE) const; |
| 57 |
void printState(raw_ostream &Out, ProgramStateRef State, const char *NL, |
| 58 |
const char *Sep) const override; |
| 59 |
|
| 60 |
public: |
| 61 |
ContainerModeling() = default; |
| 62 |
|
| 63 |
void checkPostCall(const CallEvent &Call, CheckerContext &C) const; |
| 64 |
void checkLiveSymbols(ProgramStateRef State, SymbolReaper &SR) const; |
| 65 |
void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const; |
| 66 |
|
| 67 |
using NoItParamFn = void (ContainerModeling::*)(CheckerContext &, SVal, |
| 68 |
const Expr *) const; |
| 69 |
using OneItParamFn = void (ContainerModeling::*)(CheckerContext &, SVal, |
| 70 |
SVal) const; |
| 71 |
using TwoItParamFn = void (ContainerModeling::*)(CheckerContext &, SVal, SVal, |
| 72 |
SVal) const; |
| 73 |
|
| 74 |
CallDescriptionMap<NoItParamFn> NoIterParamFunctions = { |
| 75 |
{{{"clear"}, 0}, &ContainerModeling::handleClear}, |
| 76 |
{{{"assign"}, 2}, &ContainerModeling::handleAssign}, |
| 77 |
{{{"push_back"}, 1}, &ContainerModeling::handlePushBack}, |
| 78 |
{{{"emplace_back"}, 1}, &ContainerModeling::handlePushBack}, |
| 79 |
{{{"pop_back"}, 0}, &ContainerModeling::handlePopBack}, |
| 80 |
{{{"push_front"}, 1}, &ContainerModeling::handlePushFront}, |
| 81 |
{{{"emplace_front"}, 1}, &ContainerModeling::handlePushFront}, |
| 82 |
{{{"pop_front"}, 0}, &ContainerModeling::handlePopFront}, |
| 83 |
}; |
| 84 |
|
| 85 |
CallDescriptionMap<OneItParamFn> OneIterParamFunctions = { |
| 86 |
{{{"insert"}, 2}, &ContainerModeling::handleInsert}, |
| 87 |
{{{"emplace"}, 2}, &ContainerModeling::handleInsert}, |
| 88 |
{{{"erase"}, 1}, &ContainerModeling::handleErase}, |
| 89 |
{{{"erase_after"}, 1}, &ContainerModeling::handleEraseAfter}, |
| 90 |
}; |
| 91 |
|
| 92 |
CallDescriptionMap<TwoItParamFn> TwoIterParamFunctions = { |
| 93 |
{{{"erase"}, 2}, &ContainerModeling::handleErase}, |
| 94 |
{{{"erase_after"}, 2}, &ContainerModeling::handleEraseAfter}, |
| 95 |
}; |
| 96 |
}; |
| 97 |
|
| 98 |
bool isBeginCall(const FunctionDecl *Func); |
| 99 |
bool isEndCall(const FunctionDecl *Func); |
| 100 |
bool hasSubscriptOperator(ProgramStateRef State, const MemRegion *Reg); |
| 101 |
bool frontModifiable(ProgramStateRef State, const MemRegion *Reg); |
| 102 |
bool backModifiable(ProgramStateRef State, const MemRegion *Reg); |
| 103 |
SymbolRef getContainerBegin(ProgramStateRef State, const MemRegion *Cont); |
| 104 |
SymbolRef getContainerEnd(ProgramStateRef State, const MemRegion *Cont); |
| 105 |
ProgramStateRef createContainerBegin(ProgramStateRef State, |
| 106 |
const MemRegion *Cont, const Expr *E, |
| 107 |
QualType T, const LocationContext *LCtx, |
| 108 |
unsigned BlockCount); |
| 109 |
ProgramStateRef createContainerEnd(ProgramStateRef State, const MemRegion *Cont, |
| 110 |
const Expr *E, QualType T, |
| 111 |
const LocationContext *LCtx, |
| 112 |
unsigned BlockCount); |
| 113 |
ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont, |
| 114 |
const ContainerData &CData); |
| 115 |
ProgramStateRef invalidateAllIteratorPositions(ProgramStateRef State, |
| 116 |
const MemRegion *Cont); |
| 117 |
ProgramStateRef |
| 118 |
invalidateAllIteratorPositionsExcept(ProgramStateRef State, |
| 119 |
const MemRegion *Cont, SymbolRef Offset, |
| 120 |
BinaryOperator::Opcode Opc); |
| 121 |
ProgramStateRef invalidateIteratorPositions(ProgramStateRef State, |
| 122 |
SymbolRef Offset, |
| 123 |
BinaryOperator::Opcode Opc); |
| 124 |
ProgramStateRef invalidateIteratorPositions(ProgramStateRef State, |
| 125 |
SymbolRef Offset1, |
| 126 |
BinaryOperator::Opcode Opc1, |
| 127 |
SymbolRef Offset2, |
| 128 |
BinaryOperator::Opcode Opc2); |
| 129 |
ProgramStateRef reassignAllIteratorPositions(ProgramStateRef State, |
| 130 |
const MemRegion *Cont, |
| 131 |
const MemRegion *NewCont); |
| 132 |
ProgramStateRef reassignAllIteratorPositionsUnless(ProgramStateRef State, |
| 133 |
const MemRegion *Cont, |
| 134 |
const MemRegion *NewCont, |
| 135 |
SymbolRef Offset, |
| 136 |
BinaryOperator::Opcode Opc); |
| 137 |
ProgramStateRef rebaseSymbolInIteratorPositionsIf( |
| 138 |
ProgramStateRef State, SValBuilder &SVB, SymbolRef OldSym, |
| 139 |
SymbolRef NewSym, SymbolRef CondSym, BinaryOperator::Opcode Opc); |
| 140 |
SymbolRef rebaseSymbol(ProgramStateRef State, SValBuilder &SVB, SymbolRef Expr, |
| 141 |
SymbolRef OldSym, SymbolRef NewSym); |
| 142 |
bool hasLiveIterators(ProgramStateRef State, const MemRegion *Cont); |
| 143 |
|
| 144 |
} // namespace |
| 145 |
|
| 146 |
void ContainerModeling::checkPostCall(const CallEvent &Call, |
| 147 |
CheckerContext &C) const { |
| 148 |
const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl()); |
| 149 |
if (!Func) |
| 150 |
return; |
| 151 |
|
| 152 |
if (Func->isOverloadedOperator()) { |
| 153 |
const auto Op = Func->getOverloadedOperator(); |
| 154 |
if (Op == OO_Equal) { |
| 155 |
// Overloaded 'operator=' must be a non-static member function. |
| 156 |
const auto *InstCall = cast<CXXInstanceCall>(&Call); |
| 157 |
if (cast<CXXMethodDecl>(Func)->isMoveAssignmentOperator()) { |
| 158 |
handleAssignment(C, InstCall->getCXXThisVal(), Call.getOriginExpr(), |
| 159 |
Call.getArgSVal(0)); |
| 160 |
return; |
| 161 |
} |
| 162 |
|
| 163 |
handleAssignment(C, InstCall->getCXXThisVal()); |
| 164 |
return; |
| 165 |
} |
| 166 |
} else { |
| 167 |
if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) { |
| 168 |
const NoItParamFn *Handler0 = NoIterParamFunctions.lookup(Call); |
| 169 |
if (Handler0) { |
| 170 |
(this->**Handler0)(C, InstCall->getCXXThisVal(), |
| 171 |
InstCall->getCXXThisExpr()); |
| 172 |
return; |
| 173 |
} |
| 174 |
|
| 175 |
const OneItParamFn *Handler1 = OneIterParamFunctions.lookup(Call); |
| 176 |
if (Handler1) { |
| 177 |
(this->**Handler1)(C, InstCall->getCXXThisVal(), Call.getArgSVal(0)); |
| 178 |
return; |
| 179 |
} |
| 180 |
|
| 181 |
const TwoItParamFn *Handler2 = TwoIterParamFunctions.lookup(Call); |
| 182 |
if (Handler2) { |
| 183 |
(this->**Handler2)(C, InstCall->getCXXThisVal(), Call.getArgSVal(0), |
| 184 |
Call.getArgSVal(1)); |
| 185 |
return; |
| 186 |
} |
| 187 |
|
| 188 |
const auto *OrigExpr = Call.getOriginExpr(); |
| 189 |
if (!OrigExpr) |
| 190 |
return; |
| 191 |
|
| 192 |
if (isBeginCall(Func)) { |
| 193 |
handleBegin(C, OrigExpr, Call.getReturnValue(), |
| 194 |
InstCall->getCXXThisVal()); |
| 195 |
return; |
| 196 |
} |
| 197 |
|
| 198 |
if (isEndCall(Func)) { |
| 199 |
handleEnd(C, OrigExpr, Call.getReturnValue(), |
| 200 |
InstCall->getCXXThisVal()); |
| 201 |
return; |
| 202 |
} |
| 203 |
} |
| 204 |
} |
| 205 |
} |
| 206 |
|
| 207 |
void ContainerModeling::checkLiveSymbols(ProgramStateRef State, |
| 208 |
SymbolReaper &SR) const { |
| 209 |
// Keep symbolic expressions of container begins and ends alive |
| 210 |
auto ContMap = State->get<ContainerMap>(); |
| 211 |
for (const auto &Cont : ContMap) { |
| 212 |
const auto CData = Cont.second; |
| 213 |
if (CData.getBegin()) { |
| 214 |
SR.markLive(CData.getBegin()); |
| 215 |
if(const auto *SIE = dyn_cast<SymIntExpr>(CData.getBegin())) |
| 216 |
SR.markLive(SIE->getLHS()); |
| 217 |
} |
| 218 |
if (CData.getEnd()) { |
| 219 |
SR.markLive(CData.getEnd()); |
| 220 |
if(const auto *SIE = dyn_cast<SymIntExpr>(CData.getEnd())) |
| 221 |
SR.markLive(SIE->getLHS()); |
| 222 |
} |
| 223 |
} |
| 224 |
} |
| 225 |
|
| 226 |
void ContainerModeling::checkDeadSymbols(SymbolReaper &SR, |
| 227 |
CheckerContext &C) const { |
| 228 |
// Cleanup |
| 229 |
auto State = C.getState(); |
| 230 |
|
| 231 |
auto ContMap = State->get<ContainerMap>(); |
| 232 |
for (const auto &Cont : ContMap) { |
| 233 |
if (!SR.isLiveRegion(Cont.first)) { |
| 234 |
// We must keep the container data while it has live iterators to be able |
| 235 |
// to compare them to the begin and the end of the container. |
| 236 |
if (!hasLiveIterators(State, Cont.first)) { |
| 237 |
State = State->remove<ContainerMap>(Cont.first); |
| 238 |
} |
| 239 |
} |
| 240 |
} |
| 241 |
|
| 242 |
C.addTransition(State); |
| 243 |
} |
| 244 |
|
| 245 |
void ContainerModeling::handleBegin(CheckerContext &C, const Expr *CE, |
| 246 |
SVal RetVal, SVal Cont) const { |
| 247 |
const auto *ContReg = Cont.getAsRegion(); |
| 248 |
if (!ContReg) |
| 249 |
return; |
| 250 |
|
| 251 |
ContReg = ContReg->getMostDerivedObjectRegion(); |
| 252 |
|
| 253 |
// If the container already has a begin symbol then use it. Otherwise first |
| 254 |
// create a new one. |
| 255 |
auto State = C.getState(); |
| 256 |
auto BeginSym = getContainerBegin(State, ContReg); |
| 257 |
if (!BeginSym) { |
| 258 |
State = createContainerBegin(State, ContReg, CE, C.getASTContext().LongTy, |
| 259 |
C.getLocationContext(), C.blockCount()); |
| 260 |
BeginSym = getContainerBegin(State, ContReg); |
| 261 |
} |
| 262 |
State = setIteratorPosition(State, RetVal, |
| 263 |
IteratorPosition::getPosition(ContReg, BeginSym)); |
| 264 |
C.addTransition(State); |
| 265 |
} |
| 266 |
|
| 267 |
void ContainerModeling::handleEnd(CheckerContext &C, const Expr *CE, |
| 268 |
SVal RetVal, SVal Cont) const { |
| 269 |
const auto *ContReg = Cont.getAsRegion(); |
| 270 |
if (!ContReg) |
| 271 |
return; |
| 272 |
|
| 273 |
ContReg = ContReg->getMostDerivedObjectRegion(); |
| 274 |
|
| 275 |
// If the container already has an end symbol then use it. Otherwise first |
| 276 |
// create a new one. |
| 277 |
auto State = C.getState(); |
| 278 |
auto EndSym = getContainerEnd(State, ContReg); |
| 279 |
if (!EndSym) { |
| 280 |
State = createContainerEnd(State, ContReg, CE, C.getASTContext().LongTy, |
| 281 |
C.getLocationContext(), C.blockCount()); |
| 282 |
EndSym = getContainerEnd(State, ContReg); |
| 283 |
} |
| 284 |
State = setIteratorPosition(State, RetVal, |
| 285 |
IteratorPosition::getPosition(ContReg, EndSym)); |
| 286 |
C.addTransition(State); |
| 287 |
} |
| 288 |
|
| 289 |
void ContainerModeling::handleAssignment(CheckerContext &C, SVal Cont, |
| 290 |
const Expr *CE, SVal OldCont) const { |
| 291 |
const auto *ContReg = Cont.getAsRegion(); |
| 292 |
if (!ContReg) |
| 293 |
return; |
| 294 |
|
| 295 |
ContReg = ContReg->getMostDerivedObjectRegion(); |
| 296 |
|
| 297 |
// Assignment of a new value to a container always invalidates all its |
| 298 |
// iterators |
| 299 |
auto State = C.getState(); |
| 300 |
const auto CData = getContainerData(State, ContReg); |
| 301 |
if (CData) { |
| 302 |
State = invalidateAllIteratorPositions(State, ContReg); |
| 303 |
} |
| 304 |
|
| 305 |
// In case of move, iterators of the old container (except the past-end |
| 306 |
// iterators) remain valid but refer to the new container |
| 307 |
if (!OldCont.isUndef()) { |
| 308 |
const auto *OldContReg = OldCont.getAsRegion(); |
| 309 |
if (OldContReg) { |
| 310 |
OldContReg = OldContReg->getMostDerivedObjectRegion(); |
| 311 |
const auto OldCData = getContainerData(State, OldContReg); |
| 312 |
if (OldCData) { |
| 313 |
if (const auto OldEndSym = OldCData->getEnd()) { |
| 314 |
// If we already assigned an "end" symbol to the old container, then |
| 315 |
// first reassign all iterator positions to the new container which |
| 316 |
// are not past the container (thus not greater or equal to the |
| 317 |
// current "end" symbol). |
| 318 |
State = reassignAllIteratorPositionsUnless(State, OldContReg, ContReg, |
| 319 |
OldEndSym, BO_GE); |
| 320 |
auto &SymMgr = C.getSymbolManager(); |
| 321 |
auto &SVB = C.getSValBuilder(); |
| 322 |
// Then generate and assign a new "end" symbol for the new container. |
| 323 |
auto NewEndSym = |
| 324 |
SymMgr.conjureSymbol(CE, C.getLocationContext(), |
| 325 |
C.getASTContext().LongTy, C.blockCount()); |
| 326 |
State = assumeNoOverflow(State, NewEndSym, 4); |
| 327 |
if (CData) { |
| 328 |
State = setContainerData(State, ContReg, CData->newEnd(NewEndSym)); |
| 329 |
} else { |
| 330 |
State = setContainerData(State, ContReg, |
| 331 |
ContainerData::fromEnd(NewEndSym)); |
| 332 |
} |
| 333 |
// Finally, replace the old "end" symbol in the already reassigned |
| 334 |
// iterator positions with the new "end" symbol. |
| 335 |
State = rebaseSymbolInIteratorPositionsIf( |
| 336 |
State, SVB, OldEndSym, NewEndSym, OldEndSym, BO_LT); |
| 337 |
} else { |
| 338 |
// There was no "end" symbol assigned yet to the old container, |
| 339 |
// so reassign all iterator positions to the new container. |
| 340 |
State = reassignAllIteratorPositions(State, OldContReg, ContReg); |
| 341 |
} |
| 342 |
if (const auto OldBeginSym = OldCData->getBegin()) { |
| 343 |
// If we already assigned a "begin" symbol to the old container, then |
| 344 |
// assign it to the new container and remove it from the old one. |
| 345 |
if (CData) { |
| 346 |
State = |
| 347 |
setContainerData(State, ContReg, CData->newBegin(OldBeginSym)); |
| 348 |
} else { |
| 349 |
State = setContainerData(State, ContReg, |
| 350 |
ContainerData::fromBegin(OldBeginSym)); |
| 351 |
} |
| 352 |
State = |
| 353 |
setContainerData(State, OldContReg, OldCData->newBegin(nullptr)); |
| 354 |
} |
| 355 |
} else { |
| 356 |
// There was neither "begin" nor "end" symbol assigned yet to the old |
| 357 |
// container, so reassign all iterator positions to the new container. |
| 358 |
State = reassignAllIteratorPositions(State, OldContReg, ContReg); |
| 359 |
} |
| 360 |
} |
| 361 |
} |
| 362 |
C.addTransition(State); |
| 363 |
} |
| 364 |
|
| 365 |
void ContainerModeling::handleAssign(CheckerContext &C, SVal Cont, |
| 366 |
const Expr *ContE) const { |
| 367 |
const auto *ContReg = Cont.getAsRegion(); |
| 368 |
if (!ContReg) |
| 369 |
return; |
| 370 |
|
| 371 |
ContReg = ContReg->getMostDerivedObjectRegion(); |
| 372 |
|
| 373 |
// The assign() operation invalidates all the iterators |
| 374 |
auto State = C.getState(); |
| 375 |
State = invalidateAllIteratorPositions(State, ContReg); |
| 376 |
C.addTransition(State); |
| 377 |
} |
| 378 |
|
| 379 |
void ContainerModeling::handleClear(CheckerContext &C, SVal Cont, |
| 380 |
const Expr *ContE) const { |
| 381 |
const auto *ContReg = Cont.getAsRegion(); |
| 382 |
if (!ContReg) |
| 383 |
return; |
| 384 |
|
| 385 |
ContReg = ContReg->getMostDerivedObjectRegion(); |
| 386 |
|
| 387 |
// The clear() operation invalidates all the iterators, except the past-end |
| 388 |
// iterators of list-like containers |
| 389 |
auto State = C.getState(); |
| 390 |
if (!hasSubscriptOperator(State, ContReg) || |
| 391 |
!backModifiable(State, ContReg)) { |
| 392 |
const auto CData = getContainerData(State, ContReg); |
| 393 |
if (CData) { |
| 394 |
if (const auto EndSym = CData->getEnd()) { |
| 395 |
State = |
| 396 |
invalidateAllIteratorPositionsExcept(State, ContReg, EndSym, BO_GE); |
| 397 |
C.addTransition(State); |
| 398 |
return; |
| 399 |
} |
| 400 |
} |
| 401 |
} |
| 402 |
const NoteTag *ChangeTag = |
| 403 |
getChangeTag(C, "became empty", ContReg, ContE); |
| 404 |
State = invalidateAllIteratorPositions(State, ContReg); |
| 405 |
C.addTransition(State, ChangeTag); |
| 406 |
} |
| 407 |
|
| 408 |
void ContainerModeling::handlePushBack(CheckerContext &C, SVal Cont, |
| 409 |
const Expr *ContE) const { |
| 410 |
const auto *ContReg = Cont.getAsRegion(); |
| 411 |
if (!ContReg) |
| 412 |
return; |
| 413 |
|
| 414 |
ContReg = ContReg->getMostDerivedObjectRegion(); |
| 415 |
|
| 416 |
// For deque-like containers invalidate all iterator positions |
| 417 |
auto State = C.getState(); |
| 418 |
if (hasSubscriptOperator(State, ContReg) && frontModifiable(State, ContReg)) { |
| 419 |
State = invalidateAllIteratorPositions(State, ContReg); |
| 420 |
C.addTransition(State); |
| 421 |
return; |
| 422 |
} |
| 423 |
|
| 424 |
const auto CData = getContainerData(State, ContReg); |
| 425 |
if (!CData) |
| 426 |
return; |
| 427 |
|
| 428 |
// For vector-like containers invalidate the past-end iterator positions |
| 429 |
if (const auto EndSym = CData->getEnd()) { |
| 430 |
if (hasSubscriptOperator(State, ContReg)) { |
| 431 |
State = invalidateIteratorPositions(State, EndSym, BO_GE); |
| 432 |
} |
| 433 |
auto &SymMgr = C.getSymbolManager(); |
| 434 |
auto &BVF = SymMgr.getBasicVals(); |
| 435 |
auto &SVB = C.getSValBuilder(); |
| 436 |
const auto newEndSym = |
| 437 |
SVB.evalBinOp(State, BO_Add, |
| 438 |
nonloc::SymbolVal(EndSym), |
| 439 |
nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))), |
| 440 |
SymMgr.getType(EndSym)).getAsSymbol(); |
| 441 |
const NoteTag *ChangeTag = |
| 442 |
getChangeTag(C, "extended to the back by 1 position", ContReg, ContE); |
| 443 |
State = setContainerData(State, ContReg, CData->newEnd(newEndSym)); |
| 444 |
C.addTransition(State, ChangeTag); |
| 445 |
} |
| 446 |
} |
| 447 |
|
| 448 |
void ContainerModeling::handlePopBack(CheckerContext &C, SVal Cont, |
| 449 |
const Expr *ContE) const { |
| 450 |
const auto *ContReg = Cont.getAsRegion(); |
| 451 |
if (!ContReg) |
| 452 |
return; |
| 453 |
|
| 454 |
ContReg = ContReg->getMostDerivedObjectRegion(); |
| 455 |
|
| 456 |
auto State = C.getState(); |
| 457 |
const auto CData = getContainerData(State, ContReg); |
| 458 |
if (!CData) |
| 459 |
return; |
| 460 |
|
| 461 |
if (const auto EndSym = CData->getEnd()) { |
| 462 |
auto &SymMgr = C.getSymbolManager(); |
| 463 |
auto &BVF = SymMgr.getBasicVals(); |
| 464 |
auto &SVB = C.getSValBuilder(); |
| 465 |
const auto BackSym = |
| 466 |
SVB.evalBinOp(State, BO_Sub, |
| 467 |
nonloc::SymbolVal(EndSym), |
| 468 |
nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))), |
| 469 |
SymMgr.getType(EndSym)).getAsSymbol(); |
| 470 |
const NoteTag *ChangeTag = |
| 471 |
getChangeTag(C, "shrank from the back by 1 position", ContReg, ContE); |
| 472 |
// For vector-like and deque-like containers invalidate the last and the |
| 473 |
// past-end iterator positions. For list-like containers only invalidate |
| 474 |
// the last position |
| 475 |
if (hasSubscriptOperator(State, ContReg) && |
| 476 |
backModifiable(State, ContReg)) { |
| 477 |
State = invalidateIteratorPositions(State, BackSym, BO_GE); |
| 478 |
State = setContainerData(State, ContReg, CData->newEnd(nullptr)); |
| 479 |
} else { |
| 480 |
State = invalidateIteratorPositions(State, BackSym, BO_EQ); |
| 481 |
} |
| 482 |
auto newEndSym = BackSym; |
| 483 |
State = setContainerData(State, ContReg, CData->newEnd(newEndSym)); |
| 484 |
C.addTransition(State, ChangeTag); |
| 485 |
} |
| 486 |
} |
| 487 |
|
| 488 |
void ContainerModeling::handlePushFront(CheckerContext &C, SVal Cont, |
| 489 |
const Expr *ContE) const { |
| 490 |
const auto *ContReg = Cont.getAsRegion(); |
| 491 |
if (!ContReg) |
| 492 |
return; |
| 493 |
|
| 494 |
ContReg = ContReg->getMostDerivedObjectRegion(); |
| 495 |
|
| 496 |
// For deque-like containers invalidate all iterator positions |
| 497 |
auto State = C.getState(); |
| 498 |
if (hasSubscriptOperator(State, ContReg)) { |
| 499 |
State = invalidateAllIteratorPositions(State, ContReg); |
| 500 |
C.addTransition(State); |
| 501 |
} else { |
| 502 |
const auto CData = getContainerData(State, ContReg); |
| 503 |
if (!CData) |
| 504 |
return; |
| 505 |
|
| 506 |
if (const auto BeginSym = CData->getBegin()) { |
| 507 |
auto &SymMgr = C.getSymbolManager(); |
| 508 |
auto &BVF = SymMgr.getBasicVals(); |
| 509 |
auto &SVB = C.getSValBuilder(); |
| 510 |
const auto newBeginSym = |
| 511 |
SVB.evalBinOp(State, BO_Sub, |
| 512 |
nonloc::SymbolVal(BeginSym), |
| 513 |
nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))), |
| 514 |
SymMgr.getType(BeginSym)).getAsSymbol(); |
| 515 |
const NoteTag *ChangeTag = |
| 516 |
getChangeTag(C, "extended to the front by 1 position", ContReg, ContE); |
| 517 |
State = setContainerData(State, ContReg, CData->newBegin(newBeginSym)); |
| 518 |
C.addTransition(State, ChangeTag); |
| 519 |
} |
| 520 |
} |
| 521 |
} |
| 522 |
|
| 523 |
void ContainerModeling::handlePopFront(CheckerContext &C, SVal Cont, |
| 524 |
const Expr *ContE) const { |
| 525 |
const auto *ContReg = Cont.getAsRegion(); |
| 526 |
if (!ContReg) |
| 527 |
return; |
| 528 |
|
| 529 |
ContReg = ContReg->getMostDerivedObjectRegion(); |
| 530 |
|
| 531 |
auto State = C.getState(); |
| 532 |
const auto CData = getContainerData(State, ContReg); |
| 533 |
if (!CData) |
| 534 |
return; |
| 535 |
|
| 536 |
// For deque-like containers invalidate all iterator positions. For list-like |
| 537 |
// iterators only invalidate the first position |
| 538 |
if (const auto BeginSym = CData->getBegin()) { |
| 539 |
if (hasSubscriptOperator(State, ContReg)) { |
| 540 |
State = invalidateIteratorPositions(State, BeginSym, BO_LE); |
| 541 |
} else { |
| 542 |
State = invalidateIteratorPositions(State, BeginSym, BO_EQ); |
| 543 |
} |
| 544 |
auto &SymMgr = C.getSymbolManager(); |
| 545 |
auto &BVF = SymMgr.getBasicVals(); |
| 546 |
auto &SVB = C.getSValBuilder(); |
| 547 |
const auto newBeginSym = |
| 548 |
SVB.evalBinOp(State, BO_Add, |
| 549 |
nonloc::SymbolVal(BeginSym), |
| 550 |
nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))), |
| 551 |
SymMgr.getType(BeginSym)).getAsSymbol(); |
| 552 |
const NoteTag *ChangeTag = |
| 553 |
getChangeTag(C, "shrank from the front by 1 position", ContReg, ContE); |
| 554 |
State = setContainerData(State, ContReg, CData->newBegin(newBeginSym)); |
| 555 |
C.addTransition(State, ChangeTag); |
| 556 |
} |
| 557 |
} |
| 558 |
|
| 559 |
void ContainerModeling::handleInsert(CheckerContext &C, SVal Cont, |
| 560 |
SVal Iter) const { |
| 561 |
const auto *ContReg = Cont.getAsRegion(); |
| 562 |
if (!ContReg) |
| 563 |
return; |
| 564 |
|
| 565 |
ContReg = ContReg->getMostDerivedObjectRegion(); |
| 566 |
|
| 567 |
auto State = C.getState(); |
| 568 |
const auto *Pos = getIteratorPosition(State, Iter); |
| 569 |
if (!Pos) |
| 570 |
return; |
| 571 |
|
| 572 |
// For deque-like containers invalidate all iterator positions. For |
| 573 |
// vector-like containers invalidate iterator positions after the insertion. |
| 574 |
if (hasSubscriptOperator(State, ContReg) && backModifiable(State, ContReg)) { |
| 575 |
if (frontModifiable(State, ContReg)) { |
| 576 |
State = invalidateAllIteratorPositions(State, ContReg); |
| 577 |
} else { |
| 578 |
State = invalidateIteratorPositions(State, Pos->getOffset(), BO_GE); |
| 579 |
} |
| 580 |
if (const auto *CData = getContainerData(State, ContReg)) { |
| 581 |
if (const auto EndSym = CData->getEnd()) { |
| 582 |
State = invalidateIteratorPositions(State, EndSym, BO_GE); |
| 583 |
State = setContainerData(State, ContReg, CData->newEnd(nullptr)); |
| 584 |
} |
| 585 |
} |
| 586 |
C.addTransition(State); |
| 587 |
} |
| 588 |
} |
| 589 |
|
| 590 |
void ContainerModeling::handleErase(CheckerContext &C, SVal Cont, |
| 591 |
SVal Iter) const { |
| 592 |
const auto *ContReg = Cont.getAsRegion(); |
| 593 |
if (!ContReg) |
| 594 |
return; |
| 595 |
|
| 596 |
ContReg = ContReg->getMostDerivedObjectRegion(); |
| 597 |
|
| 598 |
auto State = C.getState(); |
| 599 |
const auto *Pos = getIteratorPosition(State, Iter); |
| 600 |
if (!Pos) |
| 601 |
return; |
| 602 |
|
| 603 |
// For deque-like containers invalidate all iterator positions. For |
| 604 |
// vector-like containers invalidate iterator positions at and after the |
| 605 |
// deletion. For list-like containers only invalidate the deleted position. |
| 606 |
if (hasSubscriptOperator(State, ContReg) && backModifiable(State, ContReg)) { |
| 607 |
if (frontModifiable(State, ContReg)) { |
| 608 |
State = invalidateAllIteratorPositions(State, ContReg); |
| 609 |
} else { |
| 610 |
State = invalidateIteratorPositions(State, Pos->getOffset(), BO_GE); |
| 611 |
} |
| 612 |
if (const auto *CData = getContainerData(State, ContReg)) { |
| 613 |
if (const auto EndSym = CData->getEnd()) { |
| 614 |
State = invalidateIteratorPositions(State, EndSym, BO_GE); |
| 615 |
State = setContainerData(State, ContReg, CData->newEnd(nullptr)); |
| 616 |
} |
| 617 |
} |
| 618 |
} else { |
| 619 |
State = invalidateIteratorPositions(State, Pos->getOffset(), BO_EQ); |
| 620 |
} |
| 621 |
C.addTransition(State); |
| 622 |
} |
| 623 |
|
| 624 |
void ContainerModeling::handleErase(CheckerContext &C, SVal Cont, SVal Iter1, |
| 625 |
SVal Iter2) const { |
| 626 |
const auto *ContReg = Cont.getAsRegion(); |
| 627 |
if (!ContReg) |
| 628 |
return; |
| 629 |
|
| 630 |
ContReg = ContReg->getMostDerivedObjectRegion(); |
| 631 |
auto State = C.getState(); |
| 632 |
const auto *Pos1 = getIteratorPosition(State, Iter1); |
| 633 |
const auto *Pos2 = getIteratorPosition(State, Iter2); |
| 634 |
if (!Pos1 || !Pos2) |
| 635 |
return; |
| 636 |
|
| 637 |
// For deque-like containers invalidate all iterator positions. For |
| 638 |
// vector-like containers invalidate iterator positions at and after the |
| 639 |
// deletion range. For list-like containers only invalidate the deleted |
| 640 |
// position range [first..last]. |
| 641 |
if (hasSubscriptOperator(State, ContReg) && backModifiable(State, ContReg)) { |
| 642 |
if (frontModifiable(State, ContReg)) { |
| 643 |
State = invalidateAllIteratorPositions(State, ContReg); |
| 644 |
} else { |
| 645 |
State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GE); |
| 646 |
} |
| 647 |
if (const auto *CData = getContainerData(State, ContReg)) { |
| 648 |
if (const auto EndSym = CData->getEnd()) { |
| 649 |
State = invalidateIteratorPositions(State, EndSym, BO_GE); |
| 650 |
State = setContainerData(State, ContReg, CData->newEnd(nullptr)); |
| 651 |
} |
| 652 |
} |
| 653 |
} else { |
| 654 |
State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GE, |
| 655 |
Pos2->getOffset(), BO_LT); |
| 656 |
} |
| 657 |
C.addTransition(State); |
| 658 |
} |
| 659 |
|
| 660 |
void ContainerModeling::handleEraseAfter(CheckerContext &C, SVal Cont, |
| 661 |
SVal Iter) const { |
| 662 |
auto State = C.getState(); |
| 663 |
const auto *Pos = getIteratorPosition(State, Iter); |
| 664 |
if (!Pos) |
| 665 |
return; |
| 666 |
|
| 667 |
// Invalidate the deleted iterator position, which is the position of the |
| 668 |
// parameter plus one. |
| 669 |
auto &SymMgr = C.getSymbolManager(); |
| 670 |
auto &BVF = SymMgr.getBasicVals(); |
| 671 |
auto &SVB = C.getSValBuilder(); |
| 672 |
const auto NextSym = |
| 673 |
SVB.evalBinOp(State, BO_Add, |
| 674 |
nonloc::SymbolVal(Pos->getOffset()), |
| 675 |
nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))), |
| 676 |
SymMgr.getType(Pos->getOffset())).getAsSymbol(); |
| 677 |
State = invalidateIteratorPositions(State, NextSym, BO_EQ); |
| 678 |
C.addTransition(State); |
| 679 |
} |
| 680 |
|
| 681 |
void ContainerModeling::handleEraseAfter(CheckerContext &C, SVal Cont, |
| 682 |
SVal Iter1, SVal Iter2) const { |
| 683 |
auto State = C.getState(); |
| 684 |
const auto *Pos1 = getIteratorPosition(State, Iter1); |
| 685 |
const auto *Pos2 = getIteratorPosition(State, Iter2); |
| 686 |
if (!Pos1 || !Pos2) |
| 687 |
return; |
| 688 |
|
| 689 |
// Invalidate the deleted iterator position range (first..last) |
| 690 |
State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GT, |
| 691 |
Pos2->getOffset(), BO_LT); |
| 692 |
C.addTransition(State); |
| 693 |
} |
| 694 |
|
| 695 |
const NoteTag *ContainerModeling::getChangeTag(CheckerContext &C, |
| 696 |
StringRef Text, |
| 697 |
const MemRegion *ContReg, |
| 698 |
const Expr *ContE) const { |
| 699 |
StringRef Name; |
| 700 |
// First try to get the name of the variable from the region |
| 701 |
if (const auto *DR = dyn_cast<DeclRegion>(ContReg)) { |
| 702 |
Name = DR->getDecl()->getName(); |
| 703 |
// If the region is not a `DeclRegion` then use the expression instead |
| 704 |
} else if (const auto *DRE = |
| 705 |
dyn_cast<DeclRefExpr>(ContE->IgnoreParenCasts())) { |
| 706 |
Name = DRE->getDecl()->getName(); |
| 707 |
} |
| 708 |
|
| 709 |
return C.getNoteTag( |
| 710 |
[Text, Name, ContReg](PathSensitiveBugReport &BR) -> std::string { |
| 711 |
if (!BR.isInteresting(ContReg)) |
| 712 |
return ""; |
| 713 |
|
| 714 |
SmallString<256> Msg; |
| 715 |
llvm::raw_svector_ostream Out(Msg); |
| 716 |
Out << "Container " << (!Name.empty() ? ("'" + Name.str() + "' ") : "" ) |
| 717 |
<< Text; |
| 718 |
return std::string(Out.str()); |
| 719 |
}); |
| 720 |
} |
| 721 |
|
| 722 |
void ContainerModeling::printState(raw_ostream &Out, ProgramStateRef State, |
| 723 |
const char *NL, const char *Sep) const { |
| 724 |
auto ContMap = State->get<ContainerMap>(); |
| 725 |
|
| 726 |
if (!ContMap.isEmpty()) { |
| 727 |
Out << Sep << "Container Data :" << NL; |
| 728 |
for (const auto &Cont : ContMap) { |
| 729 |
Cont.first->dumpToStream(Out); |
| 730 |
Out << " : [ "; |
| 731 |
const auto CData = Cont.second; |
| 732 |
if (CData.getBegin()) |
| 733 |
CData.getBegin()->dumpToStream(Out); |
| 734 |
else |
| 735 |
Out << "<Unknown>"; |
| 736 |
Out << " .. "; |
| 737 |
if (CData.getEnd()) |
| 738 |
CData.getEnd()->dumpToStream(Out); |
| 739 |
else |
| 740 |
Out << "<Unknown>"; |
| 741 |
Out << " ]"; |
| 742 |
} |
| 743 |
} |
| 744 |
} |
| 745 |
|
| 746 |
namespace { |
| 747 |
|
| 748 |
bool isBeginCall(const FunctionDecl *Func) { |
| 749 |
const auto *IdInfo = Func->getIdentifier(); |
| 750 |
if (!IdInfo) |
| 751 |
return false; |
| 752 |
return IdInfo->getName().endswith_insensitive("begin"); |
| 753 |
} |
| 754 |
|
| 755 |
bool isEndCall(const FunctionDecl *Func) { |
| 756 |
const auto *IdInfo = Func->getIdentifier(); |
| 757 |
if (!IdInfo) |
| 758 |
return false; |
| 759 |
return IdInfo->getName().endswith_insensitive("end"); |
| 760 |
} |
| 761 |
|
| 762 |
const CXXRecordDecl *getCXXRecordDecl(ProgramStateRef State, |
| 763 |
const MemRegion *Reg) { |
| 764 |
auto TI = getDynamicTypeInfo(State, Reg); |
| 765 |
if (!TI.isValid()) |
| 766 |
return nullptr; |
| 767 |
|
| 768 |
auto Type = TI.getType(); |
| 769 |
if (const auto *RefT = Type->getAs<ReferenceType>()) { |
| 770 |
Type = RefT->getPointeeType(); |
| 771 |
} |
| 772 |
|
| 773 |
return Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl(); |
| 774 |
} |
| 775 |
|
| 776 |
bool hasSubscriptOperator(ProgramStateRef State, const MemRegion *Reg) { |
| 777 |
const auto *CRD = getCXXRecordDecl(State, Reg); |
| 778 |
if (!CRD) |
| 779 |
return false; |
| 780 |
|
| 781 |
for (const auto *Method : CRD->methods()) { |
| 782 |
if (!Method->isOverloadedOperator()) |
| 783 |
continue; |
| 784 |
const auto OPK = Method->getOverloadedOperator(); |
| 785 |
if (OPK == OO_Subscript) { |
| 786 |
return true; |
| 787 |
} |
| 788 |
} |
| 789 |
return false; |
| 790 |
} |
| 791 |
|
| 792 |
bool frontModifiable(ProgramStateRef State, const MemRegion *Reg) { |
| 793 |
const auto *CRD = getCXXRecordDecl(State, Reg); |
| 794 |
if (!CRD) |
| 795 |
return false; |
| 796 |
|
| 797 |
for (const auto *Method : CRD->methods()) { |
| 798 |
if (!Method->getDeclName().isIdentifier()) |
| 799 |
continue; |
| 800 |
if (Method->getName() == "push_front" || Method->getName() == "pop_front") { |
| 801 |
return true; |
| 802 |
} |
| 803 |
} |
| 804 |
return false; |
| 805 |
} |
| 806 |
|
| 807 |
bool backModifiable(ProgramStateRef State, const MemRegion *Reg) { |
| 808 |
const auto *CRD = getCXXRecordDecl(State, Reg); |
| 809 |
if (!CRD) |
| 810 |
return false; |
| 811 |
|
| 812 |
for (const auto *Method : CRD->methods()) { |
| 813 |
if (!Method->getDeclName().isIdentifier()) |
| 814 |
continue; |
| 815 |
if (Method->getName() == "push_back" || Method->getName() == "pop_back") { |
| 816 |
return true; |
| 817 |
} |
| 818 |
} |
| 819 |
return false; |
| 820 |
} |
| 821 |
|
| 822 |
SymbolRef getContainerBegin(ProgramStateRef State, const MemRegion *Cont) { |
| 823 |
const auto *CDataPtr = getContainerData(State, Cont); |
| 824 |
if (!CDataPtr) |
| 825 |
return nullptr; |
| 826 |
|
| 827 |
return CDataPtr->getBegin(); |
| 828 |
} |
| 829 |
|
| 830 |
SymbolRef getContainerEnd(ProgramStateRef State, const MemRegion *Cont) { |
| 831 |
const auto *CDataPtr = getContainerData(State, Cont); |
| 832 |
if (!CDataPtr) |
| 833 |
return nullptr; |
| 834 |
|
| 835 |
return CDataPtr->getEnd(); |
| 836 |
} |
| 837 |
|
| 838 |
ProgramStateRef createContainerBegin(ProgramStateRef State, |
| 839 |
const MemRegion *Cont, const Expr *E, |
| 840 |
QualType T, const LocationContext *LCtx, |
| 841 |
unsigned BlockCount) { |
| 842 |
// Only create if it does not exist |
| 843 |
const auto *CDataPtr = getContainerData(State, Cont); |
| 844 |
if (CDataPtr && CDataPtr->getBegin()) |
| 845 |
return State; |
| 846 |
|
| 847 |
auto &SymMgr = State->getSymbolManager(); |
| 848 |
const SymbolConjured *Sym = SymMgr.conjureSymbol(E, LCtx, T, BlockCount, |
| 849 |
"begin"); |
| 850 |
State = assumeNoOverflow(State, Sym, 4); |
| 851 |
|
| 852 |
if (CDataPtr) { |
| 853 |
const auto CData = CDataPtr->newBegin(Sym); |
| 854 |
return setContainerData(State, Cont, CData); |
| 855 |
} |
| 856 |
|
| 857 |
const auto CData = ContainerData::fromBegin(Sym); |
| 858 |
return setContainerData(State, Cont, CData); |
| 859 |
} |
| 860 |
|
| 861 |
ProgramStateRef createContainerEnd(ProgramStateRef State, const MemRegion *Cont, |
| 862 |
const Expr *E, QualType T, |
| 863 |
const LocationContext *LCtx, |
| 864 |
unsigned BlockCount) { |
| 865 |
// Only create if it does not exist |
| 866 |
const auto *CDataPtr = getContainerData(State, Cont); |
| 867 |
if (CDataPtr && CDataPtr->getEnd()) |
| 868 |
return State; |
| 869 |
|
| 870 |
auto &SymMgr = State->getSymbolManager(); |
| 871 |
const SymbolConjured *Sym = SymMgr.conjureSymbol(E, LCtx, T, BlockCount, |
| 872 |
"end"); |
| 873 |
State = assumeNoOverflow(State, Sym, 4); |
| 874 |
|
| 875 |
if (CDataPtr) { |
| 876 |
const auto CData = CDataPtr->newEnd(Sym); |
| 877 |
return setContainerData(State, Cont, CData); |
| 878 |
} |
| 879 |
|
| 880 |
const auto CData = ContainerData::fromEnd(Sym); |
| 881 |
return setContainerData(State, Cont, CData); |
| 882 |
} |
| 883 |
|
| 884 |
ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont, |
| 885 |
const ContainerData &CData) { |
| 886 |
return State->set<ContainerMap>(Cont, CData); |
| 887 |
} |
| 888 |
|
| 889 |
template <typename Condition, typename Process> |
| 890 |
ProgramStateRef processIteratorPositions(ProgramStateRef State, Condition Cond, |
| 891 |
Process Proc) { |
| 892 |
auto &RegionMapFactory = State->get_context<IteratorRegionMap>(); |
| 893 |
auto RegionMap = State->get<IteratorRegionMap>(); |
| 894 |
bool Changed = false; |
| 895 |
for (const auto &Reg : RegionMap) { |
| 896 |
if (Cond(Reg.second)) { |
| 897 |
RegionMap = RegionMapFactory.add(RegionMap, Reg.first, Proc(Reg.second)); |
| 898 |
Changed = true; |
| 899 |
} |
| 900 |
} |
| 901 |
|
| 902 |
if (Changed) |
| 903 |
State = State->set<IteratorRegionMap>(RegionMap); |
| 904 |
|
| 905 |
auto &SymbolMapFactory = State->get_context<IteratorSymbolMap>(); |
| 906 |
auto SymbolMap = State->get<IteratorSymbolMap>(); |
| 907 |
Changed = false; |
| 908 |
for (const auto &Sym : SymbolMap) { |
| 909 |
if (Cond(Sym.second)) { |
| 910 |
SymbolMap = SymbolMapFactory.add(SymbolMap, Sym.first, Proc(Sym.second)); |
| 911 |
Changed = true; |
| 912 |
} |
| 913 |
} |
| 914 |
|
| 915 |
if (Changed) |
| 916 |
State = State->set<IteratorSymbolMap>(SymbolMap); |
| 917 |
|
| 918 |
return State; |
| 919 |
} |
| 920 |
|
| 921 |
ProgramStateRef invalidateAllIteratorPositions(ProgramStateRef State, |
| 922 |
const MemRegion *Cont) { |
| 923 |
auto MatchCont = [&](const IteratorPosition &Pos) { |
| 924 |
return Pos.getContainer() == Cont; |
| 925 |
}; |
| 926 |
auto Invalidate = [&](const IteratorPosition &Pos) { |
| 927 |
return Pos.invalidate(); |
| 928 |
}; |
| 929 |
return processIteratorPositions(State, MatchCont, Invalidate); |
| 930 |
} |
| 931 |
|
| 932 |
ProgramStateRef |
| 933 |
invalidateAllIteratorPositionsExcept(ProgramStateRef State, |
| 934 |
const MemRegion *Cont, SymbolRef Offset, |
| 935 |
BinaryOperator::Opcode Opc) { |
| 936 |
auto MatchContAndCompare = [&](const IteratorPosition &Pos) { |
| 937 |
return Pos.getContainer() == Cont && |
| 938 |
!compare(State, Pos.getOffset(), Offset, Opc); |
| 939 |
}; |
| 940 |
auto Invalidate = [&](const IteratorPosition &Pos) { |
| 941 |
return Pos.invalidate(); |
| 942 |
}; |
| 943 |
return processIteratorPositions(State, MatchContAndCompare, Invalidate); |
| 944 |
} |
| 945 |
|
| 946 |
ProgramStateRef invalidateIteratorPositions(ProgramStateRef State, |
| 947 |
SymbolRef Offset, |
| 948 |
BinaryOperator::Opcode Opc) { |
| 949 |
auto Compare = [&](const IteratorPosition &Pos) { |
| 950 |
return compare(State, Pos.getOffset(), Offset, Opc); |
| 951 |
}; |
| 952 |
auto Invalidate = [&](const IteratorPosition &Pos) { |
| 953 |
return Pos.invalidate(); |
| 954 |
}; |
| 955 |
return processIteratorPositions(State, Compare, Invalidate); |
| 956 |
} |
| 957 |
|
| 958 |
ProgramStateRef invalidateIteratorPositions(ProgramStateRef State, |
| 959 |
SymbolRef Offset1, |
| 960 |
BinaryOperator::Opcode Opc1, |
| 961 |
SymbolRef Offset2, |
| 962 |
BinaryOperator::Opcode Opc2) { |
| 963 |
auto Compare = [&](const IteratorPosition &Pos) { |
| 964 |
return compare(State, Pos.getOffset(), Offset1, Opc1) && |
| 965 |
compare(State, Pos.getOffset(), Offset2, Opc2); |
| 966 |
}; |
| 967 |
auto Invalidate = [&](const IteratorPosition &Pos) { |
| 968 |
return Pos.invalidate(); |
| 969 |
}; |
| 970 |
return processIteratorPositions(State, Compare, Invalidate); |
| 971 |
} |
| 972 |
|
| 973 |
ProgramStateRef reassignAllIteratorPositions(ProgramStateRef State, |
| 974 |
const MemRegion *Cont, |
| 975 |
const MemRegion *NewCont) { |
| 976 |
auto MatchCont = [&](const IteratorPosition &Pos) { |
| 977 |
return Pos.getContainer() == Cont; |
| 978 |
}; |
| 979 |
auto ReAssign = [&](const IteratorPosition &Pos) { |
| 980 |
return Pos.reAssign(NewCont); |
| 981 |
}; |
| 982 |
return processIteratorPositions(State, MatchCont, ReAssign); |
| 983 |
} |
| 984 |
|
| 985 |
ProgramStateRef reassignAllIteratorPositionsUnless(ProgramStateRef State, |
| 986 |
const MemRegion *Cont, |
| 987 |
const MemRegion *NewCont, |
| 988 |
SymbolRef Offset, |
| 989 |
BinaryOperator::Opcode Opc) { |
| 990 |
auto MatchContAndCompare = [&](const IteratorPosition &Pos) { |
| 991 |
return Pos.getContainer() == Cont && |
| 992 |
!compare(State, Pos.getOffset(), Offset, Opc); |
| 993 |
}; |
| 994 |
auto ReAssign = [&](const IteratorPosition &Pos) { |
| 995 |
return Pos.reAssign(NewCont); |
| 996 |
}; |
| 997 |
return processIteratorPositions(State, MatchContAndCompare, ReAssign); |
| 998 |
} |
| 999 |
|
| 1000 |
// This function rebases symbolic expression `OldSym + Int` to `NewSym + Int`, |
| 1001 |
// `OldSym - Int` to `NewSym - Int` and `OldSym` to `NewSym` in any iterator |
| 1002 |
// position offsets where `CondSym` is true. |
| 1003 |
ProgramStateRef rebaseSymbolInIteratorPositionsIf( |
| 1004 |
ProgramStateRef State, SValBuilder &SVB, SymbolRef OldSym, |
| 1005 |
SymbolRef NewSym, SymbolRef CondSym, BinaryOperator::Opcode Opc) { |
| 1006 |
auto LessThanEnd = [&](const IteratorPosition &Pos) { |
| 1007 |
return compare(State, Pos.getOffset(), CondSym, Opc); |
| 1008 |
}; |
| 1009 |
auto RebaseSymbol = [&](const IteratorPosition &Pos) { |
| 1010 |
return Pos.setTo(rebaseSymbol(State, SVB, Pos.getOffset(), OldSym, |
| 1011 |
NewSym)); |
| 1012 |
}; |
| 1013 |
return processIteratorPositions(State, LessThanEnd, RebaseSymbol); |
| 1014 |
} |
| 1015 |
|
| 1016 |
// This function rebases symbolic expression `OldExpr + Int` to `NewExpr + Int`, |
| 1017 |
// `OldExpr - Int` to `NewExpr - Int` and `OldExpr` to `NewExpr` in expression |
| 1018 |
// `OrigExpr`. |
| 1019 |
SymbolRef rebaseSymbol(ProgramStateRef State, SValBuilder &SVB, |
| 1020 |
SymbolRef OrigExpr, SymbolRef OldExpr, |
| 1021 |
SymbolRef NewSym) { |
| 1022 |
auto &SymMgr = SVB.getSymbolManager(); |
| 1023 |
auto Diff = SVB.evalBinOpNN(State, BO_Sub, nonloc::SymbolVal(OrigExpr), |
| 1024 |
nonloc::SymbolVal(OldExpr), |
| 1025 |
SymMgr.getType(OrigExpr)); |
| 1026 |
|
| 1027 |
const auto DiffInt = Diff.getAs<nonloc::ConcreteInt>(); |
| 1028 |
if (!DiffInt) |
| 1029 |
return OrigExpr; |
| 1030 |
|
| 1031 |
return SVB.evalBinOpNN(State, BO_Add, *DiffInt, nonloc::SymbolVal(NewSym), |
| 1032 |
SymMgr.getType(OrigExpr)).getAsSymbol(); |
| 1033 |
} |
| 1034 |
|
| 1035 |
bool hasLiveIterators(ProgramStateRef State, const MemRegion *Cont) { |
| 1036 |
auto RegionMap = State->get<IteratorRegionMap>(); |
| 1037 |
for (const auto &Reg : RegionMap) { |
| 1038 |
if (Reg.second.getContainer() == Cont) |
| 1039 |
return true; |
| 1040 |
} |
| 1041 |
|
| 1042 |
auto SymbolMap = State->get<IteratorSymbolMap>(); |
| 1043 |
for (const auto &Sym : SymbolMap) { |
| 1044 |
if (Sym.second.getContainer() == Cont) |
| 1045 |
return true; |
| 1046 |
} |
| 1047 |
|
| 1048 |
return false; |
| 1049 |
} |
| 1050 |
|
| 1051 |
} // namespace |
| 1052 |
|
| 1053 |
void ento::registerContainerModeling(CheckerManager &mgr) { |
| 1054 |
mgr.registerChecker<ContainerModeling>(); |
| 1055 |
} |
| 1056 |
|
| 1057 |
bool ento::shouldRegisterContainerModeling(const CheckerManager &mgr) { |
| 1058 |
if (!mgr.getLangOpts().CPlusPlus) |
| 1059 |
return false; |
| 1060 |
|
| 1061 |
if (!mgr.getAnalyzerOptions().ShouldAggressivelySimplifyBinaryOperation) { |
| 1062 |
mgr.getASTContext().getDiagnostics().Report( |
| 1063 |
diag::err_analyzer_checker_incompatible_analyzer_option) |
| 1064 |
<< "aggressive-binary-operation-simplification" << "false"; |
| 1065 |
return false; |
| 1066 |
} |
| 1067 |
|
| 1068 |
return true; |
| 1069 |
} |