clang/lib/StaticAnalyzer/Checkers/MismatchedIteratorChecker.cpp

   1 //===-- MismatchedIteratorChecker.cpp -----------------------------*- 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 a checker for mistakenly applying a foreign iterator on a container
  10 // and for using iterators of two different containers in a context where
  11 // iterators of the same container should be used.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
  16 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
  17 #include "clang/StaticAnalyzer/Core/Checker.h"
  18 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
  19 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
  20
  21
  22 #include "Iterator.h"
  23
  24 using namespace clang;
  25 using namespace ento;
  26 using namespace iterator;
  27
  28 namespace {
  29
  30 class MismatchedIteratorChecker
  31   : public Checker<check::PreCall, check::PreStmt<BinaryOperator>> {
  32
  33   std::unique_ptr<BugType> MismatchedBugType;
  34
  35   void verifyMatch(CheckerContext &C, const SVal &Iter,
  36                    const MemRegion *Cont) const;
  37   void verifyMatch(CheckerContext &C, const SVal &Iter1,
  38                    const SVal &Iter2) const;
  39   void reportBug(const StringRef &Message, const SVal &Val1,
  40                  const SVal &Val2, CheckerContext &C,
  41                  ExplodedNode *ErrNode) const;
  42   void reportBug(const StringRef &Message, const SVal &Val,
  43                  const MemRegion *Reg, CheckerContext &C,
  44                  ExplodedNode *ErrNode) const;
  45
  46 public:
  47   MismatchedIteratorChecker();
  48
  49   void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
  50   void checkPreStmt(const BinaryOperator *BO, CheckerContext &C) const;
  51
  52 };
  53
  54 } // namespace
  55
  56 MismatchedIteratorChecker::MismatchedIteratorChecker() {
  57   MismatchedBugType.reset(
  58       new BugType(this, "Iterator(s) mismatched", "Misuse of STL APIs",
  59                   /*SuppressOnSink=*/true));
  60 }
  61
  62 void MismatchedIteratorChecker::checkPreCall(const CallEvent &Call,
  63                                              CheckerContext &C) const {
  64   // Check for iterator mismatches
  65   const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
  66   if (!Func)
  67     return;
  68
  69   if (Func->isOverloadedOperator() &&
  70       isComparisonOperator(Func->getOverloadedOperator())) {
  71     // Check for comparisons of iterators of different containers
  72     if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
  73       if (Call.getNumArgs() < 1)
  74         return;
  75
  76       if (!isIteratorType(InstCall->getCXXThisExpr()->getType()) ||
  77           !isIteratorType(Call.getArgExpr(0)->getType()))
  78         return;
  79
  80       verifyMatch(C, InstCall->getCXXThisVal(), Call.getArgSVal(0));
  81     } else {
  82       if (Call.getNumArgs() < 2)
  83         return;
  84
  85       if (!isIteratorType(Call.getArgExpr(0)->getType()) ||
  86           !isIteratorType(Call.getArgExpr(1)->getType()))
  87         return;
  88
  89       verifyMatch(C, Call.getArgSVal(0), Call.getArgSVal(1));
  90     }
  91   } else if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
  92     const auto *ContReg = InstCall->getCXXThisVal().getAsRegion();
  93     if (!ContReg)
  94       return;
  95     // Check for erase, insert and emplace using iterator of another container
  96     if (isEraseCall(Func) || isEraseAfterCall(Func)) {
  97       verifyMatch(C, Call.getArgSVal(0),
  98                   InstCall->getCXXThisVal().getAsRegion());
  99       if (Call.getNumArgs() == 2) {
 100         verifyMatch(C, Call.getArgSVal(1),
 101                     InstCall->getCXXThisVal().getAsRegion());
 102       }
 103     } else if (isInsertCall(Func)) {
 104       verifyMatch(C, Call.getArgSVal(0),
 105                   InstCall->getCXXThisVal().getAsRegion());
 106       if (Call.getNumArgs() == 3 &&
 107           isIteratorType(Call.getArgExpr(1)->getType()) &&
 108           isIteratorType(Call.getArgExpr(2)->getType())) {
 109         verifyMatch(C, Call.getArgSVal(1), Call.getArgSVal(2));
 110       }
 111     } else if (isEmplaceCall(Func)) {
 112       verifyMatch(C, Call.getArgSVal(0),
 113                   InstCall->getCXXThisVal().getAsRegion());
 114     }
 115   } else if (isa<CXXConstructorCall>(&Call)) {
 116     // Check match of first-last iterator pair in a constructor of a container
 117     if (Call.getNumArgs() < 2)
 118       return;
 119
 120     const auto *Ctr = cast<CXXConstructorDecl>(Call.getDecl());
 121     if (Ctr->getNumParams() < 2)
 122       return;
 123
 124     if (Ctr->getParamDecl(0)->getName() != "first" ||
 125         Ctr->getParamDecl(1)->getName() != "last")
 126       return;
 127
 128     if (!isIteratorType(Call.getArgExpr(0)->getType()) ||
 129         !isIteratorType(Call.getArgExpr(1)->getType()))
 130       return;
 131
 132     verifyMatch(C, Call.getArgSVal(0), Call.getArgSVal(1));
 133   } else {
 134     // The main purpose of iterators is to abstract away from different
 135     // containers and provide a (maybe limited) uniform access to them.
 136     // This implies that any correctly written template function that
 137     // works on multiple containers using iterators takes different
 138     // template parameters for different containers. So we can safely
 139     // assume that passing iterators of different containers as arguments
 140     // whose type replaces the same template parameter is a bug.
 141     //
 142     // Example:
 143     // template<typename I1, typename I2>
 144     // void f(I1 first1, I1 last1, I2 first2, I2 last2);
 145     //
 146     // In this case the first two arguments to f() must be iterators must belong
 147     // to the same container and the last to also to the same container but
 148     // not necessarily to the same as the first two.
 149
 150     const auto *Templ = Func->getPrimaryTemplate();
 151     if (!Templ)
 152       return;
 153
 154     const auto *TParams = Templ->getTemplateParameters();
 155     const auto *TArgs = Func->getTemplateSpecializationArgs();
 156
 157     // Iterate over all the template parameters
 158     for (size_t I = 0; I < TParams->size(); ++I) {
 159       const auto *TPDecl = dyn_cast<TemplateTypeParmDecl>(TParams->getParam(I));
 160       if (!TPDecl)
 161         continue;
 162
 163       if (TPDecl->isParameterPack())
 164         continue;
 165
 166       const auto TAType = TArgs->get(I).getAsType();
 167       if (!isIteratorType(TAType))
 168         continue;
 169
 170       SVal LHS = UndefinedVal();
 171
 172       // For every template parameter which is an iterator type in the
 173       // instantiation look for all functions' parameters' type by it and
 174       // check whether they belong to the same container
 175       for (auto J = 0U; J < Func->getNumParams(); ++J) {
 176         const auto *Param = Func->getParamDecl(J);
 177         const auto *ParamType =
 178             Param->getType()->getAs<SubstTemplateTypeParmType>();
 179         if (!ParamType)
 180           continue;
 181         const TemplateTypeParmDecl *D = ParamType->getReplacedParameter();
 182         if (D != TPDecl)
 183           continue;
 184         if (LHS.isUndef()) {
 185           LHS = Call.getArgSVal(J);
 186         } else {
 187           verifyMatch(C, LHS, Call.getArgSVal(J));
 188         }
 189       }
 190     }
 191   }
 192 }
 193
 194 void MismatchedIteratorChecker::checkPreStmt(const BinaryOperator *BO,
 195                                              CheckerContext &C) const {
 196   if (!BO->isComparisonOp())
 197     return;
 198
 199   ProgramStateRef State = C.getState();
 200   SVal LVal = State->getSVal(BO->getLHS(), C.getLocationContext());
 201   SVal RVal = State->getSVal(BO->getRHS(), C.getLocationContext());
 202   verifyMatch(C, LVal, RVal);
 203 }
 204
 205 void MismatchedIteratorChecker::verifyMatch(CheckerContext &C, const SVal &Iter,
 206                                             const MemRegion *Cont) const {
 207   // Verify match between a container and the container of an iterator
 208   Cont = Cont->getMostDerivedObjectRegion();
 209
 210   if (const auto *ContSym = Cont->getSymbolicBase()) {
 211     if (isa<SymbolConjured>(ContSym->getSymbol()))
 212       return;
 213   }
 214
 215   auto State = C.getState();
 216   const auto *Pos = getIteratorPosition(State, Iter);
 217   if (!Pos)
 218     return;
 219
 220   const auto *IterCont = Pos->getContainer();
 221
 222   // Skip symbolic regions based on conjured symbols. Two conjured symbols
 223   // may or may not be the same. For example, the same function can return
 224   // the same or a different container but we get different conjured symbols
 225   // for each call. This may cause false positives so omit them from the check.
 226   if (const auto *ContSym = IterCont->getSymbolicBase()) {
 227     if (isa<SymbolConjured>(ContSym->getSymbol()))
 228       return;
 229   }
 230
 231   if (IterCont != Cont) {
 232     auto *N = C.generateNonFatalErrorNode(State);
 233     if (!N) {
 234       return;
 235     }
 236     reportBug("Container accessed using foreign iterator argument.",
 237                         Iter, Cont, C, N);
 238   }
 239 }
 240
 241 void MismatchedIteratorChecker::verifyMatch(CheckerContext &C,
 242                                             const SVal &Iter1,
 243                                             const SVal &Iter2) const {
 244   // Verify match between the containers of two iterators
 245   auto State = C.getState();
 246   const auto *Pos1 = getIteratorPosition(State, Iter1);
 247   if (!Pos1)
 248     return;
 249
 250   const auto *IterCont1 = Pos1->getContainer();
 251
 252   // Skip symbolic regions based on conjured symbols. Two conjured symbols
 253   // may or may not be the same. For example, the same function can return
 254   // the same or a different container but we get different conjured symbols
 255   // for each call. This may cause false positives so omit them from the check.
 256   if (const auto *ContSym = IterCont1->getSymbolicBase()) {
 257     if (isa<SymbolConjured>(ContSym->getSymbol()))
 258       return;
 259   }
 260
 261   const auto *Pos2 = getIteratorPosition(State, Iter2);
 262   if (!Pos2)
 263     return;
 264
 265   const auto *IterCont2 = Pos2->getContainer();
 266   if (const auto *ContSym = IterCont2->getSymbolicBase()) {
 267     if (isa<SymbolConjured>(ContSym->getSymbol()))
 268       return;
 269   }
 270
 271   if (IterCont1 != IterCont2) {
 272     auto *N = C.generateNonFatalErrorNode(State);
 273     if (!N)
 274       return;
 275     reportBug("Iterators of different containers used where the "
 276                         "same container is expected.", Iter1, Iter2, C, N);
 277   }
 278 }
 279
 280 void MismatchedIteratorChecker::reportBug(const StringRef &Message,
 281                                           const SVal &Val1,
 282                                           const SVal &Val2,
 283                                           CheckerContext &C,
 284                                           ExplodedNode *ErrNode) const {
 285   auto R = std::make_unique<PathSensitiveBugReport>(*MismatchedBugType, Message,
 286                                                     ErrNode);
 287   R->markInteresting(Val1);
 288   R->markInteresting(Val2);
 289   C.emitReport(std::move(R));
 290 }
 291
 292 void MismatchedIteratorChecker::reportBug(const StringRef &Message,
 293                                           const SVal &Val, const MemRegion *Reg,
 294                                           CheckerContext &C,
 295                                           ExplodedNode *ErrNode) const {
 296   auto R = std::make_unique<PathSensitiveBugReport>(*MismatchedBugType, Message,
 297                                                     ErrNode);
 298   R->markInteresting(Val);
 299   R->markInteresting(Reg);
 300   C.emitReport(std::move(R));
 301 }
 302
 303 void ento::registerMismatchedIteratorChecker(CheckerManager &mgr) {
 304   mgr.registerChecker<MismatchedIteratorChecker>();
 305 }
 306
 307 bool ento::shouldRegisterMismatchedIteratorChecker(const CheckerManager &mgr) {
 308   return true;
 309 }