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, 185 const SVal &Val) { 186 if (auto Reg = Val.getAsRegion()) { 187 Reg = Reg->getMostDerivedObjectRegion(); 188 return State->get<IteratorRegionMap>(Reg); 189 } else if (const auto Sym = Val.getAsSymbol()) { 190 return State->get<IteratorSymbolMap>(Sym); 191 } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) { 192 return State->get<IteratorRegionMap>(LCVal->getRegion()); 193 } 194 return nullptr; 195 } 196 197 ProgramStateRef setIteratorPosition(ProgramStateRef State, const SVal &Val, 198 const IteratorPosition &Pos) { 199 if (auto Reg = Val.getAsRegion()) { 200 Reg = Reg->getMostDerivedObjectRegion(); 201 return State->set<IteratorRegionMap>(Reg, Pos); 202 } else if (const auto Sym = Val.getAsSymbol()) { 203 return State->set<IteratorSymbolMap>(Sym, Pos); 204 } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) { 205 return State->set<IteratorRegionMap>(LCVal->getRegion(), Pos); 206 } 207 return nullptr; 208 } 209 210 ProgramStateRef createIteratorPosition(ProgramStateRef State, const SVal &Val, 211 const MemRegion *Cont, const Stmt* S, 212 const LocationContext *LCtx, 213 unsigned blockCount) { 214 auto &StateMgr = State->getStateManager(); 215 auto &SymMgr = StateMgr.getSymbolManager(); 216 auto &ACtx = StateMgr.getContext(); 217 218 auto Sym = SymMgr.conjureSymbol(S, LCtx, ACtx.LongTy, blockCount); 219 State = assumeNoOverflow(State, Sym, 4); 220 return setIteratorPosition(State, Val, 221 IteratorPosition::getPosition(Cont, Sym)); 222 } 223 224 ProgramStateRef advancePosition(ProgramStateRef State, const SVal &Iter, 225 OverloadedOperatorKind Op, 226 const SVal &Distance) { 227 const auto *Pos = getIteratorPosition(State, Iter); 228 if (!Pos) 229 return nullptr; 230 231 auto &SymMgr = State->getStateManager().getSymbolManager(); 232 auto &SVB = State->getStateManager().getSValBuilder(); 233 auto &BVF = State->getStateManager().getBasicVals(); 234 235 assert ((Op == OO_Plus || Op == OO_PlusEqual || 236 Op == OO_Minus || Op == OO_MinusEqual) && 237 "Advance operator must be one of +, -, += and -=."); 238 auto BinOp = (Op == OO_Plus || Op == OO_PlusEqual) ? BO_Add : BO_Sub; 239 const auto IntDistOp = Distance.getAs<nonloc::ConcreteInt>(); 240 if (!IntDistOp) 241 return nullptr; 242 243 // For concrete integers we can calculate the new position 244 nonloc::ConcreteInt IntDist = *IntDistOp; 245 246 if (IntDist.getValue().isNegative()) { 247 IntDist = nonloc::ConcreteInt(BVF.getValue(-IntDist.getValue())); 248 BinOp = (BinOp == BO_Add) ? BO_Sub : BO_Add; 249 } 250 const auto NewPos = 251 Pos->setTo(SVB.evalBinOp(State, BinOp, 252 nonloc::SymbolVal(Pos->getOffset()), 253 IntDist, SymMgr.getType(Pos->getOffset())) 254 .getAsSymbol()); 255 return setIteratorPosition(State, Iter, NewPos); 256 } 257 258 // This function tells the analyzer's engine that symbols produced by our 259 // checker, most notably iterator positions, are relatively small. 260 // A distance between items in the container should not be very large. 261 // By assuming that it is within around 1/8 of the address space, 262 // we can help the analyzer perform operations on these symbols 263 // without being afraid of integer overflows. 264 // FIXME: Should we provide it as an API, so that all checkers could use it? 265 ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym, 266 long Scale) { 267 SValBuilder &SVB = State->getStateManager().getSValBuilder(); 268 BasicValueFactory &BV = SVB.getBasicValueFactory(); 269 270 QualType T = Sym->getType(); 271 assert(T->isSignedIntegerOrEnumerationType()); 272 APSIntType AT = BV.getAPSIntType(T); 273 274 ProgramStateRef NewState = State; 275 276 llvm::APSInt Max = AT.getMaxValue() / AT.getValue(Scale); 277 SVal IsCappedFromAbove = 278 SVB.evalBinOpNN(State, BO_LE, nonloc::SymbolVal(Sym), 279 nonloc::ConcreteInt(Max), SVB.getConditionType()); 280 if (auto DV = IsCappedFromAbove.getAs<DefinedSVal>()) { 281 NewState = NewState->assume(*DV, true); 282 if (!NewState) 283 return State; 284 } 285 286 llvm::APSInt Min = -Max; 287 SVal IsCappedFromBelow = 288 SVB.evalBinOpNN(State, BO_GE, nonloc::SymbolVal(Sym), 289 nonloc::ConcreteInt(Min), SVB.getConditionType()); 290 if (auto DV = IsCappedFromBelow.getAs<DefinedSVal>()) { 291 NewState = NewState->assume(*DV, true); 292 if (!NewState) 293 return State; 294 } 295 296 return NewState; 297 } 298 299 bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2, 300 BinaryOperator::Opcode Opc) { 301 return compare(State, nonloc::SymbolVal(Sym1), nonloc::SymbolVal(Sym2), Opc); 302 } 303 304 bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2, 305 BinaryOperator::Opcode Opc) { 306 auto &SVB = State->getStateManager().getSValBuilder(); 307 308 const auto comparison = 309 SVB.evalBinOp(State, Opc, NL1, NL2, SVB.getConditionType()); 310 311 assert(isa<DefinedSVal>(comparison) && 312 "Symbol comparison must be a `DefinedSVal`"); 313 314 return !State->assume(comparison.castAs<DefinedSVal>(), false); 315 } 316 317 } // namespace iterator 318 } // namespace ento 319 } // namespace clang 320