clang/lib/StaticAnalyzer/Checkers/Iterator.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-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