contrib/llvm/tools/clang/include/clang/AST/LexicallyOrderedRecursiveASTVisitor.h

   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->getBeginLoc(),
 103                                           Child->getEndLoc()))
 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