319 lines · cpp
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-exception6//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,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 224ProgramStateRef 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 position243 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 our258// 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 symbols262// without being afraid of integer overflows.263// FIXME: Should we provide it as an API, so that all checkers could use it?264ProgramStateRef 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 298bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,299 BinaryOperator::Opcode Opc) {300 return compare(State, nonloc::SymbolVal(Sym1), nonloc::SymbolVal(Sym2), Opc);301}302 303bool 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 iterator317} // namespace ento318} // namespace clang319