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 15 namespace clang { 16 namespace ento { 17 namespace iterator { 18 19 bool 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 27 bool 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 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; 74 } 75 76 bool 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 87 bool 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 98 bool 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 112 bool 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 126 bool isAccessOperator(OverloadedOperatorKind OK) { 127 return isDereferenceOperator(OK) || isIncrementOperator(OK) || 128 isDecrementOperator(OK) || isRandomIncrOrDecrOperator(OK); 129 } 130 131 bool isAccessOperator(UnaryOperatorKind OK) { 132 return isDereferenceOperator(OK) || isIncrementOperator(OK) || 133 isDecrementOperator(OK); 134 } 135 136 bool isAccessOperator(BinaryOperatorKind OK) { 137 return isDereferenceOperator(OK) || isRandomIncrOrDecrOperator(OK); 138 } 139 140 bool isDereferenceOperator(OverloadedOperatorKind OK) { 141 return OK == OO_Star || OK == OO_Arrow || OK == OO_ArrowStar || 142 OK == OO_Subscript; 143 } 144 145 bool isDereferenceOperator(UnaryOperatorKind OK) { 146 return OK == UO_Deref; 147 } 148 149 bool isDereferenceOperator(BinaryOperatorKind OK) { 150 return OK == BO_PtrMemI; 151 } 152 153 bool isIncrementOperator(OverloadedOperatorKind OK) { 154 return OK == OO_PlusPlus; 155 } 156 157 bool isIncrementOperator(UnaryOperatorKind OK) { 158 return OK == UO_PreInc || OK == UO_PostInc; 159 } 160 161 bool isDecrementOperator(OverloadedOperatorKind OK) { 162 return OK == OO_MinusMinus; 163 } 164 165 bool isDecrementOperator(UnaryOperatorKind OK) { 166 return OK == UO_PreDec || OK == UO_PostDec; 167 } 168 169 bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK) { 170 return OK == OO_Plus || OK == OO_PlusEqual || OK == OO_Minus || 171 OK == OO_MinusEqual; 172 } 173 174 bool isRandomIncrOrDecrOperator(BinaryOperatorKind OK) { 175 return OK == BO_Add || OK == BO_AddAssign || 176 OK == BO_Sub || OK == BO_SubAssign; 177 } 178 179 const ContainerData *getContainerData(ProgramStateRef State, 180 const MemRegion *Cont) { 181 return State->get<ContainerMap>(Cont); 182 } 183 184 const 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 196 ProgramStateRef 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 209 ProgramStateRef 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 223 ProgramStateRef 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? 263 ProgramStateRef 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 297 bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2, 298 BinaryOperator::Opcode Opc) { 299 return compare(State, nonloc::SymbolVal(Sym1), nonloc::SymbolVal(Sym2), Opc); 300 } 301 302 bool 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