clang/AST/LexicallyOrderedRecursiveASTVisitor.h

0001 //===--- LexicallyOrderedRecursiveASTVisitor.h - ----------------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 //  This file defines the LexicallyOrderedRecursiveASTVisitor interface, which
0010 //  recursively traverses the entire AST in a lexical order.
0011 //
0012 //===----------------------------------------------------------------------===//
0013
0014 #ifndef LLVM_CLANG_AST_LEXICALLYORDEREDRECURSIVEASTVISITOR_H
0015 #define LLVM_CLANG_AST_LEXICALLYORDEREDRECURSIVEASTVISITOR_H
0016
0017 #include "clang/AST/RecursiveASTVisitor.h"
0018 #include "clang/Basic/LLVM.h"
0019 #include "clang/Basic/SourceManager.h"
0020 #include "llvm/Support/SaveAndRestore.h"
0021
0022 namespace clang {
0023
0024 /// A RecursiveASTVisitor subclass that guarantees that AST traversal is
0025 /// performed in a lexical order (i.e. the order in which declarations are
0026 /// written in the source).
0027 ///
0028 /// RecursiveASTVisitor doesn't guarantee lexical ordering because there are
0029 /// some declarations, like Objective-C @implementation declarations
0030 /// that might be represented in the AST differently to how they were written
0031 /// in the source.
0032 /// In particular, Objective-C @implementation declarations may contain
0033 /// non-Objective-C declarations, like functions:
0034 ///
0035 ///   @implementation MyClass
0036 ///
0037 ///   - (void) method { }
0038 ///   void normalFunction() { }
0039 ///
0040 ///   @end
0041 ///
0042 /// Clang's AST stores these declarations outside of the @implementation
0043 /// declaration, so the example above would be represented using the following
0044 /// AST:
0045 ///   |-ObjCImplementationDecl ... MyClass
0046 ///   | `-ObjCMethodDecl ... method
0047 ///   |    ...
0048 ///   `-FunctionDecl ... normalFunction
0049 ///       ...
0050 ///
0051 /// This class ensures that these declarations are traversed before the
0052 /// corresponding TraverseDecl for the @implementation returns. This ensures
0053 /// that the lexical parent relationship between these declarations and the
0054 /// @implementation is preserved while traversing the AST. Note that the
0055 /// current implementation doesn't mix these declarations with the declarations
0056 /// contained in the @implementation, so the traversal of all of the
0057 /// declarations in the @implementation still doesn't follow the lexical order.
0058 template <typename Derived>
0059 class LexicallyOrderedRecursiveASTVisitor
0060     : public RecursiveASTVisitor<Derived> {
0061   using BaseType = RecursiveASTVisitor<Derived>;
0062
0063 public:
0064   LexicallyOrderedRecursiveASTVisitor(const SourceManager &SM) : SM(SM) {}
0065
0066   bool TraverseObjCImplementationDecl(ObjCImplementationDecl *D) {
0067     // Objective-C @implementation declarations should not trigger early exit
0068     // until the additional decls are traversed as their children are not
0069     // lexically ordered.
0070     bool Result = BaseType::TraverseObjCImplementationDecl(D);
0071     return TraverseAdditionalLexicallyNestedDeclarations() ? Result : false;
0072   }
0073
0074   bool TraverseObjCCategoryImplDecl(ObjCCategoryImplDecl *D) {
0075     bool Result = BaseType::TraverseObjCCategoryImplDecl(D);
0076     return TraverseAdditionalLexicallyNestedDeclarations() ? Result : false;
0077   }
0078
0079   bool TraverseDeclContextHelper(DeclContext *DC) {
0080     if (!DC)
0081       return true;
0082
0083     for (auto I = DC->decls_begin(), E = DC->decls_end(); I != E;) {
0084       Decl *Child = *I;
0085       if (BaseType::canIgnoreChildDeclWhileTraversingDeclContext(Child)) {
0086         ++I;
0087         continue;
0088       }
0089       if (!isa<ObjCImplementationDecl>(Child) &&
0090           !isa<ObjCCategoryImplDecl>(Child)) {
0091         if (!BaseType::getDerived().TraverseDecl(Child))
0092           return false;
0093         ++I;
0094         continue;
0095       }
0096       // Gather declarations that follow the Objective-C implementation
0097       // declarations but are lexically contained in the implementation.
0098       LexicallyNestedDeclarations.clear();
0099       for (++I; I != E; ++I) {
0100         Decl *Sibling = *I;
0101         if (!SM.isBeforeInTranslationUnit(Sibling->getBeginLoc(),
0102                                           Child->getEndLoc()))
0103           break;
0104         if (!BaseType::canIgnoreChildDeclWhileTraversingDeclContext(Sibling))
0105           LexicallyNestedDeclarations.push_back(Sibling);
0106       }
0107       if (!BaseType::getDerived().TraverseDecl(Child))
0108         return false;
0109     }
0110     return true;
0111   }
0112
0113   Stmt::child_range getStmtChildren(Stmt *S) { return S->children(); }
0114
0115   SmallVector<Stmt *, 8> getStmtChildren(CXXOperatorCallExpr *CE) {
0116     SmallVector<Stmt *, 8> Children(CE->children());
0117     bool Swap;
0118     // Switch the operator and the first operand for all infix and postfix
0119     // operations.
0120     switch (CE->getOperator()) {
0121     case OO_Arrow:
0122     case OO_Call:
0123     case OO_Subscript:
0124       Swap = true;
0125       break;
0126     case OO_PlusPlus:
0127     case OO_MinusMinus:
0128       // These are postfix unless there is exactly one argument.
0129       Swap = Children.size() != 2;
0130       break;
0131     default:
0132       Swap = CE->isInfixBinaryOp();
0133       break;
0134     }
0135     if (Swap && Children.size() > 1)
0136       std::swap(Children[0], Children[1]);
0137     return Children;
0138   }
0139
0140 private:
0141   bool TraverseAdditionalLexicallyNestedDeclarations() {
0142     // FIXME: Ideally the gathered declarations and the declarations in the
0143     // @implementation should be mixed and sorted to get a true lexical order,
0144     // but right now we only care about getting the correct lexical parent, so
0145     // we can traverse the gathered nested declarations after the declarations
0146     // in the decl context.
0147     assert(!BaseType::getDerived().shouldTraversePostOrder() &&
0148            "post-order traversal is not supported for lexically ordered "
0149            "recursive ast visitor");
0150     for (Decl *D : LexicallyNestedDeclarations) {
0151       if (!BaseType::getDerived().TraverseDecl(D))
0152         return false;
0153     }
0154     return true;
0155   }
0156
0157   const SourceManager &SM;
0158   llvm::SmallVector<Decl *, 8> LexicallyNestedDeclarations;
0159 };
0160
0161 } // end namespace clang
0162
0163 #endif // LLVM_CLANG_AST_LEXICALLYORDEREDRECURSIVEASTVISITOR_H