1 //=== Iterator.cpp - Common functions for iterator checkers. -------*- C++ -*-//
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
7 //===----------------------------------------------------------------------===//
9 // Defines common functions to be used by the itertor checkers .
11 //===----------------------------------------------------------------------===//
19 bool isIteratorType(const QualType &Type) {
20 if (Type->isPointerType())
23 const auto *CRD = Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl();
24 return isIterator(CRD);
27 bool isIterator(const CXXRecordDecl *CRD) {
31 const auto Name = CRD->getName();
32 if (!(Name.endswith_lower("iterator") || Name.endswith_lower("iter") ||
33 Name.endswith_lower("it")))
36 bool HasCopyCtor = false, HasCopyAssign = true, HasDtor = false,
37 HasPreIncrOp = false, HasPostIncrOp = false, HasDerefOp = false;
38 for (const auto *Method : CRD->methods()) {
39 if (const auto *Ctor = dyn_cast<CXXConstructorDecl>(Method)) {
40 if (Ctor->isCopyConstructor()) {
41 HasCopyCtor = !Ctor->isDeleted() && Ctor->getAccess() == AS_public;
45 if (const auto *Dtor = dyn_cast<CXXDestructorDecl>(Method)) {
46 HasDtor = !Dtor->isDeleted() && Dtor->getAccess() == AS_public;
49 if (Method->isCopyAssignmentOperator()) {
50 HasCopyAssign = !Method->isDeleted() && Method->getAccess() == AS_public;
53 if (!Method->isOverloadedOperator())
55 const auto OPK = Method->getOverloadedOperator();
56 if (OPK == OO_PlusPlus) {
57 HasPreIncrOp = HasPreIncrOp || (Method->getNumParams() == 0);
58 HasPostIncrOp = HasPostIncrOp || (Method->getNumParams() == 1);
62 HasDerefOp = (Method->getNumParams() == 0);
67 return HasCopyCtor && HasCopyAssign && HasDtor && HasPreIncrOp &&
68 HasPostIncrOp && HasDerefOp;
71 bool isComparisonOperator(OverloadedOperatorKind OK) {
72 return OK == OO_EqualEqual || OK == OO_ExclaimEqual || OK == OO_Less ||
73 OK == OO_LessEqual || OK == OO_Greater || OK == OO_GreaterEqual;
76 bool isInsertCall(const FunctionDecl *Func) {
77 const auto *IdInfo = Func->getIdentifier();
80 if (Func->getNumParams() < 2 || Func->getNumParams() > 3)
82 if (!isIteratorType(Func->getParamDecl(0)->getType()))
84 return IdInfo->getName() == "insert";
87 bool isEmplaceCall(const FunctionDecl *Func) {
88 const auto *IdInfo = Func->getIdentifier();
91 if (Func->getNumParams() < 2)
93 if (!isIteratorType(Func->getParamDecl(0)->getType()))
95 return IdInfo->getName() == "emplace";
98 bool isEraseCall(const FunctionDecl *Func) {
99 const auto *IdInfo = Func->getIdentifier();
102 if (Func->getNumParams() < 1 || Func->getNumParams() > 2)
104 if (!isIteratorType(Func->getParamDecl(0)->getType()))
106 if (Func->getNumParams() == 2 &&
107 !isIteratorType(Func->getParamDecl(1)->getType()))
109 return IdInfo->getName() == "erase";
112 bool isEraseAfterCall(const FunctionDecl *Func) {
113 const auto *IdInfo = Func->getIdentifier();
116 if (Func->getNumParams() < 1 || Func->getNumParams() > 2)
118 if (!isIteratorType(Func->getParamDecl(0)->getType()))
120 if (Func->getNumParams() == 2 &&
121 !isIteratorType(Func->getParamDecl(1)->getType()))
123 return IdInfo->getName() == "erase_after";
126 bool isAccessOperator(OverloadedOperatorKind OK) {
127 return isDereferenceOperator(OK) || isIncrementOperator(OK) ||
128 isDecrementOperator(OK) || isRandomIncrOrDecrOperator(OK);
131 bool isDereferenceOperator(OverloadedOperatorKind OK) {
132 return OK == OO_Star || OK == OO_Arrow || OK == OO_ArrowStar ||
136 bool isIncrementOperator(OverloadedOperatorKind OK) {
137 return OK == OO_PlusPlus;
140 bool isDecrementOperator(OverloadedOperatorKind OK) {
141 return OK == OO_MinusMinus;
144 bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK) {
145 return OK == OO_Plus || OK == OO_PlusEqual || OK == OO_Minus ||
149 const ContainerData *getContainerData(ProgramStateRef State,
150 const MemRegion *Cont) {
151 return State->get<ContainerMap>(Cont);
154 const IteratorPosition *getIteratorPosition(ProgramStateRef State,
156 if (auto Reg = Val.getAsRegion()) {
157 Reg = Reg->getMostDerivedObjectRegion();
158 return State->get<IteratorRegionMap>(Reg);
159 } else if (const auto Sym = Val.getAsSymbol()) {
160 return State->get<IteratorSymbolMap>(Sym);
161 } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
162 return State->get<IteratorRegionMap>(LCVal->getRegion());
167 ProgramStateRef setIteratorPosition(ProgramStateRef State, const SVal &Val,
168 const IteratorPosition &Pos) {
169 if (auto Reg = Val.getAsRegion()) {
170 Reg = Reg->getMostDerivedObjectRegion();
171 return State->set<IteratorRegionMap>(Reg, Pos);
172 } else if (const auto Sym = Val.getAsSymbol()) {
173 return State->set<IteratorSymbolMap>(Sym, Pos);
174 } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
175 return State->set<IteratorRegionMap>(LCVal->getRegion(), Pos);
180 ProgramStateRef advancePosition(ProgramStateRef State, const SVal &Iter,
181 OverloadedOperatorKind Op,
182 const SVal &Distance) {
183 const auto *Pos = getIteratorPosition(State, Iter);
187 auto &SymMgr = State->getStateManager().getSymbolManager();
188 auto &SVB = State->getStateManager().getSValBuilder();
190 assert ((Op == OO_Plus || Op == OO_PlusEqual ||
191 Op == OO_Minus || Op == OO_MinusEqual) &&
192 "Advance operator must be one of +, -, += and -=.");
193 auto BinOp = (Op == OO_Plus || Op == OO_PlusEqual) ? BO_Add : BO_Sub;
194 if (const auto IntDist = Distance.getAs<nonloc::ConcreteInt>()) {
195 // For concrete integers we can calculate the new position
197 Pos->setTo(SVB.evalBinOp(State, BinOp,
198 nonloc::SymbolVal(Pos->getOffset()),
199 *IntDist, SymMgr.getType(Pos->getOffset()))
201 return setIteratorPosition(State, Iter, NewPos);
207 bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,
208 BinaryOperator::Opcode Opc) {
209 return compare(State, nonloc::SymbolVal(Sym1), nonloc::SymbolVal(Sym2), Opc);
212 bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2,
213 BinaryOperator::Opcode Opc) {
214 auto &SVB = State->getStateManager().getSValBuilder();
216 const auto comparison =
217 SVB.evalBinOp(State, Opc, NL1, NL2, SVB.getConditionType());
219 assert(comparison.getAs<DefinedSVal>() &&
220 "Symbol comparison must be a `DefinedSVal`");
222 return !State->assume(comparison.castAs<DefinedSVal>(), false);
225 } // namespace iterator