1//===--- LexicallyOrderedRecursiveASTVisitor.h - ----------------*- 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//  This file defines the LexicallyOrderedRecursiveASTVisitor interface, which
10//  recursively traverses the entire AST in a lexical order.
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_CLANG_AST_LEXICALLY_ORDERED_RECURSIVEASTVISITOR_H
15#define LLVM_CLANG_AST_LEXICALLY_ORDERED_RECURSIVEASTVISITOR_H
16
17#include "clang/AST/RecursiveASTVisitor.h"
18#include "clang/Basic/LLVM.h"
19#include "clang/Basic/SourceManager.h"
20#include "llvm/Support/SaveAndRestore.h"
21
22namespace clang {
23
24/// A RecursiveASTVisitor subclass that guarantees that AST traversal is
25/// performed in a lexical order (i.e. the order in which declarations are
26/// written in the source).
27///
28/// RecursiveASTVisitor doesn't guarantee lexical ordering because there are
29/// some declarations, like Objective-C @implementation declarations
30/// that might be represented in the AST differently to how they were written
31/// in the source.
32/// In particular, Objective-C @implementation declarations may contain
33/// non-Objective-C declarations, like functions:
34///
35///   @implementation MyClass
36///
37///   - (void) method { }
38///   void normalFunction() { }
39///
40///   @end
41///
42/// Clang's AST stores these declarations outside of the @implementation
43/// declaration, so the example above would be represented using the following
44/// AST:
45///   |-ObjCImplementationDecl ... MyClass
46///   | `-ObjCMethodDecl ... method
47///   |    ...
48///   `-FunctionDecl ... normalFunction
49///       ...
50///
51/// This class ensures that these declarations are traversed before the
52/// corresponding TraverseDecl for the @implementation returns. This ensures
53/// that the lexical parent relationship between these declarations and the
54/// @implementation is preserved while traversing the AST. Note that the
55/// current implementation doesn't mix these declarations with the declarations
56/// contained in the @implementation, so the traversal of all of the
57/// declarations in the @implementation still doesn't follow the lexical order.
58template <typename Derived>
59class LexicallyOrderedRecursiveASTVisitor
60    : public RecursiveASTVisitor<Derived> {
61  using BaseType = RecursiveASTVisitor<Derived>;
62
63public:
64  LexicallyOrderedRecursiveASTVisitor(const SourceManager &SM) : SM(SM) {}
65
66  bool TraverseObjCImplementationDecl(ObjCImplementationDecl *D) {
67    // Objective-C @implementation declarations should not trigger early exit
68    // until the additional decls are traversed as their children are not
69    // lexically ordered.
70    bool Result = BaseType::TraverseObjCImplementationDecl(D);
71    return TraverseAdditionalLexicallyNestedDeclarations() ? Result : false;
72  }
73
74  bool TraverseObjCCategoryImplDecl(ObjCCategoryImplDecl *D) {
75    bool Result = BaseType::TraverseObjCCategoryImplDecl(D);
76    return TraverseAdditionalLexicallyNestedDeclarations() ? Result : false;
77  }
78
79  bool TraverseDeclContextHelper(DeclContext *DC) {
80    if (!DC)
81      return true;
82
83    for (auto I = DC->decls_begin(), E = DC->decls_end(); I != E;) {
84      Decl *Child = *I;
85      if (BaseType::canIgnoreChildDeclWhileTraversingDeclContext(Child)) {
86        ++I;
87        continue;
88      }
89      if (!isa<ObjCImplementationDecl>(Child) &&
90          !isa<ObjCCategoryImplDecl>(Child)) {
91        if (!BaseType::getDerived().TraverseDecl(Child))
92          return false;
93        ++I;
94        continue;
95      }
96      // Gather declarations that follow the Objective-C implementation
97      // declarations but are lexically contained in the implementation.
98      LexicallyNestedDeclarations.clear();
99      for (++I; I != E; ++I) {
100        Decl *Sibling = *I;
101        if (!SM.isBeforeInTranslationUnit(Sibling->getBeginLoc(),
102                                          Child->getEndLoc()))
103          break;
104        if (!BaseType::canIgnoreChildDeclWhileTraversingDeclContext(Sibling))
105          LexicallyNestedDeclarations.push_back(Sibling);
106      }
107      if (!BaseType::getDerived().TraverseDecl(Child))
108        return false;
109    }
110    return true;
111  }
112
113  Stmt::child_range getStmtChildren(Stmt *S) { return S->children(); }
114
115  SmallVector<Stmt *, 8> getStmtChildren(CXXOperatorCallExpr *CE) {
116    SmallVector<Stmt *, 8> Children(CE->children());
117    bool Swap;
118    // Switch the operator and the first operand for all infix and postfix
119    // operations.
120    switch (CE->getOperator()) {
121    case OO_Arrow:
122    case OO_Call:
123    case OO_Subscript:
124      Swap = true;
125      break;
126    case OO_PlusPlus:
127    case OO_MinusMinus:
128      // These are postfix unless there is exactly one argument.
129      Swap = Children.size() != 2;
130      break;
131    default:
132      Swap = CE->isInfixBinaryOp();
133      break;
134    }
135    if (Swap && Children.size() > 1)
136      std::swap(Children[0], Children[1]);
137    return Children;
138  }
139
140private:
141  bool TraverseAdditionalLexicallyNestedDeclarations() {
142    // FIXME: Ideally the gathered declarations and the declarations in the
143    // @implementation should be mixed and sorted to get a true lexical order,
144    // but right now we only care about getting the correct lexical parent, so
145    // we can traverse the gathered nested declarations after the declarations
146    // in the decl context.
147    assert(!BaseType::getDerived().shouldTraversePostOrder() &&
148           "post-order traversal is not supported for lexically ordered "
149           "recursive ast visitor");
150    for (Decl *D : LexicallyNestedDeclarations) {
151      if (!BaseType::getDerived().TraverseDecl(D))
152        return false;
153    }
154    return true;
155  }
156
157  const SourceManager &SM;
158  llvm::SmallVector<Decl *, 8> LexicallyNestedDeclarations;
159};
160
161} // end namespace clang
162
163#endif // LLVM_CLANG_AST_LEXICALLY_ORDERED_RECURSIVEASTVISITOR_H
164