1356843Sdim//===-- MismatchedIteratorChecker.cpp -----------------------------*- C++ -*--// 2356843Sdim// 3356843Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4356843Sdim// See https://llvm.org/LICENSE.txt for license information. 5356843Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6356843Sdim// 7356843Sdim//===----------------------------------------------------------------------===// 8356843Sdim// 9356843Sdim// Defines a checker for mistakenly applying a foreign iterator on a container 10356843Sdim// and for using iterators of two different containers in a context where 11356843Sdim// iterators of the same container should be used. 12356843Sdim// 13356843Sdim//===----------------------------------------------------------------------===// 14356843Sdim 15356843Sdim#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h" 16356843Sdim#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" 17356843Sdim#include "clang/StaticAnalyzer/Core/Checker.h" 18356843Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" 19356843Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" 20356843Sdim 21356843Sdim 22356843Sdim#include "Iterator.h" 23356843Sdim 24356843Sdimusing namespace clang; 25356843Sdimusing namespace ento; 26356843Sdimusing namespace iterator; 27356843Sdim 28356843Sdimnamespace { 29356843Sdim 30356843Sdimclass MismatchedIteratorChecker 31356843Sdim : public Checker<check::PreCall> { 32356843Sdim 33356843Sdim std::unique_ptr<BugType> MismatchedBugType; 34356843Sdim 35356843Sdim void verifyMatch(CheckerContext &C, const SVal &Iter, 36356843Sdim const MemRegion *Cont) const; 37356843Sdim void verifyMatch(CheckerContext &C, const SVal &Iter1, 38356843Sdim const SVal &Iter2) const; 39356843Sdim void reportBug(const StringRef &Message, const SVal &Val1, 40356843Sdim const SVal &Val2, CheckerContext &C, 41356843Sdim ExplodedNode *ErrNode) const; 42356843Sdim void reportBug(const StringRef &Message, const SVal &Val, 43356843Sdim const MemRegion *Reg, CheckerContext &C, 44356843Sdim ExplodedNode *ErrNode) const; 45356843Sdim 46356843Sdimpublic: 47356843Sdim MismatchedIteratorChecker(); 48356843Sdim 49356843Sdim void checkPreCall(const CallEvent &Call, CheckerContext &C) const; 50356843Sdim 51356843Sdim}; 52356843Sdim 53356843Sdim} // namespace 54356843Sdim 55356843SdimMismatchedIteratorChecker::MismatchedIteratorChecker() { 56356843Sdim MismatchedBugType.reset( 57356843Sdim new BugType(this, "Iterator(s) mismatched", "Misuse of STL APIs", 58356843Sdim /*SuppressOnSink=*/true)); 59356843Sdim} 60356843Sdim 61356843Sdimvoid MismatchedIteratorChecker::checkPreCall(const CallEvent &Call, 62356843Sdim CheckerContext &C) const { 63356843Sdim // Check for iterator mismatches 64356843Sdim const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl()); 65356843Sdim if (!Func) 66356843Sdim return; 67356843Sdim 68356843Sdim if (Func->isOverloadedOperator() && 69356843Sdim isComparisonOperator(Func->getOverloadedOperator())) { 70356843Sdim // Check for comparisons of iterators of different containers 71356843Sdim if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) { 72356843Sdim if (Call.getNumArgs() < 1) 73356843Sdim return; 74356843Sdim 75356843Sdim if (!isIteratorType(InstCall->getCXXThisExpr()->getType()) || 76356843Sdim !isIteratorType(Call.getArgExpr(0)->getType())) 77356843Sdim return; 78356843Sdim 79356843Sdim verifyMatch(C, InstCall->getCXXThisVal(), Call.getArgSVal(0)); 80356843Sdim } else { 81356843Sdim if (Call.getNumArgs() < 2) 82356843Sdim return; 83356843Sdim 84356843Sdim if (!isIteratorType(Call.getArgExpr(0)->getType()) || 85356843Sdim !isIteratorType(Call.getArgExpr(1)->getType())) 86356843Sdim return; 87356843Sdim 88356843Sdim verifyMatch(C, Call.getArgSVal(0), Call.getArgSVal(1)); 89356843Sdim } 90356843Sdim } else if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) { 91356843Sdim const auto *ContReg = InstCall->getCXXThisVal().getAsRegion(); 92356843Sdim if (!ContReg) 93356843Sdim return; 94356843Sdim // Check for erase, insert and emplace using iterator of another container 95356843Sdim if (isEraseCall(Func) || isEraseAfterCall(Func)) { 96356843Sdim verifyMatch(C, Call.getArgSVal(0), 97356843Sdim InstCall->getCXXThisVal().getAsRegion()); 98356843Sdim if (Call.getNumArgs() == 2) { 99356843Sdim verifyMatch(C, Call.getArgSVal(1), 100356843Sdim InstCall->getCXXThisVal().getAsRegion()); 101356843Sdim } 102356843Sdim } else if (isInsertCall(Func)) { 103356843Sdim verifyMatch(C, Call.getArgSVal(0), 104356843Sdim InstCall->getCXXThisVal().getAsRegion()); 105356843Sdim if (Call.getNumArgs() == 3 && 106356843Sdim isIteratorType(Call.getArgExpr(1)->getType()) && 107356843Sdim isIteratorType(Call.getArgExpr(2)->getType())) { 108356843Sdim verifyMatch(C, Call.getArgSVal(1), Call.getArgSVal(2)); 109356843Sdim } 110356843Sdim } else if (isEmplaceCall(Func)) { 111356843Sdim verifyMatch(C, Call.getArgSVal(0), 112356843Sdim InstCall->getCXXThisVal().getAsRegion()); 113356843Sdim } 114356843Sdim } else if (isa<CXXConstructorCall>(&Call)) { 115356843Sdim // Check match of first-last iterator pair in a constructor of a container 116356843Sdim if (Call.getNumArgs() < 2) 117356843Sdim return; 118356843Sdim 119356843Sdim const auto *Ctr = cast<CXXConstructorDecl>(Call.getDecl()); 120356843Sdim if (Ctr->getNumParams() < 2) 121356843Sdim return; 122356843Sdim 123356843Sdim if (Ctr->getParamDecl(0)->getName() != "first" || 124356843Sdim Ctr->getParamDecl(1)->getName() != "last") 125356843Sdim return; 126356843Sdim 127356843Sdim if (!isIteratorType(Call.getArgExpr(0)->getType()) || 128356843Sdim !isIteratorType(Call.getArgExpr(1)->getType())) 129356843Sdim return; 130356843Sdim 131356843Sdim verifyMatch(C, Call.getArgSVal(0), Call.getArgSVal(1)); 132356843Sdim } else { 133356843Sdim // The main purpose of iterators is to abstract away from different 134356843Sdim // containers and provide a (maybe limited) uniform access to them. 135356843Sdim // This implies that any correctly written template function that 136356843Sdim // works on multiple containers using iterators takes different 137356843Sdim // template parameters for different containers. So we can safely 138356843Sdim // assume that passing iterators of different containers as arguments 139356843Sdim // whose type replaces the same template parameter is a bug. 140356843Sdim // 141356843Sdim // Example: 142356843Sdim // template<typename I1, typename I2> 143356843Sdim // void f(I1 first1, I1 last1, I2 first2, I2 last2); 144356843Sdim // 145356843Sdim // In this case the first two arguments to f() must be iterators must belong 146356843Sdim // to the same container and the last to also to the same container but 147356843Sdim // not necessarily to the same as the first two. 148356843Sdim 149356843Sdim const auto *Templ = Func->getPrimaryTemplate(); 150356843Sdim if (!Templ) 151356843Sdim return; 152356843Sdim 153356843Sdim const auto *TParams = Templ->getTemplateParameters(); 154356843Sdim const auto *TArgs = Func->getTemplateSpecializationArgs(); 155356843Sdim 156356843Sdim // Iterate over all the template parameters 157356843Sdim for (size_t I = 0; I < TParams->size(); ++I) { 158356843Sdim const auto *TPDecl = dyn_cast<TemplateTypeParmDecl>(TParams->getParam(I)); 159356843Sdim if (!TPDecl) 160356843Sdim continue; 161356843Sdim 162356843Sdim if (TPDecl->isParameterPack()) 163356843Sdim continue; 164356843Sdim 165356843Sdim const auto TAType = TArgs->get(I).getAsType(); 166356843Sdim if (!isIteratorType(TAType)) 167356843Sdim continue; 168356843Sdim 169356843Sdim SVal LHS = UndefinedVal(); 170356843Sdim 171356843Sdim // For every template parameter which is an iterator type in the 172356843Sdim // instantiation look for all functions' parameters' type by it and 173356843Sdim // check whether they belong to the same container 174356843Sdim for (auto J = 0U; J < Func->getNumParams(); ++J) { 175356843Sdim const auto *Param = Func->getParamDecl(J); 176356843Sdim const auto *ParamType = 177356843Sdim Param->getType()->getAs<SubstTemplateTypeParmType>(); 178356843Sdim if (!ParamType || 179356843Sdim ParamType->getReplacedParameter()->getDecl() != TPDecl) 180356843Sdim continue; 181356843Sdim if (LHS.isUndef()) { 182356843Sdim LHS = Call.getArgSVal(J); 183356843Sdim } else { 184356843Sdim verifyMatch(C, LHS, Call.getArgSVal(J)); 185356843Sdim } 186356843Sdim } 187356843Sdim } 188356843Sdim } 189356843Sdim} 190356843Sdim 191356843Sdimvoid MismatchedIteratorChecker::verifyMatch(CheckerContext &C, const SVal &Iter, 192356843Sdim const MemRegion *Cont) const { 193356843Sdim // Verify match between a container and the container of an iterator 194356843Sdim Cont = Cont->getMostDerivedObjectRegion(); 195356843Sdim 196356843Sdim if (const auto *ContSym = Cont->getSymbolicBase()) { 197356843Sdim if (isa<SymbolConjured>(ContSym->getSymbol())) 198356843Sdim return; 199356843Sdim } 200356843Sdim 201356843Sdim auto State = C.getState(); 202356843Sdim const auto *Pos = getIteratorPosition(State, Iter); 203356843Sdim if (!Pos) 204356843Sdim return; 205356843Sdim 206356843Sdim const auto *IterCont = Pos->getContainer(); 207356843Sdim 208356843Sdim // Skip symbolic regions based on conjured symbols. Two conjured symbols 209356843Sdim // may or may not be the same. For example, the same function can return 210356843Sdim // the same or a different container but we get different conjured symbols 211356843Sdim // for each call. This may cause false positives so omit them from the check. 212356843Sdim if (const auto *ContSym = IterCont->getSymbolicBase()) { 213356843Sdim if (isa<SymbolConjured>(ContSym->getSymbol())) 214356843Sdim return; 215356843Sdim } 216356843Sdim 217356843Sdim if (IterCont != Cont) { 218356843Sdim auto *N = C.generateNonFatalErrorNode(State); 219356843Sdim if (!N) { 220356843Sdim return; 221356843Sdim } 222356843Sdim reportBug("Container accessed using foreign iterator argument.", 223356843Sdim Iter, Cont, C, N); 224356843Sdim } 225356843Sdim} 226356843Sdim 227356843Sdimvoid MismatchedIteratorChecker::verifyMatch(CheckerContext &C, 228356843Sdim const SVal &Iter1, 229356843Sdim const SVal &Iter2) const { 230356843Sdim // Verify match between the containers of two iterators 231356843Sdim auto State = C.getState(); 232356843Sdim const auto *Pos1 = getIteratorPosition(State, Iter1); 233356843Sdim if (!Pos1) 234356843Sdim return; 235356843Sdim 236356843Sdim const auto *IterCont1 = Pos1->getContainer(); 237356843Sdim 238356843Sdim // Skip symbolic regions based on conjured symbols. Two conjured symbols 239356843Sdim // may or may not be the same. For example, the same function can return 240356843Sdim // the same or a different container but we get different conjured symbols 241356843Sdim // for each call. This may cause false positives so omit them from the check. 242356843Sdim if (const auto *ContSym = IterCont1->getSymbolicBase()) { 243356843Sdim if (isa<SymbolConjured>(ContSym->getSymbol())) 244356843Sdim return; 245356843Sdim } 246356843Sdim 247356843Sdim const auto *Pos2 = getIteratorPosition(State, Iter2); 248356843Sdim if (!Pos2) 249356843Sdim return; 250356843Sdim 251356843Sdim const auto *IterCont2 = Pos2->getContainer(); 252356843Sdim if (const auto *ContSym = IterCont2->getSymbolicBase()) { 253356843Sdim if (isa<SymbolConjured>(ContSym->getSymbol())) 254356843Sdim return; 255356843Sdim } 256356843Sdim 257356843Sdim if (IterCont1 != IterCont2) { 258356843Sdim auto *N = C.generateNonFatalErrorNode(State); 259356843Sdim if (!N) 260356843Sdim return; 261356843Sdim reportBug("Iterators of different containers used where the " 262356843Sdim "same container is expected.", Iter1, Iter2, C, N); 263356843Sdim } 264356843Sdim} 265356843Sdim 266356843Sdimvoid MismatchedIteratorChecker::reportBug(const StringRef &Message, 267356843Sdim const SVal &Val1, 268356843Sdim const SVal &Val2, 269356843Sdim CheckerContext &C, 270356843Sdim ExplodedNode *ErrNode) const { 271356843Sdim auto R = std::make_unique<PathSensitiveBugReport>(*MismatchedBugType, Message, 272356843Sdim ErrNode); 273356843Sdim R->markInteresting(Val1); 274356843Sdim R->markInteresting(Val2); 275356843Sdim C.emitReport(std::move(R)); 276356843Sdim} 277356843Sdim 278356843Sdimvoid MismatchedIteratorChecker::reportBug(const StringRef &Message, 279356843Sdim const SVal &Val, const MemRegion *Reg, 280356843Sdim CheckerContext &C, 281356843Sdim ExplodedNode *ErrNode) const { 282356843Sdim auto R = std::make_unique<PathSensitiveBugReport>(*MismatchedBugType, Message, 283356843Sdim ErrNode); 284356843Sdim R->markInteresting(Val); 285356843Sdim R->markInteresting(Reg); 286356843Sdim C.emitReport(std::move(R)); 287356843Sdim} 288356843Sdim 289356843Sdimvoid ento::registerMismatchedIteratorChecker(CheckerManager &mgr) { 290356843Sdim mgr.registerChecker<MismatchedIteratorChecker>(); 291356843Sdim} 292356843Sdim 293356843Sdimbool ento::shouldRegisterMismatchedIteratorChecker(const LangOptions &LO) { 294356843Sdim return true; 295356843Sdim} 296