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 23namespace 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. 59template <typename Derived> 60class LexicallyOrderedRecursiveASTVisitor 61 : public RecursiveASTVisitor<Derived> { 62 using BaseType = RecursiveASTVisitor<Derived>; 63 64public: 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 141private: 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