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