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