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 
22 namespace 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.
58 template <typename Derived>
59 class LexicallyOrderedRecursiveASTVisitor
60     : public RecursiveASTVisitor<Derived> {
61   using BaseType = RecursiveASTVisitor<Derived>;
62 
63 public:
LexicallyOrderedRecursiveASTVisitor(const SourceManager & SM)64   LexicallyOrderedRecursiveASTVisitor(const SourceManager &SM) : SM(SM) {}
65 
TraverseObjCImplementationDecl(ObjCImplementationDecl * D)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 
TraverseObjCCategoryImplDecl(ObjCCategoryImplDecl * D)74   bool TraverseObjCCategoryImplDecl(ObjCCategoryImplDecl *D) {
75     bool Result = BaseType::TraverseObjCCategoryImplDecl(D);
76     return TraverseAdditionalLexicallyNestedDeclarations() ? Result : false;
77   }
78 
TraverseDeclContextHelper(DeclContext * DC)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 
getStmtChildren(Stmt * S)113   Stmt::child_range getStmtChildren(Stmt *S) { return S->children(); }
114 
getStmtChildren(CXXOperatorCallExpr * CE)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 
140 private:
TraverseAdditionalLexicallyNestedDeclarations()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