//===-- MismatchedIteratorChecker.cpp -----------------------------*- C++ -*--//

//

// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

// See https://llvm.org/LICENSE.txt for license information.

// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

//

//===----------------------------------------------------------------------===//

//

// Defines a checker for mistakenly applying a foreign iterator on a container

// and for using iterators of two different containers in a context where

// iterators of the same container should be used.

//

//===----------------------------------------------------------------------===//

#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"

#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"

#include "clang/StaticAnalyzer/Core/Checker.h"

#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"

#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"

#include "Iterator.h"

using namespace clang;

using namespace ento;

using namespace iterator;

namespace {

class MismatchedIteratorChecker

  : public Checker<check::PreCall, check::PreStmt<BinaryOperator>> {

  std::unique_ptr<BugType> MismatchedBugType;

  void verifyMatch(CheckerContext &C, const SVal &Iter,

                   const MemRegion *Cont) const;

  void verifyMatch(CheckerContext &C, const SVal &Iter1,

                   const SVal &Iter2) const;

  void reportBug(const StringRef &Message, const SVal &Val1,

                 const SVal &Val2, CheckerContext &C,

                 ExplodedNode *ErrNode) const;

  void reportBug(const StringRef &Message, const SVal &Val,

                 const MemRegion *Reg, CheckerContext &C,

                 ExplodedNode *ErrNode) const;

public:

  MismatchedIteratorChecker();

  void checkPreCall(const CallEvent &Call, CheckerContext &C) const;

  void checkPreStmt(const BinaryOperator *BO, CheckerContext &C) const;

};

} // namespace

MismatchedIteratorChecker::MismatchedIteratorChecker() {

  MismatchedBugType.reset(

      new BugType(this, "Iterator(s) mismatched", "Misuse of STL APIs",

                  /*SuppressOnSink=*/true));

}

void MismatchedIteratorChecker::checkPreCall(const CallEvent &Call,

                                             CheckerContext &C) const {

  // Check for iterator mismatches

  const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());

  if (!Func)

    return;

  if (Func->isOverloadedOperator() &&

      
isComparisonOperator(Func->getOverloadedOperator())46
) {

    // Check for comparisons of iterators of different containers

    if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {

      if (Call.getNumArgs() < 1)

        return;

      if (!isIteratorType(InstCall->getCXXThisExpr()->getType()) ||

          !isIteratorType(Call.getArgExpr(0)->getType()))

        return;

      verifyMatch(C, InstCall->getCXXThisVal(), Call.getArgSVal(0));

    } else {

      if (Call.getNumArgs() < 2)

        return;

      if (!isIteratorType(Call.getArgExpr(0)->getType()) ||

          !isIteratorType(Call.getArgExpr(1)->getType()))

        return;

      verifyMatch(C, Call.getArgSVal(0), Call.getArgSVal(1));

    }

  } else if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {

    const auto *ContReg = InstCall->getCXXThisVal().getAsRegion();

    if (!ContReg)

      return;

    // Check for erase, insert and emplace using iterator of another container

    if (isEraseCall(Func) || 
isEraseAfterCall(Func)208
) {

      verifyMatch(C, Call.getArgSVal(0),

                  InstCall->getCXXThisVal().getAsRegion());

      if (Call.getNumArgs() == 2) {

        verifyMatch(C, Call.getArgSVal(1),

                    InstCall->getCXXThisVal().getAsRegion());

      }

    } else if (isInsertCall(Func)) {

      verifyMatch(C, Call.getArgSVal(0),

                  InstCall->getCXXThisVal().getAsRegion());

      if (Call.getNumArgs() == 3 &&

          
isIteratorType(Call.getArgExpr(1)->getType())12
 &&

          
isIteratorType(Call.getArgExpr(2)->getType())8
) {

        verifyMatch(C, Call.getArgSVal(1), Call.getArgSVal(2));

      }

    } else if (isEmplaceCall(Func)) {

      verifyMatch(C, Call.getArgSVal(0),

                  InstCall->getCXXThisVal().getAsRegion());

    }

  } else 
if (134
isa<CXXConstructorCall>(&Call)134
) {

    // Check match of first-last iterator pair in a constructor of a container

    if (Call.getNumArgs() < 2)

      return;

    const auto *Ctr = cast<CXXConstructorDecl>(Call.getDecl());

    if (Ctr->getNumParams() < 2)

      return;

    if (Ctr->getParamDecl(0)->getName() != "first" ||

        Ctr->getParamDecl(1)->getName() != "last")

      return;

    if (!isIteratorType(Call.getArgExpr(0)->getType()) ||

        !isIteratorType(Call.getArgExpr(1)->getType()))

      return;

    verifyMatch(C, Call.getArgSVal(0), Call.getArgSVal(1));

  } else {

    // The main purpose of iterators is to abstract away from different

    // containers and provide a (maybe limited) uniform access to them.

    // This implies that any correctly written template function that

    // works on multiple containers using iterators takes different

    // template parameters for different containers. So we can safely

    // assume that passing iterators of different containers as arguments

    // whose type replaces the same template parameter is a bug.

    //

    // Example:

    // template<typename I1, typename I2>

    // void f(I1 first1, I1 last1, I2 first2, I2 last2);

    //

    // In this case the first two arguments to f() must be iterators must belong

    // to the same container and the last to also to the same container but

    // not necessarily to the same as the first two.

    const auto *Templ = Func->getPrimaryTemplate();

    if (!Templ)

      return;

    const auto *TParams = Templ->getTemplateParameters();

    const auto *TArgs = Func->getTemplateSpecializationArgs();

    // Iterate over all the template parameters

    for (size_t I = 0; I < TParams->size(); 
++I36
) {

      const auto *TPDecl = dyn_cast<TemplateTypeParmDecl>(TParams->getParam(I));

      if (!TPDecl)

        continue;

      if (TPDecl->isParameterPack())

        continue;

      const auto TAType = TArgs->get(I).getAsType();

      if (!isIteratorType(TAType))

        continue;

      SVal LHS = UndefinedVal();

      // For every template parameter which is an iterator type in the

      // instantiation look for all functions' parameters' type by it and

      // check whether they belong to the same container

      for (auto J = 0U; J < Func->getNumParams(); 
++J102
) {

        const auto *Param = Func->getParamDecl(J);

        const auto *ParamType =

            Param->getType()->getAs<SubstTemplateTypeParmType>();

        if (!ParamType)

          continue;

        const TemplateTypeParmDecl *D = ParamType->getReplacedParameter();

        if (D != TPDecl)

          continue;

        if (LHS.isUndef()) {

          LHS = Call.getArgSVal(J);

        } else {

          verifyMatch(C, LHS, Call.getArgSVal(J));

        }

      }

    }

  }

}

