1 //===-- IteratorChecker.cpp ---------------------------------------*- C++ -*--//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Defines a checker for using iterators outside their range (past end). Usage
11 // means here dereferencing, incrementing etc.
13 //===----------------------------------------------------------------------===//
15 // In the code, iterator can be represented as a:
16 // * type-I: typedef-ed pointer. Operations over such iterator, such as
17 // comparisons or increments, are modeled straightforwardly by the
19 // * type-II: structure with its method bodies available. Operations over such
20 // iterator are inlined by the analyzer, and results of modeling
21 // these operations are exposing implementation details of the
22 // iterators, which is not necessarily helping.
23 // * type-III: completely opaque structure. Operations over such iterator are
24 // modeled conservatively, producing conjured symbols everywhere.
26 // To handle all these types in a common way we introduce a structure called
27 // IteratorPosition which is an abstraction of the position the iterator
28 // represents using symbolic expressions. The checker handles all the
29 // operations on this structure.
31 // Additionally, depending on the circumstances, operators of types II and III
32 // can be represented as:
33 // * type-IIa, type-IIIa: conjured structure symbols - when returned by value
34 // from conservatively evaluated methods such as
36 // * type-IIb, type-IIIb: memory regions of iterator-typed objects, such as
37 // variables or temporaries, when the iterator object is
38 // currently treated as an lvalue.
39 // * type-IIc, type-IIIc: compound values of iterator-typed objects, when the
40 // iterator object is treated as an rvalue taken of a
41 // particular lvalue, eg. a copy of "type-a" iterator
42 // object, or an iterator that existed before the
43 // analysis has started.
45 // To handle any of these three different representations stored in an SVal we
46 // use setter and getters functions which separate the three cases. To store
47 // them we use a pointer union of symbol and memory region.
49 // The checker works the following way: We record the past-end iterator for
50 // all containers whenever their `.end()` is called. Since the Constraint
51 // Manager cannot handle SVals we need to take over its role. We post-check
52 // equality and non-equality comparisons and propagate the position of the
53 // iterator to the other side of the comparison if it is past-end and we are in
54 // the 'equal' branch (true-branch for `==` and false-branch for `!=`).
56 // In case of type-I or type-II iterators we get a concrete integer as a result
57 // of the comparison (1 or 0) but in case of type-III we only get a Symbol. In
58 // this latter case we record the symbol and reload it in evalAssume() and do
59 // the propagation there. We also handle (maybe double) negated comparisons
60 // which are represented in the form of (x == 0 or x !=0 ) where x is the
63 #include "ClangSACheckers.h"
64 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
65 #include "clang/StaticAnalyzer/Core/Checker.h"
66 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
67 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
69 using namespace clang;
74 // Abstract position of an iterator. This helps to handle all three kinds
75 // of operators in a common way by using a symbolic position.
76 struct IteratorPosition {
79 // Container the iterator belongs to
80 const MemRegion *Cont;
85 IteratorPosition(const MemRegion *C, SymbolRef Of)
86 : Cont(C), Offset(Of) {}
89 const MemRegion *getContainer() const { return Cont; }
90 SymbolRef getOffset() const { return Offset; }
92 static IteratorPosition getPosition(const MemRegion *C, SymbolRef Of) {
93 return IteratorPosition(C, Of);
96 IteratorPosition setTo(SymbolRef NewOf) const {
97 return IteratorPosition(Cont, NewOf);
100 bool operator==(const IteratorPosition &X) const {
101 return Cont == X.Cont && Offset == X.Offset;
104 bool operator!=(const IteratorPosition &X) const {
105 return Cont != X.Cont || Offset != X.Offset;
108 void Profile(llvm::FoldingSetNodeID &ID) const {
114 typedef llvm::PointerUnion<const MemRegion *, SymbolRef> RegionOrSymbol;
116 // Structure to record the symbolic end position of a container
117 struct ContainerData {
121 ContainerData(SymbolRef E) : End(E) {}
124 static ContainerData fromEnd(SymbolRef E) {
125 return ContainerData(E);
128 SymbolRef getEnd() const { return End; }
130 ContainerData newEnd(SymbolRef E) const { return ContainerData(E); }
132 bool operator==(const ContainerData &X) const {
136 bool operator!=(const ContainerData &X) const {
140 void Profile(llvm::FoldingSetNodeID &ID) const {
145 // Structure fo recording iterator comparisons. We needed to retrieve the
146 // original comparison expression in assumptions.
147 struct IteratorComparison {
149 RegionOrSymbol Left, Right;
153 IteratorComparison(RegionOrSymbol L, RegionOrSymbol R, bool Eq)
154 : Left(L), Right(R), Equality(Eq) {}
156 RegionOrSymbol getLeft() const { return Left; }
157 RegionOrSymbol getRight() const { return Right; }
158 bool isEquality() const { return Equality; }
159 bool operator==(const IteratorComparison &X) const {
160 return Left == X.Left && Right == X.Right && Equality == X.Equality;
162 bool operator!=(const IteratorComparison &X) const {
163 return Left != X.Left || Right != X.Right || Equality != X.Equality;
165 void Profile(llvm::FoldingSetNodeID &ID) const { ID.AddInteger(Equality); }
168 class IteratorChecker
169 : public Checker<check::PreCall, check::PostCall,
170 check::PostStmt<MaterializeTemporaryExpr>,
174 std::unique_ptr<BugType> OutOfRangeBugType;
176 void handleComparison(CheckerContext &C, const SVal &RetVal, const SVal &LVal,
177 const SVal &RVal, OverloadedOperatorKind Op) const;
178 void verifyDereference(CheckerContext &C, const SVal &Val) const;
179 void handleEnd(CheckerContext &C, const Expr *CE, const SVal &RetVal,
180 const SVal &Cont) const;
181 void assignToContainer(CheckerContext &C, const Expr *CE, const SVal &RetVal,
182 const MemRegion *Cont) const;
183 void reportOutOfRangeBug(const StringRef &Message, const SVal &Val,
184 CheckerContext &C, ExplodedNode *ErrNode) const;
190 CK_IteratorRangeChecker,
194 DefaultBool ChecksEnabled[CK_NumCheckKinds];
195 CheckName CheckNames[CK_NumCheckKinds];
197 void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
198 void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
199 void checkPostStmt(const MaterializeTemporaryExpr *MTE,
200 CheckerContext &C) const;
201 void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;
202 ProgramStateRef evalAssume(ProgramStateRef State, SVal Cond,
203 bool Assumption) const;
207 REGISTER_MAP_WITH_PROGRAMSTATE(IteratorSymbolMap, SymbolRef, IteratorPosition)
208 REGISTER_MAP_WITH_PROGRAMSTATE(IteratorRegionMap, const MemRegion *,
211 REGISTER_MAP_WITH_PROGRAMSTATE(ContainerMap, const MemRegion *, ContainerData)
213 REGISTER_MAP_WITH_PROGRAMSTATE(IteratorComparisonMap, const SymExpr *,
218 bool isIteratorType(const QualType &Type);
219 bool isIterator(const CXXRecordDecl *CRD);
220 bool isEndCall(const FunctionDecl *Func);
221 bool isSimpleComparisonOperator(OverloadedOperatorKind OK);
222 bool isDereferenceOperator(OverloadedOperatorKind OK);
223 BinaryOperator::Opcode getOpcode(const SymExpr *SE);
224 const RegionOrSymbol getRegionOrSymbol(const SVal &Val);
225 const ProgramStateRef processComparison(ProgramStateRef State,
227 RegionOrSymbol RVal, bool Equal);
228 const ProgramStateRef saveComparison(ProgramStateRef State,
229 const SymExpr *Condition, const SVal &LVal,
230 const SVal &RVal, bool Eq);
231 const IteratorComparison *loadComparison(ProgramStateRef State,
232 const SymExpr *Condition);
233 SymbolRef getContainerEnd(ProgramStateRef State, const MemRegion *Cont);
234 ProgramStateRef createContainerEnd(ProgramStateRef State, const MemRegion *Cont,
235 const SymbolRef Sym);
236 const IteratorPosition *getIteratorPosition(ProgramStateRef State,
238 const IteratorPosition *getIteratorPosition(ProgramStateRef State,
239 RegionOrSymbol RegOrSym);
240 ProgramStateRef setIteratorPosition(ProgramStateRef State, const SVal &Val,
241 const IteratorPosition &Pos);
242 ProgramStateRef setIteratorPosition(ProgramStateRef State,
243 RegionOrSymbol RegOrSym,
244 const IteratorPosition &Pos);
245 ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val);
246 ProgramStateRef adjustIteratorPosition(ProgramStateRef State,
247 RegionOrSymbol RegOrSym,
248 const IteratorPosition &Pos, bool Equal);
249 ProgramStateRef relateIteratorPositions(ProgramStateRef State,
250 const IteratorPosition &Pos1,
251 const IteratorPosition &Pos2,
253 const ContainerData *getContainerData(ProgramStateRef State,
254 const MemRegion *Cont);
255 ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont,
256 const ContainerData &CData);
257 bool isOutOfRange(ProgramStateRef State, const IteratorPosition &Pos);
260 IteratorChecker::IteratorChecker() {
261 OutOfRangeBugType.reset(
262 new BugType(this, "Iterator out of range", "Misuse of STL APIs"));
263 OutOfRangeBugType->setSuppressOnSink(true);
266 void IteratorChecker::checkPreCall(const CallEvent &Call,
267 CheckerContext &C) const {
268 // Check for out of range access
269 const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
273 if (Func->isOverloadedOperator()) {
274 if (ChecksEnabled[CK_IteratorRangeChecker] &&
275 isDereferenceOperator(Func->getOverloadedOperator())) {
276 // Check for dereference of out-of-range iterators
277 if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
278 verifyDereference(C, InstCall->getCXXThisVal());
280 verifyDereference(C, Call.getArgSVal(0));
286 void IteratorChecker::checkPostCall(const CallEvent &Call,
287 CheckerContext &C) const {
288 // Record new iterator positions and iterator position changes
289 const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
293 if (Func->isOverloadedOperator()) {
294 const auto Op = Func->getOverloadedOperator();
295 if (isSimpleComparisonOperator(Op)) {
296 if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
297 handleComparison(C, Call.getReturnValue(), InstCall->getCXXThisVal(),
298 Call.getArgSVal(0), Op);
300 handleComparison(C, Call.getReturnValue(), Call.getArgSVal(0),
301 Call.getArgSVal(1), Op);
305 const auto *OrigExpr = Call.getOriginExpr();
309 if (!isIteratorType(Call.getResultType()))
312 auto State = C.getState();
313 // Already bound to container?
314 if (getIteratorPosition(State, Call.getReturnValue()))
317 if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
318 if (isEndCall(Func)) {
319 handleEnd(C, OrigExpr, Call.getReturnValue(),
320 InstCall->getCXXThisVal());
325 // Copy-like and move constructors
326 if (isa<CXXConstructorCall>(&Call) && Call.getNumArgs() == 1) {
327 if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(0))) {
328 State = setIteratorPosition(State, Call.getReturnValue(), *Pos);
329 if (cast<CXXConstructorDecl>(Func)->isMoveConstructor()) {
330 State = removeIteratorPosition(State, Call.getArgSVal(0));
332 C.addTransition(State);
337 // Assumption: if return value is an iterator which is not yet bound to a
338 // container, then look for the first iterator argument, and
339 // bind the return value to the same container. This approach
340 // works for STL algorithms.
341 // FIXME: Add a more conservative mode
342 for (unsigned i = 0; i < Call.getNumArgs(); ++i) {
343 if (isIteratorType(Call.getArgExpr(i)->getType())) {
344 if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(i))) {
345 assignToContainer(C, OrigExpr, Call.getReturnValue(),
346 Pos->getContainer());
354 void IteratorChecker::checkPostStmt(const MaterializeTemporaryExpr *MTE,
355 CheckerContext &C) const {
356 /* Transfer iterator state to temporary objects */
357 auto State = C.getState();
358 const auto *LCtx = C.getLocationContext();
360 getIteratorPosition(State, State->getSVal(MTE->GetTemporaryExpr(), LCtx));
363 State = setIteratorPosition(State, State->getSVal(MTE, LCtx), *Pos);
364 C.addTransition(State);
367 void IteratorChecker::checkDeadSymbols(SymbolReaper &SR,
368 CheckerContext &C) const {
370 auto State = C.getState();
372 auto RegionMap = State->get<IteratorRegionMap>();
373 for (const auto Reg : RegionMap) {
374 if (!SR.isLiveRegion(Reg.first)) {
375 State = State->remove<IteratorRegionMap>(Reg.first);
379 auto SymbolMap = State->get<IteratorSymbolMap>();
380 for (const auto Sym : SymbolMap) {
381 if (!SR.isLive(Sym.first)) {
382 State = State->remove<IteratorSymbolMap>(Sym.first);
386 auto ContMap = State->get<ContainerMap>();
387 for (const auto Cont : ContMap) {
388 if (!SR.isLiveRegion(Cont.first)) {
389 State = State->remove<ContainerMap>(Cont.first);
393 auto ComparisonMap = State->get<IteratorComparisonMap>();
394 for (const auto Comp : ComparisonMap) {
395 if (!SR.isLive(Comp.first)) {
396 State = State->remove<IteratorComparisonMap>(Comp.first);
401 ProgramStateRef IteratorChecker::evalAssume(ProgramStateRef State, SVal Cond,
402 bool Assumption) const {
403 // Load recorded comparison and transfer iterator state between sides
404 // according to comparison operator and assumption
405 const auto *SE = Cond.getAsSymExpr();
409 auto Opc = getOpcode(SE);
410 if (Opc != BO_EQ && Opc != BO_NE)
413 bool Negated = false;
414 const auto *Comp = loadComparison(State, SE);
416 // Try negated comparison, which is a SymExpr to 0 integer comparison
417 const auto *SIE = dyn_cast<SymIntExpr>(SE);
421 if (SIE->getRHS() != 0)
425 Negated = SIE->getOpcode() == BO_EQ; // Equal to zero means negation
427 if (Opc != BO_EQ && Opc != BO_NE)
430 Comp = loadComparison(State, SE);
435 return processComparison(State, Comp->getLeft(), Comp->getRight(),
436 (Comp->isEquality() == Assumption) != Negated);
439 void IteratorChecker::handleComparison(CheckerContext &C, const SVal &RetVal,
440 const SVal &LVal, const SVal &RVal,
441 OverloadedOperatorKind Op) const {
442 // Record the operands and the operator of the comparison for the next
443 // evalAssume, if the result is a symbolic expression. If it is a concrete
444 // value (only one branch is possible), then transfer the state between
445 // the operands according to the operator and the result
446 auto State = C.getState();
447 if (const auto *Condition = RetVal.getAsSymbolicExpression()) {
448 const auto *LPos = getIteratorPosition(State, LVal);
449 const auto *RPos = getIteratorPosition(State, RVal);
452 State = saveComparison(State, Condition, LVal, RVal, Op == OO_EqualEqual);
453 C.addTransition(State);
454 } else if (const auto TruthVal = RetVal.getAs<nonloc::ConcreteInt>()) {
455 if ((State = processComparison(
456 State, getRegionOrSymbol(LVal), getRegionOrSymbol(RVal),
457 (Op == OO_EqualEqual) == (TruthVal->getValue() != 0)))) {
458 C.addTransition(State);
460 C.generateSink(State, C.getPredecessor());
465 void IteratorChecker::verifyDereference(CheckerContext &C,
466 const SVal &Val) const {
467 auto State = C.getState();
468 const auto *Pos = getIteratorPosition(State, Val);
469 if (Pos && isOutOfRange(State, *Pos)) {
470 // If I do not put a tag here, some range tests will fail
471 static CheckerProgramPointTag Tag("IteratorRangeChecker",
472 "IteratorOutOfRange");
473 auto *N = C.generateNonFatalErrorNode(State, &Tag);
477 reportOutOfRangeBug("Iterator accessed outside of its range.", Val, C, N);
481 void IteratorChecker::handleEnd(CheckerContext &C, const Expr *CE,
482 const SVal &RetVal, const SVal &Cont) const {
483 const auto *ContReg = Cont.getAsRegion();
487 while (const auto *CBOR = ContReg->getAs<CXXBaseObjectRegion>()) {
488 ContReg = CBOR->getSuperRegion();
491 // If the container already has an end symbol then use it. Otherwise first
493 auto State = C.getState();
494 auto EndSym = getContainerEnd(State, ContReg);
496 auto &SymMgr = C.getSymbolManager();
497 EndSym = SymMgr.conjureSymbol(CE, C.getLocationContext(),
498 C.getASTContext().LongTy, C.blockCount());
499 State = createContainerEnd(State, ContReg, EndSym);
501 State = setIteratorPosition(State, RetVal,
502 IteratorPosition::getPosition(ContReg, EndSym));
503 C.addTransition(State);
506 void IteratorChecker::assignToContainer(CheckerContext &C, const Expr *CE,
508 const MemRegion *Cont) const {
509 while (const auto *CBOR = Cont->getAs<CXXBaseObjectRegion>()) {
510 Cont = CBOR->getSuperRegion();
513 auto State = C.getState();
514 auto &SymMgr = C.getSymbolManager();
515 auto Sym = SymMgr.conjureSymbol(CE, C.getLocationContext(),
516 C.getASTContext().LongTy, C.blockCount());
517 State = setIteratorPosition(State, RetVal,
518 IteratorPosition::getPosition(Cont, Sym));
519 C.addTransition(State);
522 void IteratorChecker::reportOutOfRangeBug(const StringRef &Message,
523 const SVal &Val, CheckerContext &C,
524 ExplodedNode *ErrNode) const {
525 auto R = llvm::make_unique<BugReport>(*OutOfRangeBugType, Message, ErrNode);
526 R->markInteresting(Val);
527 C.emitReport(std::move(R));
532 bool isGreaterOrEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
533 bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,
534 BinaryOperator::Opcode Opc);
536 bool isIteratorType(const QualType &Type) {
537 if (Type->isPointerType())
540 const auto *CRD = Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl();
541 return isIterator(CRD);
544 bool isIterator(const CXXRecordDecl *CRD) {
548 const auto Name = CRD->getName();
549 if (!(Name.endswith_lower("iterator") || Name.endswith_lower("iter") ||
550 Name.endswith_lower("it")))
553 bool HasCopyCtor = false, HasCopyAssign = true, HasDtor = false,
554 HasPreIncrOp = false, HasPostIncrOp = false, HasDerefOp = false;
555 for (const auto *Method : CRD->methods()) {
556 if (const auto *Ctor = dyn_cast<CXXConstructorDecl>(Method)) {
557 if (Ctor->isCopyConstructor()) {
558 HasCopyCtor = !Ctor->isDeleted() && Ctor->getAccess() == AS_public;
562 if (const auto *Dtor = dyn_cast<CXXDestructorDecl>(Method)) {
563 HasDtor = !Dtor->isDeleted() && Dtor->getAccess() == AS_public;
566 if (Method->isCopyAssignmentOperator()) {
567 HasCopyAssign = !Method->isDeleted() && Method->getAccess() == AS_public;
570 if (!Method->isOverloadedOperator())
572 const auto OPK = Method->getOverloadedOperator();
573 if (OPK == OO_PlusPlus) {
574 HasPreIncrOp = HasPreIncrOp || (Method->getNumParams() == 0);
575 HasPostIncrOp = HasPostIncrOp || (Method->getNumParams() == 1);
578 if (OPK == OO_Star) {
579 HasDerefOp = (Method->getNumParams() == 0);
584 return HasCopyCtor && HasCopyAssign && HasDtor && HasPreIncrOp &&
585 HasPostIncrOp && HasDerefOp;
588 bool isEndCall(const FunctionDecl *Func) {
589 const auto *IdInfo = Func->getIdentifier();
592 return IdInfo->getName().endswith_lower("end");
595 bool isSimpleComparisonOperator(OverloadedOperatorKind OK) {
596 return OK == OO_EqualEqual || OK == OO_ExclaimEqual;
599 bool isDereferenceOperator(OverloadedOperatorKind OK) {
600 return OK == OO_Star || OK == OO_Arrow || OK == OO_ArrowStar ||
604 BinaryOperator::Opcode getOpcode(const SymExpr *SE) {
605 if (const auto *BSE = dyn_cast<BinarySymExpr>(SE)) {
606 return BSE->getOpcode();
607 } else if (const auto *SC = dyn_cast<SymbolConjured>(SE)) {
608 const auto *COE = dyn_cast<CXXOperatorCallExpr>(SC->getStmt());
610 return BO_Comma; // Extremal value, neither EQ nor NE
611 if (COE->getOperator() == OO_EqualEqual) {
613 } else if (COE->getOperator() == OO_ExclaimEqual) {
616 return BO_Comma; // Extremal value, neither EQ nor NE
618 return BO_Comma; // Extremal value, neither EQ nor NE
621 const RegionOrSymbol getRegionOrSymbol(const SVal &Val) {
622 if (const auto Reg = Val.getAsRegion()) {
624 } else if (const auto Sym = Val.getAsSymbol()) {
626 } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
627 return LCVal->getRegion();
629 return RegionOrSymbol();
632 const ProgramStateRef processComparison(ProgramStateRef State,
634 RegionOrSymbol RVal, bool Equal) {
635 const auto *LPos = getIteratorPosition(State, LVal);
636 const auto *RPos = getIteratorPosition(State, RVal);
638 State = adjustIteratorPosition(State, RVal, *LPos, Equal);
639 } else if (!LPos && RPos) {
640 State = adjustIteratorPosition(State, LVal, *RPos, Equal);
641 } else if (LPos && RPos) {
642 State = relateIteratorPositions(State, *LPos, *RPos, Equal);
647 const ProgramStateRef saveComparison(ProgramStateRef State,
648 const SymExpr *Condition, const SVal &LVal,
649 const SVal &RVal, bool Eq) {
650 const auto Left = getRegionOrSymbol(LVal);
651 const auto Right = getRegionOrSymbol(RVal);
654 return State->set<IteratorComparisonMap>(Condition,
655 IteratorComparison(Left, Right, Eq));
658 const IteratorComparison *loadComparison(ProgramStateRef State,
659 const SymExpr *Condition) {
660 return State->get<IteratorComparisonMap>(Condition);
663 SymbolRef getContainerEnd(ProgramStateRef State, const MemRegion *Cont) {
664 const auto *CDataPtr = getContainerData(State, Cont);
668 return CDataPtr->getEnd();
671 ProgramStateRef createContainerEnd(ProgramStateRef State, const MemRegion *Cont,
672 const SymbolRef Sym) {
673 // Only create if it does not exist
674 const auto *CDataPtr = getContainerData(State, Cont);
676 if (CDataPtr->getEnd()) {
679 const auto CData = CDataPtr->newEnd(Sym);
680 return setContainerData(State, Cont, CData);
683 const auto CData = ContainerData::fromEnd(Sym);
684 return setContainerData(State, Cont, CData);
688 const ContainerData *getContainerData(ProgramStateRef State,
689 const MemRegion *Cont) {
690 return State->get<ContainerMap>(Cont);
693 ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont,
694 const ContainerData &CData) {
695 return State->set<ContainerMap>(Cont, CData);
698 const IteratorPosition *getIteratorPosition(ProgramStateRef State,
700 if (const auto Reg = Val.getAsRegion()) {
701 return State->get<IteratorRegionMap>(Reg);
702 } else if (const auto Sym = Val.getAsSymbol()) {
703 return State->get<IteratorSymbolMap>(Sym);
704 } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
705 return State->get<IteratorRegionMap>(LCVal->getRegion());
710 const IteratorPosition *getIteratorPosition(ProgramStateRef State,
711 RegionOrSymbol RegOrSym) {
712 if (RegOrSym.is<const MemRegion *>()) {
713 return State->get<IteratorRegionMap>(RegOrSym.get<const MemRegion *>());
714 } else if (RegOrSym.is<SymbolRef>()) {
715 return State->get<IteratorSymbolMap>(RegOrSym.get<SymbolRef>());
720 ProgramStateRef setIteratorPosition(ProgramStateRef State, const SVal &Val,
721 const IteratorPosition &Pos) {
722 if (const auto Reg = Val.getAsRegion()) {
723 return State->set<IteratorRegionMap>(Reg, Pos);
724 } else if (const auto Sym = Val.getAsSymbol()) {
725 return State->set<IteratorSymbolMap>(Sym, Pos);
726 } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
727 return State->set<IteratorRegionMap>(LCVal->getRegion(), Pos);
732 ProgramStateRef setIteratorPosition(ProgramStateRef State,
733 RegionOrSymbol RegOrSym,
734 const IteratorPosition &Pos) {
735 if (RegOrSym.is<const MemRegion *>()) {
736 return State->set<IteratorRegionMap>(RegOrSym.get<const MemRegion *>(),
738 } else if (RegOrSym.is<SymbolRef>()) {
739 return State->set<IteratorSymbolMap>(RegOrSym.get<SymbolRef>(), Pos);
744 ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val) {
745 if (const auto Reg = Val.getAsRegion()) {
746 return State->remove<IteratorRegionMap>(Reg);
747 } else if (const auto Sym = Val.getAsSymbol()) {
748 return State->remove<IteratorSymbolMap>(Sym);
749 } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
750 return State->remove<IteratorRegionMap>(LCVal->getRegion());
755 ProgramStateRef adjustIteratorPosition(ProgramStateRef State,
756 RegionOrSymbol RegOrSym,
757 const IteratorPosition &Pos,
760 return setIteratorPosition(State, RegOrSym, Pos);
766 ProgramStateRef relateIteratorPositions(ProgramStateRef State,
767 const IteratorPosition &Pos1,
768 const IteratorPosition &Pos2,
770 // Try to compare them and get a defined value
771 auto &SVB = State->getStateManager().getSValBuilder();
772 const auto comparison =
773 SVB.evalBinOp(State, BO_EQ, nonloc::SymbolVal(Pos1.getOffset()),
774 nonloc::SymbolVal(Pos2.getOffset()), SVB.getConditionType())
775 .getAs<DefinedSVal>();
777 return State->assume(*comparison, Equal);
783 bool isOutOfRange(ProgramStateRef State, const IteratorPosition &Pos) {
784 const auto *Cont = Pos.getContainer();
785 const auto *CData = getContainerData(State, Cont);
789 // Out of range means less than the begin symbol or greater or equal to the
792 const auto End = CData->getEnd();
794 if (isGreaterOrEqual(State, Pos.getOffset(), End)) {
802 bool isGreaterOrEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) {
803 return compare(State, Sym1, Sym2, BO_GE);
806 bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,
807 BinaryOperator::Opcode Opc) {
808 auto &SMgr = State->getStateManager();
809 auto &SVB = SMgr.getSValBuilder();
811 const auto comparison =
812 SVB.evalBinOp(State, Opc, nonloc::SymbolVal(Sym1),
813 nonloc::SymbolVal(Sym2), SVB.getConditionType())
814 .getAs<DefinedSVal>();
817 return !!State->assume(*comparison, true);
825 #define REGISTER_CHECKER(name) \
826 void ento::register##name(CheckerManager &Mgr) { \
827 auto *checker = Mgr.registerChecker<IteratorChecker>(); \
828 checker->ChecksEnabled[IteratorChecker::CK_##name] = true; \
829 checker->CheckNames[IteratorChecker::CK_##name] = \
830 Mgr.getCurrentCheckName(); \
833 REGISTER_CHECKER(IteratorRangeChecker)