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