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