1 //===--- DirectiveTree.h - Find and strip preprocessor directives *- 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 // The pseudoparser tries to match a token stream to the C++ grammar.
10 // Preprocessor #defines and other directives are not part of this grammar, and
11 // should be removed before the file can be parsed.
12 //
13 // Conditional blocks like #if...#else...#endif are particularly tricky, as
14 // simply stripping the directives may not produce a grammatical result:
15 //
16 //   return
17 //     #ifndef DEBUG
18 //       1
19 //     #else
20 //       0
21 //     #endif
22 //       ;
23 //
24 // This header supports analyzing and removing the directives in a source file.
25 //
26 //===----------------------------------------------------------------------===//
27 
28 #ifndef CLANG_PSEUDO_DIRECTIVETREE_H
29 #define CLANG_PSEUDO_DIRECTIVETREE_H
30 
31 #include "clang-pseudo/Token.h"
32 #include "clang/Basic/TokenKinds.h"
33 #include <vector>
34 
35 namespace clang {
36 class LangOptions;
37 namespace pseudo {
38 
39 /// Describes the structure of a source file, as seen by the preprocessor.
40 ///
41 /// The structure is a tree, whose leaves are plain source code and directives,
42 /// and whose internal nodes are #if...#endif sections.
43 ///
44 /// (root)
45 /// |-+ Directive                    #include <stdio.h>
46 /// |-+ Code                         int main() {
47 /// | `                                printf("hello, ");
48 /// |-+ Conditional -+ Directive     #ifndef NDEBUG
49 /// | |-+ Code                         printf("debug\n");
50 /// | |-+ Directive                  #else
51 /// | |-+ Code                         printf("production\n");
52 /// | `-+ Directive                  #endif
53 /// |-+ Code                           return 0;
54 ///   `                              }
55 ///
56 /// Unlike the clang preprocessor, we model the full tree explicitly.
57 /// This class does not recognize macro usage, only directives.
58 struct DirectiveTree {
59   /// A range of code (and possibly comments) containing no directives.
60   struct Code {
61     Token::Range Tokens;
62   };
63   /// A preprocessor directive.
64   struct Directive {
65     /// Raw tokens making up the directive, starting with `#`.
66     Token::Range Tokens;
67     clang::tok::PPKeywordKind Kind = clang::tok::pp_not_keyword;
68   };
69   /// A preprocessor conditional section.
70   ///
71   /// This starts with an #if, #ifdef, #ifndef etc directive.
72   /// It covers all #else branches, and spans until the matching #endif.
73   struct Conditional {
74     /// The sequence of directives that introduce top-level alternative parses.
75     ///
76     /// The first branch will have an #if type directive.
77     /// Subsequent branches will have #else type directives.
78     std::vector<std::pair<Directive, DirectiveTree>> Branches;
79     /// The directive terminating the conditional, should be #endif.
80     Directive End;
81     /// The index of the conditional branch we chose as active.
82     /// None indicates no branch was taken (e.g. #if 0 ... #endif).
83     /// The initial tree from `parse()` has no branches marked as taken.
84     /// See `chooseConditionalBranches()`.
85     llvm::Optional<unsigned> Taken;
86   };
87 
88   /// Some piece of the file. {One of Code, Directive, Conditional}.
89   class Chunk; // Defined below.
90   std::vector<Chunk> Chunks;
91 
92   /// Extract preprocessor structure by examining the raw tokens.
93   static DirectiveTree parse(const TokenStream &);
94 
95   /// Produce a parseable token stream by stripping all directive tokens.
96   ///
97   /// Conditional sections are replaced by the taken branch, if any.
98   /// This tree must describe the provided token stream.
99   TokenStream stripDirectives(const TokenStream &) const;
100 };
101 llvm::raw_ostream &operator<<(llvm::raw_ostream &, const DirectiveTree &);
102 llvm::raw_ostream &operator<<(llvm::raw_ostream &, const DirectiveTree::Chunk &);
103 llvm::raw_ostream &operator<<(llvm::raw_ostream &, const DirectiveTree::Code &);
104 llvm::raw_ostream &operator<<(llvm::raw_ostream &,
105                               const DirectiveTree::Directive &);
106 llvm::raw_ostream &operator<<(llvm::raw_ostream &,
107                               const DirectiveTree::Conditional &);
108 
109 /// Selects a "taken" branch for each conditional directive in the file.
110 ///
111 /// The choice is somewhat arbitrary, but aims to produce a useful parse:
112 ///  - idioms like `#if 0` are respected
113 ///  - we avoid paths that reach `#error`
114 ///  - we try to maximize the amount of code seen
115 /// The choice may also be "no branch taken".
116 ///
117 /// Choices are also made for conditionals themselves inside not-taken branches:
118 ///   #if 1 // taken!
119 ///   #else // not taken
120 ///      #if 1 // taken!
121 ///      #endif
122 ///   #endif
123 ///
124 /// The choices are stored in Conditional::Taken nodes.
125 void chooseConditionalBranches(DirectiveTree &, const TokenStream &Code);
126 
127 // FIXME: This approximates std::variant<Code, Directive, Conditional>.
128 //         Switch once we can use C++17.
129 class DirectiveTree::Chunk {
130 public:
131   enum Kind { K_Empty, K_Code, K_Directive, K_Conditional };
kind()132   Kind kind() const {
133     return CodeVariant          ? K_Code
134            : DirectiveVariant   ? K_Directive
135            : ConditionalVariant ? K_Conditional
136                                 : K_Empty;
137   }
138 
139   Chunk() = delete;
140   Chunk(const Chunk &) = delete;
141   Chunk(Chunk &&) = default;
142   Chunk &operator=(const Chunk &) = delete;
143   Chunk &operator=(Chunk &&) = default;
144   ~Chunk() = default;
145 
146   // T => Chunk constructor.
Chunk(Code C)147   Chunk(Code C) : CodeVariant(std::move(C)) {}
Chunk(Directive C)148   Chunk(Directive C) : DirectiveVariant(std::move(C)) {}
Chunk(Conditional C)149   Chunk(Conditional C) : ConditionalVariant(std::move(C)) {}
150 
151   // Chunk => T& and const T& conversions.
152 #define CONVERSION(CONST, V)                                                   \
153   explicit operator CONST V &() CONST { return *V##Variant; }
154   CONVERSION(const, Code);
155   CONVERSION(, Code);
156   CONVERSION(const, Directive);
157   CONVERSION(, Directive);
158   CONVERSION(const, Conditional);
159   CONVERSION(, Conditional);
160 #undef CONVERSION
161 
162 private:
163   // Wasteful, a union variant would be better!
164   llvm::Optional<Code> CodeVariant;
165   llvm::Optional<Directive> DirectiveVariant;
166   llvm::Optional<Conditional> ConditionalVariant;
167 };
168 
169 } // namespace pseudo
170 } // namespace clang
171 
172 #endif // CLANG_PSEUDO_DIRECTIVETREE_H
173