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