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