brintos / llvm-project-archived public Read only

1//===- UnsafeBufferUsage.cpp - Replace pointers with modern 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#include "clang/Analysis/Analyses/UnsafeBufferUsage.h"10#include "clang/AST/APValue.h"11#include "clang/AST/ASTContext.h"12#include "clang/AST/ASTTypeTraits.h"13#include "clang/AST/Attr.h"14#include "clang/AST/Decl.h"15#include "clang/AST/DeclCXX.h"16#include "clang/AST/DeclTemplate.h"17#include "clang/AST/DynamicRecursiveASTVisitor.h"18#include "clang/AST/Expr.h"19#include "clang/AST/FormatString.h"20#include "clang/AST/ParentMapContext.h"21#include "clang/AST/Stmt.h"22#include "clang/AST/StmtVisitor.h"23#include "clang/AST/Type.h"24#include "clang/ASTMatchers/LowLevelHelpers.h"25#include "clang/Analysis/Support/FixitUtil.h"26#include "clang/Basic/SourceLocation.h"27#include "clang/Lex/Lexer.h"28#include "clang/Lex/Preprocessor.h"29#include "llvm/ADT/APInt.h"30#include "llvm/ADT/APSInt.h"31#include "llvm/ADT/STLFunctionalExtras.h"32#include "llvm/ADT/SmallSet.h"33#include "llvm/ADT/SmallVector.h"34#include "llvm/ADT/StringRef.h"35#include <cstddef>36#include <optional>37#include <queue>38#include <set>39#include <sstream>40 41using namespace clang;42 43#ifndef NDEBUG44namespace {45class StmtDebugPrinter46    : public ConstStmtVisitor<StmtDebugPrinter, std::string> {47public:48  std::string VisitStmt(const Stmt *S) { return S->getStmtClassName(); }49 50  std::string VisitBinaryOperator(const BinaryOperator *BO) {51    return "BinaryOperator(" + BO->getOpcodeStr().str() + ")";52  }53 54  std::string VisitUnaryOperator(const UnaryOperator *UO) {55    return "UnaryOperator(" + UO->getOpcodeStr(UO->getOpcode()).str() + ")";56  }57 58  std::string VisitImplicitCastExpr(const ImplicitCastExpr *ICE) {59    return "ImplicitCastExpr(" + std::string(ICE->getCastKindName()) + ")";60  }61};62 63// Returns a string of ancestor `Stmt`s of the given `DRE` in such a form:64// "DRE ==> parent-of-DRE ==> grandparent-of-DRE ==> ...".65static std::string getDREAncestorString(const DeclRefExpr *DRE,66                                        ASTContext &Ctx) {67  std::stringstream SS;68  const Stmt *St = DRE;69  StmtDebugPrinter StmtPriner;70 71  do {72    SS << StmtPriner.Visit(St);73 74    DynTypedNodeList StParents = Ctx.getParents(*St);75 76    if (StParents.size() > 1)77      return "unavailable due to multiple parents";78    if (StParents.empty())79      break;80    St = StParents.begin()->get<Stmt>();81    if (St)82      SS << " ==> ";83  } while (St);84  return SS.str();85}86 87} // namespace88#endif /* NDEBUG */89 90namespace {91// Using a custom `FastMatcher` instead of ASTMatchers to achieve better92// performance. FastMatcher uses simple function `matches` to find if a node93// is a match, avoiding the dependency on the ASTMatchers framework which94// provide a nice abstraction, but incur big performance costs.95class FastMatcher {96public:97  virtual bool matches(const DynTypedNode &DynNode, ASTContext &Ctx,98                       const UnsafeBufferUsageHandler &Handler) = 0;99  virtual ~FastMatcher() = default;100};101 102class MatchResult {103 104public:105  template <typename T> const T *getNodeAs(StringRef ID) const {106    auto It = Nodes.find(ID);107    if (It == Nodes.end()) {108      return nullptr;109    }110    return It->second.get<T>();111  }112 113  void addNode(StringRef ID, const DynTypedNode &Node) { Nodes[ID] = Node; }114 115private:116  llvm::StringMap<DynTypedNode> Nodes;117};118} // namespace119 120#define SIZED_CONTAINER_OR_VIEW_LIST                                           \121  "span", "array", "vector", "basic_string_view", "basic_string",              \122      "initializer_list",123 124// A `RecursiveASTVisitor` that traverses all descendants of a given node "n"125// except for those belonging to a different callable of "n".126class MatchDescendantVisitor : public DynamicRecursiveASTVisitor {127public:128  // Creates an AST visitor that matches `Matcher` on all129  // descendants of a given node "n" except for the ones130  // belonging to a different callable of "n".131  MatchDescendantVisitor(ASTContext &Context, FastMatcher &Matcher,132                         bool FindAll, bool ignoreUnevaluatedContext,133                         const UnsafeBufferUsageHandler &NewHandler)134      : Matcher(&Matcher), FindAll(FindAll), Matches(false),135        ignoreUnevaluatedContext(ignoreUnevaluatedContext),136        ActiveASTContext(&Context), Handler(&NewHandler) {137    ShouldVisitTemplateInstantiations = true;138    ShouldVisitImplicitCode = false; // TODO: let's ignore implicit code for now139  }140 141  // Returns true if a match is found in a subtree of `DynNode`, which belongs142  // to the same callable of `DynNode`.143  bool findMatch(const DynTypedNode &DynNode) {144    Matches = false;145    if (const Stmt *StmtNode = DynNode.get<Stmt>()) {146      TraverseStmt(const_cast<Stmt *>(StmtNode));147      return Matches;148    }149    return false;150  }151 152  // The following are overriding methods from the base visitor class.153  // They are public only to allow CRTP to work. They are *not *part154  // of the public API of this class.155 156  // For the matchers so far used in safe buffers, we only need to match157  // `Stmt`s.  To override more as needed.158 159  bool TraverseDecl(Decl *Node) override {160    if (!Node)161      return true;162    if (!match(*Node))163      return false;164    // To skip callables:165    if (isa<FunctionDecl, BlockDecl, ObjCMethodDecl>(Node))166      return true;167    // Traverse descendants168    return DynamicRecursiveASTVisitor::TraverseDecl(Node);169  }170 171  bool TraverseGenericSelectionExpr(GenericSelectionExpr *Node) override {172    // These are unevaluated, except the result expression.173    if (ignoreUnevaluatedContext)174      return TraverseStmt(Node->getResultExpr());175    return DynamicRecursiveASTVisitor::TraverseGenericSelectionExpr(Node);176  }177 178  bool179  TraverseUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *Node) override {180    // Unevaluated context.181    if (ignoreUnevaluatedContext)182      return true;183    return DynamicRecursiveASTVisitor::TraverseUnaryExprOrTypeTraitExpr(Node);184  }185 186  bool TraverseTypeOfExprTypeLoc(TypeOfExprTypeLoc Node,187                                 bool TraverseQualifier) override {188    // Unevaluated context.189    if (ignoreUnevaluatedContext)190      return true;191    return DynamicRecursiveASTVisitor::TraverseTypeOfExprTypeLoc(192        Node, TraverseQualifier);193  }194 195  bool TraverseDecltypeTypeLoc(DecltypeTypeLoc Node,196                               bool TraverseQualifier) override {197    // Unevaluated context.198    if (ignoreUnevaluatedContext)199      return true;200    return DynamicRecursiveASTVisitor::TraverseDecltypeTypeLoc(201        Node, TraverseQualifier);202  }203 204  bool TraverseCXXNoexceptExpr(CXXNoexceptExpr *Node) override {205    // Unevaluated context.206    if (ignoreUnevaluatedContext)207      return true;208    return DynamicRecursiveASTVisitor::TraverseCXXNoexceptExpr(Node);209  }210 211  bool TraverseCXXTypeidExpr(CXXTypeidExpr *Node) override {212    // Unevaluated context.213    if (ignoreUnevaluatedContext)214      return true;215    return DynamicRecursiveASTVisitor::TraverseCXXTypeidExpr(Node);216  }217 218  bool TraverseCXXDefaultInitExpr(CXXDefaultInitExpr *Node) override {219    if (!TraverseStmt(Node->getExpr()))220      return false;221    return DynamicRecursiveASTVisitor::TraverseCXXDefaultInitExpr(Node);222  }223 224  bool TraverseStmt(Stmt *Node) override {225    if (!Node)226      return true;227    if (!match(*Node))228      return false;229    return DynamicRecursiveASTVisitor::TraverseStmt(Node);230  }231 232private:233  // Sets 'Matched' to true if 'Matcher' matches 'Node'234  //235  // Returns 'true' if traversal should continue after this function236  // returns, i.e. if no match is found or 'Bind' is 'BK_All'.237  template <typename T> bool match(const T &Node) {238    if (Matcher->matches(DynTypedNode::create(Node), *ActiveASTContext,239                         *Handler)) {240      Matches = true;241      if (!FindAll)242        return false; // Abort as soon as a match is found.243    }244    return true;245  }246 247  FastMatcher *const Matcher;248  // When true, finds all matches. When false, finds the first match and stops.249  const bool FindAll;250  bool Matches;251  bool ignoreUnevaluatedContext;252  ASTContext *ActiveASTContext;253  const UnsafeBufferUsageHandler *Handler;254};255 256// Because we're dealing with raw pointers, let's define what we mean by that.257static bool hasPointerType(const Expr &E) {258  return isa<PointerType>(E.getType().getCanonicalType());259}260 261static bool hasArrayType(const Expr &E) {262  return isa<ArrayType>(E.getType().getCanonicalType());263}264 265static void266forEachDescendantEvaluatedStmt(const Stmt *S, ASTContext &Ctx,267                               const UnsafeBufferUsageHandler &Handler,268                               FastMatcher &Matcher) {269  MatchDescendantVisitor Visitor(Ctx, Matcher, /*FindAll=*/true,270                                 /*ignoreUnevaluatedContext=*/true, Handler);271  Visitor.findMatch(DynTypedNode::create(*S));272}273 274static void forEachDescendantStmt(const Stmt *S, ASTContext &Ctx,275                                  const UnsafeBufferUsageHandler &Handler,276                                  FastMatcher &Matcher) {277  MatchDescendantVisitor Visitor(Ctx, Matcher, /*FindAll=*/true,278                                 /*ignoreUnevaluatedContext=*/false, Handler);279  Visitor.findMatch(DynTypedNode::create(*S));280}281 282// Matches a `Stmt` node iff the node is in a safe-buffer opt-out region283static bool notInSafeBufferOptOut(const Stmt &Node,284                                  const UnsafeBufferUsageHandler *Handler) {285  return !Handler->isSafeBufferOptOut(Node.getBeginLoc());286}287 288static bool289ignoreUnsafeBufferInContainer(const Stmt &Node,290                              const UnsafeBufferUsageHandler *Handler) {291  return Handler->ignoreUnsafeBufferInContainer(Node.getBeginLoc());292}293 294static bool ignoreUnsafeLibcCall(const ASTContext &Ctx, const Stmt &Node,295                                 const UnsafeBufferUsageHandler *Handler) {296  if (Ctx.getLangOpts().CPlusPlus)297    return Handler->ignoreUnsafeBufferInLibcCall(Node.getBeginLoc());298  return true; /* Only warn about libc calls for C++ */299}300 301// Finds any expression 'e' such that `OnResult`302// matches 'e' and 'e' is in an Unspecified Lvalue Context.303static void findStmtsInUnspecifiedLvalueContext(304    const Stmt *S, const llvm::function_ref<void(const Expr *)> OnResult) {305  if (const auto *CE = dyn_cast<ImplicitCastExpr>(S);306      CE && CE->getCastKind() == CastKind::CK_LValueToRValue)307    OnResult(CE->getSubExpr());308  if (const auto *BO = dyn_cast<BinaryOperator>(S);309      BO && BO->getOpcode() == BO_Assign)310    OnResult(BO->getLHS());311}312 313// Finds any expression `e` such that `InnerMatcher` matches `e` and314// `e` is in an Unspecified Pointer Context (UPC).315static void findStmtsInUnspecifiedPointerContext(316    const Stmt *S, llvm::function_ref<void(const Stmt *)> InnerMatcher) {317  // A UPC can be318  // 1. an argument of a function call (except the callee has [[unsafe_...]]319  //    attribute), or320  // 2. the operand of a pointer-to-(integer or bool) cast operation; or321  // 3. the operand of a comparator operation; or322  // 4. the operand of a pointer subtraction operation323  //    (i.e., computing the distance between two pointers); or ...324 325  if (auto *CE = dyn_cast<CallExpr>(S)) {326    if (const auto *FnDecl = CE->getDirectCallee();327        FnDecl && FnDecl->hasAttr<UnsafeBufferUsageAttr>())328      return;329    ast_matchers::matchEachArgumentWithParamType(330        *CE, [&InnerMatcher](QualType Type, const Expr *Arg) {331          if (Type->isAnyPointerType())332            InnerMatcher(Arg);333        });334  }335 336  if (auto *CE = dyn_cast<CastExpr>(S)) {337    if (CE->getCastKind() != CastKind::CK_PointerToIntegral &&338        CE->getCastKind() != CastKind::CK_PointerToBoolean)339      return;340    if (!hasPointerType(*CE->getSubExpr()))341      return;342    InnerMatcher(CE->getSubExpr());343  }344 345  // Pointer comparison operator.346  if (const auto *BO = dyn_cast<BinaryOperator>(S);347      BO && (BO->getOpcode() == BO_EQ || BO->getOpcode() == BO_NE ||348             BO->getOpcode() == BO_LT || BO->getOpcode() == BO_LE ||349             BO->getOpcode() == BO_GT || BO->getOpcode() == BO_GE)) {350    auto *LHS = BO->getLHS();351    if (hasPointerType(*LHS))352      InnerMatcher(LHS);353 354    auto *RHS = BO->getRHS();355    if (hasPointerType(*RHS))356      InnerMatcher(RHS);357  }358 359  // Pointer subtractions.360  if (const auto *BO = dyn_cast<BinaryOperator>(S);361      BO && BO->getOpcode() == BO_Sub && hasPointerType(*BO->getLHS()) &&362      hasPointerType(*BO->getRHS())) {363    // Note that here we need both LHS and RHS to be364    // pointer. Then the inner matcher can match any of365    // them:366    InnerMatcher(BO->getLHS());367    InnerMatcher(BO->getRHS());368  }369  // FIXME: any more cases? (UPC excludes the RHS of an assignment.  For now370  // we don't have to check that.)371}372 373// Finds statements in unspecified untyped context i.e. any expression 'e' such374// that `InnerMatcher` matches 'e' and 'e' is in an unspecified untyped context375// (i.e the expression 'e' isn't evaluated to an RValue). For example, consider376// the following code:377//    int *p = new int[4];378//    int *q = new int[4];379//    if ((p = q)) {}380//    p = q;381// The expression `p = q` in the conditional of the `if` statement382// `if ((p = q))` is evaluated as an RValue, whereas the expression `p = q;`383// in the assignment statement is in an untyped context.384static void findStmtsInUnspecifiedUntypedContext(385    const Stmt *S, llvm::function_ref<void(const Stmt *)> InnerMatcher) {386  // An unspecified context can be387  // 1. A compound statement,388  // 2. The body of an if statement389  // 3. Body of a loop390  if (auto *CS = dyn_cast<CompoundStmt>(S)) {391    for (auto *Child : CS->body())392      InnerMatcher(Child);393  }394  if (auto *IfS = dyn_cast<IfStmt>(S)) {395    if (IfS->getThen())396      InnerMatcher(IfS->getThen());397    if (IfS->getElse())398      InnerMatcher(IfS->getElse());399  }400  // FIXME: Handle loop bodies.401}402 403// Returns true iff integer E1 is equivalent to integer E2.404//405// For now we only support such expressions:406//    expr := DRE | const-value | expr BO expr407//    BO   := '*' | '+'408//409// FIXME: We can reuse the expression comparator of the interop analysis after410// it has been upstreamed.411static bool areEqualIntegers(const Expr *E1, const Expr *E2, ASTContext &Ctx);412static bool areEqualIntegralBinaryOperators(const BinaryOperator *E1,413                                            const Expr *E2_LHS,414                                            BinaryOperatorKind BOP,415                                            const Expr *E2_RHS,416                                            ASTContext &Ctx) {417  if (E1->getOpcode() == BOP) {418    switch (BOP) {419      // Commutative operators:420    case BO_Mul:421    case BO_Add:422      return (areEqualIntegers(E1->getLHS(), E2_LHS, Ctx) &&423              areEqualIntegers(E1->getRHS(), E2_RHS, Ctx)) ||424             (areEqualIntegers(E1->getLHS(), E2_RHS, Ctx) &&425              areEqualIntegers(E1->getRHS(), E2_LHS, Ctx));426    default:427      return false;428    }429  }430  return false;431}432 433static bool areEqualIntegers(const Expr *E1, const Expr *E2, ASTContext &Ctx) {434  E1 = E1->IgnoreParenImpCasts();435  E2 = E2->IgnoreParenImpCasts();436  if (!E1->getType()->isIntegerType() || E1->getType() != E2->getType())437    return false;438 439  Expr::EvalResult ER1, ER2;440 441  // If both are constants:442  if (E1->EvaluateAsInt(ER1, Ctx) && E2->EvaluateAsInt(ER2, Ctx))443    return ER1.Val.getInt() == ER2.Val.getInt();444 445  // Otherwise, they should have identical stmt kind:446  if (E1->getStmtClass() != E2->getStmtClass())447    return false;448  switch (E1->getStmtClass()) {449  case Stmt::DeclRefExprClass:450    return cast<DeclRefExpr>(E1)->getDecl() == cast<DeclRefExpr>(E2)->getDecl();451  case Stmt::BinaryOperatorClass: {452    auto BO2 = cast<BinaryOperator>(E2);453    return areEqualIntegralBinaryOperators(cast<BinaryOperator>(E1),454                                           BO2->getLHS(), BO2->getOpcode(),455                                           BO2->getRHS(), Ctx);456  }457  default:458    return false;459  }460}461 462// Providing that `Ptr` is a pointer and `Size` is an unsigned-integral463// expression, returns true iff they follow one of the following safe464// patterns:465//  1. Ptr is `DRE.data()` and Size is `DRE.size()`, where DRE is a hardened466//     container or view;467//468//  2. Ptr is `a` and Size is `n`, where `a` is of an array-of-T with constant469//     size `n`;470//471//  3. Ptr is `&var` and Size is `1`; or472//     Ptr is `std::addressof(...)` and Size is `1`;473//474//  4. Size is `0`;475static bool isPtrBufferSafe(const Expr *Ptr, const Expr *Size,476                            ASTContext &Ctx) {477  // Pattern 1:478  if (auto *MCEPtr = dyn_cast<CXXMemberCallExpr>(Ptr->IgnoreParenImpCasts()))479    if (auto *MCESize =480            dyn_cast<CXXMemberCallExpr>(Size->IgnoreParenImpCasts())) {481      auto *DREOfPtr = dyn_cast<DeclRefExpr>(482          MCEPtr->getImplicitObjectArgument()->IgnoreParenImpCasts());483      auto *DREOfSize = dyn_cast<DeclRefExpr>(484          MCESize->getImplicitObjectArgument()->IgnoreParenImpCasts());485 486      if (!DREOfPtr || !DREOfSize)487        return false; // not in safe pattern488      // We need to make sure 'a' is identical to 'b' for 'a.data()' and489      // 'b.size()' otherwise we do not know they match:490      if (DREOfPtr->getDecl() != DREOfSize->getDecl())491        return false;492      if (MCEPtr->getMethodDecl()->getName() != "data")493        return false;494      // `MCEPtr->getRecordDecl()` must be non-null as `DREOfPtr` is non-null:495      if (!MCEPtr->getRecordDecl()->isInStdNamespace())496        return false;497 498      auto *ObjII = MCEPtr->getRecordDecl()->getIdentifier();499 500      if (!ObjII)501        return false;502 503      bool AcceptSizeBytes = Ptr->getType()->getPointeeType()->isCharType();504 505      if (!((AcceptSizeBytes &&506             MCESize->getMethodDecl()->getName() == "size_bytes") ||507            // Note here the pointer must be a pointer-to-char type unless there508            // is explicit casting.  If there is explicit casting, this branch509            // is unreachable. Thus, at this branch "size" and "size_bytes" are510            // equivalent as the pointer is a char pointer:511            MCESize->getMethodDecl()->getName() == "size"))512        return false;513 514      return llvm::is_contained({SIZED_CONTAINER_OR_VIEW_LIST},515                                ObjII->getName());516    }517 518  Expr::EvalResult ER;519 520  // Pattern 2-4:521  if (Size->EvaluateAsInt(ER, Ctx)) {522    // Pattern 2:523    if (auto *DRE = dyn_cast<DeclRefExpr>(Ptr->IgnoreParenImpCasts())) {524      if (auto *CAT = Ctx.getAsConstantArrayType(DRE->getType())) {525        llvm::APSInt SizeInt = ER.Val.getInt();526 527        return llvm::APSInt::compareValues(528                   SizeInt, llvm::APSInt(CAT->getSize(), true)) == 0;529      }530      return false;531    }532 533    // Pattern 3:534    if (ER.Val.getInt().isOne()) {535      if (auto *UO = dyn_cast<UnaryOperator>(Ptr->IgnoreParenImpCasts()))536        return UO && UO->getOpcode() == UnaryOperator::Opcode::UO_AddrOf;537      if (auto *CE = dyn_cast<CallExpr>(Ptr->IgnoreParenImpCasts())) {538        auto *FnDecl = CE->getDirectCallee();539 540        return FnDecl && FnDecl->getNameAsString() == "addressof" &&541               FnDecl->isInStdNamespace();542      }543      return false;544    }545    // Pattern 4:546    if (ER.Val.getInt().isZero())547      return true;548  }549  return false;550}551 552// Given a two-param std::span construct call, matches iff the call has the553// following forms:554//   1. `std::span<T>{new T[n], n}`, where `n` is a literal or a DRE555//   2. `std::span<T>{new T, 1}`556//   3. `std::span<T>{ (char *)f(args), args[N] * arg*[M]}`, where557//       `f` is a function with attribute `alloc_size(N, M)`;558//       `args` represents the list of arguments;559//       `N, M` are parameter indexes to the allocating element number and size.560//        Sometimes, there is only one parameter index representing the total561//        size.562//   4. `std::span<T>{x.begin(), x.end()}` where `x` is an object in the563//      SIZED_CONTAINER_OR_VIEW_LIST.564//   5. `isPtrBufferSafe` returns true for the two arguments of the span565//      constructor566static bool isSafeSpanTwoParamConstruct(const CXXConstructExpr &Node,567                                        ASTContext &Ctx) {568  assert(Node.getNumArgs() == 2 &&569         "expecting a two-parameter std::span constructor");570  const Expr *Arg0 = Node.getArg(0)->IgnoreParenImpCasts();571  const Expr *Arg1 = Node.getArg(1)->IgnoreParenImpCasts();572  auto HaveEqualConstantValues = [&Ctx](const Expr *E0, const Expr *E1) {573    if (auto E0CV = E0->getIntegerConstantExpr(Ctx))574      if (auto E1CV = E1->getIntegerConstantExpr(Ctx)) {575        return llvm::APSInt::compareValues(*E0CV, *E1CV) == 0;576      }577    return false;578  };579  auto AreSameDRE = [](const Expr *E0, const Expr *E1) {580    if (auto *DRE0 = dyn_cast<DeclRefExpr>(E0))581      if (auto *DRE1 = dyn_cast<DeclRefExpr>(E1)) {582        return DRE0->getDecl() == DRE1->getDecl();583      }584    return false;585  };586  std::optional<llvm::APSInt> Arg1CV = Arg1->getIntegerConstantExpr(Ctx);587 588  if (Arg1CV && Arg1CV->isZero())589    // Check form 5:590    return true;591 592  // Check forms 1-2:593  switch (Arg0->getStmtClass()) {594  case Stmt::CXXNewExprClass:595    if (auto Size = cast<CXXNewExpr>(Arg0)->getArraySize()) {596      // Check form 1:597      return AreSameDRE((*Size)->IgnoreImplicit(), Arg1) ||598             HaveEqualConstantValues(*Size, Arg1);599    }600    // TODO: what's placeholder type? avoid it for now.601    if (!cast<CXXNewExpr>(Arg0)->hasPlaceholderType()) {602      // Check form 2:603      return Arg1CV && Arg1CV->isOne();604    }605    break;606  default:607    break;608  }609 610  // Check form 3:611  if (auto CCast = dyn_cast<CStyleCastExpr>(Arg0)) {612    if (!CCast->getType()->isPointerType())613      return false;614 615    QualType PteTy = CCast->getType()->getPointeeType();616 617    if (!(PteTy->isConstantSizeType() && Ctx.getTypeSizeInChars(PteTy).isOne()))618      return false;619 620    if (const auto *Call = dyn_cast<CallExpr>(CCast->getSubExpr())) {621      if (const FunctionDecl *FD = Call->getDirectCallee())622        if (auto *AllocAttr = FD->getAttr<AllocSizeAttr>()) {623          const Expr *EleSizeExpr =624              Call->getArg(AllocAttr->getElemSizeParam().getASTIndex());625          // NumElemIdx is invalid if AllocSizeAttr has 1 argument:626          ParamIdx NumElemIdx = AllocAttr->getNumElemsParam();627 628          if (!NumElemIdx.isValid())629            return areEqualIntegers(Arg1, EleSizeExpr, Ctx);630 631          const Expr *NumElesExpr = Call->getArg(NumElemIdx.getASTIndex());632 633          if (auto BO = dyn_cast<BinaryOperator>(Arg1))634            return areEqualIntegralBinaryOperators(BO, NumElesExpr, BO_Mul,635                                                   EleSizeExpr, Ctx);636        }637    }638  }639  // Check form 4:640  auto IsMethodCallToSizedObject = [](const Stmt *Node, StringRef MethodName) {641    if (const auto *MC = dyn_cast<CXXMemberCallExpr>(Node)) {642      const auto *MD = MC->getMethodDecl();643      const auto *RD = MC->getRecordDecl();644 645      if (RD && MD)646        if (auto *II = RD->getDeclName().getAsIdentifierInfo();647            II && RD->isInStdNamespace())648          return llvm::is_contained({SIZED_CONTAINER_OR_VIEW_LIST},649                                    II->getName()) &&650                 MD->getName() == MethodName;651    }652    return false;653  };654 655  if (IsMethodCallToSizedObject(Arg0, "begin") &&656      IsMethodCallToSizedObject(Arg1, "end"))657    return AreSameDRE(658        // We know Arg0 and Arg1 are `CXXMemberCallExpr`s:659        cast<CXXMemberCallExpr>(Arg0)660            ->getImplicitObjectArgument()661            ->IgnoreParenImpCasts(),662        cast<CXXMemberCallExpr>(Arg1)663            ->getImplicitObjectArgument()664            ->IgnoreParenImpCasts());665 666  // Check 5:667  return isPtrBufferSafe(Arg0, Arg1, Ctx);668}669 670static bool isSafeArraySubscript(const ArraySubscriptExpr &Node,671                                 const ASTContext &Ctx) {672  // FIXME: Proper solution:673  //  - refactor Sema::CheckArrayAccess674  //    - split safe/OOB/unknown decision logic from diagnostics emitting code675  //    -  e. g. "Try harder to find a NamedDecl to point at in the note."676  //    already duplicated677  //  - call both from Sema and from here678 679  uint64_t limit;680  if (const auto *CATy =681          dyn_cast<ConstantArrayType>(Node.getBase()682                                          ->IgnoreParenImpCasts()683                                          ->getType()684                                          ->getUnqualifiedDesugaredType())) {685    limit = CATy->getLimitedSize();686  } else if (const auto *SLiteral = dyn_cast<clang::StringLiteral>(687                 Node.getBase()->IgnoreParenImpCasts())) {688    limit = SLiteral->getLength() + 1;689  } else {690    return false;691  }692 693  Expr::EvalResult EVResult;694  const Expr *IndexExpr = Node.getIdx();695  if (!IndexExpr->isValueDependent() &&696      IndexExpr->EvaluateAsInt(EVResult, Ctx)) {697    llvm::APSInt ArrIdx = EVResult.Val.getInt();698    // FIXME: ArrIdx.isNegative() we could immediately emit an error as that's a699    // bug700    if (ArrIdx.isNonNegative() && ArrIdx.getLimitedValue() < limit)701      return true;702  } else if (const auto *BE = dyn_cast<BinaryOperator>(IndexExpr)) {703    // For an integer expression `e` and an integer constant `n`, `e & n` and704    // `n & e` are bounded by `n`:705    if (BE->getOpcode() != BO_And && BE->getOpcode() != BO_Rem)706      return false;707 708    const Expr *LHS = BE->getLHS();709    const Expr *RHS = BE->getRHS();710 711    if (BE->getOpcode() == BO_Rem) {712      // If n is a negative number, then n % const can be greater than const713      if (!LHS->getType()->isUnsignedIntegerType()) {714        return false;715      }716 717      if (!RHS->isValueDependent() && RHS->EvaluateAsInt(EVResult, Ctx)) {718        llvm::APSInt result = EVResult.Val.getInt();719        if (result.isNonNegative() && result.getLimitedValue() <= limit)720          return true;721      }722 723      return false;724    }725 726    if ((!LHS->isValueDependent() &&727         LHS->EvaluateAsInt(EVResult, Ctx)) || // case: `n & e`728        (!RHS->isValueDependent() &&729         RHS->EvaluateAsInt(EVResult, Ctx))) { // `e & n`730      llvm::APSInt result = EVResult.Val.getInt();731      if (result.isNonNegative() && result.getLimitedValue() < limit)732        return true;733    }734    return false;735  }736  return false;737}738 739namespace libc_func_matchers {740// Under `libc_func_matchers`, define a set of matchers that match unsafe741// functions in libc and unsafe calls to them.742 743//  A tiny parser to strip off common prefix and suffix of libc function names744//  in real code.745//746//  Given a function name, `matchName` returns `CoreName` according to the747//  following grammar:748//749//  LibcName     := CoreName | CoreName + "_s"750//  MatchingName := "__builtin_" + LibcName              |751//                  "__builtin___" + LibcName + "_chk"   |752//                  "__asan_" + LibcName753//754struct LibcFunNamePrefixSuffixParser {755  StringRef matchName(StringRef FunName, bool isBuiltin) {756    // Try to match __builtin_:757    if (isBuiltin && FunName.starts_with("__builtin_"))758      // Then either it is __builtin_LibcName or __builtin___LibcName_chk or759      // no match:760      return matchLibcNameOrBuiltinChk(761          FunName.drop_front(10 /* truncate "__builtin_" */));762    // Try to match __asan_:763    if (FunName.starts_with("__asan_"))764      return matchLibcName(FunName.drop_front(7 /* truncate of "__asan_" */));765    return matchLibcName(FunName);766  }767 768  // Parameter `Name` is the substring after stripping off the prefix769  // "__builtin_".770  StringRef matchLibcNameOrBuiltinChk(StringRef Name) {771    if (Name.starts_with("__") && Name.ends_with("_chk"))772      return matchLibcName(773          Name.drop_front(2).drop_back(4) /* truncate "__" and "_chk" */);774    return matchLibcName(Name);775  }776 777  StringRef matchLibcName(StringRef Name) {778    if (Name.ends_with("_s"))779      return Name.drop_back(2 /* truncate "_s" */);780    return Name;781  }782};783 784// Constant fold a conditional expression 'cond ? A : B' to785// - 'A', if 'cond' has constant true value;786// - 'B', if 'cond' has constant false value.787static const Expr *tryConstantFoldConditionalExpr(const Expr *E,788                                                  const ASTContext &Ctx) {789  // FIXME: more places can use this function790  if (const auto *CE = dyn_cast<ConditionalOperator>(E)) {791    bool CondEval;792 793    if (CE->getCond()->EvaluateAsBooleanCondition(CondEval, Ctx))794      return CondEval ? CE->getLHS() : CE->getRHS();795  }796  return E;797}798 799// A pointer type expression is known to be null-terminated, if it has the800// form: E.c_str(), for any expression E of `std::string` type.801static bool isNullTermPointer(const Expr *Ptr, ASTContext &Ctx) {802  Ptr = tryConstantFoldConditionalExpr(Ptr, Ctx);803  if (isa<clang::StringLiteral>(Ptr->IgnoreParenImpCasts()))804    return true;805  if (isa<PredefinedExpr>(Ptr->IgnoreParenImpCasts()))806    return true;807  if (auto *MCE = dyn_cast<CXXMemberCallExpr>(Ptr->IgnoreParenImpCasts())) {808    const CXXMethodDecl *MD = MCE->getMethodDecl();809    const CXXRecordDecl *RD = MCE->getRecordDecl()->getCanonicalDecl();810 811    if (MD && RD && RD->isInStdNamespace() && MD->getIdentifier())812      if (MD->getName() == "c_str" && RD->getName() == "basic_string")813        return true;814  }815  return false;816}817 818// Return true iff at least one of following cases holds:819//  1. Format string is a literal and there is an unsafe pointer argument820//     corresponding to an `s` specifier;821//  2. Format string is not a literal and there is least an unsafe pointer822//     argument (including the formatter argument).823//824// `UnsafeArg` is the output argument that will be set only if this function825// returns true.826static bool hasUnsafeFormatOrSArg(const CallExpr *Call, const Expr *&UnsafeArg,827                                  const unsigned FmtArgIdx, ASTContext &Ctx,828                                  bool isKprintf = false) {829  class StringFormatStringHandler830      : public analyze_format_string::FormatStringHandler {831    const CallExpr *Call;832    unsigned FmtArgIdx;833    const Expr *&UnsafeArg;834    ASTContext &Ctx;835 836    // Returns an `Expr` representing the precision if specified, null837    // otherwise.838    // The parameter `Call` is a printf call and the parameter `Precision` is839    // the precision of a format specifier of the `Call`.840    //841    // For example, for the `printf("%d, %.10s", 10, p)` call842    // `Precision` can be the precision of either "%d" or "%.10s". The former843    // one will have `NotSpecified` kind.844    const Expr *845    getPrecisionAsExpr(const analyze_printf::OptionalAmount &Precision,846                       const CallExpr *Call) {847      unsigned PArgIdx = -1;848 849      if (Precision.hasDataArgument())850        PArgIdx = Precision.getPositionalArgIndex() + FmtArgIdx;851      if (0 < PArgIdx && PArgIdx < Call->getNumArgs()) {852        const Expr *PArg = Call->getArg(PArgIdx);853 854        // Strip the cast if `PArg` is a cast-to-int expression:855        if (auto *CE = dyn_cast<CastExpr>(PArg);856            CE && CE->getType()->isSignedIntegerType())857          PArg = CE->getSubExpr();858        return PArg;859      }860      if (Precision.getHowSpecified() ==861          analyze_printf::OptionalAmount::HowSpecified::Constant) {862        auto SizeTy = Ctx.getSizeType();863        llvm::APSInt PArgVal = llvm::APSInt(864            llvm::APInt(Ctx.getTypeSize(SizeTy), Precision.getConstantAmount()),865            true);866 867        return IntegerLiteral::Create(Ctx, PArgVal, Ctx.getSizeType(), {});868      }869      return nullptr;870    }871 872  public:873    StringFormatStringHandler(const CallExpr *Call, unsigned FmtArgIdx,874                              const Expr *&UnsafeArg, ASTContext &Ctx)875        : Call(Call), FmtArgIdx(FmtArgIdx), UnsafeArg(UnsafeArg), Ctx(Ctx) {}876 877    bool HandlePrintfSpecifier(const analyze_printf::PrintfSpecifier &FS,878                               const char *startSpecifier,879                               unsigned specifierLen,880                               const TargetInfo &Target) override {881      if (FS.getConversionSpecifier().getKind() !=882          analyze_printf::PrintfConversionSpecifier::sArg)883        return true; // continue parsing884 885      unsigned ArgIdx = FS.getPositionalArgIndex() + FmtArgIdx;886 887      if (!(0 < ArgIdx && ArgIdx < Call->getNumArgs()))888        // If the `ArgIdx` is invalid, give up.889        return true; // continue parsing890 891      const Expr *Arg = Call->getArg(ArgIdx);892 893      if (isNullTermPointer(Arg, Ctx))894        // If Arg is a null-terminated pointer, it is safe anyway.895        return true; // continue parsing896 897      // Otherwise, check if the specifier has a precision and if the character898      // pointer is safely bound by the precision:899      auto LengthModifier = FS.getLengthModifier();900      QualType ArgType = Arg->getType();901      bool IsArgTypeValid = // Is ArgType a character pointer type?902          ArgType->isPointerType() &&903          (LengthModifier.getKind() == LengthModifier.AsWideChar904               ? ArgType->getPointeeType()->isWideCharType()905               : ArgType->getPointeeType()->isCharType());906 907      if (auto *Precision = getPrecisionAsExpr(FS.getPrecision(), Call);908          Precision && IsArgTypeValid)909        if (isPtrBufferSafe(Arg, Precision, Ctx))910          return true;911      // Handle unsafe case:912      UnsafeArg = Call->getArg(ArgIdx); // output913      return false; // returning false stops parsing immediately914    }915  };916 917  const Expr *Fmt = Call->getArg(FmtArgIdx);918 919  if (auto *SL = dyn_cast<clang::StringLiteral>(Fmt->IgnoreParenImpCasts())) {920    if (SL->getCharByteWidth() == 1) {921      StringRef FmtStr = SL->getString();922      StringFormatStringHandler Handler(Call, FmtArgIdx, UnsafeArg, Ctx);923 924      return analyze_format_string::ParsePrintfString(925          Handler, FmtStr.begin(), FmtStr.end(), Ctx.getLangOpts(),926          Ctx.getTargetInfo(), isKprintf);927    }928 929    if (auto FmtStr = SL->tryEvaluateString(Ctx)) {930      StringFormatStringHandler Handler(Call, FmtArgIdx, UnsafeArg, Ctx);931      return analyze_format_string::ParsePrintfString(932          Handler, FmtStr->data(), FmtStr->data() + FmtStr->size(),933          Ctx.getLangOpts(), Ctx.getTargetInfo(), isKprintf);934    }935  }936  // If format is not a string literal, we cannot analyze the format string.937  // In this case, this call is considered unsafe if at least one argument938  // (including the format argument) is unsafe pointer.939  return llvm::any_of(940      llvm::make_range(Call->arg_begin() + FmtArgIdx, Call->arg_end()),941      [&UnsafeArg, &Ctx](const Expr *Arg) -> bool {942        if (Arg->getType()->isPointerType() && !isNullTermPointer(Arg, Ctx)) {943          UnsafeArg = Arg;944          return true;945        }946        return false;947      });948}949 950// Matches a FunctionDecl node such that951//  1. It's name, after stripping off predefined prefix and suffix, is952//     `CoreName`; and953//  2. `CoreName` or `CoreName[str/wcs]` is one of the `PredefinedNames`, which954//     is a set of libc function names.955//956//  Note: For predefined prefix and suffix, see `LibcFunNamePrefixSuffixParser`.957//  The notation `CoreName[str/wcs]` means a new name obtained from replace958//  string "wcs" with "str" in `CoreName`.959static bool isPredefinedUnsafeLibcFunc(const FunctionDecl &Node) {960  static std::unique_ptr<std::set<StringRef>> PredefinedNames = nullptr;961  if (!PredefinedNames)962    PredefinedNames =963        std::make_unique<std::set<StringRef>, std::set<StringRef>>({964            // numeric conversion:965            "atof",966            "atoi",967            "atol",968            "atoll",969            "strtol",970            "strtoll",971            "strtoul",972            "strtoull",973            "strtof",974            "strtod",975            "strtold",976            "strtoimax",977            "strtoumax",978            // "strfromf",  "strfromd", "strfroml", // C23?979            // string manipulation:980            "strcpy",981            "strncpy",982            "strlcpy",983            "strcat",984            "strncat",985            "strlcat",986            "strxfrm",987            "strdup",988            "strndup",989            // string examination:990            "strlen",991            "strnlen",992            "strcmp",993            "strncmp",994            "stricmp",995            "strcasecmp",996            "strcoll",997            "strchr",998            "strrchr",999            "strspn",1000            "strcspn",1001            "strpbrk",1002            "strstr",1003            "strtok",1004            // "mem-" functions1005            "memchr",1006            "wmemchr",1007            "memcmp",1008            "wmemcmp",1009            "memcpy",1010            "memccpy",1011            "mempcpy",1012            "wmemcpy",1013            "memmove",1014            "wmemmove",1015            "memset",1016            "wmemset",1017            // IO:1018            "fread",1019            "fwrite",1020            "fgets",1021            "fgetws",1022            "gets",1023            "fputs",1024            "fputws",1025            "puts",1026            // others1027            "strerror_s",1028            "strerror_r",1029            "bcopy",1030            "bzero",1031            "bsearch",1032            "qsort",1033        });1034 1035  auto *II = Node.getIdentifier();1036 1037  if (!II)1038    return false;1039 1040  StringRef Name = LibcFunNamePrefixSuffixParser().matchName(1041      II->getName(), Node.getBuiltinID());1042 1043  // Match predefined names:1044  if (PredefinedNames->find(Name) != PredefinedNames->end())1045    return true;1046 1047  std::string NameWCS = Name.str();1048  size_t WcsPos = NameWCS.find("wcs");1049 1050  while (WcsPos != std::string::npos) {1051    NameWCS[WcsPos++] = 's';1052    NameWCS[WcsPos++] = 't';1053    NameWCS[WcsPos++] = 'r';1054    WcsPos = NameWCS.find("wcs", WcsPos);1055  }1056  if (PredefinedNames->find(NameWCS) != PredefinedNames->end())1057    return true;1058  // All `scanf` functions are unsafe (including `sscanf`, `vsscanf`, etc.. They1059  // all should end with "scanf"):1060  return Name.ends_with("scanf");1061}1062 1063// Match a call to one of the `v*printf` functions taking `va_list`.  We cannot1064// check safety for these functions so they should be changed to their1065// non-va_list versions.1066static bool isUnsafeVaListPrintfFunc(const FunctionDecl &Node) {1067  auto *II = Node.getIdentifier();1068 1069  if (!II)1070    return false;1071 1072  StringRef Name = LibcFunNamePrefixSuffixParser().matchName(1073      II->getName(), Node.getBuiltinID());1074 1075  if (!Name.ends_with("printf"))1076    return false; // neither printf nor scanf1077  return Name.starts_with("v");1078}1079 1080// Matches a call to one of the `sprintf` functions as they are always unsafe1081// and should be changed to `snprintf`.1082static bool isUnsafeSprintfFunc(const FunctionDecl &Node) {1083  auto *II = Node.getIdentifier();1084 1085  if (!II)1086    return false;1087 1088  StringRef Name = LibcFunNamePrefixSuffixParser().matchName(1089      II->getName(), Node.getBuiltinID());1090 1091  if (!Name.ends_with("printf") ||1092      // Let `isUnsafeVaListPrintfFunc` check for cases with va-list:1093      Name.starts_with("v"))1094    return false;1095 1096  StringRef Prefix = Name.drop_back(6);1097 1098  if (Prefix.ends_with("w"))1099    Prefix = Prefix.drop_back(1);1100  return Prefix == "s";1101}1102 1103// Match function declarations of `printf`, `fprintf`, `snprintf` and their wide1104// character versions.  Calls to these functions can be safe if their arguments1105// are carefully made safe.1106static bool isNormalPrintfFunc(const FunctionDecl &Node) {1107  auto *II = Node.getIdentifier();1108 1109  if (!II)1110    return false;1111 1112  StringRef Name = LibcFunNamePrefixSuffixParser().matchName(1113      II->getName(), Node.getBuiltinID());1114 1115  if (!Name.ends_with("printf") || Name.starts_with("v"))1116    return false;1117 1118  StringRef Prefix = Name.drop_back(6);1119 1120  if (Prefix.ends_with("w"))1121    Prefix = Prefix.drop_back(1);1122 1123  return Prefix.empty() || Prefix == "k" || Prefix == "f" || Prefix == "sn";1124}1125 1126// This matcher requires that it is known that the callee `isNormalPrintf`.1127// Then if the format string is a string literal, this matcher matches when at1128// least one string argument is unsafe. If the format is not a string literal,1129// this matcher matches when at least one pointer type argument is unsafe.1130static bool hasUnsafePrintfStringArg(const CallExpr &Node, ASTContext &Ctx,1131                                     MatchResult &Result, llvm::StringRef Tag) {1132  // Determine what printf it is by examining formal parameters:1133  const FunctionDecl *FD = Node.getDirectCallee();1134 1135  assert(FD && "It should have been checked that FD is non-null.");1136 1137  unsigned NumParms = FD->getNumParams();1138 1139  if (NumParms < 1)1140    return false; // possibly some user-defined printf function1141 1142  QualType FirstParmTy = FD->getParamDecl(0)->getType();1143 1144  if (!FirstParmTy->isPointerType())1145    return false; // possibly some user-defined printf function1146 1147  QualType FirstPteTy = FirstParmTy->castAs<PointerType>()->getPointeeType();1148 1149  if (!Ctx.getFILEType()1150           .isNull() && //`FILE *` must be in the context if it is fprintf1151      FirstPteTy.getCanonicalType() == Ctx.getFILEType().getCanonicalType()) {1152    // It is a fprintf:1153    const Expr *UnsafeArg;1154 1155    if (hasUnsafeFormatOrSArg(&Node, UnsafeArg, 1, Ctx, false)) {1156      Result.addNode(Tag, DynTypedNode::create(*UnsafeArg));1157      return true;1158    }1159    return false;1160  }1161 1162  if (FirstPteTy.isConstQualified()) {1163    // If the first parameter is a `const char *`, it is a printf/kprintf:1164    bool isKprintf = false;1165    const Expr *UnsafeArg;1166 1167    if (auto *II = FD->getIdentifier())1168      isKprintf = II->getName() == "kprintf";1169    if (hasUnsafeFormatOrSArg(&Node, UnsafeArg, 0, Ctx, isKprintf)) {1170      Result.addNode(Tag, DynTypedNode::create(*UnsafeArg));1171      return true;1172    }1173    return false;1174  }1175 1176  if (NumParms > 2) {1177    QualType SecondParmTy = FD->getParamDecl(1)->getType();1178 1179    if (!FirstPteTy.isConstQualified() && SecondParmTy->isIntegerType()) {1180      // If the first parameter type is non-const qualified `char *` and the1181      // second is an integer, it is a snprintf:1182      const Expr *UnsafeArg;1183 1184      if (hasUnsafeFormatOrSArg(&Node, UnsafeArg, 2, Ctx, false)) {1185        Result.addNode(Tag, DynTypedNode::create(*UnsafeArg));1186        return true;1187      }1188      return false;1189    }1190  }1191  // We don't really recognize this "normal" printf, the only thing we1192  // can do is to require all pointers to be null-terminated:1193  for (const auto *Arg : Node.arguments())1194    if (Arg->getType()->isPointerType() && !isNullTermPointer(Arg, Ctx)) {1195      Result.addNode(Tag, DynTypedNode::create(*Arg));1196      return true;1197    }1198  return false;1199}1200 1201// This function requires that it is known that the callee `isNormalPrintf`.1202// It returns true iff the first two arguments of the call is a pointer1203// `Ptr` and an unsigned integer `Size` and they are NOT safe, i.e.,1204// `!isPtrBufferSafe(Ptr, Size)`.1205static bool hasUnsafeSnprintfBuffer(const CallExpr &Node, ASTContext &Ctx) {1206  const FunctionDecl *FD = Node.getDirectCallee();1207 1208  assert(FD && "It should have been checked that FD is non-null.");1209 1210  if (FD->getNumParams() < 3)1211    return false; // Not an snprint1212 1213  QualType FirstParmTy = FD->getParamDecl(0)->getType();1214 1215  if (!FirstParmTy->isPointerType())1216    return false; // Not an snprint1217 1218  QualType FirstPteTy = FirstParmTy->castAs<PointerType>()->getPointeeType();1219  const Expr *Buf = Node.getArg(0), *Size = Node.getArg(1);1220 1221  if (FirstPteTy.isConstQualified() || !FirstPteTy->isAnyCharacterType() ||1222      !Buf->getType()->isPointerType() ||1223      !Size->getType()->isUnsignedIntegerType())1224    return false; // not an snprintf call1225 1226  return !isPtrBufferSafe(Buf, Size, Ctx);1227}1228} // namespace libc_func_matchers1229 1230namespace {1231// Because the analysis revolves around variables and their types, we'll need to1232// track uses of variables (aka DeclRefExprs).1233using DeclUseList = SmallVector<const DeclRefExpr *, 1>;1234 1235// Convenience typedef.1236using FixItList = SmallVector<FixItHint, 4>;1237} // namespace1238 1239namespace {1240/// Gadget is an individual operation in the code that may be of interest to1241/// this analysis. Each (non-abstract) subclass corresponds to a specific1242/// rigid AST structure that constitutes an operation on a pointer-type object.1243/// Discovery of a gadget in the code corresponds to claiming that we understand1244/// what this part of code is doing well enough to potentially improve it.1245/// Gadgets can be warning (immediately deserving a warning) or fixable (not1246/// always deserving a warning per se, but requires our attention to identify1247/// it warrants a fixit).1248class Gadget {1249public:1250  enum class Kind {1251#define GADGET(x) x,1252#include "clang/Analysis/Analyses/UnsafeBufferUsageGadgets.def"1253  };1254 1255  Gadget(Kind K) : K(K) {}1256 1257  Kind getKind() const { return K; }1258 1259#ifndef NDEBUG1260  StringRef getDebugName() const {1261    switch (K) {1262#define GADGET(x)                                                              \1263  case Kind::x:                                                                \1264    return #x;1265#include "clang/Analysis/Analyses/UnsafeBufferUsageGadgets.def"1266    }1267    llvm_unreachable("Unhandled Gadget::Kind enum");1268  }1269#endif1270 1271  virtual bool isWarningGadget() const = 0;1272  // TODO remove this method from WarningGadget interface. It's only used for1273  // debug prints in FixableGadget.1274  virtual SourceLocation getSourceLoc() const = 0;1275 1276  /// Returns the list of pointer-type variables on which this gadget performs1277  /// its operation. Typically, there's only one variable. This isn't a list1278  /// of all DeclRefExprs in the gadget's AST!1279  virtual DeclUseList getClaimedVarUseSites() const = 0;1280 1281  virtual ~Gadget() = default;1282 1283private:1284  Kind K;1285};1286 1287/// Warning gadgets correspond to unsafe code patterns that warrants1288/// an immediate warning.1289class WarningGadget : public Gadget {1290public:1291  WarningGadget(Kind K) : Gadget(K) {}1292 1293  static bool classof(const Gadget *G) { return G->isWarningGadget(); }1294  bool isWarningGadget() const final { return true; }1295 1296  virtual void handleUnsafeOperation(UnsafeBufferUsageHandler &Handler,1297                                     bool IsRelatedToDecl,1298                                     ASTContext &Ctx) const = 0;1299 1300  virtual SmallVector<const Expr *, 1> getUnsafePtrs() const = 0;1301};1302 1303/// Fixable gadgets correspond to code patterns that aren't always unsafe but1304/// need to be properly recognized in order to emit fixes. For example, if a raw1305/// pointer-type variable is replaced by a safe C++ container, every use of such1306/// variable must be carefully considered and possibly updated.1307class FixableGadget : public Gadget {1308public:1309  FixableGadget(Kind K) : Gadget(K) {}1310 1311  static bool classof(const Gadget *G) { return !G->isWarningGadget(); }1312  bool isWarningGadget() const final { return false; }1313 1314  /// Returns a fixit that would fix the current gadget according to1315  /// the current strategy. Returns std::nullopt if the fix cannot be produced;1316  /// returns an empty list if no fixes are necessary.1317  virtual std::optional<FixItList> getFixits(const FixitStrategy &) const {1318    return std::nullopt;1319  }1320 1321  /// Returns a list of two elements where the first element is the LHS of a1322  /// pointer assignment statement and the second element is the RHS. This1323  /// two-element list represents the fact that the LHS buffer gets its bounds1324  /// information from the RHS buffer. This information will be used later to1325  /// group all those variables whose types must be modified together to prevent1326  /// type mismatches.1327  virtual std::optional<std::pair<const VarDecl *, const VarDecl *>>1328  getStrategyImplications() const {1329    return std::nullopt;1330  }1331};1332 1333static bool isSupportedVariable(const DeclRefExpr &Node) {1334  const Decl *D = Node.getDecl();1335  return D != nullptr && isa<VarDecl>(D);1336}1337 1338// Returns true for RecordDecl of type std::unique_ptr<T[]>1339static bool isUniquePtrArray(const CXXRecordDecl *RecordDecl) {1340  if (!RecordDecl || !RecordDecl->isInStdNamespace() ||1341      RecordDecl->getNameAsString() != "unique_ptr")1342    return false;1343 1344  const ClassTemplateSpecializationDecl *class_template_specialization_decl =1345      dyn_cast<ClassTemplateSpecializationDecl>(RecordDecl);1346  if (!class_template_specialization_decl)1347    return false;1348 1349  const TemplateArgumentList &template_args =1350      class_template_specialization_decl->getTemplateArgs();1351  if (template_args.size() == 0)1352    return false;1353 1354  const TemplateArgument &first_arg = template_args[0];1355  if (first_arg.getKind() != TemplateArgument::Type)1356    return false;1357 1358  QualType referred_type = first_arg.getAsType();1359  return referred_type->isArrayType();1360}1361 1362class UniquePtrArrayAccessGadget : public WarningGadget {1363private:1364  static constexpr const char *const AccessorTag = "unique_ptr_array_access";1365  const CXXOperatorCallExpr *AccessorExpr;1366 1367public:1368  UniquePtrArrayAccessGadget(const MatchResult &Result)1369      : WarningGadget(Kind::UniquePtrArrayAccess),1370        AccessorExpr(Result.getNodeAs<CXXOperatorCallExpr>(AccessorTag)) {1371    assert(AccessorExpr &&1372           "UniquePtrArrayAccessGadget requires a matched CXXOperatorCallExpr");1373  }1374 1375  static bool classof(const Gadget *G) {1376    return G->getKind() == Kind::UniquePtrArrayAccess;1377  }1378 1379  static bool matches(const Stmt *S, const ASTContext &Ctx,1380                      MatchResult &Result) {1381 1382    const CXXOperatorCallExpr *OpCall = dyn_cast<CXXOperatorCallExpr>(S);1383    if (!OpCall || OpCall->getOperator() != OO_Subscript)1384      return false;1385 1386    const Expr *Callee = OpCall->getCallee()->IgnoreParenImpCasts();1387    if (!Callee)1388      return false;1389 1390    const CXXMethodDecl *Method =1391        dyn_cast_or_null<CXXMethodDecl>(OpCall->getDirectCallee());1392    if (!Method)1393      return false;1394 1395    if (Method->getOverloadedOperator() != OO_Subscript)1396      return false;1397 1398    const CXXRecordDecl *RecordDecl = Method->getParent();1399    if (!isUniquePtrArray(RecordDecl))1400      return false;1401 1402    const Expr *IndexExpr = OpCall->getArg(1);1403    clang::Expr::EvalResult Eval;1404 1405    // Allow [0]1406    if (IndexExpr->EvaluateAsInt(Eval, Ctx) && Eval.Val.getInt().isZero())1407      return false;1408 1409    Result.addNode(AccessorTag, DynTypedNode::create(*OpCall));1410    return true;1411  }1412  void handleUnsafeOperation(UnsafeBufferUsageHandler &Handler,1413                             bool IsRelatedToDecl,1414                             ASTContext &Ctx) const override {1415    Handler.handleUnsafeUniquePtrArrayAccess(1416        DynTypedNode::create(*AccessorExpr), IsRelatedToDecl, Ctx);1417  }1418 1419  SourceLocation getSourceLoc() const override {1420    if (AccessorExpr)1421      return AccessorExpr->getOperatorLoc();1422    return SourceLocation();1423  }1424 1425  DeclUseList getClaimedVarUseSites() const override { return {}; }1426  SmallVector<const Expr *, 1> getUnsafePtrs() const override { return {}; }1427};1428 1429using FixableGadgetList = std::vector<std::unique_ptr<FixableGadget>>;1430using WarningGadgetList = std::vector<std::unique_ptr<WarningGadget>>;1431 1432/// An increment of a pointer-type value is unsafe as it may run the pointer1433/// out of bounds.1434class IncrementGadget : public WarningGadget {1435  static constexpr const char *const OpTag = "op";1436  const UnaryOperator *Op;1437 1438public:1439  IncrementGadget(const MatchResult &Result)1440      : WarningGadget(Kind::Increment),1441        Op(Result.getNodeAs<UnaryOperator>(OpTag)) {}1442 1443  static bool classof(const Gadget *G) {1444    return G->getKind() == Kind::Increment;1445  }1446 1447  static bool matches(const Stmt *S, const ASTContext &Ctx,1448                      MatchResult &Result) {1449    const auto *UO = dyn_cast<UnaryOperator>(S);1450    if (!UO || !UO->isIncrementOp())1451      return false;1452    if (!hasPointerType(*UO->getSubExpr()->IgnoreParenImpCasts()))1453      return false;1454    Result.addNode(OpTag, DynTypedNode::create(*UO));1455    return true;1456  }1457 1458  void handleUnsafeOperation(UnsafeBufferUsageHandler &Handler,1459                             bool IsRelatedToDecl,1460                             ASTContext &Ctx) const override {1461    Handler.handleUnsafeOperation(Op, IsRelatedToDecl, Ctx);1462  }1463  SourceLocation getSourceLoc() const override { return Op->getBeginLoc(); }1464 1465  DeclUseList getClaimedVarUseSites() const override {1466    SmallVector<const DeclRefExpr *, 2> Uses;1467    if (const auto *DRE =1468            dyn_cast<DeclRefExpr>(Op->getSubExpr()->IgnoreParenImpCasts())) {1469      Uses.push_back(DRE);1470    }1471 1472    return std::move(Uses);1473  }1474 1475  SmallVector<const Expr *, 1> getUnsafePtrs() const override {1476    return {Op->getSubExpr()->IgnoreParenImpCasts()};1477  }1478};1479 1480/// A decrement of a pointer-type value is unsafe as it may run the pointer1481/// out of bounds.1482class DecrementGadget : public WarningGadget {1483  static constexpr const char *const OpTag = "op";1484  const UnaryOperator *Op;1485 1486public:1487  DecrementGadget(const MatchResult &Result)1488      : WarningGadget(Kind::Decrement),1489        Op(Result.getNodeAs<UnaryOperator>(OpTag)) {}1490 1491  static bool classof(const Gadget *G) {1492    return G->getKind() == Kind::Decrement;1493  }1494 1495  static bool matches(const Stmt *S, const ASTContext &Ctx,1496                      MatchResult &Result) {1497    const auto *UO = dyn_cast<UnaryOperator>(S);1498    if (!UO || !UO->isDecrementOp())1499      return false;1500    if (!hasPointerType(*UO->getSubExpr()->IgnoreParenImpCasts()))1501      return false;1502    Result.addNode(OpTag, DynTypedNode::create(*UO));1503    return true;1504  }1505 1506  void handleUnsafeOperation(UnsafeBufferUsageHandler &Handler,1507                             bool IsRelatedToDecl,1508                             ASTContext &Ctx) const override {1509    Handler.handleUnsafeOperation(Op, IsRelatedToDecl, Ctx);1510  }1511  SourceLocation getSourceLoc() const override { return Op->getBeginLoc(); }1512 1513  DeclUseList getClaimedVarUseSites() const override {1514    if (const auto *DRE =1515            dyn_cast<DeclRefExpr>(Op->getSubExpr()->IgnoreParenImpCasts())) {1516      return {DRE};1517    }1518 1519    return {};1520  }1521 1522  SmallVector<const Expr *, 1> getUnsafePtrs() const override {1523    return {Op->getSubExpr()->IgnoreParenImpCasts()};1524  }1525};1526 1527/// Array subscript expressions on raw pointers as if they're arrays. Unsafe as1528/// it doesn't have any bounds checks for the array.1529class ArraySubscriptGadget : public WarningGadget {1530  static constexpr const char *const ArraySubscrTag = "ArraySubscript";1531  const ArraySubscriptExpr *ASE;1532 1533public:1534  ArraySubscriptGadget(const MatchResult &Result)1535      : WarningGadget(Kind::ArraySubscript),1536        ASE(Result.getNodeAs<ArraySubscriptExpr>(ArraySubscrTag)) {}1537 1538  static bool classof(const Gadget *G) {1539    return G->getKind() == Kind::ArraySubscript;1540  }1541 1542  static bool matches(const Stmt *S, const ASTContext &Ctx,1543                      MatchResult &Result) {1544    const auto *ASE = dyn_cast<ArraySubscriptExpr>(S);1545    if (!ASE)1546      return false;1547    const auto *const Base = ASE->getBase()->IgnoreParenImpCasts();1548    if (!hasPointerType(*Base) && !hasArrayType(*Base))1549      return false;1550    const auto *Idx = dyn_cast<IntegerLiteral>(ASE->getIdx());1551    bool IsSafeIndex = (Idx && Idx->getValue().isZero()) ||1552                       isa<ArrayInitIndexExpr>(ASE->getIdx());1553    if (IsSafeIndex || isSafeArraySubscript(*ASE, Ctx))1554      return false;1555    Result.addNode(ArraySubscrTag, DynTypedNode::create(*ASE));1556    return true;1557  }1558 1559  void handleUnsafeOperation(UnsafeBufferUsageHandler &Handler,1560                             bool IsRelatedToDecl,1561                             ASTContext &Ctx) const override {1562    Handler.handleUnsafeOperation(ASE, IsRelatedToDecl, Ctx);1563  }1564  SourceLocation getSourceLoc() const override { return ASE->getBeginLoc(); }1565 1566  DeclUseList getClaimedVarUseSites() const override {1567    if (const auto *DRE =1568            dyn_cast<DeclRefExpr>(ASE->getBase()->IgnoreParenImpCasts())) {1569      return {DRE};1570    }1571 1572    return {};1573  }1574 1575  SmallVector<const Expr *, 1> getUnsafePtrs() const override {1576    return {ASE->getBase()->IgnoreParenImpCasts()};1577  }1578};1579 1580/// A pointer arithmetic expression of one of the forms:1581///  \code1582///  ptr + n | n + ptr | ptr - n | ptr += n | ptr -= n1583///  \endcode1584class PointerArithmeticGadget : public WarningGadget {1585  static constexpr const char *const PointerArithmeticTag = "ptrAdd";1586  static constexpr const char *const PointerArithmeticPointerTag = "ptrAddPtr";1587  const BinaryOperator *PA; // pointer arithmetic expression1588  const Expr *Ptr;          // the pointer expression in `PA`1589 1590public:1591  PointerArithmeticGadget(const MatchResult &Result)1592      : WarningGadget(Kind::PointerArithmetic),1593        PA(Result.getNodeAs<BinaryOperator>(PointerArithmeticTag)),1594        Ptr(Result.getNodeAs<Expr>(PointerArithmeticPointerTag)) {}1595 1596  static bool classof(const Gadget *G) {1597    return G->getKind() == Kind::PointerArithmetic;1598  }1599 1600  static bool matches(const Stmt *S, const ASTContext &Ctx,1601                      MatchResult &Result) {1602    const auto *BO = dyn_cast<BinaryOperator>(S);1603    if (!BO)1604      return false;1605    const auto *LHS = BO->getLHS();1606    const auto *RHS = BO->getRHS();1607    // ptr at left1608    if (BO->getOpcode() == BO_Add || BO->getOpcode() == BO_Sub ||1609        BO->getOpcode() == BO_AddAssign || BO->getOpcode() == BO_SubAssign) {1610      if (hasPointerType(*LHS) && (RHS->getType()->isIntegerType() ||1611                                   RHS->getType()->isEnumeralType())) {1612        Result.addNode(PointerArithmeticPointerTag, DynTypedNode::create(*LHS));1613        Result.addNode(PointerArithmeticTag, DynTypedNode::create(*BO));1614        return true;1615      }1616    }1617    // ptr at right1618    if (BO->getOpcode() == BO_Add && hasPointerType(*RHS) &&1619        (LHS->getType()->isIntegerType() || LHS->getType()->isEnumeralType())) {1620      Result.addNode(PointerArithmeticPointerTag, DynTypedNode::create(*RHS));1621      Result.addNode(PointerArithmeticTag, DynTypedNode::create(*BO));1622      return true;1623    }1624    return false;1625  }1626 1627  void handleUnsafeOperation(UnsafeBufferUsageHandler &Handler,1628                             bool IsRelatedToDecl,1629                             ASTContext &Ctx) const override {1630    Handler.handleUnsafeOperation(PA, IsRelatedToDecl, Ctx);1631  }1632  SourceLocation getSourceLoc() const override { return PA->getBeginLoc(); }1633 1634  DeclUseList getClaimedVarUseSites() const override {1635    if (const auto *DRE = dyn_cast<DeclRefExpr>(Ptr->IgnoreParenImpCasts())) {1636      return {DRE};1637    }1638 1639    return {};1640  }1641 1642  SmallVector<const Expr *, 1> getUnsafePtrs() const override {1643    return {Ptr->IgnoreParenImpCasts()};1644  }1645 1646  // FIXME: pointer adding zero should be fine1647  // FIXME: this gadge will need a fix-it1648};1649 1650class SpanTwoParamConstructorGadget : public WarningGadget {1651  static constexpr const char *const SpanTwoParamConstructorTag =1652      "spanTwoParamConstructor";1653  const CXXConstructExpr *Ctor; // the span constructor expression1654 1655public:1656  SpanTwoParamConstructorGadget(const MatchResult &Result)1657      : WarningGadget(Kind::SpanTwoParamConstructor),1658        Ctor(Result.getNodeAs<CXXConstructExpr>(SpanTwoParamConstructorTag)) {}1659 1660  static bool classof(const Gadget *G) {1661    return G->getKind() == Kind::SpanTwoParamConstructor;1662  }1663 1664  static bool matches(const Stmt *S, ASTContext &Ctx, MatchResult &Result) {1665    const auto *CE = dyn_cast<CXXConstructExpr>(S);1666    if (!CE)1667      return false;1668    const auto *CDecl = CE->getConstructor();1669    const auto *CRecordDecl = CDecl->getParent();1670    auto HasTwoParamSpanCtorDecl =1671        CRecordDecl->isInStdNamespace() &&1672        CDecl->getDeclName().getAsString() == "span" && CE->getNumArgs() == 2;1673    if (!HasTwoParamSpanCtorDecl || isSafeSpanTwoParamConstruct(*CE, Ctx))1674      return false;1675    Result.addNode(SpanTwoParamConstructorTag, DynTypedNode::create(*CE));1676    return true;1677  }1678 1679  static bool matches(const Stmt *S, ASTContext &Ctx,1680                      const UnsafeBufferUsageHandler *Handler,1681                      MatchResult &Result) {1682    if (ignoreUnsafeBufferInContainer(*S, Handler))1683      return false;1684    return matches(S, Ctx, Result);1685  }1686 1687  void handleUnsafeOperation(UnsafeBufferUsageHandler &Handler,1688                             bool IsRelatedToDecl,1689                             ASTContext &Ctx) const override {1690    Handler.handleUnsafeOperationInContainer(Ctor, IsRelatedToDecl, Ctx);1691  }1692  SourceLocation getSourceLoc() const override { return Ctor->getBeginLoc(); }1693 1694  DeclUseList getClaimedVarUseSites() const override {1695    // If the constructor call is of the form `std::span{var, n}`, `var` is1696    // considered an unsafe variable.1697    if (auto *DRE = dyn_cast<DeclRefExpr>(Ctor->getArg(0))) {1698      if (isa<VarDecl>(DRE->getDecl()))1699        return {DRE};1700    }1701    return {};1702  }1703 1704  SmallVector<const Expr *, 1> getUnsafePtrs() const override { return {}; }1705};1706 1707/// A pointer initialization expression of the form:1708///  \code1709///  int *p = q;1710///  \endcode1711class PointerInitGadget : public FixableGadget {1712private:1713  static constexpr const char *const PointerInitLHSTag = "ptrInitLHS";1714  static constexpr const char *const PointerInitRHSTag = "ptrInitRHS";1715  const VarDecl *PtrInitLHS;     // the LHS pointer expression in `PI`1716  const DeclRefExpr *PtrInitRHS; // the RHS pointer expression in `PI`1717 1718public:1719  PointerInitGadget(const MatchResult &Result)1720      : FixableGadget(Kind::PointerInit),1721        PtrInitLHS(Result.getNodeAs<VarDecl>(PointerInitLHSTag)),1722        PtrInitRHS(Result.getNodeAs<DeclRefExpr>(PointerInitRHSTag)) {}1723 1724  static bool classof(const Gadget *G) {1725    return G->getKind() == Kind::PointerInit;1726  }1727 1728  static bool matches(const Stmt *S,1729                      llvm::SmallVectorImpl<MatchResult> &Results) {1730    const DeclStmt *DS = dyn_cast<DeclStmt>(S);1731    if (!DS || !DS->isSingleDecl())1732      return false;1733    const VarDecl *VD = dyn_cast<VarDecl>(DS->getSingleDecl());1734    if (!VD)1735      return false;1736    const Expr *Init = VD->getAnyInitializer();1737    if (!Init)1738      return false;1739    const auto *DRE = dyn_cast<DeclRefExpr>(Init->IgnoreImpCasts());1740    if (!DRE || !hasPointerType(*DRE) || !isSupportedVariable(*DRE)) {1741      return false;1742    }1743    MatchResult R;1744    R.addNode(PointerInitLHSTag, DynTypedNode::create(*VD));1745    R.addNode(PointerInitRHSTag, DynTypedNode::create(*DRE));1746    Results.emplace_back(std::move(R));1747    return true;1748  }1749 1750  virtual std::optional<FixItList>1751  getFixits(const FixitStrategy &S) const override;1752  SourceLocation getSourceLoc() const override {1753    return PtrInitRHS->getBeginLoc();1754  }1755 1756  virtual DeclUseList getClaimedVarUseSites() const override {1757    return DeclUseList{PtrInitRHS};1758  }1759 1760  virtual std::optional<std::pair<const VarDecl *, const VarDecl *>>1761  getStrategyImplications() const override {1762    return std::make_pair(PtrInitLHS, cast<VarDecl>(PtrInitRHS->getDecl()));1763  }1764};1765 1766/// A pointer assignment expression of the form:1767///  \code1768///  p = q;1769///  \endcode1770/// where both `p` and `q` are pointers.1771class PtrToPtrAssignmentGadget : public FixableGadget {1772private:1773  static constexpr const char *const PointerAssignLHSTag = "ptrLHS";1774  static constexpr const char *const PointerAssignRHSTag = "ptrRHS";1775  const DeclRefExpr *PtrLHS; // the LHS pointer expression in `PA`1776  const DeclRefExpr *PtrRHS; // the RHS pointer expression in `PA`1777 1778public:1779  PtrToPtrAssignmentGadget(const MatchResult &Result)1780      : FixableGadget(Kind::PtrToPtrAssignment),1781        PtrLHS(Result.getNodeAs<DeclRefExpr>(PointerAssignLHSTag)),1782        PtrRHS(Result.getNodeAs<DeclRefExpr>(PointerAssignRHSTag)) {}1783 1784  static bool classof(const Gadget *G) {1785    return G->getKind() == Kind::PtrToPtrAssignment;1786  }1787 1788  static bool matches(const Stmt *S,1789                      llvm::SmallVectorImpl<MatchResult> &Results) {1790    size_t SizeBefore = Results.size();1791    findStmtsInUnspecifiedUntypedContext(S, [&Results](const Stmt *S) {1792      const auto *BO = dyn_cast<BinaryOperator>(S);1793      if (!BO || BO->getOpcode() != BO_Assign)1794        return;1795      const auto *RHS = BO->getRHS()->IgnoreParenImpCasts();1796      if (const auto *RHSRef = dyn_cast<DeclRefExpr>(RHS);1797          !RHSRef || !hasPointerType(*RHSRef) ||1798          !isSupportedVariable(*RHSRef)) {1799        return;1800      }1801      const auto *LHS = BO->getLHS();1802      if (const auto *LHSRef = dyn_cast<DeclRefExpr>(LHS);1803          !LHSRef || !hasPointerType(*LHSRef) ||1804          !isSupportedVariable(*LHSRef)) {1805        return;1806      }1807      MatchResult R;1808      R.addNode(PointerAssignLHSTag, DynTypedNode::create(*LHS));1809      R.addNode(PointerAssignRHSTag, DynTypedNode::create(*RHS));1810      Results.emplace_back(std::move(R));1811    });1812    return SizeBefore != Results.size();1813  }1814 1815  virtual std::optional<FixItList>1816  getFixits(const FixitStrategy &S) const override;1817  SourceLocation getSourceLoc() const override { return PtrLHS->getBeginLoc(); }1818 1819  virtual DeclUseList getClaimedVarUseSites() const override {1820    return DeclUseList{PtrLHS, PtrRHS};1821  }1822 1823  virtual std::optional<std::pair<const VarDecl *, const VarDecl *>>1824  getStrategyImplications() const override {1825    return std::make_pair(cast<VarDecl>(PtrLHS->getDecl()),1826                          cast<VarDecl>(PtrRHS->getDecl()));1827  }1828};1829 1830/// An assignment expression of the form:1831///  \code1832///  ptr = array;1833///  \endcode1834/// where `p` is a pointer and `array` is a constant size array.1835class CArrayToPtrAssignmentGadget : public FixableGadget {1836private:1837  static constexpr const char *const PointerAssignLHSTag = "ptrLHS";1838  static constexpr const char *const PointerAssignRHSTag = "ptrRHS";1839  const DeclRefExpr *PtrLHS; // the LHS pointer expression in `PA`1840  const DeclRefExpr *PtrRHS; // the RHS pointer expression in `PA`1841 1842public:1843  CArrayToPtrAssignmentGadget(const MatchResult &Result)1844      : FixableGadget(Kind::CArrayToPtrAssignment),1845        PtrLHS(Result.getNodeAs<DeclRefExpr>(PointerAssignLHSTag)),1846        PtrRHS(Result.getNodeAs<DeclRefExpr>(PointerAssignRHSTag)) {}1847 1848  static bool classof(const Gadget *G) {1849    return G->getKind() == Kind::CArrayToPtrAssignment;1850  }1851 1852  static bool matches(const Stmt *S,1853                      llvm::SmallVectorImpl<MatchResult> &Results) {1854    size_t SizeBefore = Results.size();1855    findStmtsInUnspecifiedUntypedContext(S, [&Results](const Stmt *S) {1856      const auto *BO = dyn_cast<BinaryOperator>(S);1857      if (!BO || BO->getOpcode() != BO_Assign)1858        return;1859      const auto *RHS = BO->getRHS()->IgnoreParenImpCasts();1860      if (const auto *RHSRef = dyn_cast<DeclRefExpr>(RHS);1861          !RHSRef ||1862          !isa<ConstantArrayType>(RHSRef->getType().getCanonicalType()) ||1863          !isSupportedVariable(*RHSRef)) {1864        return;1865      }1866      const auto *LHS = BO->getLHS();1867      if (const auto *LHSRef = dyn_cast<DeclRefExpr>(LHS);1868          !LHSRef || !hasPointerType(*LHSRef) ||1869          !isSupportedVariable(*LHSRef)) {1870        return;1871      }1872      MatchResult R;1873      R.addNode(PointerAssignLHSTag, DynTypedNode::create(*LHS));1874      R.addNode(PointerAssignRHSTag, DynTypedNode::create(*RHS));1875      Results.emplace_back(std::move(R));1876    });1877    return SizeBefore != Results.size();1878  }1879 1880  virtual std::optional<FixItList>1881  getFixits(const FixitStrategy &S) const override;1882  SourceLocation getSourceLoc() const override { return PtrLHS->getBeginLoc(); }1883 1884  virtual DeclUseList getClaimedVarUseSites() const override {1885    return DeclUseList{PtrLHS, PtrRHS};1886  }1887 1888  virtual std::optional<std::pair<const VarDecl *, const VarDecl *>>1889  getStrategyImplications() const override {1890    return {};1891  }1892};1893 1894/// A call of a function or method that performs unchecked buffer operations1895/// over one of its pointer parameters.1896class UnsafeBufferUsageAttrGadget : public WarningGadget {1897  constexpr static const char *const OpTag = "attr_expr";1898  const Expr *Op;1899 1900public:1901  UnsafeBufferUsageAttrGadget(const MatchResult &Result)1902      : WarningGadget(Kind::UnsafeBufferUsageAttr),1903        Op(Result.getNodeAs<Expr>(OpTag)) {}1904 1905  static bool classof(const Gadget *G) {1906    return G->getKind() == Kind::UnsafeBufferUsageAttr;1907  }1908 1909  static bool matches(const Stmt *S, const ASTContext &Ctx,1910                      MatchResult &Result) {1911    if (auto *CE = dyn_cast<CallExpr>(S)) {1912      if (CE->getDirectCallee() &&1913          CE->getDirectCallee()->hasAttr<UnsafeBufferUsageAttr>()) {1914        Result.addNode(OpTag, DynTypedNode::create(*CE));1915        return true;1916      }1917    }1918    if (auto *ME = dyn_cast<MemberExpr>(S)) {1919      if (!isa<FieldDecl>(ME->getMemberDecl()))1920        return false;1921      if (ME->getMemberDecl()->hasAttr<UnsafeBufferUsageAttr>()) {1922        Result.addNode(OpTag, DynTypedNode::create(*ME));1923        return true;1924      }1925    }1926    return false;1927  }1928 1929  void handleUnsafeOperation(UnsafeBufferUsageHandler &Handler,1930                             bool IsRelatedToDecl,1931                             ASTContext &Ctx) const override {1932    Handler.handleUnsafeOperation(Op, IsRelatedToDecl, Ctx);1933  }1934  SourceLocation getSourceLoc() const override { return Op->getBeginLoc(); }1935 1936  DeclUseList getClaimedVarUseSites() const override { return {}; }1937 1938  SmallVector<const Expr *, 1> getUnsafePtrs() const override { return {}; }1939};1940 1941/// A call of a constructor that performs unchecked buffer operations1942/// over one of its pointer parameters, or constructs a class object that will1943/// perform buffer operations that depend on the correctness of the parameters.1944class UnsafeBufferUsageCtorAttrGadget : public WarningGadget {1945  constexpr static const char *const OpTag = "cxx_construct_expr";1946  const CXXConstructExpr *Op;1947 1948public:1949  UnsafeBufferUsageCtorAttrGadget(const MatchResult &Result)1950      : WarningGadget(Kind::UnsafeBufferUsageCtorAttr),1951        Op(Result.getNodeAs<CXXConstructExpr>(OpTag)) {}1952 1953  static bool classof(const Gadget *G) {1954    return G->getKind() == Kind::UnsafeBufferUsageCtorAttr;1955  }1956 1957  static bool matches(const Stmt *S, ASTContext &Ctx, MatchResult &Result) {1958    const auto *CE = dyn_cast<CXXConstructExpr>(S);1959    if (!CE || !CE->getConstructor()->hasAttr<UnsafeBufferUsageAttr>())1960      return false;1961    // std::span(ptr, size) ctor is handled by SpanTwoParamConstructorGadget.1962    MatchResult Tmp;1963    if (SpanTwoParamConstructorGadget::matches(CE, Ctx, Tmp))1964      return false;1965    Result.addNode(OpTag, DynTypedNode::create(*CE));1966    return true;1967  }1968 1969  void handleUnsafeOperation(UnsafeBufferUsageHandler &Handler,1970                             bool IsRelatedToDecl,1971                             ASTContext &Ctx) const override {1972    Handler.handleUnsafeOperation(Op, IsRelatedToDecl, Ctx);1973  }1974  SourceLocation getSourceLoc() const override { return Op->getBeginLoc(); }1975 1976  DeclUseList getClaimedVarUseSites() const override { return {}; }1977 1978  SmallVector<const Expr *, 1> getUnsafePtrs() const override { return {}; }1979};1980 1981// Warning gadget for unsafe invocation of span::data method.1982// Triggers when the pointer returned by the invocation is immediately1983// cast to a larger type.1984 1985class DataInvocationGadget : public WarningGadget {1986  constexpr static const char *const OpTag = "data_invocation_expr";1987  const ExplicitCastExpr *Op;1988 1989public:1990  DataInvocationGadget(const MatchResult &Result)1991      : WarningGadget(Kind::DataInvocation),1992        Op(Result.getNodeAs<ExplicitCastExpr>(OpTag)) {}1993 1994  static bool classof(const Gadget *G) {1995    return G->getKind() == Kind::DataInvocation;1996  }1997 1998  static bool matches(const Stmt *S, const ASTContext &Ctx,1999                      MatchResult &Result) {2000    auto *CE = dyn_cast<ExplicitCastExpr>(S);2001    if (!CE)2002      return false;2003    for (auto *Child : CE->children()) {2004      if (auto *MCE = dyn_cast<CXXMemberCallExpr>(Child);2005          MCE && isDataFunction(MCE)) {2006        Result.addNode(OpTag, DynTypedNode::create(*CE));2007        return true;2008      }2009      if (auto *Paren = dyn_cast<ParenExpr>(Child)) {2010        if (auto *MCE = dyn_cast<CXXMemberCallExpr>(Paren->getSubExpr());2011            MCE && isDataFunction(MCE)) {2012          Result.addNode(OpTag, DynTypedNode::create(*CE));2013          return true;2014        }2015      }2016    }2017    return false;2018  }2019 2020  void handleUnsafeOperation(UnsafeBufferUsageHandler &Handler,2021                             bool IsRelatedToDecl,2022                             ASTContext &Ctx) const override {2023    Handler.handleUnsafeOperation(Op, IsRelatedToDecl, Ctx);2024  }2025  SourceLocation getSourceLoc() const override { return Op->getBeginLoc(); }2026 2027  DeclUseList getClaimedVarUseSites() const override { return {}; }2028 2029private:2030  static bool isDataFunction(const CXXMemberCallExpr *call) {2031    if (!call)2032      return false;2033    auto *callee = call->getDirectCallee();2034    if (!callee || !isa<CXXMethodDecl>(callee))2035      return false;2036    auto *method = cast<CXXMethodDecl>(callee);2037    if (method->getNameAsString() == "data" &&2038        method->getParent()->isInStdNamespace() &&2039        llvm::is_contained({SIZED_CONTAINER_OR_VIEW_LIST},2040                           method->getParent()->getName()))2041      return true;2042    return false;2043  }2044 2045  SmallVector<const Expr *, 1> getUnsafePtrs() const override { return {}; }2046};2047 2048class UnsafeLibcFunctionCallGadget : public WarningGadget {2049  const CallExpr *const Call;2050  const Expr *UnsafeArg = nullptr;2051  constexpr static const char *const Tag = "UnsafeLibcFunctionCall";2052  // Extra tags for additional information:2053  constexpr static const char *const UnsafeSprintfTag =2054      "UnsafeLibcFunctionCall_sprintf";2055  constexpr static const char *const UnsafeSizedByTag =2056      "UnsafeLibcFunctionCall_sized_by";2057  constexpr static const char *const UnsafeStringTag =2058      "UnsafeLibcFunctionCall_string";2059  constexpr static const char *const UnsafeVaListTag =2060      "UnsafeLibcFunctionCall_va_list";2061 2062  enum UnsafeKind {2063    OTHERS = 0,  // no specific information, the callee function is unsafe2064    SPRINTF = 1, // never call `-sprintf`s, call `-snprintf`s instead.2065    SIZED_BY =2066        2, // the first two arguments of `snprintf` function have2067           // "__sized_by" relation but they do not conform to safe patterns2068    STRING = 3,  // an argument is a pointer-to-char-as-string but does not2069                 // guarantee null-termination2070    VA_LIST = 4, // one of the `-printf`s function that take va_list, which is2071                 // considered unsafe as it is not compile-time check2072  } WarnedFunKind = OTHERS;2073 2074public:2075  UnsafeLibcFunctionCallGadget(const MatchResult &Result)2076      : WarningGadget(Kind::UnsafeLibcFunctionCall),2077        Call(Result.getNodeAs<CallExpr>(Tag)) {2078    if (Result.getNodeAs<Decl>(UnsafeSprintfTag))2079      WarnedFunKind = SPRINTF;2080    else if (auto *E = Result.getNodeAs<Expr>(UnsafeStringTag)) {2081      WarnedFunKind = STRING;2082      UnsafeArg = E;2083    } else if (Result.getNodeAs<CallExpr>(UnsafeSizedByTag)) {2084      WarnedFunKind = SIZED_BY;2085      UnsafeArg = Call->getArg(0);2086    } else if (Result.getNodeAs<Decl>(UnsafeVaListTag))2087      WarnedFunKind = VA_LIST;2088  }2089 2090  static bool matches(const Stmt *S, ASTContext &Ctx,2091                      const UnsafeBufferUsageHandler *Handler,2092                      MatchResult &Result) {2093    if (ignoreUnsafeLibcCall(Ctx, *S, Handler))2094      return false;2095    auto *CE = dyn_cast<CallExpr>(S);2096    if (!CE || !CE->getDirectCallee())2097      return false;2098    const auto *FD = dyn_cast<FunctionDecl>(CE->getDirectCallee());2099    if (!FD)2100      return false;2101 2102    bool IsGlobalAndNotInAnyNamespace =2103        FD->isGlobal() && !FD->getEnclosingNamespaceContext()->isNamespace();2104 2105    // A libc function must either be in the std:: namespace or a global2106    // function that is not in any namespace:2107    if (!FD->isInStdNamespace() && !IsGlobalAndNotInAnyNamespace)2108      return false;2109    auto isSingleStringLiteralArg = false;2110    if (CE->getNumArgs() == 1) {2111      isSingleStringLiteralArg =2112          isa<clang::StringLiteral>(CE->getArg(0)->IgnoreParenImpCasts());2113    }2114    if (!isSingleStringLiteralArg) {2115      // (unless the call has a sole string literal argument):2116      if (libc_func_matchers::isPredefinedUnsafeLibcFunc(*FD)) {2117        Result.addNode(Tag, DynTypedNode::create(*CE));2118        return true;2119      }2120      if (libc_func_matchers::isUnsafeVaListPrintfFunc(*FD)) {2121        Result.addNode(Tag, DynTypedNode::create(*CE));2122        Result.addNode(UnsafeVaListTag, DynTypedNode::create(*FD));2123        return true;2124      }2125      if (libc_func_matchers::isUnsafeSprintfFunc(*FD)) {2126        Result.addNode(Tag, DynTypedNode::create(*CE));2127        Result.addNode(UnsafeSprintfTag, DynTypedNode::create(*FD));2128        return true;2129      }2130    }2131    if (libc_func_matchers::isNormalPrintfFunc(*FD)) {2132      if (libc_func_matchers::hasUnsafeSnprintfBuffer(*CE, Ctx)) {2133        Result.addNode(Tag, DynTypedNode::create(*CE));2134        Result.addNode(UnsafeSizedByTag, DynTypedNode::create(*CE));2135        return true;2136      }2137      if (libc_func_matchers::hasUnsafePrintfStringArg(*CE, Ctx, Result,2138                                                       UnsafeStringTag)) {2139        Result.addNode(Tag, DynTypedNode::create(*CE));2140        return true;2141      }2142    }2143    return false;2144  }2145 2146  const Stmt *getBaseStmt() const { return Call; }2147 2148  SourceLocation getSourceLoc() const override { return Call->getBeginLoc(); }2149 2150  void handleUnsafeOperation(UnsafeBufferUsageHandler &Handler,2151                             bool IsRelatedToDecl,2152                             ASTContext &Ctx) const override {2153    Handler.handleUnsafeLibcCall(Call, WarnedFunKind, Ctx, UnsafeArg);2154  }2155 2156  DeclUseList getClaimedVarUseSites() const override { return {}; }2157 2158  SmallVector<const Expr *, 1> getUnsafePtrs() const override { return {}; }2159};2160 2161// Represents expressions of the form `DRE[*]` in the Unspecified Lvalue2162// Context (see `findStmtsInUnspecifiedLvalueContext`).2163// Note here `[]` is the built-in subscript operator.2164class ULCArraySubscriptGadget : public FixableGadget {2165private:2166  static constexpr const char *const ULCArraySubscriptTag =2167      "ArraySubscriptUnderULC";2168  const ArraySubscriptExpr *Node;2169 2170public:2171  ULCArraySubscriptGadget(const MatchResult &Result)2172      : FixableGadget(Kind::ULCArraySubscript),2173        Node(Result.getNodeAs<ArraySubscriptExpr>(ULCArraySubscriptTag)) {2174    assert(Node != nullptr && "Expecting a non-null matching result");2175  }2176 2177  static bool classof(const Gadget *G) {2178    return G->getKind() == Kind::ULCArraySubscript;2179  }2180 2181  static bool matches(const Stmt *S,2182                      llvm::SmallVectorImpl<MatchResult> &Results) {2183    size_t SizeBefore = Results.size();2184    findStmtsInUnspecifiedLvalueContext(S, [&Results](const Expr *E) {2185      const auto *ASE = dyn_cast<ArraySubscriptExpr>(E);2186      if (!ASE)2187        return;2188      const auto *DRE =2189          dyn_cast<DeclRefExpr>(ASE->getBase()->IgnoreParenImpCasts());2190      if (!DRE || !(hasPointerType(*DRE) || hasArrayType(*DRE)) ||2191          !isSupportedVariable(*DRE))2192        return;2193      MatchResult R;2194      R.addNode(ULCArraySubscriptTag, DynTypedNode::create(*ASE));2195      Results.emplace_back(std::move(R));2196    });2197    return SizeBefore != Results.size();2198  }2199 2200  virtual std::optional<FixItList>2201  getFixits(const FixitStrategy &S) const override;2202  SourceLocation getSourceLoc() const override { return Node->getBeginLoc(); }2203 2204  virtual DeclUseList getClaimedVarUseSites() const override {2205    if (const auto *DRE =2206            dyn_cast<DeclRefExpr>(Node->getBase()->IgnoreImpCasts())) {2207      return {DRE};2208    }2209    return {};2210  }2211};2212 2213// Fixable gadget to handle stand alone pointers of the form `UPC(DRE)` in the2214// unspecified pointer context (findStmtsInUnspecifiedPointerContext). The2215// gadget emits fixit of the form `UPC(DRE.data())`.2216class UPCStandalonePointerGadget : public FixableGadget {2217private:2218  static constexpr const char *const DeclRefExprTag = "StandalonePointer";2219  const DeclRefExpr *Node;2220 2221public:2222  UPCStandalonePointerGadget(const MatchResult &Result)2223      : FixableGadget(Kind::UPCStandalonePointer),2224        Node(Result.getNodeAs<DeclRefExpr>(DeclRefExprTag)) {2225    assert(Node != nullptr && "Expecting a non-null matching result");2226  }2227 2228  static bool classof(const Gadget *G) {2229    return G->getKind() == Kind::UPCStandalonePointer;2230  }2231 2232  static bool matches(const Stmt *S,2233                      llvm::SmallVectorImpl<MatchResult> &Results) {2234    size_t SizeBefore = Results.size();2235    findStmtsInUnspecifiedPointerContext(S, [&Results](const Stmt *S) {2236      auto *E = dyn_cast<Expr>(S);2237      if (!E)2238        return;2239      const auto *DRE = dyn_cast<DeclRefExpr>(E->IgnoreParenImpCasts());2240      if (!DRE || (!hasPointerType(*DRE) && !hasArrayType(*DRE)) ||2241          !isSupportedVariable(*DRE))2242        return;2243      MatchResult R;2244      R.addNode(DeclRefExprTag, DynTypedNode::create(*DRE));2245      Results.emplace_back(std::move(R));2246    });2247    return SizeBefore != Results.size();2248  }2249 2250  virtual std::optional<FixItList>2251  getFixits(const FixitStrategy &S) const override;2252  SourceLocation getSourceLoc() const override { return Node->getBeginLoc(); }2253 2254  virtual DeclUseList getClaimedVarUseSites() const override { return {Node}; }2255};2256 2257class PointerDereferenceGadget : public FixableGadget {2258  static constexpr const char *const BaseDeclRefExprTag = "BaseDRE";2259  static constexpr const char *const OperatorTag = "op";2260 2261  const DeclRefExpr *BaseDeclRefExpr = nullptr;2262  const UnaryOperator *Op = nullptr;2263 2264public:2265  PointerDereferenceGadget(const MatchResult &Result)2266      : FixableGadget(Kind::PointerDereference),2267        BaseDeclRefExpr(Result.getNodeAs<DeclRefExpr>(BaseDeclRefExprTag)),2268        Op(Result.getNodeAs<UnaryOperator>(OperatorTag)) {}2269 2270  static bool classof(const Gadget *G) {2271    return G->getKind() == Kind::PointerDereference;2272  }2273 2274  static bool matches(const Stmt *S,2275                      llvm::SmallVectorImpl<MatchResult> &Results) {2276    size_t SizeBefore = Results.size();2277    findStmtsInUnspecifiedLvalueContext(S, [&Results](const Stmt *S) {2278      const auto *UO = dyn_cast<UnaryOperator>(S);2279      if (!UO || UO->getOpcode() != UO_Deref)2280        return;2281      const auto *CE = dyn_cast<Expr>(UO->getSubExpr());2282      if (!CE)2283        return;2284      CE = CE->IgnoreParenImpCasts();2285      const auto *DRE = dyn_cast<DeclRefExpr>(CE);2286      if (!DRE || !isSupportedVariable(*DRE))2287        return;2288      MatchResult R;2289      R.addNode(BaseDeclRefExprTag, DynTypedNode::create(*DRE));2290      R.addNode(OperatorTag, DynTypedNode::create(*UO));2291      Results.emplace_back(std::move(R));2292    });2293    return SizeBefore != Results.size();2294  }2295 2296  DeclUseList getClaimedVarUseSites() const override {2297    return {BaseDeclRefExpr};2298  }2299 2300  virtual std::optional<FixItList>2301  getFixits(const FixitStrategy &S) const override;2302  SourceLocation getSourceLoc() const override { return Op->getBeginLoc(); }2303};2304 2305// Represents expressions of the form `&DRE[any]` in the Unspecified Pointer2306// Context (see `findStmtsInUnspecifiedPointerContext`).2307// Note here `[]` is the built-in subscript operator.2308class UPCAddressofArraySubscriptGadget : public FixableGadget {2309private:2310  static constexpr const char *const UPCAddressofArraySubscriptTag =2311      "AddressofArraySubscriptUnderUPC";2312  const UnaryOperator *Node; // the `&DRE[any]` node2313 2314public:2315  UPCAddressofArraySubscriptGadget(const MatchResult &Result)2316      : FixableGadget(Kind::ULCArraySubscript),2317        Node(Result.getNodeAs<UnaryOperator>(UPCAddressofArraySubscriptTag)) {2318    assert(Node != nullptr && "Expecting a non-null matching result");2319  }2320 2321  static bool classof(const Gadget *G) {2322    return G->getKind() == Kind::UPCAddressofArraySubscript;2323  }2324 2325  static bool matches(const Stmt *S,2326                      llvm::SmallVectorImpl<MatchResult> &Results) {2327    size_t SizeBefore = Results.size();2328    findStmtsInUnspecifiedPointerContext(S, [&Results](const Stmt *S) {2329      auto *E = dyn_cast<Expr>(S);2330      if (!E)2331        return;2332      const auto *UO = dyn_cast<UnaryOperator>(E->IgnoreImpCasts());2333      if (!UO || UO->getOpcode() != UO_AddrOf)2334        return;2335      const auto *ASE = dyn_cast<ArraySubscriptExpr>(UO->getSubExpr());2336      if (!ASE)2337        return;2338      const auto *DRE =2339          dyn_cast<DeclRefExpr>(ASE->getBase()->IgnoreParenImpCasts());2340      if (!DRE || !isSupportedVariable(*DRE))2341        return;2342      MatchResult R;2343      R.addNode(UPCAddressofArraySubscriptTag, DynTypedNode::create(*UO));2344      Results.emplace_back(std::move(R));2345    });2346    return SizeBefore != Results.size();2347  }2348 2349  virtual std::optional<FixItList>2350  getFixits(const FixitStrategy &) const override;2351  SourceLocation getSourceLoc() const override { return Node->getBeginLoc(); }2352 2353  virtual DeclUseList getClaimedVarUseSites() const override {2354    const auto *ArraySubst = cast<ArraySubscriptExpr>(Node->getSubExpr());2355    const auto *DRE =2356        cast<DeclRefExpr>(ArraySubst->getBase()->IgnoreParenImpCasts());2357    return {DRE};2358  }2359};2360} // namespace2361 2362namespace {2363// An auxiliary tracking facility for the fixit analysis. It helps connect2364// declarations to its uses and make sure we've covered all uses with our2365// analysis before we try to fix the declaration.2366class DeclUseTracker {2367  using UseSetTy = llvm::SmallPtrSet<const DeclRefExpr *, 16>;2368  using DefMapTy = llvm::DenseMap<const VarDecl *, const DeclStmt *>;2369 2370  // Allocate on the heap for easier move.2371  std::unique_ptr<UseSetTy> Uses{std::make_unique<UseSetTy>()};2372  DefMapTy Defs{};2373 2374public:2375  DeclUseTracker() = default;2376  DeclUseTracker(const DeclUseTracker &) = delete; // Let's avoid copies.2377  DeclUseTracker &operator=(const DeclUseTracker &) = delete;2378  DeclUseTracker(DeclUseTracker &&) = default;2379  DeclUseTracker &operator=(DeclUseTracker &&) = default;2380 2381  // Start tracking a freshly discovered DRE.2382  void discoverUse(const DeclRefExpr *DRE) { Uses->insert(DRE); }2383 2384  // Stop tracking the DRE as it's been fully figured out.2385  void claimUse(const DeclRefExpr *DRE) {2386    assert(Uses->count(DRE) &&2387           "DRE not found or claimed by multiple matchers!");2388    Uses->erase(DRE);2389  }2390 2391  // A variable is unclaimed if at least one use is unclaimed.2392  bool hasUnclaimedUses(const VarDecl *VD) const {2393    // FIXME: Can this be less linear? Maybe maintain a map from VDs to DREs?2394    return any_of(*Uses, [VD](const DeclRefExpr *DRE) {2395      return DRE->getDecl()->getCanonicalDecl() == VD->getCanonicalDecl();2396    });2397  }2398 2399  UseSetTy getUnclaimedUses(const VarDecl *VD) const {2400    UseSetTy ReturnSet;2401    for (auto use : *Uses) {2402      if (use->getDecl()->getCanonicalDecl() == VD->getCanonicalDecl()) {2403        ReturnSet.insert(use);2404      }2405    }2406    return ReturnSet;2407  }2408 2409  void discoverDecl(const DeclStmt *DS) {2410    for (const Decl *D : DS->decls()) {2411      if (const auto *VD = dyn_cast<VarDecl>(D)) {2412        // FIXME: Assertion temporarily disabled due to a bug in2413        // ASTMatcher internal behavior in presence of GNU2414        // statement-expressions. We need to properly investigate this2415        // because it can screw up our algorithm in other ways.2416        // assert(Defs.count(VD) == 0 && "Definition already discovered!");2417        Defs[VD] = DS;2418      }2419    }2420  }2421 2422  const DeclStmt *lookupDecl(const VarDecl *VD) const {2423    return Defs.lookup(VD);2424  }2425};2426} // namespace2427 2428// Representing a pointer type expression of the form `++Ptr` in an Unspecified2429// Pointer Context (UPC):2430class UPCPreIncrementGadget : public FixableGadget {2431private:2432  static constexpr const char *const UPCPreIncrementTag =2433      "PointerPreIncrementUnderUPC";2434  const UnaryOperator *Node; // the `++Ptr` node2435 2436public:2437  UPCPreIncrementGadget(const MatchResult &Result)2438      : FixableGadget(Kind::UPCPreIncrement),2439        Node(Result.getNodeAs<UnaryOperator>(UPCPreIncrementTag)) {2440    assert(Node != nullptr && "Expecting a non-null matching result");2441  }2442 2443  static bool classof(const Gadget *G) {2444    return G->getKind() == Kind::UPCPreIncrement;2445  }2446 2447  static bool matches(const Stmt *S,2448                      llvm::SmallVectorImpl<MatchResult> &Results) {2449    // Note here we match `++Ptr` for any expression `Ptr` of pointer type.2450    // Although currently we can only provide fix-its when `Ptr` is a DRE, we2451    // can have the matcher be general, so long as `getClaimedVarUseSites` does2452    // things right.2453    size_t SizeBefore = Results.size();2454    findStmtsInUnspecifiedPointerContext(S, [&Results](const Stmt *S) {2455      auto *E = dyn_cast<Expr>(S);2456      if (!E)2457        return;2458      const auto *UO = dyn_cast<UnaryOperator>(E->IgnoreImpCasts());2459      if (!UO || UO->getOpcode() != UO_PreInc)2460        return;2461      const auto *DRE = dyn_cast<DeclRefExpr>(UO->getSubExpr());2462      if (!DRE || !isSupportedVariable(*DRE))2463        return;2464      MatchResult R;2465      R.addNode(UPCPreIncrementTag, DynTypedNode::create(*UO));2466      Results.emplace_back(std::move(R));2467    });2468    return SizeBefore != Results.size();2469  }2470 2471  virtual std::optional<FixItList>2472  getFixits(const FixitStrategy &S) const override;2473  SourceLocation getSourceLoc() const override { return Node->getBeginLoc(); }2474 2475  virtual DeclUseList getClaimedVarUseSites() const override {2476    return {dyn_cast<DeclRefExpr>(Node->getSubExpr())};2477  }2478};2479 2480// Representing a pointer type expression of the form `Ptr += n` in an2481// Unspecified Untyped Context (UUC):2482class UUCAddAssignGadget : public FixableGadget {2483private:2484  static constexpr const char *const UUCAddAssignTag =2485      "PointerAddAssignUnderUUC";2486  static constexpr const char *const OffsetTag = "Offset";2487 2488  const BinaryOperator *Node; // the `Ptr += n` node2489  const Expr *Offset = nullptr;2490 2491public:2492  UUCAddAssignGadget(const MatchResult &Result)2493      : FixableGadget(Kind::UUCAddAssign),2494        Node(Result.getNodeAs<BinaryOperator>(UUCAddAssignTag)),2495        Offset(Result.getNodeAs<Expr>(OffsetTag)) {2496    assert(Node != nullptr && "Expecting a non-null matching result");2497  }2498 2499  static bool classof(const Gadget *G) {2500    return G->getKind() == Kind::UUCAddAssign;2501  }2502 2503  static bool matches(const Stmt *S,2504                      llvm::SmallVectorImpl<MatchResult> &Results) {2505    size_t SizeBefore = Results.size();2506    findStmtsInUnspecifiedUntypedContext(S, [&Results](const Stmt *S) {2507      const auto *E = dyn_cast<Expr>(S);2508      if (!E)2509        return;2510      const auto *BO = dyn_cast<BinaryOperator>(E->IgnoreImpCasts());2511      if (!BO || BO->getOpcode() != BO_AddAssign)2512        return;2513      const auto *DRE = dyn_cast<DeclRefExpr>(BO->getLHS());2514      if (!DRE || !hasPointerType(*DRE) || !isSupportedVariable(*DRE))2515        return;2516      MatchResult R;2517      R.addNode(UUCAddAssignTag, DynTypedNode::create(*BO));2518      R.addNode(OffsetTag, DynTypedNode::create(*BO->getRHS()));2519      Results.emplace_back(std::move(R));2520    });2521    return SizeBefore != Results.size();2522  }2523 2524  virtual std::optional<FixItList>2525  getFixits(const FixitStrategy &S) const override;2526  SourceLocation getSourceLoc() const override { return Node->getBeginLoc(); }2527 2528  virtual DeclUseList getClaimedVarUseSites() const override {2529    return {dyn_cast<DeclRefExpr>(Node->getLHS())};2530  }2531};2532 2533// Representing a fixable expression of the form `*(ptr + 123)` or `*(123 +2534// ptr)`:2535class DerefSimplePtrArithFixableGadget : public FixableGadget {2536  static constexpr const char *const BaseDeclRefExprTag = "BaseDRE";2537  static constexpr const char *const DerefOpTag = "DerefOp";2538  static constexpr const char *const AddOpTag = "AddOp";2539  static constexpr const char *const OffsetTag = "Offset";2540 2541  const DeclRefExpr *BaseDeclRefExpr = nullptr;2542  const UnaryOperator *DerefOp = nullptr;2543  const BinaryOperator *AddOp = nullptr;2544  const IntegerLiteral *Offset = nullptr;2545 2546public:2547  DerefSimplePtrArithFixableGadget(const MatchResult &Result)2548      : FixableGadget(Kind::DerefSimplePtrArithFixable),2549        BaseDeclRefExpr(Result.getNodeAs<DeclRefExpr>(BaseDeclRefExprTag)),2550        DerefOp(Result.getNodeAs<UnaryOperator>(DerefOpTag)),2551        AddOp(Result.getNodeAs<BinaryOperator>(AddOpTag)),2552        Offset(Result.getNodeAs<IntegerLiteral>(OffsetTag)) {}2553 2554  static bool matches(const Stmt *S,2555                      llvm::SmallVectorImpl<MatchResult> &Results) {2556    auto IsPtr = [](const Expr *E, MatchResult &R) {2557      if (!E || !hasPointerType(*E))2558        return false;2559      const auto *DRE = dyn_cast<DeclRefExpr>(E->IgnoreImpCasts());2560      if (!DRE || !isSupportedVariable(*DRE))2561        return false;2562      R.addNode(BaseDeclRefExprTag, DynTypedNode::create(*DRE));2563      return true;2564    };2565    const auto IsPlusOverPtrAndInteger = [&IsPtr](const Expr *E,2566                                                  MatchResult &R) {2567      const auto *BO = dyn_cast<BinaryOperator>(E);2568      if (!BO || BO->getOpcode() != BO_Add)2569        return false;2570 2571      const auto *LHS = BO->getLHS();2572      const auto *RHS = BO->getRHS();2573      if (isa<IntegerLiteral>(RHS) && IsPtr(LHS, R)) {2574        R.addNode(OffsetTag, DynTypedNode::create(*RHS));2575        R.addNode(AddOpTag, DynTypedNode::create(*BO));2576        return true;2577      }2578      if (isa<IntegerLiteral>(LHS) && IsPtr(RHS, R)) {2579        R.addNode(OffsetTag, DynTypedNode::create(*LHS));2580        R.addNode(AddOpTag, DynTypedNode::create(*BO));2581        return true;2582      }2583      return false;2584    };2585    size_t SizeBefore = Results.size();2586    const auto InnerMatcher = [&IsPlusOverPtrAndInteger,2587                               &Results](const Expr *E) {2588      const auto *UO = dyn_cast<UnaryOperator>(E);2589      if (!UO || UO->getOpcode() != UO_Deref)2590        return;2591 2592      const auto *Operand = UO->getSubExpr()->IgnoreParens();2593      MatchResult R;2594      if (IsPlusOverPtrAndInteger(Operand, R)) {2595        R.addNode(DerefOpTag, DynTypedNode::create(*UO));2596        Results.emplace_back(std::move(R));2597      }2598    };2599    findStmtsInUnspecifiedLvalueContext(S, InnerMatcher);2600    return SizeBefore != Results.size();2601  }2602 2603  virtual std::optional<FixItList>2604  getFixits(const FixitStrategy &s) const final;2605  SourceLocation getSourceLoc() const override {2606    return DerefOp->getBeginLoc();2607  }2608 2609  virtual DeclUseList getClaimedVarUseSites() const final {2610    return {BaseDeclRefExpr};2611  }2612};2613 2614class WarningGadgetMatcher : public FastMatcher {2615 2616public:2617  WarningGadgetMatcher(WarningGadgetList &WarningGadgets)2618      : WarningGadgets(WarningGadgets) {}2619 2620  bool matches(const DynTypedNode &DynNode, ASTContext &Ctx,2621               const UnsafeBufferUsageHandler &Handler) override {2622    const Stmt *S = DynNode.get<Stmt>();2623    if (!S)2624      return false;2625 2626    MatchResult Result;2627#define WARNING_GADGET(name)                                                   \2628  if (name##Gadget::matches(S, Ctx, Result) &&                                 \2629      notInSafeBufferOptOut(*S, &Handler)) {                                   \2630    WarningGadgets.push_back(std::make_unique<name##Gadget>(Result));          \2631    return true;                                                               \2632  }2633#define WARNING_OPTIONAL_GADGET(name)                                          \2634  if (name##Gadget::matches(S, Ctx, &Handler, Result) &&                       \2635      notInSafeBufferOptOut(*S, &Handler)) {                                   \2636    WarningGadgets.push_back(std::make_unique<name##Gadget>(Result));          \2637    return true;                                                               \2638  }2639#include "clang/Analysis/Analyses/UnsafeBufferUsageGadgets.def"2640    return false;2641  }2642 2643private:2644  WarningGadgetList &WarningGadgets;2645};2646 2647class FixableGadgetMatcher : public FastMatcher {2648 2649public:2650  FixableGadgetMatcher(FixableGadgetList &FixableGadgets,2651                       DeclUseTracker &Tracker)2652      : FixableGadgets(FixableGadgets), Tracker(Tracker) {}2653 2654  bool matches(const DynTypedNode &DynNode, ASTContext &Ctx,2655               const UnsafeBufferUsageHandler &Handler) override {2656    bool matchFound = false;2657    const Stmt *S = DynNode.get<Stmt>();2658    if (!S) {2659      return matchFound;2660    }2661 2662    llvm::SmallVector<MatchResult> Results;2663#define FIXABLE_GADGET(name)                                                   \2664  if (name##Gadget::matches(S, Results)) {                                     \2665    for (const auto &R : Results) {                                            \2666      FixableGadgets.push_back(std::make_unique<name##Gadget>(R));             \2667      matchFound = true;                                                       \2668    }                                                                          \2669    Results = {};                                                              \2670  }2671#include "clang/Analysis/Analyses/UnsafeBufferUsageGadgets.def"2672    // In parallel, match all DeclRefExprs so that to find out2673    // whether there are any uncovered by gadgets.2674    if (auto *DRE = findDeclRefExpr(S); DRE) {2675      Tracker.discoverUse(DRE);2676      matchFound = true;2677    }2678    // Also match DeclStmts because we'll need them when fixing2679    // their underlying VarDecls that otherwise don't have2680    // any backreferences to DeclStmts.2681    if (auto *DS = findDeclStmt(S); DS) {2682      Tracker.discoverDecl(DS);2683      matchFound = true;2684    }2685    return matchFound;2686  }2687 2688private:2689  const DeclRefExpr *findDeclRefExpr(const Stmt *S) {2690    const auto *DRE = dyn_cast<DeclRefExpr>(S);2691    if (!DRE || (!hasPointerType(*DRE) && !hasArrayType(*DRE)))2692      return nullptr;2693    const Decl *D = DRE->getDecl();2694    if (!D || (!isa<VarDecl>(D) && !isa<BindingDecl>(D)))2695      return nullptr;2696    return DRE;2697  }2698  const DeclStmt *findDeclStmt(const Stmt *S) {2699    const auto *DS = dyn_cast<DeclStmt>(S);2700    if (!DS)2701      return nullptr;2702    return DS;2703  }2704  FixableGadgetList &FixableGadgets;2705  DeclUseTracker &Tracker;2706};2707 2708// Scan the function and return a list of gadgets found with provided kits.2709static void findGadgets(const Stmt *S, ASTContext &Ctx,2710                        const UnsafeBufferUsageHandler &Handler,2711                        bool EmitSuggestions, FixableGadgetList &FixableGadgets,2712                        WarningGadgetList &WarningGadgets,2713                        DeclUseTracker &Tracker) {2714  WarningGadgetMatcher WMatcher{WarningGadgets};2715  forEachDescendantEvaluatedStmt(S, Ctx, Handler, WMatcher);2716  if (EmitSuggestions) {2717    FixableGadgetMatcher FMatcher{FixableGadgets, Tracker};2718    forEachDescendantStmt(S, Ctx, Handler, FMatcher);2719  }2720}2721 2722// Compares AST nodes by source locations.2723template <typename NodeTy> struct CompareNode {2724  bool operator()(const NodeTy *N1, const NodeTy *N2) const {2725    return N1->getBeginLoc().getRawEncoding() <2726           N2->getBeginLoc().getRawEncoding();2727  }2728};2729 2730std::set<const Expr *> clang::findUnsafePointers(const FunctionDecl *FD) {2731  class MockReporter : public UnsafeBufferUsageHandler {2732  public:2733    MockReporter() {}2734    void handleUnsafeOperation(const Stmt *, bool, ASTContext &) override {}2735    void handleUnsafeLibcCall(const CallExpr *, unsigned, ASTContext &,2736                              const Expr *UnsafeArg = nullptr) override {}2737    void handleUnsafeOperationInContainer(const Stmt *, bool,2738                                          ASTContext &) override {}2739    void handleUnsafeVariableGroup(const VarDecl *,2740                                   const VariableGroupsManager &, FixItList &&,2741                                   const Decl *,2742                                   const FixitStrategy &) override {}2743    void handleUnsafeUniquePtrArrayAccess(const DynTypedNode &Node,2744                                          bool IsRelatedToDecl,2745                                          ASTContext &Ctx) override {}2746    bool ignoreUnsafeBufferInContainer(const SourceLocation &) const override {2747      return false;2748    }2749    bool isSafeBufferOptOut(const SourceLocation &) const override {2750      return false;2751    }2752    bool ignoreUnsafeBufferInLibcCall(const SourceLocation &) const override {2753      return false;2754    }2755    std::string getUnsafeBufferUsageAttributeTextAt(2756        SourceLocation, StringRef WSSuffix = "") const override {2757      return "";2758    }2759  };2760 2761  FixableGadgetList FixableGadgets;2762  WarningGadgetList WarningGadgets;2763  DeclUseTracker Tracker;2764  MockReporter IgnoreHandler;2765 2766  findGadgets(FD->getBody(), FD->getASTContext(), IgnoreHandler, false,2767              FixableGadgets, WarningGadgets, Tracker);2768 2769  std::set<const Expr *> Result;2770  for (auto &G : WarningGadgets) {2771    for (const Expr *E : G->getUnsafePtrs()) {2772      Result.insert(E);2773    }2774  }2775 2776  return Result;2777}2778 2779struct WarningGadgetSets {2780  std::map<const VarDecl *, std::set<const WarningGadget *>,2781           // To keep keys sorted by their locations in the map so that the2782           // order is deterministic:2783           CompareNode<VarDecl>>2784      byVar;2785  // These Gadgets are not related to pointer variables (e. g. temporaries).2786  llvm::SmallVector<const WarningGadget *, 16> noVar;2787};2788 2789static WarningGadgetSets2790groupWarningGadgetsByVar(const WarningGadgetList &AllUnsafeOperations) {2791  WarningGadgetSets result;2792  // If some gadgets cover more than one2793  // variable, they'll appear more than once in the map.2794  for (auto &G : AllUnsafeOperations) {2795    DeclUseList ClaimedVarUseSites = G->getClaimedVarUseSites();2796 2797    bool AssociatedWithVarDecl = false;2798    for (const DeclRefExpr *DRE : ClaimedVarUseSites) {2799      if (const auto *VD = dyn_cast<VarDecl>(DRE->getDecl())) {2800        result.byVar[VD].insert(G.get());2801        AssociatedWithVarDecl = true;2802      }2803    }2804 2805    if (!AssociatedWithVarDecl) {2806      result.noVar.push_back(G.get());2807      continue;2808    }2809  }2810  return result;2811}2812 2813struct FixableGadgetSets {2814  std::map<const VarDecl *, std::set<const FixableGadget *>,2815           // To keep keys sorted by their locations in the map so that the2816           // order is deterministic:2817           CompareNode<VarDecl>>2818      byVar;2819};2820 2821static FixableGadgetSets2822groupFixablesByVar(FixableGadgetList &&AllFixableOperations) {2823  FixableGadgetSets FixablesForUnsafeVars;2824  for (auto &F : AllFixableOperations) {2825    DeclUseList DREs = F->getClaimedVarUseSites();2826 2827    for (const DeclRefExpr *DRE : DREs) {2828      if (const auto *VD = dyn_cast<VarDecl>(DRE->getDecl())) {2829        FixablesForUnsafeVars.byVar[VD].insert(F.get());2830      }2831    }2832  }2833  return FixablesForUnsafeVars;2834}2835 2836bool clang::internal::anyConflict(const SmallVectorImpl<FixItHint> &FixIts,2837                                  const SourceManager &SM) {2838  // A simple interval overlap detection algorithm.  Sorts all ranges by their2839  // begin location then finds the first overlap in one pass.2840  std::vector<const FixItHint *> All; // a copy of `FixIts`2841 2842  for (const FixItHint &H : FixIts)2843    All.push_back(&H);2844  std::sort(All.begin(), All.end(),2845            [&SM](const FixItHint *H1, const FixItHint *H2) {2846              return SM.isBeforeInTranslationUnit(H1->RemoveRange.getBegin(),2847                                                  H2->RemoveRange.getBegin());2848            });2849 2850  const FixItHint *CurrHint = nullptr;2851 2852  for (const FixItHint *Hint : All) {2853    if (!CurrHint ||2854        SM.isBeforeInTranslationUnit(CurrHint->RemoveRange.getEnd(),2855                                     Hint->RemoveRange.getBegin())) {2856      // Either to initialize `CurrHint` or `CurrHint` does not2857      // overlap with `Hint`:2858      CurrHint = Hint;2859    } else2860      // In case `Hint` overlaps the `CurrHint`, we found at least one2861      // conflict:2862      return true;2863  }2864  return false;2865}2866 2867std::optional<FixItList>2868PtrToPtrAssignmentGadget::getFixits(const FixitStrategy &S) const {2869  const auto *LeftVD = cast<VarDecl>(PtrLHS->getDecl());2870  const auto *RightVD = cast<VarDecl>(PtrRHS->getDecl());2871  switch (S.lookup(LeftVD)) {2872  case FixitStrategy::Kind::Span:2873    if (S.lookup(RightVD) == FixitStrategy::Kind::Span)2874      return FixItList{};2875    return std::nullopt;2876  case FixitStrategy::Kind::Wontfix:2877    return std::nullopt;2878  case FixitStrategy::Kind::Iterator:2879  case FixitStrategy::Kind::Array:2880    return std::nullopt;2881  case FixitStrategy::Kind::Vector:2882    llvm_unreachable("unsupported strategies for FixableGadgets");2883  }2884  return std::nullopt;2885}2886 2887/// \returns fixit that adds .data() call after \DRE.2888static inline std::optional<FixItList> createDataFixit(const ASTContext &Ctx,2889                                                       const DeclRefExpr *DRE);2890 2891std::optional<FixItList>2892CArrayToPtrAssignmentGadget::getFixits(const FixitStrategy &S) const {2893  const auto *LeftVD = cast<VarDecl>(PtrLHS->getDecl());2894  const auto *RightVD = cast<VarDecl>(PtrRHS->getDecl());2895  // TLDR: Implementing fixits for non-Wontfix strategy on both LHS and RHS is2896  // non-trivial.2897  //2898  // CArrayToPtrAssignmentGadget doesn't have strategy implications because2899  // constant size array propagates its bounds. Because of that LHS and RHS are2900  // addressed by two different fixits.2901  //2902  // At the same time FixitStrategy S doesn't reflect what group a fixit belongs2903  // to and can't be generally relied on in multi-variable Fixables!2904  //2905  // E. g. If an instance of this gadget is fixing variable on LHS then the2906  // variable on RHS is fixed by a different fixit and its strategy for LHS2907  // fixit is as if Wontfix.2908  //2909  // The only exception is Wontfix strategy for a given variable as that is2910  // valid for any fixit produced for the given input source code.2911  if (S.lookup(LeftVD) == FixitStrategy::Kind::Span) {2912    if (S.lookup(RightVD) == FixitStrategy::Kind::Wontfix) {2913      return FixItList{};2914    }2915  } else if (S.lookup(LeftVD) == FixitStrategy::Kind::Wontfix) {2916    if (S.lookup(RightVD) == FixitStrategy::Kind::Array) {2917      return createDataFixit(RightVD->getASTContext(), PtrRHS);2918    }2919  }2920  return std::nullopt;2921}2922 2923std::optional<FixItList>2924PointerInitGadget::getFixits(const FixitStrategy &S) const {2925  const auto *LeftVD = PtrInitLHS;2926  const auto *RightVD = cast<VarDecl>(PtrInitRHS->getDecl());2927  switch (S.lookup(LeftVD)) {2928  case FixitStrategy::Kind::Span:2929    if (S.lookup(RightVD) == FixitStrategy::Kind::Span)2930      return FixItList{};2931    return std::nullopt;2932  case FixitStrategy::Kind::Wontfix:2933    return std::nullopt;2934  case FixitStrategy::Kind::Iterator:2935  case FixitStrategy::Kind::Array:2936    return std::nullopt;2937  case FixitStrategy::Kind::Vector:2938    llvm_unreachable("unsupported strategies for FixableGadgets");2939  }2940  return std::nullopt;2941}2942 2943static bool isNonNegativeIntegerExpr(const Expr *Expr, const VarDecl *VD,2944                                     const ASTContext &Ctx) {2945  if (auto ConstVal = Expr->getIntegerConstantExpr(Ctx)) {2946    if (ConstVal->isNegative())2947      return false;2948  } else if (!Expr->getType()->isUnsignedIntegerType())2949    return false;2950  return true;2951}2952 2953std::optional<FixItList>2954ULCArraySubscriptGadget::getFixits(const FixitStrategy &S) const {2955  if (const auto *DRE =2956          dyn_cast<DeclRefExpr>(Node->getBase()->IgnoreImpCasts()))2957    if (const auto *VD = dyn_cast<VarDecl>(DRE->getDecl())) {2958      switch (S.lookup(VD)) {2959      case FixitStrategy::Kind::Span: {2960 2961        // If the index has a negative constant value, we give up as no valid2962        // fix-it can be generated:2963        const ASTContext &Ctx = // FIXME: we need ASTContext to be passed in!2964            VD->getASTContext();2965        if (!isNonNegativeIntegerExpr(Node->getIdx(), VD, Ctx))2966          return std::nullopt;2967        // no-op is a good fix-it, otherwise2968        return FixItList{};2969      }2970      case FixitStrategy::Kind::Array:2971        return FixItList{};2972      case FixitStrategy::Kind::Wontfix:2973      case FixitStrategy::Kind::Iterator:2974      case FixitStrategy::Kind::Vector:2975        llvm_unreachable("unsupported strategies for FixableGadgets");2976      }2977    }2978  return std::nullopt;2979}2980 2981static std::optional<FixItList> // forward declaration2982fixUPCAddressofArraySubscriptWithSpan(const UnaryOperator *Node);2983 2984std::optional<FixItList>2985UPCAddressofArraySubscriptGadget::getFixits(const FixitStrategy &S) const {2986  auto DREs = getClaimedVarUseSites();2987  const auto *VD = cast<VarDecl>(DREs.front()->getDecl());2988 2989  switch (S.lookup(VD)) {2990  case FixitStrategy::Kind::Span:2991    return fixUPCAddressofArraySubscriptWithSpan(Node);2992  case FixitStrategy::Kind::Wontfix:2993  case FixitStrategy::Kind::Iterator:2994  case FixitStrategy::Kind::Array:2995    return std::nullopt;2996  case FixitStrategy::Kind::Vector:2997    llvm_unreachable("unsupported strategies for FixableGadgets");2998  }2999  return std::nullopt; // something went wrong, no fix-it3000}3001 3002// FIXME: this function should be customizable through format3003static StringRef getEndOfLine() {3004  static const char *const EOL = "\n";3005  return EOL;3006}3007 3008// Returns the text indicating that the user needs to provide input there:3009static std::string3010getUserFillPlaceHolder(StringRef HintTextToUser = "placeholder") {3011  std::string s = std::string("<# ");3012  s += HintTextToUser;3013  s += " #>";3014  return s;3015}3016 3017// Return the source location of the last character of the AST `Node`.3018template <typename NodeTy>3019static std::optional<SourceLocation>3020getEndCharLoc(const NodeTy *Node, const SourceManager &SM,3021              const LangOptions &LangOpts) {3022  if (unsigned TkLen =3023          Lexer::MeasureTokenLength(Node->getEndLoc(), SM, LangOpts)) {3024    SourceLocation Loc = Node->getEndLoc().getLocWithOffset(TkLen - 1);3025 3026    if (Loc.isValid())3027      return Loc;3028  }3029  return std::nullopt;3030}3031 3032// We cannot fix a variable declaration if it has some other specifiers than the3033// type specifier.  Because the source ranges of those specifiers could overlap3034// with the source range that is being replaced using fix-its.  Especially when3035// we often cannot obtain accurate source ranges of cv-qualified type3036// specifiers.3037// FIXME: also deal with type attributes3038static bool hasUnsupportedSpecifiers(const VarDecl *VD,3039                                     const SourceManager &SM) {3040  // AttrRangeOverlapping: true if at least one attribute of `VD` overlaps the3041  // source range of `VD`:3042  bool AttrRangeOverlapping = llvm::any_of(VD->attrs(), [&](Attr *At) -> bool {3043    return !(SM.isBeforeInTranslationUnit(At->getRange().getEnd(),3044                                          VD->getBeginLoc())) &&3045           !(SM.isBeforeInTranslationUnit(VD->getEndLoc(),3046                                          At->getRange().getBegin()));3047  });3048  return VD->isInlineSpecified() || VD->isConstexpr() ||3049         VD->hasConstantInitialization() || !VD->hasLocalStorage() ||3050         AttrRangeOverlapping;3051}3052 3053// Returns the `SourceRange` of `D`.  The reason why this function exists is3054// that `D->getSourceRange()` may return a range where the end location is the3055// starting location of the last token.  The end location of the source range3056// returned by this function is the last location of the last token.3057static SourceRange getSourceRangeToTokenEnd(const Decl *D,3058                                            const SourceManager &SM,3059                                            const LangOptions &LangOpts) {3060  SourceLocation Begin = D->getBeginLoc();3061  SourceLocation3062      End = // `D->getEndLoc` should always return the starting location of the3063      // last token, so we should get the end of the token3064      Lexer::getLocForEndOfToken(D->getEndLoc(), 0, SM, LangOpts);3065 3066  return SourceRange(Begin, End);3067}3068 3069// Returns the text of the name (with qualifiers) of a `FunctionDecl`.3070static std::optional<StringRef> getFunNameText(const FunctionDecl *FD,3071                                               const SourceManager &SM,3072                                               const LangOptions &LangOpts) {3073  SourceLocation BeginLoc = FD->getQualifier()3074                                ? FD->getQualifierLoc().getBeginLoc()3075                                : FD->getNameInfo().getBeginLoc();3076  // Note that `FD->getNameInfo().getEndLoc()` returns the begin location of the3077  // last token:3078  SourceLocation EndLoc = Lexer::getLocForEndOfToken(3079      FD->getNameInfo().getEndLoc(), 0, SM, LangOpts);3080  SourceRange NameRange{BeginLoc, EndLoc};3081 3082  return getRangeText(NameRange, SM, LangOpts);3083}3084 3085// Returns the text representing a `std::span` type where the element type is3086// represented by `EltTyText`.3087//3088// Note the optional parameter `Qualifiers`: one needs to pass qualifiers3089// explicitly if the element type needs to be qualified.3090static std::string3091getSpanTypeText(StringRef EltTyText,3092                std::optional<Qualifiers> Quals = std::nullopt) {3093  const char *const SpanOpen = "std::span<";3094 3095  if (Quals)3096    return SpanOpen + EltTyText.str() + ' ' + Quals->getAsString() + '>';3097  return SpanOpen + EltTyText.str() + '>';3098}3099 3100std::optional<FixItList>3101DerefSimplePtrArithFixableGadget::getFixits(const FixitStrategy &s) const {3102  const VarDecl *VD = dyn_cast<VarDecl>(BaseDeclRefExpr->getDecl());3103 3104  if (VD && s.lookup(VD) == FixitStrategy::Kind::Span) {3105    ASTContext &Ctx = VD->getASTContext();3106    // std::span can't represent elements before its begin()3107    if (auto ConstVal = Offset->getIntegerConstantExpr(Ctx))3108      if (ConstVal->isNegative())3109        return std::nullopt;3110 3111    // note that the expr may (oddly) has multiple layers of parens3112    // example:3113    //   *((..(pointer + 123)..))3114    // goal:3115    //   pointer[123]3116    // Fix-It:3117    //   remove '*('3118    //   replace ' + ' with '['3119    //   replace ')' with ']'3120 3121    // example:3122    //   *((..(123 + pointer)..))3123    // goal:3124    //   123[pointer]3125    // Fix-It:3126    //   remove '*('3127    //   replace ' + ' with '['3128    //   replace ')' with ']'3129 3130    const Expr *LHS = AddOp->getLHS(), *RHS = AddOp->getRHS();3131    const SourceManager &SM = Ctx.getSourceManager();3132    const LangOptions &LangOpts = Ctx.getLangOpts();3133    CharSourceRange StarWithTrailWhitespace =3134        clang::CharSourceRange::getCharRange(DerefOp->getOperatorLoc(),3135                                             LHS->getBeginLoc());3136 3137    std::optional<SourceLocation> LHSLocation = getPastLoc(LHS, SM, LangOpts);3138    if (!LHSLocation)3139      return std::nullopt;3140 3141    CharSourceRange PlusWithSurroundingWhitespace =3142        clang::CharSourceRange::getCharRange(*LHSLocation, RHS->getBeginLoc());3143 3144    std::optional<SourceLocation> AddOpLocation =3145        getPastLoc(AddOp, SM, LangOpts);3146    std::optional<SourceLocation> DerefOpLocation =3147        getPastLoc(DerefOp, SM, LangOpts);3148 3149    if (!AddOpLocation || !DerefOpLocation)3150      return std::nullopt;3151 3152    CharSourceRange ClosingParenWithPrecWhitespace =3153        clang::CharSourceRange::getCharRange(*AddOpLocation, *DerefOpLocation);3154 3155    return FixItList{3156        {FixItHint::CreateRemoval(StarWithTrailWhitespace),3157         FixItHint::CreateReplacement(PlusWithSurroundingWhitespace, "["),3158         FixItHint::CreateReplacement(ClosingParenWithPrecWhitespace, "]")}};3159  }3160  return std::nullopt; // something wrong or unsupported, give up3161}3162 3163std::optional<FixItList>3164PointerDereferenceGadget::getFixits(const FixitStrategy &S) const {3165  const VarDecl *VD = cast<VarDecl>(BaseDeclRefExpr->getDecl());3166  switch (S.lookup(VD)) {3167  case FixitStrategy::Kind::Span: {3168    ASTContext &Ctx = VD->getASTContext();3169    SourceManager &SM = Ctx.getSourceManager();3170    // Required changes: *(ptr); => (ptr[0]); and *ptr; => ptr[0]3171    // Deletes the *operand3172    CharSourceRange derefRange = clang::CharSourceRange::getCharRange(3173        Op->getBeginLoc(), Op->getBeginLoc().getLocWithOffset(1));3174    // Inserts the [0]3175    if (auto LocPastOperand =3176            getPastLoc(BaseDeclRefExpr, SM, Ctx.getLangOpts())) {3177      return FixItList{{FixItHint::CreateRemoval(derefRange),3178                        FixItHint::CreateInsertion(*LocPastOperand, "[0]")}};3179    }3180    break;3181  }3182  case FixitStrategy::Kind::Iterator:3183  case FixitStrategy::Kind::Array:3184    return std::nullopt;3185  case FixitStrategy::Kind::Vector:3186    llvm_unreachable("FixitStrategy not implemented yet!");3187  case FixitStrategy::Kind::Wontfix:3188    llvm_unreachable("Invalid strategy!");3189  }3190 3191  return std::nullopt;3192}3193 3194static inline std::optional<FixItList> createDataFixit(const ASTContext &Ctx,3195                                                       const DeclRefExpr *DRE) {3196  const SourceManager &SM = Ctx.getSourceManager();3197  // Inserts the .data() after the DRE3198  std::optional<SourceLocation> EndOfOperand =3199      getPastLoc(DRE, SM, Ctx.getLangOpts());3200 3201  if (EndOfOperand)3202    return FixItList{{FixItHint::CreateInsertion(*EndOfOperand, ".data()")}};3203 3204  return std::nullopt;3205}3206 3207// Generates fix-its replacing an expression of the form UPC(DRE) with3208// `DRE.data()`3209std::optional<FixItList>3210UPCStandalonePointerGadget::getFixits(const FixitStrategy &S) const {3211  const auto VD = cast<VarDecl>(Node->getDecl());3212  switch (S.lookup(VD)) {3213  case FixitStrategy::Kind::Array:3214  case FixitStrategy::Kind::Span: {3215    return createDataFixit(VD->getASTContext(), Node);3216    // FIXME: Points inside a macro expansion.3217    break;3218  }3219  case FixitStrategy::Kind::Wontfix:3220  case FixitStrategy::Kind::Iterator:3221    return std::nullopt;3222  case FixitStrategy::Kind::Vector:3223    llvm_unreachable("unsupported strategies for FixableGadgets");3224  }3225 3226  return std::nullopt;3227}3228 3229// Generates fix-its replacing an expression of the form `&DRE[e]` with3230// `&DRE.data()[e]`:3231static std::optional<FixItList>3232fixUPCAddressofArraySubscriptWithSpan(const UnaryOperator *Node) {3233  const auto *ArraySub = cast<ArraySubscriptExpr>(Node->getSubExpr());3234  const auto *DRE = cast<DeclRefExpr>(ArraySub->getBase()->IgnoreImpCasts());3235  // FIXME: this `getASTContext` call is costly, we should pass the3236  // ASTContext in:3237  const ASTContext &Ctx = DRE->getDecl()->getASTContext();3238  const Expr *Idx = ArraySub->getIdx();3239  const SourceManager &SM = Ctx.getSourceManager();3240  const LangOptions &LangOpts = Ctx.getLangOpts();3241  std::stringstream SS;3242  bool IdxIsLitZero = false;3243 3244  if (auto ICE = Idx->getIntegerConstantExpr(Ctx))3245    if ((*ICE).isZero())3246      IdxIsLitZero = true;3247  std::optional<StringRef> DreString = getExprText(DRE, SM, LangOpts);3248  if (!DreString)3249    return std::nullopt;3250 3251  if (IdxIsLitZero) {3252    // If the index is literal zero, we produce the most concise fix-it:3253    SS << (*DreString).str() << ".data()";3254  } else {3255    std::optional<StringRef> IndexString = getExprText(Idx, SM, LangOpts);3256    if (!IndexString)3257      return std::nullopt;3258 3259    SS << "&" << (*DreString).str() << ".data()"3260       << "[" << (*IndexString).str() << "]";3261  }3262  return FixItList{3263      FixItHint::CreateReplacement(Node->getSourceRange(), SS.str())};3264}3265 3266std::optional<FixItList>3267UUCAddAssignGadget::getFixits(const FixitStrategy &S) const {3268  DeclUseList DREs = getClaimedVarUseSites();3269 3270  if (DREs.size() != 1)3271    return std::nullopt; // In cases of `Ptr += n` where `Ptr` is not a DRE, we3272                         // give up3273  if (const VarDecl *VD = dyn_cast<VarDecl>(DREs.front()->getDecl())) {3274    if (S.lookup(VD) == FixitStrategy::Kind::Span) {3275      FixItList Fixes;3276 3277      const Stmt *AddAssignNode = Node;3278      StringRef varName = VD->getName();3279      const ASTContext &Ctx = VD->getASTContext();3280 3281      if (!isNonNegativeIntegerExpr(Offset, VD, Ctx))3282        return std::nullopt;3283 3284      // To transform UUC(p += n) to UUC(p = p.subspan(..)):3285      bool NotParenExpr =3286          (Offset->IgnoreParens()->getBeginLoc() == Offset->getBeginLoc());3287      std::string SS = varName.str() + " = " + varName.str() + ".subspan";3288      if (NotParenExpr)3289        SS += "(";3290 3291      std::optional<SourceLocation> AddAssignLocation = getEndCharLoc(3292          AddAssignNode, Ctx.getSourceManager(), Ctx.getLangOpts());3293      if (!AddAssignLocation)3294        return std::nullopt;3295 3296      Fixes.push_back(FixItHint::CreateReplacement(3297          SourceRange(AddAssignNode->getBeginLoc(), Node->getOperatorLoc()),3298          SS));3299      if (NotParenExpr)3300        Fixes.push_back(FixItHint::CreateInsertion(3301            Offset->getEndLoc().getLocWithOffset(1), ")"));3302      return Fixes;3303    }3304  }3305  return std::nullopt; // Not in the cases that we can handle for now, give up.3306}3307 3308std::optional<FixItList>3309UPCPreIncrementGadget::getFixits(const FixitStrategy &S) const {3310  DeclUseList DREs = getClaimedVarUseSites();3311 3312  if (DREs.size() != 1)3313    return std::nullopt; // In cases of `++Ptr` where `Ptr` is not a DRE, we3314                         // give up3315  if (const VarDecl *VD = dyn_cast<VarDecl>(DREs.front()->getDecl())) {3316    if (S.lookup(VD) == FixitStrategy::Kind::Span) {3317      FixItList Fixes;3318      std::stringstream SS;3319      StringRef varName = VD->getName();3320      const ASTContext &Ctx = VD->getASTContext();3321 3322      // To transform UPC(++p) to UPC((p = p.subspan(1)).data()):3323      SS << "(" << varName.data() << " = " << varName.data()3324         << ".subspan(1)).data()";3325      std::optional<SourceLocation> PreIncLocation =3326          getEndCharLoc(Node, Ctx.getSourceManager(), Ctx.getLangOpts());3327      if (!PreIncLocation)3328        return std::nullopt;3329 3330      Fixes.push_back(FixItHint::CreateReplacement(3331          SourceRange(Node->getBeginLoc(), *PreIncLocation), SS.str()));3332      return Fixes;3333    }3334  }3335  return std::nullopt; // Not in the cases that we can handle for now, give up.3336}3337 3338// For a non-null initializer `Init` of `T *` type, this function returns3339// `FixItHint`s producing a list initializer `{Init,  S}` as a part of a fix-it3340// to output stream.3341// In many cases, this function cannot figure out the actual extent `S`.  It3342// then will use a place holder to replace `S` to ask users to fill `S` in.  The3343// initializer shall be used to initialize a variable of type `std::span<T>`.3344// In some cases (e. g. constant size array) the initializer should remain3345// unchanged and the function returns empty list. In case the function can't3346// provide the right fixit it will return nullopt.3347//3348// FIXME: Support multi-level pointers3349//3350// Parameters:3351//   `Init` a pointer to the initializer expression3352//   `Ctx` a reference to the ASTContext3353static std::optional<FixItList>3354FixVarInitializerWithSpan(const Expr *Init, ASTContext &Ctx,3355                          const StringRef UserFillPlaceHolder) {3356  const SourceManager &SM = Ctx.getSourceManager();3357  const LangOptions &LangOpts = Ctx.getLangOpts();3358 3359  // If `Init` has a constant value that is (or equivalent to) a3360  // NULL pointer, we use the default constructor to initialize the span3361  // object, i.e., a `std:span` variable declaration with no initializer.3362  // So the fix-it is just to remove the initializer.3363  if (Init->isNullPointerConstant(3364          Ctx,3365          // FIXME: Why does this function not ask for `const ASTContext3366          // &`? It should. Maybe worth an NFC patch later.3367          Expr::NullPointerConstantValueDependence::3368              NPC_ValueDependentIsNotNull)) {3369    std::optional<SourceLocation> InitLocation =3370        getEndCharLoc(Init, SM, LangOpts);3371    if (!InitLocation)3372      return std::nullopt;3373 3374    SourceRange SR(Init->getBeginLoc(), *InitLocation);3375 3376    return FixItList{FixItHint::CreateRemoval(SR)};3377  }3378 3379  FixItList FixIts{};3380  std::string ExtentText = UserFillPlaceHolder.data();3381  StringRef One = "1";3382 3383  // Insert `{` before `Init`:3384  FixIts.push_back(FixItHint::CreateInsertion(Init->getBeginLoc(), "{"));3385  // Try to get the data extent. Break into different cases:3386  if (auto CxxNew = dyn_cast<CXXNewExpr>(Init->IgnoreImpCasts())) {3387    // In cases `Init` is `new T[n]` and there is no explicit cast over3388    // `Init`, we know that `Init` must evaluates to a pointer to `n` objects3389    // of `T`. So the extent is `n` unless `n` has side effects.  Similar but3390    // simpler for the case where `Init` is `new T`.3391    if (const Expr *Ext = CxxNew->getArraySize().value_or(nullptr)) {3392      if (!Ext->HasSideEffects(Ctx)) {3393        std::optional<StringRef> ExtentString = getExprText(Ext, SM, LangOpts);3394        if (!ExtentString)3395          return std::nullopt;3396        ExtentText = *ExtentString;3397      }3398    } else if (!CxxNew->isArray())3399      // Although the initializer is not allocating a buffer, the pointer3400      // variable could still be used in buffer access operations.3401      ExtentText = One;3402  } else if (Ctx.getAsConstantArrayType(Init->IgnoreImpCasts()->getType())) {3403    // std::span has a single parameter constructor for initialization with3404    // constant size array. The size is auto-deduced as the constructor is a3405    // function template. The correct fixit is empty - no changes should happen.3406    return FixItList{};3407  } else {3408    // In cases `Init` is of the form `&Var` after stripping of implicit3409    // casts, where `&` is the built-in operator, the extent is 1.3410    if (auto AddrOfExpr = dyn_cast<UnaryOperator>(Init->IgnoreImpCasts()))3411      if (AddrOfExpr->getOpcode() == UnaryOperatorKind::UO_AddrOf &&3412          isa_and_present<DeclRefExpr>(AddrOfExpr->getSubExpr()))3413        ExtentText = One;3414    // TODO: we can handle more cases, e.g., `&a[0]`, `&a`, `std::addressof`,3415    // and explicit casting, etc. etc.3416  }3417 3418  SmallString<32> StrBuffer{};3419  std::optional<SourceLocation> LocPassInit = getPastLoc(Init, SM, LangOpts);3420 3421  if (!LocPassInit)3422    return std::nullopt;3423 3424  StrBuffer.append(", ");3425  StrBuffer.append(ExtentText);3426  StrBuffer.append("}");3427  FixIts.push_back(FixItHint::CreateInsertion(*LocPassInit, StrBuffer.str()));3428  return FixIts;3429}3430 3431#ifndef NDEBUG3432#define DEBUG_NOTE_DECL_FAIL(D, Msg)                                           \3433  Handler.addDebugNoteForVar((D), (D)->getBeginLoc(),                          \3434                             "failed to produce fixit for declaration '" +     \3435                                 (D)->getNameAsString() + "'" + (Msg))3436#else3437#define DEBUG_NOTE_DECL_FAIL(D, Msg)3438#endif3439 3440// For the given variable declaration with a pointer-to-T type, returns the text3441// `std::span<T>`.  If it is unable to generate the text, returns3442// `std::nullopt`.3443static std::optional<std::string>3444createSpanTypeForVarDecl(const VarDecl *VD, const ASTContext &Ctx) {3445  assert(VD->getType()->isPointerType());3446 3447  std::optional<Qualifiers> PteTyQualifiers = std::nullopt;3448  std::optional<std::string> PteTyText = getPointeeTypeText(3449      VD, Ctx.getSourceManager(), Ctx.getLangOpts(), &PteTyQualifiers);3450 3451  if (!PteTyText)3452    return std::nullopt;3453 3454  std::string SpanTyText = "std::span<";3455 3456  SpanTyText.append(*PteTyText);3457  // Append qualifiers to span element type if any:3458  if (PteTyQualifiers) {3459    SpanTyText.append(" ");3460    SpanTyText.append(PteTyQualifiers->getAsString());3461  }3462  SpanTyText.append(">");3463  return SpanTyText;3464}3465 3466// For a `VarDecl` of the form `T  * var (= Init)?`, this3467// function generates fix-its that3468//  1) replace `T * var` with `std::span<T> var`; and3469//  2) change `Init` accordingly to a span constructor, if it exists.3470//3471// FIXME: support Multi-level pointers3472//3473// Parameters:3474//   `D` a pointer the variable declaration node3475//   `Ctx` a reference to the ASTContext3476//   `UserFillPlaceHolder` the user-input placeholder text3477// Returns:3478//    the non-empty fix-it list, if fix-its are successfuly generated; empty3479//    list otherwise.3480static FixItList fixLocalVarDeclWithSpan(const VarDecl *D, ASTContext &Ctx,3481                                         const StringRef UserFillPlaceHolder,3482                                         UnsafeBufferUsageHandler &Handler) {3483  if (hasUnsupportedSpecifiers(D, Ctx.getSourceManager()))3484    return {};3485 3486  FixItList FixIts{};3487  std::optional<std::string> SpanTyText = createSpanTypeForVarDecl(D, Ctx);3488 3489  if (!SpanTyText) {3490    DEBUG_NOTE_DECL_FAIL(D, " : failed to generate 'std::span' type");3491    return {};3492  }3493 3494  // Will hold the text for `std::span<T> Ident`:3495  std::stringstream SS;3496 3497  SS << *SpanTyText;3498  // Fix the initializer if it exists:3499  if (const Expr *Init = D->getInit()) {3500    std::optional<FixItList> InitFixIts =3501        FixVarInitializerWithSpan(Init, Ctx, UserFillPlaceHolder);3502    if (!InitFixIts)3503      return {};3504    FixIts.insert(FixIts.end(), std::make_move_iterator(InitFixIts->begin()),3505                  std::make_move_iterator(InitFixIts->end()));3506  }3507  // For declaration of the form `T * ident = init;`, we want to replace3508  // `T * ` with `std::span<T>`.3509  // We ignore CV-qualifiers so for `T * const ident;` we also want to replace3510  // just `T *` with `std::span<T>`.3511  const SourceLocation EndLocForReplacement = D->getTypeSpecEndLoc();3512  if (!EndLocForReplacement.isValid()) {3513    DEBUG_NOTE_DECL_FAIL(D, " : failed to locate the end of the declaration");3514    return {};3515  }3516  // The only exception is that for `T *ident` we'll add a single space between3517  // "std::span<T>" and "ident".3518  // FIXME: The condition is false for identifiers expended from macros.3519  if (EndLocForReplacement.getLocWithOffset(1) == getVarDeclIdentifierLoc(D))3520    SS << " ";3521 3522  FixIts.push_back(FixItHint::CreateReplacement(3523      SourceRange(D->getBeginLoc(), EndLocForReplacement), SS.str()));3524  return FixIts;3525}3526 3527static bool hasConflictingOverload(const FunctionDecl *FD) {3528  return !FD->getDeclContext()->lookup(FD->getDeclName()).isSingleResult();3529}3530 3531// For a `FunctionDecl`, whose `ParmVarDecl`s are being changed to have new3532// types, this function produces fix-its to make the change self-contained.  Let3533// 'F' be the entity defined by the original `FunctionDecl` and "NewF" be the3534// entity defined by the `FunctionDecl` after the change to the parameters.3535// Fix-its produced by this function are3536//   1. Add the `[[clang::unsafe_buffer_usage]]` attribute to each declaration3537//   of 'F';3538//   2. Create a declaration of "NewF" next to each declaration of `F`;3539//   3. Create a definition of "F" (as its' original definition is now belongs3540//      to "NewF") next to its original definition.  The body of the creating3541//      definition calls to "NewF".3542//3543// Example:3544//3545// void f(int *p);  // original declaration3546// void f(int *p) { // original definition3547//    p[5];3548// }3549//3550// To change the parameter `p` to be of `std::span<int>` type, we3551// also add overloads:3552//3553// [[clang::unsafe_buffer_usage]] void f(int *p); // original decl3554// void f(std::span<int> p);                      // added overload decl3555// void f(std::span<int> p) {     // original def where param is changed3556//    p[5];3557// }3558// [[clang::unsafe_buffer_usage]] void f(int *p) {  // added def3559//   return f(std::span(p, <# size #>));3560// }3561//3562static std::optional<FixItList>3563createOverloadsForFixedParams(const FixitStrategy &S, const FunctionDecl *FD,3564                              const ASTContext &Ctx,3565                              UnsafeBufferUsageHandler &Handler) {3566  // FIXME: need to make this conflict checking better:3567  if (hasConflictingOverload(FD))3568    return std::nullopt;3569 3570  const SourceManager &SM = Ctx.getSourceManager();3571  const LangOptions &LangOpts = Ctx.getLangOpts();3572  const unsigned NumParms = FD->getNumParams();3573  std::vector<std::string> NewTysTexts(NumParms);3574  std::vector<bool> ParmsMask(NumParms, false);3575  bool AtLeastOneParmToFix = false;3576 3577  for (unsigned i = 0; i < NumParms; i++) {3578    const ParmVarDecl *PVD = FD->getParamDecl(i);3579 3580    if (S.lookup(PVD) == FixitStrategy::Kind::Wontfix)3581      continue;3582    if (S.lookup(PVD) != FixitStrategy::Kind::Span)3583      // Not supported, not suppose to happen:3584      return std::nullopt;3585 3586    std::optional<Qualifiers> PteTyQuals = std::nullopt;3587    std::optional<std::string> PteTyText =3588        getPointeeTypeText(PVD, SM, LangOpts, &PteTyQuals);3589 3590    if (!PteTyText)3591      // something wrong in obtaining the text of the pointee type, give up3592      return std::nullopt;3593    // FIXME: whether we should create std::span type depends on the3594    // FixitStrategy.3595    NewTysTexts[i] = getSpanTypeText(*PteTyText, PteTyQuals);3596    ParmsMask[i] = true;3597    AtLeastOneParmToFix = true;3598  }3599  if (!AtLeastOneParmToFix)3600    // No need to create function overloads:3601    return {};3602  // FIXME Respect indentation of the original code.3603 3604  // A lambda that creates the text representation of a function declaration3605  // with the new type signatures:3606  const auto NewOverloadSignatureCreator =3607      [&SM, &LangOpts, &NewTysTexts,3608       &ParmsMask](const FunctionDecl *FD) -> std::optional<std::string> {3609    std::stringstream SS;3610 3611    SS << ";";3612    SS << getEndOfLine().str();3613    // Append: ret-type func-name "("3614    if (auto Prefix = getRangeText(3615            SourceRange(FD->getBeginLoc(), (*FD->param_begin())->getBeginLoc()),3616            SM, LangOpts))3617      SS << Prefix->str();3618    else3619      return std::nullopt; // give up3620    // Append: parameter-type-list3621    const unsigned NumParms = FD->getNumParams();3622 3623    for (unsigned i = 0; i < NumParms; i++) {3624      const ParmVarDecl *Parm = FD->getParamDecl(i);3625 3626      if (Parm->isImplicit())3627        continue;3628      if (ParmsMask[i]) {3629        // This `i`-th parameter will be fixed with `NewTysTexts[i]` being its3630        // new type:3631        SS << NewTysTexts[i];3632        // print parameter name if provided:3633        if (IdentifierInfo *II = Parm->getIdentifier())3634          SS << ' ' << II->getName().str();3635      } else if (auto ParmTypeText =3636                     getRangeText(getSourceRangeToTokenEnd(Parm, SM, LangOpts),3637                                  SM, LangOpts)) {3638        // print the whole `Parm` without modification:3639        SS << ParmTypeText->str();3640      } else3641        return std::nullopt; // something wrong, give up3642      if (i != NumParms - 1)3643        SS << ", ";3644    }3645    SS << ")";3646    return SS.str();3647  };3648 3649  // A lambda that creates the text representation of a function definition with3650  // the original signature:3651  const auto OldOverloadDefCreator =3652      [&Handler, &SM, &LangOpts, &NewTysTexts,3653       &ParmsMask](const FunctionDecl *FD) -> std::optional<std::string> {3654    std::stringstream SS;3655 3656    SS << getEndOfLine().str();3657    // Append: attr-name ret-type func-name "(" param-list ")" "{"3658    if (auto FDPrefix = getRangeText(3659            SourceRange(FD->getBeginLoc(), FD->getBody()->getBeginLoc()), SM,3660            LangOpts))3661      SS << Handler.getUnsafeBufferUsageAttributeTextAt(FD->getBeginLoc(), " ")3662         << FDPrefix->str() << "{";3663    else3664      return std::nullopt;3665    // Append: "return" func-name "("3666    if (auto FunQualName = getFunNameText(FD, SM, LangOpts))3667      SS << "return " << FunQualName->str() << "(";3668    else3669      return std::nullopt;3670 3671    // Append: arg-list3672    const unsigned NumParms = FD->getNumParams();3673    for (unsigned i = 0; i < NumParms; i++) {3674      const ParmVarDecl *Parm = FD->getParamDecl(i);3675 3676      if (Parm->isImplicit())3677        continue;3678      // FIXME: If a parameter has no name, it is unused in the3679      // definition. So we could just leave it as it is.3680      if (!Parm->getIdentifier())3681        // If a parameter of a function definition has no name:3682        return std::nullopt;3683      if (ParmsMask[i])3684        // This is our spanified paramter!3685        SS << NewTysTexts[i] << "(" << Parm->getIdentifier()->getName().str()3686           << ", " << getUserFillPlaceHolder("size") << ")";3687      else3688        SS << Parm->getIdentifier()->getName().str();3689      if (i != NumParms - 1)3690        SS << ", ";3691    }3692    // finish call and the body3693    SS << ");}" << getEndOfLine().str();3694    // FIXME: 80-char line formatting?3695    return SS.str();3696  };3697 3698  FixItList FixIts{};3699  for (FunctionDecl *FReDecl : FD->redecls()) {3700    std::optional<SourceLocation> Loc = getPastLoc(FReDecl, SM, LangOpts);3701 3702    if (!Loc)3703      return {};3704    if (FReDecl->isThisDeclarationADefinition()) {3705      assert(FReDecl == FD && "inconsistent function definition");3706      // Inserts a definition with the old signature to the end of3707      // `FReDecl`:3708      if (auto OldOverloadDef = OldOverloadDefCreator(FReDecl))3709        FixIts.emplace_back(FixItHint::CreateInsertion(*Loc, *OldOverloadDef));3710      else3711        return {}; // give up3712    } else {3713      // Adds the unsafe-buffer attribute (if not already there) to `FReDecl`:3714      if (!FReDecl->hasAttr<UnsafeBufferUsageAttr>()) {3715        FixIts.emplace_back(FixItHint::CreateInsertion(3716            FReDecl->getBeginLoc(), Handler.getUnsafeBufferUsageAttributeTextAt(3717                                        FReDecl->getBeginLoc(), " ")));3718      }3719      // Inserts a declaration with the new signature to the end of `FReDecl`:3720      if (auto NewOverloadDecl = NewOverloadSignatureCreator(FReDecl))3721        FixIts.emplace_back(FixItHint::CreateInsertion(*Loc, *NewOverloadDecl));3722      else3723        return {};3724    }3725  }3726  return FixIts;3727}3728 3729// To fix a `ParmVarDecl` to be of `std::span` type.3730static FixItList fixParamWithSpan(const ParmVarDecl *PVD, const ASTContext &Ctx,3731                                  UnsafeBufferUsageHandler &Handler) {3732  if (hasUnsupportedSpecifiers(PVD, Ctx.getSourceManager())) {3733    DEBUG_NOTE_DECL_FAIL(PVD, " : has unsupport specifier(s)");3734    return {};3735  }3736  if (PVD->hasDefaultArg()) {3737    // FIXME: generate fix-its for default values:3738    DEBUG_NOTE_DECL_FAIL(PVD, " : has default arg");3739    return {};3740  }3741 3742  std::optional<Qualifiers> PteTyQualifiers = std::nullopt;3743  std::optional<std::string> PteTyText = getPointeeTypeText(3744      PVD, Ctx.getSourceManager(), Ctx.getLangOpts(), &PteTyQualifiers);3745 3746  if (!PteTyText) {3747    DEBUG_NOTE_DECL_FAIL(PVD, " : invalid pointee type");3748    return {};3749  }3750 3751  std::optional<StringRef> PVDNameText = PVD->getIdentifier()->getName();3752 3753  if (!PVDNameText) {3754    DEBUG_NOTE_DECL_FAIL(PVD, " : invalid identifier name");3755    return {};3756  }3757 3758  std::stringstream SS;3759  std::optional<std::string> SpanTyText = createSpanTypeForVarDecl(PVD, Ctx);3760 3761  if (PteTyQualifiers)3762    // Append qualifiers if they exist:3763    SS << getSpanTypeText(*PteTyText, PteTyQualifiers);3764  else3765    SS << getSpanTypeText(*PteTyText);3766  // Append qualifiers to the type of the parameter:3767  if (PVD->getType().hasQualifiers())3768    SS << ' ' << PVD->getType().getQualifiers().getAsString();3769  // Append parameter's name:3770  SS << ' ' << PVDNameText->str();3771  // Add replacement fix-it:3772  return {FixItHint::CreateReplacement(PVD->getSourceRange(), SS.str())};3773}3774 3775static FixItList fixVariableWithSpan(const VarDecl *VD,3776                                     const DeclUseTracker &Tracker,3777                                     ASTContext &Ctx,3778                                     UnsafeBufferUsageHandler &Handler) {3779  const DeclStmt *DS = Tracker.lookupDecl(VD);3780  if (!DS) {3781    DEBUG_NOTE_DECL_FAIL(VD,3782                         " : variables declared this way not implemented yet");3783    return {};3784  }3785  if (!DS->isSingleDecl()) {3786    // FIXME: to support handling multiple `VarDecl`s in a single `DeclStmt`3787    DEBUG_NOTE_DECL_FAIL(VD, " : multiple VarDecls");3788    return {};3789  }3790  // Currently DS is an unused variable but we'll need it when3791  // non-single decls are implemented, where the pointee type name3792  // and the '*' are spread around the place.3793  (void)DS;3794 3795  // FIXME: handle cases where DS has multiple declarations3796  return fixLocalVarDeclWithSpan(VD, Ctx, getUserFillPlaceHolder(), Handler);3797}3798 3799static FixItList fixVarDeclWithArray(const VarDecl *D, const ASTContext &Ctx,3800                                     UnsafeBufferUsageHandler &Handler) {3801  FixItList FixIts{};3802 3803  // Note: the code below expects the declaration to not use any type sugar like3804  // typedef.3805  if (auto CAT = Ctx.getAsConstantArrayType(D->getType())) {3806    const QualType &ArrayEltT = CAT->getElementType();3807    assert(!ArrayEltT.isNull() && "Trying to fix a non-array type variable!");3808    // FIXME: support multi-dimensional arrays3809    if (isa<clang::ArrayType>(ArrayEltT.getCanonicalType()))3810      return {};3811 3812    const SourceLocation IdentifierLoc = getVarDeclIdentifierLoc(D);3813 3814    // Get the spelling of the element type as written in the source file3815    // (including macros, etc.).3816    auto MaybeElemTypeTxt =3817        getRangeText({D->getBeginLoc(), IdentifierLoc}, Ctx.getSourceManager(),3818                     Ctx.getLangOpts());3819    if (!MaybeElemTypeTxt)3820      return {};3821    const llvm::StringRef ElemTypeTxt = MaybeElemTypeTxt->trim();3822 3823    // Find the '[' token.3824    std::optional<Token> NextTok = Lexer::findNextToken(3825        IdentifierLoc, Ctx.getSourceManager(), Ctx.getLangOpts());3826    while (NextTok && !NextTok->is(tok::l_square) &&3827           NextTok->getLocation() <= D->getSourceRange().getEnd())3828      NextTok = Lexer::findNextToken(NextTok->getLocation(),3829                                     Ctx.getSourceManager(), Ctx.getLangOpts());3830    if (!NextTok)3831      return {};3832    const SourceLocation LSqBracketLoc = NextTok->getLocation();3833 3834    // Get the spelling of the array size as written in the source file3835    // (including macros, etc.).3836    auto MaybeArraySizeTxt = getRangeText(3837        {LSqBracketLoc.getLocWithOffset(1), D->getTypeSpecEndLoc()},3838        Ctx.getSourceManager(), Ctx.getLangOpts());3839    if (!MaybeArraySizeTxt)3840      return {};3841    const llvm::StringRef ArraySizeTxt = MaybeArraySizeTxt->trim();3842    if (ArraySizeTxt.empty()) {3843      // FIXME: Support array size getting determined from the initializer.3844      // Examples:3845      //    int arr1[] = {0, 1, 2};3846      //    int arr2{3, 4, 5};3847      // We might be able to preserve the non-specified size with `auto` and3848      // `std::to_array`:3849      //    auto arr1 = std::to_array<int>({0, 1, 2});3850      return {};3851    }3852 3853    std::optional<StringRef> IdentText =3854        getVarDeclIdentifierText(D, Ctx.getSourceManager(), Ctx.getLangOpts());3855 3856    if (!IdentText) {3857      DEBUG_NOTE_DECL_FAIL(D, " : failed to locate the identifier");3858      return {};3859    }3860 3861    SmallString<32> Replacement;3862    llvm::raw_svector_ostream OS(Replacement);3863    OS << "std::array<" << ElemTypeTxt << ", " << ArraySizeTxt << "> "3864       << IdentText->str();3865 3866    FixIts.push_back(FixItHint::CreateReplacement(3867        SourceRange{D->getBeginLoc(), D->getTypeSpecEndLoc()}, OS.str()));3868  }3869 3870  return FixIts;3871}3872 3873static FixItList fixVariableWithArray(const VarDecl *VD,3874                                      const DeclUseTracker &Tracker,3875                                      const ASTContext &Ctx,3876                                      UnsafeBufferUsageHandler &Handler) {3877  const DeclStmt *DS = Tracker.lookupDecl(VD);3878  assert(DS && "Fixing non-local variables not implemented yet!");3879  if (!DS->isSingleDecl()) {3880    // FIXME: to support handling multiple `VarDecl`s in a single `DeclStmt`3881    return {};3882  }3883  // Currently DS is an unused variable but we'll need it when3884  // non-single decls are implemented, where the pointee type name3885  // and the '*' are spread around the place.3886  (void)DS;3887 3888  // FIXME: handle cases where DS has multiple declarations3889  return fixVarDeclWithArray(VD, Ctx, Handler);3890}3891 3892// TODO: we should be consistent to use `std::nullopt` to represent no-fix due3893// to any unexpected problem.3894static FixItList3895fixVariable(const VarDecl *VD, FixitStrategy::Kind K,3896            /* The function decl under analysis */ const Decl *D,3897            const DeclUseTracker &Tracker, ASTContext &Ctx,3898            UnsafeBufferUsageHandler &Handler) {3899  if (const auto *PVD = dyn_cast<ParmVarDecl>(VD)) {3900    auto *FD = dyn_cast<clang::FunctionDecl>(PVD->getDeclContext());3901    if (!FD || FD != D) {3902      // `FD != D` means that `PVD` belongs to a function that is not being3903      // analyzed currently.  Thus `FD` may not be complete.3904      DEBUG_NOTE_DECL_FAIL(VD, " : function not currently analyzed");3905      return {};3906    }3907 3908    // TODO If function has a try block we can't change params unless we check3909    // also its catch block for their use.3910    // FIXME We might support static class methods, some select methods,3911    // operators and possibly lamdas.3912    if (FD->isMain() || FD->isConstexpr() ||3913        FD->getTemplatedKind() != FunctionDecl::TemplatedKind::TK_NonTemplate ||3914        FD->isVariadic() ||3915        // also covers call-operator of lamdas3916        isa<CXXMethodDecl>(FD) ||3917        // skip when the function body is a try-block3918        (FD->hasBody() && isa<CXXTryStmt>(FD->getBody())) ||3919        FD->isOverloadedOperator()) {3920      DEBUG_NOTE_DECL_FAIL(VD, " : unsupported function decl");3921      return {}; // TODO test all these cases3922    }3923  }3924 3925  switch (K) {3926  case FixitStrategy::Kind::Span: {3927    if (VD->getType()->isPointerType()) {3928      if (const auto *PVD = dyn_cast<ParmVarDecl>(VD))3929        return fixParamWithSpan(PVD, Ctx, Handler);3930 3931      if (VD->isLocalVarDecl())3932        return fixVariableWithSpan(VD, Tracker, Ctx, Handler);3933    }3934    DEBUG_NOTE_DECL_FAIL(VD, " : not a pointer");3935    return {};3936  }3937  case FixitStrategy::Kind::Array: {3938    if (VD->isLocalVarDecl() && Ctx.getAsConstantArrayType(VD->getType()))3939      return fixVariableWithArray(VD, Tracker, Ctx, Handler);3940 3941    DEBUG_NOTE_DECL_FAIL(VD, " : not a local const-size array");3942    return {};3943  }3944  case FixitStrategy::Kind::Iterator:3945  case FixitStrategy::Kind::Vector:3946    llvm_unreachable("FixitStrategy not implemented yet!");3947  case FixitStrategy::Kind::Wontfix:3948    llvm_unreachable("Invalid strategy!");3949  }3950  llvm_unreachable("Unknown strategy!");3951}3952 3953// Returns true iff there exists a `FixItHint` 'h' in `FixIts` such that the3954// `RemoveRange` of 'h' overlaps with a macro use.3955static bool overlapWithMacro(const FixItList &FixIts) {3956  // FIXME: For now we only check if the range (or the first token) is (part of)3957  // a macro expansion.  Ideally, we want to check for all tokens in the range.3958  return llvm::any_of(FixIts, [](const FixItHint &Hint) {3959    auto Range = Hint.RemoveRange;3960    if (Range.getBegin().isMacroID() || Range.getEnd().isMacroID())3961      // If the range (or the first token) is (part of) a macro expansion:3962      return true;3963    return false;3964  });3965}3966 3967// Returns true iff `VD` is a parameter of the declaration `D`:3968static bool isParameterOf(const VarDecl *VD, const Decl *D) {3969  return isa<ParmVarDecl>(VD) &&3970         VD->getDeclContext() == dyn_cast<DeclContext>(D);3971}3972 3973// Erases variables in `FixItsForVariable`, if such a variable has an unfixable3974// group mate.  A variable `v` is unfixable iff `FixItsForVariable` does not3975// contain `v`.3976static void eraseVarsForUnfixableGroupMates(3977    std::map<const VarDecl *, FixItList> &FixItsForVariable,3978    const VariableGroupsManager &VarGrpMgr) {3979  // Variables will be removed from `FixItsForVariable`:3980  SmallVector<const VarDecl *, 8> ToErase;3981 3982  for (const auto &[VD, Ignore] : FixItsForVariable) {3983    VarGrpRef Grp = VarGrpMgr.getGroupOfVar(VD);3984    if (llvm::any_of(Grp,3985                     [&FixItsForVariable](const VarDecl *GrpMember) -> bool {3986                       return !FixItsForVariable.count(GrpMember);3987                     })) {3988      // At least one group member cannot be fixed, so we have to erase the3989      // whole group:3990      for (const VarDecl *Member : Grp)3991        ToErase.push_back(Member);3992    }3993  }3994  for (auto *VarToErase : ToErase)3995    FixItsForVariable.erase(VarToErase);3996}3997 3998// Returns the fix-its that create bounds-safe function overloads for the3999// function `D`, if `D`'s parameters will be changed to safe-types through4000// fix-its in `FixItsForVariable`.4001//4002// NOTE: In case `D`'s parameters will be changed but bounds-safe function4003// overloads cannot created, the whole group that contains the parameters will4004// be erased from `FixItsForVariable`.4005static FixItList createFunctionOverloadsForParms(4006    std::map<const VarDecl *, FixItList> &FixItsForVariable /* mutable */,4007    const VariableGroupsManager &VarGrpMgr, const FunctionDecl *FD,4008    const FixitStrategy &S, ASTContext &Ctx,4009    UnsafeBufferUsageHandler &Handler) {4010  FixItList FixItsSharedByParms{};4011 4012  std::optional<FixItList> OverloadFixes =4013      createOverloadsForFixedParams(S, FD, Ctx, Handler);4014 4015  if (OverloadFixes) {4016    FixItsSharedByParms.append(*OverloadFixes);4017  } else {4018    // Something wrong in generating `OverloadFixes`, need to remove the4019    // whole group, where parameters are in, from `FixItsForVariable` (Note4020    // that all parameters should be in the same group):4021    for (auto *Member : VarGrpMgr.getGroupOfParms())4022      FixItsForVariable.erase(Member);4023  }4024  return FixItsSharedByParms;4025}4026 4027// Constructs self-contained fix-its for each variable in `FixablesForAllVars`.4028static std::map<const VarDecl *, FixItList>4029getFixIts(FixableGadgetSets &FixablesForAllVars, const FixitStrategy &S,4030          ASTContext &Ctx,4031          /* The function decl under analysis */ const Decl *D,4032          const DeclUseTracker &Tracker, UnsafeBufferUsageHandler &Handler,4033          const VariableGroupsManager &VarGrpMgr) {4034  // `FixItsForVariable` will map each variable to a set of fix-its directly4035  // associated to the variable itself.  Fix-its of distinct variables in4036  // `FixItsForVariable` are disjoint.4037  std::map<const VarDecl *, FixItList> FixItsForVariable;4038 4039  // Populate `FixItsForVariable` with fix-its directly associated with each4040  // variable.  Fix-its directly associated to a variable 'v' are the ones4041  // produced by the `FixableGadget`s whose claimed variable is 'v'.4042  for (const auto &[VD, Fixables] : FixablesForAllVars.byVar) {4043    FixItsForVariable[VD] =4044        fixVariable(VD, S.lookup(VD), D, Tracker, Ctx, Handler);4045    // If we fail to produce Fix-It for the declaration we have to skip the4046    // variable entirely.4047    if (FixItsForVariable[VD].empty()) {4048      FixItsForVariable.erase(VD);4049      continue;4050    }4051    for (const auto &F : Fixables) {4052      std::optional<FixItList> Fixits = F->getFixits(S);4053 4054      if (Fixits) {4055        FixItsForVariable[VD].insert(FixItsForVariable[VD].end(),4056                                     Fixits->begin(), Fixits->end());4057        continue;4058      }4059#ifndef NDEBUG4060      Handler.addDebugNoteForVar(4061          VD, F->getSourceLoc(),4062          ("gadget '" + F->getDebugName() + "' refused to produce a fix")4063              .str());4064#endif4065      FixItsForVariable.erase(VD);4066      break;4067    }4068  }4069 4070  // `FixItsForVariable` now contains only variables that can be4071  // fixed. A variable can be fixed if its' declaration and all Fixables4072  // associated to it can all be fixed.4073 4074  // To further remove from `FixItsForVariable` variables whose group mates4075  // cannot be fixed...4076  eraseVarsForUnfixableGroupMates(FixItsForVariable, VarGrpMgr);4077  // Now `FixItsForVariable` gets further reduced: a variable is in4078  // `FixItsForVariable` iff it can be fixed and all its group mates can be4079  // fixed.4080 4081  // Fix-its of bounds-safe overloads of `D` are shared by parameters of `D`.4082  // That is,  when fixing multiple parameters in one step,  these fix-its will4083  // be applied only once (instead of being applied per parameter).4084  FixItList FixItsSharedByParms{};4085 4086  if (auto *FD = dyn_cast<FunctionDecl>(D))4087    FixItsSharedByParms = createFunctionOverloadsForParms(4088        FixItsForVariable, VarGrpMgr, FD, S, Ctx, Handler);4089 4090  // The map that maps each variable `v` to fix-its for the whole group where4091  // `v` is in:4092  std::map<const VarDecl *, FixItList> FinalFixItsForVariable{4093      FixItsForVariable};4094 4095  for (auto &[Var, Ignore] : FixItsForVariable) {4096    bool AnyParm = false;4097    const auto VarGroupForVD = VarGrpMgr.getGroupOfVar(Var, &AnyParm);4098 4099    for (const VarDecl *GrpMate : VarGroupForVD) {4100      if (Var == GrpMate)4101        continue;4102      if (FixItsForVariable.count(GrpMate))4103        FinalFixItsForVariable[Var].append(FixItsForVariable[GrpMate]);4104    }4105    if (AnyParm) {4106      // This assertion should never fail.  Otherwise we have a bug.4107      assert(!FixItsSharedByParms.empty() &&4108             "Should not try to fix a parameter that does not belong to a "4109             "FunctionDecl");4110      FinalFixItsForVariable[Var].append(FixItsSharedByParms);4111    }4112  }4113  // Fix-its that will be applied in one step shall NOT:4114  // 1. overlap with macros or/and templates; or4115  // 2. conflict with each other.4116  // Otherwise, the fix-its will be dropped.4117  for (auto Iter = FinalFixItsForVariable.begin();4118       Iter != FinalFixItsForVariable.end();)4119    if (overlapWithMacro(Iter->second) ||4120        clang::internal::anyConflict(Iter->second, Ctx.getSourceManager())) {4121      Iter = FinalFixItsForVariable.erase(Iter);4122    } else4123      Iter++;4124  return FinalFixItsForVariable;4125}4126 4127template <typename VarDeclIterTy>4128static FixitStrategy4129getNaiveStrategy(llvm::iterator_range<VarDeclIterTy> UnsafeVars) {4130  FixitStrategy S;4131  for (const VarDecl *VD : UnsafeVars) {4132    if (isa<ConstantArrayType>(VD->getType().getCanonicalType()))4133      S.set(VD, FixitStrategy::Kind::Array);4134    else4135      S.set(VD, FixitStrategy::Kind::Span);4136  }4137  return S;4138}4139 4140//  Manages variable groups:4141class VariableGroupsManagerImpl : public VariableGroupsManager {4142  const std::vector<VarGrpTy> Groups;4143  const std::map<const VarDecl *, unsigned> &VarGrpMap;4144  const llvm::SetVector<const VarDecl *> &GrpsUnionForParms;4145 4146public:4147  VariableGroupsManagerImpl(4148      const std::vector<VarGrpTy> &Groups,4149      const std::map<const VarDecl *, unsigned> &VarGrpMap,4150      const llvm::SetVector<const VarDecl *> &GrpsUnionForParms)4151      : Groups(Groups), VarGrpMap(VarGrpMap),4152        GrpsUnionForParms(GrpsUnionForParms) {}4153 4154  VarGrpRef getGroupOfVar(const VarDecl *Var, bool *HasParm) const override {4155    if (GrpsUnionForParms.contains(Var)) {4156      if (HasParm)4157        *HasParm = true;4158      return GrpsUnionForParms.getArrayRef();4159    }4160    if (HasParm)4161      *HasParm = false;4162 4163    auto It = VarGrpMap.find(Var);4164 4165    if (It == VarGrpMap.end())4166      return {};4167    return Groups[It->second];4168  }4169 4170  VarGrpRef getGroupOfParms() const override {4171    return GrpsUnionForParms.getArrayRef();4172  }4173};4174 4175static void applyGadgets(const Decl *D, FixableGadgetList FixableGadgets,4176                         WarningGadgetList WarningGadgets,4177                         DeclUseTracker Tracker,4178                         UnsafeBufferUsageHandler &Handler,4179                         bool EmitSuggestions) {4180  if (!EmitSuggestions) {4181    // Our job is very easy without suggestions. Just warn about4182    // every problematic operation and consider it done. No need to deal4183    // with fixable gadgets, no need to group operations by variable.4184    for (const auto &G : WarningGadgets) {4185      G->handleUnsafeOperation(Handler, /*IsRelatedToDecl=*/false,4186                               D->getASTContext());4187    }4188 4189    // This return guarantees that most of the machine doesn't run when4190    // suggestions aren't requested.4191    assert(FixableGadgets.empty() &&4192           "Fixable gadgets found but suggestions not requested!");4193    return;4194  }4195 4196  // If no `WarningGadget`s ever matched, there is no unsafe operations in the4197  //  function under the analysis. No need to fix any Fixables.4198  if (!WarningGadgets.empty()) {4199    // Gadgets "claim" variables they're responsible for. Once this loop4200    // finishes, the tracker will only track DREs that weren't claimed by any4201    // gadgets, i.e. not understood by the analysis.4202    for (const auto &G : FixableGadgets) {4203      for (const auto *DRE : G->getClaimedVarUseSites()) {4204        Tracker.claimUse(DRE);4205      }4206    }4207  }4208 4209  // If no `WarningGadget`s ever matched, there is no unsafe operations in the4210  // function under the analysis.  Thus, it early returns here as there is4211  // nothing needs to be fixed.4212  //4213  // Note this claim is based on the assumption that there is no unsafe4214  // variable whose declaration is invisible from the analyzing function.4215  // Otherwise, we need to consider if the uses of those unsafe varuables needs4216  // fix.4217  // So far, we are not fixing any global variables or class members. And,4218  // lambdas will be analyzed along with the enclosing function. So this early4219  // return is correct for now.4220  if (WarningGadgets.empty())4221    return;4222 4223  WarningGadgetSets UnsafeOps =4224      groupWarningGadgetsByVar(std::move(WarningGadgets));4225  FixableGadgetSets FixablesForAllVars =4226      groupFixablesByVar(std::move(FixableGadgets));4227 4228  std::map<const VarDecl *, FixItList> FixItsForVariableGroup;4229 4230  // Filter out non-local vars and vars with unclaimed DeclRefExpr-s.4231  for (auto it = FixablesForAllVars.byVar.cbegin();4232       it != FixablesForAllVars.byVar.cend();) {4233    // FIXME: need to deal with global variables later4234    if ((!it->first->isLocalVarDecl() && !isa<ParmVarDecl>(it->first))) {4235#ifndef NDEBUG4236      Handler.addDebugNoteForVar(it->first, it->first->getBeginLoc(),4237                                 ("failed to produce fixit for '" +4238                                  it->first->getNameAsString() +4239                                  "' : neither local nor a parameter"));4240#endif4241      it = FixablesForAllVars.byVar.erase(it);4242    } else if (it->first->getType().getCanonicalType()->isReferenceType()) {4243#ifndef NDEBUG4244      Handler.addDebugNoteForVar(it->first, it->first->getBeginLoc(),4245                                 ("failed to produce fixit for '" +4246                                  it->first->getNameAsString() +4247                                  "' : has a reference type"));4248#endif4249      it = FixablesForAllVars.byVar.erase(it);4250    } else if (Tracker.hasUnclaimedUses(it->first)) {4251      it = FixablesForAllVars.byVar.erase(it);4252    } else if (it->first->isInitCapture()) {4253#ifndef NDEBUG4254      Handler.addDebugNoteForVar(it->first, it->first->getBeginLoc(),4255                                 ("failed to produce fixit for '" +4256                                  it->first->getNameAsString() +4257                                  "' : init capture"));4258#endif4259      it = FixablesForAllVars.byVar.erase(it);4260    } else {4261      ++it;4262    }4263  }4264 4265#ifndef NDEBUG4266  for (const auto &it : UnsafeOps.byVar) {4267    const VarDecl *const UnsafeVD = it.first;4268    auto UnclaimedDREs = Tracker.getUnclaimedUses(UnsafeVD);4269    if (UnclaimedDREs.empty())4270      continue;4271    const auto UnfixedVDName = UnsafeVD->getNameAsString();4272    for (const clang::DeclRefExpr *UnclaimedDRE : UnclaimedDREs) {4273      std::string UnclaimedUseTrace =4274          getDREAncestorString(UnclaimedDRE, D->getASTContext());4275 4276      Handler.addDebugNoteForVar(4277          UnsafeVD, UnclaimedDRE->getBeginLoc(),4278          ("failed to produce fixit for '" + UnfixedVDName +4279           "' : has an unclaimed use\nThe unclaimed DRE trace: " +4280           UnclaimedUseTrace));4281    }4282  }4283#endif4284 4285  // Fixpoint iteration for pointer assignments4286  using DepMapTy =4287      llvm::DenseMap<const VarDecl *, llvm::SetVector<const VarDecl *>>;4288  DepMapTy DependenciesMap{};4289  DepMapTy PtrAssignmentGraph{};4290 4291  for (const auto &it : FixablesForAllVars.byVar) {4292    for (const FixableGadget *fixable : it.second) {4293      std::optional<std::pair<const VarDecl *, const VarDecl *>> ImplPair =4294          fixable->getStrategyImplications();4295      if (ImplPair) {4296        std::pair<const VarDecl *, const VarDecl *> Impl = std::move(*ImplPair);4297        PtrAssignmentGraph[Impl.first].insert(Impl.second);4298      }4299    }4300  }4301 4302  /*4303   The following code does a BFS traversal of the `PtrAssignmentGraph`4304   considering all unsafe vars as starting nodes and constructs an undirected4305   graph `DependenciesMap`. Constructing the `DependenciesMap` in this manner4306   elimiates all variables that are unreachable from any unsafe var. In other4307   words, this removes all dependencies that don't include any unsafe variable4308   and consequently don't need any fixit generation.4309   Note: A careful reader would observe that the code traverses4310   `PtrAssignmentGraph` using `CurrentVar` but adds edges between `Var` and4311   `Adj` and not between `CurrentVar` and `Adj`. Both approaches would4312   achieve the same result but the one used here dramatically cuts the4313   amount of hoops the second part of the algorithm needs to jump, given that4314   a lot of these connections become "direct". The reader is advised not to4315   imagine how the graph is transformed because of using `Var` instead of4316   `CurrentVar`. The reader can continue reading as if `CurrentVar` was used,4317   and think about why it's equivalent later.4318   */4319  std::set<const VarDecl *> VisitedVarsDirected{};4320  for (const auto &[Var, ignore] : UnsafeOps.byVar) {4321    if (VisitedVarsDirected.find(Var) == VisitedVarsDirected.end()) {4322 4323      std::queue<const VarDecl *> QueueDirected{};4324      QueueDirected.push(Var);4325      while (!QueueDirected.empty()) {4326        const VarDecl *CurrentVar = QueueDirected.front();4327        QueueDirected.pop();4328        VisitedVarsDirected.insert(CurrentVar);4329        auto AdjacentNodes = PtrAssignmentGraph[CurrentVar];4330        for (const VarDecl *Adj : AdjacentNodes) {4331          if (VisitedVarsDirected.find(Adj) == VisitedVarsDirected.end()) {4332            QueueDirected.push(Adj);4333          }4334          DependenciesMap[Var].insert(Adj);4335          DependenciesMap[Adj].insert(Var);4336        }4337      }4338    }4339  }4340 4341  // `Groups` stores the set of Connected Components in the graph.4342  std::vector<VarGrpTy> Groups;4343  // `VarGrpMap` maps variables that need fix to the groups (indexes) that the4344  // variables belong to.  Group indexes refer to the elements in `Groups`.4345  // `VarGrpMap` is complete in that every variable that needs fix is in it.4346  std::map<const VarDecl *, unsigned> VarGrpMap;4347  // The union group over the ones in "Groups" that contain parameters of `D`:4348  llvm::SetVector<const VarDecl *>4349      GrpsUnionForParms; // these variables need to be fixed in one step4350 4351  // Group Connected Components for Unsafe Vars4352  // (Dependencies based on pointer assignments)4353  std::set<const VarDecl *> VisitedVars{};4354  for (const auto &[Var, ignore] : UnsafeOps.byVar) {4355    if (VisitedVars.find(Var) == VisitedVars.end()) {4356      VarGrpTy &VarGroup = Groups.emplace_back();4357      std::queue<const VarDecl *> Queue{};4358 4359      Queue.push(Var);4360      while (!Queue.empty()) {4361        const VarDecl *CurrentVar = Queue.front();4362        Queue.pop();4363        VisitedVars.insert(CurrentVar);4364        VarGroup.push_back(CurrentVar);4365        auto AdjacentNodes = DependenciesMap[CurrentVar];4366        for (const VarDecl *Adj : AdjacentNodes) {4367          if (VisitedVars.find(Adj) == VisitedVars.end()) {4368            Queue.push(Adj);4369          }4370        }4371      }4372 4373      bool HasParm = false;4374      unsigned GrpIdx = Groups.size() - 1;4375 4376      for (const VarDecl *V : VarGroup) {4377        VarGrpMap[V] = GrpIdx;4378        if (!HasParm && isParameterOf(V, D))4379          HasParm = true;4380      }4381      if (HasParm)4382        GrpsUnionForParms.insert_range(VarGroup);4383    }4384  }4385 4386  // Remove a `FixableGadget` if the associated variable is not in the graph4387  // computed above.  We do not want to generate fix-its for such variables,4388  // since they are neither warned nor reachable from a warned one.4389  //4390  // Note a variable is not warned if it is not directly used in any unsafe4391  // operation. A variable `v` is NOT reachable from an unsafe variable, if it4392  // does not exist another variable `u` such that `u` is warned and fixing `u`4393  // (transitively) implicates fixing `v`.4394  //4395  // For example,4396  // ```4397  // void f(int * p) {4398  //   int * a = p; *p = 0;4399  // }4400  // ```4401  // `*p = 0` is a fixable gadget associated with a variable `p` that is neither4402  // warned nor reachable from a warned one.  If we add `a[5] = 0` to the end of4403  // the function above, `p` becomes reachable from a warned variable.4404  for (auto I = FixablesForAllVars.byVar.begin();4405       I != FixablesForAllVars.byVar.end();) {4406    // Note `VisitedVars` contain all the variables in the graph:4407    if (!VisitedVars.count((*I).first)) {4408      // no such var in graph:4409      I = FixablesForAllVars.byVar.erase(I);4410    } else4411      ++I;4412  }4413 4414  // We assign strategies to variables that are 1) in the graph and 2) can be4415  // fixed. Other variables have the default "Won't fix" strategy.4416  FixitStrategy NaiveStrategy = getNaiveStrategy(llvm::make_filter_range(4417      VisitedVars, [&FixablesForAllVars](const VarDecl *V) {4418        // If a warned variable has no "Fixable", it is considered unfixable:4419        return FixablesForAllVars.byVar.count(V);4420      }));4421  VariableGroupsManagerImpl VarGrpMgr(Groups, VarGrpMap, GrpsUnionForParms);4422 4423  if (isa<NamedDecl>(D))4424    // The only case where `D` is not a `NamedDecl` is when `D` is a4425    // `BlockDecl`. Let's not fix variables in blocks for now4426    FixItsForVariableGroup =4427        getFixIts(FixablesForAllVars, NaiveStrategy, D->getASTContext(), D,4428                  Tracker, Handler, VarGrpMgr);4429 4430  for (const auto &G : UnsafeOps.noVar) {4431    G->handleUnsafeOperation(Handler, /*IsRelatedToDecl=*/false,4432                             D->getASTContext());4433  }4434 4435  for (const auto &[VD, WarningGadgets] : UnsafeOps.byVar) {4436    auto FixItsIt = FixItsForVariableGroup.find(VD);4437    Handler.handleUnsafeVariableGroup(VD, VarGrpMgr,4438                                      FixItsIt != FixItsForVariableGroup.end()4439                                          ? std::move(FixItsIt->second)4440                                          : FixItList{},4441                                      D, NaiveStrategy);4442    for (const auto &G : WarningGadgets) {4443      G->handleUnsafeOperation(Handler, /*IsRelatedToDecl=*/true,4444                               D->getASTContext());4445    }4446  }4447}4448 4449void clang::checkUnsafeBufferUsage(const Decl *D,4450                                   UnsafeBufferUsageHandler &Handler,4451                                   bool EmitSuggestions) {4452#ifndef NDEBUG4453  Handler.clearDebugNotes();4454#endif4455 4456  assert(D);4457 4458  SmallVector<Stmt *> Stmts;4459 4460  if (const auto *FD = dyn_cast<FunctionDecl>(D)) {4461    // We do not want to visit a Lambda expression defined inside a method4462    // independently. Instead, it should be visited along with the outer method.4463    // FIXME: do we want to do the same thing for `BlockDecl`s?4464    if (const auto *MD = dyn_cast<CXXMethodDecl>(D)) {4465      if (MD->getParent()->isLambda() && MD->getParent()->isLocalClass())4466        return;4467    }4468 4469    for (FunctionDecl *FReDecl : FD->redecls()) {4470      if (FReDecl->isExternC()) {4471        // Do not emit fixit suggestions for functions declared in an4472        // extern "C" block.4473        EmitSuggestions = false;4474        break;4475      }4476    }4477 4478    Stmts.push_back(FD->getBody());4479 4480    if (const auto *ID = dyn_cast<CXXConstructorDecl>(D)) {4481      for (const CXXCtorInitializer *CI : ID->inits()) {4482        Stmts.push_back(CI->getInit());4483      }4484    }4485  } else if (isa<BlockDecl>(D) || isa<ObjCMethodDecl>(D)) {4486    Stmts.push_back(D->getBody());4487  }4488 4489  assert(!Stmts.empty());4490 4491  FixableGadgetList FixableGadgets;4492  WarningGadgetList WarningGadgets;4493  DeclUseTracker Tracker;4494  for (Stmt *S : Stmts) {4495    findGadgets(S, D->getASTContext(), Handler, EmitSuggestions, FixableGadgets,4496                WarningGadgets, Tracker);4497  }4498  applyGadgets(D, std::move(FixableGadgets), std::move(WarningGadgets),4499               std::move(Tracker), Handler, EmitSuggestions);4500}4501