Coverage Report

Created: 2020-02-25 14:32

/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/Tooling/Refactoring/ASTSelection.cpp
Line
Count
Source (jump to first uncovered line)
1
//===--- ASTSelection.cpp - Clang refactoring library ---------------------===//
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/Tooling/Refactoring/ASTSelection.h"
10
#include "clang/AST/LexicallyOrderedRecursiveASTVisitor.h"
11
#include "clang/Lex/Lexer.h"
12
#include "llvm/Support/SaveAndRestore.h"
13
14
using namespace clang;
15
using namespace tooling;
16
17
namespace {
18
19
CharSourceRange getLexicalDeclRange(Decl *D, const SourceManager &SM,
20
877
                                    const LangOptions &LangOpts) {
21
877
  if (!isa<ObjCImplDecl>(D))
22
861
    return CharSourceRange::getTokenRange(D->getSourceRange());
23
16
  // Objective-C implementation declarations end at the '@' instead of the 'end'
24
16
  // keyword. Use the lexer to find the location right after 'end'.
25
16
  SourceRange R = D->getSourceRange();
26
16
  SourceLocation LocAfterEnd = Lexer::findLocationAfterToken(
27
16
      R.getEnd(), tok::raw_identifier, SM, LangOpts,
28
16
      /*SkipTrailingWhitespaceAndNewLine=*/false);
29
16
  return LocAfterEnd.isValid()
30
16
             ? CharSourceRange::getCharRange(R.getBegin(), LocAfterEnd)
31
16
             : 
CharSourceRange::getTokenRange(R)0
;
32
16
}
33
34
/// Constructs the tree of selected AST nodes that either contain the location
35
/// of the cursor or overlap with the selection range.
36
class ASTSelectionFinder
37
    : public LexicallyOrderedRecursiveASTVisitor<ASTSelectionFinder> {
38
public:
39
  ASTSelectionFinder(SourceRange Selection, FileID TargetFile,
40
                     const ASTContext &Context)
41
      : LexicallyOrderedRecursiveASTVisitor(Context.getSourceManager()),
42
        SelectionBegin(Selection.getBegin()),
43
        SelectionEnd(Selection.getBegin() == Selection.getEnd()
44
                         ? SourceLocation()
45
                         : Selection.getEnd()),
46
87
        TargetFile(TargetFile), Context(Context) {
47
87
    // The TU decl is the root of the selected node tree.
48
87
    SelectionStack.push_back(
49
87
        SelectedASTNode(DynTypedNode::create(*Context.getTranslationUnitDecl()),
50
87
                        SourceSelectionKind::None));
51
87
  }
52
53
87
  Optional<SelectedASTNode> getSelectedASTNode() {
54
87
    assert(SelectionStack.size() == 1 && "stack was not popped");
55
87
    SelectedASTNode Result = std::move(SelectionStack.back());
56
87
    SelectionStack.pop_back();
57
87
    if (Result.Children.empty())
58
3
      return None;
59
84
    return std::move(Result);
60
84
  }
61
62
26
  bool TraversePseudoObjectExpr(PseudoObjectExpr *E) {
63
26
    // Avoid traversing the semantic expressions. They should be handled by
64
26
    // looking through the appropriate opaque expressions in order to build
65
26
    // a meaningful selection tree.
66
26
    llvm::SaveAndRestore<bool> LookThrough(LookThroughOpaqueValueExprs, true);
67
26
    return TraverseStmt(E->getSyntacticForm());
68
26
  }
69
70
40
  bool TraverseOpaqueValueExpr(OpaqueValueExpr *E) {
71
40
    if (!LookThroughOpaqueValueExprs)
72
0
      return true;
73
40
    llvm::SaveAndRestore<bool> LookThrough(LookThroughOpaqueValueExprs, false);
74
40
    return TraverseStmt(E->getSourceExpr());
75
40
  }
76
77
1.57k
  bool TraverseDecl(Decl *D) {
78
1.57k
    if (isa<TranslationUnitDecl>(D))
79
87
      return LexicallyOrderedRecursiveASTVisitor::TraverseDecl(D);
80
1.48k
    if (D->isImplicit())
81
607
      return true;
82
877
83
877
    // Check if this declaration is written in the file of interest.
84
877
    const SourceRange DeclRange = D->getSourceRange();
85
877
    const SourceManager &SM = Context.getSourceManager();
86
877
    SourceLocation FileLoc;
87
877
    if (DeclRange.getBegin().isMacroID() && 
!DeclRange.getEnd().isMacroID()0
)
88
0
      FileLoc = DeclRange.getEnd();
89
877
    else
90
877
      FileLoc = SM.getSpellingLoc(DeclRange.getBegin());
91
877
    if (SM.getFileID(FileLoc) != TargetFile)
92
0
      return true;
93
877
94
877
    SourceSelectionKind SelectionKind =
95
877
        selectionKindFor(getLexicalDeclRange(D, SM, Context.getLangOpts()));
96
877
    SelectionStack.push_back(
97
877
        SelectedASTNode(DynTypedNode::create(*D), SelectionKind));
98
877
    LexicallyOrderedRecursiveASTVisitor::TraverseDecl(D);
99
877
    popAndAddToSelectionIfSelected(SelectionKind);
100
877
101
877
    if (DeclRange.getEnd().isValid() &&
102
877
        SM.isBeforeInTranslationUnit(SelectionEnd.isValid() ? 
SelectionEnd856
103
877
                                                            : 
SelectionBegin21
,
104
877
                                     DeclRange.getEnd())) {
105
127
      // Stop early when we've reached a declaration after the selection.
106
127
      return false;
107
127
    }
108
750
    return true;
109
750
  }
110
111
2.40k
  bool TraverseStmt(Stmt *S) {
112
2.40k
    if (!S)
113
31
      return true;
114
2.37k
    if (auto *Opaque = dyn_cast<OpaqueValueExpr>(S))
115
40
      return TraverseOpaqueValueExpr(Opaque);
116
2.33k
    // Avoid selecting implicit 'this' expressions.
117
2.33k
    if (auto *TE = dyn_cast<CXXThisExpr>(S)) {
118
3
      if (TE->isImplicit())
119
3
        return true;
120
2.32k
    }
121
2.32k
    // FIXME (Alex Lorenz): Improve handling for macro locations.
122
2.32k
    SourceSelectionKind SelectionKind =
123
2.32k
        selectionKindFor(CharSourceRange::getTokenRange(S->getSourceRange()));
124
2.32k
    SelectionStack.push_back(
125
2.32k
        SelectedASTNode(DynTypedNode::create(*S), SelectionKind));
126
2.32k
    LexicallyOrderedRecursiveASTVisitor::TraverseStmt(S);
127
2.32k
    popAndAddToSelectionIfSelected(SelectionKind);
128
2.32k
    return true;
129
2.32k
  }
130
131
private:
132
3.20k
  void popAndAddToSelectionIfSelected(SourceSelectionKind SelectionKind) {
133
3.20k
    SelectedASTNode Node = std::move(SelectionStack.back());
134
3.20k
    SelectionStack.pop_back();
135
3.20k
    if (SelectionKind != SourceSelectionKind::None || 
!Node.Children.empty()2.56k
)
136
637
      SelectionStack.back().Children.push_back(std::move(Node));
137
3.20k
  }
138
139
3.20k
  SourceSelectionKind selectionKindFor(CharSourceRange Range) {
140
3.20k
    SourceLocation End = Range.getEnd();
141
3.20k
    const SourceManager &SM = Context.getSourceManager();
142
3.20k
    if (Range.isTokenRange())
143
3.18k
      End = Lexer::getLocForEndOfToken(End, 0, SM, Context.getLangOpts());
144
3.20k
    if (!SourceLocation::isPairOfFileLocations(Range.getBegin(), End))
145
0
      return SourceSelectionKind::None;
146
3.20k
    if (!SelectionEnd.isValid()) {
147
80
      // Do a quick check when the selection is of length 0.
148
80
      if (SM.isPointWithin(SelectionBegin, Range.getBegin(), End))
149
13
        return SourceSelectionKind::ContainsSelection;
150
67
      return SourceSelectionKind::None;
151
67
    }
152
3.12k
    bool HasStart = SM.isPointWithin(SelectionBegin, Range.getBegin(), End);
153
3.12k
    bool HasEnd = SM.isPointWithin(SelectionEnd, Range.getBegin(), End);
154
3.12k
    if (HasStart && 
HasEnd313
)
155
260
      return SourceSelectionKind::ContainsSelection;
156
2.86k
    if (SM.isPointWithin(Range.getBegin(), SelectionBegin, SelectionEnd) &&
157
2.86k
        
SM.isPointWithin(End, SelectionBegin, SelectionEnd)354
)
158
345
      return SourceSelectionKind::InsideSelection;
159
2.52k
    // Ensure there's at least some overlap with the 'start'/'end' selection
160
2.52k
    // types.
161
2.52k
    if (HasStart && 
SelectionBegin != End12
)
162
10
      return SourceSelectionKind::ContainsSelectionStart;
163
2.51k
    if (HasEnd && 
SelectionEnd != Range.getBegin()9
)
164
8
      return SourceSelectionKind::ContainsSelectionEnd;
165
2.50k
166
2.50k
    return SourceSelectionKind::None;
167
2.50k
  }
168
169
  const SourceLocation SelectionBegin, SelectionEnd;
170
  FileID TargetFile;
171
  const ASTContext &Context;
172
  std::vector<SelectedASTNode> SelectionStack;
173
  /// Controls whether we can traverse through the OpaqueValueExpr. This is
174
  /// typically enabled during the traversal of syntactic form for
175
  /// PseudoObjectExprs.
176
  bool LookThroughOpaqueValueExprs = false;
177
};
178
179
} // end anonymous namespace
180
181
Optional<SelectedASTNode>
182
clang::tooling::findSelectedASTNodes(const ASTContext &Context,
183
87
                                     SourceRange SelectionRange) {
184
87
  assert(SelectionRange.isValid() &&
185
87
         SourceLocation::isPairOfFileLocations(SelectionRange.getBegin(),
186
87
                                               SelectionRange.getEnd()) &&
187
87
         "Expected a file range");
188
87
  FileID TargetFile =
189
87
      Context.getSourceManager().getFileID(SelectionRange.getBegin());
190
87
  assert(Context.getSourceManager().getFileID(SelectionRange.getEnd()) ==
191
87
             TargetFile &&
192
87
         "selection range must span one file");
193
87
194
87
  ASTSelectionFinder Visitor(SelectionRange, TargetFile, Context);
195
87
  Visitor.TraverseDecl(Context.getTranslationUnitDecl());
196
87
  return Visitor.getSelectedASTNode();
197
87
}
198
199
7
static const char *selectionKindToString(SourceSelectionKind Kind) {
200
7
  switch (Kind) {
201
1
  case SourceSelectionKind::None:
202
1
    return "none";
203
6
  case SourceSelectionKind::ContainsSelection:
204
6
    return "contains-selection";
205
0
  case SourceSelectionKind::ContainsSelectionStart:
206
0
    return "contains-selection-start";
207
0
  case SourceSelectionKind::ContainsSelectionEnd:
208
0
    return "contains-selection-end";
209
0
  case SourceSelectionKind::InsideSelection:
210
0
    return "inside";
211
0
  }
212
0
  llvm_unreachable("invalid selection kind");
213
0
}
214
215
static void dump(const SelectedASTNode &Node, llvm::raw_ostream &OS,
216
7
                 unsigned Indent = 0) {
217
7
  OS.indent(Indent * 2);
218
7
  if (const Decl *D = Node.Node.get<Decl>()) {
219
3
    OS << D->getDeclKindName() << "Decl";
220
3
    if (const auto *ND = dyn_cast<NamedDecl>(D))
221
2
      OS << " \"" << ND->getNameAsString() << '"';
222
4
  } else if (const Stmt *S = Node.Node.get<Stmt>()) {
223
4
    OS << S->getStmtClassName();
224
4
  }
225
7
  OS << ' ' << selectionKindToString(Node.SelectionKind) << "\n";
226
7
  for (const auto &Child : Node.Children)
227
5
    dump(Child, OS, Indent + 1);
228
7
}
229
230
2
void SelectedASTNode::dump(llvm::raw_ostream &OS) const { ::dump(*this, OS); }
231
232
/// Returns true if the given node has any direct children with the following
233
/// selection kind.
234
///
235
/// Note: The direct children also include children of direct children with the
236
/// "None" selection kind.
237
static bool hasAnyDirectChildrenWithKind(const SelectedASTNode &Node,
238
276
                                         SourceSelectionKind Kind) {
239
276
  assert(Kind != SourceSelectionKind::None && "invalid predicate!");
240
305
  for (const auto &Child : Node.Children) {
241
305
    if (Child.SelectionKind == Kind)
242
217
      return true;
243
88
    if (Child.SelectionKind == SourceSelectionKind::None)
244
0
      return hasAnyDirectChildrenWithKind(Child, Kind);
245
88
  }
246
276
  
return false59
;
247
276
}
248
249
namespace {
250
struct SelectedNodeWithParents {
251
  SelectedASTNode::ReferenceType Node;
252
  llvm::SmallVector<SelectedASTNode::ReferenceType, 8> Parents;
253
254
  /// Canonicalizes the given selection by selecting different related AST nodes
255
  /// when it makes sense to do so.
256
  void canonicalize();
257
};
258
259
enum SelectionCanonicalizationAction { KeepSelection, SelectParent };
260
261
/// Returns the canonicalization action which should be applied to the
262
/// selected statement.
263
SelectionCanonicalizationAction
264
40
getSelectionCanonizalizationAction(const Stmt *S, const Stmt *Parent) {
265
40
  // Select the parent expression when:
266
40
  // - The string literal in ObjC string literal is selected, e.g.:
267
40
  //     @"test"   becomes   @"test"
268
40
  //      ~~~~~~             ~~~~~~~
269
40
  if (isa<StringLiteral>(S) && 
isa<ObjCStringLiteral>(Parent)3
)
270
2
    return SelectParent;
271
38
  // The entire call should be selected when just the member expression
272
38
  // that refers to the method or the decl ref that refers to the function
273
38
  // is selected.
274
38
  //    f.call(args)  becomes  f.call(args)
275
38
  //      ~~~~                 ~~~~~~~~~~~~
276
38
  //    func(args)  becomes  func(args)
277
38
  //    ~~~~                 ~~~~~~~~~~
278
38
  else if (const auto *CE = dyn_cast<CallExpr>(Parent)) {
279
4
    if ((isa<MemberExpr>(S) || 
isa<DeclRefExpr>(S)1
) &&
280
4
        CE->getCallee()->IgnoreImpCasts() == S)
281
3
      return SelectParent;
282
35
  }
283
35
  // FIXME: Syntactic form -> Entire pseudo-object expr.
284
35
  return KeepSelection;
285
35
}
286
287
} // end anonymous namespace
288
289
49
void SelectedNodeWithParents::canonicalize() {
290
49
  const Stmt *S = Node.get().Node.get<Stmt>();
291
49
  assert(S && "non statement selection!");
292
49
  const Stmt *Parent = Parents[Parents.size() - 1].get().Node.get<Stmt>();
293
49
  if (!Parent)
294
9
    return;
295
40
296
40
  // Look through the implicit casts in the parents.
297
40
  unsigned ParentIndex = 1;
298
41
  for (; (ParentIndex + 1) <= Parents.size() && isa<ImplicitCastExpr>(Parent);
299
40
       
++ParentIndex1
) {
300
1
    const Stmt *NewParent =
301
1
        Parents[Parents.size() - ParentIndex - 1].get().Node.get<Stmt>();
302
1
    if (!NewParent)
303
0
      break;
304
1
    Parent = NewParent;
305
1
  }
306
40
307
40
  switch (getSelectionCanonizalizationAction(S, Parent)) {
308
5
  case SelectParent:
309
5
    Node = Parents[Parents.size() - ParentIndex];
310
11
    for (; ParentIndex != 0; 
--ParentIndex6
)
311
6
      Parents.pop_back();
312
5
    break;
313
35
  case KeepSelection:
314
35
    break;
315
40
  }
316
40
}
317
318
/// Finds the set of bottom-most selected AST nodes that are in the selection
319
/// tree with the specified selection kind.
320
///
321
/// For example, given the following selection tree:
322
///
323
/// FunctionDecl "f" contains-selection
324
///   CompoundStmt contains-selection [#1]
325
///     CallExpr inside
326
///     ImplicitCastExpr inside
327
///       DeclRefExpr inside
328
///     IntegerLiteral inside
329
///     IntegerLiteral inside
330
/// FunctionDecl "f2" contains-selection
331
///   CompoundStmt contains-selection [#2]
332
///     CallExpr inside
333
///     ImplicitCastExpr inside
334
///       DeclRefExpr inside
335
///     IntegerLiteral inside
336
///     IntegerLiteral inside
337
///
338
/// This function will find references to nodes #1 and #2 when searching for the
339
/// \c ContainsSelection kind.
340
static void findDeepestWithKind(
341
    const SelectedASTNode &ASTSelection,
342
    llvm::SmallVectorImpl<SelectedNodeWithParents> &MatchingNodes,
343
    SourceSelectionKind Kind,
344
276
    llvm::SmallVectorImpl<SelectedASTNode::ReferenceType> &ParentStack) {
345
276
  if (ASTSelection.Node.get<DeclStmt>()) {
346
12
    // Select the entire decl stmt when any of its child declarations is the
347
12
    // bottom-most.
348
12
    for (const auto &Child : ASTSelection.Children) {
349
12
      if (!hasAnyDirectChildrenWithKind(Child, Kind)) {
350
5
        MatchingNodes.push_back(SelectedNodeWithParents{
351
5
            std::cref(ASTSelection), {ParentStack.begin(), ParentStack.end()}});
352
5
        return;
353
5
      }
354
12
    }
355
264
  } else {
356
264
    if (!hasAnyDirectChildrenWithKind(ASTSelection, Kind)) {
357
54
      // This node is the bottom-most.
358
54
      MatchingNodes.push_back(SelectedNodeWithParents{
359
54
          std::cref(ASTSelection), {ParentStack.begin(), ParentStack.end()}});
360
54
      return;
361
54
    }
362
217
  }
363
217
  // Search in the children.
364
217
  ParentStack.push_back(std::cref(ASTSelection));
365
217
  for (const auto &Child : ASTSelection.Children)
366
217
    findDeepestWithKind(Child, MatchingNodes, Kind, ParentStack);
367
217
  ParentStack.pop_back();
368
217
}
369
370
static void findDeepestWithKind(
371
    const SelectedASTNode &ASTSelection,
372
    llvm::SmallVectorImpl<SelectedNodeWithParents> &MatchingNodes,
373
59
    SourceSelectionKind Kind) {
374
59
  llvm::SmallVector<SelectedASTNode::ReferenceType, 16> ParentStack;
375
59
  findDeepestWithKind(ASTSelection, MatchingNodes, Kind, ParentStack);
376
59
}
377
378
Optional<CodeRangeASTSelection>
379
CodeRangeASTSelection::create(SourceRange SelectionRange,
380
62
                              const SelectedASTNode &ASTSelection) {
381
62
  // Code range is selected when the selection range is not empty.
382
62
  if (SelectionRange.getBegin() == SelectionRange.getEnd())
383
3
    return None;
384
59
  llvm::SmallVector<SelectedNodeWithParents, 4> ContainSelection;
385
59
  findDeepestWithKind(ASTSelection, ContainSelection,
386
59
                      SourceSelectionKind::ContainsSelection);
387
59
  // We are looking for a selection in one body of code, so let's focus on
388
59
  // one matching result.
389
59
  if (ContainSelection.size() != 1)
390
0
    return None;
391
59
  SelectedNodeWithParents &Selected = ContainSelection[0];
392
59
  if (!Selected.Node.get().Node.get<Stmt>())
393
2
    return None;
394
57
  const Stmt *CodeRangeStmt = Selected.Node.get().Node.get<Stmt>();
395
57
  if (!isa<CompoundStmt>(CodeRangeStmt)) {
396
49
    Selected.canonicalize();
397
49
    return CodeRangeASTSelection(Selected.Node, Selected.Parents,
398
49
                                 /*AreChildrenSelected=*/false);
399
49
  }
400
8
  // FIXME (Alex L): First selected SwitchCase means that first case statement.
401
8
  // is selected actually
402
8
  // (See https://github.com/apple/swift-clang & CompoundStmtRange).
403
8
404
8
  // FIXME (Alex L): Tweak selection rules for compound statements, see:
405
8
  // https://github.com/apple/swift-clang/blob/swift-4.1-branch/lib/Tooling/
406
8
  // Refactor/ASTSlice.cpp#L513
407
8
  // The user selected multiple statements in a compound statement.
408
8
  Selected.Parents.push_back(Selected.Node);
409
8
  return CodeRangeASTSelection(Selected.Node, Selected.Parents,
410
8
                               /*AreChildrenSelected=*/true);
411
8
}
412
413
77
static bool isFunctionLikeDeclaration(const Decl *D) {
414
77
  // FIXME (Alex L): Test for BlockDecl.
415
77
  return isa<FunctionDecl>(D) || 
isa<ObjCMethodDecl>(D)21
;
416
77
}
417
418
41
bool CodeRangeASTSelection::isInFunctionLikeBodyOfCode() const {
419
41
  bool IsPrevCompound = false;
420
41
  // Scan through the parents (bottom-to-top) and check if the selection is
421
41
  // contained in a compound statement that's a body of a function/method
422
41
  // declaration.
423
103
  for (const auto &Parent : llvm::reverse(Parents)) {
424
103
    const DynTypedNode &Node = Parent.get().Node;
425
103
    if (const auto *D = Node.get<Decl>()) {
426
50
      if (isFunctionLikeDeclaration(D))
427
36
        return IsPrevCompound;
428
14
      // Stop the search at any type declaration to avoid returning true for
429
14
      // expressions in type declarations in functions, like:
430
14
      // function foo() { struct X {
431
14
      //   int m = /*selection:*/ 1 + 2 /*selection end*/; }; };
432
14
      if (isa<TypeDecl>(D))
433
4
        return false;
434
63
    }
435
63
    IsPrevCompound = Node.get<CompoundStmt>() != nullptr;
436
63
  }
437
41
  
return false1
;
438
41
}
439
440
26
const Decl *CodeRangeASTSelection::getFunctionLikeNearestParent() const {
441
60
  for (const auto &Parent : llvm::reverse(Parents)) {
442
60
    const DynTypedNode &Node = Parent.get().Node;
443
60
    if (const auto *D = Node.get<Decl>()) {
444
27
      if (isFunctionLikeDeclaration(D))
445
26
        return D;
446
27
    }
447
60
  }
448
26
  
return nullptr0
;
449
26
}