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