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.endswith_lower("iterator") || Name.endswith_lower("iter") || 33 Name.endswith_lower("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 isDereferenceOperator(OverloadedOperatorKind OK) { 132 return OK == OO_Star || OK == OO_Arrow || OK == OO_ArrowStar || 133 OK == OO_Subscript; 134 } 135 136 bool isIncrementOperator(OverloadedOperatorKind OK) { 137 return OK == OO_PlusPlus; 138 } 139 140 bool isDecrementOperator(OverloadedOperatorKind OK) { 141 return OK == OO_MinusMinus; 142 } 143 144 bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK) { 145 return OK == OO_Plus || OK == OO_PlusEqual || OK == OO_Minus || 146 OK == OO_MinusEqual; 147 } 148 149 const ContainerData *getContainerData(ProgramStateRef State, 150 const MemRegion *Cont) { 151 return State->get<ContainerMap>(Cont); 152 } 153 154 const IteratorPosition *getIteratorPosition(ProgramStateRef State, 155 const SVal &Val) { 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()); 163 } 164 return nullptr; 165 } 166 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); 176 } 177 return nullptr; 178 } 179 180 ProgramStateRef createIteratorPosition(ProgramStateRef State, const SVal &Val, 181 const MemRegion *Cont, const Stmt* S, 182 const LocationContext *LCtx, 183 unsigned blockCount) { 184 auto &StateMgr = State->getStateManager(); 185 auto &SymMgr = StateMgr.getSymbolManager(); 186 auto &ACtx = StateMgr.getContext(); 187 188 auto Sym = SymMgr.conjureSymbol(S, LCtx, ACtx.LongTy, blockCount); 189 State = assumeNoOverflow(State, Sym, 4); 190 return setIteratorPosition(State, Val, 191 IteratorPosition::getPosition(Cont, Sym)); 192 } 193 194 ProgramStateRef advancePosition(ProgramStateRef State, const SVal &Iter, 195 OverloadedOperatorKind Op, 196 const SVal &Distance) { 197 const auto *Pos = getIteratorPosition(State, Iter); 198 if (!Pos) 199 return nullptr; 200 201 auto &SymMgr = State->getStateManager().getSymbolManager(); 202 auto &SVB = State->getStateManager().getSValBuilder(); 203 auto &BVF = State->getStateManager().getBasicVals(); 204 205 assert ((Op == OO_Plus || Op == OO_PlusEqual || 206 Op == OO_Minus || Op == OO_MinusEqual) && 207 "Advance operator must be one of +, -, += and -=."); 208 auto BinOp = (Op == OO_Plus || Op == OO_PlusEqual) ? BO_Add : BO_Sub; 209 const auto IntDistOp = Distance.getAs<nonloc::ConcreteInt>(); 210 if (!IntDistOp) 211 return nullptr; 212 213 // For concrete integers we can calculate the new position 214 nonloc::ConcreteInt IntDist = *IntDistOp; 215 216 if (IntDist.getValue().isNegative()) { 217 IntDist = nonloc::ConcreteInt(BVF.getValue(-IntDist.getValue())); 218 BinOp = (BinOp == BO_Add) ? BO_Sub : BO_Add; 219 } 220 const auto NewPos = 221 Pos->setTo(SVB.evalBinOp(State, BinOp, 222 nonloc::SymbolVal(Pos->getOffset()), 223 IntDist, SymMgr.getType(Pos->getOffset())) 224 .getAsSymbol()); 225 return setIteratorPosition(State, Iter, NewPos); 226 } 227 228 // This function tells the analyzer's engine that symbols produced by our 229 // checker, most notably iterator positions, are relatively small. 230 // A distance between items in the container should not be very large. 231 // By assuming that it is within around 1/8 of the address space, 232 // we can help the analyzer perform operations on these symbols 233 // without being afraid of integer overflows. 234 // FIXME: Should we provide it as an API, so that all checkers could use it? 235 ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym, 236 long Scale) { 237 SValBuilder &SVB = State->getStateManager().getSValBuilder(); 238 BasicValueFactory &BV = SVB.getBasicValueFactory(); 239 240 QualType T = Sym->getType(); 241 assert(T->isSignedIntegerOrEnumerationType()); 242 APSIntType AT = BV.getAPSIntType(T); 243 244 ProgramStateRef NewState = State; 245 246 llvm::APSInt Max = AT.getMaxValue() / AT.getValue(Scale); 247 SVal IsCappedFromAbove = 248 SVB.evalBinOpNN(State, BO_LE, nonloc::SymbolVal(Sym), 249 nonloc::ConcreteInt(Max), SVB.getConditionType()); 250 if (auto DV = IsCappedFromAbove.getAs<DefinedSVal>()) { 251 NewState = NewState->assume(*DV, true); 252 if (!NewState) 253 return State; 254 } 255 256 llvm::APSInt Min = -Max; 257 SVal IsCappedFromBelow = 258 SVB.evalBinOpNN(State, BO_GE, nonloc::SymbolVal(Sym), 259 nonloc::ConcreteInt(Min), SVB.getConditionType()); 260 if (auto DV = IsCappedFromBelow.getAs<DefinedSVal>()) { 261 NewState = NewState->assume(*DV, true); 262 if (!NewState) 263 return State; 264 } 265 266 return NewState; 267 } 268 269 bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2, 270 BinaryOperator::Opcode Opc) { 271 return compare(State, nonloc::SymbolVal(Sym1), nonloc::SymbolVal(Sym2), Opc); 272 } 273 274 bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2, 275 BinaryOperator::Opcode Opc) { 276 auto &SVB = State->getStateManager().getSValBuilder(); 277 278 const auto comparison = 279 SVB.evalBinOp(State, Opc, NL1, NL2, SVB.getConditionType()); 280 281 assert(comparison.getAs<DefinedSVal>() && 282 "Symbol comparison must be a `DefinedSVal`"); 283 284 return !State->assume(comparison.castAs<DefinedSVal>(), false); 285 } 286 287 } // namespace iterator 288 } // namespace ento 289 } // namespace clang 290