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