1 | //===--- UnwrappedLineParser.h - Format C++ code ----------------*- 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 | /// \file |
10 | /// This file contains the declaration of the UnwrappedLineParser, |
11 | /// which turns a stream of tokens into UnwrappedLines. |
12 | /// |
13 | //===----------------------------------------------------------------------===// |
14 | |
15 | #ifndef LLVM_CLANG_LIB_FORMAT_UNWRAPPEDLINEPARSER_H |
16 | #define LLVM_CLANG_LIB_FORMAT_UNWRAPPEDLINEPARSER_H |
17 | |
18 | #include "Macros.h" |
19 | #include <stack> |
20 | |
21 | namespace clang { |
22 | namespace format { |
23 | |
24 | struct UnwrappedLineNode; |
25 | |
26 | /// An unwrapped line is a sequence of \c Token, that we would like to |
27 | /// put on a single line if there was no column limit. |
28 | /// |
29 | /// This is used as a main interface between the \c UnwrappedLineParser and the |
30 | /// \c UnwrappedLineFormatter. The key property is that changing the formatting |
31 | /// within an unwrapped line does not affect any other unwrapped lines. |
32 | struct UnwrappedLine { |
33 | UnwrappedLine() = default; |
34 | |
35 | /// The \c Tokens comprising this \c UnwrappedLine. |
36 | std::list<UnwrappedLineNode> Tokens; |
37 | |
38 | /// The indent level of the \c UnwrappedLine. |
39 | unsigned Level = 0; |
40 | |
41 | /// The \c PPBranchLevel (adjusted for header guards) if this line is a |
42 | /// \c InMacroBody line, and 0 otherwise. |
43 | unsigned PPLevel = 0; |
44 | |
45 | /// Whether this \c UnwrappedLine is part of a preprocessor directive. |
46 | bool InPPDirective = false; |
47 | /// Whether this \c UnwrappedLine is part of a pramga directive. |
48 | bool InPragmaDirective = false; |
49 | /// Whether it is part of a macro body. |
50 | bool InMacroBody = false; |
51 | |
52 | /// Nesting level of unbraced body of a control statement. |
53 | unsigned UnbracedBodyLevel = 0; |
54 | |
55 | bool MustBeDeclaration = false; |
56 | |
57 | /// Whether the parser has seen \c decltype(auto) in this line. |
58 | bool SeenDecltypeAuto = false; |
59 | |
60 | /// \c True if this line should be indented by ContinuationIndent in |
61 | /// addition to the normal indention level. |
62 | bool IsContinuation = false; |
63 | |
64 | /// If this \c UnwrappedLine closes a block in a sequence of lines, |
65 | /// \c MatchingOpeningBlockLineIndex stores the index of the corresponding |
66 | /// opening line. Otherwise, \c MatchingOpeningBlockLineIndex must be |
67 | /// \c kInvalidIndex. |
68 | size_t MatchingOpeningBlockLineIndex = kInvalidIndex; |
69 | |
70 | /// If this \c UnwrappedLine opens a block, stores the index of the |
71 | /// line with the corresponding closing brace. |
72 | size_t MatchingClosingBlockLineIndex = kInvalidIndex; |
73 | |
74 | static const size_t kInvalidIndex = -1; |
75 | |
76 | unsigned FirstStartColumn = 0; |
77 | }; |
78 | |
79 | /// Interface for users of the UnwrappedLineParser to receive the parsed lines. |
80 | /// Parsing a single snippet of code can lead to multiple runs, where each |
81 | /// run is a coherent view of the file. |
82 | /// |
83 | /// For example, different runs are generated: |
84 | /// - for different combinations of #if blocks |
85 | /// - when macros are involved, for the expanded code and the as-written code |
86 | /// |
87 | /// Some tokens will only be visible in a subset of the runs. |
88 | /// For each run, \c UnwrappedLineParser will call \c consumeUnwrappedLine |
89 | /// for each parsed unwrapped line, and then \c finishRun to indicate |
90 | /// that the set of unwrapped lines before is one coherent view of the |
91 | /// code snippet to be formatted. |
92 | class UnwrappedLineConsumer { |
93 | public: |
94 | virtual ~UnwrappedLineConsumer() {} |
95 | virtual void consumeUnwrappedLine(const UnwrappedLine &Line) = 0; |
96 | virtual void finishRun() = 0; |
97 | }; |
98 | |
99 | class FormatTokenSource; |
100 | |
101 | class UnwrappedLineParser { |
102 | public: |
103 | UnwrappedLineParser(SourceManager &SourceMgr, const FormatStyle &Style, |
104 | const AdditionalKeywords &Keywords, |
105 | unsigned FirstStartColumn, ArrayRef<FormatToken *> Tokens, |
106 | UnwrappedLineConsumer &Callback, |
107 | llvm::SpecificBumpPtrAllocator<FormatToken> &Allocator, |
108 | IdentifierTable &IdentTable); |
109 | |
110 | void parse(); |
111 | |
112 | private: |
113 | enum class IfStmtKind { |
114 | NotIf, // Not an if statement. |
115 | IfOnly, // An if statement without the else clause. |
116 | IfElse, // An if statement followed by else but not else if. |
117 | IfElseIf // An if statement followed by else if. |
118 | }; |
119 | |
120 | void reset(); |
121 | void parseFile(); |
122 | bool () const; |
123 | bool parseLevel(const FormatToken *OpeningBrace = nullptr, |
124 | IfStmtKind *IfKind = nullptr, |
125 | FormatToken **IfLeftBrace = nullptr); |
126 | bool mightFitOnOneLine(UnwrappedLine &Line, |
127 | const FormatToken *OpeningBrace = nullptr) const; |
128 | FormatToken *parseBlock(bool MustBeDeclaration = false, |
129 | unsigned AddLevels = 1u, bool MunchSemi = true, |
130 | bool KeepBraces = true, IfStmtKind *IfKind = nullptr, |
131 | bool UnindentWhitesmithsBraces = false); |
132 | void parseChildBlock(); |
133 | void parsePPDirective(); |
134 | void parsePPDefine(); |
135 | void parsePPIf(bool IfDef); |
136 | void parsePPElse(); |
137 | void parsePPEndIf(); |
138 | void parsePPPragma(); |
139 | void parsePPUnknown(); |
140 | void readTokenWithJavaScriptASI(); |
141 | void parseStructuralElement(const FormatToken *OpeningBrace = nullptr, |
142 | IfStmtKind *IfKind = nullptr, |
143 | FormatToken **IfLeftBrace = nullptr, |
144 | bool *HasDoWhile = nullptr, |
145 | bool *HasLabel = nullptr); |
146 | bool tryToParseBracedList(); |
147 | bool parseBracedList(bool IsAngleBracket = false, bool IsEnum = false); |
148 | bool parseParens(TokenType AmpAmpTokenType = TT_Unknown); |
149 | void parseSquare(bool LambdaIntroducer = false); |
150 | void keepAncestorBraces(); |
151 | void parseUnbracedBody(bool CheckEOF = false); |
152 | void handleAttributes(); |
153 | bool handleCppAttributes(); |
154 | bool isBlockBegin(const FormatToken &Tok) const; |
155 | FormatToken *parseIfThenElse(IfStmtKind *IfKind, bool KeepBraces = false, |
156 | bool IsVerilogAssert = false); |
157 | void parseTryCatch(); |
158 | void parseLoopBody(bool KeepBraces, bool WrapRightBrace); |
159 | void parseForOrWhileLoop(bool HasParens = true); |
160 | void parseDoWhile(); |
161 | void parseLabel(bool LeftAlignLabel = false); |
162 | void parseCaseLabel(); |
163 | void parseSwitch(bool IsExpr); |
164 | void parseNamespace(); |
165 | bool parseModuleImport(); |
166 | void parseNew(); |
167 | void parseAccessSpecifier(); |
168 | bool parseEnum(); |
169 | bool parseStructLike(); |
170 | bool parseRequires(bool SeenEqual); |
171 | void parseRequiresClause(FormatToken *RequiresToken); |
172 | void parseRequiresExpression(FormatToken *RequiresToken); |
173 | void parseConstraintExpression(); |
174 | void parseCppExportBlock(); |
175 | void parseNamespaceOrExportBlock(unsigned AddLevels); |
176 | void parseJavaEnumBody(); |
177 | // Parses a record (aka class) as a top level element. If ParseAsExpr is true, |
178 | // parses the record as a child block, i.e. if the class declaration is an |
179 | // expression. |
180 | void parseRecord(bool ParseAsExpr = false, bool IsJavaRecord = false); |
181 | void parseObjCLightweightGenerics(); |
182 | void parseObjCMethod(); |
183 | void parseObjCProtocolList(); |
184 | void parseObjCUntilAtEnd(); |
185 | void parseObjCInterfaceOrImplementation(); |
186 | bool parseObjCProtocol(); |
187 | void parseJavaScriptEs6ImportExport(); |
188 | void parseStatementMacro(); |
189 | void parseCSharpAttribute(); |
190 | // Parse a C# generic type constraint: `where T : IComparable<T>`. |
191 | // See: |
192 | // https://docs.microsoft.com/en-us/dotnet/csharp/language-reference/keywords/where-generic-type-constraint |
193 | void parseCSharpGenericTypeConstraint(); |
194 | bool tryToParseLambda(); |
195 | bool tryToParseChildBlock(); |
196 | bool tryToParseLambdaIntroducer(); |
197 | bool tryToParsePropertyAccessor(); |
198 | void tryToParseJSFunction(); |
199 | bool tryToParseSimpleAttribute(); |
200 | void parseVerilogHierarchyIdentifier(); |
201 | void parseVerilogSensitivityList(); |
202 | // Returns the number of levels of indentation in addition to the normal 1 |
203 | // level for a block, used for indenting case labels. |
204 | unsigned (); |
205 | void parseVerilogTable(); |
206 | void parseVerilogCaseLabel(); |
207 | std::optional<llvm::SmallVector<llvm::SmallVector<FormatToken *, 8>, 1>> |
208 | parseMacroCall(); |
209 | |
210 | // Used by addUnwrappedLine to denote whether to keep or remove a level |
211 | // when resetting the line state. |
212 | enum class LineLevel { Remove, Keep }; |
213 | |
214 | void addUnwrappedLine(LineLevel AdjustLevel = LineLevel::Remove); |
215 | bool eof() const; |
216 | // LevelDifference is the difference of levels after and before the current |
217 | // token. For example: |
218 | // - if the token is '{' and opens a block, LevelDifference is 1. |
219 | // - if the token is '}' and closes a block, LevelDifference is -1. |
220 | void nextToken(int LevelDifference = 0); |
221 | void readToken(int LevelDifference = 0); |
222 | |
223 | // Decides which comment tokens should be added to the current line and which |
224 | // should be added as comments before the next token. |
225 | // |
226 | // Comments specifies the sequence of comment tokens to analyze. They get |
227 | // either pushed to the current line or added to the comments before the next |
228 | // token. |
229 | // |
230 | // NextTok specifies the next token. A null pointer NextTok is supported, and |
231 | // signifies either the absence of a next token, or that the next token |
232 | // shouldn't be taken into account for the analysis. |
233 | void (const ArrayRef<FormatToken *> &, |
234 | const FormatToken *NextTok); |
235 | |
236 | // Adds the comment preceding the next token to unwrapped lines. |
237 | void (bool NewlineBeforeNext); |
238 | void pushToken(FormatToken *Tok); |
239 | void calculateBraceTypes(bool ExpectClassBody = false); |
240 | void setPreviousRBraceType(TokenType Type); |
241 | |
242 | // Marks a conditional compilation edge (for example, an '#if', '#ifdef', |
243 | // '#else' or merge conflict marker). If 'Unreachable' is true, assumes |
244 | // this branch either cannot be taken (for example '#if false'), or should |
245 | // not be taken in this round. |
246 | void conditionalCompilationCondition(bool Unreachable); |
247 | void conditionalCompilationStart(bool Unreachable); |
248 | void conditionalCompilationAlternative(); |
249 | void conditionalCompilationEnd(); |
250 | |
251 | bool isOnNewLine(const FormatToken &FormatTok); |
252 | |
253 | // Returns whether there is a macro expansion in the line, i.e. a token that |
254 | // was expanded from a macro call. |
255 | bool containsExpansion(const UnwrappedLine &Line) const; |
256 | |
257 | // Compute hash of the current preprocessor branch. |
258 | // This is used to identify the different branches, and thus track if block |
259 | // open and close in the same branch. |
260 | size_t computePPHash() const; |
261 | |
262 | bool parsingPPDirective() const { return CurrentLines != &Lines; } |
263 | |
264 | // FIXME: We are constantly running into bugs where Line.Level is incorrectly |
265 | // subtracted from beyond 0. Introduce a method to subtract from Line.Level |
266 | // and use that everywhere in the Parser. |
267 | std::unique_ptr<UnwrappedLine> Line; |
268 | |
269 | // Lines that are created by macro expansion. |
270 | // When formatting code containing macro calls, we first format the expanded |
271 | // lines to set the token types correctly. Afterwards, we format the |
272 | // reconstructed macro calls, re-using the token types determined in the first |
273 | // step. |
274 | // ExpandedLines will be reset every time we create a new LineAndExpansion |
275 | // instance once a line containing macro calls has been parsed. |
276 | SmallVector<UnwrappedLine, 8> CurrentExpandedLines; |
277 | |
278 | // Maps from the first token of a top-level UnwrappedLine that contains |
279 | // a macro call to the replacement UnwrappedLines expanded from the macro |
280 | // call. |
281 | llvm::DenseMap<FormatToken *, SmallVector<UnwrappedLine, 8>> ExpandedLines; |
282 | |
283 | // Map from the macro identifier to a line containing the full unexpanded |
284 | // macro call. |
285 | llvm::DenseMap<FormatToken *, std::unique_ptr<UnwrappedLine>> Unexpanded; |
286 | |
287 | // For recursive macro expansions, trigger reconstruction only on the |
288 | // outermost expansion. |
289 | bool InExpansion = false; |
290 | |
291 | // Set while we reconstruct a macro call. |
292 | // For reconstruction, we feed the expanded lines into the reconstructor |
293 | // until it is finished. |
294 | std::optional<MacroCallReconstructor> Reconstruct; |
295 | |
296 | // Comments are sorted into unwrapped lines by whether they are in the same |
297 | // line as the previous token, or not. If not, they belong to the next token. |
298 | // Since the next token might already be in a new unwrapped line, we need to |
299 | // store the comments belonging to that token. |
300 | SmallVector<FormatToken *, 1> ; |
301 | |
302 | FormatToken *FormatTok = nullptr; |
303 | |
304 | // Has just finished parsing a preprocessor line. |
305 | bool AtEndOfPPLine; |
306 | |
307 | // The parsed lines. Only added to through \c CurrentLines. |
308 | SmallVector<UnwrappedLine, 8> Lines; |
309 | |
310 | // Preprocessor directives are parsed out-of-order from other unwrapped lines. |
311 | // Thus, we need to keep a list of preprocessor directives to be reported |
312 | // after an unwrapped line that has been started was finished. |
313 | SmallVector<UnwrappedLine, 4> PreprocessorDirectives; |
314 | |
315 | // New unwrapped lines are added via CurrentLines. |
316 | // Usually points to \c &Lines. While parsing a preprocessor directive when |
317 | // there is an unfinished previous unwrapped line, will point to |
318 | // \c &PreprocessorDirectives. |
319 | SmallVectorImpl<UnwrappedLine> *CurrentLines; |
320 | |
321 | // We store for each line whether it must be a declaration depending on |
322 | // whether we are in a compound statement or not. |
323 | llvm::BitVector DeclarationScopeStack; |
324 | |
325 | const FormatStyle &Style; |
326 | bool IsCpp; |
327 | LangOptions LangOpts; |
328 | const AdditionalKeywords &Keywords; |
329 | |
330 | llvm::Regex ; |
331 | |
332 | FormatTokenSource *Tokens; |
333 | UnwrappedLineConsumer &Callback; |
334 | |
335 | ArrayRef<FormatToken *> AllTokens; |
336 | |
337 | // Keeps a stack of the states of nested control statements (true if the |
338 | // statement contains more than some predefined number of nested statements). |
339 | SmallVector<bool, 8> NestedTooDeep; |
340 | |
341 | // Keeps a stack of the states of nested lambdas (true if the return type of |
342 | // the lambda is `decltype(auto)`). |
343 | SmallVector<bool, 4> NestedLambdas; |
344 | |
345 | // Whether the parser is parsing the body of a function whose return type is |
346 | // `decltype(auto)`. |
347 | bool IsDecltypeAutoFunction = false; |
348 | |
349 | // Represents preprocessor branch type, so we can find matching |
350 | // #if/#else/#endif directives. |
351 | enum PPBranchKind { |
352 | PP_Conditional, // Any #if, #ifdef, #ifndef, #elif, block outside #if 0 |
353 | PP_Unreachable // #if 0 or a conditional preprocessor block inside #if 0 |
354 | }; |
355 | |
356 | struct PPBranch { |
357 | PPBranch(PPBranchKind Kind, size_t Line) : Kind(Kind), Line(Line) {} |
358 | PPBranchKind Kind; |
359 | size_t Line; |
360 | }; |
361 | |
362 | // Keeps a stack of currently active preprocessor branching directives. |
363 | SmallVector<PPBranch, 16> PPStack; |
364 | |
365 | // The \c UnwrappedLineParser re-parses the code for each combination |
366 | // of preprocessor branches that can be taken. |
367 | // To that end, we take the same branch (#if, #else, or one of the #elif |
368 | // branches) for each nesting level of preprocessor branches. |
369 | // \c PPBranchLevel stores the current nesting level of preprocessor |
370 | // branches during one pass over the code. |
371 | int PPBranchLevel; |
372 | |
373 | // Contains the current branch (#if, #else or one of the #elif branches) |
374 | // for each nesting level. |
375 | SmallVector<int, 8> PPLevelBranchIndex; |
376 | |
377 | // Contains the maximum number of branches at each nesting level. |
378 | SmallVector<int, 8> PPLevelBranchCount; |
379 | |
380 | // Contains the number of branches per nesting level we are currently |
381 | // in while parsing a preprocessor branch sequence. |
382 | // This is used to update PPLevelBranchCount at the end of a branch |
383 | // sequence. |
384 | std::stack<int> PPChainBranchIndex; |
385 | |
386 | // Include guard search state. Used to fixup preprocessor indent levels |
387 | // so that include guards do not participate in indentation. |
388 | enum IncludeGuardState { |
389 | IG_Inited, // Search started, looking for #ifndef. |
390 | IG_IfNdefed, // #ifndef found, IncludeGuardToken points to condition. |
391 | IG_Defined, // Matching #define found, checking other requirements. |
392 | IG_Found, // All requirements met, need to fix indents. |
393 | IG_Rejected, // Search failed or never started. |
394 | }; |
395 | |
396 | // Current state of include guard search. |
397 | IncludeGuardState IncludeGuard; |
398 | |
399 | // Points to the #ifndef condition for a potential include guard. Null unless |
400 | // IncludeGuardState == IG_IfNdefed. |
401 | FormatToken *IncludeGuardToken; |
402 | |
403 | // Contains the first start column where the source begins. This is zero for |
404 | // normal source code and may be nonzero when formatting a code fragment that |
405 | // does not start at the beginning of the file. |
406 | unsigned FirstStartColumn; |
407 | |
408 | MacroExpander Macros; |
409 | |
410 | friend class ScopedLineState; |
411 | friend class CompoundStatementIndenter; |
412 | }; |
413 | |
414 | struct UnwrappedLineNode { |
415 | UnwrappedLineNode() : Tok(nullptr) {} |
416 | UnwrappedLineNode(FormatToken *Tok, |
417 | llvm::ArrayRef<UnwrappedLine> Children = {}) |
418 | : Tok(Tok), Children(Children) {} |
419 | |
420 | FormatToken *Tok; |
421 | SmallVector<UnwrappedLine, 0> Children; |
422 | }; |
423 | |
424 | std::ostream &operator<<(std::ostream &Stream, const UnwrappedLine &Line); |
425 | |
426 | } // end namespace format |
427 | } // end namespace clang |
428 | |
429 | #endif |
430 | |