1//=== Iterator.cpp - Common functions for iterator checkers. -------*- 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 common functions to be used by the itertor checkers . 10// 11//===----------------------------------------------------------------------===// 12 13#include "Iterator.h" 14 15namespace clang { 16namespace ento { 17namespace iterator { 18 19bool isIteratorType(const QualType &Type) { 20 if (Type->isPointerType()) 21 return true; 22 23 const auto *CRD = Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl(); 24 return isIterator(CRD); 25} 26 27bool isIterator(const CXXRecordDecl *CRD) { 28 if (!CRD) 29 return false; 30 31 const auto Name = CRD->getName(); 32 if (!(Name.ends_with_insensitive("iterator") || 33 Name.ends_with_insensitive("iter") || Name.ends_with_insensitive("it"))) 34 return false; 35 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; 42 } 43 continue; 44 } 45 if (const auto *Dtor = dyn_cast<CXXDestructorDecl>(Method)) { 46 HasDtor = !Dtor->isDeleted() && Dtor->getAccess() == AS_public; 47 continue; 48 } 49 if (Method->isCopyAssignmentOperator()) { 50 HasCopyAssign = !Method->isDeleted() && Method->getAccess() == AS_public; 51 continue; 52 } 53 if (!Method->isOverloadedOperator()) 54 continue; 55 const auto OPK = Method->getOverloadedOperator(); 56 if (OPK == OO_PlusPlus) { 57 HasPreIncrOp = HasPreIncrOp || (Method->getNumParams() == 0); 58 HasPostIncrOp = HasPostIncrOp || (Method->getNumParams() == 1); 59 continue; 60 } 61 if (OPK == OO_Star) { 62 HasDerefOp = (Method->getNumParams() == 0); 63 continue; 64 } 65 } 66 67 return HasCopyCtor && HasCopyAssign && HasDtor && HasPreIncrOp && 68 HasPostIncrOp && HasDerefOp; 69} 70 71bool isComparisonOperator(OverloadedOperatorKind OK) { 72 return OK == OO_EqualEqual || OK == OO_ExclaimEqual || OK == OO_Less || 73 OK == OO_LessEqual || OK == OO_Greater || OK == OO_GreaterEqual; 74} 75 76bool isInsertCall(const FunctionDecl *Func) { 77 const auto *IdInfo = Func->getIdentifier(); 78 if (!IdInfo) 79 return false; 80 if (Func->getNumParams() < 2 || Func->getNumParams() > 3) 81 return false; 82 if (!isIteratorType(Func->getParamDecl(0)->getType())) 83 return false; 84 return IdInfo->getName() == "insert"; 85} 86 87bool isEmplaceCall(const FunctionDecl *Func) { 88 const auto *IdInfo = Func->getIdentifier(); 89 if (!IdInfo) 90 return false; 91 if (Func->getNumParams() < 2) 92 return false; 93 if (!isIteratorType(Func->getParamDecl(0)->getType())) 94 return false; 95 return IdInfo->getName() == "emplace"; 96} 97 98bool isEraseCall(const FunctionDecl *Func) { 99 const auto *IdInfo = Func->getIdentifier(); 100 if (!IdInfo) 101 return false; 102 if (Func->getNumParams() < 1 || Func->getNumParams() > 2) 103 return false; 104 if (!isIteratorType(Func->getParamDecl(0)->getType())) 105 return false; 106 if (Func->getNumParams() == 2 && 107 !isIteratorType(Func->getParamDecl(1)->getType())) 108 return false; 109 return IdInfo->getName() == "erase"; 110} 111 112bool isEraseAfterCall(const FunctionDecl *Func) { 113 const auto *IdInfo = Func->getIdentifier(); 114 if (!IdInfo) 115 return false; 116 if (Func->getNumParams() < 1 || Func->getNumParams() > 2) 117 return false; 118 if (!isIteratorType(Func->getParamDecl(0)->getType())) 119 return false; 120 if (Func->getNumParams() == 2 && 121 !isIteratorType(Func->getParamDecl(1)->getType())) 122 return false; 123 return IdInfo->getName() == "erase_after"; 124} 125 126bool isAccessOperator(OverloadedOperatorKind OK) { 127 return isDereferenceOperator(OK) || isIncrementOperator(OK) || 128 isDecrementOperator(OK) || isRandomIncrOrDecrOperator(OK); 129} 130 131bool isAccessOperator(UnaryOperatorKind OK) { 132 return isDereferenceOperator(OK) || isIncrementOperator(OK) || 133 isDecrementOperator(OK); 134} 135 136bool isAccessOperator(BinaryOperatorKind OK) { 137 return isDereferenceOperator(OK) || isRandomIncrOrDecrOperator(OK); 138} 139 140bool isDereferenceOperator(OverloadedOperatorKind OK) { 141 return OK == OO_Star || OK == OO_Arrow || OK == OO_ArrowStar || 142 OK == OO_Subscript; 143} 144 145bool isDereferenceOperator(UnaryOperatorKind OK) { 146 return OK == UO_Deref; 147} 148 149bool isDereferenceOperator(BinaryOperatorKind OK) { 150 return OK == BO_PtrMemI; 151} 152 153bool isIncrementOperator(OverloadedOperatorKind OK) { 154 return OK == OO_PlusPlus; 155} 156 157bool isIncrementOperator(UnaryOperatorKind OK) { 158 return OK == UO_PreInc || OK == UO_PostInc; 159} 160 161bool isDecrementOperator(OverloadedOperatorKind OK) { 162 return OK == OO_MinusMinus; 163} 164 165bool isDecrementOperator(UnaryOperatorKind OK) { 166 return OK == UO_PreDec || OK == UO_PostDec; 167} 168 169bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK) { 170 return OK == OO_Plus || OK == OO_PlusEqual || OK == OO_Minus || 171 OK == OO_MinusEqual; 172} 173 174bool isRandomIncrOrDecrOperator(BinaryOperatorKind OK) { 175 return OK == BO_Add || OK == BO_AddAssign || 176 OK == BO_Sub || OK == BO_SubAssign; 177} 178 179const ContainerData *getContainerData(ProgramStateRef State, 180 const MemRegion *Cont) { 181 return State->get<ContainerMap>(Cont); 182} 183 184const IteratorPosition *getIteratorPosition(ProgramStateRef State, SVal Val) { 185 if (auto Reg = Val.getAsRegion()) { 186 Reg = Reg->getMostDerivedObjectRegion(); 187 return State->get<IteratorRegionMap>(Reg); 188 } else if (const auto Sym = Val.getAsSymbol()) { 189 return State->get<IteratorSymbolMap>(Sym); 190 } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) { 191 return State->get<IteratorRegionMap>(LCVal->getRegion()); 192 } 193 return nullptr; 194} 195 196ProgramStateRef setIteratorPosition(ProgramStateRef State, SVal Val, 197 const IteratorPosition &Pos) { 198 if (auto Reg = Val.getAsRegion()) { 199 Reg = Reg->getMostDerivedObjectRegion(); 200 return State->set<IteratorRegionMap>(Reg, Pos); 201 } else if (const auto Sym = Val.getAsSymbol()) { 202 return State->set<IteratorSymbolMap>(Sym, Pos); 203 } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) { 204 return State->set<IteratorRegionMap>(LCVal->getRegion(), Pos); 205 } 206 return nullptr; 207} 208 209ProgramStateRef createIteratorPosition(ProgramStateRef State, SVal Val, 210 const MemRegion *Cont, const Stmt *S, 211 const LocationContext *LCtx, 212 unsigned blockCount) { 213 auto &StateMgr = State->getStateManager(); 214 auto &SymMgr = StateMgr.getSymbolManager(); 215 auto &ACtx = StateMgr.getContext(); 216 217 auto Sym = SymMgr.conjureSymbol(S, LCtx, ACtx.LongTy, blockCount); 218 State = assumeNoOverflow(State, Sym, 4); 219 return setIteratorPosition(State, Val, 220 IteratorPosition::getPosition(Cont, Sym)); 221} 222 223ProgramStateRef advancePosition(ProgramStateRef State, SVal Iter, 224 OverloadedOperatorKind Op, SVal Distance) { 225 const auto *Pos = getIteratorPosition(State, Iter); 226 if (!Pos) 227 return nullptr; 228 229 auto &SymMgr = State->getStateManager().getSymbolManager(); 230 auto &SVB = State->getStateManager().getSValBuilder(); 231 auto &BVF = State->getStateManager().getBasicVals(); 232 233 assert ((Op == OO_Plus || Op == OO_PlusEqual || 234 Op == OO_Minus || Op == OO_MinusEqual) && 235 "Advance operator must be one of +, -, += and -=."); 236 auto BinOp = (Op == OO_Plus || Op == OO_PlusEqual) ? BO_Add : BO_Sub; 237 const auto IntDistOp = Distance.getAs<nonloc::ConcreteInt>(); 238 if (!IntDistOp) 239 return nullptr; 240 241 // For concrete integers we can calculate the new position 242 nonloc::ConcreteInt IntDist = *IntDistOp; 243 244 if (IntDist.getValue().isNegative()) { 245 IntDist = nonloc::ConcreteInt(BVF.getValue(-IntDist.getValue())); 246 BinOp = (BinOp == BO_Add) ? BO_Sub : BO_Add; 247 } 248 const auto NewPos = 249 Pos->setTo(SVB.evalBinOp(State, BinOp, 250 nonloc::SymbolVal(Pos->getOffset()), 251 IntDist, SymMgr.getType(Pos->getOffset())) 252 .getAsSymbol()); 253 return setIteratorPosition(State, Iter, NewPos); 254} 255 256// This function tells the analyzer's engine that symbols produced by our 257// checker, most notably iterator positions, are relatively small. 258// A distance between items in the container should not be very large. 259// By assuming that it is within around 1/8 of the address space, 260// we can help the analyzer perform operations on these symbols 261// without being afraid of integer overflows. 262// FIXME: Should we provide it as an API, so that all checkers could use it? 263ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym, 264 long Scale) { 265 SValBuilder &SVB = State->getStateManager().getSValBuilder(); 266 BasicValueFactory &BV = SVB.getBasicValueFactory(); 267 268 QualType T = Sym->getType(); 269 assert(T->isSignedIntegerOrEnumerationType()); 270 APSIntType AT = BV.getAPSIntType(T); 271 272 ProgramStateRef NewState = State; 273 274 llvm::APSInt Max = AT.getMaxValue() / AT.getValue(Scale); 275 SVal IsCappedFromAbove = 276 SVB.evalBinOpNN(State, BO_LE, nonloc::SymbolVal(Sym), 277 nonloc::ConcreteInt(Max), SVB.getConditionType()); 278 if (auto DV = IsCappedFromAbove.getAs<DefinedSVal>()) { 279 NewState = NewState->assume(*DV, true); 280 if (!NewState) 281 return State; 282 } 283 284 llvm::APSInt Min = -Max; 285 SVal IsCappedFromBelow = 286 SVB.evalBinOpNN(State, BO_GE, nonloc::SymbolVal(Sym), 287 nonloc::ConcreteInt(Min), SVB.getConditionType()); 288 if (auto DV = IsCappedFromBelow.getAs<DefinedSVal>()) { 289 NewState = NewState->assume(*DV, true); 290 if (!NewState) 291 return State; 292 } 293 294 return NewState; 295} 296 297bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2, 298 BinaryOperator::Opcode Opc) { 299 return compare(State, nonloc::SymbolVal(Sym1), nonloc::SymbolVal(Sym2), Opc); 300} 301 302bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2, 303 BinaryOperator::Opcode Opc) { 304 auto &SVB = State->getStateManager().getSValBuilder(); 305 306 const auto comparison = 307 SVB.evalBinOp(State, Opc, NL1, NL2, SVB.getConditionType()); 308 309 assert(isa<DefinedSVal>(comparison) && 310 "Symbol comparison must be a `DefinedSVal`"); 311 312 return !State->assume(comparison.castAs<DefinedSVal>(), false); 313} 314 315} // namespace iterator 316} // namespace ento 317} // namespace clang 318