void MismatchedIteratorChecker::checkPreStmt(const BinaryOperator *BO,

                                             CheckerContext &C) const {

  if (!BO->isComparisonOp())

    return;

  ProgramStateRef State = C.getState();

  SVal LVal = State->getSVal(BO->getLHS(), C.getLocationContext());

  SVal RVal = State->getSVal(BO->getRHS(), C.getLocationContext());

  verifyMatch(C, LVal, RVal);

}

void MismatchedIteratorChecker::verifyMatch(CheckerContext &C, const SVal &Iter,

                                            const MemRegion *Cont) const {

  // Verify match between a container and the container of an iterator

  Cont = Cont->getMostDerivedObjectRegion();

  if (const auto *ContSym = Cont->getSymbolicBase()) {

    if (isa<SymbolConjured>(ContSym->getSymbol()))

      return;

  }

  auto State = C.getState();

  const auto *Pos = getIteratorPosition(State, Iter);

  if (!Pos)

    return;

  const auto *IterCont = Pos->getContainer();

  // Skip symbolic regions based on conjured symbols. Two conjured symbols

  // may or may not be the same. For example, the same function can return

  // the same or a different container but we get different conjured symbols

  // for each call. This may cause false positives so omit them from the check.

  if (const auto *ContSym = IterCont->getSymbolicBase()) {

    if (isa<SymbolConjured>(ContSym->getSymbol()))

      return;

  }

  if (IterCont != Cont) {

    auto *N = C.generateNonFatalErrorNode(State);

    if (!N) {

      return;

    }

    reportBug("Container accessed using foreign iterator argument.",

                        Iter, Cont, C, N);

  }

}

void MismatchedIteratorChecker::verifyMatch(CheckerContext &C,

                                            const SVal &Iter1,

                                            const SVal &Iter2) const {

  // Verify match between the containers of two iterators

  auto State = C.getState();

  const auto *Pos1 = getIteratorPosition(State, Iter1);

  if (!Pos1)

    return;

  const auto *IterCont1 = Pos1->getContainer();

  // Skip symbolic regions based on conjured symbols. Two conjured symbols

  // may or may not be the same. For example, the same function can return

  // the same or a different container but we get different conjured symbols

  // for each call. This may cause false positives so omit them from the check.

  if (const auto *ContSym = IterCont1->getSymbolicBase()) {

    if (isa<SymbolConjured>(ContSym->getSymbol()))

      return;

  }

  const auto *Pos2 = getIteratorPosition(State, Iter2);

  if (!Pos2)

    return;

  const auto *IterCont2 = Pos2->getContainer();

  if (const auto *ContSym = IterCont2->getSymbolicBase()) {

    if (isa<SymbolConjured>(ContSym->getSymbol()))

      return;

  }

  if (IterCont1 != IterCont2) {

    auto *N = C.generateNonFatalErrorNode(State);

    if (!N)

      return;

    reportBug("Iterators of different containers used where the "

                        "same container is expected.", Iter1, Iter2, C, N);

  }

}

void MismatchedIteratorChecker::reportBug(const StringRef &Message,

                                          const SVal &Val1,

                                          const SVal &Val2,

                                          CheckerContext &C,

                                          ExplodedNode *ErrNode) const {

  auto R = std::make_unique<PathSensitiveBugReport>(*MismatchedBugType, Message,

                                                    ErrNode);

  R->markInteresting(Val1);

  R->markInteresting(Val2);

  C.emitReport(std::move(R));

}

void MismatchedIteratorChecker::reportBug(const StringRef &Message,

                                          const SVal &Val, const MemRegion *Reg,

                                          CheckerContext &C,

                                          ExplodedNode *ErrNode) const {

  auto R = std::make_unique<PathSensitiveBugReport>(*MismatchedBugType, Message,

                                                    ErrNode);

  R->markInteresting(Val);

  R->markInteresting(Reg);

  C.emitReport(std::move(R));

}

void ento::registerMismatchedIteratorChecker(CheckerManager &mgr) {

  mgr.registerChecker<MismatchedIteratorChecker>();

}

bool ento::shouldRegisterMismatchedIteratorChecker(const CheckerManager &mgr) {

  return true;

}