contrib/llvm-project/clang/include/clang/AST/LexicallyOrderedRecursiveASTVisitor.h

   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:
  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
 140 private:
 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