Coverage Report

Created: 2023-11-11 10:31

/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/Analysis/UnsafeBufferUsage.cpp
Line
Count
Source (jump to first uncovered line)
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-exception
6
//
7
//===----------------------------------------------------------------------===//
8
9
#include "clang/Analysis/Analyses/UnsafeBufferUsage.h"
10
#include "clang/AST/Decl.h"
11
#include "clang/AST/Expr.h"
12
#include "clang/AST/RecursiveASTVisitor.h"
13
#include "clang/AST/StmtVisitor.h"
14
#include "clang/ASTMatchers/ASTMatchFinder.h"
15
#include "clang/Lex/Lexer.h"
16
#include "clang/Lex/Preprocessor.h"
17
#include "llvm/ADT/SmallVector.h"
18
#include <memory>
19
#include <optional>
20
#include <sstream>
21
#include <queue>
22
23
using namespace llvm;
24
using namespace clang;
25
using namespace ast_matchers;
26
27
#ifndef NDEBUG
28
namespace {
29
class StmtDebugPrinter
30
    : public ConstStmtVisitor<StmtDebugPrinter, std::string> {
31
public:
32
311
  std::string VisitStmt(const Stmt *S) { return S->getStmtClassName(); }
33
34
31
  std::string VisitBinaryOperator(const BinaryOperator *BO) {
35
31
    return "BinaryOperator(" + BO->getOpcodeStr().str() + ")";
36
31
  }
37
38
65
  std::string VisitUnaryOperator(const UnaryOperator *UO) {
39
65
    return "UnaryOperator(" + UO->getOpcodeStr(UO->getOpcode()).str() + ")";
40
65
  }
41
42
82
  std::string VisitImplicitCastExpr(const ImplicitCastExpr *ICE) {
43
82
    return "ImplicitCastExpr(" + std::string(ICE->getCastKindName()) + ")";
44
82
  }
45
};
46
47
// Returns a string of ancestor `Stmt`s of the given `DRE` in such a form:
48
// "DRE ==> parent-of-DRE ==> grandparent-of-DRE ==> ...".
49
static std::string getDREAncestorString(const DeclRefExpr *DRE,
50
119
                                        ASTContext &Ctx) {
51
119
  std::stringstream SS;
52
119
  const Stmt *St = DRE;
53
119
  StmtDebugPrinter StmtPriner;
54
55
489
  do {
56
489
    SS << StmtPriner.Visit(St);
57
58
489
    DynTypedNodeList StParents = Ctx.getParents(*St);
59
60
489
    if (StParents.size() > 1)
61
0
      return "unavailable due to multiple parents";
62
489
    if (StParents.size() == 0)
63
0
      break;
64
489
    St = StParents.begin()->get<Stmt>();
65
489
    if (St)
66
370
      SS << " ==> ";
67
489
  } while (St);
68
119
  return SS.str();
69
119
}
70
} // namespace
71
#endif /* NDEBUG */
72
73
namespace clang::ast_matchers {
74
// A `RecursiveASTVisitor` that traverses all descendants of a given node "n"
75
// except for those belonging to a different callable of "n".
76
class MatchDescendantVisitor
77
    : public RecursiveASTVisitor<MatchDescendantVisitor> {
78
public:
79
  typedef RecursiveASTVisitor<MatchDescendantVisitor> VisitorBase;
80
81
  // Creates an AST visitor that matches `Matcher` on all
82
  // descendants of a given node "n" except for the ones
83
  // belonging to a different callable of "n".
84
  MatchDescendantVisitor(const internal::DynTypedMatcher *Matcher,
85
                         internal::ASTMatchFinder *Finder,
86
                         internal::BoundNodesTreeBuilder *Builder,
87
                         internal::ASTMatchFinder::BindKind Bind,
88
                         const bool ignoreUnevaluatedContext)
89
850
      : Matcher(Matcher), Finder(Finder), Builder(Builder), Bind(Bind),
90
850
        Matches(false), ignoreUnevaluatedContext(ignoreUnevaluatedContext) {}
91
92
  // Returns true if a match is found in a subtree of `DynNode`, which belongs
93
  // to the same callable of `DynNode`.
94
850
  bool findMatch(const DynTypedNode &DynNode) {
95
850
    Matches = false;
96
850
    if (const Stmt *StmtNode = DynNode.get<Stmt>()) {
97
850
      TraverseStmt(const_cast<Stmt *>(StmtNode));
98
850
      *Builder = ResultBindings;
99
850
      return Matches;
100
850
    }
101
0
    return false;
102
850
  }
103
104
  // The following are overriding methods from the base visitor class.
105
  // They are public only to allow CRTP to work. They are *not *part
106
  // of the public API of this class.
107
108
  // For the matchers so far used in safe buffers, we only need to match
109
  // `Stmt`s.  To override more as needed.
110
111
1.85k
  bool TraverseDecl(Decl *Node) {
112
1.85k
    if (!Node)
113
0
      return true;
114
1.85k
    if (!match(*Node))
115
0
      return false;
116
    // To skip callables:
117
1.85k
    if (isa<FunctionDecl, BlockDecl, ObjCMethodDecl>(Node))
118
27
      return true;
119
    // Traverse descendants
120
1.82k
    return VisitorBase::TraverseDecl(Node);
121
1.85k
  }
122
123
16
  bool TraverseGenericSelectionExpr(GenericSelectionExpr *Node) {
124
    // These are unevaluated, except the result expression.
125
16
    if(ignoreUnevaluatedContext)
126
8
      return TraverseStmt(Node->getResultExpr());
127
8
    return VisitorBase::TraverseGenericSelectionExpr(Node);
128
16
  }
129
130
20
  bool TraverseUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *Node) {
131
    // Unevaluated context.
132
20
    if(ignoreUnevaluatedContext)
133
10
      return true;
134
10
    return VisitorBase::TraverseUnaryExprOrTypeTraitExpr(Node);
135
20
  }
136
137
12
  bool TraverseTypeOfExprTypeLoc(TypeOfExprTypeLoc Node) {
138
    // Unevaluated context.
139
12
    if(ignoreUnevaluatedContext)
140
6
      return true;
141
6
    return VisitorBase::TraverseTypeOfExprTypeLoc(Node);
142
12
  }
143
144
11
  bool TraverseDecltypeTypeLoc(DecltypeTypeLoc Node) {
145
    // Unevaluated context.
146
11
    if(ignoreUnevaluatedContext)
147
4
      return true;
148
7
    return VisitorBase::TraverseDecltypeTypeLoc(Node);
149
11
  }
150
151
4
  bool TraverseCXXNoexceptExpr(CXXNoexceptExpr *Node) {
152
    // Unevaluated context.
153
4
    if(ignoreUnevaluatedContext)
154
2
      return true;
155
2
    return VisitorBase::TraverseCXXNoexceptExpr(Node);
156
4
  }
157
158
14
  bool TraverseCXXTypeidExpr(CXXTypeidExpr *Node) {
159
    // Unevaluated context.
160
14
    if(ignoreUnevaluatedContext)
161
7
      return true;
162
7
    return VisitorBase::TraverseCXXTypeidExpr(Node);
163
14
  }
164
165
18.9k
  bool TraverseStmt(Stmt *Node, DataRecursionQueue *Queue = nullptr) {
166
18.9k
    if (!Node)
167
773
      return true;
168
18.2k
    if (!match(*Node))
169
0
      return false;
170
18.2k
    return VisitorBase::TraverseStmt(Node);
171
18.2k
  }
172
173
0
  bool shouldVisitTemplateInstantiations() const { return true; }
174
1.93k
  bool shouldVisitImplicitCode() const {
175
    // TODO: let's ignore implicit code for now
176
1.93k
    return false;
177
1.93k
  }
178
179
private:
180
  // Sets 'Matched' to true if 'Matcher' matches 'Node'
181
  //
182
  // Returns 'true' if traversal should continue after this function
183
  // returns, i.e. if no match is found or 'Bind' is 'BK_All'.
184
20.0k
  template <typename T> bool match(const T &Node) {
185
20.0k
    internal::BoundNodesTreeBuilder RecursiveBuilder(*Builder);
186
187
20.0k
    if (Matcher->matches(DynTypedNode::create(Node), Finder,
188
20.0k
                         &RecursiveBuilder)) {
189
3.46k
      ResultBindings.addMatch(RecursiveBuilder);
190
3.46k
      Matches = true;
191
3.46k
      if (Bind != internal::ASTMatchFinder::BK_All)
192
0
        return false; // Abort as soon as a match is found.
193
3.46k
    }
194
20.0k
    return true;
195
20.0k
  }
bool clang::ast_matchers::MatchDescendantVisitor::match<clang::Stmt>(clang::Stmt const&)
Line
Count
Source
184
18.2k
  template <typename T> bool match(const T &Node) {
185
18.2k
    internal::BoundNodesTreeBuilder RecursiveBuilder(*Builder);
186
187
18.2k
    if (Matcher->matches(DynTypedNode::create(Node), Finder,
188
18.2k
                         &RecursiveBuilder)) {
189
3.46k
      ResultBindings.addMatch(RecursiveBuilder);
190
3.46k
      Matches = true;
191
3.46k
      if (Bind != internal::ASTMatchFinder::BK_All)
192
0
        return false; // Abort as soon as a match is found.
193
3.46k
    }
194
18.2k
    return true;
195
18.2k
  }
bool clang::ast_matchers::MatchDescendantVisitor::match<clang::Decl>(clang::Decl const&)
Line
Count
Source
184
1.85k
  template <typename T> bool match(const T &Node) {
185
1.85k
    internal::BoundNodesTreeBuilder RecursiveBuilder(*Builder);
186
187
1.85k
    if (Matcher->matches(DynTypedNode::create(Node), Finder,
188
1.85k
                         &RecursiveBuilder)) {
189
0
      ResultBindings.addMatch(RecursiveBuilder);
190
0
      Matches = true;
191
0
      if (Bind != internal::ASTMatchFinder::BK_All)
192
0
        return false; // Abort as soon as a match is found.
193
0
    }
194
1.85k
    return true;
195
1.85k
  }
196
197
  const internal::DynTypedMatcher *const Matcher;
198
  internal::ASTMatchFinder *const Finder;
199
  internal::BoundNodesTreeBuilder *const Builder;
200
  internal::BoundNodesTreeBuilder ResultBindings;
201
  const internal::ASTMatchFinder::BindKind Bind;
202
  bool Matches;
203
  bool ignoreUnevaluatedContext;
204
};
205
206
// Because we're dealing with raw pointers, let's define what we mean by that.
207
11.6k
static auto hasPointerType() {
208
11.6k
    return hasType(hasCanonicalType(pointerType()));
209
11.6k
}
210
211
1.58k
static auto hasArrayType() {
212
1.58k
    return hasType(hasCanonicalType(arrayType()));
213
1.58k
}
214
215
481
AST_MATCHER_P(Stmt, forEachDescendantEvaluatedStmt, internal::Matcher<Stmt>, innerMatcher) {
216
481
  const DynTypedMatcher &DTM = static_cast<DynTypedMatcher>(innerMatcher);
217
218
481
  MatchDescendantVisitor Visitor(&DTM, Finder, Builder, ASTMatchFinder::BK_All, true);
219
481
  return Visitor.findMatch(DynTypedNode::create(Node));
220
481
}
221
222
369
AST_MATCHER_P(Stmt, forEachDescendantStmt, internal::Matcher<Stmt>, innerMatcher) {
223
369
  const DynTypedMatcher &DTM = static_cast<DynTypedMatcher>(innerMatcher);
224
225
369
  MatchDescendantVisitor Visitor(&DTM, Finder, Builder, ASTMatchFinder::BK_All, false);
226
369
  return Visitor.findMatch(DynTypedNode::create(Node));
227
369
}
228
229
// Matches a `Stmt` node iff the node is in a safe-buffer opt-out region
230
AST_MATCHER_P(Stmt, notInSafeBufferOptOut, const UnsafeBufferUsageHandler *,
231
982
              Handler) {
232
982
  return !Handler->isSafeBufferOptOut(Node.getBeginLoc());
233
982
}
234
235
4.21k
AST_MATCHER_P(CastExpr, castSubExpr, internal::Matcher<Expr>, innerMatcher) {
236
4.21k
  return innerMatcher.matches(*Node.getSubExpr(), Finder, Builder);
237
4.21k
}
238
239
// Matches a `UnaryOperator` whose operator is pre-increment:
240
65
AST_MATCHER(UnaryOperator, isPreInc) {
241
65
  return Node.getOpcode() == UnaryOperator::Opcode::UO_PreInc;
242
65
}
243
244
// Returns a matcher that matches any expression 'e' such that `innerMatcher`
245
// matches 'e' and 'e' is in an Unspecified Lvalue Context.
246
1.10k
static auto isInUnspecifiedLvalueContext(internal::Matcher<Expr> innerMatcher) {
247
  // clang-format off
248
1.10k
  return
249
1.10k
    expr(anyOf(
250
1.10k
      implicitCastExpr(
251
1.10k
        hasCastKind(CastKind::CK_LValueToRValue),
252
1.10k
        castSubExpr(innerMatcher)),
253
1.10k
      binaryOperator(
254
1.10k
        hasAnyOperatorName("="),
255
1.10k
        hasLHS(innerMatcher)
256
1.10k
      )
257
1.10k
    ));
258
// clang-format on
259
1.10k
}
260
261
262
// Returns a matcher that matches any expression `e` such that `InnerMatcher`
263
// matches `e` and `e` is in an Unspecified Pointer Context (UPC).
264
static internal::Matcher<Stmt>
265
1.10k
isInUnspecifiedPointerContext(internal::Matcher<Stmt> InnerMatcher) {
266
  // A UPC can be
267
  // 1. an argument of a function call (except the callee has [[unsafe_...]]
268
  //    attribute), or
269
  // 2. the operand of a pointer-to-(integer or bool) cast operation; or
270
  // 3. the operand of a comparator operation; or
271
  // 4. the operand of a pointer subtraction operation
272
  //    (i.e., computing the distance between two pointers); or ...
273
274
1.10k
  auto CallArgMatcher =
275
1.10k
      callExpr(forEachArgumentWithParam(InnerMatcher,
276
1.10k
                  hasPointerType() /* array also decays to pointer type*/),
277
1.10k
          unless(callee(functionDecl(hasAttr(attr::UnsafeBufferUsage)))));
278
279
1.10k
  auto CastOperandMatcher =
280
1.10k
      castExpr(anyOf(hasCastKind(CastKind::CK_PointerToIntegral),
281
1.10k
         hasCastKind(CastKind::CK_PointerToBoolean)),
282
1.10k
         castSubExpr(allOf(hasPointerType(), InnerMatcher)));
283
284
1.10k
  auto CompOperandMatcher =
285
1.10k
      binaryOperator(hasAnyOperatorName("!=", "==", "<", "<=", ">", ">="),
286
1.10k
                     eachOf(hasLHS(allOf(hasPointerType(), InnerMatcher)),
287
1.10k
                            hasRHS(allOf(hasPointerType(), InnerMatcher))));
288
289
  // A matcher that matches pointer subtractions:
290
1.10k
  auto PtrSubtractionMatcher =
291
1.10k
      binaryOperator(hasOperatorName("-"),
292
         // Note that here we need both LHS and RHS to be
293
         // pointer. Then the inner matcher can match any of
294
         // them:
295
1.10k
         allOf(hasLHS(hasPointerType()),
296
1.10k
         hasRHS(hasPointerType())),
297
1.10k
         eachOf(hasLHS(InnerMatcher),
298
1.10k
          hasRHS(InnerMatcher)));
299
300
1.10k
  return stmt(anyOf(CallArgMatcher, CastOperandMatcher, CompOperandMatcher,
301
1.10k
        PtrSubtractionMatcher));
302
  // FIXME: any more cases? (UPC excludes the RHS of an assignment.  For now we
303
  // don't have to check that.)
304
1.10k
}
305
306
// Returns a matcher that matches any expression 'e' such that `innerMatcher`
307
// matches 'e' and 'e' is in an unspecified untyped context (i.e the expression
308
// 'e' isn't evaluated to an RValue). For example, consider the following code:
309
//    int *p = new int[4];
310
//    int *q = new int[4];
311
//    if ((p = q)) {}
312
//    p = q;
313
// The expression `p = q` in the conditional of the `if` statement
314
// `if ((p = q))` is evaluated as an RValue, whereas the expression `p = q;`
315
// in the assignment statement is in an untyped context.
316
static internal::Matcher<Stmt>
317
369
isInUnspecifiedUntypedContext(internal::Matcher<Stmt> InnerMatcher) {
318
  // An unspecified context can be
319
  // 1. A compound statement,
320
  // 2. The body of an if statement
321
  // 3. Body of a loop
322
369
  auto CompStmt = compoundStmt(forEach(InnerMatcher));
323
369
  auto IfStmtThen = ifStmt(hasThen(InnerMatcher));
324
369
  auto IfStmtElse = ifStmt(hasElse(InnerMatcher));
325
  // FIXME: Handle loop bodies.
326
369
  return stmt(anyOf(CompStmt, IfStmtThen, IfStmtElse));
327
369
}
328
} // namespace clang::ast_matchers
329
330
namespace {
331
// Because the analysis revolves around variables and their types, we'll need to
332
// track uses of variables (aka DeclRefExprs).
333
using DeclUseList = SmallVector<const DeclRefExpr *, 1>;
334
335
// Convenience typedef.
336
using FixItList = SmallVector<FixItHint, 4>;
337
338
// Defined below.
339
class Strategy;
340
} // namespace
341
342
namespace {
343
/// Gadget is an individual operation in the code that may be of interest to
344
/// this analysis. Each (non-abstract) subclass corresponds to a specific
345
/// rigid AST structure that constitutes an operation on a pointer-type object.
346
/// Discovery of a gadget in the code corresponds to claiming that we understand
347
/// what this part of code is doing well enough to potentially improve it.
348
/// Gadgets can be warning (immediately deserving a warning) or fixable (not
349
/// always deserving a warning per se, but requires our attention to identify
350
/// it warrants a fixit).
351
class Gadget {
352
public:
353
  enum class Kind {
354
#define GADGET(x) x,
355
#include "clang/Analysis/Analyses/UnsafeBufferUsageGadgets.def"
356
  };
357
358
  /// Common type of ASTMatchers used for discovering gadgets.
359
  /// Useful for implementing the static matcher() methods
360
  /// that are expected from all non-abstract subclasses.
361
  using Matcher = decltype(stmt());
362
363
1.71k
  Gadget(Kind K) : K(K) {}
364
365
0
  Kind getKind() const { return K; }
366
367
#ifndef NDEBUG
368
57
  StringRef getDebugName() const {
369
57
    switch (K) {
370
57
#define GADGET(x) case Kind::x: return #x;
371
57
#include 
"clang/Analysis/Analyses/UnsafeBufferUsageGadgets.def"0
372
57
    }
373
0
    llvm_unreachable("Unhandled Gadget::Kind enum");
374
0
  }
375
#endif
376
377
  virtual bool isWarningGadget() const = 0;
378
  virtual const Stmt *getBaseStmt() const = 0;
379
380
  /// Returns the list of pointer-type variables on which this gadget performs
381
  /// its operation. Typically, there's only one variable. This isn't a list
382
  /// of all DeclRefExprs in the gadget's AST!
383
  virtual DeclUseList getClaimedVarUseSites() const = 0;
384
385
1.71k
  virtual ~Gadget() = default;
386
387
private:
388
  Kind K;
389
};
390
391
392
/// Warning gadgets correspond to unsafe code patterns that warrants
393
/// an immediate warning.
394
class WarningGadget : public Gadget {
395
public:
396
938
  WarningGadget(Kind K) : Gadget(K) {}
397
398
0
  static bool classof(const Gadget *G) { return G->isWarningGadget(); }
399
0
  bool isWarningGadget() const final { return true; }
400
};
401
402
/// Fixable gadgets correspond to code patterns that aren't always unsafe but need to be
403
/// properly recognized in order to emit fixes. For example, if a raw pointer-type
404
/// variable is replaced by a safe C++ container, every use of such variable must be
405
/// carefully considered and possibly updated.
406
class FixableGadget : public Gadget {
407
public:
408
773
  FixableGadget(Kind K) : Gadget(K) {}
409
410
0
  static bool classof(const Gadget *G) { return !G->isWarningGadget(); }
411
0
  bool isWarningGadget() const final { return false; }
412
413
  /// Returns a fixit that would fix the current gadget according to
414
  /// the current strategy. Returns std::nullopt if the fix cannot be produced;
415
  /// returns an empty list if no fixes are necessary.
416
0
  virtual std::optional<FixItList> getFixits(const Strategy &) const {
417
0
    return std::nullopt;
418
0
  }
419
420
  /// Returns a list of two elements where the first element is the LHS of a pointer assignment
421
  /// statement and the second element is the RHS. This two-element list represents the fact that
422
  /// the LHS buffer gets its bounds information from the RHS buffer. This information will be used
423
  /// later to group all those variables whose types must be modified together to prevent type
424
  /// mismatches.
425
  virtual std::optional<std::pair<const VarDecl *, const VarDecl *>>
426
498
  getStrategyImplications() const {
427
498
    return std::nullopt;
428
498
  }
429
};
430
431
3.32k
static auto toSupportedVariable() {
432
3.32k
  return to(varDecl());
433
3.32k
}
434
435
using FixableGadgetList = std::vector<std::unique_ptr<FixableGadget>>;
436
using WarningGadgetList = std::vector<std::unique_ptr<WarningGadget>>;
437
438
/// An increment of a pointer-type value is unsafe as it may run the pointer
439
/// out of bounds.
440
class IncrementGadget : public WarningGadget {
441
  static constexpr const char *const OpTag = "op";
442
  const UnaryOperator *Op;
443
444
public:
445
  IncrementGadget(const MatchFinder::MatchResult &Result)
446
90
      : WarningGadget(Kind::Increment),
447
90
        Op(Result.Nodes.getNodeAs<UnaryOperator>(OpTag)) {}
448
449
0
  static bool classof(const Gadget *G) {
450
0
    return G->getKind() == Kind::Increment;
451
0
  }
452
453
481
  static Matcher matcher() {
454
481
    return stmt(unaryOperator(
455
481
      hasOperatorName("++"),
456
481
      hasUnaryOperand(ignoringParenImpCasts(hasPointerType()))
457
481
    ).bind(OpTag));
458
481
  }
459
460
90
  const UnaryOperator *getBaseStmt() const override { return Op; }
461
462
88
  DeclUseList getClaimedVarUseSites() const override {
463
88
    SmallVector<const DeclRefExpr *, 2> Uses;
464
88
    if (const auto *DRE =
465
88
            dyn_cast<DeclRefExpr>(Op->getSubExpr()->IgnoreParenImpCasts())) {
466
87
      Uses.push_back(DRE);
467
87
    }
468
469
88
    return std::move(Uses);
470
88
  }
471
};
472
473
/// A decrement of a pointer-type value is unsafe as it may run the pointer
474
/// out of bounds.
475
class DecrementGadget : public WarningGadget {
476
  static constexpr const char *const OpTag = "op";
477
  const UnaryOperator *Op;
478
479
public:
480
  DecrementGadget(const MatchFinder::MatchResult &Result)
481
6
      : WarningGadget(Kind::Decrement),
482
6
        Op(Result.Nodes.getNodeAs<UnaryOperator>(OpTag)) {}
483
484
0
  static bool classof(const Gadget *G) {
485
0
    return G->getKind() == Kind::Decrement;
486
0
  }
487
488
481
  static Matcher matcher() {
489
481
    return stmt(unaryOperator(
490
481
      hasOperatorName("--"),
491
481
      hasUnaryOperand(ignoringParenImpCasts(hasPointerType()))
492
481
    ).bind(OpTag));
493
481
  }
494
495
6
  const UnaryOperator *getBaseStmt() const override { return Op; }
496
497
4
  DeclUseList getClaimedVarUseSites() const override {
498
4
    if (const auto *DRE =
499
4
            dyn_cast<DeclRefExpr>(Op->getSubExpr()->IgnoreParenImpCasts())) {
500
4
      return {DRE};
501
4
    }
502
503
0
    return {};
504
4
  }
505
};
506
507
/// Array subscript expressions on raw pointers as if they're arrays. Unsafe as
508
/// it doesn't have any bounds checks for the array.
509
class ArraySubscriptGadget : public WarningGadget {
510
  static constexpr const char *const ArraySubscrTag = "ArraySubscript";
511
  const ArraySubscriptExpr *ASE;
512
513
public:
514
  ArraySubscriptGadget(const MatchFinder::MatchResult &Result)
515
726
      : WarningGadget(Kind::ArraySubscript),
516
726
        ASE(Result.Nodes.getNodeAs<ArraySubscriptExpr>(ArraySubscrTag)) {}
517
518
0
  static bool classof(const Gadget *G) {
519
0
    return G->getKind() == Kind::ArraySubscript;
520
0
  }
521
522
481
  static Matcher matcher() {
523
    // FIXME: What if the index is integer literal 0? Should this be
524
    // a safe gadget in this case?
525
      // clang-format off
526
481
      return stmt(arraySubscriptExpr(
527
481
            hasBase(ignoringParenImpCasts(
528
481
              anyOf(hasPointerType(), hasArrayType()))),
529
481
            unless(hasIndex(
530
481
                anyOf(integerLiteral(equals(0)), arrayInitIndexExpr())
531
481
             )))
532
481
            .bind(ArraySubscrTag));
533
    // clang-format on
534
481
  }
535
536
726
  const ArraySubscriptExpr *getBaseStmt() const override { return ASE; }
537
538
494
  DeclUseList getClaimedVarUseSites() const override {
539
494
    if (const auto *DRE =
540
494
            dyn_cast<DeclRefExpr>(ASE->getBase()->IgnoreParenImpCasts())) {
541
442
      return {DRE};
542
442
    }
543
544
52
    return {};
545
494
  }
546
};
547
548
/// A pointer arithmetic expression of one of the forms:
549
///  \code
550
///  ptr + n | n + ptr | ptr - n | ptr += n | ptr -= n
551
///  \endcode
552
class PointerArithmeticGadget : public WarningGadget {
553
  static constexpr const char *const PointerArithmeticTag = "ptrAdd";
554
  static constexpr const char *const PointerArithmeticPointerTag = "ptrAddPtr";
555
  const BinaryOperator *PA; // pointer arithmetic expression
556
  const Expr *Ptr;          // the pointer expression in `PA`
557
558
public:
559
  PointerArithmeticGadget(const MatchFinder::MatchResult &Result)
560
93
      : WarningGadget(Kind::PointerArithmetic),
561
93
        PA(Result.Nodes.getNodeAs<BinaryOperator>(PointerArithmeticTag)),
562
93
        Ptr(Result.Nodes.getNodeAs<Expr>(PointerArithmeticPointerTag)) {}
563
564
0
  static bool classof(const Gadget *G) {
565
0
    return G->getKind() == Kind::PointerArithmetic;
566
0
  }
567
568
481
  static Matcher matcher() {
569
481
    auto HasIntegerType = anyOf(hasType(isInteger()), hasType(enumType()));
570
481
    auto PtrAtRight =
571
481
        allOf(hasOperatorName("+"),
572
481
              hasRHS(expr(hasPointerType()).bind(PointerArithmeticPointerTag)),
573
481
              hasLHS(HasIntegerType));
574
481
    auto PtrAtLeft =
575
481
        allOf(anyOf(hasOperatorName("+"), hasOperatorName("-"),
576
481
                    hasOperatorName("+="), hasOperatorName("-=")),
577
481
              hasLHS(expr(hasPointerType()).bind(PointerArithmeticPointerTag)),
578
481
              hasRHS(HasIntegerType));
579
580
481
    return stmt(binaryOperator(anyOf(PtrAtLeft, PtrAtRight))
581
481
                    .bind(PointerArithmeticTag));
582
481
  }
583
584
93
  const Stmt *getBaseStmt() const override { return PA; }
585
586
79
  DeclUseList getClaimedVarUseSites() const override {
587
79
    if (const auto *DRE = dyn_cast<DeclRefExpr>(Ptr->IgnoreParenImpCasts())) {
588
65
      return {DRE};
589
65
    }
590
591
14
    return {};
592
79
  }
593
  // FIXME: pointer adding zero should be fine
594
  // FIXME: this gadge will need a fix-it
595
};
596
597
/// A pointer initialization expression of the form:
598
///  \code
599
///  int *p = q;
600
///  \endcode
601
class PointerInitGadget : public FixableGadget {
602
private:
603
  static constexpr const char *const PointerInitLHSTag = "ptrInitLHS";
604
  static constexpr const char *const PointerInitRHSTag = "ptrInitRHS";
605
  const VarDecl * PtrInitLHS;         // the LHS pointer expression in `PI`
606
  const DeclRefExpr * PtrInitRHS;         // the RHS pointer expression in `PI`
607
608
public:
609
  PointerInitGadget(const MatchFinder::MatchResult &Result)
610
38
      : FixableGadget(Kind::PointerInit),
611
38
    PtrInitLHS(Result.Nodes.getNodeAs<VarDecl>(PointerInitLHSTag)),
612
38
    PtrInitRHS(Result.Nodes.getNodeAs<DeclRefExpr>(PointerInitRHSTag)) {}
613
614
0
  static bool classof(const Gadget *G) {
615
0
    return G->getKind() == Kind::PointerInit;
616
0
  }
617
618
369
  static Matcher matcher() {
619
369
    auto PtrInitStmt = declStmt(hasSingleDecl(varDecl(
620
369
                                 hasInitializer(ignoringImpCasts(declRefExpr(
621
369
                                                  hasPointerType(),
622
369
                                                    toSupportedVariable()).
623
369
                                                  bind(PointerInitRHSTag)))).
624
369
                                              bind(PointerInitLHSTag)));
625
626
369
    return stmt(PtrInitStmt);
627
369
  }
628
629
  virtual std::optional<FixItList> getFixits(const Strategy &S) const override;
630
631
4
  virtual const Stmt *getBaseStmt() const override {
632
    // FIXME: This needs to be the entire DeclStmt, assuming that this method
633
    // makes sense at all on a FixableGadget.
634
4
    return PtrInitRHS;
635
4
  }
636
637
76
  virtual DeclUseList getClaimedVarUseSites() const override {
638
76
    return DeclUseList{PtrInitRHS};
639
76
  }
640
641
  virtual std::optional<std::pair<const VarDecl *, const VarDecl *>>
642
33
  getStrategyImplications() const override {
643
33
      return std::make_pair(PtrInitLHS,
644
33
                            cast<VarDecl>(PtrInitRHS->getDecl()));
645
33
  }
646
};
647
648
/// A pointer assignment expression of the form:
649
///  \code
650
///  p = q;
651
///  \endcode
652
class PointerAssignmentGadget : public FixableGadget {
653
private:
654
  static constexpr const char *const PointerAssignLHSTag = "ptrLHS";
655
  static constexpr const char *const PointerAssignRHSTag = "ptrRHS";
656
  const DeclRefExpr * PtrLHS;         // the LHS pointer expression in `PA`
657
  const DeclRefExpr * PtrRHS;         // the RHS pointer expression in `PA`
658
659
public:
660
  PointerAssignmentGadget(const MatchFinder::MatchResult &Result)
661
165
      : FixableGadget(Kind::PointerAssignment),
662
165
    PtrLHS(Result.Nodes.getNodeAs<DeclRefExpr>(PointerAssignLHSTag)),
663
165
    PtrRHS(Result.Nodes.getNodeAs<DeclRefExpr>(PointerAssignRHSTag)) {}
664
665
0
  static bool classof(const Gadget *G) {
666
0
    return G->getKind() == Kind::PointerAssignment;
667
0
  }
668
669
369
  static Matcher matcher() {
670
369
    auto PtrAssignExpr = binaryOperator(allOf(hasOperatorName("="),
671
369
      hasRHS(ignoringParenImpCasts(declRefExpr(hasPointerType(),
672
369
                                               toSupportedVariable()).
673
369
                                   bind(PointerAssignRHSTag))),
674
369
                                   hasLHS(declRefExpr(hasPointerType(),
675
369
                                                      toSupportedVariable()).
676
369
                                          bind(PointerAssignLHSTag))));
677
678
369
    return stmt(isInUnspecifiedUntypedContext(PtrAssignExpr));
679
369
  }
680
681
  virtual std::optional<FixItList> getFixits(const Strategy &S) const override;
682
683
45
  virtual const Stmt *getBaseStmt() const override {
684
    // FIXME: This should be the binary operator, assuming that this method
685
    // makes sense at all on a FixableGadget.
686
45
    return PtrLHS;
687
45
  }
688
689
324
  virtual DeclUseList getClaimedVarUseSites() const override {
690
324
    return DeclUseList{PtrLHS, PtrRHS};
691
324
  }
692
693
  virtual std::optional<std::pair<const VarDecl *, const VarDecl *>>
694
299
  getStrategyImplications() const override {
695
299
    return std::make_pair(cast<VarDecl>(PtrLHS->getDecl()),
696
299
                          cast<VarDecl>(PtrRHS->getDecl()));
697
299
  }
698
};
699
700
/// A call of a function or method that performs unchecked buffer operations
701
/// over one of its pointer parameters.
702
class UnsafeBufferUsageAttrGadget : public WarningGadget {
703
  constexpr static const char *const OpTag = "call_expr";
704
  const CallExpr *Op;
705
706
public:
707
  UnsafeBufferUsageAttrGadget(const MatchFinder::MatchResult &Result)
708
23
      : WarningGadget(Kind::UnsafeBufferUsageAttr),
709
23
        Op(Result.Nodes.getNodeAs<CallExpr>(OpTag)) {}
710
711
0
  static bool classof(const Gadget *G) {
712
0
    return G->getKind() == Kind::UnsafeBufferUsageAttr;
713
0
  }
714
715
481
  static Matcher matcher() {
716
481
    return stmt(callExpr(callee(functionDecl(hasAttr(attr::UnsafeBufferUsage))))
717
481
                    .bind(OpTag));
718
481
  }
719
23
  const Stmt *getBaseStmt() const override { return Op; }
720
721
19
  DeclUseList getClaimedVarUseSites() const override { return {}; }
722
};
723
724
// Represents expressions of the form `DRE[*]` in the Unspecified Lvalue
725
// Context (see `isInUnspecifiedLvalueContext`).
726
// Note here `[]` is the built-in subscript operator.
727
class ULCArraySubscriptGadget : public FixableGadget {
728
private:
729
  static constexpr const char *const ULCArraySubscriptTag =
730
      "ArraySubscriptUnderULC";
731
  const ArraySubscriptExpr *Node;
732
733
public:
734
  ULCArraySubscriptGadget(const MatchFinder::MatchResult &Result)
735
420
      : FixableGadget(Kind::ULCArraySubscript),
736
420
        Node(Result.Nodes.getNodeAs<ArraySubscriptExpr>(ULCArraySubscriptTag)) {
737
420
    assert(Node != nullptr && "Expecting a non-null matching result");
738
420
  }
739
740
0
  static bool classof(const Gadget *G) {
741
0
    return G->getKind() == Kind::ULCArraySubscript;
742
0
  }
743
744
369
  static Matcher matcher() {
745
369
    auto ArrayOrPtr = anyOf(hasPointerType(), hasArrayType());
746
369
    auto BaseIsArrayOrPtrDRE =
747
369
        hasBase(ignoringParenImpCasts(declRefExpr(ArrayOrPtr,
748
369
                                                  toSupportedVariable())));
749
369
    auto Target =
750
369
        arraySubscriptExpr(BaseIsArrayOrPtrDRE).bind(ULCArraySubscriptTag);
751
752
369
    return expr(isInUnspecifiedLvalueContext(Target));
753
369
  }
754
755
  virtual std::optional<FixItList> getFixits(const Strategy &S) const override;
756
757
8
  virtual const Stmt *getBaseStmt() const override { return Node; }
758
759
838
  virtual DeclUseList getClaimedVarUseSites() const override {
760
838
    if (const auto *DRE =
761
838
            dyn_cast<DeclRefExpr>(Node->getBase()->IgnoreImpCasts())) {
762
838
      return {DRE};
763
838
    }
764
0
    return {};
765
838
  }
766
};
767
768
// Fixable gadget to handle stand alone pointers of the form `UPC(DRE)` in the
769
// unspecified pointer context (isInUnspecifiedPointerContext). The gadget emits
770
// fixit of the form `UPC(DRE.data())`.
771
class UPCStandalonePointerGadget : public FixableGadget {
772
private:
773
  static constexpr const char *const DeclRefExprTag = "StandalonePointer";
774
  const DeclRefExpr *Node;
775
776
public:
777
  UPCStandalonePointerGadget(const MatchFinder::MatchResult &Result)
778
50
      : FixableGadget(Kind::UPCStandalonePointer),
779
50
        Node(Result.Nodes.getNodeAs<DeclRefExpr>(DeclRefExprTag)) {
780
50
    assert(Node != nullptr && "Expecting a non-null matching result");
781
50
  }
782
783
0
  static bool classof(const Gadget *G) {
784
0
    return G->getKind() == Kind::UPCStandalonePointer;
785
0
  }
786
787
369
  static Matcher matcher() {
788
369
    auto ArrayOrPtr = anyOf(hasPointerType(), hasArrayType());
789
369
    auto target = expr(
790
369
        ignoringParenImpCasts(declRefExpr(allOf(ArrayOrPtr,
791
369
                              toSupportedVariable())).bind(DeclRefExprTag)));
792
369
    return stmt(isInUnspecifiedPointerContext(target));
793
369
  }
794
795
  virtual std::optional<FixItList> getFixits(const Strategy &S) const override;
796
797
0
  virtual const Stmt *getBaseStmt() const override { return Node; }
798
799
92
  virtual DeclUseList getClaimedVarUseSites() const override {
800
92
    return {Node};
801
92
  }
802
};
803
804
class PointerDereferenceGadget : public FixableGadget {
805
  static constexpr const char *const BaseDeclRefExprTag = "BaseDRE";
806
  static constexpr const char *const OperatorTag = "op";
807
808
  const DeclRefExpr *BaseDeclRefExpr = nullptr;
809
  const UnaryOperator *Op = nullptr;
810
811
public:
812
  PointerDereferenceGadget(const MatchFinder::MatchResult &Result)
813
19
      : FixableGadget(Kind::PointerDereference),
814
        BaseDeclRefExpr(
815
19
            Result.Nodes.getNodeAs<DeclRefExpr>(BaseDeclRefExprTag)),
816
19
        Op(Result.Nodes.getNodeAs<UnaryOperator>(OperatorTag)) {}
817
818
0
  static bool classof(const Gadget *G) {
819
0
    return G->getKind() == Kind::PointerDereference;
820
0
  }
821
822
369
  static Matcher matcher() {
823
369
    auto Target =
824
369
        unaryOperator(
825
369
            hasOperatorName("*"),
826
369
            has(expr(ignoringParenImpCasts(
827
369
                declRefExpr(toSupportedVariable()).bind(BaseDeclRefExprTag)))))
828
369
            .bind(OperatorTag);
829
830
369
    return expr(isInUnspecifiedLvalueContext(Target));
831
369
  }
832
833
38
  DeclUseList getClaimedVarUseSites() const override {
834
38
    return {BaseDeclRefExpr};
835
38
  }
836
837
0
  virtual const Stmt *getBaseStmt() const final { return Op; }
838
839
  virtual std::optional<FixItList> getFixits(const Strategy &S) const override;
840
};
841
842
// Represents expressions of the form `&DRE[any]` in the Unspecified Pointer
843
// Context (see `isInUnspecifiedPointerContext`).
844
// Note here `[]` is the built-in subscript operator.
845
class UPCAddressofArraySubscriptGadget : public FixableGadget {
846
private:
847
  static constexpr const char *const UPCAddressofArraySubscriptTag =
848
      "AddressofArraySubscriptUnderUPC";
849
  const UnaryOperator *Node; // the `&DRE[any]` node
850
851
public:
852
  UPCAddressofArraySubscriptGadget(const MatchFinder::MatchResult &Result)
853
18
      : FixableGadget(Kind::ULCArraySubscript),
854
18
        Node(Result.Nodes.getNodeAs<UnaryOperator>(
855
18
            UPCAddressofArraySubscriptTag)) {
856
18
    assert(Node != nullptr && "Expecting a non-null matching result");
857
18
  }
858
859
0
  static bool classof(const Gadget *G) {
860
0
    return G->getKind() == Kind::UPCAddressofArraySubscript;
861
0
  }
862
863
369
  static Matcher matcher() {
864
369
    return expr(isInUnspecifiedPointerContext(expr(ignoringImpCasts(
865
369
        unaryOperator(hasOperatorName("&"),
866
369
                      hasUnaryOperand(arraySubscriptExpr(
867
369
                          hasBase(ignoringParenImpCasts(declRefExpr(
868
369
                                                  toSupportedVariable()))))))
869
369
            .bind(UPCAddressofArraySubscriptTag)))));
870
369
  }
871
872
  virtual std::optional<FixItList> getFixits(const Strategy &) const override;
873
874
0
  virtual const Stmt *getBaseStmt() const override { return Node; }
875
876
53
  virtual DeclUseList getClaimedVarUseSites() const override {
877
53
    const auto *ArraySubst = cast<ArraySubscriptExpr>(Node->getSubExpr());
878
53
    const auto *DRE =
879
53
        cast<DeclRefExpr>(ArraySubst->getBase()->IgnoreImpCasts());
880
53
    return {DRE};
881
53
  }
882
};
883
} // namespace
884
885
namespace {
886
// An auxiliary tracking facility for the fixit analysis. It helps connect
887
// declarations to its uses and make sure we've covered all uses with our
888
// analysis before we try to fix the declaration.
889
class DeclUseTracker {
890
  using UseSetTy = SmallSet<const DeclRefExpr *, 16>;
891
  using DefMapTy = DenseMap<const VarDecl *, const DeclStmt *>;
892
893
  // Allocate on the heap for easier move.
894
  std::unique_ptr<UseSetTy> Uses{std::make_unique<UseSetTy>()};
895
  DefMapTy Defs{};
896
897
public:
898
481
  DeclUseTracker() = default;
899
  DeclUseTracker(const DeclUseTracker &) = delete; // Let's avoid copies.
900
  DeclUseTracker &operator=(const DeclUseTracker &) = delete;
901
481
  DeclUseTracker(DeclUseTracker &&) = default;
902
  DeclUseTracker &operator=(DeclUseTracker &&) = default;
903
904
  // Start tracking a freshly discovered DRE.
905
1.21k
  void discoverUse(const DeclRefExpr *DRE) { Uses->insert(DRE); }
906
907
  // Stop tracking the DRE as it's been fully figured out.
908
927
  void claimUse(const DeclRefExpr *DRE) {
909
927
    assert(Uses->count(DRE) &&
910
927
           "DRE not found or claimed by multiple matchers!");
911
927
    Uses->erase(DRE);
912
927
  }
913
914
  // A variable is unclaimed if at least one use is unclaimed.
915
591
  bool hasUnclaimedUses(const VarDecl *VD) const {
916
    // FIXME: Can this be less linear? Maybe maintain a map from VDs to DREs?
917
591
    return any_of(*Uses, [VD](const DeclRefExpr *DRE) {
918
237
      return DRE->getDecl()->getCanonicalDecl() == VD->getCanonicalDecl();
919
237
    });
920
591
  }
921
922
76
  UseSetTy getUnclaimedUses(const VarDecl *VD) const {
923
76
    UseSetTy ReturnSet;
924
182
    for (auto use : *Uses) {
925
182
      if (use->getDecl()->getCanonicalDecl() == VD->getCanonicalDecl()) {
926
119
        ReturnSet.insert(use);
927
119
      }
928
182
    }
929
76
    return ReturnSet;
930
76
  }
931
932
677
  void discoverDecl(const DeclStmt *DS) {
933
683
    for (const Decl *D : DS->decls()) {
934
683
      if (const auto *VD = dyn_cast<VarDecl>(D)) {
935
        // FIXME: Assertion temporarily disabled due to a bug in
936
        // ASTMatcher internal behavior in presence of GNU
937
        // statement-expressions. We need to properly investigate this
938
        // because it can screw up our algorithm in other ways.
939
        // assert(Defs.count(VD) == 0 && "Definition already discovered!");
940
680
        Defs[VD] = DS;
941
680
      }
942
683
    }
943
677
  }
944
945
285
  const DeclStmt *lookupDecl(const VarDecl *VD) const {
946
285
    return Defs.lookup(VD);
947
285
  }
948
};
949
} // namespace
950
951
namespace {
952
// Strategy is a map from variables to the way we plan to emit fixes for
953
// these variables. It is figured out gradually by trying different fixes
954
// for different variables depending on gadgets in which these variables
955
// participate.
956
class Strategy {
957
public:
958
  enum class Kind {
959
    Wontfix,  // We don't plan to emit a fixit for this variable.
960
    Span,     // We recommend replacing the variable with std::span.
961
    Iterator, // We recommend replacing the variable with std::span::iterator.
962
    Array,    // We recommend replacing the variable with std::array.
963
    Vector    // We recommend replacing the variable with std::vector.
964
  };
965
966
private:
967
  using MapTy = llvm::DenseMap<const VarDecl *, Kind>;
968
969
  MapTy Map;
970
971
public:
972
337
  Strategy() = default;
973
  Strategy(const Strategy &) = delete; // Let's avoid copies.
974
  Strategy &operator=(const Strategy &) = delete;
975
  Strategy(Strategy &&) = default;
976
  Strategy &operator=(Strategy &&) = default;
977
978
467
  void set(const VarDecl *VD, Kind K) { Map[VD] = K; }
979
980
1.76k
  Kind lookup(const VarDecl *VD) const {
981
1.76k
    auto I = Map.find(VD);
982
1.76k
    if (I == Map.end())
983
138
      return Kind::Wontfix;
984
985
1.62k
    return I->second;
986
1.76k
  }
987
};
988
} // namespace
989
990
991
// Representing a pointer type expression of the form `++Ptr` in an Unspecified
992
// Pointer Context (UPC):
993
class UPCPreIncrementGadget : public FixableGadget {
994
private:
995
  static constexpr const char *const UPCPreIncrementTag =
996
    "PointerPreIncrementUnderUPC";
997
  const UnaryOperator *Node; // the `++Ptr` node
998
999
public:
1000
  UPCPreIncrementGadget(const MatchFinder::MatchResult &Result)
1001
34
    : FixableGadget(Kind::UPCPreIncrement),
1002
34
      Node(Result.Nodes.getNodeAs<UnaryOperator>(UPCPreIncrementTag)) {
1003
34
    assert(Node != nullptr && "Expecting a non-null matching result");
1004
34
  }
1005
1006
0
  static bool classof(const Gadget *G) {
1007
0
    return G->getKind() == Kind::UPCPreIncrement;
1008
0
  }
1009
1010
369
  static Matcher matcher() {
1011
    // Note here we match `++Ptr` for any expression `Ptr` of pointer type.
1012
    // Although currently we can only provide fix-its when `Ptr` is a DRE, we
1013
    // can have the matcher be general, so long as `getClaimedVarUseSites` does
1014
    // things right.
1015
369
    return stmt(isInUnspecifiedPointerContext(expr(ignoringImpCasts(
1016
369
                    unaryOperator(isPreInc(),
1017
369
                      hasUnaryOperand(declRefExpr(
1018
369
                                                    toSupportedVariable()))
1019
369
                      ).bind(UPCPreIncrementTag)))));
1020
369
  }
1021
1022
  virtual std::optional<FixItList> getFixits(const Strategy &S) const override;
1023
1024
28
  virtual const Stmt *getBaseStmt() const override { return Node; }
1025
1026
96
  virtual DeclUseList getClaimedVarUseSites() const override {
1027
96
    return {dyn_cast<DeclRefExpr>(Node->getSubExpr())};
1028
96
  }
1029
};
1030
1031
// Representing a fixable expression of the form `*(ptr + 123)` or `*(123 +
1032
// ptr)`:
1033
class DerefSimplePtrArithFixableGadget : public FixableGadget {
1034
  static constexpr const char *const BaseDeclRefExprTag = "BaseDRE";
1035
  static constexpr const char *const DerefOpTag = "DerefOp";
1036
  static constexpr const char *const AddOpTag = "AddOp";
1037
  static constexpr const char *const OffsetTag = "Offset";
1038
1039
  const DeclRefExpr *BaseDeclRefExpr = nullptr;
1040
  const UnaryOperator *DerefOp = nullptr;
1041
  const BinaryOperator *AddOp = nullptr;
1042
  const IntegerLiteral *Offset = nullptr;
1043
1044
public:
1045
  DerefSimplePtrArithFixableGadget(const MatchFinder::MatchResult &Result)
1046
29
      : FixableGadget(Kind::DerefSimplePtrArithFixable),
1047
        BaseDeclRefExpr(
1048
29
            Result.Nodes.getNodeAs<DeclRefExpr>(BaseDeclRefExprTag)),
1049
29
        DerefOp(Result.Nodes.getNodeAs<UnaryOperator>(DerefOpTag)),
1050
29
        AddOp(Result.Nodes.getNodeAs<BinaryOperator>(AddOpTag)),
1051
29
        Offset(Result.Nodes.getNodeAs<IntegerLiteral>(OffsetTag)) {}
1052
1053
369
  static Matcher matcher() {
1054
    // clang-format off
1055
369
    auto ThePtr = expr(hasPointerType(),
1056
369
                       ignoringImpCasts(declRefExpr(toSupportedVariable()).
1057
369
                                        bind(BaseDeclRefExprTag)));
1058
369
    auto PlusOverPtrAndInteger = expr(anyOf(
1059
369
          binaryOperator(hasOperatorName("+"), hasLHS(ThePtr),
1060
369
                         hasRHS(integerLiteral().bind(OffsetTag)))
1061
369
                         .bind(AddOpTag),
1062
369
          binaryOperator(hasOperatorName("+"), hasRHS(ThePtr),
1063
369
                         hasLHS(integerLiteral().bind(OffsetTag)))
1064
369
                         .bind(AddOpTag)));
1065
369
    return isInUnspecifiedLvalueContext(unaryOperator(
1066
369
        hasOperatorName("*"),
1067
369
        hasUnaryOperand(ignoringParens(PlusOverPtrAndInteger)))
1068
369
        .bind(DerefOpTag));
1069
    // clang-format on
1070
369
  }
1071
1072
  virtual std::optional<FixItList> getFixits(const Strategy &s) const final;
1073
1074
  // TODO remove this method from FixableGadget interface
1075
0
  virtual const Stmt *getBaseStmt() const final { return nullptr; }
1076
1077
58
  virtual DeclUseList getClaimedVarUseSites() const final {
1078
58
    return {BaseDeclRefExpr};
1079
58
  }
1080
};
1081
1082
/// Scan the function and return a list of gadgets found with provided kits.
1083
static std::tuple<FixableGadgetList, WarningGadgetList, DeclUseTracker>
1084
findGadgets(const Decl *D, const UnsafeBufferUsageHandler &Handler,
1085
481
            bool EmitSuggestions) {
1086
1087
481
  struct GadgetFinderCallback : MatchFinder::MatchCallback {
1088
481
    FixableGadgetList FixableGadgets;
1089
481
    WarningGadgetList WarningGadgets;
1090
481
    DeclUseTracker Tracker;
1091
1092
3.60k
    void run(const MatchFinder::MatchResult &Result) override {
1093
      // In debug mode, assert that we've found exactly one gadget.
1094
      // This helps us avoid conflicts in .bind() tags.
1095
#if NDEBUG
1096
#define NEXT return
1097
#else
1098
3.60k
      [[maybe_unused]] int numFound = 0;
1099
3.60k
#define NEXT ++numFound
1100
3.60k
#endif
1101
1102
3.60k
      if (const auto *DRE = Result.Nodes.getNodeAs<DeclRefExpr>("any_dre")) {
1103
1.21k
        Tracker.discoverUse(DRE);
1104
1.21k
        NEXT;
1105
1.21k
      }
1106
1107
3.60k
      if (const auto *DS = Result.Nodes.getNodeAs<DeclStmt>("any_ds")) {
1108
677
        Tracker.discoverDecl(DS);
1109
677
        NEXT;
1110
677
      }
1111
1112
      // Figure out which matcher we've found, and call the appropriate
1113
      // subclass constructor.
1114
      // FIXME: Can we do this more logarithmically?
1115
3.60k
#define FIXABLE_GADGET(name)                                                   \
1116
28.8k
  if (Result.Nodes.getNodeAs<Stmt>(#name)) {                                   \
1117
773
    FixableGadgets.push_back(std::make_unique<name##Gadget>(Result));          \
1118
773
    NEXT;                                                                      \
1119
773
  }
1120
3.60k
#include "clang/Analysis/Analyses/UnsafeBufferUsageGadgets.def"
1121
3.60k
#define WARNING_GADGET(name)                                                   \
1122
18.0k
  if (Result.Nodes.getNodeAs<Stmt>(#name)) {                                   \
1123
938
    WarningGadgets.push_back(std::make_unique<name##Gadget>(Result));          \
1124
938
    NEXT;                                                                      \
1125
938
  }
1126
3.60k
#include "clang/Analysis/Analyses/UnsafeBufferUsageGadgets.def"
1127
1128
3.60k
      assert(numFound >= 1 && "Gadgets not found in match result!");
1129
3.60k
      assert(numFound <= 1 && "Conflicting bind tags in gadgets!");
1130
3.60k
    }
1131
481
  };
1132
1133
481
  MatchFinder M;
1134
481
  GadgetFinderCallback CB;
1135
1136
  // clang-format off
1137
481
  M.addMatcher(
1138
481
      stmt(
1139
481
        forEachDescendantEvaluatedStmt(stmt(anyOf(
1140
          // Add Gadget::matcher() for every gadget in the registry.
1141
481
#define WARNING_GADGET(x)                                                      \
1142
2.40k
          allOf(x ## Gadget::matcher().bind(#x),                               \
1143
2.40k
                notInSafeBufferOptOut(&Handler)),
1144
481
#include "clang/Analysis/Analyses/UnsafeBufferUsageGadgets.def"
1145
            // Avoid a hanging comma.
1146
481
            unless(stmt())
1147
481
        )))
1148
481
    ),
1149
481
    &CB
1150
481
  );
1151
  // clang-format on
1152
1153
481
  if (EmitSuggestions) {
1154
    // clang-format off
1155
369
    M.addMatcher(
1156
369
        stmt(
1157
369
          forEachDescendantStmt(stmt(eachOf(
1158
369
#define FIXABLE_GADGET(x)                                                      \
1159
2.95k
            x ## Gadget::matcher().bind(#x),
1160
369
#include "clang/Analysis/Analyses/UnsafeBufferUsageGadgets.def"
1161
            // In parallel, match all DeclRefExprs so that to find out
1162
            // whether there are any uncovered by gadgets.
1163
369
            declRefExpr(anyOf(hasPointerType(), hasArrayType()),
1164
369
                        to(anyOf(varDecl(), bindingDecl()))).bind("any_dre"),
1165
            // Also match DeclStmts because we'll need them when fixing
1166
            // their underlying VarDecls that otherwise don't have
1167
            // any backreferences to DeclStmts.
1168
369
            declStmt().bind("any_ds")
1169
369
          )))
1170
369
      ),
1171
369
      &CB
1172
369
    );
1173
    // clang-format on
1174
369
  }
1175
1176
481
  M.match(*D->getBody(), D->getASTContext());
1177
481
  return {std::move(CB.FixableGadgets), std::move(CB.WarningGadgets),
1178
481
          std::move(CB.Tracker)};
1179
481
}
1180
1181
// Compares AST nodes by source locations.
1182
template <typename NodeTy> struct CompareNode {
1183
3.83k
  bool operator()(const NodeTy *N1, const NodeTy *N2) const {
1184
3.83k
    return N1->getBeginLoc().getRawEncoding() <
1185
3.83k
           N2->getBeginLoc().getRawEncoding();
1186
3.83k
  }
1187
};
1188
1189
struct WarningGadgetSets {
1190
  std::map<const VarDecl *, std::set<const WarningGadget *>,
1191
           // To keep keys sorted by their locations in the map so that the
1192
           // order is deterministic:
1193
           CompareNode<VarDecl>>
1194
      byVar;
1195
  // These Gadgets are not related to pointer variables (e. g. temporaries).
1196
  llvm::SmallVector<const WarningGadget *, 16> noVar;
1197
};
1198
1199
static WarningGadgetSets
1200
337
groupWarningGadgetsByVar(const WarningGadgetList &AllUnsafeOperations) {
1201
337
  WarningGadgetSets result;
1202
  // If some gadgets cover more than one
1203
  // variable, they'll appear more than once in the map.
1204
684
  for (auto &G : AllUnsafeOperations) {
1205
684
    DeclUseList ClaimedVarUseSites = G->getClaimedVarUseSites();
1206
1207
684
    bool AssociatedWithVarDecl = false;
1208
684
    for (const DeclRefExpr *DRE : ClaimedVarUseSites) {
1209
598
      if (const auto *VD = dyn_cast<VarDecl>(DRE->getDecl())) {
1210
589
        result.byVar[VD].insert(G.get());
1211
589
        AssociatedWithVarDecl = true;
1212
589
      }
1213
598
    }
1214
1215
684
    if (!AssociatedWithVarDecl) {
1216
95
      result.noVar.push_back(G.get());
1217
95
      continue;
1218
95
    }
1219
684
  }
1220
337
  return result;
1221
337
}
1222
1223
struct FixableGadgetSets {
1224
  std::map<const VarDecl *, std::set<const FixableGadget *>,
1225
           // To keep keys sorted by their locations in the map so that the
1226
           // order is deterministic:
1227
           CompareNode<VarDecl>>
1228
      byVar;
1229
};
1230
1231
static FixableGadgetSets
1232
337
groupFixablesByVar(FixableGadgetList &&AllFixableOperations) {
1233
337
  FixableGadgetSets FixablesForUnsafeVars;
1234
765
  for (auto &F : AllFixableOperations) {
1235
765
    DeclUseList DREs = F->getClaimedVarUseSites();
1236
1237
927
    for (const DeclRefExpr *DRE : DREs) {
1238
927
      if (const auto *VD = dyn_cast<VarDecl>(DRE->getDecl())) {
1239
927
        FixablesForUnsafeVars.byVar[VD].insert(F.get());
1240
927
      }
1241
927
    }
1242
765
  }
1243
337
  return FixablesForUnsafeVars;
1244
337
}
1245
1246
bool clang::internal::anyConflict(const SmallVectorImpl<FixItHint> &FixIts,
1247
282
                                  const SourceManager &SM) {
1248
  // A simple interval overlap detection algorithm.  Sorts all ranges by their
1249
  // begin location then finds the first overlap in one pass.
1250
282
  std::vector<const FixItHint *> All; // a copy of `FixIts`
1251
1252
282
  for (const FixItHint &H : FixIts)
1253
1.67k
    All.push_back(&H);
1254
282
  std::sort(All.begin(), All.end(),
1255
3.79k
            [&SM](const FixItHint *H1, const FixItHint *H2) {
1256
3.79k
              return SM.isBeforeInTranslationUnit(H1->RemoveRange.getBegin(),
1257
3.79k
                                                  H2->RemoveRange.getBegin());
1258
3.79k
            });
1259
1260
282
  const FixItHint *CurrHint = nullptr;
1261
1262
1.67k
  for (const FixItHint *Hint : All) {
1263
1.67k
    if (!CurrHint ||
1264
1.67k
        SM.isBeforeInTranslationUnit(CurrHint->RemoveRange.getEnd(),
1265
1.66k
                                     Hint->RemoveRange.getBegin())) {
1266
      // Either to initialize `CurrHint` or `CurrHint` does not
1267
      // overlap with `Hint`:
1268
1.66k
      CurrHint = Hint;
1269
1.66k
    } else
1270
      // In case `Hint` overlaps the `CurrHint`, we found at least one
1271
      // conflict:
1272
4
      return true;
1273
1.67k
  }
1274
278
  return false;
1275
282
}
1276
1277
std::optional<FixItList>
1278
249
PointerAssignmentGadget::getFixits(const Strategy &S) const {
1279
249
  const auto *LeftVD = cast<VarDecl>(PtrLHS->getDecl());
1280
249
  const auto *RightVD = cast<VarDecl>(PtrRHS->getDecl());
1281
249
  switch (S.lookup(LeftVD)) {
1282
216
    case Strategy::Kind::Span:
1283
216
      if (S.lookup(RightVD) == Strategy::Kind::Span)
1284
204
        return FixItList{};
1285
12
      return std::nullopt;
1286
33
    case Strategy::Kind::Wontfix:
1287
33
      return std::nullopt;
1288
0
    case Strategy::Kind::Iterator:
1289
0
    case Strategy::Kind::Array:
1290
0
    case Strategy::Kind::Vector:
1291
0
      llvm_unreachable("unsupported strategies for FixableGadgets");
1292
249
  }
1293
0
  return std::nullopt;
1294
249
}
1295
1296
std::optional<FixItList>
1297
27
PointerInitGadget::getFixits(const Strategy &S) const {
1298
27
  const auto *LeftVD = PtrInitLHS;
1299
27
  const auto *RightVD = cast<VarDecl>(PtrInitRHS->getDecl());
1300
27
  switch (S.lookup(LeftVD)) {
1301
23
    case Strategy::Kind::Span:
1302
23
      if (S.lookup(RightVD) == Strategy::Kind::Span)
1303
23
        return FixItList{};
1304
0
      return std::nullopt;
1305
4
    case Strategy::Kind::Wontfix:
1306
4
      return std::nullopt;
1307
0
    case Strategy::Kind::Iterator:
1308
0
    case Strategy::Kind::Array:
1309
0
    case Strategy::Kind::Vector:
1310
0
    llvm_unreachable("unsupported strategies for FixableGadgets");
1311
27
  }
1312
0
  return std::nullopt;
1313
27
}
1314
1315
std::optional<FixItList>
1316
278
ULCArraySubscriptGadget::getFixits(const Strategy &S) const {
1317
278
  if (const auto *DRE =
1318
278
          dyn_cast<DeclRefExpr>(Node->getBase()->IgnoreImpCasts()))
1319
278
    if (const auto *VD = dyn_cast<VarDecl>(DRE->getDecl())) {
1320
278
      switch (S.lookup(VD)) {
1321
278
      case Strategy::Kind::Span: {
1322
        // If the index has a negative constant value, we give up as no valid
1323
        // fix-it can be generated:
1324
278
        const ASTContext &Ctx = // FIXME: we need ASTContext to be passed in!
1325
278
            VD->getASTContext();
1326
278
        if (auto ConstVal = Node->getIdx()->getIntegerConstantExpr(Ctx)) {
1327
275
          if (ConstVal->isNegative())
1328
7
            return std::nullopt;
1329
275
        } else 
if (3
!Node->getIdx()->getType()->isUnsignedIntegerType()3
)
1330
1
          return std::nullopt;
1331
        // no-op is a good fix-it, otherwise
1332
270
        return FixItList{};
1333
278
      }
1334
0
      case Strategy::Kind::Wontfix:
1335
0
      case Strategy::Kind::Iterator:
1336
0
      case Strategy::Kind::Array:
1337
0
      case Strategy::Kind::Vector:
1338
0
        llvm_unreachable("unsupported strategies for FixableGadgets");
1339
278
      }
1340
278
    }
1341
0
  return std::nullopt;
1342
278
}
1343
1344
static std::optional<FixItList> // forward declaration
1345
fixUPCAddressofArraySubscriptWithSpan(const UnaryOperator *Node);
1346
1347
std::optional<FixItList>
1348
17
UPCAddressofArraySubscriptGadget::getFixits(const Strategy &S) const {
1349
17
  auto DREs = getClaimedVarUseSites();
1350
17
  const auto *VD = cast<VarDecl>(DREs.front()->getDecl());
1351
1352
17
  switch (S.lookup(VD)) {
1353
17
  case Strategy::Kind::Span:
1354
17
    return fixUPCAddressofArraySubscriptWithSpan(Node);
1355
0
  case Strategy::Kind::Wontfix:
1356
0
  case Strategy::Kind::Iterator:
1357
0
  case Strategy::Kind::Array:
1358
0
  case Strategy::Kind::Vector:
1359
0
    llvm_unreachable("unsupported strategies for FixableGadgets");
1360
17
  }
1361
0
  return std::nullopt; // something went wrong, no fix-it
1362
17
}
1363
1364
// FIXME: this function should be customizable through format
1365
203
static StringRef getEndOfLine() {
1366
203
  static const char *const EOL = "\n";
1367
203
  return EOL;
1368
203
}
1369
1370
// Returns the text indicating that the user needs to provide input there:
1371
430
std::string getUserFillPlaceHolder(StringRef HintTextToUser = "placeholder") {
1372
430
  std::string s = std::string("<# ");
1373
430
  s += HintTextToUser;
1374
430
  s += " #>";
1375
430
  return s;
1376
430
}
1377
1378
// Return the text representation of the given `APInt Val`:
1379
4
static std::string getAPIntText(APInt Val) {
1380
4
  SmallVector<char> Txt;
1381
4
  Val.toString(Txt, 10, true);
1382
  // APInt::toString does not add '\0' to the end of the string for us:
1383
4
  Txt.push_back('\0');
1384
4
  return Txt.data();
1385
4
}
1386
1387
// Return the source location of the last character of the AST `Node`.
1388
template <typename NodeTy>
1389
static std::optional<SourceLocation>
1390
getEndCharLoc(const NodeTy *Node, const SourceManager &SM,
1391
31
              const LangOptions &LangOpts) {
1392
31
  unsigned TkLen = Lexer::MeasureTokenLength(Node->getEndLoc(), SM, LangOpts);
1393
31
  SourceLocation Loc = Node->getEndLoc().getLocWithOffset(TkLen - 1);
1394
1395
31
  if (Loc.isValid())
1396
31
    return Loc;
1397
1398
0
  return std::nullopt;
1399
31
}
UnsafeBufferUsage.cpp:std::__1::optional<clang::SourceLocation> getEndCharLoc<clang::Expr>(clang::Expr const*, clang::SourceManager const&, clang::LangOptions const&)
Line
Count
Source
1391
3
              const LangOptions &LangOpts) {
1392
3
  unsigned TkLen = Lexer::MeasureTokenLength(Node->getEndLoc(), SM, LangOpts);
1393
3
  SourceLocation Loc = Node->getEndLoc().getLocWithOffset(TkLen - 1);
1394
1395
3
  if (Loc.isValid())
1396
3
    return Loc;
1397
1398
0
  return std::nullopt;
1399
3
}
UnsafeBufferUsage.cpp:std::__1::optional<clang::SourceLocation> getEndCharLoc<clang::Stmt>(clang::Stmt const*, clang::SourceManager const&, clang::LangOptions const&)
Line
Count
Source
1391
28
              const LangOptions &LangOpts) {
1392
28
  unsigned TkLen = Lexer::MeasureTokenLength(Node->getEndLoc(), SM, LangOpts);
1393
28
  SourceLocation Loc = Node->getEndLoc().getLocWithOffset(TkLen - 1);
1394
1395
28
  if (Loc.isValid())
1396
28
    return Loc;
1397
1398
0
  return std::nullopt;
1399
28
}
1400
1401
// Return the source location just past the last character of the AST `Node`.
1402
template <typename NodeTy>
1403
static std::optional<SourceLocation> getPastLoc(const NodeTy *Node,
1404
                                                const SourceManager &SM,
1405
594
                                                const LangOptions &LangOpts) {
1406
594
  SourceLocation Loc =
1407
594
      Lexer::getLocForEndOfToken(Node->getEndLoc(), 0, SM, LangOpts);
1408
1409
594
  if (Loc.isValid())
1410
594
    return Loc;
1411
1412
0
  return std::nullopt;
1413
594
}
UnsafeBufferUsage.cpp:std::__1::optional<clang::SourceLocation> getPastLoc<clang::DeclRefExpr>(clang::DeclRefExpr const*, clang::SourceManager const&, clang::LangOptions const&)
Line
Count
Source
1405
28
                                                const LangOptions &LangOpts) {
1406
28
  SourceLocation Loc =
1407
28
      Lexer::getLocForEndOfToken(Node->getEndLoc(), 0, SM, LangOpts);
1408
1409
28
  if (Loc.isValid())
1410
28
    return Loc;
1411
1412
0
  return std::nullopt;
1413
28
}
UnsafeBufferUsage.cpp:std::__1::optional<clang::SourceLocation> getPastLoc<clang::FunctionDecl>(clang::FunctionDecl const*, clang::SourceManager const&, clang::LangOptions const&)
Line
Count
Source
1405
111
                                                const LangOptions &LangOpts) {
1406
111
  SourceLocation Loc =
1407
111
      Lexer::getLocForEndOfToken(Node->getEndLoc(), 0, SM, LangOpts);
1408
1409
111
  if (Loc.isValid())
1410
111
    return Loc;
1411
1412
0
  return std::nullopt;
1413
111
}
UnsafeBufferUsage.cpp:std::__1::optional<clang::SourceLocation> getPastLoc<clang::Expr>(clang::Expr const*, clang::SourceManager const&, clang::LangOptions const&)
Line
Count
Source
1405
397
                                                const LangOptions &LangOpts) {
1406
397
  SourceLocation Loc =
1407
397
      Lexer::getLocForEndOfToken(Node->getEndLoc(), 0, SM, LangOpts);
1408
1409
397
  if (Loc.isValid())
1410
397
    return Loc;
1411
1412
0
  return std::nullopt;
1413
397
}
UnsafeBufferUsage.cpp:std::__1::optional<clang::SourceLocation> getPastLoc<clang::BinaryOperator>(clang::BinaryOperator const*, clang::SourceManager const&, clang::LangOptions const&)
Line
Count
Source
1405
29
                                                const LangOptions &LangOpts) {
1406
29
  SourceLocation Loc =
1407
29
      Lexer::getLocForEndOfToken(Node->getEndLoc(), 0, SM, LangOpts);
1408
1409
29
  if (Loc.isValid())
1410
29
    return Loc;
1411
1412
0
  return std::nullopt;
1413
29
}
UnsafeBufferUsage.cpp:std::__1::optional<clang::SourceLocation> getPastLoc<clang::UnaryOperator>(clang::UnaryOperator const*, clang::SourceManager const&, clang::LangOptions const&)
Line
Count
Source
1405
29
                                                const LangOptions &LangOpts) {
1406
29
  SourceLocation Loc =
1407
29
      Lexer::getLocForEndOfToken(Node->getEndLoc(), 0, SM, LangOpts);
1408
1409
29
  if (Loc.isValid())
1410
29
    return Loc;
1411
1412
0
  return std::nullopt;
1413
29
}
1414
1415
// Return text representation of an `Expr`.
1416
static std::optional<StringRef> getExprText(const Expr *E,
1417
                                            const SourceManager &SM,
1418
181
                                            const LangOptions &LangOpts) {
1419
181
  std::optional<SourceLocation> LastCharLoc = getPastLoc(E, SM, LangOpts);
1420
1421
181
  if (LastCharLoc)
1422
181
    return Lexer::getSourceText(
1423
181
        CharSourceRange::getCharRange(E->getBeginLoc(), *LastCharLoc), SM,
1424
181
        LangOpts);
1425
1426
0
  return std::nullopt;
1427
181
}
1428
1429
// Returns the literal text in `SourceRange SR`, if `SR` is a valid range.
1430
static std::optional<StringRef> getRangeText(SourceRange SR,
1431
                                             const SourceManager &SM,
1432
1.16k
                                             const LangOptions &LangOpts) {
1433
1.16k
  bool Invalid = false;
1434
1.16k
  CharSourceRange CSR = CharSourceRange::getCharRange(SR);
1435
1.16k
  StringRef Text = Lexer::getSourceText(CSR, SM, LangOpts, &Invalid);
1436
1437
1.16k
  if (!Invalid)
1438
1.16k
    return Text;
1439
0
  return std::nullopt;
1440
1.16k
}
1441
1442
// Returns the begin location of the identifier of the given variable
1443
// declaration.
1444
976
static SourceLocation getVarDeclIdentifierLoc(const VarDecl *VD) {
1445
  // According to the implementation of `VarDecl`, `VD->getLocation()` actually
1446
  // returns the begin location of the identifier of the declaration:
1447
976
  return VD->getLocation();
1448
976
}
1449
1450
// Returns the literal text of the identifier of the given variable declaration.
1451
static std::optional<StringRef>
1452
getVarDeclIdentifierText(const VarDecl *VD, const SourceManager &SM,
1453
275
                         const LangOptions &LangOpts) {
1454
275
  SourceLocation ParmIdentBeginLoc = getVarDeclIdentifierLoc(VD);
1455
275
  SourceLocation ParmIdentEndLoc =
1456
275
      Lexer::getLocForEndOfToken(ParmIdentBeginLoc, 0, SM, LangOpts);
1457
1458
275
  if (ParmIdentEndLoc.isMacroID() &&
1459
275
      
!Lexer::isAtEndOfMacroExpansion(ParmIdentEndLoc, SM, LangOpts)0
)
1460
0
    return std::nullopt;
1461
275
  return getRangeText({ParmIdentBeginLoc, ParmIdentEndLoc}, SM, LangOpts);
1462
275
}
1463
1464
// We cannot fix a variable declaration if it has some other specifiers than the
1465
// type specifier.  Because the source ranges of those specifiers could overlap
1466
// with the source range that is being replaced using fix-its.  Especially when
1467
// we often cannot obtain accurate source ranges of cv-qualified type
1468
// specifiers.
1469
// FIXME: also deal with type attributes
1470
static bool hasUnsupportedSpecifiers(const VarDecl *VD,
1471
427
                                     const SourceManager &SM) {
1472
  // AttrRangeOverlapping: true if at least one attribute of `VD` overlaps the
1473
  // source range of `VD`:
1474
427
  bool AttrRangeOverlapping = llvm::any_of(VD->attrs(), [&](Attr *At) -> bool {
1475
1
    return !(SM.isBeforeInTranslationUnit(At->getRange().getEnd(),
1476
1
                                          VD->getBeginLoc())) &&
1477
1
           !(SM.isBeforeInTranslationUnit(VD->getEndLoc(),
1478
0
                                          At->getRange().getBegin()));
1479
1
  });
1480
427
  return VD->isInlineSpecified() || VD->isConstexpr() ||
1481
427
         VD->hasConstantInitialization() || !VD->hasLocalStorage() ||
1482
427
         AttrRangeOverlapping;
1483
427
}
1484
1485
// Returns the `SourceRange` of `D`.  The reason why this function exists is
1486
// that `D->getSourceRange()` may return a range where the end location is the
1487
// starting location of the last token.  The end location of the source range
1488
// returned by this function is the last location of the last token.
1489
static SourceRange getSourceRangeToTokenEnd(const Decl *D,
1490
                                            const SourceManager &SM,
1491
2
                                            LangOptions LangOpts) {
1492
2
  SourceLocation Begin = D->getBeginLoc();
1493
2
  SourceLocation
1494
2
    End = // `D->getEndLoc` should always return the starting location of the
1495
    // last token, so we should get the end of the token
1496
2
    Lexer::getLocForEndOfToken(D->getEndLoc(), 0, SM, LangOpts);
1497
1498
2
  return SourceRange(Begin, End);
1499
2
}
1500
1501
// Returns the text of the pointee type of `T` from a `VarDecl` of a pointer
1502
// type. The text is obtained through from `TypeLoc`s.  Since `TypeLoc` does not
1503
// have source ranges of qualifiers ( The `QualifiedTypeLoc` looks hacky too me
1504
// :( ), `Qualifiers` of the pointee type is returned separately through the
1505
// output parameter `QualifiersToAppend`.
1506
static std::optional<std::string>
1507
getPointeeTypeText(const VarDecl *VD, const SourceManager &SM,
1508
                   const LangOptions &LangOpts,
1509
708
                   std::optional<Qualifiers> *QualifiersToAppend) {
1510
708
  QualType Ty = VD->getType();
1511
708
  QualType PteTy;
1512
1513
708
  assert(Ty->isPointerType() && !Ty->isFunctionPointerType() &&
1514
708
         "Expecting a VarDecl of type of pointer to object type");
1515
708
  PteTy = Ty->getPointeeType();
1516
1517
708
  TypeLoc TyLoc = VD->getTypeSourceInfo()->getTypeLoc().getUnqualifiedLoc();
1518
708
  TypeLoc PteTyLoc;
1519
1520
  // We only deal with the cases that we know `TypeLoc::getNextTypeLoc` returns
1521
  // the `TypeLoc` of the pointee type:
1522
708
  switch (TyLoc.getTypeLocClass()) {
1523
8
  case TypeLoc::ConstantArray:
1524
23
  case TypeLoc::IncompleteArray:
1525
23
  case TypeLoc::VariableArray:
1526
23
  case TypeLoc::DependentSizedArray:
1527
23
  case TypeLoc::Decayed:
1528
23
    assert(isa<ParmVarDecl>(VD) && "An array type shall not be treated as a "
1529
23
                                   "pointer type unless it decays.");
1530
23
    PteTyLoc = TyLoc.getNextTypeLoc();
1531
23
    break;
1532
678
  case TypeLoc::Pointer:
1533
678
    PteTyLoc = TyLoc.castAs<PointerTypeLoc>().getPointeeLoc();
1534
678
    break;
1535
7
  default:
1536
7
    return std::nullopt;
1537
708
  }
1538
701
  if (PteTyLoc.isNull())
1539
    // Sometimes we cannot get a useful `TypeLoc` for the pointee type, e.g.,
1540
    // when the pointer type is `auto`.
1541
0
    return std::nullopt;
1542
1543
701
  SourceLocation IdentLoc = getVarDeclIdentifierLoc(VD);
1544
1545
701
  if (!(IdentLoc.isValid() && PteTyLoc.getSourceRange().isValid())) {
1546
    // We are expecting these locations to be valid. But in some cases, they are
1547
    // not all valid. It is a Clang bug to me and we are not responsible for
1548
    // fixing it.  So we will just give up for now when it happens.
1549
4
    return std::nullopt;
1550
4
  }
1551
1552
  // Note that TypeLoc.getEndLoc() returns the begin location of the last token:
1553
697
  SourceLocation PteEndOfTokenLoc =
1554
697
      Lexer::getLocForEndOfToken(PteTyLoc.getEndLoc(), 0, SM, LangOpts);
1555
1556
697
  if (!PteEndOfTokenLoc.isValid())
1557
    // Sometimes we cannot get the end location of the pointee type, e.g., when
1558
    // there are macros involved.
1559
7
    return std::nullopt;
1560
690
  if (!SM.isBeforeInTranslationUnit(PteEndOfTokenLoc, IdentLoc)) {
1561
    // We only deal with the cases where the source text of the pointee type
1562
    // appears on the left-hand side of the variable identifier completely,
1563
    // including the following forms:
1564
    // `T ident`,
1565
    // `T ident[]`, where `T` is any type.
1566
    // Examples of excluded cases are `T (*ident)[]` or `T ident[][n]`.
1567
6
    return std::nullopt;
1568
6
  }
1569
684
  if (PteTy.hasQualifiers()) {
1570
    // TypeLoc does not provide source ranges for qualifiers (it says it's
1571
    // intentional but seems fishy to me), so we cannot get the full text
1572
    // `PteTy` via source ranges.
1573
24
    *QualifiersToAppend = PteTy.getQualifiers();
1574
24
  }
1575
684
  return getRangeText({PteTyLoc.getBeginLoc(), PteEndOfTokenLoc}, SM, LangOpts)
1576
684
      ->str();
1577
690
}
1578
1579
// Returns the text of the name (with qualifiers) of a `FunctionDecl`.
1580
static std::optional<StringRef> getFunNameText(const FunctionDecl *FD,
1581
                                               const SourceManager &SM,
1582
94
                                               const LangOptions &LangOpts) {
1583
94
  SourceLocation BeginLoc = FD->getQualifier()
1584
94
                                ? 
FD->getQualifierLoc().getBeginLoc()4
1585
94
                                : 
FD->getNameInfo().getBeginLoc()90
;
1586
  // Note that `FD->getNameInfo().getEndLoc()` returns the begin location of the
1587
  // last token:
1588
94
  SourceLocation EndLoc = Lexer::getLocForEndOfToken(
1589
94
      FD->getNameInfo().getEndLoc(), 0, SM, LangOpts);
1590
94
  SourceRange NameRange{BeginLoc, EndLoc};
1591
1592
94
  return getRangeText(NameRange, SM, LangOpts);
1593
94
}
1594
1595
// Returns the text representing a `std::span` type where the element type is
1596
// represented by `EltTyText`.
1597
//
1598
// Note the optional parameter `Qualifiers`: one needs to pass qualifiers
1599
// explicitly if the element type needs to be qualified.
1600
static std::string
1601
getSpanTypeText(StringRef EltTyText,
1602
279
                std::optional<Qualifiers> Quals = std::nullopt) {
1603
279
  const char *const SpanOpen = "std::span<";
1604
1605
279
  if (Quals)
1606
14
    return SpanOpen + EltTyText.str() + ' ' + Quals->getAsString() + '>';
1607
265
  return SpanOpen + EltTyText.str() + '>';
1608
279
}
1609
1610
std::optional<FixItList>
1611
29
DerefSimplePtrArithFixableGadget::getFixits(const Strategy &s) const {
1612
29
  const VarDecl *VD = dyn_cast<VarDecl>(BaseDeclRefExpr->getDecl());
1613
1614
29
  if (VD && s.lookup(VD) == Strategy::Kind::Span) {
1615
29
    ASTContext &Ctx = VD->getASTContext();
1616
    // std::span can't represent elements before its begin()
1617
29
    if (auto ConstVal = Offset->getIntegerConstantExpr(Ctx))
1618
29
      if (ConstVal->isNegative())
1619
0
        return std::nullopt;
1620
1621
    // note that the expr may (oddly) has multiple layers of parens
1622
    // example:
1623
    //   *((..(pointer + 123)..))
1624
    // goal:
1625
    //   pointer[123]
1626
    // Fix-It:
1627
    //   remove '*('
1628
    //   replace ' + ' with '['
1629
    //   replace ')' with ']'
1630
1631
    // example:
1632
    //   *((..(123 + pointer)..))
1633
    // goal:
1634
    //   123[pointer]
1635
    // Fix-It:
1636
    //   remove '*('
1637
    //   replace ' + ' with '['
1638
    //   replace ')' with ']'
1639
1640
29
    const Expr *LHS = AddOp->getLHS(), *RHS = AddOp->getRHS();
1641
29
    const SourceManager &SM = Ctx.getSourceManager();
1642
29
    const LangOptions &LangOpts = Ctx.getLangOpts();
1643
29
    CharSourceRange StarWithTrailWhitespace =
1644
29
        clang::CharSourceRange::getCharRange(DerefOp->getOperatorLoc(),
1645
29
                                             LHS->getBeginLoc());
1646
1647
29
    std::optional<SourceLocation> LHSLocation = getPastLoc(LHS, SM, LangOpts);
1648
29
    if (!LHSLocation)
1649
0
      return std::nullopt;
1650
1651
29
    CharSourceRange PlusWithSurroundingWhitespace =
1652
29
        clang::CharSourceRange::getCharRange(*LHSLocation, RHS->getBeginLoc());
1653
1654
29
    std::optional<SourceLocation> AddOpLocation =
1655
29
        getPastLoc(AddOp, SM, LangOpts);
1656
29
    std::optional<SourceLocation> DerefOpLocation =
1657
29
        getPastLoc(DerefOp, SM, LangOpts);
1658
1659
29
    if (!AddOpLocation || !DerefOpLocation)
1660
0
      return std::nullopt;
1661
1662
29
    CharSourceRange ClosingParenWithPrecWhitespace =
1663
29
        clang::CharSourceRange::getCharRange(*AddOpLocation, *DerefOpLocation);
1664
1665
29
    return FixItList{
1666
29
        {FixItHint::CreateRemoval(StarWithTrailWhitespace),
1667
29
         FixItHint::CreateReplacement(PlusWithSurroundingWhitespace, "["),
1668
29
         FixItHint::CreateReplacement(ClosingParenWithPrecWhitespace, "]")}};
1669
29
  }
1670
0
  return std::nullopt; // something wrong or unsupported, give up
1671
29
}
1672
1673
std::optional<FixItList>
1674
8
PointerDereferenceGadget::getFixits(const Strategy &S) const {
1675
8
  const VarDecl *VD = cast<VarDecl>(BaseDeclRefExpr->getDecl());
1676
8
  switch (S.lookup(VD)) {
1677
8
  case Strategy::Kind::Span: {
1678
8
    ASTContext &Ctx = VD->getASTContext();
1679
8
    SourceManager &SM = Ctx.getSourceManager();
1680
    // Required changes: *(ptr); => (ptr[0]); and *ptr; => ptr[0]
1681
    // Deletes the *operand
1682
8
    CharSourceRange derefRange = clang::CharSourceRange::getCharRange(
1683
8
        Op->getBeginLoc(), Op->getBeginLoc().getLocWithOffset(1));
1684
    // Inserts the [0]
1685
8
    if (auto LocPastOperand =
1686
8
            getPastLoc(BaseDeclRefExpr, SM, Ctx.getLangOpts())) {
1687
8
      return FixItList{{FixItHint::CreateRemoval(derefRange),
1688
8
      FixItHint::CreateInsertion(*LocPastOperand, "[0]")}};
1689
8
    }
1690
0
    break;
1691
8
  }
1692
0
  case Strategy::Kind::Iterator:
1693
0
  case Strategy::Kind::Array:
1694
0
  case Strategy::Kind::Vector:
1695
0
    llvm_unreachable("Strategy not implemented yet!");
1696
0
  case Strategy::Kind::Wontfix:
1697
0
    llvm_unreachable("Invalid strategy!");
1698
8
  }
1699
1700
0
  return std::nullopt;
1701
8
}
1702
1703
// Generates fix-its replacing an expression of the form UPC(DRE) with
1704
// `DRE.data()`
1705
std::optional<FixItList> UPCStandalonePointerGadget::getFixits(const Strategy &S)
1706
20
      const {
1707
20
  const auto VD = cast<VarDecl>(Node->getDecl());
1708
20
  switch (S.lookup(VD)) {
1709
20
    case Strategy::Kind::Span: {
1710
20
      ASTContext &Ctx = VD->getASTContext();
1711
20
      SourceManager &SM = Ctx.getSourceManager();
1712
      // Inserts the .data() after the DRE
1713
20
      std::optional<SourceLocation> EndOfOperand =
1714
20
          getPastLoc(Node, SM, Ctx.getLangOpts());
1715
1716
20
      if (EndOfOperand)
1717
20
        return FixItList{{FixItHint::CreateInsertion(
1718
20
            *EndOfOperand, ".data()")}};
1719
      // FIXME: Points inside a macro expansion.
1720
0
      break;
1721
20
    }
1722
0
    case Strategy::Kind::Wontfix:
1723
0
    case Strategy::Kind::Iterator:
1724
0
    case Strategy::Kind::Array:
1725
0
    case Strategy::Kind::Vector:
1726
0
      llvm_unreachable("unsupported strategies for FixableGadgets");
1727
20
  }
1728
1729
0
  return std::nullopt;
1730
20
}
1731
1732
// Generates fix-its replacing an expression of the form `&DRE[e]` with
1733
// `&DRE.data()[e]`:
1734
static std::optional<FixItList>
1735
17
fixUPCAddressofArraySubscriptWithSpan(const UnaryOperator *Node) {
1736
17
  const auto *ArraySub = cast<ArraySubscriptExpr>(Node->getSubExpr());
1737
17
  const auto *DRE = cast<DeclRefExpr>(ArraySub->getBase()->IgnoreImpCasts());
1738
  // FIXME: this `getASTContext` call is costly, we should pass the
1739
  // ASTContext in:
1740
17
  const ASTContext &Ctx = DRE->getDecl()->getASTContext();
1741
17
  const Expr *Idx = ArraySub->getIdx();
1742
17
  const SourceManager &SM = Ctx.getSourceManager();
1743
17
  const LangOptions &LangOpts = Ctx.getLangOpts();
1744
17
  std::stringstream SS;
1745
17
  bool IdxIsLitZero = false;
1746
1747
17
  if (auto ICE = Idx->getIntegerConstantExpr(Ctx))
1748
12
    if ((*ICE).isZero())
1749
2
      IdxIsLitZero = true;
1750
17
  std::optional<StringRef> DreString = getExprText(DRE, SM, LangOpts);
1751
17
  if (!DreString)
1752
0
    return std::nullopt;
1753
1754
17
  if (IdxIsLitZero) {
1755
    // If the index is literal zero, we produce the most concise fix-it:
1756
2
    SS << (*DreString).str() << ".data()";
1757
15
  } else {
1758
15
    std::optional<StringRef> IndexString = getExprText(Idx, SM, LangOpts);
1759
15
    if (!IndexString)
1760
0
      return std::nullopt;
1761
1762
15
    SS << "&" << (*DreString).str() << ".data()"
1763
15
       << "[" << (*IndexString).str() << "]";
1764
15
  }
1765
17
  return FixItList{
1766
17
      FixItHint::CreateReplacement(Node->getSourceRange(), SS.str())};
1767
17
}
1768
1769
1770
28
std::optional<FixItList> UPCPreIncrementGadget::getFixits(const Strategy &S) const {
1771
28
  DeclUseList DREs = getClaimedVarUseSites();
1772
1773
28
  if (DREs.size() != 1)
1774
0
    return std::nullopt; // In cases of `++Ptr` where `Ptr` is not a DRE, we
1775
                         // give up
1776
28
  if (const VarDecl *VD = dyn_cast<VarDecl>(DREs.front()->getDecl())) {
1777
28
    if (S.lookup(VD) == Strategy::Kind::Span) {
1778
28
      FixItList Fixes;
1779
28
      std::stringstream SS;
1780
28
      const Stmt *PreIncNode = getBaseStmt();
1781
28
      StringRef varName = VD->getName();
1782
28
      const ASTContext &Ctx = VD->getASTContext();
1783
1784
      // To transform UPC(++p) to UPC((p = p.subspan(1)).data()):
1785
28
      SS << "(" << varName.data() << " = " << varName.data()
1786
28
         << ".subspan(1)).data()";
1787
28
      std::optional<SourceLocation> PreIncLocation =
1788
28
          getEndCharLoc(PreIncNode, Ctx.getSourceManager(), Ctx.getLangOpts());
1789
28
      if (!PreIncLocation)
1790
0
        return std::nullopt;
1791
1792
28
      Fixes.push_back(FixItHint::CreateReplacement(
1793
28
          SourceRange(PreIncNode->getBeginLoc(), *PreIncLocation), SS.str()));
1794
28
      return Fixes;
1795
28
    }
1796
28
  }
1797
0
  return std::nullopt; // Not in the cases that we can handle for now, give up.
1798
28
}
1799
1800
1801
// For a non-null initializer `Init` of `T *` type, this function returns
1802
// `FixItHint`s producing a list initializer `{Init,  S}` as a part of a fix-it
1803
// to output stream.
1804
// In many cases, this function cannot figure out the actual extent `S`.  It
1805
// then will use a place holder to replace `S` to ask users to fill `S` in.  The
1806
// initializer shall be used to initialize a variable of type `std::span<T>`.
1807
//
1808
// FIXME: Support multi-level pointers
1809
//
1810
// Parameters:
1811
//   `Init` a pointer to the initializer expression
1812
//   `Ctx` a reference to the ASTContext
1813
static FixItList
1814
FixVarInitializerWithSpan(const Expr *Init, ASTContext &Ctx,
1815
190
                                 const StringRef UserFillPlaceHolder) {
1816
190
  const SourceManager &SM = Ctx.getSourceManager();
1817
190
  const LangOptions &LangOpts = Ctx.getLangOpts();
1818
1819
  // If `Init` has a constant value that is (or equivalent to) a
1820
  // NULL pointer, we use the default constructor to initialize the span
1821
  // object, i.e., a `std:span` variable declaration with no initializer.
1822
  // So the fix-it is just to remove the initializer.
1823
190
  if (Init->isNullPointerConstant(Ctx,
1824
          // FIXME: Why does this function not ask for `const ASTContext
1825
          // &`? It should. Maybe worth an NFC patch later.
1826
190
          Expr::NullPointerConstantValueDependence::
1827
190
              NPC_ValueDependentIsNotNull)) {
1828
3
    std::optional<SourceLocation> InitLocation =
1829
3
        getEndCharLoc(Init, SM, LangOpts);
1830
3
    if (!InitLocation)
1831
0
      return {};
1832
1833
3
    SourceRange SR(Init->getBeginLoc(), *InitLocation);
1834
1835
3
    return {FixItHint::CreateRemoval(SR)};
1836
3
  }
1837
1838
187
  FixItList FixIts{};
1839
187
  std::string ExtentText = UserFillPlaceHolder.data();
1840
187
  StringRef One = "1";
1841
1842
  // Insert `{` before `Init`:
1843
187
  FixIts.push_back(FixItHint::CreateInsertion(Init->getBeginLoc(), "{"));
1844
  // Try to get the data extent. Break into different cases:
1845
187
  if (auto CxxNew = dyn_cast<CXXNewExpr>(Init->IgnoreImpCasts())) {
1846
    // In cases `Init` is `new T[n]` and there is no explicit cast over
1847
    // `Init`, we know that `Init` must evaluates to a pointer to `n` objects
1848
    // of `T`. So the extent is `n` unless `n` has side effects.  Similar but
1849
    // simpler for the case where `Init` is `new T`.
1850
150
    if (const Expr *Ext = CxxNew->getArraySize().value_or(nullptr)) {
1851
150
      if (!Ext->HasSideEffects(Ctx)) {
1852
149
        std::optional<StringRef> ExtentString = getExprText(Ext, SM, LangOpts);
1853
149
        if (!ExtentString)
1854
0
          return {};
1855
149
        ExtentText = *ExtentString;
1856
149
      }
1857
150
    } else 
if (0
!CxxNew->isArray()0
)
1858
      // Although the initializer is not allocating a buffer, the pointer
1859
      // variable could still be used in buffer access operations.
1860
0
      ExtentText = One;
1861
150
  } else 
if (const auto *37
CArrTy37
= Ctx.getAsConstantArrayType(
1862
37
                 Init->IgnoreImpCasts()->getType())) {
1863
    // In cases `Init` is of an array type after stripping off implicit casts,
1864
    // the extent is the array size.  Note that if the array size is not a
1865
    // constant, we cannot use it as the extent.
1866
4
    ExtentText = getAPIntText(CArrTy->getSize());
1867
33
  } else {
1868
    // In cases `Init` is of the form `&Var` after stripping of implicit
1869
    // casts, where `&` is the built-in operator, the extent is 1.
1870
33
    if (auto AddrOfExpr = dyn_cast<UnaryOperator>(Init->IgnoreImpCasts()))
1871
1
      if (AddrOfExpr->getOpcode() == UnaryOperatorKind::UO_AddrOf &&
1872
1
          isa_and_present<DeclRefExpr>(AddrOfExpr->getSubExpr()))
1873
1
        ExtentText = One;
1874
    // TODO: we can handle more cases, e.g., `&a[0]`, `&a`, `std::addressof`,
1875
    // and explicit casting, etc. etc.
1876
33
  }
1877
1878
187
  SmallString<32> StrBuffer{};
1879
187
  std::optional<SourceLocation> LocPassInit = getPastLoc(Init, SM, LangOpts);
1880
1881
187
  if (!LocPassInit)
1882
0
    return {};
1883
1884
187
  StrBuffer.append(", ");
1885
187
  StrBuffer.append(ExtentText);
1886
187
  StrBuffer.append("}");
1887
187
  FixIts.push_back(FixItHint::CreateInsertion(*LocPassInit, StrBuffer.str()));
1888
187
  return FixIts;
1889
187
}
1890
1891
#ifndef NDEBUG
1892
60
#define DEBUG_NOTE_DECL_FAIL(D, Msg)  \
1893
60
Handler.addDebugNoteForVar((D), (D)->getBeginLoc(), "failed to produce fixit for declaration '" + (D)->getNameAsString() + "'" + (Msg))
1894
#else
1895
#define DEBUG_NOTE_DECL_FAIL(D, Msg)
1896
#endif
1897
1898
// For the given variable declaration with a pointer-to-T type, returns the text
1899
// `std::span<T>`.  If it is unable to generate the text, returns
1900
// `std::nullopt`.
1901
static std::optional<std::string> createSpanTypeForVarDecl(const VarDecl *VD,
1902
411
                                                           const ASTContext &Ctx) {
1903
411
  assert(VD->getType()->isPointerType());
1904
1905
411
  std::optional<Qualifiers> PteTyQualifiers = std::nullopt;
1906
411
  std::optional<std::string> PteTyText = getPointeeTypeText(
1907
411
      VD, Ctx.getSourceManager(), Ctx.getLangOpts(), &PteTyQualifiers);
1908
1909
411
  if (!PteTyText)
1910
6
    return std::nullopt;
1911
1912
405
  std::string SpanTyText = "std::span<";
1913
1914
405
  SpanTyText.append(*PteTyText);
1915
  // Append qualifiers to span element type if any:
1916
405
  if (PteTyQualifiers) {
1917
10
    SpanTyText.append(" ");
1918
10
    SpanTyText.append(PteTyQualifiers->getAsString());
1919
10
  }
1920
405
  SpanTyText.append(">");
1921
405
  return SpanTyText;
1922
411
}
1923
1924
// For a `VarDecl` of the form `T  * var (= Init)?`, this
1925
// function generates fix-its that
1926
//  1) replace `T * var` with `std::span<T> var`; and
1927
//  2) change `Init` accordingly to a span constructor, if it exists.
1928
//
1929
// FIXME: support Multi-level pointers
1930
//
1931
// Parameters:
1932
//   `D` a pointer the variable declaration node
1933
//   `Ctx` a reference to the ASTContext
1934
//   `UserFillPlaceHolder` the user-input placeholder text
1935
// Returns:
1936
//    the non-empty fix-it list, if fix-its are successfuly generated; empty
1937
//    list otherwise.
1938
static FixItList fixLocalVarDeclWithSpan(const VarDecl *D, ASTContext &Ctx,
1939
           const StringRef UserFillPlaceHolder,
1940
281
           UnsafeBufferUsageHandler &Handler) {
1941
281
  if (hasUnsupportedSpecifiers(D, Ctx.getSourceManager()))
1942
0
    return {};
1943
1944
281
  FixItList FixIts{};
1945
281
  std::optional<std::string> SpanTyText = createSpanTypeForVarDecl(D, Ctx);
1946
1947
281
  if (!SpanTyText) {
1948
6
    DEBUG_NOTE_DECL_FAIL(D, " : failed to generate 'std::span' type");
1949
6
    return {};
1950
6
  }
1951
1952
  // Will hold the text for `std::span<T> Ident`:
1953
275
  std::stringstream SS;
1954
1955
275
  SS << *SpanTyText;
1956
  // Append qualifiers to the type of `D`, if any:
1957
275
  if (D->getType().hasQualifiers())
1958
1
    SS << " " << D->getType().getQualifiers().getAsString();
1959
1960
  // The end of the range of the original source that will be replaced
1961
  // by `std::span<T> ident`:
1962
275
  SourceLocation EndLocForReplacement = D->getEndLoc();
1963
275
  std::optional<StringRef> IdentText =
1964
275
      getVarDeclIdentifierText(D, Ctx.getSourceManager(), Ctx.getLangOpts());
1965
1966
275
  if (!IdentText) {
1967
0
    DEBUG_NOTE_DECL_FAIL(D, " : failed to locate the identifier");
1968
0
    return {};
1969
0
  }
1970
  // Fix the initializer if it exists:
1971
275
  if (const Expr *Init = D->getInit()) {
1972
190
    FixItList InitFixIts =
1973
190
        FixVarInitializerWithSpan(Init, Ctx, UserFillPlaceHolder);
1974
190
    if (InitFixIts.empty())
1975
0
      return {};
1976
190
    FixIts.insert(FixIts.end(), std::make_move_iterator(InitFixIts.begin()),
1977
190
                  std::make_move_iterator(InitFixIts.end()));
1978
    // If the declaration has the form `T *ident = init`, we want to replace
1979
    // `T *ident = ` with `std::span<T> ident`:
1980
190
    EndLocForReplacement = Init->getBeginLoc().getLocWithOffset(-1);
1981
190
  }
1982
275
  SS << " " << IdentText->str();
1983
275
  if (!EndLocForReplacement.isValid()) {
1984
0
    DEBUG_NOTE_DECL_FAIL(D, " : failed to locate the end of the declaration");
1985
0
    return {};
1986
0
  }
1987
275
  FixIts.push_back(FixItHint::CreateReplacement(
1988
275
      SourceRange(D->getBeginLoc(), EndLocForReplacement), SS.str()));
1989
275
  return FixIts;
1990
275
}
1991
1992
332
static bool hasConflictingOverload(const FunctionDecl *FD) {
1993
332
  return !FD->getDeclContext()->lookup(FD->getDeclName()).isSingleResult();
1994
332
}
1995
1996
// For a `FunctionDecl`, whose `ParmVarDecl`s are being changed to have new
1997
// types, this function produces fix-its to make the change self-contained.  Let
1998
// 'F' be the entity defined by the original `FunctionDecl` and "NewF" be the
1999
// entity defined by the `FunctionDecl` after the change to the parameters.
2000
// Fix-its produced by this function are
2001
//   1. Add the `[[clang::unsafe_buffer_usage]]` attribute to each declaration
2002
//   of 'F';
2003
//   2. Create a declaration of "NewF" next to each declaration of `F`;
2004
//   3. Create a definition of "F" (as its' original definition is now belongs
2005
//      to "NewF") next to its original definition.  The body of the creating
2006
//      definition calls to "NewF".
2007
//
2008
// Example:
2009
//
2010
// void f(int *p);  // original declaration
2011
// void f(int *p) { // original definition
2012
//    p[5];
2013
// }
2014
//
2015
// To change the parameter `p` to be of `std::span<int>` type, we
2016
// also add overloads:
2017
//
2018
// [[clang::unsafe_buffer_usage]] void f(int *p); // original decl
2019
// void f(std::span<int> p);                      // added overload decl
2020
// void f(std::span<int> p) {     // original def where param is changed
2021
//    p[5];
2022
// }
2023
// [[clang::unsafe_buffer_usage]] void f(int *p) {  // added def
2024
//   return f(std::span(p, <# size #>));
2025
// }
2026
//
2027
static std::optional<FixItList>
2028
createOverloadsForFixedParams(const Strategy &S, const FunctionDecl *FD,
2029
                              const ASTContext &Ctx,
2030
332
                              UnsafeBufferUsageHandler &Handler) {
2031
  // FIXME: need to make this conflict checking better:
2032
332
  if (hasConflictingOverload(FD))
2033
6
    return std::nullopt;
2034
2035
326
  const SourceManager &SM = Ctx.getSourceManager();
2036
326
  const LangOptions &LangOpts = Ctx.getLangOpts();
2037
326
  const unsigned NumParms = FD->getNumParams();
2038
326
  std::vector<std::string> NewTysTexts(NumParms);
2039
326
  std::vector<bool> ParmsMask(NumParms, false);
2040
326
  bool AtLeastOneParmToFix = false;
2041
2042
564
  for (unsigned i = 0; i < NumParms; 
i++238
) {
2043
248
    const ParmVarDecl *PVD = FD->getParamDecl(i);
2044
2045
248
    if (S.lookup(PVD) == Strategy::Kind::Wontfix)
2046
89
      continue;
2047
159
    if (S.lookup(PVD) != Strategy::Kind::Span)
2048
      // Not supported, not suppose to happen:
2049
0
      return std::nullopt;
2050
2051
159
    std::optional<Qualifiers> PteTyQuals = std::nullopt;
2052
159
    std::optional<std::string> PteTyText =
2053
159
        getPointeeTypeText(PVD, SM, LangOpts, &PteTyQuals);
2054
2055
159
    if (!PteTyText)
2056
      // something wrong in obtaining the text of the pointee type, give up
2057
10
      return std::nullopt;
2058
    // FIXME: whether we should create std::span type depends on the Strategy.
2059
149
    NewTysTexts[i] = getSpanTypeText(*PteTyText, PteTyQuals);
2060
149
    ParmsMask[i] = true;
2061
149
    AtLeastOneParmToFix = true;
2062
149
  }
2063
316
  if (!AtLeastOneParmToFix)
2064
    // No need to create function overloads:
2065
222
    return {};
2066
  // FIXME Respect indentation of the original code.
2067
2068
  // A lambda that creates the text representation of a function declaration
2069
  // with the new type signatures:
2070
94
  const auto NewOverloadSignatureCreator =
2071
94
      [&SM, &LangOpts, &NewTysTexts,
2072
94
       &ParmsMask](const FunctionDecl *FD) -> std::optional<std::string> {
2073
17
    std::stringstream SS;
2074
2075
17
    SS << ";";
2076
17
    SS << getEndOfLine().str();
2077
    // Append: ret-type func-name "("
2078
17
    if (auto Prefix = getRangeText(
2079
17
            SourceRange(FD->getBeginLoc(), (*FD->param_begin())->getBeginLoc()),
2080
17
            SM, LangOpts))
2081
17
      SS << Prefix->str();
2082
0
    else
2083
0
      return std::nullopt; // give up
2084
    // Append: parameter-type-list
2085
17
    const unsigned NumParms = FD->getNumParams();
2086
2087
40
    for (unsigned i = 0; i < NumParms; 
i++23
) {
2088
23
      const ParmVarDecl *Parm = FD->getParamDecl(i);
2089
2090
23
      if (Parm->isImplicit())
2091
0
        continue;
2092
23
      if (ParmsMask[i]) {
2093
        // This `i`-th parameter will be fixed with `NewTysTexts[i]` being its
2094
        // new type:
2095
21
        SS << NewTysTexts[i];
2096
        // print parameter name if provided:
2097
21
        if (IdentifierInfo *II = Parm->getIdentifier())
2098
12
          SS << ' ' << II->getName().str();
2099
21
      } else 
if (auto 2
ParmTypeText2
= getRangeText(
2100
2
                     getSourceRangeToTokenEnd(Parm, SM, LangOpts),
2101
2
                     SM, LangOpts)) {
2102
        // print the whole `Parm` without modification:
2103
2
        SS << ParmTypeText->str();
2104
2
      } else
2105
0
        return std::nullopt; // something wrong, give up
2106
23
      if (i != NumParms - 1)
2107
6
        SS << ", ";
2108
23
    }
2109
17
    SS << ")";
2110
17
    return SS.str();
2111
17
  };
2112
2113
  // A lambda that creates the text representation of a function definition with
2114
  // the original signature:
2115
94
  const auto OldOverloadDefCreator =
2116
94
      [&Handler, &SM, &LangOpts, &NewTysTexts,
2117
94
       &ParmsMask](const FunctionDecl *FD) -> std::optional<std::string> {
2118
94
    std::stringstream SS;
2119
2120
94
    SS << getEndOfLine().str();
2121
    // Append: attr-name ret-type func-name "(" param-list ")" "{"
2122
94
    if (auto FDPrefix = getRangeText(
2123
94
            SourceRange(FD->getBeginLoc(), FD->getBody()->getBeginLoc()), SM,
2124
94
            LangOpts))
2125
94
      SS << Handler.getUnsafeBufferUsageAttributeTextAt(FD->getBeginLoc(), " ")
2126
94
         << FDPrefix->str() << "{";
2127
0
    else
2128
0
      return std::nullopt;
2129
    // Append: "return" func-name "("
2130
94
    if (auto FunQualName = getFunNameText(FD, SM, LangOpts))
2131
94
      SS << "return " << FunQualName->str() << "(";
2132
0
    else
2133
0
      return std::nullopt;
2134
2135
    // Append: arg-list
2136
94
    const unsigned NumParms = FD->getNumParams();
2137
250
    for (unsigned i = 0; i < NumParms; 
i++156
) {
2138
158
      const ParmVarDecl *Parm = FD->getParamDecl(i);
2139
2140
158
      if (Parm->isImplicit())
2141
0
        continue;
2142
      // FIXME: If a parameter has no name, it is unused in the
2143
      // definition. So we could just leave it as it is.
2144
158
      if (!Parm->getIdentifier())
2145
        // If a parameter of a function definition has no name:
2146
2
        return std::nullopt;
2147
156
      if (ParmsMask[i])
2148
        // This is our spanified paramter!
2149
149
        SS << NewTysTexts[i] << "(" << Parm->getIdentifier()->getName().str()
2150
149
           << ", " << getUserFillPlaceHolder("size") << ")";
2151
7
      else
2152
7
        SS << Parm->getIdentifier()->getName().str();
2153
156
      if (i != NumParms - 1)
2154
64
        SS << ", ";
2155
156
    }
2156
    // finish call and the body
2157
92
    SS << ");}" << getEndOfLine().str();
2158
    // FIXME: 80-char line formatting?
2159
92
    return SS.str();
2160
94
  };
2161
2162
94
  FixItList FixIts{};
2163
111
  for (FunctionDecl *FReDecl : FD->redecls()) {
2164
111
    std::optional<SourceLocation> Loc = getPastLoc(FReDecl, SM, LangOpts);
2165
2166
111
    if (!Loc)
2167
0
      return {};
2168
111
    if (FReDecl->isThisDeclarationADefinition()) {
2169
94
      assert(FReDecl == FD && "inconsistent function definition");
2170
      // Inserts a definition with the old signature to the end of
2171
      // `FReDecl`:
2172
94
      if (auto OldOverloadDef = OldOverloadDefCreator(FReDecl))
2173
92
        FixIts.emplace_back(FixItHint::CreateInsertion(*Loc, *OldOverloadDef));
2174
2
      else
2175
2
        return {}; // give up
2176
94
    } else {
2177
      // Adds the unsafe-buffer attribute (if not already there) to `FReDecl`:
2178
17
      if (!FReDecl->hasAttr<UnsafeBufferUsageAttr>()) {
2179
17
        FixIts.emplace_back(FixItHint::CreateInsertion(
2180
17
            FReDecl->getBeginLoc(), Handler.getUnsafeBufferUsageAttributeTextAt(
2181
17
                                        FReDecl->getBeginLoc(), " ")));
2182
17
      }
2183
      // Inserts a declaration with the new signature to the end of `FReDecl`:
2184
17
      if (auto NewOverloadDecl = NewOverloadSignatureCreator(FReDecl))
2185
17
        FixIts.emplace_back(FixItHint::CreateInsertion(*Loc, *NewOverloadDecl));
2186
0
      else
2187
0
        return {};
2188
17
    }
2189
111
  }
2190
92
  return FixIts;
2191
94
}
2192
2193
// To fix a `ParmVarDecl` to be of `std::span` type.
2194
static FixItList fixParamWithSpan(const ParmVarDecl *PVD, const ASTContext &Ctx,
2195
146
                                  UnsafeBufferUsageHandler &Handler) {
2196
146
  if (hasUnsupportedSpecifiers(PVD, Ctx.getSourceManager())) {
2197
0
    DEBUG_NOTE_DECL_FAIL(PVD, " : has unsupport specifier(s)");
2198
0
    return {};
2199
0
  }
2200
146
  if (PVD->hasDefaultArg()) {
2201
    // FIXME: generate fix-its for default values:
2202
8
    DEBUG_NOTE_DECL_FAIL(PVD, " : has default arg");
2203
8
    return {};
2204
8
  }
2205
2206
138
  std::optional<Qualifiers> PteTyQualifiers = std::nullopt;
2207
138
  std::optional<std::string> PteTyText = getPointeeTypeText(
2208
138
      PVD, Ctx.getSourceManager(), Ctx.getLangOpts(), &PteTyQualifiers);
2209
2210
138
  if (!PteTyText) {
2211
8
    DEBUG_NOTE_DECL_FAIL(PVD, " : invalid pointee type");
2212
8
    return {};
2213
8
  }
2214
2215
130
  std::optional<StringRef> PVDNameText = PVD->getIdentifier()->getName();
2216
2217
130
  if (!PVDNameText) {
2218
0
    DEBUG_NOTE_DECL_FAIL(PVD, " : invalid identifier name");
2219
0
    return {};
2220
0
  }
2221
2222
130
  std::stringstream SS;
2223
130
  std::optional<std::string> SpanTyText = createSpanTypeForVarDecl(PVD, Ctx);
2224
2225
130
  if (PteTyQualifiers)
2226
    // Append qualifiers if they exist:
2227
7
    SS << getSpanTypeText(*PteTyText, PteTyQualifiers);
2228
123
  else
2229
123
    SS << getSpanTypeText(*PteTyText);
2230
  // Append qualifiers to the type of the parameter:
2231
130
  if (PVD->getType().hasQualifiers())
2232
6
    SS << ' ' << PVD->getType().getQualifiers().getAsString();
2233
  // Append parameter's name:
2234
130
  SS << ' ' << PVDNameText->str();
2235
  // Add replacement fix-it:
2236
130
  return {FixItHint::CreateReplacement(PVD->getSourceRange(), SS.str())};
2237
130
}
2238
2239
static FixItList fixVariableWithSpan(const VarDecl *VD,
2240
                                     const DeclUseTracker &Tracker,
2241
                                     ASTContext &Ctx,
2242
285
                                     UnsafeBufferUsageHandler &Handler) {
2243
285
  const DeclStmt *DS = Tracker.lookupDecl(VD);
2244
285
  if (!DS) {
2245
0
    DEBUG_NOTE_DECL_FAIL(VD, " : variables declared this way not implemented yet");
2246
0
    return {};
2247
0
  }
2248
285
  if (!DS->isSingleDecl()) {
2249
    // FIXME: to support handling multiple `VarDecl`s in a single `DeclStmt`
2250
4
    DEBUG_NOTE_DECL_FAIL(VD, " : multiple VarDecls");
2251
4
    return {};
2252
4
  }
2253
  // Currently DS is an unused variable but we'll need it when
2254
  // non-single decls are implemented, where the pointee type name
2255
  // and the '*' are spread around the place.
2256
281
  (void)DS;
2257
2258
  // FIXME: handle cases where DS has multiple declarations
2259
281
  return fixLocalVarDeclWithSpan(VD, Ctx, getUserFillPlaceHolder(), Handler);
2260
285
}
2261
2262
// TODO: we should be consistent to use `std::nullopt` to represent no-fix due
2263
// to any unexpected problem.
2264
static FixItList
2265
fixVariable(const VarDecl *VD, Strategy::Kind K,
2266
            /* The function decl under analysis */ const Decl *D,
2267
            const DeclUseTracker &Tracker, ASTContext &Ctx,
2268
465
            UnsafeBufferUsageHandler &Handler) {
2269
465
  if (const auto *PVD = dyn_cast<ParmVarDecl>(VD)) {
2270
170
    auto *FD = dyn_cast<clang::FunctionDecl>(PVD->getDeclContext());
2271
170
    if (!FD || FD != D) {
2272
      // `FD != D` means that `PVD` belongs to a function that is not being
2273
      // analyzed currently.  Thus `FD` may not be complete.
2274
4
      DEBUG_NOTE_DECL_FAIL(VD, " : function not currently analyzed");
2275
4
      return {};
2276
4
    }
2277
2278
    // TODO If function has a try block we can't change params unless we check
2279
    // also its catch block for their use.
2280
    // FIXME We might support static class methods, some select methods,
2281
    // operators and possibly lamdas.
2282
166
    if (FD->isMain() || 
FD->isConstexpr()164
||
2283
166
        
FD->getTemplatedKind() != FunctionDecl::TemplatedKind::TK_NonTemplate161
||
2284
166
        
FD->isVariadic()156
||
2285
        // also covers call-operator of lamdas
2286
166
        
isa<CXXMethodDecl>(FD)154
||
2287
        // skip when the function body is a try-block
2288
166
        
(148
FD->hasBody()148
&&
isa<CXXTryStmt>(FD->getBody())148
) ||
2289
166
        
FD->isOverloadedOperator()146
) {
2290
20
      DEBUG_NOTE_DECL_FAIL(VD, " : unsupported function decl");
2291
20
      return {}; // TODO test all these cases
2292
20
    }
2293
166
  }
2294
2295
441
  switch (K) {
2296
441
  case Strategy::Kind::Span: {
2297
441
    if (VD->getType()->isPointerType()) {
2298
431
      if (const auto *PVD = dyn_cast<ParmVarDecl>(VD))
2299
146
        return fixParamWithSpan(PVD, Ctx, Handler);
2300
2301
285
      if (VD->isLocalVarDecl())
2302
285
        return fixVariableWithSpan(VD, Tracker, Ctx, Handler);
2303
285
    }
2304
10
    DEBUG_NOTE_DECL_FAIL(VD, " : not a pointer");
2305
10
    return {};
2306
441
  }
2307
0
  case Strategy::Kind::Iterator:
2308
0
  case Strategy::Kind::Array:
2309
0
  case Strategy::Kind::Vector:
2310
0
    llvm_unreachable("Strategy not implemented yet!");
2311
0
  case Strategy::Kind::Wontfix:
2312
0
    llvm_unreachable("Invalid strategy!");
2313
441
  }
2314
0
  llvm_unreachable("Unknown strategy!");
2315
0
}
2316
2317
// Returns true iff there exists a `FixItHint` 'h' in `FixIts` such that the
2318
// `RemoveRange` of 'h' overlaps with a macro use.
2319
280
static bool overlapWithMacro(const FixItList &FixIts) {
2320
  // FIXME: For now we only check if the range (or the first token) is (part of)
2321
  // a macro expansion.  Ideally, we want to check for all tokens in the range.
2322
1.66k
  return llvm::any_of(FixIts, [](const FixItHint &Hint) {
2323
1.66k
    auto Range = Hint.RemoveRange;
2324
1.66k
    if (Range.getBegin().isMacroID() || 
Range.getEnd().isMacroID()1.66k
)
2325
      // If the range (or the first token) is (part of) a macro expansion:
2326
4
      return true;
2327
1.65k
    return false;
2328
1.66k
  });
2329
280
}
2330
2331
// Returns true iff `VD` is a parameter of the declaration `D`:
2332
540
static bool isParameterOf(const VarDecl *VD, const Decl *D) {
2333
540
  return isa<ParmVarDecl>(VD) &&
2334
540
         
VD->getDeclContext() == dyn_cast<DeclContext>(D)208
;
2335
540
}
2336
2337
// Erases variables in `FixItsForVariable`, if such a variable has an unfixable
2338
// group mate.  A variable `v` is unfixable iff `FixItsForVariable` does not
2339
// contain `v`.
2340
static void eraseVarsForUnfixableGroupMates(
2341
    std::map<const VarDecl *, FixItList> &FixItsForVariable,
2342
332
    const VariableGroupsManager &VarGrpMgr) {
2343
  // Variables will be removed from `FixItsForVariable`:
2344
332
  SmallVector<const VarDecl *, 8> ToErase;
2345
2346
348
  for (const auto &[VD, Ignore] : FixItsForVariable) {
2347
348
    VarGrpRef Grp = VarGrpMgr.getGroupOfVar(VD);
2348
348
    if (llvm::any_of(Grp,
2349
915
                     [&FixItsForVariable](const VarDecl *GrpMember) -> bool {
2350
915
                       return !FixItsForVariable.count(GrpMember);
2351
915
                     })) {
2352
      // At least one group member cannot be fixed, so we have to erase the
2353
      // whole group:
2354
59
      for (const VarDecl *Member : Grp)
2355
270
        ToErase.push_back(Member);
2356
59
    }
2357
348
  }
2358
332
  for (auto *VarToErase : ToErase)
2359
270
    FixItsForVariable.erase(VarToErase);
2360
332
}
2361
2362
// Returns the fix-its that create bounds-safe function overloads for the
2363
// function `D`, if `D`'s parameters will be changed to safe-types through
2364
// fix-its in `FixItsForVariable`.
2365
//
2366
// NOTE: In case `D`'s parameters will be changed but bounds-safe function
2367
// overloads cannot created, the whole group that contains the parameters will
2368
// be erased from `FixItsForVariable`.
2369
static FixItList createFunctionOverloadsForParms(
2370
    std::map<const VarDecl *, FixItList> &FixItsForVariable /* mutable */,
2371
    const VariableGroupsManager &VarGrpMgr, const FunctionDecl *FD,
2372
332
    const Strategy &S, ASTContext &Ctx, UnsafeBufferUsageHandler &Handler) {
2373
332
  FixItList FixItsSharedByParms{};
2374
2375
332
  std::optional<FixItList> OverloadFixes =
2376
332
      createOverloadsForFixedParams(S, FD, Ctx, Handler);
2377
2378
332
  if (OverloadFixes) {
2379
92
    FixItsSharedByParms.append(*OverloadFixes);
2380
240
  } else {
2381
    // Something wrong in generating `OverloadFixes`, need to remove the
2382
    // whole group, where parameters are in, from `FixItsForVariable` (Note
2383
    // that all parameters should be in the same group):
2384
240
    for (auto *Member : VarGrpMgr.getGroupOfParms())
2385
51
      FixItsForVariable.erase(Member);
2386
240
  }
2387
332
  return FixItsSharedByParms;
2388
332
}
2389
2390
// Constructs self-contained fix-its for each variable in `FixablesForAllVars`.
2391
static std::map<const VarDecl *, FixItList>
2392
getFixIts(FixableGadgetSets &FixablesForAllVars, const Strategy &S,
2393
    ASTContext &Ctx,
2394
          /* The function decl under analysis */ const Decl *D,
2395
          const DeclUseTracker &Tracker, UnsafeBufferUsageHandler &Handler,
2396
332
          const VariableGroupsManager &VarGrpMgr) {
2397
  // `FixItsForVariable` will map each variable to a set of fix-its directly
2398
  // associated to the variable itself.  Fix-its of distinct variables in
2399
  // `FixItsForVariable` are disjoint.
2400
332
  std::map<const VarDecl *, FixItList> FixItsForVariable;
2401
2402
  // Populate `FixItsForVariable` with fix-its directly associated with each
2403
  // variable.  Fix-its directly associated to a variable 'v' are the ones
2404
  // produced by the `FixableGadget`s whose claimed variable is 'v'.
2405
465
  for (const auto &[VD, Fixables] : FixablesForAllVars.byVar) {
2406
465
    FixItsForVariable[VD] =
2407
465
        fixVariable(VD, S.lookup(VD), D, Tracker, Ctx, Handler);
2408
    // If we fail to produce Fix-It for the declaration we have to skip the
2409
    // variable entirely.
2410
465
    if (FixItsForVariable[VD].empty()) {
2411
60
      FixItsForVariable.erase(VD);
2412
60
      continue;
2413
60
    }
2414
656
    
for (const auto &F : Fixables)405
{
2415
656
      std::optional<FixItList> Fixits = F->getFixits(S);
2416
2417
656
      if (Fixits) {
2418
599
        FixItsForVariable[VD].insert(FixItsForVariable[VD].end(),
2419
599
                                     Fixits->begin(), Fixits->end());
2420
599
        continue;
2421
599
      }
2422
57
#ifndef NDEBUG
2423
57
      Handler.addDebugNoteForVar(
2424
57
          VD, F->getBaseStmt()->getBeginLoc(),
2425
57
          ("gadget '" + F->getDebugName() + "' refused to produce a fix")
2426
57
              .str());
2427
57
#endif
2428
57
      FixItsForVariable.erase(VD);
2429
57
      break;
2430
656
    }
2431
405
  }
2432
2433
  // `FixItsForVariable` now contains only variables that can be
2434
  // fixed. A variable can be fixed if its' declaration and all Fixables
2435
  // associated to it can all be fixed.
2436
2437
  // To further remove from `FixItsForVariable` variables whose group mates
2438
  // cannot be fixed...
2439
332
  eraseVarsForUnfixableGroupMates(FixItsForVariable, VarGrpMgr);
2440
  // Now `FixItsForVariable` gets further reduced: a variable is in
2441
  // `FixItsForVariable` iff it can be fixed and all its group mates can be
2442
  // fixed.
2443
2444
  // Fix-its of bounds-safe overloads of `D` are shared by parameters of `D`.
2445
  // That is,  when fixing multiple parameters in one step,  these fix-its will
2446
  // be applied only once (instead of being applied per parameter).
2447
332
  FixItList FixItsSharedByParms{};
2448
2449
332
  if (auto *FD = dyn_cast<FunctionDecl>(D))
2450
332
    FixItsSharedByParms = createFunctionOverloadsForParms(
2451
332
        FixItsForVariable, VarGrpMgr, FD, S, Ctx, Handler);
2452
2453
  // The map that maps each variable `v` to fix-its for the whole group where
2454
  // `v` is in:
2455
332
  std::map<const VarDecl *, FixItList> FinalFixItsForVariable{
2456
332
      FixItsForVariable};
2457
2458
332
  for (auto &[Var, Ignore] : FixItsForVariable) {
2459
280
    bool AnyParm = false;
2460
280
    const auto VarGroupForVD = VarGrpMgr.getGroupOfVar(Var, &AnyParm);
2461
2462
728
    for (const VarDecl *GrpMate : VarGroupForVD) {
2463
728
      if (Var == GrpMate)
2464
280
        continue;
2465
448
      if (FixItsForVariable.count(GrpMate))
2466
448
        FinalFixItsForVariable[Var].append(FixItsForVariable[GrpMate]);
2467
448
    }
2468
280
    if (AnyParm) {
2469
      // This assertion should never fail.  Otherwise we have a bug.
2470
101
      assert(!FixItsSharedByParms.empty() &&
2471
101
             "Should not try to fix a parameter that does not belong to a "
2472
101
             "FunctionDecl");
2473
101
      FinalFixItsForVariable[Var].append(FixItsSharedByParms);
2474
101
    }
2475
280
  }
2476
  // Fix-its that will be applied in one step shall NOT:
2477
  // 1. overlap with macros or/and templates; or
2478
  // 2. conflict with each other.
2479
  // Otherwise, the fix-its will be dropped.
2480
332
  for (auto Iter = FinalFixItsForVariable.begin();
2481
612
       Iter != FinalFixItsForVariable.end();)
2482
280
    if (overlapWithMacro(Iter->second) ||
2483
280
        
clang::internal::anyConflict(Iter->second, Ctx.getSourceManager())276
) {
2484
4
      Iter = FinalFixItsForVariable.erase(Iter);
2485
4
    } else
2486
276
      Iter++;
2487
332
  return FinalFixItsForVariable;
2488
332
}
2489
2490
template <typename VarDeclIterTy>
2491
static Strategy
2492
337
getNaiveStrategy(llvm::iterator_range<VarDeclIterTy> UnsafeVars) {
2493
337
  Strategy S;
2494
467
  for (const VarDecl *VD : UnsafeVars) {
2495
467
    S.set(VD, Strategy::Kind::Span);
2496
467
  }
2497
337
  return S;
2498
337
}
2499
2500
//  Manages variable groups:
2501
class VariableGroupsManagerImpl : public VariableGroupsManager {
2502
  const std::vector<VarGrpTy> Groups;
2503
  const std::map<const VarDecl *, unsigned> &VarGrpMap;
2504
  const llvm::SetVector<const VarDecl *> &GrpsUnionForParms;
2505
2506
public:
2507
  VariableGroupsManagerImpl(
2508
      const std::vector<VarGrpTy> &Groups,
2509
      const std::map<const VarDecl *, unsigned> &VarGrpMap,
2510
      const llvm::SetVector<const VarDecl *> &GrpsUnionForParms)
2511
337
      : Groups(Groups), VarGrpMap(VarGrpMap),
2512
337
        GrpsUnionForParms(GrpsUnionForParms) {}
2513
2514
830
  VarGrpRef getGroupOfVar(const VarDecl *Var, bool *HasParm) const override {
2515
830
    if (GrpsUnionForParms.contains(Var)) {
2516
345
      if (HasParm)
2517
187
        *HasParm = true;
2518
345
      return GrpsUnionForParms.getArrayRef();
2519
345
    }
2520
485
    if (HasParm)
2521
295
      *HasParm = false;
2522
2523
485
    auto It = VarGrpMap.find(Var);
2524
2525
485
    if (It == VarGrpMap.end())
2526
0
      return std::nullopt;
2527
485
    return Groups[It->second];
2528
485
  }
2529
2530
240
  VarGrpRef getGroupOfParms() const override {
2531
240
    return GrpsUnionForParms.getArrayRef();
2532
240
  }
2533
};
2534
2535
void clang::checkUnsafeBufferUsage(const Decl *D,
2536
                                   UnsafeBufferUsageHandler &Handler,
2537
501
                                   bool EmitSuggestions) {
2538
501
#ifndef NDEBUG
2539
501
  Handler.clearDebugNotes();
2540
501
#endif
2541
2542
501
  assert(D && D->getBody());
2543
  // We do not want to visit a Lambda expression defined inside a method independently.
2544
  // Instead, it should be visited along with the outer method.
2545
  // FIXME: do we want to do the same thing for `BlockDecl`s?
2546
501
  if (const auto *fd = dyn_cast<CXXMethodDecl>(D)) {
2547
38
    if (fd->getParent()->isLambda() && 
fd->getParent()->isLocalClass()21
)
2548
20
      return;
2549
38
  }
2550
2551
  // Do not emit fixit suggestions for functions declared in an
2552
  // extern "C" block.
2553
481
  if (const auto *FD = dyn_cast<FunctionDecl>(D)) {
2554
499
      for (FunctionDecl *FReDecl : FD->redecls()) {
2555
499
      if (FReDecl->isExternC()) {
2556
53
        EmitSuggestions = false;
2557
53
        break;
2558
53
      }
2559
499
    }
2560
472
  }
2561
2562
481
  WarningGadgetSets UnsafeOps;
2563
481
  FixableGadgetSets FixablesForAllVars;
2564
2565
481
  auto [FixableGadgets, WarningGadgets, Tracker] =
2566
481
    findGadgets(D, Handler, EmitSuggestions);
2567
2568
481
  if (!EmitSuggestions) {
2569
    // Our job is very easy without suggestions. Just warn about
2570
    // every problematic operation and consider it done. No need to deal
2571
    // with fixable gadgets, no need to group operations by variable.
2572
254
    for (const auto &G : WarningGadgets) {
2573
254
      Handler.handleUnsafeOperation(G->getBaseStmt(),
2574
254
                                    /*IsRelatedToDecl=*/false);
2575
254
    }
2576
2577
    // This return guarantees that most of the machine doesn't run when
2578
    // suggestions aren't requested.
2579
112
    assert(FixableGadgets.size() == 0 &&
2580
112
           "Fixable gadgets found but suggestions not requested!");
2581
112
    return;
2582
112
  }
2583
2584
  // If no `WarningGadget`s ever matched, there is no unsafe operations in the
2585
  //  function under the analysis. No need to fix any Fixables.
2586
369
  if (!WarningGadgets.empty()) {
2587
    // Gadgets "claim" variables they're responsible for. Once this loop
2588
    // finishes, the tracker will only track DREs that weren't claimed by any
2589
    // gadgets, i.e. not understood by the analysis.
2590
765
    for (const auto &G : FixableGadgets) {
2591
927
      for (const auto *DRE : G->getClaimedVarUseSites()) {
2592
927
        Tracker.claimUse(DRE);
2593
927
      }
2594
765
    }
2595
337
  }
2596
2597
  // If no `WarningGadget`s ever matched, there is no unsafe operations in the
2598
  // function under the analysis.  Thus, it early returns here as there is
2599
  // nothing needs to be fixed.
2600
  //
2601
  // Note this claim is based on the assumption that there is no unsafe
2602
  // variable whose declaration is invisible from the analyzing function.
2603
  // Otherwise, we need to consider if the uses of those unsafe varuables needs
2604
  // fix.
2605
  // So far, we are not fixing any global variables or class members. And,
2606
  // lambdas will be analyzed along with the enclosing function. So this early
2607
  // return is correct for now.
2608
369
  if (WarningGadgets.empty())
2609
32
    return;
2610
2611
337
  UnsafeOps = groupWarningGadgetsByVar(std::move(WarningGadgets));
2612
337
  FixablesForAllVars = groupFixablesByVar(std::move(FixableGadgets));
2613
2614
337
  std::map<const VarDecl *, FixItList> FixItsForVariableGroup;
2615
2616
  // Filter out non-local vars and vars with unclaimed DeclRefExpr-s.
2617
337
  for (auto it = FixablesForAllVars.byVar.cbegin();
2618
935
       it != FixablesForAllVars.byVar.cend();) {
2619
      // FIXME: need to deal with global variables later
2620
598
      if ((!it->first->isLocalVarDecl() && 
!isa<ParmVarDecl>(it->first)206
)) {
2621
6
#ifndef NDEBUG
2622
6
          Handler.addDebugNoteForVar(
2623
6
              it->first, it->first->getBeginLoc(),
2624
6
              ("failed to produce fixit for '" + it->first->getNameAsString() +
2625
6
               "' : neither local nor a parameter"));
2626
6
#endif
2627
6
        it = FixablesForAllVars.byVar.erase(it);
2628
592
      } else if (it->first->getType().getCanonicalType()->isReferenceType()) {
2629
1
#ifndef NDEBUG
2630
1
        Handler.addDebugNoteForVar(it->first, it->first->getBeginLoc(),
2631
1
                                   ("failed to produce fixit for '" +
2632
1
                                    it->first->getNameAsString() +
2633
1
                                    "' : has a reference type"));
2634
1
#endif
2635
1
        it = FixablesForAllVars.byVar.erase(it);
2636
591
      } else if (Tracker.hasUnclaimedUses(it->first)) {
2637
76
#ifndef NDEBUG
2638
76
        auto AllUnclaimed = Tracker.getUnclaimedUses(it->first);
2639
119
        for (auto UnclaimedDRE : AllUnclaimed) {
2640
119
        std::string UnclaimedUseTrace =
2641
119
            getDREAncestorString(UnclaimedDRE, D->getASTContext());
2642
2643
119
        Handler.addDebugNoteForVar(
2644
119
            it->first, UnclaimedDRE->getBeginLoc(),
2645
119
            ("failed to produce fixit for '" + it->first->getNameAsString() +
2646
119
             "' : has an unclaimed use\nThe unclaimed DRE trace: " +
2647
119
             UnclaimedUseTrace));
2648
119
        }
2649
76
#endif
2650
76
        it = FixablesForAllVars.byVar.erase(it);
2651
515
      } else if (it->first->isInitCapture()) {
2652
2
#ifndef NDEBUG
2653
2
        Handler.addDebugNoteForVar(
2654
2
            it->first, it->first->getBeginLoc(),
2655
2
                                   ("failed to produce fixit for '" + it->first->getNameAsString() +
2656
2
                                    "' : init capture"));
2657
2
#endif
2658
2
        it = FixablesForAllVars.byVar.erase(it);
2659
513
      }else {
2660
513
      ++it;
2661
513
    }
2662
598
  }
2663
2664
  // Fixpoint iteration for pointer assignments
2665
337
  using DepMapTy = DenseMap<const VarDecl *, llvm::SetVector<const VarDecl *>>;
2666
337
  DepMapTy DependenciesMap{};
2667
337
  DepMapTy PtrAssignmentGraph{};
2668
2669
513
  for (auto it : FixablesForAllVars.byVar) {
2670
830
    for (const FixableGadget *fixable : it.second) {
2671
830
      std::optional<std::pair<const VarDecl *, const VarDecl *>> ImplPair =
2672
830
                                  fixable->getStrategyImplications();
2673
830
      if (ImplPair) {
2674
332
        std::pair<const VarDecl *, const VarDecl *> Impl = std::move(*ImplPair);
2675
332
        PtrAssignmentGraph[Impl.first].insert(Impl.second);
2676
332
      }
2677
830
    }
2678
513
  }
2679
2680
  /*
2681
   The following code does a BFS traversal of the `PtrAssignmentGraph`
2682
   considering all unsafe vars as starting nodes and constructs an undirected
2683
   graph `DependenciesMap`. Constructing the `DependenciesMap` in this manner
2684
   elimiates all variables that are unreachable from any unsafe var. In other
2685
   words, this removes all dependencies that don't include any unsafe variable
2686
   and consequently don't need any fixit generation.
2687
   Note: A careful reader would observe that the code traverses
2688
   `PtrAssignmentGraph` using `CurrentVar` but adds edges between `Var` and
2689
   `Adj` and not between `CurrentVar` and `Adj`. Both approaches would
2690
   achieve the same result but the one used here dramatically cuts the
2691
   amount of hoops the second part of the algorithm needs to jump, given that
2692
   a lot of these connections become "direct". The reader is advised not to
2693
   imagine how the graph is transformed because of using `Var` instead of
2694
   `CurrentVar`. The reader can continue reading as if `CurrentVar` was used,
2695
   and think about why it's equivalent later.
2696
   */
2697
337
  std::set<const VarDecl *> VisitedVarsDirected{};
2698
480
  for (const auto &[Var, ignore] : UnsafeOps.byVar) {
2699
480
    if (VisitedVarsDirected.find(Var) == VisitedVarsDirected.end()) {
2700
2701
470
      std::queue<const VarDecl*> QueueDirected{};
2702
470
      QueueDirected.push(Var);
2703
1.05k
      while(!QueueDirected.empty()) {
2704
586
        const VarDecl* CurrentVar = QueueDirected.front();
2705
586
        QueueDirected.pop();
2706
586
        VisitedVarsDirected.insert(CurrentVar);
2707
586
        auto AdjacentNodes = PtrAssignmentGraph[CurrentVar];
2708
586
        for (const VarDecl *Adj : AdjacentNodes) {
2709
156
          if (VisitedVarsDirected.find(Adj) == VisitedVarsDirected.end()) {
2710
116
            QueueDirected.push(Adj);
2711
116
          }
2712
156
          DependenciesMap[Var].insert(Adj);
2713
156
          DependenciesMap[Adj].insert(Var);
2714
156
        }
2715
586
      }
2716
470
    }
2717
480
  }
2718
2719
  // `Groups` stores the set of Connected Components in the graph.
2720
337
  std::vector<VarGrpTy> Groups;
2721
  // `VarGrpMap` maps variables that need fix to the groups (indexes) that the
2722
  // variables belong to.  Group indexes refer to the elements in `Groups`.
2723
  // `VarGrpMap` is complete in that every variable that needs fix is in it.
2724
337
  std::map<const VarDecl *, unsigned> VarGrpMap;
2725
  // The union group over the ones in "Groups" that contain parameters of `D`:
2726
337
  llvm::SetVector<const VarDecl *>
2727
337
      GrpsUnionForParms; // these variables need to be fixed in one step
2728
2729
  // Group Connected Components for Unsafe Vars
2730
  // (Dependencies based on pointer assignments)
2731
337
  std::set<const VarDecl *> VisitedVars{};
2732
480
  for (const auto &[Var, ignore] : UnsafeOps.byVar) {
2733
480
    if (VisitedVars.find(Var) == VisitedVars.end()) {
2734
437
      VarGrpTy &VarGroup = Groups.emplace_back();
2735
437
      std::queue<const VarDecl*> Queue{};
2736
2737
437
      Queue.push(Var);
2738
1.02k
      while(!Queue.empty()) {
2739
586
        const VarDecl* CurrentVar = Queue.front();
2740
586
        Queue.pop();
2741
586
        VisitedVars.insert(CurrentVar);
2742
586
        VarGroup.push_back(CurrentVar);
2743
586
        auto AdjacentNodes = DependenciesMap[CurrentVar];
2744
586
        for (const VarDecl *Adj : AdjacentNodes) {
2745
305
          if (VisitedVars.find(Adj) == VisitedVars.end()) {
2746
149
            Queue.push(Adj);
2747
149
          }
2748
305
        }
2749
586
      }
2750
2751
437
      bool HasParm = false;
2752
437
      unsigned GrpIdx = Groups.size() - 1;
2753
2754
586
      for (const VarDecl *V : VarGroup) {
2755
586
        VarGrpMap[V] = GrpIdx;
2756
586
        if (!HasParm && 
isParameterOf(V, D)540
)
2757
204
          HasParm = true;
2758
586
      }
2759
437
      if (HasParm)
2760
204
        GrpsUnionForParms.insert(VarGroup.begin(), VarGroup.end());
2761
437
    }
2762
480
  }
2763
2764
  // Remove a `FixableGadget` if the associated variable is not in the graph
2765
  // computed above.  We do not want to generate fix-its for such variables,
2766
  // since they are neither warned nor reachable from a warned one.
2767
  //
2768
  // Note a variable is not warned if it is not directly used in any unsafe
2769
  // operation. A variable `v` is NOT reachable from an unsafe variable, if it
2770
  // does not exist another variable `u` such that `u` is warned and fixing `u`
2771
  // (transitively) implicates fixing `v`.
2772
  //
2773
  // For example,
2774
  // ```
2775
  // void f(int * p) {
2776
  //   int * a = p; *p = 0;
2777
  // }
2778
  // ```
2779
  // `*p = 0` is a fixable gadget associated with a variable `p` that is neither
2780
  // warned nor reachable from a warned one.  If we add `a[5] = 0` to the end of
2781
  // the function above, `p` becomes reachable from a warned variable.
2782
337
  for (auto I = FixablesForAllVars.byVar.begin();
2783
850
       I != FixablesForAllVars.byVar.end();) {
2784
    // Note `VisitedVars` contain all the variables in the graph:
2785
513
    if (!VisitedVars.count((*I).first)) {
2786
      // no such var in graph:
2787
46
      I = FixablesForAllVars.byVar.erase(I);
2788
46
    } else
2789
467
      ++I;
2790
513
  }
2791
2792
  // We assign strategies to variables that are 1) in the graph and 2) can be
2793
  // fixed. Other variables have the default "Won't fix" strategy.
2794
337
  Strategy NaiveStrategy = getNaiveStrategy(llvm::make_filter_range(
2795
586
      VisitedVars, [&FixablesForAllVars](const VarDecl *V) {
2796
        // If a warned variable has no "Fixable", it is considered unfixable:
2797
586
        return FixablesForAllVars.byVar.count(V);
2798
586
      }));
2799
337
  VariableGroupsManagerImpl VarGrpMgr(Groups, VarGrpMap, GrpsUnionForParms);
2800
2801
337
  if (isa<NamedDecl>(D))
2802
    // The only case where `D` is not a `NamedDecl` is when `D` is a
2803
    // `BlockDecl`. Let's not fix variables in blocks for now
2804
332
    FixItsForVariableGroup =
2805
332
        getFixIts(FixablesForAllVars, NaiveStrategy, D->getASTContext(), D,
2806
332
                  Tracker, Handler, VarGrpMgr);
2807
2808
337
  for (const auto &G : UnsafeOps.noVar) {
2809
95
    Handler.handleUnsafeOperation(G->getBaseStmt(), /*IsRelatedToDecl=*/false);
2810
95
  }
2811
2812
480
  for (const auto &[VD, WarningGadgets] : UnsafeOps.byVar) {
2813
480
    auto FixItsIt = FixItsForVariableGroup.find(VD);
2814
480
    Handler.handleUnsafeVariableGroup(VD, VarGrpMgr,
2815
480
                                      FixItsIt != FixItsForVariableGroup.end()
2816
480
                                      ? 
std::move(FixItsIt->second)202
2817
480
                                      : 
FixItList{}278
,
2818
480
                                      D);
2819
589
    for (const auto &G : WarningGadgets) {
2820
589
      Handler.handleUnsafeOperation(G->getBaseStmt(), /*IsRelatedToDecl=*/true);
2821
589
    }
2822
480
  }
2823
337
}