1//===--- Format.cpp - Format C++ code -------------------------------------===//
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 implements functions declared in Format.h. This will be
11/// split into separate files as we go.
12///
13//===----------------------------------------------------------------------===//
14
15#include "clang/Format/Format.h"
16#include "AffectedRangeManager.h"
17#include "BreakableToken.h"
18#include "ContinuationIndenter.h"
19#include "FormatInternal.h"
20#include "FormatTokenLexer.h"
21#include "NamespaceEndCommentsFixer.h"
22#include "SortJavaScriptImports.h"
23#include "TokenAnalyzer.h"
24#include "TokenAnnotator.h"
25#include "UnwrappedLineFormatter.h"
26#include "UnwrappedLineParser.h"
27#include "UsingDeclarationsSorter.h"
28#include "WhitespaceManager.h"
29#include "clang/Basic/Diagnostic.h"
30#include "clang/Basic/DiagnosticOptions.h"
31#include "clang/Basic/SourceManager.h"
32#include "clang/Lex/Lexer.h"
33#include "clang/Tooling/Inclusions/HeaderIncludes.h"
34#include "llvm/ADT/STLExtras.h"
35#include "llvm/ADT/StringRef.h"
36#include "llvm/Support/Allocator.h"
37#include "llvm/Support/Debug.h"
38#include "llvm/Support/Path.h"
39#include "llvm/Support/Regex.h"
40#include "llvm/Support/VirtualFileSystem.h"
41#include "llvm/Support/YAMLTraits.h"
42#include <algorithm>
43#include <memory>
44#include <mutex>
45#include <string>
46#include <unordered_map>
47
48#define DEBUG_TYPE "format-formatter"
49
50using clang::format::FormatStyle;
51
52LLVM_YAML_IS_SEQUENCE_VECTOR(clang::format::FormatStyle::RawStringFormat)
53
54namespace llvm {
55namespace yaml {
56template <> struct ScalarEnumerationTraits<FormatStyle::LanguageKind> {
57  static void enumeration(IO &IO, FormatStyle::LanguageKind &Value) {
58    IO.enumCase(Value, "Cpp", FormatStyle::LK_Cpp);
59    IO.enumCase(Value, "Java", FormatStyle::LK_Java);
60    IO.enumCase(Value, "JavaScript", FormatStyle::LK_JavaScript);
61    IO.enumCase(Value, "ObjC", FormatStyle::LK_ObjC);
62    IO.enumCase(Value, "Proto", FormatStyle::LK_Proto);
63    IO.enumCase(Value, "TableGen", FormatStyle::LK_TableGen);
64    IO.enumCase(Value, "TextProto", FormatStyle::LK_TextProto);
65    IO.enumCase(Value, "CSharp", FormatStyle::LK_CSharp);
66  }
67};
68
69template <> struct ScalarEnumerationTraits<FormatStyle::LanguageStandard> {
70  static void enumeration(IO &IO, FormatStyle::LanguageStandard &Value) {
71    IO.enumCase(Value, "c++03", FormatStyle::LS_Cpp03);
72    IO.enumCase(Value, "C++03", FormatStyle::LS_Cpp03); // Legacy alias
73    IO.enumCase(Value, "Cpp03", FormatStyle::LS_Cpp03); // Legacy alias
74
75    IO.enumCase(Value, "c++11", FormatStyle::LS_Cpp11);
76    IO.enumCase(Value, "C++11", FormatStyle::LS_Cpp11); // Legacy alias
77
78    IO.enumCase(Value, "c++14", FormatStyle::LS_Cpp14);
79    IO.enumCase(Value, "c++17", FormatStyle::LS_Cpp17);
80    IO.enumCase(Value, "c++20", FormatStyle::LS_Cpp20);
81
82    IO.enumCase(Value, "Latest", FormatStyle::LS_Latest);
83    IO.enumCase(Value, "Cpp11", FormatStyle::LS_Latest); // Legacy alias
84    IO.enumCase(Value, "Auto", FormatStyle::LS_Auto);
85  }
86};
87
88template <> struct ScalarEnumerationTraits<FormatStyle::UseTabStyle> {
89  static void enumeration(IO &IO, FormatStyle::UseTabStyle &Value) {
90    IO.enumCase(Value, "Never", FormatStyle::UT_Never);
91    IO.enumCase(Value, "false", FormatStyle::UT_Never);
92    IO.enumCase(Value, "Always", FormatStyle::UT_Always);
93    IO.enumCase(Value, "true", FormatStyle::UT_Always);
94    IO.enumCase(Value, "ForIndentation", FormatStyle::UT_ForIndentation);
95    IO.enumCase(Value, "ForContinuationAndIndentation",
96                FormatStyle::UT_ForContinuationAndIndentation);
97    IO.enumCase(Value, "AlignWithSpaces", FormatStyle::UT_AlignWithSpaces);
98  }
99};
100
101template <> struct ScalarEnumerationTraits<FormatStyle::JavaScriptQuoteStyle> {
102  static void enumeration(IO &IO, FormatStyle::JavaScriptQuoteStyle &Value) {
103    IO.enumCase(Value, "Leave", FormatStyle::JSQS_Leave);
104    IO.enumCase(Value, "Single", FormatStyle::JSQS_Single);
105    IO.enumCase(Value, "Double", FormatStyle::JSQS_Double);
106  }
107};
108
109template <> struct ScalarEnumerationTraits<FormatStyle::ShortBlockStyle> {
110  static void enumeration(IO &IO, FormatStyle::ShortBlockStyle &Value) {
111    IO.enumCase(Value, "Never", FormatStyle::SBS_Never);
112    IO.enumCase(Value, "false", FormatStyle::SBS_Never);
113    IO.enumCase(Value, "Always", FormatStyle::SBS_Always);
114    IO.enumCase(Value, "true", FormatStyle::SBS_Always);
115    IO.enumCase(Value, "Empty", FormatStyle::SBS_Empty);
116  }
117};
118
119template <> struct ScalarEnumerationTraits<FormatStyle::ShortFunctionStyle> {
120  static void enumeration(IO &IO, FormatStyle::ShortFunctionStyle &Value) {
121    IO.enumCase(Value, "None", FormatStyle::SFS_None);
122    IO.enumCase(Value, "false", FormatStyle::SFS_None);
123    IO.enumCase(Value, "All", FormatStyle::SFS_All);
124    IO.enumCase(Value, "true", FormatStyle::SFS_All);
125    IO.enumCase(Value, "Inline", FormatStyle::SFS_Inline);
126    IO.enumCase(Value, "InlineOnly", FormatStyle::SFS_InlineOnly);
127    IO.enumCase(Value, "Empty", FormatStyle::SFS_Empty);
128  }
129};
130
131template <> struct ScalarEnumerationTraits<FormatStyle::ShortIfStyle> {
132  static void enumeration(IO &IO, FormatStyle::ShortIfStyle &Value) {
133    IO.enumCase(Value, "Never", FormatStyle::SIS_Never);
134    IO.enumCase(Value, "Always", FormatStyle::SIS_Always);
135    IO.enumCase(Value, "WithoutElse", FormatStyle::SIS_WithoutElse);
136
137    // For backward compatibility.
138    IO.enumCase(Value, "false", FormatStyle::SIS_Never);
139    IO.enumCase(Value, "true", FormatStyle::SIS_WithoutElse);
140  }
141};
142
143template <> struct ScalarEnumerationTraits<FormatStyle::ShortLambdaStyle> {
144  static void enumeration(IO &IO, FormatStyle::ShortLambdaStyle &Value) {
145    IO.enumCase(Value, "None", FormatStyle::SLS_None);
146    IO.enumCase(Value, "false", FormatStyle::SLS_None);
147    IO.enumCase(Value, "Empty", FormatStyle::SLS_Empty);
148    IO.enumCase(Value, "Inline", FormatStyle::SLS_Inline);
149    IO.enumCase(Value, "All", FormatStyle::SLS_All);
150    IO.enumCase(Value, "true", FormatStyle::SLS_All);
151  }
152};
153
154template <> struct ScalarEnumerationTraits<FormatStyle::BinPackStyle> {
155  static void enumeration(IO &IO, FormatStyle::BinPackStyle &Value) {
156    IO.enumCase(Value, "Auto", FormatStyle::BPS_Auto);
157    IO.enumCase(Value, "Always", FormatStyle::BPS_Always);
158    IO.enumCase(Value, "Never", FormatStyle::BPS_Never);
159  }
160};
161
162template <> struct ScalarEnumerationTraits<FormatStyle::TrailingCommaStyle> {
163  static void enumeration(IO &IO, FormatStyle::TrailingCommaStyle &Value) {
164    IO.enumCase(Value, "None", FormatStyle::TCS_None);
165    IO.enumCase(Value, "Wrapped", FormatStyle::TCS_Wrapped);
166  }
167};
168
169template <> struct ScalarEnumerationTraits<FormatStyle::BinaryOperatorStyle> {
170  static void enumeration(IO &IO, FormatStyle::BinaryOperatorStyle &Value) {
171    IO.enumCase(Value, "All", FormatStyle::BOS_All);
172    IO.enumCase(Value, "true", FormatStyle::BOS_All);
173    IO.enumCase(Value, "None", FormatStyle::BOS_None);
174    IO.enumCase(Value, "false", FormatStyle::BOS_None);
175    IO.enumCase(Value, "NonAssignment", FormatStyle::BOS_NonAssignment);
176  }
177};
178
179template <> struct ScalarEnumerationTraits<FormatStyle::BraceBreakingStyle> {
180  static void enumeration(IO &IO, FormatStyle::BraceBreakingStyle &Value) {
181    IO.enumCase(Value, "Attach", FormatStyle::BS_Attach);
182    IO.enumCase(Value, "Linux", FormatStyle::BS_Linux);
183    IO.enumCase(Value, "Mozilla", FormatStyle::BS_Mozilla);
184    IO.enumCase(Value, "Stroustrup", FormatStyle::BS_Stroustrup);
185    IO.enumCase(Value, "Allman", FormatStyle::BS_Allman);
186    IO.enumCase(Value, "Whitesmiths", FormatStyle::BS_Whitesmiths);
187    IO.enumCase(Value, "GNU", FormatStyle::BS_GNU);
188    IO.enumCase(Value, "WebKit", FormatStyle::BS_WebKit);
189    IO.enumCase(Value, "Custom", FormatStyle::BS_Custom);
190  }
191};
192
193template <>
194struct ScalarEnumerationTraits<
195    FormatStyle::BraceWrappingAfterControlStatementStyle> {
196  static void
197  enumeration(IO &IO,
198              FormatStyle::BraceWrappingAfterControlStatementStyle &Value) {
199    IO.enumCase(Value, "Never", FormatStyle::BWACS_Never);
200    IO.enumCase(Value, "MultiLine", FormatStyle::BWACS_MultiLine);
201    IO.enumCase(Value, "Always", FormatStyle::BWACS_Always);
202
203    // For backward compatibility.
204    IO.enumCase(Value, "false", FormatStyle::BWACS_Never);
205    IO.enumCase(Value, "true", FormatStyle::BWACS_Always);
206  }
207};
208
209template <>
210struct ScalarEnumerationTraits<FormatStyle::BreakConstructorInitializersStyle> {
211  static void
212  enumeration(IO &IO, FormatStyle::BreakConstructorInitializersStyle &Value) {
213    IO.enumCase(Value, "BeforeColon", FormatStyle::BCIS_BeforeColon);
214    IO.enumCase(Value, "BeforeComma", FormatStyle::BCIS_BeforeComma);
215    IO.enumCase(Value, "AfterColon", FormatStyle::BCIS_AfterColon);
216  }
217};
218
219template <>
220struct ScalarEnumerationTraits<FormatStyle::BreakInheritanceListStyle> {
221  static void enumeration(IO &IO,
222                          FormatStyle::BreakInheritanceListStyle &Value) {
223    IO.enumCase(Value, "BeforeColon", FormatStyle::BILS_BeforeColon);
224    IO.enumCase(Value, "BeforeComma", FormatStyle::BILS_BeforeComma);
225    IO.enumCase(Value, "AfterColon", FormatStyle::BILS_AfterColon);
226  }
227};
228
229template <>
230struct ScalarEnumerationTraits<FormatStyle::PPDirectiveIndentStyle> {
231  static void enumeration(IO &IO, FormatStyle::PPDirectiveIndentStyle &Value) {
232    IO.enumCase(Value, "None", FormatStyle::PPDIS_None);
233    IO.enumCase(Value, "AfterHash", FormatStyle::PPDIS_AfterHash);
234    IO.enumCase(Value, "BeforeHash", FormatStyle::PPDIS_BeforeHash);
235  }
236};
237
238template <>
239struct ScalarEnumerationTraits<FormatStyle::IndentExternBlockStyle> {
240  static void enumeration(IO &IO, FormatStyle::IndentExternBlockStyle &Value) {
241    IO.enumCase(Value, "AfterExternBlock", FormatStyle::IEBS_AfterExternBlock);
242    IO.enumCase(Value, "Indent", FormatStyle::IEBS_Indent);
243    IO.enumCase(Value, "NoIndent", FormatStyle::IEBS_NoIndent);
244    IO.enumCase(Value, "true", FormatStyle::IEBS_Indent);
245    IO.enumCase(Value, "false", FormatStyle::IEBS_NoIndent);
246  }
247};
248
249template <>
250struct ScalarEnumerationTraits<FormatStyle::ReturnTypeBreakingStyle> {
251  static void enumeration(IO &IO, FormatStyle::ReturnTypeBreakingStyle &Value) {
252    IO.enumCase(Value, "None", FormatStyle::RTBS_None);
253    IO.enumCase(Value, "All", FormatStyle::RTBS_All);
254    IO.enumCase(Value, "TopLevel", FormatStyle::RTBS_TopLevel);
255    IO.enumCase(Value, "TopLevelDefinitions",
256                FormatStyle::RTBS_TopLevelDefinitions);
257    IO.enumCase(Value, "AllDefinitions", FormatStyle::RTBS_AllDefinitions);
258  }
259};
260
261template <>
262struct ScalarEnumerationTraits<FormatStyle::BreakTemplateDeclarationsStyle> {
263  static void enumeration(IO &IO,
264                          FormatStyle::BreakTemplateDeclarationsStyle &Value) {
265    IO.enumCase(Value, "No", FormatStyle::BTDS_No);
266    IO.enumCase(Value, "MultiLine", FormatStyle::BTDS_MultiLine);
267    IO.enumCase(Value, "Yes", FormatStyle::BTDS_Yes);
268
269    // For backward compatibility.
270    IO.enumCase(Value, "false", FormatStyle::BTDS_MultiLine);
271    IO.enumCase(Value, "true", FormatStyle::BTDS_Yes);
272  }
273};
274
275template <>
276struct ScalarEnumerationTraits<FormatStyle::DefinitionReturnTypeBreakingStyle> {
277  static void
278  enumeration(IO &IO, FormatStyle::DefinitionReturnTypeBreakingStyle &Value) {
279    IO.enumCase(Value, "None", FormatStyle::DRTBS_None);
280    IO.enumCase(Value, "All", FormatStyle::DRTBS_All);
281    IO.enumCase(Value, "TopLevel", FormatStyle::DRTBS_TopLevel);
282
283    // For backward compatibility.
284    IO.enumCase(Value, "false", FormatStyle::DRTBS_None);
285    IO.enumCase(Value, "true", FormatStyle::DRTBS_All);
286  }
287};
288
289template <>
290struct ScalarEnumerationTraits<FormatStyle::NamespaceIndentationKind> {
291  static void enumeration(IO &IO,
292                          FormatStyle::NamespaceIndentationKind &Value) {
293    IO.enumCase(Value, "None", FormatStyle::NI_None);
294    IO.enumCase(Value, "Inner", FormatStyle::NI_Inner);
295    IO.enumCase(Value, "All", FormatStyle::NI_All);
296  }
297};
298
299template <> struct ScalarEnumerationTraits<FormatStyle::BracketAlignmentStyle> {
300  static void enumeration(IO &IO, FormatStyle::BracketAlignmentStyle &Value) {
301    IO.enumCase(Value, "Align", FormatStyle::BAS_Align);
302    IO.enumCase(Value, "DontAlign", FormatStyle::BAS_DontAlign);
303    IO.enumCase(Value, "AlwaysBreak", FormatStyle::BAS_AlwaysBreak);
304
305    // For backward compatibility.
306    IO.enumCase(Value, "true", FormatStyle::BAS_Align);
307    IO.enumCase(Value, "false", FormatStyle::BAS_DontAlign);
308  }
309};
310
311template <>
312struct ScalarEnumerationTraits<FormatStyle::EscapedNewlineAlignmentStyle> {
313  static void enumeration(IO &IO,
314                          FormatStyle::EscapedNewlineAlignmentStyle &Value) {
315    IO.enumCase(Value, "DontAlign", FormatStyle::ENAS_DontAlign);
316    IO.enumCase(Value, "Left", FormatStyle::ENAS_Left);
317    IO.enumCase(Value, "Right", FormatStyle::ENAS_Right);
318
319    // For backward compatibility.
320    IO.enumCase(Value, "true", FormatStyle::ENAS_Left);
321    IO.enumCase(Value, "false", FormatStyle::ENAS_Right);
322  }
323};
324
325template <> struct ScalarEnumerationTraits<FormatStyle::OperandAlignmentStyle> {
326  static void enumeration(IO &IO, FormatStyle::OperandAlignmentStyle &Value) {
327    IO.enumCase(Value, "DontAlign", FormatStyle::OAS_DontAlign);
328    IO.enumCase(Value, "Align", FormatStyle::OAS_Align);
329    IO.enumCase(Value, "AlignAfterOperator",
330                FormatStyle::OAS_AlignAfterOperator);
331
332    // For backward compatibility.
333    IO.enumCase(Value, "true", FormatStyle::OAS_Align);
334    IO.enumCase(Value, "false", FormatStyle::OAS_DontAlign);
335  }
336};
337
338template <> struct ScalarEnumerationTraits<FormatStyle::PointerAlignmentStyle> {
339  static void enumeration(IO &IO, FormatStyle::PointerAlignmentStyle &Value) {
340    IO.enumCase(Value, "Middle", FormatStyle::PAS_Middle);
341    IO.enumCase(Value, "Left", FormatStyle::PAS_Left);
342    IO.enumCase(Value, "Right", FormatStyle::PAS_Right);
343
344    // For backward compatibility.
345    IO.enumCase(Value, "true", FormatStyle::PAS_Left);
346    IO.enumCase(Value, "false", FormatStyle::PAS_Right);
347  }
348};
349
350template <>
351struct ScalarEnumerationTraits<FormatStyle::SpaceBeforeParensOptions> {
352  static void enumeration(IO &IO,
353                          FormatStyle::SpaceBeforeParensOptions &Value) {
354    IO.enumCase(Value, "Never", FormatStyle::SBPO_Never);
355    IO.enumCase(Value, "ControlStatements",
356                FormatStyle::SBPO_ControlStatements);
357    IO.enumCase(Value, "ControlStatementsExceptForEachMacros",
358                FormatStyle::SBPO_ControlStatementsExceptForEachMacros);
359    IO.enumCase(Value, "NonEmptyParentheses",
360                FormatStyle::SBPO_NonEmptyParentheses);
361    IO.enumCase(Value, "Always", FormatStyle::SBPO_Always);
362
363    // For backward compatibility.
364    IO.enumCase(Value, "false", FormatStyle::SBPO_Never);
365    IO.enumCase(Value, "true", FormatStyle::SBPO_ControlStatements);
366  }
367};
368
369template <> struct MappingTraits<FormatStyle> {
370  static void mapping(IO &IO, FormatStyle &Style) {
371    // When reading, read the language first, we need it for getPredefinedStyle.
372    IO.mapOptional("Language", Style.Language);
373
374    if (IO.outputting()) {
375      StringRef StylesArray[] = {"LLVM",   "Google", "Chromium", "Mozilla",
376                                 "WebKit", "GNU",    "Microsoft"};
377      ArrayRef<StringRef> Styles(StylesArray);
378      for (size_t i = 0, e = Styles.size(); i < e; ++i) {
379        StringRef StyleName(Styles[i]);
380        FormatStyle PredefinedStyle;
381        if (getPredefinedStyle(StyleName, Style.Language, &PredefinedStyle) &&
382            Style == PredefinedStyle) {
383          IO.mapOptional("# BasedOnStyle", StyleName);
384          break;
385        }
386      }
387    } else {
388      StringRef BasedOnStyle;
389      IO.mapOptional("BasedOnStyle", BasedOnStyle);
390      if (!BasedOnStyle.empty()) {
391        FormatStyle::LanguageKind OldLanguage = Style.Language;
392        FormatStyle::LanguageKind Language =
393            ((FormatStyle *)IO.getContext())->Language;
394        if (!getPredefinedStyle(BasedOnStyle, Language, &Style)) {
395          IO.setError(Twine("Unknown value for BasedOnStyle: ", BasedOnStyle));
396          return;
397        }
398        Style.Language = OldLanguage;
399      }
400    }
401
402    // For backward compatibility.
403    if (!IO.outputting()) {
404      IO.mapOptional("AlignEscapedNewlinesLeft", Style.AlignEscapedNewlines);
405      IO.mapOptional("DerivePointerBinding", Style.DerivePointerAlignment);
406      IO.mapOptional("IndentFunctionDeclarationAfterType",
407                     Style.IndentWrappedFunctionNames);
408      IO.mapOptional("PointerBindsToType", Style.PointerAlignment);
409      IO.mapOptional("SpaceAfterControlStatementKeyword",
410                     Style.SpaceBeforeParens);
411    }
412
413    IO.mapOptional("AccessModifierOffset", Style.AccessModifierOffset);
414    IO.mapOptional("AlignAfterOpenBracket", Style.AlignAfterOpenBracket);
415    IO.mapOptional("AlignConsecutiveMacros", Style.AlignConsecutiveMacros);
416    IO.mapOptional("AlignConsecutiveAssignments",
417                   Style.AlignConsecutiveAssignments);
418    IO.mapOptional("AlignConsecutiveBitFields",
419                   Style.AlignConsecutiveBitFields);
420    IO.mapOptional("AlignConsecutiveDeclarations",
421                   Style.AlignConsecutiveDeclarations);
422    IO.mapOptional("AlignEscapedNewlines", Style.AlignEscapedNewlines);
423    IO.mapOptional("AlignOperands", Style.AlignOperands);
424    IO.mapOptional("AlignTrailingComments", Style.AlignTrailingComments);
425    IO.mapOptional("AllowAllArgumentsOnNextLine",
426                   Style.AllowAllArgumentsOnNextLine);
427    IO.mapOptional("AllowAllConstructorInitializersOnNextLine",
428                   Style.AllowAllConstructorInitializersOnNextLine);
429    IO.mapOptional("AllowAllParametersOfDeclarationOnNextLine",
430                   Style.AllowAllParametersOfDeclarationOnNextLine);
431    IO.mapOptional("AllowShortEnumsOnASingleLine",
432                   Style.AllowShortEnumsOnASingleLine);
433    IO.mapOptional("AllowShortBlocksOnASingleLine",
434                   Style.AllowShortBlocksOnASingleLine);
435    IO.mapOptional("AllowShortCaseLabelsOnASingleLine",
436                   Style.AllowShortCaseLabelsOnASingleLine);
437    IO.mapOptional("AllowShortFunctionsOnASingleLine",
438                   Style.AllowShortFunctionsOnASingleLine);
439    IO.mapOptional("AllowShortLambdasOnASingleLine",
440                   Style.AllowShortLambdasOnASingleLine);
441    IO.mapOptional("AllowShortIfStatementsOnASingleLine",
442                   Style.AllowShortIfStatementsOnASingleLine);
443    IO.mapOptional("AllowShortLoopsOnASingleLine",
444                   Style.AllowShortLoopsOnASingleLine);
445    IO.mapOptional("AlwaysBreakAfterDefinitionReturnType",
446                   Style.AlwaysBreakAfterDefinitionReturnType);
447    IO.mapOptional("AlwaysBreakAfterReturnType",
448                   Style.AlwaysBreakAfterReturnType);
449
450    // If AlwaysBreakAfterDefinitionReturnType was specified but
451    // AlwaysBreakAfterReturnType was not, initialize the latter from the
452    // former for backwards compatibility.
453    if (Style.AlwaysBreakAfterDefinitionReturnType != FormatStyle::DRTBS_None &&
454        Style.AlwaysBreakAfterReturnType == FormatStyle::RTBS_None) {
455      if (Style.AlwaysBreakAfterDefinitionReturnType == FormatStyle::DRTBS_All)
456        Style.AlwaysBreakAfterReturnType = FormatStyle::RTBS_AllDefinitions;
457      else if (Style.AlwaysBreakAfterDefinitionReturnType ==
458               FormatStyle::DRTBS_TopLevel)
459        Style.AlwaysBreakAfterReturnType =
460            FormatStyle::RTBS_TopLevelDefinitions;
461    }
462
463    IO.mapOptional("AlwaysBreakBeforeMultilineStrings",
464                   Style.AlwaysBreakBeforeMultilineStrings);
465    IO.mapOptional("AlwaysBreakTemplateDeclarations",
466                   Style.AlwaysBreakTemplateDeclarations);
467    IO.mapOptional("BinPackArguments", Style.BinPackArguments);
468    IO.mapOptional("BinPackParameters", Style.BinPackParameters);
469    IO.mapOptional("BraceWrapping", Style.BraceWrapping);
470    IO.mapOptional("BreakBeforeBinaryOperators",
471                   Style.BreakBeforeBinaryOperators);
472    IO.mapOptional("BreakBeforeBraces", Style.BreakBeforeBraces);
473
474    bool BreakBeforeInheritanceComma = false;
475    IO.mapOptional("BreakBeforeInheritanceComma", BreakBeforeInheritanceComma);
476    IO.mapOptional("BreakInheritanceList", Style.BreakInheritanceList);
477    // If BreakBeforeInheritanceComma was specified but
478    // BreakInheritance was not, initialize the latter from the
479    // former for backwards compatibility.
480    if (BreakBeforeInheritanceComma &&
481        Style.BreakInheritanceList == FormatStyle::BILS_BeforeColon)
482      Style.BreakInheritanceList = FormatStyle::BILS_BeforeComma;
483
484    IO.mapOptional("BreakBeforeTernaryOperators",
485                   Style.BreakBeforeTernaryOperators);
486
487    bool BreakConstructorInitializersBeforeComma = false;
488    IO.mapOptional("BreakConstructorInitializersBeforeComma",
489                   BreakConstructorInitializersBeforeComma);
490    IO.mapOptional("BreakConstructorInitializers",
491                   Style.BreakConstructorInitializers);
492    // If BreakConstructorInitializersBeforeComma was specified but
493    // BreakConstructorInitializers was not, initialize the latter from the
494    // former for backwards compatibility.
495    if (BreakConstructorInitializersBeforeComma &&
496        Style.BreakConstructorInitializers == FormatStyle::BCIS_BeforeColon)
497      Style.BreakConstructorInitializers = FormatStyle::BCIS_BeforeComma;
498
499    IO.mapOptional("BreakAfterJavaFieldAnnotations",
500                   Style.BreakAfterJavaFieldAnnotations);
501    IO.mapOptional("BreakStringLiterals", Style.BreakStringLiterals);
502    IO.mapOptional("ColumnLimit", Style.ColumnLimit);
503    IO.mapOptional("CommentPragmas", Style.CommentPragmas);
504    IO.mapOptional("CompactNamespaces", Style.CompactNamespaces);
505    IO.mapOptional("ConstructorInitializerAllOnOneLineOrOnePerLine",
506                   Style.ConstructorInitializerAllOnOneLineOrOnePerLine);
507    IO.mapOptional("ConstructorInitializerIndentWidth",
508                   Style.ConstructorInitializerIndentWidth);
509    IO.mapOptional("ContinuationIndentWidth", Style.ContinuationIndentWidth);
510    IO.mapOptional("Cpp11BracedListStyle", Style.Cpp11BracedListStyle);
511    IO.mapOptional("DeriveLineEnding", Style.DeriveLineEnding);
512    IO.mapOptional("DerivePointerAlignment", Style.DerivePointerAlignment);
513    IO.mapOptional("DisableFormat", Style.DisableFormat);
514    IO.mapOptional("ExperimentalAutoDetectBinPacking",
515                   Style.ExperimentalAutoDetectBinPacking);
516    IO.mapOptional("FixNamespaceComments", Style.FixNamespaceComments);
517    IO.mapOptional("ForEachMacros", Style.ForEachMacros);
518    IO.mapOptional("IncludeBlocks", Style.IncludeStyle.IncludeBlocks);
519    IO.mapOptional("IncludeCategories", Style.IncludeStyle.IncludeCategories);
520    IO.mapOptional("IncludeIsMainRegex", Style.IncludeStyle.IncludeIsMainRegex);
521    IO.mapOptional("IncludeIsMainSourceRegex",
522                   Style.IncludeStyle.IncludeIsMainSourceRegex);
523    IO.mapOptional("IndentCaseLabels", Style.IndentCaseLabels);
524    IO.mapOptional("IndentCaseBlocks", Style.IndentCaseBlocks);
525    IO.mapOptional("IndentGotoLabels", Style.IndentGotoLabels);
526    IO.mapOptional("IndentPPDirectives", Style.IndentPPDirectives);
527    IO.mapOptional("IndentExternBlock", Style.IndentExternBlock);
528    IO.mapOptional("IndentWidth", Style.IndentWidth);
529    IO.mapOptional("IndentWrappedFunctionNames",
530                   Style.IndentWrappedFunctionNames);
531    IO.mapOptional("InsertTrailingCommas", Style.InsertTrailingCommas);
532    IO.mapOptional("JavaImportGroups", Style.JavaImportGroups);
533    IO.mapOptional("JavaScriptQuotes", Style.JavaScriptQuotes);
534    IO.mapOptional("JavaScriptWrapImports", Style.JavaScriptWrapImports);
535    IO.mapOptional("KeepEmptyLinesAtTheStartOfBlocks",
536                   Style.KeepEmptyLinesAtTheStartOfBlocks);
537    IO.mapOptional("MacroBlockBegin", Style.MacroBlockBegin);
538    IO.mapOptional("MacroBlockEnd", Style.MacroBlockEnd);
539    IO.mapOptional("MaxEmptyLinesToKeep", Style.MaxEmptyLinesToKeep);
540    IO.mapOptional("NamespaceIndentation", Style.NamespaceIndentation);
541    IO.mapOptional("NamespaceMacros", Style.NamespaceMacros);
542    IO.mapOptional("ObjCBinPackProtocolList", Style.ObjCBinPackProtocolList);
543    IO.mapOptional("ObjCBlockIndentWidth", Style.ObjCBlockIndentWidth);
544    IO.mapOptional("ObjCBreakBeforeNestedBlockParam",
545                   Style.ObjCBreakBeforeNestedBlockParam);
546    IO.mapOptional("ObjCSpaceAfterProperty", Style.ObjCSpaceAfterProperty);
547    IO.mapOptional("ObjCSpaceBeforeProtocolList",
548                   Style.ObjCSpaceBeforeProtocolList);
549    IO.mapOptional("PenaltyBreakAssignment", Style.PenaltyBreakAssignment);
550    IO.mapOptional("PenaltyBreakBeforeFirstCallParameter",
551                   Style.PenaltyBreakBeforeFirstCallParameter);
552    IO.mapOptional("PenaltyBreakComment", Style.PenaltyBreakComment);
553    IO.mapOptional("PenaltyBreakFirstLessLess",
554                   Style.PenaltyBreakFirstLessLess);
555    IO.mapOptional("PenaltyBreakString", Style.PenaltyBreakString);
556    IO.mapOptional("PenaltyBreakTemplateDeclaration",
557                   Style.PenaltyBreakTemplateDeclaration);
558    IO.mapOptional("PenaltyExcessCharacter", Style.PenaltyExcessCharacter);
559    IO.mapOptional("PenaltyReturnTypeOnItsOwnLine",
560                   Style.PenaltyReturnTypeOnItsOwnLine);
561    IO.mapOptional("PointerAlignment", Style.PointerAlignment);
562    IO.mapOptional("RawStringFormats", Style.RawStringFormats);
563    IO.mapOptional("ReflowComments", Style.ReflowComments);
564    IO.mapOptional("SortIncludes", Style.SortIncludes);
565    IO.mapOptional("SortUsingDeclarations", Style.SortUsingDeclarations);
566    IO.mapOptional("SpaceAfterCStyleCast", Style.SpaceAfterCStyleCast);
567    IO.mapOptional("SpaceAfterLogicalNot", Style.SpaceAfterLogicalNot);
568    IO.mapOptional("SpaceAfterTemplateKeyword",
569                   Style.SpaceAfterTemplateKeyword);
570    IO.mapOptional("SpaceBeforeAssignmentOperators",
571                   Style.SpaceBeforeAssignmentOperators);
572    IO.mapOptional("SpaceBeforeCpp11BracedList",
573                   Style.SpaceBeforeCpp11BracedList);
574    IO.mapOptional("SpaceBeforeCtorInitializerColon",
575                   Style.SpaceBeforeCtorInitializerColon);
576    IO.mapOptional("SpaceBeforeInheritanceColon",
577                   Style.SpaceBeforeInheritanceColon);
578    IO.mapOptional("SpaceBeforeParens", Style.SpaceBeforeParens);
579    IO.mapOptional("SpaceBeforeRangeBasedForLoopColon",
580                   Style.SpaceBeforeRangeBasedForLoopColon);
581    IO.mapOptional("SpaceInEmptyBlock", Style.SpaceInEmptyBlock);
582    IO.mapOptional("SpaceInEmptyParentheses", Style.SpaceInEmptyParentheses);
583    IO.mapOptional("SpacesBeforeTrailingComments",
584                   Style.SpacesBeforeTrailingComments);
585    IO.mapOptional("SpacesInAngles", Style.SpacesInAngles);
586    IO.mapOptional("SpacesInConditionalStatement",
587                   Style.SpacesInConditionalStatement);
588    IO.mapOptional("SpacesInContainerLiterals",
589                   Style.SpacesInContainerLiterals);
590    IO.mapOptional("SpacesInCStyleCastParentheses",
591                   Style.SpacesInCStyleCastParentheses);
592    IO.mapOptional("SpacesInParentheses", Style.SpacesInParentheses);
593    IO.mapOptional("SpacesInSquareBrackets", Style.SpacesInSquareBrackets);
594    IO.mapOptional("SpaceBeforeSquareBrackets",
595                   Style.SpaceBeforeSquareBrackets);
596    IO.mapOptional("Standard", Style.Standard);
597    IO.mapOptional("StatementMacros", Style.StatementMacros);
598    IO.mapOptional("TabWidth", Style.TabWidth);
599    IO.mapOptional("TypenameMacros", Style.TypenameMacros);
600    IO.mapOptional("UseCRLF", Style.UseCRLF);
601    IO.mapOptional("UseTab", Style.UseTab);
602    IO.mapOptional("WhitespaceSensitiveMacros",
603                   Style.WhitespaceSensitiveMacros);
604  }
605};
606
607template <> struct MappingTraits<FormatStyle::BraceWrappingFlags> {
608  static void mapping(IO &IO, FormatStyle::BraceWrappingFlags &Wrapping) {
609    IO.mapOptional("AfterCaseLabel", Wrapping.AfterCaseLabel);
610    IO.mapOptional("AfterClass", Wrapping.AfterClass);
611    IO.mapOptional("AfterControlStatement", Wrapping.AfterControlStatement);
612    IO.mapOptional("AfterEnum", Wrapping.AfterEnum);
613    IO.mapOptional("AfterFunction", Wrapping.AfterFunction);
614    IO.mapOptional("AfterNamespace", Wrapping.AfterNamespace);
615    IO.mapOptional("AfterObjCDeclaration", Wrapping.AfterObjCDeclaration);
616    IO.mapOptional("AfterStruct", Wrapping.AfterStruct);
617    IO.mapOptional("AfterUnion", Wrapping.AfterUnion);
618    IO.mapOptional("AfterExternBlock", Wrapping.AfterExternBlock);
619    IO.mapOptional("BeforeCatch", Wrapping.BeforeCatch);
620    IO.mapOptional("BeforeElse", Wrapping.BeforeElse);
621    IO.mapOptional("BeforeLambdaBody", Wrapping.BeforeLambdaBody);
622    IO.mapOptional("BeforeWhile", Wrapping.BeforeWhile);
623    IO.mapOptional("IndentBraces", Wrapping.IndentBraces);
624    IO.mapOptional("SplitEmptyFunction", Wrapping.SplitEmptyFunction);
625    IO.mapOptional("SplitEmptyRecord", Wrapping.SplitEmptyRecord);
626    IO.mapOptional("SplitEmptyNamespace", Wrapping.SplitEmptyNamespace);
627  }
628};
629
630template <> struct MappingTraits<FormatStyle::RawStringFormat> {
631  static void mapping(IO &IO, FormatStyle::RawStringFormat &Format) {
632    IO.mapOptional("Language", Format.Language);
633    IO.mapOptional("Delimiters", Format.Delimiters);
634    IO.mapOptional("EnclosingFunctions", Format.EnclosingFunctions);
635    IO.mapOptional("CanonicalDelimiter", Format.CanonicalDelimiter);
636    IO.mapOptional("BasedOnStyle", Format.BasedOnStyle);
637  }
638};
639
640// Allows to read vector<FormatStyle> while keeping default values.
641// IO.getContext() should contain a pointer to the FormatStyle structure, that
642// will be used to get default values for missing keys.
643// If the first element has no Language specified, it will be treated as the
644// default one for the following elements.
645template <> struct DocumentListTraits<std::vector<FormatStyle>> {
646  static size_t size(IO &IO, std::vector<FormatStyle> &Seq) {
647    return Seq.size();
648  }
649  static FormatStyle &element(IO &IO, std::vector<FormatStyle> &Seq,
650                              size_t Index) {
651    if (Index >= Seq.size()) {
652      assert(Index == Seq.size());
653      FormatStyle Template;
654      if (!Seq.empty() && Seq[0].Language == FormatStyle::LK_None) {
655        Template = Seq[0];
656      } else {
657        Template = *((const FormatStyle *)IO.getContext());
658        Template.Language = FormatStyle::LK_None;
659      }
660      Seq.resize(Index + 1, Template);
661    }
662    return Seq[Index];
663  }
664};
665} // namespace yaml
666} // namespace llvm
667
668namespace clang {
669namespace format {
670
671const std::error_category &getParseCategory() {
672  static const ParseErrorCategory C{};
673  return C;
674}
675std::error_code make_error_code(ParseError e) {
676  return std::error_code(static_cast<int>(e), getParseCategory());
677}
678
679inline llvm::Error make_string_error(const llvm::Twine &Message) {
680  return llvm::make_error<llvm::StringError>(Message,
681                                             llvm::inconvertibleErrorCode());
682}
683
684const char *ParseErrorCategory::name() const noexcept {
685  return "clang-format.parse_error";
686}
687
688std::string ParseErrorCategory::message(int EV) const {
689  switch (static_cast<ParseError>(EV)) {
690  case ParseError::Success:
691    return "Success";
692  case ParseError::Error:
693    return "Invalid argument";
694  case ParseError::Unsuitable:
695    return "Unsuitable";
696  case ParseError::BinPackTrailingCommaConflict:
697    return "trailing comma insertion cannot be used with bin packing";
698  }
699  llvm_unreachable("unexpected parse error");
700}
701
702static FormatStyle expandPresets(const FormatStyle &Style) {
703  if (Style.BreakBeforeBraces == FormatStyle::BS_Custom)
704    return Style;
705  FormatStyle Expanded = Style;
706  Expanded.BraceWrapping = {/*AfterCaseLabel=*/false,
707                            /*AfterClass=*/false,
708                            /*AfterControlStatement=*/FormatStyle::BWACS_Never,
709                            /*AfterEnum=*/false,
710                            /*AfterFunction=*/false,
711                            /*AfterNamespace=*/false,
712                            /*AfterObjCDeclaration=*/false,
713                            /*AfterStruct=*/false,
714                            /*AfterUnion=*/false,
715                            /*AfterExternBlock=*/false,
716                            /*BeforeCatch=*/false,
717                            /*BeforeElse=*/false,
718                            /*BeforeLambdaBody=*/false,
719                            /*BeforeWhile=*/false,
720                            /*IndentBraces=*/false,
721                            /*SplitEmptyFunction=*/true,
722                            /*SplitEmptyRecord=*/true,
723                            /*SplitEmptyNamespace=*/true};
724  switch (Style.BreakBeforeBraces) {
725  case FormatStyle::BS_Linux:
726    Expanded.BraceWrapping.AfterClass = true;
727    Expanded.BraceWrapping.AfterFunction = true;
728    Expanded.BraceWrapping.AfterNamespace = true;
729    break;
730  case FormatStyle::BS_Mozilla:
731    Expanded.BraceWrapping.AfterClass = true;
732    Expanded.BraceWrapping.AfterEnum = true;
733    Expanded.BraceWrapping.AfterFunction = true;
734    Expanded.BraceWrapping.AfterStruct = true;
735    Expanded.BraceWrapping.AfterUnion = true;
736    Expanded.BraceWrapping.AfterExternBlock = true;
737    Expanded.IndentExternBlock = FormatStyle::IEBS_AfterExternBlock;
738    Expanded.BraceWrapping.SplitEmptyFunction = true;
739    Expanded.BraceWrapping.SplitEmptyRecord = false;
740    break;
741  case FormatStyle::BS_Stroustrup:
742    Expanded.BraceWrapping.AfterFunction = true;
743    Expanded.BraceWrapping.BeforeCatch = true;
744    Expanded.BraceWrapping.BeforeElse = true;
745    break;
746  case FormatStyle::BS_Allman:
747    Expanded.BraceWrapping.AfterCaseLabel = true;
748    Expanded.BraceWrapping.AfterClass = true;
749    Expanded.BraceWrapping.AfterControlStatement = FormatStyle::BWACS_Always;
750    Expanded.BraceWrapping.AfterEnum = true;
751    Expanded.BraceWrapping.AfterFunction = true;
752    Expanded.BraceWrapping.AfterNamespace = true;
753    Expanded.BraceWrapping.AfterObjCDeclaration = true;
754    Expanded.BraceWrapping.AfterStruct = true;
755    Expanded.BraceWrapping.AfterUnion = true;
756    Expanded.BraceWrapping.AfterExternBlock = true;
757    Expanded.IndentExternBlock = FormatStyle::IEBS_AfterExternBlock;
758    Expanded.BraceWrapping.BeforeCatch = true;
759    Expanded.BraceWrapping.BeforeElse = true;
760    break;
761  case FormatStyle::BS_Whitesmiths:
762    Expanded.BraceWrapping.AfterCaseLabel = true;
763    Expanded.BraceWrapping.AfterClass = true;
764    Expanded.BraceWrapping.AfterControlStatement = FormatStyle::BWACS_Always;
765    Expanded.BraceWrapping.AfterEnum = true;
766    Expanded.BraceWrapping.AfterFunction = true;
767    Expanded.BraceWrapping.AfterNamespace = true;
768    Expanded.BraceWrapping.AfterObjCDeclaration = true;
769    Expanded.BraceWrapping.AfterStruct = true;
770    Expanded.BraceWrapping.AfterExternBlock = true;
771    Expanded.IndentExternBlock = FormatStyle::IEBS_AfterExternBlock;
772    Expanded.BraceWrapping.BeforeCatch = true;
773    Expanded.BraceWrapping.BeforeElse = true;
774    Expanded.BraceWrapping.BeforeLambdaBody = true;
775    break;
776  case FormatStyle::BS_GNU:
777    Expanded.BraceWrapping = {
778        /*AfterCaseLabel=*/true,
779        /*AfterClass=*/true,
780        /*AfterControlStatement=*/FormatStyle::BWACS_Always,
781        /*AfterEnum=*/true,
782        /*AfterFunction=*/true,
783        /*AfterNamespace=*/true,
784        /*AfterObjCDeclaration=*/true,
785        /*AfterStruct=*/true,
786        /*AfterUnion=*/true,
787        /*AfterExternBlock=*/true,
788        /*BeforeCatch=*/true,
789        /*BeforeElse=*/true,
790        /*BeforeLambdaBody=*/false,
791        /*BeforeWhile=*/true,
792        /*IndentBraces=*/true,
793        /*SplitEmptyFunction=*/true,
794        /*SplitEmptyRecord=*/true,
795        /*SplitEmptyNamespace=*/true};
796    Expanded.IndentExternBlock = FormatStyle::IEBS_AfterExternBlock;
797    break;
798  case FormatStyle::BS_WebKit:
799    Expanded.BraceWrapping.AfterFunction = true;
800    break;
801  default:
802    break;
803  }
804  return Expanded;
805}
806
807FormatStyle getLLVMStyle(FormatStyle::LanguageKind Language) {
808  FormatStyle LLVMStyle;
809  LLVMStyle.Language = Language;
810  LLVMStyle.AccessModifierOffset = -2;
811  LLVMStyle.AlignEscapedNewlines = FormatStyle::ENAS_Right;
812  LLVMStyle.AlignAfterOpenBracket = FormatStyle::BAS_Align;
813  LLVMStyle.AlignOperands = FormatStyle::OAS_Align;
814  LLVMStyle.AlignTrailingComments = true;
815  LLVMStyle.AlignConsecutiveAssignments = false;
816  LLVMStyle.AlignConsecutiveBitFields = false;
817  LLVMStyle.AlignConsecutiveDeclarations = false;
818  LLVMStyle.AlignConsecutiveMacros = false;
819  LLVMStyle.AllowAllArgumentsOnNextLine = true;
820  LLVMStyle.AllowAllConstructorInitializersOnNextLine = true;
821  LLVMStyle.AllowAllParametersOfDeclarationOnNextLine = true;
822  LLVMStyle.AllowShortEnumsOnASingleLine = true;
823  LLVMStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_All;
824  LLVMStyle.AllowShortBlocksOnASingleLine = FormatStyle::SBS_Never;
825  LLVMStyle.AllowShortCaseLabelsOnASingleLine = false;
826  LLVMStyle.AllowShortIfStatementsOnASingleLine = FormatStyle::SIS_Never;
827  LLVMStyle.AllowShortLambdasOnASingleLine = FormatStyle::SLS_All;
828  LLVMStyle.AllowShortLoopsOnASingleLine = false;
829  LLVMStyle.AlwaysBreakAfterReturnType = FormatStyle::RTBS_None;
830  LLVMStyle.AlwaysBreakAfterDefinitionReturnType = FormatStyle::DRTBS_None;
831  LLVMStyle.AlwaysBreakBeforeMultilineStrings = false;
832  LLVMStyle.AlwaysBreakTemplateDeclarations = FormatStyle::BTDS_MultiLine;
833  LLVMStyle.BinPackArguments = true;
834  LLVMStyle.BinPackParameters = true;
835  LLVMStyle.BreakBeforeBinaryOperators = FormatStyle::BOS_None;
836  LLVMStyle.BreakBeforeTernaryOperators = true;
837  LLVMStyle.BreakBeforeBraces = FormatStyle::BS_Attach;
838  LLVMStyle.BraceWrapping = {/*AfterCaseLabel=*/false,
839                             /*AfterClass=*/false,
840                             /*AfterControlStatement=*/FormatStyle::BWACS_Never,
841                             /*AfterEnum=*/false,
842                             /*AfterFunction=*/false,
843                             /*AfterNamespace=*/false,
844                             /*AfterObjCDeclaration=*/false,
845                             /*AfterStruct=*/false,
846                             /*AfterUnion=*/false,
847                             /*AfterExternBlock=*/false,
848                             /*BeforeCatch=*/false,
849                             /*BeforeElse=*/false,
850                             /*BeforeLambdaBody=*/false,
851                             /*BeforeWhile=*/false,
852                             /*IndentBraces=*/false,
853                             /*SplitEmptyFunction=*/true,
854                             /*SplitEmptyRecord=*/true,
855                             /*SplitEmptyNamespace=*/true};
856  LLVMStyle.IndentExternBlock = FormatStyle::IEBS_AfterExternBlock;
857  LLVMStyle.BreakAfterJavaFieldAnnotations = false;
858  LLVMStyle.BreakConstructorInitializers = FormatStyle::BCIS_BeforeColon;
859  LLVMStyle.BreakInheritanceList = FormatStyle::BILS_BeforeColon;
860  LLVMStyle.BreakStringLiterals = true;
861  LLVMStyle.ColumnLimit = 80;
862  LLVMStyle.CommentPragmas = "^ IWYU pragma:";
863  LLVMStyle.CompactNamespaces = false;
864  LLVMStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = false;
865  LLVMStyle.ConstructorInitializerIndentWidth = 4;
866  LLVMStyle.ContinuationIndentWidth = 4;
867  LLVMStyle.Cpp11BracedListStyle = true;
868  LLVMStyle.DeriveLineEnding = true;
869  LLVMStyle.DerivePointerAlignment = false;
870  LLVMStyle.ExperimentalAutoDetectBinPacking = false;
871  LLVMStyle.FixNamespaceComments = true;
872  LLVMStyle.ForEachMacros.push_back("foreach");
873  LLVMStyle.ForEachMacros.push_back("Q_FOREACH");
874  LLVMStyle.ForEachMacros.push_back("BOOST_FOREACH");
875  LLVMStyle.IncludeStyle.IncludeCategories = {
876      {"^\"(llvm|llvm-c|clang|clang-c)/", 2, 0},
877      {"^(<|\"(gtest|gmock|isl|json)/)", 3, 0},
878      {".*", 1, 0}};
879  LLVMStyle.IncludeStyle.IncludeIsMainRegex = "(Test)?$";
880  LLVMStyle.IncludeStyle.IncludeBlocks = tooling::IncludeStyle::IBS_Preserve;
881  LLVMStyle.IndentCaseLabels = false;
882  LLVMStyle.IndentCaseBlocks = false;
883  LLVMStyle.IndentGotoLabels = true;
884  LLVMStyle.IndentPPDirectives = FormatStyle::PPDIS_None;
885  LLVMStyle.IndentWrappedFunctionNames = false;
886  LLVMStyle.IndentWidth = 2;
887  LLVMStyle.InsertTrailingCommas = FormatStyle::TCS_None;
888  LLVMStyle.JavaScriptQuotes = FormatStyle::JSQS_Leave;
889  LLVMStyle.JavaScriptWrapImports = true;
890  LLVMStyle.TabWidth = 8;
891  LLVMStyle.MaxEmptyLinesToKeep = 1;
892  LLVMStyle.KeepEmptyLinesAtTheStartOfBlocks = true;
893  LLVMStyle.NamespaceIndentation = FormatStyle::NI_None;
894  LLVMStyle.ObjCBinPackProtocolList = FormatStyle::BPS_Auto;
895  LLVMStyle.ObjCBlockIndentWidth = 2;
896  LLVMStyle.ObjCBreakBeforeNestedBlockParam = true;
897  LLVMStyle.ObjCSpaceAfterProperty = false;
898  LLVMStyle.ObjCSpaceBeforeProtocolList = true;
899  LLVMStyle.PointerAlignment = FormatStyle::PAS_Right;
900  LLVMStyle.SpacesBeforeTrailingComments = 1;
901  LLVMStyle.Standard = FormatStyle::LS_Latest;
902  LLVMStyle.UseCRLF = false;
903  LLVMStyle.UseTab = FormatStyle::UT_Never;
904  LLVMStyle.ReflowComments = true;
905  LLVMStyle.SpacesInParentheses = false;
906  LLVMStyle.SpacesInSquareBrackets = false;
907  LLVMStyle.SpaceInEmptyBlock = false;
908  LLVMStyle.SpaceInEmptyParentheses = false;
909  LLVMStyle.SpacesInContainerLiterals = true;
910  LLVMStyle.SpacesInCStyleCastParentheses = false;
911  LLVMStyle.SpaceAfterCStyleCast = false;
912  LLVMStyle.SpaceAfterLogicalNot = false;
913  LLVMStyle.SpaceAfterTemplateKeyword = true;
914  LLVMStyle.SpaceBeforeCtorInitializerColon = true;
915  LLVMStyle.SpaceBeforeInheritanceColon = true;
916  LLVMStyle.SpaceBeforeParens = FormatStyle::SBPO_ControlStatements;
917  LLVMStyle.SpaceBeforeRangeBasedForLoopColon = true;
918  LLVMStyle.SpaceBeforeAssignmentOperators = true;
919  LLVMStyle.SpaceBeforeCpp11BracedList = false;
920  LLVMStyle.SpaceBeforeSquareBrackets = false;
921  LLVMStyle.SpacesInAngles = false;
922  LLVMStyle.SpacesInConditionalStatement = false;
923
924  LLVMStyle.PenaltyBreakAssignment = prec::Assignment;
925  LLVMStyle.PenaltyBreakComment = 300;
926  LLVMStyle.PenaltyBreakFirstLessLess = 120;
927  LLVMStyle.PenaltyBreakString = 1000;
928  LLVMStyle.PenaltyExcessCharacter = 1000000;
929  LLVMStyle.PenaltyReturnTypeOnItsOwnLine = 60;
930  LLVMStyle.PenaltyBreakBeforeFirstCallParameter = 19;
931  LLVMStyle.PenaltyBreakTemplateDeclaration = prec::Relational;
932
933  LLVMStyle.DisableFormat = false;
934  LLVMStyle.SortIncludes = true;
935  LLVMStyle.SortUsingDeclarations = true;
936  LLVMStyle.StatementMacros.push_back("Q_UNUSED");
937  LLVMStyle.StatementMacros.push_back("QT_REQUIRE_VERSION");
938  LLVMStyle.WhitespaceSensitiveMacros.push_back("STRINGIZE");
939  LLVMStyle.WhitespaceSensitiveMacros.push_back("PP_STRINGIZE");
940  LLVMStyle.WhitespaceSensitiveMacros.push_back("BOOST_PP_STRINGIZE");
941
942  // Defaults that differ when not C++.
943  if (Language == FormatStyle::LK_TableGen) {
944    LLVMStyle.SpacesInContainerLiterals = false;
945  }
946
947  return LLVMStyle;
948}
949
950FormatStyle getGoogleStyle(FormatStyle::LanguageKind Language) {
951  if (Language == FormatStyle::LK_TextProto) {
952    FormatStyle GoogleStyle = getGoogleStyle(FormatStyle::LK_Proto);
953    GoogleStyle.Language = FormatStyle::LK_TextProto;
954
955    return GoogleStyle;
956  }
957
958  FormatStyle GoogleStyle = getLLVMStyle(Language);
959
960  GoogleStyle.AccessModifierOffset = -1;
961  GoogleStyle.AlignEscapedNewlines = FormatStyle::ENAS_Left;
962  GoogleStyle.AllowShortIfStatementsOnASingleLine =
963      FormatStyle::SIS_WithoutElse;
964  GoogleStyle.AllowShortLoopsOnASingleLine = true;
965  GoogleStyle.AlwaysBreakBeforeMultilineStrings = true;
966  GoogleStyle.AlwaysBreakTemplateDeclarations = FormatStyle::BTDS_Yes;
967  GoogleStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = true;
968  GoogleStyle.DerivePointerAlignment = true;
969  GoogleStyle.IncludeStyle.IncludeCategories = {{"^<ext/.*\\.h>", 2, 0},
970                                                {"^<.*\\.h>", 1, 0},
971                                                {"^<.*", 2, 0},
972                                                {".*", 3, 0}};
973  GoogleStyle.IncludeStyle.IncludeIsMainRegex = "([-_](test|unittest))?$";
974  GoogleStyle.IncludeStyle.IncludeBlocks = tooling::IncludeStyle::IBS_Regroup;
975  GoogleStyle.IndentCaseLabels = true;
976  GoogleStyle.KeepEmptyLinesAtTheStartOfBlocks = false;
977  GoogleStyle.ObjCBinPackProtocolList = FormatStyle::BPS_Never;
978  GoogleStyle.ObjCSpaceAfterProperty = false;
979  GoogleStyle.ObjCSpaceBeforeProtocolList = true;
980  GoogleStyle.PointerAlignment = FormatStyle::PAS_Left;
981  GoogleStyle.RawStringFormats = {
982      {
983          FormatStyle::LK_Cpp,
984          /*Delimiters=*/
985          {
986              "cc",
987              "CC",
988              "cpp",
989              "Cpp",
990              "CPP",
991              "c++",
992              "C++",
993          },
994          /*EnclosingFunctionNames=*/
995          {},
996          /*CanonicalDelimiter=*/"",
997          /*BasedOnStyle=*/"google",
998      },
999      {
1000          FormatStyle::LK_TextProto,
1001          /*Delimiters=*/
1002          {
1003              "pb",
1004              "PB",
1005              "proto",
1006              "PROTO",
1007          },
1008          /*EnclosingFunctionNames=*/
1009          {
1010              "EqualsProto",
1011              "EquivToProto",
1012              "PARSE_PARTIAL_TEXT_PROTO",
1013              "PARSE_TEST_PROTO",
1014              "PARSE_TEXT_PROTO",
1015              "ParseTextOrDie",
1016              "ParseTextProtoOrDie",
1017              "ParseTestProto",
1018              "ParsePartialTestProto",
1019          },
1020          /*CanonicalDelimiter=*/"",
1021          /*BasedOnStyle=*/"google",
1022      },
1023  };
1024  GoogleStyle.SpacesBeforeTrailingComments = 2;
1025  GoogleStyle.Standard = FormatStyle::LS_Auto;
1026
1027  GoogleStyle.PenaltyReturnTypeOnItsOwnLine = 200;
1028  GoogleStyle.PenaltyBreakBeforeFirstCallParameter = 1;
1029
1030  if (Language == FormatStyle::LK_Java) {
1031    GoogleStyle.AlignAfterOpenBracket = FormatStyle::BAS_DontAlign;
1032    GoogleStyle.AlignOperands = FormatStyle::OAS_DontAlign;
1033    GoogleStyle.AlignTrailingComments = false;
1034    GoogleStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Empty;
1035    GoogleStyle.AllowShortIfStatementsOnASingleLine = FormatStyle::SIS_Never;
1036    GoogleStyle.AlwaysBreakBeforeMultilineStrings = false;
1037    GoogleStyle.BreakBeforeBinaryOperators = FormatStyle::BOS_NonAssignment;
1038    GoogleStyle.ColumnLimit = 100;
1039    GoogleStyle.SpaceAfterCStyleCast = true;
1040    GoogleStyle.SpacesBeforeTrailingComments = 1;
1041  } else if (Language == FormatStyle::LK_JavaScript) {
1042    GoogleStyle.AlignAfterOpenBracket = FormatStyle::BAS_AlwaysBreak;
1043    GoogleStyle.AlignOperands = FormatStyle::OAS_DontAlign;
1044    GoogleStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Empty;
1045    // TODO: still under discussion whether to switch to SLS_All.
1046    GoogleStyle.AllowShortLambdasOnASingleLine = FormatStyle::SLS_Empty;
1047    GoogleStyle.AlwaysBreakBeforeMultilineStrings = false;
1048    GoogleStyle.BreakBeforeTernaryOperators = false;
1049    // taze:, triple slash directives (`/// <...`), tslint:, and @see, which is
1050    // commonly followed by overlong URLs.
1051    GoogleStyle.CommentPragmas = "(taze:|^/[ \t]*<|tslint:|@see)";
1052    // TODO: enable once decided, in particular re disabling bin packing.
1053    // https://google.github.io/styleguide/jsguide.html#features-arrays-trailing-comma
1054    // GoogleStyle.InsertTrailingCommas = FormatStyle::TCS_Wrapped;
1055    GoogleStyle.MaxEmptyLinesToKeep = 3;
1056    GoogleStyle.NamespaceIndentation = FormatStyle::NI_All;
1057    GoogleStyle.SpacesInContainerLiterals = false;
1058    GoogleStyle.JavaScriptQuotes = FormatStyle::JSQS_Single;
1059    GoogleStyle.JavaScriptWrapImports = false;
1060  } else if (Language == FormatStyle::LK_Proto) {
1061    GoogleStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Empty;
1062    GoogleStyle.AlwaysBreakBeforeMultilineStrings = false;
1063    GoogleStyle.SpacesInContainerLiterals = false;
1064    GoogleStyle.Cpp11BracedListStyle = false;
1065    // This affects protocol buffer options specifications and text protos.
1066    // Text protos are currently mostly formatted inside C++ raw string literals
1067    // and often the current breaking behavior of string literals is not
1068    // beneficial there. Investigate turning this on once proper string reflow
1069    // has been implemented.
1070    GoogleStyle.BreakStringLiterals = false;
1071  } else if (Language == FormatStyle::LK_ObjC) {
1072    GoogleStyle.AlwaysBreakBeforeMultilineStrings = false;
1073    GoogleStyle.ColumnLimit = 100;
1074    // "Regroup" doesn't work well for ObjC yet (main header heuristic,
1075    // relationship between ObjC standard library headers and other heades,
1076    // #imports, etc.)
1077    GoogleStyle.IncludeStyle.IncludeBlocks =
1078        tooling::IncludeStyle::IBS_Preserve;
1079  } else if (Language == FormatStyle::LK_CSharp) {
1080    GoogleStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Empty;
1081    GoogleStyle.AllowShortIfStatementsOnASingleLine = FormatStyle::SIS_Never;
1082    GoogleStyle.BreakStringLiterals = false;
1083    GoogleStyle.ColumnLimit = 100;
1084    GoogleStyle.NamespaceIndentation = FormatStyle::NI_All;
1085  }
1086
1087  return GoogleStyle;
1088}
1089
1090FormatStyle getChromiumStyle(FormatStyle::LanguageKind Language) {
1091  FormatStyle ChromiumStyle = getGoogleStyle(Language);
1092
1093  // Disable include reordering across blocks in Chromium code.
1094  // - clang-format tries to detect that foo.h is the "main" header for
1095  //   foo.cc and foo_unittest.cc via IncludeIsMainRegex. However, Chromium
1096  //   uses many other suffices (_win.cc, _mac.mm, _posix.cc, _browsertest.cc,
1097  //   _private.cc, _impl.cc etc) in different permutations
1098  //   (_win_browsertest.cc) so disable this until IncludeIsMainRegex has a
1099  //   better default for Chromium code.
1100  // - The default for .cc and .mm files is different (r357695) for Google style
1101  //   for the same reason. The plan is to unify this again once the main
1102  //   header detection works for Google's ObjC code, but this hasn't happened
1103  //   yet. Since Chromium has some ObjC code, switching Chromium is blocked
1104  //   on that.
1105  // - Finally, "If include reordering is harmful, put things in different
1106  //   blocks to prevent it" has been a recommendation for a long time that
1107  //   people are used to. We'll need a dev education push to change this to
1108  //   "If include reordering is harmful, put things in a different block and
1109  //   _prepend that with a comment_ to prevent it" before changing behavior.
1110  ChromiumStyle.IncludeStyle.IncludeBlocks =
1111      tooling::IncludeStyle::IBS_Preserve;
1112
1113  if (Language == FormatStyle::LK_Java) {
1114    ChromiumStyle.AllowShortIfStatementsOnASingleLine =
1115        FormatStyle::SIS_WithoutElse;
1116    ChromiumStyle.BreakAfterJavaFieldAnnotations = true;
1117    ChromiumStyle.ContinuationIndentWidth = 8;
1118    ChromiumStyle.IndentWidth = 4;
1119    // See styleguide for import groups:
1120    // https://chromium.googlesource.com/chromium/src/+/master/styleguide/java/java.md#Import-Order
1121    ChromiumStyle.JavaImportGroups = {
1122        "android",
1123        "androidx",
1124        "com",
1125        "dalvik",
1126        "junit",
1127        "org",
1128        "com.google.android.apps.chrome",
1129        "org.chromium",
1130        "java",
1131        "javax",
1132    };
1133    ChromiumStyle.SortIncludes = true;
1134  } else if (Language == FormatStyle::LK_JavaScript) {
1135    ChromiumStyle.AllowShortIfStatementsOnASingleLine = FormatStyle::SIS_Never;
1136    ChromiumStyle.AllowShortLoopsOnASingleLine = false;
1137  } else {
1138    ChromiumStyle.AllowAllParametersOfDeclarationOnNextLine = false;
1139    ChromiumStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Inline;
1140    ChromiumStyle.AllowShortIfStatementsOnASingleLine = FormatStyle::SIS_Never;
1141    ChromiumStyle.AllowShortLoopsOnASingleLine = false;
1142    ChromiumStyle.BinPackParameters = false;
1143    ChromiumStyle.DerivePointerAlignment = false;
1144    if (Language == FormatStyle::LK_ObjC)
1145      ChromiumStyle.ColumnLimit = 80;
1146  }
1147  return ChromiumStyle;
1148}
1149
1150FormatStyle getMozillaStyle() {
1151  FormatStyle MozillaStyle = getLLVMStyle();
1152  MozillaStyle.AllowAllParametersOfDeclarationOnNextLine = false;
1153  MozillaStyle.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_Inline;
1154  MozillaStyle.AlwaysBreakAfterReturnType = FormatStyle::RTBS_TopLevel;
1155  MozillaStyle.AlwaysBreakAfterDefinitionReturnType =
1156      FormatStyle::DRTBS_TopLevel;
1157  MozillaStyle.AlwaysBreakTemplateDeclarations = FormatStyle::BTDS_Yes;
1158  MozillaStyle.BinPackParameters = false;
1159  MozillaStyle.BinPackArguments = false;
1160  MozillaStyle.BreakBeforeBraces = FormatStyle::BS_Mozilla;
1161  MozillaStyle.BreakConstructorInitializers = FormatStyle::BCIS_BeforeComma;
1162  MozillaStyle.BreakInheritanceList = FormatStyle::BILS_BeforeComma;
1163  MozillaStyle.ConstructorInitializerIndentWidth = 2;
1164  MozillaStyle.ContinuationIndentWidth = 2;
1165  MozillaStyle.Cpp11BracedListStyle = false;
1166  MozillaStyle.FixNamespaceComments = false;
1167  MozillaStyle.IndentCaseLabels = true;
1168  MozillaStyle.ObjCSpaceAfterProperty = true;
1169  MozillaStyle.ObjCSpaceBeforeProtocolList = false;
1170  MozillaStyle.PenaltyReturnTypeOnItsOwnLine = 200;
1171  MozillaStyle.PointerAlignment = FormatStyle::PAS_Left;
1172  MozillaStyle.SpaceAfterTemplateKeyword = false;
1173  return MozillaStyle;
1174}
1175
1176FormatStyle getWebKitStyle() {
1177  FormatStyle Style = getLLVMStyle();
1178  Style.AccessModifierOffset = -4;
1179  Style.AlignAfterOpenBracket = FormatStyle::BAS_DontAlign;
1180  Style.AlignOperands = FormatStyle::OAS_DontAlign;
1181  Style.AlignTrailingComments = false;
1182  Style.AllowShortBlocksOnASingleLine = FormatStyle::SBS_Empty;
1183  Style.BreakBeforeBinaryOperators = FormatStyle::BOS_All;
1184  Style.BreakBeforeBraces = FormatStyle::BS_WebKit;
1185  Style.BreakConstructorInitializers = FormatStyle::BCIS_BeforeComma;
1186  Style.Cpp11BracedListStyle = false;
1187  Style.ColumnLimit = 0;
1188  Style.FixNamespaceComments = false;
1189  Style.IndentWidth = 4;
1190  Style.NamespaceIndentation = FormatStyle::NI_Inner;
1191  Style.ObjCBlockIndentWidth = 4;
1192  Style.ObjCSpaceAfterProperty = true;
1193  Style.PointerAlignment = FormatStyle::PAS_Left;
1194  Style.SpaceBeforeCpp11BracedList = true;
1195  Style.SpaceInEmptyBlock = true;
1196  return Style;
1197}
1198
1199FormatStyle getGNUStyle() {
1200  FormatStyle Style = getLLVMStyle();
1201  Style.AlwaysBreakAfterDefinitionReturnType = FormatStyle::DRTBS_All;
1202  Style.AlwaysBreakAfterReturnType = FormatStyle::RTBS_AllDefinitions;
1203  Style.BreakBeforeBinaryOperators = FormatStyle::BOS_All;
1204  Style.BreakBeforeBraces = FormatStyle::BS_GNU;
1205  Style.BreakBeforeTernaryOperators = true;
1206  Style.Cpp11BracedListStyle = false;
1207  Style.ColumnLimit = 79;
1208  Style.FixNamespaceComments = false;
1209  Style.SpaceBeforeParens = FormatStyle::SBPO_Always;
1210  Style.Standard = FormatStyle::LS_Cpp03;
1211  return Style;
1212}
1213
1214FormatStyle getMicrosoftStyle(FormatStyle::LanguageKind Language) {
1215  FormatStyle Style = getLLVMStyle(Language);
1216  Style.ColumnLimit = 120;
1217  Style.TabWidth = 4;
1218  Style.IndentWidth = 4;
1219  Style.UseTab = FormatStyle::UT_Never;
1220  Style.BreakBeforeBraces = FormatStyle::BS_Custom;
1221  Style.BraceWrapping.AfterClass = true;
1222  Style.BraceWrapping.AfterControlStatement = FormatStyle::BWACS_Always;
1223  Style.BraceWrapping.AfterEnum = true;
1224  Style.BraceWrapping.AfterFunction = true;
1225  Style.BraceWrapping.AfterNamespace = true;
1226  Style.BraceWrapping.AfterObjCDeclaration = true;
1227  Style.BraceWrapping.AfterStruct = true;
1228  Style.BraceWrapping.AfterExternBlock = true;
1229  Style.IndentExternBlock = FormatStyle::IEBS_AfterExternBlock;
1230  Style.BraceWrapping.BeforeCatch = true;
1231  Style.BraceWrapping.BeforeElse = true;
1232  Style.BraceWrapping.BeforeWhile = false;
1233  Style.PenaltyReturnTypeOnItsOwnLine = 1000;
1234  Style.AllowShortEnumsOnASingleLine = false;
1235  Style.AllowShortFunctionsOnASingleLine = FormatStyle::SFS_None;
1236  Style.AllowShortCaseLabelsOnASingleLine = false;
1237  Style.AllowShortIfStatementsOnASingleLine = FormatStyle::SIS_Never;
1238  Style.AllowShortLoopsOnASingleLine = false;
1239  Style.AlwaysBreakAfterDefinitionReturnType = FormatStyle::DRTBS_None;
1240  Style.AlwaysBreakAfterReturnType = FormatStyle::RTBS_None;
1241  return Style;
1242}
1243
1244FormatStyle getNoStyle() {
1245  FormatStyle NoStyle = getLLVMStyle();
1246  NoStyle.DisableFormat = true;
1247  NoStyle.SortIncludes = false;
1248  NoStyle.SortUsingDeclarations = false;
1249  return NoStyle;
1250}
1251
1252bool getPredefinedStyle(StringRef Name, FormatStyle::LanguageKind Language,
1253                        FormatStyle *Style) {
1254  if (Name.equals_lower("llvm")) {
1255    *Style = getLLVMStyle(Language);
1256  } else if (Name.equals_lower("chromium")) {
1257    *Style = getChromiumStyle(Language);
1258  } else if (Name.equals_lower("mozilla")) {
1259    *Style = getMozillaStyle();
1260  } else if (Name.equals_lower("google")) {
1261    *Style = getGoogleStyle(Language);
1262  } else if (Name.equals_lower("webkit")) {
1263    *Style = getWebKitStyle();
1264  } else if (Name.equals_lower("gnu")) {
1265    *Style = getGNUStyle();
1266  } else if (Name.equals_lower("microsoft")) {
1267    *Style = getMicrosoftStyle(Language);
1268  } else if (Name.equals_lower("none")) {
1269    *Style = getNoStyle();
1270  } else {
1271    return false;
1272  }
1273
1274  Style->Language = Language;
1275  return true;
1276}
1277
1278std::error_code parseConfiguration(StringRef Text, FormatStyle *Style) {
1279  assert(Style);
1280  FormatStyle::LanguageKind Language = Style->Language;
1281  assert(Language != FormatStyle::LK_None);
1282  if (Text.trim().empty())
1283    return make_error_code(ParseError::Error);
1284  Style->StyleSet.Clear();
1285  std::vector<FormatStyle> Styles;
1286  llvm::yaml::Input Input(Text);
1287  // DocumentListTraits<vector<FormatStyle>> uses the context to get default
1288  // values for the fields, keys for which are missing from the configuration.
1289  // Mapping also uses the context to get the language to find the correct
1290  // base style.
1291  Input.setContext(Style);
1292  Input >> Styles;
1293  if (Input.error())
1294    return Input.error();
1295
1296  for (unsigned i = 0; i < Styles.size(); ++i) {
1297    // Ensures that only the first configuration can skip the Language option.
1298    if (Styles[i].Language == FormatStyle::LK_None && i != 0)
1299      return make_error_code(ParseError::Error);
1300    // Ensure that each language is configured at most once.
1301    for (unsigned j = 0; j < i; ++j) {
1302      if (Styles[i].Language == Styles[j].Language) {
1303        LLVM_DEBUG(llvm::dbgs()
1304                   << "Duplicate languages in the config file on positions "
1305                   << j << " and " << i << "\n");
1306        return make_error_code(ParseError::Error);
1307      }
1308    }
1309  }
1310  // Look for a suitable configuration starting from the end, so we can
1311  // find the configuration for the specific language first, and the default
1312  // configuration (which can only be at slot 0) after it.
1313  FormatStyle::FormatStyleSet StyleSet;
1314  bool LanguageFound = false;
1315  for (int i = Styles.size() - 1; i >= 0; --i) {
1316    if (Styles[i].Language != FormatStyle::LK_None)
1317      StyleSet.Add(Styles[i]);
1318    if (Styles[i].Language == Language)
1319      LanguageFound = true;
1320  }
1321  if (!LanguageFound) {
1322    if (Styles.empty() || Styles[0].Language != FormatStyle::LK_None)
1323      return make_error_code(ParseError::Unsuitable);
1324    FormatStyle DefaultStyle = Styles[0];
1325    DefaultStyle.Language = Language;
1326    StyleSet.Add(std::move(DefaultStyle));
1327  }
1328  *Style = *StyleSet.Get(Language);
1329  if (Style->InsertTrailingCommas != FormatStyle::TCS_None &&
1330      Style->BinPackArguments) {
1331    // See comment on FormatStyle::TSC_Wrapped.
1332    return make_error_code(ParseError::BinPackTrailingCommaConflict);
1333  }
1334  return make_error_code(ParseError::Success);
1335}
1336
1337std::string configurationAsText(const FormatStyle &Style) {
1338  std::string Text;
1339  llvm::raw_string_ostream Stream(Text);
1340  llvm::yaml::Output Output(Stream);
1341  // We use the same mapping method for input and output, so we need a non-const
1342  // reference here.
1343  FormatStyle NonConstStyle = expandPresets(Style);
1344  Output << NonConstStyle;
1345  return Stream.str();
1346}
1347
1348llvm::Optional<FormatStyle>
1349FormatStyle::FormatStyleSet::Get(FormatStyle::LanguageKind Language) const {
1350  if (!Styles)
1351    return None;
1352  auto It = Styles->find(Language);
1353  if (It == Styles->end())
1354    return None;
1355  FormatStyle Style = It->second;
1356  Style.StyleSet = *this;
1357  return Style;
1358}
1359
1360void FormatStyle::FormatStyleSet::Add(FormatStyle Style) {
1361  assert(Style.Language != LK_None &&
1362         "Cannot add a style for LK_None to a StyleSet");
1363  assert(
1364      !Style.StyleSet.Styles &&
1365      "Cannot add a style associated with an existing StyleSet to a StyleSet");
1366  if (!Styles)
1367    Styles = std::make_shared<MapType>();
1368  (*Styles)[Style.Language] = std::move(Style);
1369}
1370
1371void FormatStyle::FormatStyleSet::Clear() { Styles.reset(); }
1372
1373llvm::Optional<FormatStyle>
1374FormatStyle::GetLanguageStyle(FormatStyle::LanguageKind Language) const {
1375  return StyleSet.Get(Language);
1376}
1377
1378namespace {
1379
1380class JavaScriptRequoter : public TokenAnalyzer {
1381public:
1382  JavaScriptRequoter(const Environment &Env, const FormatStyle &Style)
1383      : TokenAnalyzer(Env, Style) {}
1384
1385  std::pair<tooling::Replacements, unsigned>
1386  analyze(TokenAnnotator &Annotator,
1387          SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
1388          FormatTokenLexer &Tokens) override {
1389    AffectedRangeMgr.computeAffectedLines(AnnotatedLines);
1390    tooling::Replacements Result;
1391    requoteJSStringLiteral(AnnotatedLines, Result);
1392    return {Result, 0};
1393  }
1394
1395private:
1396  // Replaces double/single-quoted string literal as appropriate, re-escaping
1397  // the contents in the process.
1398  void requoteJSStringLiteral(SmallVectorImpl<AnnotatedLine *> &Lines,
1399                              tooling::Replacements &Result) {
1400    for (AnnotatedLine *Line : Lines) {
1401      requoteJSStringLiteral(Line->Children, Result);
1402      if (!Line->Affected)
1403        continue;
1404      for (FormatToken *FormatTok = Line->First; FormatTok;
1405           FormatTok = FormatTok->Next) {
1406        StringRef Input = FormatTok->TokenText;
1407        if (FormatTok->Finalized || !FormatTok->isStringLiteral() ||
1408            // NB: testing for not starting with a double quote to avoid
1409            // breaking `template strings`.
1410            (Style.JavaScriptQuotes == FormatStyle::JSQS_Single &&
1411             !Input.startswith("\"")) ||
1412            (Style.JavaScriptQuotes == FormatStyle::JSQS_Double &&
1413             !Input.startswith("\'")))
1414          continue;
1415
1416        // Change start and end quote.
1417        bool IsSingle = Style.JavaScriptQuotes == FormatStyle::JSQS_Single;
1418        SourceLocation Start = FormatTok->Tok.getLocation();
1419        auto Replace = [&](SourceLocation Start, unsigned Length,
1420                           StringRef ReplacementText) {
1421          auto Err = Result.add(tooling::Replacement(
1422              Env.getSourceManager(), Start, Length, ReplacementText));
1423          // FIXME: handle error. For now, print error message and skip the
1424          // replacement for release version.
1425          if (Err) {
1426            llvm::errs() << llvm::toString(std::move(Err)) << "\n";
1427            assert(false);
1428          }
1429        };
1430        Replace(Start, 1, IsSingle ? "'" : "\"");
1431        Replace(FormatTok->Tok.getEndLoc().getLocWithOffset(-1), 1,
1432                IsSingle ? "'" : "\"");
1433
1434        // Escape internal quotes.
1435        bool Escaped = false;
1436        for (size_t i = 1; i < Input.size() - 1; i++) {
1437          switch (Input[i]) {
1438          case '\\':
1439            if (!Escaped && i + 1 < Input.size() &&
1440                ((IsSingle && Input[i + 1] == '"') ||
1441                 (!IsSingle && Input[i + 1] == '\''))) {
1442              // Remove this \, it's escaping a " or ' that no longer needs
1443              // escaping
1444              Replace(Start.getLocWithOffset(i), 1, "");
1445              continue;
1446            }
1447            Escaped = !Escaped;
1448            break;
1449          case '\"':
1450          case '\'':
1451            if (!Escaped && IsSingle == (Input[i] == '\'')) {
1452              // Escape the quote.
1453              Replace(Start.getLocWithOffset(i), 0, "\\");
1454            }
1455            Escaped = false;
1456            break;
1457          default:
1458            Escaped = false;
1459            break;
1460          }
1461        }
1462      }
1463    }
1464  }
1465};
1466
1467class Formatter : public TokenAnalyzer {
1468public:
1469  Formatter(const Environment &Env, const FormatStyle &Style,
1470            FormattingAttemptStatus *Status)
1471      : TokenAnalyzer(Env, Style), Status(Status) {}
1472
1473  std::pair<tooling::Replacements, unsigned>
1474  analyze(TokenAnnotator &Annotator,
1475          SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
1476          FormatTokenLexer &Tokens) override {
1477    tooling::Replacements Result;
1478    deriveLocalStyle(AnnotatedLines);
1479    AffectedRangeMgr.computeAffectedLines(AnnotatedLines);
1480    for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1481      Annotator.calculateFormattingInformation(*AnnotatedLines[i]);
1482    }
1483    Annotator.setCommentLineLevels(AnnotatedLines);
1484
1485    WhitespaceManager Whitespaces(
1486        Env.getSourceManager(), Style,
1487        Style.DeriveLineEnding
1488            ? inputUsesCRLF(
1489                  Env.getSourceManager().getBufferData(Env.getFileID()),
1490                  Style.UseCRLF)
1491            : Style.UseCRLF);
1492    ContinuationIndenter Indenter(Style, Tokens.getKeywords(),
1493                                  Env.getSourceManager(), Whitespaces, Encoding,
1494                                  BinPackInconclusiveFunctions);
1495    unsigned Penalty =
1496        UnwrappedLineFormatter(&Indenter, &Whitespaces, Style,
1497                               Tokens.getKeywords(), Env.getSourceManager(),
1498                               Status)
1499            .format(AnnotatedLines, /*DryRun=*/false,
1500                    /*AdditionalIndent=*/0,
1501                    /*FixBadIndentation=*/false,
1502                    /*FirstStartColumn=*/Env.getFirstStartColumn(),
1503                    /*NextStartColumn=*/Env.getNextStartColumn(),
1504                    /*LastStartColumn=*/Env.getLastStartColumn());
1505    for (const auto &R : Whitespaces.generateReplacements())
1506      if (Result.add(R))
1507        return std::make_pair(Result, 0);
1508    return std::make_pair(Result, Penalty);
1509  }
1510
1511private:
1512  static bool inputUsesCRLF(StringRef Text, bool DefaultToCRLF) {
1513    size_t LF = Text.count('\n');
1514    size_t CR = Text.count('\r') * 2;
1515    return LF == CR ? DefaultToCRLF : CR > LF;
1516  }
1517
1518  bool
1519  hasCpp03IncompatibleFormat(const SmallVectorImpl<AnnotatedLine *> &Lines) {
1520    for (const AnnotatedLine *Line : Lines) {
1521      if (hasCpp03IncompatibleFormat(Line->Children))
1522        return true;
1523      for (FormatToken *Tok = Line->First->Next; Tok; Tok = Tok->Next) {
1524        if (Tok->WhitespaceRange.getBegin() == Tok->WhitespaceRange.getEnd()) {
1525          if (Tok->is(tok::coloncolon) && Tok->Previous->is(TT_TemplateOpener))
1526            return true;
1527          if (Tok->is(TT_TemplateCloser) &&
1528              Tok->Previous->is(TT_TemplateCloser))
1529            return true;
1530        }
1531      }
1532    }
1533    return false;
1534  }
1535
1536  int countVariableAlignments(const SmallVectorImpl<AnnotatedLine *> &Lines) {
1537    int AlignmentDiff = 0;
1538    for (const AnnotatedLine *Line : Lines) {
1539      AlignmentDiff += countVariableAlignments(Line->Children);
1540      for (FormatToken *Tok = Line->First; Tok && Tok->Next; Tok = Tok->Next) {
1541        if (!Tok->is(TT_PointerOrReference))
1542          continue;
1543        bool SpaceBefore =
1544            Tok->WhitespaceRange.getBegin() != Tok->WhitespaceRange.getEnd();
1545        bool SpaceAfter = Tok->Next->WhitespaceRange.getBegin() !=
1546                          Tok->Next->WhitespaceRange.getEnd();
1547        if (SpaceBefore && !SpaceAfter)
1548          ++AlignmentDiff;
1549        if (!SpaceBefore && SpaceAfter)
1550          --AlignmentDiff;
1551      }
1552    }
1553    return AlignmentDiff;
1554  }
1555
1556  void
1557  deriveLocalStyle(const SmallVectorImpl<AnnotatedLine *> &AnnotatedLines) {
1558    bool HasBinPackedFunction = false;
1559    bool HasOnePerLineFunction = false;
1560    for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1561      if (!AnnotatedLines[i]->First->Next)
1562        continue;
1563      FormatToken *Tok = AnnotatedLines[i]->First->Next;
1564      while (Tok->Next) {
1565        if (Tok->PackingKind == PPK_BinPacked)
1566          HasBinPackedFunction = true;
1567        if (Tok->PackingKind == PPK_OnePerLine)
1568          HasOnePerLineFunction = true;
1569
1570        Tok = Tok->Next;
1571      }
1572    }
1573    if (Style.DerivePointerAlignment)
1574      Style.PointerAlignment = countVariableAlignments(AnnotatedLines) <= 0
1575                                   ? FormatStyle::PAS_Left
1576                                   : FormatStyle::PAS_Right;
1577    if (Style.Standard == FormatStyle::LS_Auto)
1578      Style.Standard = hasCpp03IncompatibleFormat(AnnotatedLines)
1579                           ? FormatStyle::LS_Latest
1580                           : FormatStyle::LS_Cpp03;
1581    BinPackInconclusiveFunctions =
1582        HasBinPackedFunction || !HasOnePerLineFunction;
1583  }
1584
1585  bool BinPackInconclusiveFunctions;
1586  FormattingAttemptStatus *Status;
1587};
1588
1589/// TrailingCommaInserter inserts trailing commas into container literals.
1590/// E.g.:
1591///     const x = [
1592///       1,
1593///     ];
1594/// TrailingCommaInserter runs after formatting. To avoid causing a required
1595/// reformatting (and thus reflow), it never inserts a comma that'd exceed the
1596/// ColumnLimit.
1597///
1598/// Because trailing commas disable binpacking of arrays, TrailingCommaInserter
1599/// is conceptually incompatible with bin packing.
1600class TrailingCommaInserter : public TokenAnalyzer {
1601public:
1602  TrailingCommaInserter(const Environment &Env, const FormatStyle &Style)
1603      : TokenAnalyzer(Env, Style) {}
1604
1605  std::pair<tooling::Replacements, unsigned>
1606  analyze(TokenAnnotator &Annotator,
1607          SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
1608          FormatTokenLexer &Tokens) override {
1609    AffectedRangeMgr.computeAffectedLines(AnnotatedLines);
1610    tooling::Replacements Result;
1611    insertTrailingCommas(AnnotatedLines, Result);
1612    return {Result, 0};
1613  }
1614
1615private:
1616  /// Inserts trailing commas in [] and {} initializers if they wrap over
1617  /// multiple lines.
1618  void insertTrailingCommas(SmallVectorImpl<AnnotatedLine *> &Lines,
1619                            tooling::Replacements &Result) {
1620    for (AnnotatedLine *Line : Lines) {
1621      insertTrailingCommas(Line->Children, Result);
1622      if (!Line->Affected)
1623        continue;
1624      for (FormatToken *FormatTok = Line->First; FormatTok;
1625           FormatTok = FormatTok->Next) {
1626        if (FormatTok->NewlinesBefore == 0)
1627          continue;
1628        FormatToken *Matching = FormatTok->MatchingParen;
1629        if (!Matching || !FormatTok->getPreviousNonComment())
1630          continue;
1631        if (!(FormatTok->is(tok::r_square) &&
1632              Matching->is(TT_ArrayInitializerLSquare)) &&
1633            !(FormatTok->is(tok::r_brace) && Matching->is(TT_DictLiteral)))
1634          continue;
1635        FormatToken *Prev = FormatTok->getPreviousNonComment();
1636        if (Prev->is(tok::comma) || Prev->is(tok::semi))
1637          continue;
1638        // getEndLoc is not reliably set during re-lexing, use text length
1639        // instead.
1640        SourceLocation Start =
1641            Prev->Tok.getLocation().getLocWithOffset(Prev->TokenText.size());
1642        // If inserting a comma would push the code over the column limit, skip
1643        // this location - it'd introduce an unstable formatting due to the
1644        // required reflow.
1645        unsigned ColumnNumber =
1646            Env.getSourceManager().getSpellingColumnNumber(Start);
1647        if (ColumnNumber > Style.ColumnLimit)
1648          continue;
1649        // Comma insertions cannot conflict with each other, and this pass has a
1650        // clean set of Replacements, so the operation below cannot fail.
1651        cantFail(Result.add(
1652            tooling::Replacement(Env.getSourceManager(), Start, 0, ",")));
1653      }
1654    }
1655  }
1656};
1657
1658// This class clean up the erroneous/redundant code around the given ranges in
1659// file.
1660class Cleaner : public TokenAnalyzer {
1661public:
1662  Cleaner(const Environment &Env, const FormatStyle &Style)
1663      : TokenAnalyzer(Env, Style),
1664        DeletedTokens(FormatTokenLess(Env.getSourceManager())) {}
1665
1666  // FIXME: eliminate unused parameters.
1667  std::pair<tooling::Replacements, unsigned>
1668  analyze(TokenAnnotator &Annotator,
1669          SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
1670          FormatTokenLexer &Tokens) override {
1671    // FIXME: in the current implementation the granularity of affected range
1672    // is an annotated line. However, this is not sufficient. Furthermore,
1673    // redundant code introduced by replacements does not necessarily
1674    // intercept with ranges of replacements that result in the redundancy.
1675    // To determine if some redundant code is actually introduced by
1676    // replacements(e.g. deletions), we need to come up with a more
1677    // sophisticated way of computing affected ranges.
1678    AffectedRangeMgr.computeAffectedLines(AnnotatedLines);
1679
1680    checkEmptyNamespace(AnnotatedLines);
1681
1682    for (auto *Line : AnnotatedLines)
1683      cleanupLine(Line);
1684
1685    return {generateFixes(), 0};
1686  }
1687
1688private:
1689  void cleanupLine(AnnotatedLine *Line) {
1690    for (auto *Child : Line->Children) {
1691      cleanupLine(Child);
1692    }
1693
1694    if (Line->Affected) {
1695      cleanupRight(Line->First, tok::comma, tok::comma);
1696      cleanupRight(Line->First, TT_CtorInitializerColon, tok::comma);
1697      cleanupRight(Line->First, tok::l_paren, tok::comma);
1698      cleanupLeft(Line->First, tok::comma, tok::r_paren);
1699      cleanupLeft(Line->First, TT_CtorInitializerComma, tok::l_brace);
1700      cleanupLeft(Line->First, TT_CtorInitializerColon, tok::l_brace);
1701      cleanupLeft(Line->First, TT_CtorInitializerColon, tok::equal);
1702    }
1703  }
1704
1705  bool containsOnlyComments(const AnnotatedLine &Line) {
1706    for (FormatToken *Tok = Line.First; Tok != nullptr; Tok = Tok->Next) {
1707      if (Tok->isNot(tok::comment))
1708        return false;
1709    }
1710    return true;
1711  }
1712
1713  // Iterate through all lines and remove any empty (nested) namespaces.
1714  void checkEmptyNamespace(SmallVectorImpl<AnnotatedLine *> &AnnotatedLines) {
1715    std::set<unsigned> DeletedLines;
1716    for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1717      auto &Line = *AnnotatedLines[i];
1718      if (Line.startsWithNamespace()) {
1719        checkEmptyNamespace(AnnotatedLines, i, i, DeletedLines);
1720      }
1721    }
1722
1723    for (auto Line : DeletedLines) {
1724      FormatToken *Tok = AnnotatedLines[Line]->First;
1725      while (Tok) {
1726        deleteToken(Tok);
1727        Tok = Tok->Next;
1728      }
1729    }
1730  }
1731
1732  // The function checks if the namespace, which starts from \p CurrentLine, and
1733  // its nested namespaces are empty and delete them if they are empty. It also
1734  // sets \p NewLine to the last line checked.
1735  // Returns true if the current namespace is empty.
1736  bool checkEmptyNamespace(SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
1737                           unsigned CurrentLine, unsigned &NewLine,
1738                           std::set<unsigned> &DeletedLines) {
1739    unsigned InitLine = CurrentLine, End = AnnotatedLines.size();
1740    if (Style.BraceWrapping.AfterNamespace) {
1741      // If the left brace is in a new line, we should consume it first so that
1742      // it does not make the namespace non-empty.
1743      // FIXME: error handling if there is no left brace.
1744      if (!AnnotatedLines[++CurrentLine]->startsWith(tok::l_brace)) {
1745        NewLine = CurrentLine;
1746        return false;
1747      }
1748    } else if (!AnnotatedLines[CurrentLine]->endsWith(tok::l_brace)) {
1749      return false;
1750    }
1751    while (++CurrentLine < End) {
1752      if (AnnotatedLines[CurrentLine]->startsWith(tok::r_brace))
1753        break;
1754
1755      if (AnnotatedLines[CurrentLine]->startsWithNamespace()) {
1756        if (!checkEmptyNamespace(AnnotatedLines, CurrentLine, NewLine,
1757                                 DeletedLines))
1758          return false;
1759        CurrentLine = NewLine;
1760        continue;
1761      }
1762
1763      if (containsOnlyComments(*AnnotatedLines[CurrentLine]))
1764        continue;
1765
1766      // If there is anything other than comments or nested namespaces in the
1767      // current namespace, the namespace cannot be empty.
1768      NewLine = CurrentLine;
1769      return false;
1770    }
1771
1772    NewLine = CurrentLine;
1773    if (CurrentLine >= End)
1774      return false;
1775
1776    // Check if the empty namespace is actually affected by changed ranges.
1777    if (!AffectedRangeMgr.affectsCharSourceRange(CharSourceRange::getCharRange(
1778            AnnotatedLines[InitLine]->First->Tok.getLocation(),
1779            AnnotatedLines[CurrentLine]->Last->Tok.getEndLoc())))
1780      return false;
1781
1782    for (unsigned i = InitLine; i <= CurrentLine; ++i) {
1783      DeletedLines.insert(i);
1784    }
1785
1786    return true;
1787  }
1788
1789  // Checks pairs {start, start->next},..., {end->previous, end} and deletes one
1790  // of the token in the pair if the left token has \p LK token kind and the
1791  // right token has \p RK token kind. If \p DeleteLeft is true, the left token
1792  // is deleted on match; otherwise, the right token is deleted.
1793  template <typename LeftKind, typename RightKind>
1794  void cleanupPair(FormatToken *Start, LeftKind LK, RightKind RK,
1795                   bool DeleteLeft) {
1796    auto NextNotDeleted = [this](const FormatToken &Tok) -> FormatToken * {
1797      for (auto *Res = Tok.Next; Res; Res = Res->Next)
1798        if (!Res->is(tok::comment) &&
1799            DeletedTokens.find(Res) == DeletedTokens.end())
1800          return Res;
1801      return nullptr;
1802    };
1803    for (auto *Left = Start; Left;) {
1804      auto *Right = NextNotDeleted(*Left);
1805      if (!Right)
1806        break;
1807      if (Left->is(LK) && Right->is(RK)) {
1808        deleteToken(DeleteLeft ? Left : Right);
1809        for (auto *Tok = Left->Next; Tok && Tok != Right; Tok = Tok->Next)
1810          deleteToken(Tok);
1811        // If the right token is deleted, we should keep the left token
1812        // unchanged and pair it with the new right token.
1813        if (!DeleteLeft)
1814          continue;
1815      }
1816      Left = Right;
1817    }
1818  }
1819
1820  template <typename LeftKind, typename RightKind>
1821  void cleanupLeft(FormatToken *Start, LeftKind LK, RightKind RK) {
1822    cleanupPair(Start, LK, RK, /*DeleteLeft=*/true);
1823  }
1824
1825  template <typename LeftKind, typename RightKind>
1826  void cleanupRight(FormatToken *Start, LeftKind LK, RightKind RK) {
1827    cleanupPair(Start, LK, RK, /*DeleteLeft=*/false);
1828  }
1829
1830  // Delete the given token.
1831  inline void deleteToken(FormatToken *Tok) {
1832    if (Tok)
1833      DeletedTokens.insert(Tok);
1834  }
1835
1836  tooling::Replacements generateFixes() {
1837    tooling::Replacements Fixes;
1838    std::vector<FormatToken *> Tokens;
1839    std::copy(DeletedTokens.begin(), DeletedTokens.end(),
1840              std::back_inserter(Tokens));
1841
1842    // Merge multiple continuous token deletions into one big deletion so that
1843    // the number of replacements can be reduced. This makes computing affected
1844    // ranges more efficient when we run reformat on the changed code.
1845    unsigned Idx = 0;
1846    while (Idx < Tokens.size()) {
1847      unsigned St = Idx, End = Idx;
1848      while ((End + 1) < Tokens.size() &&
1849             Tokens[End]->Next == Tokens[End + 1]) {
1850        End++;
1851      }
1852      auto SR = CharSourceRange::getCharRange(Tokens[St]->Tok.getLocation(),
1853                                              Tokens[End]->Tok.getEndLoc());
1854      auto Err =
1855          Fixes.add(tooling::Replacement(Env.getSourceManager(), SR, ""));
1856      // FIXME: better error handling. for now just print error message and skip
1857      // for the release version.
1858      if (Err) {
1859        llvm::errs() << llvm::toString(std::move(Err)) << "\n";
1860        assert(false && "Fixes must not conflict!");
1861      }
1862      Idx = End + 1;
1863    }
1864
1865    return Fixes;
1866  }
1867
1868  // Class for less-than inequality comparason for the set `RedundantTokens`.
1869  // We store tokens in the order they appear in the translation unit so that
1870  // we do not need to sort them in `generateFixes()`.
1871  struct FormatTokenLess {
1872    FormatTokenLess(const SourceManager &SM) : SM(SM) {}
1873
1874    bool operator()(const FormatToken *LHS, const FormatToken *RHS) const {
1875      return SM.isBeforeInTranslationUnit(LHS->Tok.getLocation(),
1876                                          RHS->Tok.getLocation());
1877    }
1878    const SourceManager &SM;
1879  };
1880
1881  // Tokens to be deleted.
1882  std::set<FormatToken *, FormatTokenLess> DeletedTokens;
1883};
1884
1885class ObjCHeaderStyleGuesser : public TokenAnalyzer {
1886public:
1887  ObjCHeaderStyleGuesser(const Environment &Env, const FormatStyle &Style)
1888      : TokenAnalyzer(Env, Style), IsObjC(false) {}
1889
1890  std::pair<tooling::Replacements, unsigned>
1891  analyze(TokenAnnotator &Annotator,
1892          SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
1893          FormatTokenLexer &Tokens) override {
1894    assert(Style.Language == FormatStyle::LK_Cpp);
1895    IsObjC = guessIsObjC(Env.getSourceManager(), AnnotatedLines,
1896                         Tokens.getKeywords());
1897    tooling::Replacements Result;
1898    return {Result, 0};
1899  }
1900
1901  bool isObjC() { return IsObjC; }
1902
1903private:
1904  static bool
1905  guessIsObjC(const SourceManager &SourceManager,
1906              const SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
1907              const AdditionalKeywords &Keywords) {
1908    // Keep this array sorted, since we are binary searching over it.
1909    static constexpr llvm::StringLiteral FoundationIdentifiers[] = {
1910        "CGFloat",
1911        "CGPoint",
1912        "CGPointMake",
1913        "CGPointZero",
1914        "CGRect",
1915        "CGRectEdge",
1916        "CGRectInfinite",
1917        "CGRectMake",
1918        "CGRectNull",
1919        "CGRectZero",
1920        "CGSize",
1921        "CGSizeMake",
1922        "CGVector",
1923        "CGVectorMake",
1924        "NSAffineTransform",
1925        "NSArray",
1926        "NSAttributedString",
1927        "NSBlockOperation",
1928        "NSBundle",
1929        "NSCache",
1930        "NSCalendar",
1931        "NSCharacterSet",
1932        "NSCountedSet",
1933        "NSData",
1934        "NSDataDetector",
1935        "NSDecimal",
1936        "NSDecimalNumber",
1937        "NSDictionary",
1938        "NSEdgeInsets",
1939        "NSHashTable",
1940        "NSIndexPath",
1941        "NSIndexSet",
1942        "NSInteger",
1943        "NSInvocationOperation",
1944        "NSLocale",
1945        "NSMapTable",
1946        "NSMutableArray",
1947        "NSMutableAttributedString",
1948        "NSMutableCharacterSet",
1949        "NSMutableData",
1950        "NSMutableDictionary",
1951        "NSMutableIndexSet",
1952        "NSMutableOrderedSet",
1953        "NSMutableSet",
1954        "NSMutableString",
1955        "NSNumber",
1956        "NSNumberFormatter",
1957        "NSObject",
1958        "NSOperation",
1959        "NSOperationQueue",
1960        "NSOperationQueuePriority",
1961        "NSOrderedSet",
1962        "NSPoint",
1963        "NSPointerArray",
1964        "NSQualityOfService",
1965        "NSRange",
1966        "NSRect",
1967        "NSRegularExpression",
1968        "NSSet",
1969        "NSSize",
1970        "NSString",
1971        "NSTimeZone",
1972        "NSUInteger",
1973        "NSURL",
1974        "NSURLComponents",
1975        "NSURLQueryItem",
1976        "NSUUID",
1977        "NSValue",
1978        "UIImage",
1979        "UIView",
1980    };
1981
1982    for (auto Line : AnnotatedLines) {
1983      for (const FormatToken *FormatTok = Line->First; FormatTok;
1984           FormatTok = FormatTok->Next) {
1985        if ((FormatTok->Previous && FormatTok->Previous->is(tok::at) &&
1986             (FormatTok->Tok.getObjCKeywordID() != tok::objc_not_keyword ||
1987              FormatTok->isOneOf(tok::numeric_constant, tok::l_square,
1988                                 tok::l_brace))) ||
1989            (FormatTok->Tok.isAnyIdentifier() &&
1990             std::binary_search(std::begin(FoundationIdentifiers),
1991                                std::end(FoundationIdentifiers),
1992                                FormatTok->TokenText)) ||
1993            FormatTok->is(TT_ObjCStringLiteral) ||
1994            FormatTok->isOneOf(Keywords.kw_NS_CLOSED_ENUM, Keywords.kw_NS_ENUM,
1995                               Keywords.kw_NS_OPTIONS, TT_ObjCBlockLBrace,
1996                               TT_ObjCBlockLParen, TT_ObjCDecl, TT_ObjCForIn,
1997                               TT_ObjCMethodExpr, TT_ObjCMethodSpecifier,
1998                               TT_ObjCProperty)) {
1999          LLVM_DEBUG(llvm::dbgs()
2000                     << "Detected ObjC at location "
2001                     << FormatTok->Tok.getLocation().printToString(
2002                            SourceManager)
2003                     << " token: " << FormatTok->TokenText << " token type: "
2004                     << getTokenTypeName(FormatTok->getType()) << "\n");
2005          return true;
2006        }
2007        if (guessIsObjC(SourceManager, Line->Children, Keywords))
2008          return true;
2009      }
2010    }
2011    return false;
2012  }
2013
2014  bool IsObjC;
2015};
2016
2017struct IncludeDirective {
2018  StringRef Filename;
2019  StringRef Text;
2020  unsigned Offset;
2021  int Category;
2022  int Priority;
2023};
2024
2025struct JavaImportDirective {
2026  StringRef Identifier;
2027  StringRef Text;
2028  unsigned Offset;
2029  std::vector<StringRef> AssociatedCommentLines;
2030  bool IsStatic;
2031};
2032
2033} // end anonymous namespace
2034
2035// Determines whether 'Ranges' intersects with ('Start', 'End').
2036static bool affectsRange(ArrayRef<tooling::Range> Ranges, unsigned Start,
2037                         unsigned End) {
2038  for (auto Range : Ranges) {
2039    if (Range.getOffset() < End &&
2040        Range.getOffset() + Range.getLength() > Start)
2041      return true;
2042  }
2043  return false;
2044}
2045
2046// Returns a pair (Index, OffsetToEOL) describing the position of the cursor
2047// before sorting/deduplicating. Index is the index of the include under the
2048// cursor in the original set of includes. If this include has duplicates, it is
2049// the index of the first of the duplicates as the others are going to be
2050// removed. OffsetToEOL describes the cursor's position relative to the end of
2051// its current line.
2052// If `Cursor` is not on any #include, `Index` will be UINT_MAX.
2053static std::pair<unsigned, unsigned>
2054FindCursorIndex(const SmallVectorImpl<IncludeDirective> &Includes,
2055                const SmallVectorImpl<unsigned> &Indices, unsigned Cursor) {
2056  unsigned CursorIndex = UINT_MAX;
2057  unsigned OffsetToEOL = 0;
2058  for (int i = 0, e = Includes.size(); i != e; ++i) {
2059    unsigned Start = Includes[Indices[i]].Offset;
2060    unsigned End = Start + Includes[Indices[i]].Text.size();
2061    if (!(Cursor >= Start && Cursor < End))
2062      continue;
2063    CursorIndex = Indices[i];
2064    OffsetToEOL = End - Cursor;
2065    // Put the cursor on the only remaining #include among the duplicate
2066    // #includes.
2067    while (--i >= 0 && Includes[CursorIndex].Text == Includes[Indices[i]].Text)
2068      CursorIndex = i;
2069    break;
2070  }
2071  return std::make_pair(CursorIndex, OffsetToEOL);
2072}
2073
2074// Replace all "\r\n" with "\n".
2075std::string replaceCRLF(const std::string &Code) {
2076  std::string NewCode;
2077  size_t Pos = 0, LastPos = 0;
2078
2079  do {
2080    Pos = Code.find("\r\n", LastPos);
2081    if (Pos == LastPos) {
2082      LastPos++;
2083      continue;
2084    }
2085    if (Pos == std::string::npos) {
2086      NewCode += Code.substr(LastPos);
2087      break;
2088    }
2089    NewCode += Code.substr(LastPos, Pos - LastPos) + "\n";
2090    LastPos = Pos + 2;
2091  } while (Pos != std::string::npos);
2092
2093  return NewCode;
2094}
2095
2096// Sorts and deduplicate a block of includes given by 'Includes' alphabetically
2097// adding the necessary replacement to 'Replaces'. 'Includes' must be in strict
2098// source order.
2099// #include directives with the same text will be deduplicated, and only the
2100// first #include in the duplicate #includes remains. If the `Cursor` is
2101// provided and put on a deleted #include, it will be moved to the remaining
2102// #include in the duplicate #includes.
2103static void sortCppIncludes(const FormatStyle &Style,
2104                            const SmallVectorImpl<IncludeDirective> &Includes,
2105                            ArrayRef<tooling::Range> Ranges, StringRef FileName,
2106                            StringRef Code, tooling::Replacements &Replaces,
2107                            unsigned *Cursor) {
2108  tooling::IncludeCategoryManager Categories(Style.IncludeStyle, FileName);
2109  unsigned IncludesBeginOffset = Includes.front().Offset;
2110  unsigned IncludesEndOffset =
2111      Includes.back().Offset + Includes.back().Text.size();
2112  unsigned IncludesBlockSize = IncludesEndOffset - IncludesBeginOffset;
2113  if (!affectsRange(Ranges, IncludesBeginOffset, IncludesEndOffset))
2114    return;
2115  SmallVector<unsigned, 16> Indices;
2116  for (unsigned i = 0, e = Includes.size(); i != e; ++i) {
2117    Indices.push_back(i);
2118  }
2119  llvm::stable_sort(Indices, [&](unsigned LHSI, unsigned RHSI) {
2120    return std::tie(Includes[LHSI].Priority, Includes[LHSI].Filename) <
2121           std::tie(Includes[RHSI].Priority, Includes[RHSI].Filename);
2122  });
2123  // The index of the include on which the cursor will be put after
2124  // sorting/deduplicating.
2125  unsigned CursorIndex;
2126  // The offset from cursor to the end of line.
2127  unsigned CursorToEOLOffset;
2128  if (Cursor)
2129    std::tie(CursorIndex, CursorToEOLOffset) =
2130        FindCursorIndex(Includes, Indices, *Cursor);
2131
2132  // Deduplicate #includes.
2133  Indices.erase(std::unique(Indices.begin(), Indices.end(),
2134                            [&](unsigned LHSI, unsigned RHSI) {
2135                              return Includes[LHSI].Text == Includes[RHSI].Text;
2136                            }),
2137                Indices.end());
2138
2139  int CurrentCategory = Includes.front().Category;
2140
2141  // If the #includes are out of order, we generate a single replacement fixing
2142  // the entire block. Otherwise, no replacement is generated.
2143  // In case Style.IncldueStyle.IncludeBlocks != IBS_Preserve, this check is not
2144  // enough as additional newlines might be added or removed across #include
2145  // blocks. This we handle below by generating the updated #imclude blocks and
2146  // comparing it to the original.
2147  if (Indices.size() == Includes.size() && llvm::is_sorted(Indices) &&
2148      Style.IncludeStyle.IncludeBlocks == tooling::IncludeStyle::IBS_Preserve)
2149    return;
2150
2151  std::string result;
2152  for (unsigned Index : Indices) {
2153    if (!result.empty()) {
2154      result += "\n";
2155      if (Style.IncludeStyle.IncludeBlocks ==
2156              tooling::IncludeStyle::IBS_Regroup &&
2157          CurrentCategory != Includes[Index].Category)
2158        result += "\n";
2159    }
2160    result += Includes[Index].Text;
2161    if (Cursor && CursorIndex == Index)
2162      *Cursor = IncludesBeginOffset + result.size() - CursorToEOLOffset;
2163    CurrentCategory = Includes[Index].Category;
2164  }
2165
2166  // If the #includes are out of order, we generate a single replacement fixing
2167  // the entire range of blocks. Otherwise, no replacement is generated.
2168  if (replaceCRLF(result) == replaceCRLF(std::string(Code.substr(
2169                                 IncludesBeginOffset, IncludesBlockSize))))
2170    return;
2171
2172  auto Err = Replaces.add(tooling::Replacement(
2173      FileName, Includes.front().Offset, IncludesBlockSize, result));
2174  // FIXME: better error handling. For now, just skip the replacement for the
2175  // release version.
2176  if (Err) {
2177    llvm::errs() << llvm::toString(std::move(Err)) << "\n";
2178    assert(false);
2179  }
2180}
2181
2182namespace {
2183
2184const char CppIncludeRegexPattern[] =
2185    R"(^[\t\ ]*#[\t\ ]*(import|include)[^"<]*(["<][^">]*[">]))";
2186
2187} // anonymous namespace
2188
2189tooling::Replacements sortCppIncludes(const FormatStyle &Style, StringRef Code,
2190                                      ArrayRef<tooling::Range> Ranges,
2191                                      StringRef FileName,
2192                                      tooling::Replacements &Replaces,
2193                                      unsigned *Cursor) {
2194  unsigned Prev = 0;
2195  unsigned SearchFrom = 0;
2196  llvm::Regex IncludeRegex(CppIncludeRegexPattern);
2197  SmallVector<StringRef, 4> Matches;
2198  SmallVector<IncludeDirective, 16> IncludesInBlock;
2199
2200  // In compiled files, consider the first #include to be the main #include of
2201  // the file if it is not a system #include. This ensures that the header
2202  // doesn't have hidden dependencies
2203  // (http://llvm.org/docs/CodingStandards.html#include-style).
2204  //
2205  // FIXME: Do some sanity checking, e.g. edit distance of the base name, to fix
2206  // cases where the first #include is unlikely to be the main header.
2207  tooling::IncludeCategoryManager Categories(Style.IncludeStyle, FileName);
2208  bool FirstIncludeBlock = true;
2209  bool MainIncludeFound = false;
2210  bool FormattingOff = false;
2211
2212  for (;;) {
2213    auto Pos = Code.find('\n', SearchFrom);
2214    StringRef Line =
2215        Code.substr(Prev, (Pos != StringRef::npos ? Pos : Code.size()) - Prev);
2216
2217    StringRef Trimmed = Line.trim();
2218    if (Trimmed == "// clang-format off" || Trimmed == "/* clang-format off */")
2219      FormattingOff = true;
2220    else if (Trimmed == "// clang-format on" ||
2221             Trimmed == "/* clang-format on */")
2222      FormattingOff = false;
2223
2224    const bool EmptyLineSkipped =
2225        Trimmed.empty() &&
2226        (Style.IncludeStyle.IncludeBlocks == tooling::IncludeStyle::IBS_Merge ||
2227         Style.IncludeStyle.IncludeBlocks ==
2228             tooling::IncludeStyle::IBS_Regroup);
2229
2230    if (!FormattingOff && !Line.endswith("\\")) {
2231      if (IncludeRegex.match(Line, &Matches)) {
2232        StringRef IncludeName = Matches[2];
2233        int Category = Categories.getIncludePriority(
2234            IncludeName,
2235            /*CheckMainHeader=*/!MainIncludeFound && FirstIncludeBlock);
2236        int Priority = Categories.getSortIncludePriority(
2237            IncludeName, !MainIncludeFound && FirstIncludeBlock);
2238        if (Category == 0)
2239          MainIncludeFound = true;
2240        IncludesInBlock.push_back(
2241            {IncludeName, Line, Prev, Category, Priority});
2242      } else if (!IncludesInBlock.empty() && !EmptyLineSkipped) {
2243        sortCppIncludes(Style, IncludesInBlock, Ranges, FileName, Code,
2244                        Replaces, Cursor);
2245        IncludesInBlock.clear();
2246        FirstIncludeBlock = false;
2247      }
2248      Prev = Pos + 1;
2249    }
2250    if (Pos == StringRef::npos || Pos + 1 == Code.size())
2251      break;
2252    SearchFrom = Pos + 1;
2253  }
2254  if (!IncludesInBlock.empty()) {
2255    sortCppIncludes(Style, IncludesInBlock, Ranges, FileName, Code, Replaces,
2256                    Cursor);
2257  }
2258  return Replaces;
2259}
2260
2261// Returns group number to use as a first order sort on imports. Gives UINT_MAX
2262// if the import does not match any given groups.
2263static unsigned findJavaImportGroup(const FormatStyle &Style,
2264                                    StringRef ImportIdentifier) {
2265  unsigned LongestMatchIndex = UINT_MAX;
2266  unsigned LongestMatchLength = 0;
2267  for (unsigned I = 0; I < Style.JavaImportGroups.size(); I++) {
2268    std::string GroupPrefix = Style.JavaImportGroups[I];
2269    if (ImportIdentifier.startswith(GroupPrefix) &&
2270        GroupPrefix.length() > LongestMatchLength) {
2271      LongestMatchIndex = I;
2272      LongestMatchLength = GroupPrefix.length();
2273    }
2274  }
2275  return LongestMatchIndex;
2276}
2277
2278// Sorts and deduplicates a block of includes given by 'Imports' based on
2279// JavaImportGroups, then adding the necessary replacement to 'Replaces'.
2280// Import declarations with the same text will be deduplicated. Between each
2281// import group, a newline is inserted, and within each import group, a
2282// lexicographic sort based on ASCII value is performed.
2283static void sortJavaImports(const FormatStyle &Style,
2284                            const SmallVectorImpl<JavaImportDirective> &Imports,
2285                            ArrayRef<tooling::Range> Ranges, StringRef FileName,
2286                            StringRef Code, tooling::Replacements &Replaces) {
2287  unsigned ImportsBeginOffset = Imports.front().Offset;
2288  unsigned ImportsEndOffset =
2289      Imports.back().Offset + Imports.back().Text.size();
2290  unsigned ImportsBlockSize = ImportsEndOffset - ImportsBeginOffset;
2291  if (!affectsRange(Ranges, ImportsBeginOffset, ImportsEndOffset))
2292    return;
2293  SmallVector<unsigned, 16> Indices;
2294  SmallVector<unsigned, 16> JavaImportGroups;
2295  for (unsigned i = 0, e = Imports.size(); i != e; ++i) {
2296    Indices.push_back(i);
2297    JavaImportGroups.push_back(
2298        findJavaImportGroup(Style, Imports[i].Identifier));
2299  }
2300  llvm::sort(Indices, [&](unsigned LHSI, unsigned RHSI) {
2301    // Negating IsStatic to push static imports above non-static imports.
2302    return std::make_tuple(!Imports[LHSI].IsStatic, JavaImportGroups[LHSI],
2303                           Imports[LHSI].Identifier) <
2304           std::make_tuple(!Imports[RHSI].IsStatic, JavaImportGroups[RHSI],
2305                           Imports[RHSI].Identifier);
2306  });
2307
2308  // Deduplicate imports.
2309  Indices.erase(std::unique(Indices.begin(), Indices.end(),
2310                            [&](unsigned LHSI, unsigned RHSI) {
2311                              return Imports[LHSI].Text == Imports[RHSI].Text;
2312                            }),
2313                Indices.end());
2314
2315  bool CurrentIsStatic = Imports[Indices.front()].IsStatic;
2316  unsigned CurrentImportGroup = JavaImportGroups[Indices.front()];
2317
2318  std::string result;
2319  for (unsigned Index : Indices) {
2320    if (!result.empty()) {
2321      result += "\n";
2322      if (CurrentIsStatic != Imports[Index].IsStatic ||
2323          CurrentImportGroup != JavaImportGroups[Index])
2324        result += "\n";
2325    }
2326    for (StringRef CommentLine : Imports[Index].AssociatedCommentLines) {
2327      result += CommentLine;
2328      result += "\n";
2329    }
2330    result += Imports[Index].Text;
2331    CurrentIsStatic = Imports[Index].IsStatic;
2332    CurrentImportGroup = JavaImportGroups[Index];
2333  }
2334
2335  // If the imports are out of order, we generate a single replacement fixing
2336  // the entire block. Otherwise, no replacement is generated.
2337  if (replaceCRLF(result) == replaceCRLF(std::string(Code.substr(
2338                                 Imports.front().Offset, ImportsBlockSize))))
2339    return;
2340
2341  auto Err = Replaces.add(tooling::Replacement(FileName, Imports.front().Offset,
2342                                               ImportsBlockSize, result));
2343  // FIXME: better error handling. For now, just skip the replacement for the
2344  // release version.
2345  if (Err) {
2346    llvm::errs() << llvm::toString(std::move(Err)) << "\n";
2347    assert(false);
2348  }
2349}
2350
2351namespace {
2352
2353const char JavaImportRegexPattern[] =
2354    "^[\t ]*import[\t ]+(static[\t ]*)?([^\t ]*)[\t ]*;";
2355
2356} // anonymous namespace
2357
2358tooling::Replacements sortJavaImports(const FormatStyle &Style, StringRef Code,
2359                                      ArrayRef<tooling::Range> Ranges,
2360                                      StringRef FileName,
2361                                      tooling::Replacements &Replaces) {
2362  unsigned Prev = 0;
2363  unsigned SearchFrom = 0;
2364  llvm::Regex ImportRegex(JavaImportRegexPattern);
2365  SmallVector<StringRef, 4> Matches;
2366  SmallVector<JavaImportDirective, 16> ImportsInBlock;
2367  std::vector<StringRef> AssociatedCommentLines;
2368
2369  bool FormattingOff = false;
2370
2371  for (;;) {
2372    auto Pos = Code.find('\n', SearchFrom);
2373    StringRef Line =
2374        Code.substr(Prev, (Pos != StringRef::npos ? Pos : Code.size()) - Prev);
2375
2376    StringRef Trimmed = Line.trim();
2377    if (Trimmed == "// clang-format off")
2378      FormattingOff = true;
2379    else if (Trimmed == "// clang-format on")
2380      FormattingOff = false;
2381
2382    if (ImportRegex.match(Line, &Matches)) {
2383      if (FormattingOff) {
2384        // If at least one import line has formatting turned off, turn off
2385        // formatting entirely.
2386        return Replaces;
2387      }
2388      StringRef Static = Matches[1];
2389      StringRef Identifier = Matches[2];
2390      bool IsStatic = false;
2391      if (Static.contains("static")) {
2392        IsStatic = true;
2393      }
2394      ImportsInBlock.push_back(
2395          {Identifier, Line, Prev, AssociatedCommentLines, IsStatic});
2396      AssociatedCommentLines.clear();
2397    } else if (Trimmed.size() > 0 && !ImportsInBlock.empty()) {
2398      // Associating comments within the imports with the nearest import below
2399      AssociatedCommentLines.push_back(Line);
2400    }
2401    Prev = Pos + 1;
2402    if (Pos == StringRef::npos || Pos + 1 == Code.size())
2403      break;
2404    SearchFrom = Pos + 1;
2405  }
2406  if (!ImportsInBlock.empty())
2407    sortJavaImports(Style, ImportsInBlock, Ranges, FileName, Code, Replaces);
2408  return Replaces;
2409}
2410
2411bool isMpegTS(StringRef Code) {
2412  // MPEG transport streams use the ".ts" file extension. clang-format should
2413  // not attempt to format those. MPEG TS' frame format starts with 0x47 every
2414  // 189 bytes - detect that and return.
2415  return Code.size() > 188 && Code[0] == 0x47 && Code[188] == 0x47;
2416}
2417
2418bool isLikelyXml(StringRef Code) { return Code.ltrim().startswith("<"); }
2419
2420tooling::Replacements sortIncludes(const FormatStyle &Style, StringRef Code,
2421                                   ArrayRef<tooling::Range> Ranges,
2422                                   StringRef FileName, unsigned *Cursor) {
2423  tooling::Replacements Replaces;
2424  if (!Style.SortIncludes)
2425    return Replaces;
2426  if (isLikelyXml(Code))
2427    return Replaces;
2428  if (Style.Language == FormatStyle::LanguageKind::LK_JavaScript &&
2429      isMpegTS(Code))
2430    return Replaces;
2431  if (Style.Language == FormatStyle::LanguageKind::LK_JavaScript)
2432    return sortJavaScriptImports(Style, Code, Ranges, FileName);
2433  if (Style.Language == FormatStyle::LanguageKind::LK_Java)
2434    return sortJavaImports(Style, Code, Ranges, FileName, Replaces);
2435  sortCppIncludes(Style, Code, Ranges, FileName, Replaces, Cursor);
2436  return Replaces;
2437}
2438
2439template <typename T>
2440static llvm::Expected<tooling::Replacements>
2441processReplacements(T ProcessFunc, StringRef Code,
2442                    const tooling::Replacements &Replaces,
2443                    const FormatStyle &Style) {
2444  if (Replaces.empty())
2445    return tooling::Replacements();
2446
2447  auto NewCode = applyAllReplacements(Code, Replaces);
2448  if (!NewCode)
2449    return NewCode.takeError();
2450  std::vector<tooling::Range> ChangedRanges = Replaces.getAffectedRanges();
2451  StringRef FileName = Replaces.begin()->getFilePath();
2452
2453  tooling::Replacements FormatReplaces =
2454      ProcessFunc(Style, *NewCode, ChangedRanges, FileName);
2455
2456  return Replaces.merge(FormatReplaces);
2457}
2458
2459llvm::Expected<tooling::Replacements>
2460formatReplacements(StringRef Code, const tooling::Replacements &Replaces,
2461                   const FormatStyle &Style) {
2462  // We need to use lambda function here since there are two versions of
2463  // `sortIncludes`.
2464  auto SortIncludes = [](const FormatStyle &Style, StringRef Code,
2465                         std::vector<tooling::Range> Ranges,
2466                         StringRef FileName) -> tooling::Replacements {
2467    return sortIncludes(Style, Code, Ranges, FileName);
2468  };
2469  auto SortedReplaces =
2470      processReplacements(SortIncludes, Code, Replaces, Style);
2471  if (!SortedReplaces)
2472    return SortedReplaces.takeError();
2473
2474  // We need to use lambda function here since there are two versions of
2475  // `reformat`.
2476  auto Reformat = [](const FormatStyle &Style, StringRef Code,
2477                     std::vector<tooling::Range> Ranges,
2478                     StringRef FileName) -> tooling::Replacements {
2479    return reformat(Style, Code, Ranges, FileName);
2480  };
2481  return processReplacements(Reformat, Code, *SortedReplaces, Style);
2482}
2483
2484namespace {
2485
2486inline bool isHeaderInsertion(const tooling::Replacement &Replace) {
2487  return Replace.getOffset() == UINT_MAX && Replace.getLength() == 0 &&
2488         llvm::Regex(CppIncludeRegexPattern)
2489             .match(Replace.getReplacementText());
2490}
2491
2492inline bool isHeaderDeletion(const tooling::Replacement &Replace) {
2493  return Replace.getOffset() == UINT_MAX && Replace.getLength() == 1;
2494}
2495
2496// FIXME: insert empty lines between newly created blocks.
2497tooling::Replacements
2498fixCppIncludeInsertions(StringRef Code, const tooling::Replacements &Replaces,
2499                        const FormatStyle &Style) {
2500  if (!Style.isCpp())
2501    return Replaces;
2502
2503  tooling::Replacements HeaderInsertions;
2504  std::set<llvm::StringRef> HeadersToDelete;
2505  tooling::Replacements Result;
2506  for (const auto &R : Replaces) {
2507    if (isHeaderInsertion(R)) {
2508      // Replacements from \p Replaces must be conflict-free already, so we can
2509      // simply consume the error.
2510      llvm::consumeError(HeaderInsertions.add(R));
2511    } else if (isHeaderDeletion(R)) {
2512      HeadersToDelete.insert(R.getReplacementText());
2513    } else if (R.getOffset() == UINT_MAX) {
2514      llvm::errs() << "Insertions other than header #include insertion are "
2515                      "not supported! "
2516                   << R.getReplacementText() << "\n";
2517    } else {
2518      llvm::consumeError(Result.add(R));
2519    }
2520  }
2521  if (HeaderInsertions.empty() && HeadersToDelete.empty())
2522    return Replaces;
2523
2524  StringRef FileName = Replaces.begin()->getFilePath();
2525  tooling::HeaderIncludes Includes(FileName, Code, Style.IncludeStyle);
2526
2527  for (const auto &Header : HeadersToDelete) {
2528    tooling::Replacements Replaces =
2529        Includes.remove(Header.trim("\"<>"), Header.startswith("<"));
2530    for (const auto &R : Replaces) {
2531      auto Err = Result.add(R);
2532      if (Err) {
2533        // Ignore the deletion on conflict.
2534        llvm::errs() << "Failed to add header deletion replacement for "
2535                     << Header << ": " << llvm::toString(std::move(Err))
2536                     << "\n";
2537      }
2538    }
2539  }
2540
2541  llvm::Regex IncludeRegex = llvm::Regex(CppIncludeRegexPattern);
2542  llvm::SmallVector<StringRef, 4> Matches;
2543  for (const auto &R : HeaderInsertions) {
2544    auto IncludeDirective = R.getReplacementText();
2545    bool Matched = IncludeRegex.match(IncludeDirective, &Matches);
2546    assert(Matched && "Header insertion replacement must have replacement text "
2547                      "'#include ...'");
2548    (void)Matched;
2549    auto IncludeName = Matches[2];
2550    auto Replace =
2551        Includes.insert(IncludeName.trim("\"<>"), IncludeName.startswith("<"));
2552    if (Replace) {
2553      auto Err = Result.add(*Replace);
2554      if (Err) {
2555        llvm::consumeError(std::move(Err));
2556        unsigned NewOffset =
2557            Result.getShiftedCodePosition(Replace->getOffset());
2558        auto Shifted = tooling::Replacement(FileName, NewOffset, 0,
2559                                            Replace->getReplacementText());
2560        Result = Result.merge(tooling::Replacements(Shifted));
2561      }
2562    }
2563  }
2564  return Result;
2565}
2566
2567} // anonymous namespace
2568
2569llvm::Expected<tooling::Replacements>
2570cleanupAroundReplacements(StringRef Code, const tooling::Replacements &Replaces,
2571                          const FormatStyle &Style) {
2572  // We need to use lambda function here since there are two versions of
2573  // `cleanup`.
2574  auto Cleanup = [](const FormatStyle &Style, StringRef Code,
2575                    std::vector<tooling::Range> Ranges,
2576                    StringRef FileName) -> tooling::Replacements {
2577    return cleanup(Style, Code, Ranges, FileName);
2578  };
2579  // Make header insertion replacements insert new headers into correct blocks.
2580  tooling::Replacements NewReplaces =
2581      fixCppIncludeInsertions(Code, Replaces, Style);
2582  return processReplacements(Cleanup, Code, NewReplaces, Style);
2583}
2584
2585namespace internal {
2586std::pair<tooling::Replacements, unsigned>
2587reformat(const FormatStyle &Style, StringRef Code,
2588         ArrayRef<tooling::Range> Ranges, unsigned FirstStartColumn,
2589         unsigned NextStartColumn, unsigned LastStartColumn, StringRef FileName,
2590         FormattingAttemptStatus *Status) {
2591  FormatStyle Expanded = expandPresets(Style);
2592  if (Expanded.DisableFormat)
2593    return {tooling::Replacements(), 0};
2594  if (isLikelyXml(Code))
2595    return {tooling::Replacements(), 0};
2596  if (Expanded.Language == FormatStyle::LK_JavaScript && isMpegTS(Code))
2597    return {tooling::Replacements(), 0};
2598
2599  typedef std::function<std::pair<tooling::Replacements, unsigned>(
2600      const Environment &)>
2601      AnalyzerPass;
2602  SmallVector<AnalyzerPass, 4> Passes;
2603
2604  if (Style.Language == FormatStyle::LK_Cpp) {
2605    if (Style.FixNamespaceComments)
2606      Passes.emplace_back([&](const Environment &Env) {
2607        return NamespaceEndCommentsFixer(Env, Expanded).process();
2608      });
2609
2610    if (Style.SortUsingDeclarations)
2611      Passes.emplace_back([&](const Environment &Env) {
2612        return UsingDeclarationsSorter(Env, Expanded).process();
2613      });
2614  }
2615
2616  if (Style.Language == FormatStyle::LK_JavaScript &&
2617      Style.JavaScriptQuotes != FormatStyle::JSQS_Leave)
2618    Passes.emplace_back([&](const Environment &Env) {
2619      return JavaScriptRequoter(Env, Expanded).process();
2620    });
2621
2622  Passes.emplace_back([&](const Environment &Env) {
2623    return Formatter(Env, Expanded, Status).process();
2624  });
2625
2626  if (Style.Language == FormatStyle::LK_JavaScript &&
2627      Style.InsertTrailingCommas == FormatStyle::TCS_Wrapped)
2628    Passes.emplace_back([&](const Environment &Env) {
2629      return TrailingCommaInserter(Env, Expanded).process();
2630    });
2631
2632  auto Env =
2633      std::make_unique<Environment>(Code, FileName, Ranges, FirstStartColumn,
2634                                    NextStartColumn, LastStartColumn);
2635  llvm::Optional<std::string> CurrentCode = None;
2636  tooling::Replacements Fixes;
2637  unsigned Penalty = 0;
2638  for (size_t I = 0, E = Passes.size(); I < E; ++I) {
2639    std::pair<tooling::Replacements, unsigned> PassFixes = Passes[I](*Env);
2640    auto NewCode = applyAllReplacements(
2641        CurrentCode ? StringRef(*CurrentCode) : Code, PassFixes.first);
2642    if (NewCode) {
2643      Fixes = Fixes.merge(PassFixes.first);
2644      Penalty += PassFixes.second;
2645      if (I + 1 < E) {
2646        CurrentCode = std::move(*NewCode);
2647        Env = std::make_unique<Environment>(
2648            *CurrentCode, FileName,
2649            tooling::calculateRangesAfterReplacements(Fixes, Ranges),
2650            FirstStartColumn, NextStartColumn, LastStartColumn);
2651      }
2652    }
2653  }
2654
2655  return {Fixes, Penalty};
2656}
2657} // namespace internal
2658
2659tooling::Replacements reformat(const FormatStyle &Style, StringRef Code,
2660                               ArrayRef<tooling::Range> Ranges,
2661                               StringRef FileName,
2662                               FormattingAttemptStatus *Status) {
2663  return internal::reformat(Style, Code, Ranges,
2664                            /*FirstStartColumn=*/0,
2665                            /*NextStartColumn=*/0,
2666                            /*LastStartColumn=*/0, FileName, Status)
2667      .first;
2668}
2669
2670tooling::Replacements cleanup(const FormatStyle &Style, StringRef Code,
2671                              ArrayRef<tooling::Range> Ranges,
2672                              StringRef FileName) {
2673  // cleanups only apply to C++ (they mostly concern ctor commas etc.)
2674  if (Style.Language != FormatStyle::LK_Cpp)
2675    return tooling::Replacements();
2676  return Cleaner(Environment(Code, FileName, Ranges), Style).process().first;
2677}
2678
2679tooling::Replacements reformat(const FormatStyle &Style, StringRef Code,
2680                               ArrayRef<tooling::Range> Ranges,
2681                               StringRef FileName, bool *IncompleteFormat) {
2682  FormattingAttemptStatus Status;
2683  auto Result = reformat(Style, Code, Ranges, FileName, &Status);
2684  if (!Status.FormatComplete)
2685    *IncompleteFormat = true;
2686  return Result;
2687}
2688
2689tooling::Replacements fixNamespaceEndComments(const FormatStyle &Style,
2690                                              StringRef Code,
2691                                              ArrayRef<tooling::Range> Ranges,
2692                                              StringRef FileName) {
2693  return NamespaceEndCommentsFixer(Environment(Code, FileName, Ranges), Style)
2694      .process()
2695      .first;
2696}
2697
2698tooling::Replacements sortUsingDeclarations(const FormatStyle &Style,
2699                                            StringRef Code,
2700                                            ArrayRef<tooling::Range> Ranges,
2701                                            StringRef FileName) {
2702  return UsingDeclarationsSorter(Environment(Code, FileName, Ranges), Style)
2703      .process()
2704      .first;
2705}
2706
2707LangOptions getFormattingLangOpts(const FormatStyle &Style) {
2708  LangOptions LangOpts;
2709
2710  FormatStyle::LanguageStandard LexingStd = Style.Standard;
2711  if (LexingStd == FormatStyle::LS_Auto)
2712    LexingStd = FormatStyle::LS_Latest;
2713  if (LexingStd == FormatStyle::LS_Latest)
2714    LexingStd = FormatStyle::LS_Cpp20;
2715  LangOpts.CPlusPlus = 1;
2716  LangOpts.CPlusPlus11 = LexingStd >= FormatStyle::LS_Cpp11;
2717  LangOpts.CPlusPlus14 = LexingStd >= FormatStyle::LS_Cpp14;
2718  LangOpts.CPlusPlus17 = LexingStd >= FormatStyle::LS_Cpp17;
2719  LangOpts.CPlusPlus20 = LexingStd >= FormatStyle::LS_Cpp20;
2720  LangOpts.Char8 = LexingStd >= FormatStyle::LS_Cpp20;
2721
2722  LangOpts.LineComment = 1;
2723  bool AlternativeOperators = Style.isCpp();
2724  LangOpts.CXXOperatorNames = AlternativeOperators ? 1 : 0;
2725  LangOpts.Bool = 1;
2726  LangOpts.ObjC = 1;
2727  LangOpts.MicrosoftExt = 1;    // To get kw___try, kw___finally.
2728  LangOpts.DeclSpecKeyword = 1; // To get __declspec.
2729  return LangOpts;
2730}
2731
2732const char *StyleOptionHelpDescription =
2733    "Coding style, currently supports:\n"
2734    "  LLVM, GNU, Google, Chromium, Microsoft, Mozilla, WebKit.\n"
2735    "Use -style=file to load style configuration from\n"
2736    ".clang-format file located in one of the parent\n"
2737    "directories of the source file (or current\n"
2738    "directory for stdin).\n"
2739    "Use -style=\"{key: value, ...}\" to set specific\n"
2740    "parameters, e.g.:\n"
2741    "  -style=\"{BasedOnStyle: llvm, IndentWidth: 8}\"";
2742
2743static FormatStyle::LanguageKind getLanguageByFileName(StringRef FileName) {
2744  if (FileName.endswith(".java"))
2745    return FormatStyle::LK_Java;
2746  if (FileName.endswith_lower(".js") || FileName.endswith_lower(".mjs") ||
2747      FileName.endswith_lower(".ts"))
2748    return FormatStyle::LK_JavaScript; // (module) JavaScript or TypeScript.
2749  if (FileName.endswith(".m") || FileName.endswith(".mm"))
2750    return FormatStyle::LK_ObjC;
2751  if (FileName.endswith_lower(".proto") ||
2752      FileName.endswith_lower(".protodevel"))
2753    return FormatStyle::LK_Proto;
2754  if (FileName.endswith_lower(".textpb") ||
2755      FileName.endswith_lower(".pb.txt") ||
2756      FileName.endswith_lower(".textproto") ||
2757      FileName.endswith_lower(".asciipb"))
2758    return FormatStyle::LK_TextProto;
2759  if (FileName.endswith_lower(".td"))
2760    return FormatStyle::LK_TableGen;
2761  if (FileName.endswith_lower(".cs"))
2762    return FormatStyle::LK_CSharp;
2763  return FormatStyle::LK_Cpp;
2764}
2765
2766FormatStyle::LanguageKind guessLanguage(StringRef FileName, StringRef Code) {
2767  const auto GuessedLanguage = getLanguageByFileName(FileName);
2768  if (GuessedLanguage == FormatStyle::LK_Cpp) {
2769    auto Extension = llvm::sys::path::extension(FileName);
2770    // If there's no file extension (or it's .h), we need to check the contents
2771    // of the code to see if it contains Objective-C.
2772    if (Extension.empty() || Extension == ".h") {
2773      auto NonEmptyFileName = FileName.empty() ? "guess.h" : FileName;
2774      Environment Env(Code, NonEmptyFileName, /*Ranges=*/{});
2775      ObjCHeaderStyleGuesser Guesser(Env, getLLVMStyle());
2776      Guesser.process();
2777      if (Guesser.isObjC())
2778        return FormatStyle::LK_ObjC;
2779    }
2780  }
2781  return GuessedLanguage;
2782}
2783
2784const char *DefaultFormatStyle = "file";
2785
2786const char *DefaultFallbackStyle = "LLVM";
2787
2788llvm::Expected<FormatStyle> getStyle(StringRef StyleName, StringRef FileName,
2789                                     StringRef FallbackStyleName,
2790                                     StringRef Code,
2791                                     llvm::vfs::FileSystem *FS) {
2792  if (!FS) {
2793    FS = llvm::vfs::getRealFileSystem().get();
2794  }
2795  FormatStyle Style = getLLVMStyle(guessLanguage(FileName, Code));
2796
2797  FormatStyle FallbackStyle = getNoStyle();
2798  if (!getPredefinedStyle(FallbackStyleName, Style.Language, &FallbackStyle))
2799    return make_string_error("Invalid fallback style \"" + FallbackStyleName);
2800
2801  if (StyleName.startswith("{")) {
2802    // Parse YAML/JSON style from the command line.
2803    if (std::error_code ec = parseConfiguration(StyleName, &Style))
2804      return make_string_error("Error parsing -style: " + ec.message());
2805    return Style;
2806  }
2807
2808  if (!StyleName.equals_lower("file")) {
2809    if (!getPredefinedStyle(StyleName, Style.Language, &Style))
2810      return make_string_error("Invalid value for -style");
2811    return Style;
2812  }
2813
2814  // Look for .clang-format/_clang-format file in the file's parent directories.
2815  SmallString<128> UnsuitableConfigFiles;
2816  SmallString<128> Path(FileName);
2817  if (std::error_code EC = FS->makeAbsolute(Path))
2818    return make_string_error(EC.message());
2819
2820  llvm::SmallVector<std::string, 2> FilesToLookFor;
2821  FilesToLookFor.push_back(".clang-format");
2822  FilesToLookFor.push_back("_clang-format");
2823
2824  for (StringRef Directory = Path; !Directory.empty();
2825       Directory = llvm::sys::path::parent_path(Directory)) {
2826
2827    auto Status = FS->status(Directory);
2828    if (!Status ||
2829        Status->getType() != llvm::sys::fs::file_type::directory_file) {
2830      continue;
2831    }
2832
2833    for (const auto &F : FilesToLookFor) {
2834      SmallString<128> ConfigFile(Directory);
2835
2836      llvm::sys::path::append(ConfigFile, F);
2837      LLVM_DEBUG(llvm::dbgs() << "Trying " << ConfigFile << "...\n");
2838
2839      Status = FS->status(ConfigFile.str());
2840
2841      if (Status &&
2842          (Status->getType() == llvm::sys::fs::file_type::regular_file)) {
2843        llvm::ErrorOr<std::unique_ptr<llvm::MemoryBuffer>> Text =
2844            FS->getBufferForFile(ConfigFile.str());
2845        if (std::error_code EC = Text.getError())
2846          return make_string_error(EC.message());
2847        if (std::error_code ec =
2848                parseConfiguration(Text.get()->getBuffer(), &Style)) {
2849          if (ec == ParseError::Unsuitable) {
2850            if (!UnsuitableConfigFiles.empty())
2851              UnsuitableConfigFiles.append(", ");
2852            UnsuitableConfigFiles.append(ConfigFile);
2853            continue;
2854          }
2855          return make_string_error("Error reading " + ConfigFile + ": " +
2856                                   ec.message());
2857        }
2858        LLVM_DEBUG(llvm::dbgs()
2859                   << "Using configuration file " << ConfigFile << "\n");
2860        return Style;
2861      }
2862    }
2863  }
2864  if (!UnsuitableConfigFiles.empty())
2865    return make_string_error("Configuration file(s) do(es) not support " +
2866                             getLanguageName(Style.Language) + ": " +
2867                             UnsuitableConfigFiles);
2868  return FallbackStyle;
2869}
2870
2871} // namespace format
2872} // namespace clang
2873