1 //===--- Format.cpp - Format C++ code -------------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
11 /// \brief This file implements functions declared in Format.h. This will be
12 /// split into separate files as we go.
14 //===----------------------------------------------------------------------===//
16 #define DEBUG_TYPE "format-formatter"
18 #include "ContinuationIndenter.h"
19 #include "TokenAnnotator.h"
20 #include "UnwrappedLineParser.h"
21 #include "WhitespaceManager.h"
22 #include "clang/Basic/Diagnostic.h"
23 #include "clang/Basic/SourceManager.h"
24 #include "clang/Format/Format.h"
25 #include "clang/Lex/Lexer.h"
26 #include "llvm/ADT/STLExtras.h"
27 #include "llvm/Support/Allocator.h"
28 #include "llvm/Support/Debug.h"
29 #include "llvm/Support/YAMLTraits.h"
30 #include "llvm/Support/Path.h"
37 struct ScalarEnumerationTraits<clang::format::FormatStyle::LanguageStandard> {
38 static void enumeration(IO &IO,
39 clang::format::FormatStyle::LanguageStandard &Value) {
40 IO.enumCase(Value, "Cpp03", clang::format::FormatStyle::LS_Cpp03);
41 IO.enumCase(Value, "C++03", clang::format::FormatStyle::LS_Cpp03);
42 IO.enumCase(Value, "Cpp11", clang::format::FormatStyle::LS_Cpp11);
43 IO.enumCase(Value, "C++11", clang::format::FormatStyle::LS_Cpp11);
44 IO.enumCase(Value, "Auto", clang::format::FormatStyle::LS_Auto);
49 struct ScalarEnumerationTraits<clang::format::FormatStyle::UseTabStyle> {
50 static void enumeration(IO &IO,
51 clang::format::FormatStyle::UseTabStyle &Value) {
52 IO.enumCase(Value, "Never", clang::format::FormatStyle::UT_Never);
53 IO.enumCase(Value, "false", clang::format::FormatStyle::UT_Never);
54 IO.enumCase(Value, "Always", clang::format::FormatStyle::UT_Always);
55 IO.enumCase(Value, "true", clang::format::FormatStyle::UT_Always);
56 IO.enumCase(Value, "ForIndentation",
57 clang::format::FormatStyle::UT_ForIndentation);
62 struct ScalarEnumerationTraits<clang::format::FormatStyle::BraceBreakingStyle> {
64 enumeration(IO &IO, clang::format::FormatStyle::BraceBreakingStyle &Value) {
65 IO.enumCase(Value, "Attach", clang::format::FormatStyle::BS_Attach);
66 IO.enumCase(Value, "Linux", clang::format::FormatStyle::BS_Linux);
67 IO.enumCase(Value, "Stroustrup", clang::format::FormatStyle::BS_Stroustrup);
68 IO.enumCase(Value, "Allman", clang::format::FormatStyle::BS_Allman);
73 struct ScalarEnumerationTraits<
74 clang::format::FormatStyle::NamespaceIndentationKind> {
77 clang::format::FormatStyle::NamespaceIndentationKind &Value) {
78 IO.enumCase(Value, "None", clang::format::FormatStyle::NI_None);
79 IO.enumCase(Value, "Inner", clang::format::FormatStyle::NI_Inner);
80 IO.enumCase(Value, "All", clang::format::FormatStyle::NI_All);
84 template <> struct MappingTraits<clang::format::FormatStyle> {
85 static void mapping(llvm::yaml::IO &IO, clang::format::FormatStyle &Style) {
86 if (IO.outputting()) {
87 StringRef StylesArray[] = { "LLVM", "Google", "Chromium",
88 "Mozilla", "WebKit" };
89 ArrayRef<StringRef> Styles(StylesArray);
90 for (size_t i = 0, e = Styles.size(); i < e; ++i) {
91 StringRef StyleName(Styles[i]);
92 clang::format::FormatStyle PredefinedStyle;
93 if (clang::format::getPredefinedStyle(StyleName, &PredefinedStyle) &&
94 Style == PredefinedStyle) {
95 IO.mapOptional("# BasedOnStyle", StyleName);
100 StringRef BasedOnStyle;
101 IO.mapOptional("BasedOnStyle", BasedOnStyle);
102 if (!BasedOnStyle.empty())
103 if (!clang::format::getPredefinedStyle(BasedOnStyle, &Style)) {
104 IO.setError(Twine("Unknown value for BasedOnStyle: ", BasedOnStyle));
109 IO.mapOptional("AccessModifierOffset", Style.AccessModifierOffset);
110 IO.mapOptional("ConstructorInitializerIndentWidth",
111 Style.ConstructorInitializerIndentWidth);
112 IO.mapOptional("AlignEscapedNewlinesLeft", Style.AlignEscapedNewlinesLeft);
113 IO.mapOptional("AlignTrailingComments", Style.AlignTrailingComments);
114 IO.mapOptional("AllowAllParametersOfDeclarationOnNextLine",
115 Style.AllowAllParametersOfDeclarationOnNextLine);
116 IO.mapOptional("AllowShortIfStatementsOnASingleLine",
117 Style.AllowShortIfStatementsOnASingleLine);
118 IO.mapOptional("AllowShortLoopsOnASingleLine",
119 Style.AllowShortLoopsOnASingleLine);
120 IO.mapOptional("AlwaysBreakTemplateDeclarations",
121 Style.AlwaysBreakTemplateDeclarations);
122 IO.mapOptional("AlwaysBreakBeforeMultilineStrings",
123 Style.AlwaysBreakBeforeMultilineStrings);
124 IO.mapOptional("BreakBeforeBinaryOperators",
125 Style.BreakBeforeBinaryOperators);
126 IO.mapOptional("BreakBeforeTernaryOperators",
127 Style.BreakBeforeTernaryOperators);
128 IO.mapOptional("BreakConstructorInitializersBeforeComma",
129 Style.BreakConstructorInitializersBeforeComma);
130 IO.mapOptional("BinPackParameters", Style.BinPackParameters);
131 IO.mapOptional("ColumnLimit", Style.ColumnLimit);
132 IO.mapOptional("ConstructorInitializerAllOnOneLineOrOnePerLine",
133 Style.ConstructorInitializerAllOnOneLineOrOnePerLine);
134 IO.mapOptional("DerivePointerBinding", Style.DerivePointerBinding);
135 IO.mapOptional("ExperimentalAutoDetectBinPacking",
136 Style.ExperimentalAutoDetectBinPacking);
137 IO.mapOptional("IndentCaseLabels", Style.IndentCaseLabels);
138 IO.mapOptional("MaxEmptyLinesToKeep", Style.MaxEmptyLinesToKeep);
139 IO.mapOptional("NamespaceIndentation", Style.NamespaceIndentation);
140 IO.mapOptional("ObjCSpaceBeforeProtocolList",
141 Style.ObjCSpaceBeforeProtocolList);
142 IO.mapOptional("PenaltyBreakBeforeFirstCallParameter",
143 Style.PenaltyBreakBeforeFirstCallParameter);
144 IO.mapOptional("PenaltyBreakComment", Style.PenaltyBreakComment);
145 IO.mapOptional("PenaltyBreakString", Style.PenaltyBreakString);
146 IO.mapOptional("PenaltyBreakFirstLessLess",
147 Style.PenaltyBreakFirstLessLess);
148 IO.mapOptional("PenaltyExcessCharacter", Style.PenaltyExcessCharacter);
149 IO.mapOptional("PenaltyReturnTypeOnItsOwnLine",
150 Style.PenaltyReturnTypeOnItsOwnLine);
151 IO.mapOptional("PointerBindsToType", Style.PointerBindsToType);
152 IO.mapOptional("SpacesBeforeTrailingComments",
153 Style.SpacesBeforeTrailingComments);
154 IO.mapOptional("Cpp11BracedListStyle", Style.Cpp11BracedListStyle);
155 IO.mapOptional("Standard", Style.Standard);
156 IO.mapOptional("IndentWidth", Style.IndentWidth);
157 IO.mapOptional("TabWidth", Style.TabWidth);
158 IO.mapOptional("UseTab", Style.UseTab);
159 IO.mapOptional("BreakBeforeBraces", Style.BreakBeforeBraces);
160 IO.mapOptional("IndentFunctionDeclarationAfterType",
161 Style.IndentFunctionDeclarationAfterType);
162 IO.mapOptional("SpacesInParentheses", Style.SpacesInParentheses);
163 IO.mapOptional("SpacesInAngles", Style.SpacesInAngles);
164 IO.mapOptional("SpaceInEmptyParentheses", Style.SpaceInEmptyParentheses);
165 IO.mapOptional("SpacesInCStyleCastParentheses",
166 Style.SpacesInCStyleCastParentheses);
167 IO.mapOptional("SpaceAfterControlStatementKeyword",
168 Style.SpaceAfterControlStatementKeyword);
169 IO.mapOptional("SpaceBeforeAssignmentOperators",
170 Style.SpaceBeforeAssignmentOperators);
171 IO.mapOptional("ContinuationIndentWidth", Style.ContinuationIndentWidth);
180 void setDefaultPenalties(FormatStyle &Style) {
181 Style.PenaltyBreakComment = 60;
182 Style.PenaltyBreakFirstLessLess = 120;
183 Style.PenaltyBreakString = 1000;
184 Style.PenaltyExcessCharacter = 1000000;
187 FormatStyle getLLVMStyle() {
188 FormatStyle LLVMStyle;
189 LLVMStyle.AccessModifierOffset = -2;
190 LLVMStyle.AlignEscapedNewlinesLeft = false;
191 LLVMStyle.AlignTrailingComments = true;
192 LLVMStyle.AllowAllParametersOfDeclarationOnNextLine = true;
193 LLVMStyle.AllowShortIfStatementsOnASingleLine = false;
194 LLVMStyle.AllowShortLoopsOnASingleLine = false;
195 LLVMStyle.AlwaysBreakBeforeMultilineStrings = false;
196 LLVMStyle.AlwaysBreakTemplateDeclarations = false;
197 LLVMStyle.BinPackParameters = true;
198 LLVMStyle.BreakBeforeBinaryOperators = false;
199 LLVMStyle.BreakBeforeTernaryOperators = true;
200 LLVMStyle.BreakBeforeBraces = FormatStyle::BS_Attach;
201 LLVMStyle.BreakConstructorInitializersBeforeComma = false;
202 LLVMStyle.ColumnLimit = 80;
203 LLVMStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = false;
204 LLVMStyle.ConstructorInitializerIndentWidth = 4;
205 LLVMStyle.Cpp11BracedListStyle = false;
206 LLVMStyle.DerivePointerBinding = false;
207 LLVMStyle.ExperimentalAutoDetectBinPacking = false;
208 LLVMStyle.IndentCaseLabels = false;
209 LLVMStyle.IndentFunctionDeclarationAfterType = false;
210 LLVMStyle.IndentWidth = 2;
211 LLVMStyle.TabWidth = 8;
212 LLVMStyle.MaxEmptyLinesToKeep = 1;
213 LLVMStyle.NamespaceIndentation = FormatStyle::NI_None;
214 LLVMStyle.ObjCSpaceBeforeProtocolList = true;
215 LLVMStyle.PointerBindsToType = false;
216 LLVMStyle.SpacesBeforeTrailingComments = 1;
217 LLVMStyle.Standard = FormatStyle::LS_Cpp03;
218 LLVMStyle.UseTab = FormatStyle::UT_Never;
219 LLVMStyle.SpacesInParentheses = false;
220 LLVMStyle.SpaceInEmptyParentheses = false;
221 LLVMStyle.SpacesInCStyleCastParentheses = false;
222 LLVMStyle.SpaceAfterControlStatementKeyword = true;
223 LLVMStyle.SpaceBeforeAssignmentOperators = true;
224 LLVMStyle.ContinuationIndentWidth = 4;
225 LLVMStyle.SpacesInAngles = false;
227 setDefaultPenalties(LLVMStyle);
228 LLVMStyle.PenaltyReturnTypeOnItsOwnLine = 60;
229 LLVMStyle.PenaltyBreakBeforeFirstCallParameter = 19;
234 FormatStyle getGoogleStyle() {
235 FormatStyle GoogleStyle;
236 GoogleStyle.AccessModifierOffset = -1;
237 GoogleStyle.AlignEscapedNewlinesLeft = true;
238 GoogleStyle.AlignTrailingComments = true;
239 GoogleStyle.AllowAllParametersOfDeclarationOnNextLine = true;
240 GoogleStyle.AllowShortIfStatementsOnASingleLine = true;
241 GoogleStyle.AllowShortLoopsOnASingleLine = true;
242 GoogleStyle.AlwaysBreakBeforeMultilineStrings = true;
243 GoogleStyle.AlwaysBreakTemplateDeclarations = true;
244 GoogleStyle.BinPackParameters = true;
245 GoogleStyle.BreakBeforeBinaryOperators = false;
246 GoogleStyle.BreakBeforeTernaryOperators = true;
247 GoogleStyle.BreakBeforeBraces = FormatStyle::BS_Attach;
248 GoogleStyle.BreakConstructorInitializersBeforeComma = false;
249 GoogleStyle.ColumnLimit = 80;
250 GoogleStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = true;
251 GoogleStyle.ConstructorInitializerIndentWidth = 4;
252 GoogleStyle.Cpp11BracedListStyle = true;
253 GoogleStyle.DerivePointerBinding = true;
254 GoogleStyle.ExperimentalAutoDetectBinPacking = false;
255 GoogleStyle.IndentCaseLabels = true;
256 GoogleStyle.IndentFunctionDeclarationAfterType = true;
257 GoogleStyle.IndentWidth = 2;
258 GoogleStyle.TabWidth = 8;
259 GoogleStyle.MaxEmptyLinesToKeep = 1;
260 GoogleStyle.NamespaceIndentation = FormatStyle::NI_None;
261 GoogleStyle.ObjCSpaceBeforeProtocolList = false;
262 GoogleStyle.PointerBindsToType = true;
263 GoogleStyle.SpacesBeforeTrailingComments = 2;
264 GoogleStyle.Standard = FormatStyle::LS_Auto;
265 GoogleStyle.UseTab = FormatStyle::UT_Never;
266 GoogleStyle.SpacesInParentheses = false;
267 GoogleStyle.SpaceInEmptyParentheses = false;
268 GoogleStyle.SpacesInCStyleCastParentheses = false;
269 GoogleStyle.SpaceAfterControlStatementKeyword = true;
270 GoogleStyle.SpaceBeforeAssignmentOperators = true;
271 GoogleStyle.ContinuationIndentWidth = 4;
272 GoogleStyle.SpacesInAngles = false;
274 setDefaultPenalties(GoogleStyle);
275 GoogleStyle.PenaltyReturnTypeOnItsOwnLine = 200;
276 GoogleStyle.PenaltyBreakBeforeFirstCallParameter = 1;
281 FormatStyle getChromiumStyle() {
282 FormatStyle ChromiumStyle = getGoogleStyle();
283 ChromiumStyle.AllowAllParametersOfDeclarationOnNextLine = false;
284 ChromiumStyle.AllowShortIfStatementsOnASingleLine = false;
285 ChromiumStyle.AllowShortLoopsOnASingleLine = false;
286 ChromiumStyle.BinPackParameters = false;
287 ChromiumStyle.DerivePointerBinding = false;
288 ChromiumStyle.Standard = FormatStyle::LS_Cpp03;
289 return ChromiumStyle;
292 FormatStyle getMozillaStyle() {
293 FormatStyle MozillaStyle = getLLVMStyle();
294 MozillaStyle.AllowAllParametersOfDeclarationOnNextLine = false;
295 MozillaStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = true;
296 MozillaStyle.DerivePointerBinding = true;
297 MozillaStyle.IndentCaseLabels = true;
298 MozillaStyle.ObjCSpaceBeforeProtocolList = false;
299 MozillaStyle.PenaltyReturnTypeOnItsOwnLine = 200;
300 MozillaStyle.PointerBindsToType = true;
304 FormatStyle getWebKitStyle() {
305 FormatStyle Style = getLLVMStyle();
306 Style.AccessModifierOffset = -4;
307 Style.AlignTrailingComments = false;
308 Style.BreakBeforeBinaryOperators = true;
309 Style.BreakBeforeBraces = FormatStyle::BS_Stroustrup;
310 Style.BreakConstructorInitializersBeforeComma = true;
311 Style.ColumnLimit = 0;
312 Style.IndentWidth = 4;
313 Style.NamespaceIndentation = FormatStyle::NI_Inner;
314 Style.PointerBindsToType = true;
318 bool getPredefinedStyle(StringRef Name, FormatStyle *Style) {
319 if (Name.equals_lower("llvm"))
320 *Style = getLLVMStyle();
321 else if (Name.equals_lower("chromium"))
322 *Style = getChromiumStyle();
323 else if (Name.equals_lower("mozilla"))
324 *Style = getMozillaStyle();
325 else if (Name.equals_lower("google"))
326 *Style = getGoogleStyle();
327 else if (Name.equals_lower("webkit"))
328 *Style = getWebKitStyle();
335 llvm::error_code parseConfiguration(StringRef Text, FormatStyle *Style) {
336 if (Text.trim().empty())
337 return llvm::make_error_code(llvm::errc::invalid_argument);
338 llvm::yaml::Input Input(Text);
340 return Input.error();
343 std::string configurationAsText(const FormatStyle &Style) {
345 llvm::raw_string_ostream Stream(Text);
346 llvm::yaml::Output Output(Stream);
347 // We use the same mapping method for input and output, so we need a non-const
349 FormatStyle NonConstStyle = Style;
350 Output << NonConstStyle;
356 class NoColumnLimitFormatter {
358 NoColumnLimitFormatter(ContinuationIndenter *Indenter) : Indenter(Indenter) {}
360 /// \brief Formats the line starting at \p State, simply keeping all of the
361 /// input's line breaking decisions.
362 void format(unsigned FirstIndent, const AnnotatedLine *Line) {
364 Indenter->getInitialState(FirstIndent, Line, /*DryRun=*/false);
365 while (State.NextToken != NULL) {
367 Indenter->mustBreak(State) ||
368 (Indenter->canBreak(State) && State.NextToken->NewlinesBefore > 0);
369 Indenter->addTokenToState(State, Newline, /*DryRun=*/false);
374 ContinuationIndenter *Indenter;
379 LineJoiner(const FormatStyle &Style) : Style(Style) {}
381 /// \brief Calculates how many lines can be merged into 1 starting at \p I.
383 tryFitMultipleLinesInOne(unsigned Indent,
384 SmallVectorImpl<AnnotatedLine *>::const_iterator &I,
385 SmallVectorImpl<AnnotatedLine *>::const_iterator E) {
386 // We can never merge stuff if there are trailing line comments.
387 AnnotatedLine *TheLine = *I;
388 if (TheLine->Last->Type == TT_LineComment)
391 if (Indent > Style.ColumnLimit)
395 Style.ColumnLimit == 0 ? UINT_MAX : Style.ColumnLimit - Indent;
396 // If we already exceed the column limit, we set 'Limit' to 0. The different
397 // tryMerge..() functions can then decide whether to still do merging.
398 Limit = TheLine->Last->TotalLength > Limit
400 : Limit - TheLine->Last->TotalLength;
402 if (I + 1 == E || I[1]->Type == LT_Invalid)
405 if (TheLine->Last->is(tok::l_brace)) {
406 return tryMergeSimpleBlock(I, E, Limit);
407 } else if (Style.AllowShortIfStatementsOnASingleLine &&
408 TheLine->First->is(tok::kw_if)) {
409 return tryMergeSimpleControlStatement(I, E, Limit);
410 } else if (Style.AllowShortLoopsOnASingleLine &&
411 TheLine->First->isOneOf(tok::kw_for, tok::kw_while)) {
412 return tryMergeSimpleControlStatement(I, E, Limit);
413 } else if (TheLine->InPPDirective && (TheLine->First->HasUnescapedNewline ||
414 TheLine->First->IsFirst)) {
415 return tryMergeSimplePPDirective(I, E, Limit);
422 tryMergeSimplePPDirective(SmallVectorImpl<AnnotatedLine *>::const_iterator &I,
423 SmallVectorImpl<AnnotatedLine *>::const_iterator E,
427 if (!I[1]->InPPDirective || I[1]->First->HasUnescapedNewline)
429 if (I + 2 != E && I[2]->InPPDirective && !I[2]->First->HasUnescapedNewline)
431 if (1 + I[1]->Last->TotalLength > Limit)
436 unsigned tryMergeSimpleControlStatement(
437 SmallVectorImpl<AnnotatedLine *>::const_iterator &I,
438 SmallVectorImpl<AnnotatedLine *>::const_iterator E, unsigned Limit) {
441 if (Style.BreakBeforeBraces == FormatStyle::BS_Allman &&
442 I[1]->First->is(tok::l_brace))
444 if (I[1]->InPPDirective != (*I)->InPPDirective ||
445 (I[1]->InPPDirective && I[1]->First->HasUnescapedNewline))
447 AnnotatedLine &Line = **I;
448 if (Line.Last->isNot(tok::r_paren))
450 if (1 + I[1]->Last->TotalLength > Limit)
452 if (I[1]->First->isOneOf(tok::semi, tok::kw_if, tok::kw_for,
454 I[1]->First->Type == TT_LineComment)
456 // Only inline simple if's (no nested if or else).
457 if (I + 2 != E && Line.First->is(tok::kw_if) &&
458 I[2]->First->is(tok::kw_else))
464 tryMergeSimpleBlock(SmallVectorImpl<AnnotatedLine *>::const_iterator &I,
465 SmallVectorImpl<AnnotatedLine *>::const_iterator E,
467 // No merging if the brace already is on the next line.
468 if (Style.BreakBeforeBraces != FormatStyle::BS_Attach)
471 // First, check that the current line allows merging. This is the case if
472 // we're not in a control flow statement and the last token is an opening
474 AnnotatedLine &Line = **I;
475 if (Line.First->isOneOf(tok::kw_if, tok::kw_while, tok::kw_do, tok::r_brace,
476 tok::kw_else, tok::kw_try, tok::kw_catch,
478 // This gets rid of all ObjC @ keywords and methods.
479 tok::at, tok::minus, tok::plus))
482 FormatToken *Tok = I[1]->First;
483 if (Tok->is(tok::r_brace) && !Tok->MustBreakBefore &&
484 (Tok->getNextNonComment() == NULL ||
485 Tok->getNextNonComment()->is(tok::semi))) {
486 // We merge empty blocks even if the line exceeds the column limit.
487 Tok->SpacesRequiredBefore = 0;
488 Tok->CanBreakBefore = true;
490 } else if (Limit != 0 && Line.First->isNot(tok::kw_namespace)) {
491 // Check that we still have three lines and they fit into the limit.
492 if (I + 2 == E || I[2]->Type == LT_Invalid)
495 if (!nextTwoLinesFitInto(I, Limit))
498 // Second, check that the next line does not contain any braces - if it
499 // does, readability declines when putting it into a single line.
500 if (I[1]->Last->Type == TT_LineComment || Tok->MustBreakBefore)
503 if (Tok->isOneOf(tok::l_brace, tok::r_brace))
506 } while (Tok != NULL);
508 // Last, check that the third line contains a single closing brace.
510 if (Tok->getNextNonComment() != NULL || Tok->isNot(tok::r_brace) ||
511 Tok->MustBreakBefore)
519 bool nextTwoLinesFitInto(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
521 return 1 + I[1]->Last->TotalLength + 1 + I[2]->Last->TotalLength <= Limit;
524 const FormatStyle &Style;
527 class UnwrappedLineFormatter {
529 UnwrappedLineFormatter(SourceManager &SourceMgr,
530 SmallVectorImpl<CharSourceRange> &Ranges,
531 ContinuationIndenter *Indenter,
532 WhitespaceManager *Whitespaces,
533 const FormatStyle &Style)
534 : SourceMgr(SourceMgr), Ranges(Ranges), Indenter(Indenter),
535 Whitespaces(Whitespaces), Style(Style), Joiner(Style) {}
537 unsigned format(const SmallVectorImpl<AnnotatedLine *> &Lines, bool DryRun,
538 int AdditionalIndent = 0) {
539 assert(!Lines.empty());
540 unsigned Penalty = 0;
541 std::vector<int> IndentForLevel;
542 for (unsigned i = 0, e = Lines[0]->Level; i != e; ++i)
543 IndentForLevel.push_back(Style.IndentWidth * i + AdditionalIndent);
544 bool PreviousLineWasTouched = false;
545 const AnnotatedLine *PreviousLine = NULL;
546 bool FormatPPDirective = false;
547 for (SmallVectorImpl<AnnotatedLine *>::const_iterator I = Lines.begin(),
550 const AnnotatedLine &TheLine = **I;
551 const FormatToken *FirstTok = TheLine.First;
552 int Offset = getIndentOffset(*FirstTok);
554 // Check whether this line is part of a formatted preprocessor directive.
555 if (FirstTok->HasUnescapedNewline)
556 FormatPPDirective = false;
557 if (!FormatPPDirective && TheLine.InPPDirective &&
558 (touchesLine(TheLine) || touchesPPDirective(I + 1, E)))
559 FormatPPDirective = true;
561 // Determine indent and try to merge multiple unwrapped lines.
562 while (IndentForLevel.size() <= TheLine.Level)
563 IndentForLevel.push_back(-1);
564 IndentForLevel.resize(TheLine.Level + 1);
565 unsigned Indent = getIndent(IndentForLevel, TheLine.Level);
566 if (static_cast<int>(Indent) + Offset >= 0)
568 unsigned MergedLines = Joiner.tryFitMultipleLinesInOne(Indent, I, E);
570 for (unsigned i = 0; i < MergedLines; ++i) {
571 join(*I[i], *I[i + 1]);
576 bool WasMoved = PreviousLineWasTouched && FirstTok->NewlinesBefore == 0;
577 if (TheLine.First->is(tok::eof)) {
578 if (PreviousLineWasTouched && !DryRun) {
579 unsigned Newlines = std::min(FirstTok->NewlinesBefore, 1u);
580 Whitespaces->replaceWhitespace(*TheLine.First, Newlines,
581 /*IndentLevel=*/0, /*Spaces=*/0,
584 } else if (TheLine.Type != LT_Invalid &&
585 (WasMoved || FormatPPDirective || touchesLine(TheLine))) {
586 unsigned LevelIndent =
587 getIndent(IndentForLevel, TheLine.Level);
588 if (FirstTok->WhitespaceRange.isValid()) {
590 formatFirstToken(*TheLine.First, PreviousLine, TheLine.Level,
591 Indent, TheLine.InPPDirective);
593 Indent = LevelIndent = FirstTok->OriginalColumn;
596 // If everything fits on a single line, just put it there.
597 unsigned ColumnLimit = Style.ColumnLimit;
599 AnnotatedLine *NextLine = I[1];
600 if (NextLine->InPPDirective && !NextLine->First->HasUnescapedNewline)
601 ColumnLimit = getColumnLimit(TheLine.InPPDirective);
604 if (TheLine.Last->TotalLength + Indent <= ColumnLimit) {
605 LineState State = Indenter->getInitialState(Indent, &TheLine, DryRun);
606 while (State.NextToken != NULL)
607 Indenter->addTokenToState(State, /*Newline=*/false, DryRun);
608 } else if (Style.ColumnLimit == 0) {
609 NoColumnLimitFormatter Formatter(Indenter);
611 Formatter.format(Indent, &TheLine);
613 Penalty += format(TheLine, Indent, DryRun);
616 IndentForLevel[TheLine.Level] = LevelIndent;
617 PreviousLineWasTouched = true;
619 // Format the first token if necessary, and notify the WhitespaceManager
620 // about the unchanged whitespace.
621 for (FormatToken *Tok = TheLine.First; Tok != NULL; Tok = Tok->Next) {
622 if (Tok == TheLine.First &&
623 (Tok->NewlinesBefore > 0 || Tok->IsFirst)) {
624 unsigned LevelIndent = Tok->OriginalColumn;
626 // Remove trailing whitespace of the previous line if it was
628 if (PreviousLineWasTouched || touchesEmptyLineBefore(TheLine)) {
629 formatFirstToken(*Tok, PreviousLine, TheLine.Level, LevelIndent,
630 TheLine.InPPDirective);
632 Whitespaces->addUntouchableToken(*Tok, TheLine.InPPDirective);
636 if (static_cast<int>(LevelIndent) - Offset >= 0)
637 LevelIndent -= Offset;
638 if (Tok->isNot(tok::comment))
639 IndentForLevel[TheLine.Level] = LevelIndent;
640 } else if (!DryRun) {
641 Whitespaces->addUntouchableToken(*Tok, TheLine.InPPDirective);
644 // If we did not reformat this unwrapped line, the column at the end of
645 // the last token is unchanged - thus, we can calculate the end of the
647 PreviousLineWasTouched = false;
650 for (FormatToken *Tok = TheLine.First; Tok != NULL; Tok = Tok->Next) {
651 Tok->Finalized = true;
660 /// \brief Formats an \c AnnotatedLine and returns the penalty.
662 /// If \p DryRun is \c false, directly applies the changes.
663 unsigned format(const AnnotatedLine &Line, unsigned FirstIndent,
665 LineState State = Indenter->getInitialState(FirstIndent, &Line, DryRun);
667 // If the ObjC method declaration does not fit on a line, we should format
668 // it with one arg per line.
669 if (State.Line->Type == LT_ObjCMethodDecl)
670 State.Stack.back().BreakBeforeParameter = true;
672 // Find best solution in solution space.
673 return analyzeSolutionSpace(State, DryRun);
676 /// \brief An edge in the solution space from \c Previous->State to \c State,
677 /// inserting a newline dependent on the \c NewLine.
679 StateNode(const LineState &State, bool NewLine, StateNode *Previous)
680 : State(State), NewLine(NewLine), Previous(Previous) {}
686 /// \brief A pair of <penalty, count> that is used to prioritize the BFS on.
688 /// In case of equal penalties, we want to prefer states that were inserted
689 /// first. During state generation we make sure that we insert states first
690 /// that break the line as late as possible.
691 typedef std::pair<unsigned, unsigned> OrderedPenalty;
693 /// \brief An item in the prioritized BFS search queue. The \c StateNode's
694 /// \c State has the given \c OrderedPenalty.
695 typedef std::pair<OrderedPenalty, StateNode *> QueueItem;
697 /// \brief The BFS queue type.
698 typedef std::priority_queue<QueueItem, std::vector<QueueItem>,
699 std::greater<QueueItem> > QueueType;
701 /// \brief Get the offset of the line relatively to the level.
703 /// For example, 'public:' labels in classes are offset by 1 or 2
704 /// characters to the left from their level.
705 int getIndentOffset(const FormatToken &RootToken) {
706 if (RootToken.isAccessSpecifier(false) || RootToken.isObjCAccessSpecifier())
707 return Style.AccessModifierOffset;
711 /// \brief Add a new line and the required indent before the first Token
712 /// of the \c UnwrappedLine if there was no structural parsing error.
713 void formatFirstToken(FormatToken &RootToken,
714 const AnnotatedLine *PreviousLine, unsigned IndentLevel,
715 unsigned Indent, bool InPPDirective) {
717 std::min(RootToken.NewlinesBefore, Style.MaxEmptyLinesToKeep + 1);
718 // Remove empty lines before "}" where applicable.
719 if (RootToken.is(tok::r_brace) &&
721 (RootToken.Next->is(tok::semi) && !RootToken.Next->Next)))
722 Newlines = std::min(Newlines, 1u);
723 if (Newlines == 0 && !RootToken.IsFirst)
726 // Insert extra new line before access specifiers.
727 if (PreviousLine && PreviousLine->Last->isOneOf(tok::semi, tok::r_brace) &&
728 RootToken.isAccessSpecifier() && RootToken.NewlinesBefore == 1)
731 // Remove empty lines after access specifiers.
732 if (PreviousLine && PreviousLine->First->isAccessSpecifier())
733 Newlines = std::min(1u, Newlines);
735 Whitespaces->replaceWhitespace(
736 RootToken, Newlines, IndentLevel, Indent, Indent,
737 InPPDirective && !RootToken.HasUnescapedNewline);
740 /// \brief Get the indent of \p Level from \p IndentForLevel.
742 /// \p IndentForLevel must contain the indent for the level \c l
743 /// at \p IndentForLevel[l], or a value < 0 if the indent for
744 /// that level is unknown.
745 unsigned getIndent(const std::vector<int> IndentForLevel, unsigned Level) {
746 if (IndentForLevel[Level] != -1)
747 return IndentForLevel[Level];
750 return getIndent(IndentForLevel, Level - 1) + Style.IndentWidth;
753 void join(AnnotatedLine &A, const AnnotatedLine &B) {
754 assert(!A.Last->Next);
755 assert(!B.First->Previous);
756 A.Last->Next = B.First;
757 B.First->Previous = A.Last;
758 B.First->CanBreakBefore = true;
759 unsigned LengthA = A.Last->TotalLength + B.First->SpacesRequiredBefore;
760 for (FormatToken *Tok = B.First; Tok; Tok = Tok->Next) {
761 Tok->TotalLength += LengthA;
766 unsigned getColumnLimit(bool InPPDirective) const {
767 // In preprocessor directives reserve two chars for trailing " \"
768 return Style.ColumnLimit - (InPPDirective ? 2 : 0);
771 bool touchesRanges(const CharSourceRange &Range) {
772 for (SmallVectorImpl<CharSourceRange>::const_iterator I = Ranges.begin(),
775 if (!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(), I->getBegin()) &&
776 !SourceMgr.isBeforeInTranslationUnit(I->getEnd(), Range.getBegin()))
782 bool touchesLine(const AnnotatedLine &TheLine) {
783 const FormatToken *First = TheLine.First;
784 const FormatToken *Last = TheLine.Last;
785 CharSourceRange LineRange = CharSourceRange::getCharRange(
786 First->WhitespaceRange.getBegin().getLocWithOffset(
787 First->LastNewlineOffset),
788 Last->getStartOfNonWhitespace().getLocWithOffset(
789 Last->TokenText.size() - 1));
790 return touchesRanges(LineRange);
793 bool touchesPPDirective(SmallVectorImpl<AnnotatedLine *>::const_iterator I,
794 SmallVectorImpl<AnnotatedLine *>::const_iterator E) {
795 for (; I != E; ++I) {
796 if ((*I)->First->HasUnescapedNewline)
798 if (touchesLine(**I))
804 bool touchesEmptyLineBefore(const AnnotatedLine &TheLine) {
805 const FormatToken *First = TheLine.First;
806 CharSourceRange LineRange = CharSourceRange::getCharRange(
807 First->WhitespaceRange.getBegin(),
808 First->WhitespaceRange.getBegin().getLocWithOffset(
809 First->LastNewlineOffset));
810 return touchesRanges(LineRange);
813 /// \brief Analyze the entire solution space starting from \p InitialState.
815 /// This implements a variant of Dijkstra's algorithm on the graph that spans
816 /// the solution space (\c LineStates are the nodes). The algorithm tries to
817 /// find the shortest path (the one with lowest penalty) from \p InitialState
818 /// to a state where all tokens are placed. Returns the penalty.
820 /// If \p DryRun is \c false, directly applies the changes.
821 unsigned analyzeSolutionSpace(LineState &InitialState, bool DryRun = false) {
822 std::set<LineState> Seen;
824 // Increasing count of \c StateNode items we have created. This is used to
825 // create a deterministic order independent of the container.
829 // Insert start element into queue.
831 new (Allocator.Allocate()) StateNode(InitialState, false, NULL);
832 Queue.push(QueueItem(OrderedPenalty(0, Count), Node));
835 unsigned Penalty = 0;
837 // While not empty, take first element and follow edges.
838 while (!Queue.empty()) {
839 Penalty = Queue.top().first.first;
840 StateNode *Node = Queue.top().second;
841 if (Node->State.NextToken == NULL) {
842 DEBUG(llvm::dbgs() << "\n---\nPenalty for line: " << Penalty << "\n");
847 // Cut off the analysis of certain solutions if the analysis gets too
848 // complex. See description of IgnoreStackForComparison.
850 Node->State.IgnoreStackForComparison = true;
852 if (!Seen.insert(Node->State).second)
853 // State already examined with lower penalty.
856 FormatDecision LastFormat = Node->State.NextToken->Decision;
857 if (LastFormat == FD_Unformatted || LastFormat == FD_Continue)
858 addNextStateToQueue(Penalty, Node, /*NewLine=*/false, &Count, &Queue);
859 if (LastFormat == FD_Unformatted || LastFormat == FD_Break)
860 addNextStateToQueue(Penalty, Node, /*NewLine=*/true, &Count, &Queue);
864 // We were unable to find a solution, do nothing.
865 // FIXME: Add diagnostic?
866 DEBUG(llvm::dbgs() << "Could not find a solution.\n");
870 // Reconstruct the solution.
872 reconstructPath(InitialState, Queue.top().second);
874 DEBUG(llvm::dbgs() << "Total number of analyzed states: " << Count << "\n");
875 DEBUG(llvm::dbgs() << "---\n");
880 void reconstructPath(LineState &State, StateNode *Current) {
881 std::deque<StateNode *> Path;
882 // We do not need a break before the initial token.
883 while (Current->Previous) {
884 Path.push_front(Current);
885 Current = Current->Previous;
887 for (std::deque<StateNode *>::iterator I = Path.begin(), E = Path.end();
889 unsigned Penalty = 0;
890 formatChildren(State, (*I)->NewLine, /*DryRun=*/false, Penalty);
891 Penalty += Indenter->addTokenToState(State, (*I)->NewLine, false);
895 llvm::dbgs() << "Penalty for placing "
896 << (*I)->Previous->State.NextToken->Tok.getName() << ": "
903 /// \brief Add the following state to the analysis queue \c Queue.
905 /// Assume the current state is \p PreviousNode and has been reached with a
906 /// penalty of \p Penalty. Insert a line break if \p NewLine is \c true.
907 void addNextStateToQueue(unsigned Penalty, StateNode *PreviousNode,
908 bool NewLine, unsigned *Count, QueueType *Queue) {
909 if (NewLine && !Indenter->canBreak(PreviousNode->State))
911 if (!NewLine && Indenter->mustBreak(PreviousNode->State))
914 StateNode *Node = new (Allocator.Allocate())
915 StateNode(PreviousNode->State, NewLine, PreviousNode);
916 if (!formatChildren(Node->State, NewLine, /*DryRun=*/true, Penalty))
919 Penalty += Indenter->addTokenToState(Node->State, NewLine, true);
921 Queue->push(QueueItem(OrderedPenalty(Penalty, *Count), Node));
925 /// \brief If the \p State's next token is an r_brace closing a nested block,
926 /// format the nested block before it.
928 /// Returns \c true if all children could be placed successfully and adapts
929 /// \p Penalty as well as \p State. If \p DryRun is false, also directly
930 /// creates changes using \c Whitespaces.
932 /// The crucial idea here is that children always get formatted upon
933 /// encountering the closing brace right after the nested block. Now, if we
934 /// are currently trying to keep the "}" on the same line (i.e. \p NewLine is
935 /// \c false), the entire block has to be kept on the same line (which is only
936 /// possible if it fits on the line, only contains a single statement, etc.
938 /// If \p NewLine is true, we format the nested block on separate lines, i.e.
939 /// break after the "{", format all lines with correct indentation and the put
940 /// the closing "}" on yet another new line.
942 /// This enables us to keep the simple structure of the
943 /// \c UnwrappedLineFormatter, where we only have two options for each token:
944 /// break or don't break.
945 bool formatChildren(LineState &State, bool NewLine, bool DryRun,
947 FormatToken &Previous = *State.NextToken->Previous;
948 const FormatToken *LBrace = State.NextToken->getPreviousNonComment();
949 if (!LBrace || LBrace->isNot(tok::l_brace) ||
950 LBrace->BlockKind != BK_Block || Previous.Children.size() == 0)
951 // The previous token does not open a block. Nothing to do. We don't
952 // assert so that we can simply call this function for all tokens.
956 int AdditionalIndent = State.Stack.back().Indent -
957 Previous.Children[0]->Level * Style.IndentWidth;
958 Penalty += format(Previous.Children, DryRun, AdditionalIndent);
962 // Cannot merge multiple statements into a single line.
963 if (Previous.Children.size() > 1)
966 // We can't put the closing "}" on a line with a trailing comment.
967 if (Previous.Children[0]->Last->isTrailingComment())
971 Whitespaces->replaceWhitespace(
972 *Previous.Children[0]->First,
973 /*Newlines=*/0, /*IndentLevel=*/0, /*Spaces=*/1,
974 /*StartOfTokenColumn=*/State.Column, State.Line->InPPDirective);
976 Penalty += format(*Previous.Children[0], State.Column + 1, DryRun);
978 State.Column += 1 + Previous.Children[0]->Last->TotalLength;
982 SourceManager &SourceMgr;
983 SmallVectorImpl<CharSourceRange> &Ranges;
984 ContinuationIndenter *Indenter;
985 WhitespaceManager *Whitespaces;
989 llvm::SpecificBumpPtrAllocator<StateNode> Allocator;
992 class FormatTokenLexer {
994 FormatTokenLexer(Lexer &Lex, SourceManager &SourceMgr, FormatStyle &Style,
995 encoding::Encoding Encoding)
996 : FormatTok(NULL), IsFirstToken(true), GreaterStashed(false), Column(0),
997 TrailingWhitespace(0), Lex(Lex), SourceMgr(SourceMgr), Style(Style),
998 IdentTable(getFormattingLangOpts()), Encoding(Encoding) {
999 Lex.SetKeepWhitespaceMode(true);
1002 ArrayRef<FormatToken *> lex() {
1003 assert(Tokens.empty());
1005 Tokens.push_back(getNextToken());
1006 maybeJoinPreviousTokens();
1007 } while (Tokens.back()->Tok.isNot(tok::eof));
1011 IdentifierTable &getIdentTable() { return IdentTable; }
1014 void maybeJoinPreviousTokens() {
1015 if (Tokens.size() < 4)
1017 FormatToken *Last = Tokens.back();
1018 if (!Last->is(tok::r_paren))
1021 FormatToken *String = Tokens[Tokens.size() - 2];
1022 if (!String->is(tok::string_literal) || String->IsMultiline)
1025 if (!Tokens[Tokens.size() - 3]->is(tok::l_paren))
1028 FormatToken *Macro = Tokens[Tokens.size() - 4];
1029 if (Macro->TokenText != "_T")
1032 const char *Start = Macro->TokenText.data();
1033 const char *End = Last->TokenText.data() + Last->TokenText.size();
1034 String->TokenText = StringRef(Start, End - Start);
1035 String->IsFirst = Macro->IsFirst;
1036 String->LastNewlineOffset = Macro->LastNewlineOffset;
1037 String->WhitespaceRange = Macro->WhitespaceRange;
1038 String->OriginalColumn = Macro->OriginalColumn;
1039 String->ColumnWidth = encoding::columnWidthWithTabs(
1040 String->TokenText, String->OriginalColumn, Style.TabWidth, Encoding);
1045 Tokens.back() = String;
1048 FormatToken *getNextToken() {
1049 if (GreaterStashed) {
1050 // Create a synthesized second '>' token.
1051 // FIXME: Increment Column and set OriginalColumn.
1052 Token Greater = FormatTok->Tok;
1053 FormatTok = new (Allocator.Allocate()) FormatToken;
1054 FormatTok->Tok = Greater;
1055 SourceLocation GreaterLocation =
1056 FormatTok->Tok.getLocation().getLocWithOffset(1);
1057 FormatTok->WhitespaceRange =
1058 SourceRange(GreaterLocation, GreaterLocation);
1059 FormatTok->TokenText = ">";
1060 FormatTok->ColumnWidth = 1;
1061 GreaterStashed = false;
1065 FormatTok = new (Allocator.Allocate()) FormatToken;
1066 readRawToken(*FormatTok);
1067 SourceLocation WhitespaceStart =
1068 FormatTok->Tok.getLocation().getLocWithOffset(-TrailingWhitespace);
1069 FormatTok->IsFirst = IsFirstToken;
1070 IsFirstToken = false;
1072 // Consume and record whitespace until we find a significant token.
1073 unsigned WhitespaceLength = TrailingWhitespace;
1074 while (FormatTok->Tok.is(tok::unknown)) {
1075 for (int i = 0, e = FormatTok->TokenText.size(); i != e; ++i) {
1076 switch (FormatTok->TokenText[i]) {
1078 ++FormatTok->NewlinesBefore;
1079 // FIXME: This is technically incorrect, as it could also
1080 // be a literal backslash at the end of the line.
1081 if (i == 0 || (FormatTok->TokenText[i - 1] != '\\' &&
1082 (FormatTok->TokenText[i - 1] != '\r' || i == 1 ||
1083 FormatTok->TokenText[i - 2] != '\\')))
1084 FormatTok->HasUnescapedNewline = true;
1085 FormatTok->LastNewlineOffset = WhitespaceLength + i + 1;
1097 Column += Style.TabWidth - Column % Style.TabWidth;
1101 if (i + 1 == e || (FormatTok->TokenText[i + 1] != '\r' &&
1102 FormatTok->TokenText[i + 1] != '\n'))
1103 FormatTok->Type = TT_ImplicitStringLiteral;
1106 FormatTok->Type = TT_ImplicitStringLiteral;
1112 if (FormatTok->Type == TT_ImplicitStringLiteral)
1114 WhitespaceLength += FormatTok->Tok.getLength();
1116 readRawToken(*FormatTok);
1119 // In case the token starts with escaped newlines, we want to
1120 // take them into account as whitespace - this pattern is quite frequent
1121 // in macro definitions.
1122 // FIXME: Add a more explicit test.
1123 while (FormatTok->TokenText.size() > 1 && FormatTok->TokenText[0] == '\\' &&
1124 FormatTok->TokenText[1] == '\n') {
1125 // FIXME: ++FormatTok->NewlinesBefore is missing...
1126 WhitespaceLength += 2;
1128 FormatTok->TokenText = FormatTok->TokenText.substr(2);
1131 FormatTok->WhitespaceRange = SourceRange(
1132 WhitespaceStart, WhitespaceStart.getLocWithOffset(WhitespaceLength));
1134 FormatTok->OriginalColumn = Column;
1136 TrailingWhitespace = 0;
1137 if (FormatTok->Tok.is(tok::comment)) {
1138 // FIXME: Add the trimmed whitespace to Column.
1139 StringRef UntrimmedText = FormatTok->TokenText;
1140 FormatTok->TokenText = FormatTok->TokenText.rtrim(" \t\v\f");
1141 TrailingWhitespace = UntrimmedText.size() - FormatTok->TokenText.size();
1142 } else if (FormatTok->Tok.is(tok::raw_identifier)) {
1143 IdentifierInfo &Info = IdentTable.get(FormatTok->TokenText);
1144 FormatTok->Tok.setIdentifierInfo(&Info);
1145 FormatTok->Tok.setKind(Info.getTokenID());
1146 } else if (FormatTok->Tok.is(tok::greatergreater)) {
1147 FormatTok->Tok.setKind(tok::greater);
1148 FormatTok->TokenText = FormatTok->TokenText.substr(0, 1);
1149 GreaterStashed = true;
1152 // Now FormatTok is the next non-whitespace token.
1154 StringRef Text = FormatTok->TokenText;
1155 size_t FirstNewlinePos = Text.find('\n');
1156 if (FirstNewlinePos == StringRef::npos) {
1157 // FIXME: ColumnWidth actually depends on the start column, we need to
1158 // take this into account when the token is moved.
1159 FormatTok->ColumnWidth =
1160 encoding::columnWidthWithTabs(Text, Column, Style.TabWidth, Encoding);
1161 Column += FormatTok->ColumnWidth;
1163 FormatTok->IsMultiline = true;
1164 // FIXME: ColumnWidth actually depends on the start column, we need to
1165 // take this into account when the token is moved.
1166 FormatTok->ColumnWidth = encoding::columnWidthWithTabs(
1167 Text.substr(0, FirstNewlinePos), Column, Style.TabWidth, Encoding);
1169 // The last line of the token always starts in column 0.
1170 // Thus, the length can be precomputed even in the presence of tabs.
1171 FormatTok->LastLineColumnWidth = encoding::columnWidthWithTabs(
1172 Text.substr(Text.find_last_of('\n') + 1), 0, Style.TabWidth,
1174 Column = FormatTok->LastLineColumnWidth;
1180 FormatToken *FormatTok;
1182 bool GreaterStashed;
1184 unsigned TrailingWhitespace;
1186 SourceManager &SourceMgr;
1188 IdentifierTable IdentTable;
1189 encoding::Encoding Encoding;
1190 llvm::SpecificBumpPtrAllocator<FormatToken> Allocator;
1191 SmallVector<FormatToken *, 16> Tokens;
1193 void readRawToken(FormatToken &Tok) {
1194 Lex.LexFromRawLexer(Tok.Tok);
1195 Tok.TokenText = StringRef(SourceMgr.getCharacterData(Tok.Tok.getLocation()),
1196 Tok.Tok.getLength());
1197 // For formatting, treat unterminated string literals like normal string
1199 if (Tok.is(tok::unknown) && !Tok.TokenText.empty() &&
1200 Tok.TokenText[0] == '"') {
1201 Tok.Tok.setKind(tok::string_literal);
1202 Tok.IsUnterminatedLiteral = true;
1207 class Formatter : public UnwrappedLineConsumer {
1209 Formatter(const FormatStyle &Style, Lexer &Lex, SourceManager &SourceMgr,
1210 const std::vector<CharSourceRange> &Ranges)
1211 : Style(Style), Lex(Lex), SourceMgr(SourceMgr),
1212 Whitespaces(SourceMgr, Style, inputUsesCRLF(Lex.getBuffer())),
1213 Ranges(Ranges.begin(), Ranges.end()), UnwrappedLines(1),
1214 Encoding(encoding::detectEncoding(Lex.getBuffer())) {
1215 DEBUG(llvm::dbgs() << "File encoding: "
1216 << (Encoding == encoding::Encoding_UTF8 ? "UTF8"
1221 tooling::Replacements format() {
1222 tooling::Replacements Result;
1223 FormatTokenLexer Tokens(Lex, SourceMgr, Style, Encoding);
1225 UnwrappedLineParser Parser(Style, Tokens.lex(), *this);
1226 bool StructuralError = Parser.parse();
1227 assert(UnwrappedLines.rbegin()->empty());
1228 for (unsigned Run = 0, RunE = UnwrappedLines.size(); Run + 1 != RunE;
1230 DEBUG(llvm::dbgs() << "Run " << Run << "...\n");
1231 SmallVector<AnnotatedLine *, 16> AnnotatedLines;
1232 for (unsigned i = 0, e = UnwrappedLines[Run].size(); i != e; ++i) {
1233 AnnotatedLines.push_back(new AnnotatedLine(UnwrappedLines[Run][i]));
1235 tooling::Replacements RunResult =
1236 format(AnnotatedLines, StructuralError, Tokens);
1238 llvm::dbgs() << "Replacements for run " << Run << ":\n";
1239 for (tooling::Replacements::iterator I = RunResult.begin(),
1240 E = RunResult.end();
1242 llvm::dbgs() << I->toString() << "\n";
1245 for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1246 delete AnnotatedLines[i];
1248 Result.insert(RunResult.begin(), RunResult.end());
1249 Whitespaces.reset();
1254 tooling::Replacements format(SmallVectorImpl<AnnotatedLine *> &AnnotatedLines,
1255 bool StructuralError, FormatTokenLexer &Tokens) {
1256 TokenAnnotator Annotator(Style, Tokens.getIdentTable().get("in"));
1257 for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1258 Annotator.annotate(*AnnotatedLines[i]);
1260 deriveLocalStyle(AnnotatedLines);
1261 for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1262 Annotator.calculateFormattingInformation(*AnnotatedLines[i]);
1265 Annotator.setCommentLineLevels(AnnotatedLines);
1266 ContinuationIndenter Indenter(Style, SourceMgr, Whitespaces, Encoding,
1267 BinPackInconclusiveFunctions);
1268 UnwrappedLineFormatter Formatter(SourceMgr, Ranges, &Indenter, &Whitespaces,
1270 Formatter.format(AnnotatedLines, /*DryRun=*/false);
1271 return Whitespaces.generateReplacements();
1275 static bool inputUsesCRLF(StringRef Text) {
1276 return Text.count('\r') * 2 > Text.count('\n');
1280 deriveLocalStyle(const SmallVectorImpl<AnnotatedLine *> &AnnotatedLines) {
1281 unsigned CountBoundToVariable = 0;
1282 unsigned CountBoundToType = 0;
1283 bool HasCpp03IncompatibleFormat = false;
1284 bool HasBinPackedFunction = false;
1285 bool HasOnePerLineFunction = false;
1286 for (unsigned i = 0, e = AnnotatedLines.size(); i != e; ++i) {
1287 if (!AnnotatedLines[i]->First->Next)
1289 FormatToken *Tok = AnnotatedLines[i]->First->Next;
1291 if (Tok->Type == TT_PointerOrReference) {
1293 Tok->WhitespaceRange.getBegin() != Tok->WhitespaceRange.getEnd();
1294 bool SpacesAfter = Tok->Next->WhitespaceRange.getBegin() !=
1295 Tok->Next->WhitespaceRange.getEnd();
1296 if (SpacesBefore && !SpacesAfter)
1297 ++CountBoundToVariable;
1298 else if (!SpacesBefore && SpacesAfter)
1302 if (Tok->WhitespaceRange.getBegin() == Tok->WhitespaceRange.getEnd()) {
1303 if (Tok->is(tok::coloncolon) &&
1304 Tok->Previous->Type == TT_TemplateOpener)
1305 HasCpp03IncompatibleFormat = true;
1306 if (Tok->Type == TT_TemplateCloser &&
1307 Tok->Previous->Type == TT_TemplateCloser)
1308 HasCpp03IncompatibleFormat = true;
1311 if (Tok->PackingKind == PPK_BinPacked)
1312 HasBinPackedFunction = true;
1313 if (Tok->PackingKind == PPK_OnePerLine)
1314 HasOnePerLineFunction = true;
1319 if (Style.DerivePointerBinding) {
1320 if (CountBoundToType > CountBoundToVariable)
1321 Style.PointerBindsToType = true;
1322 else if (CountBoundToType < CountBoundToVariable)
1323 Style.PointerBindsToType = false;
1325 if (Style.Standard == FormatStyle::LS_Auto) {
1326 Style.Standard = HasCpp03IncompatibleFormat ? FormatStyle::LS_Cpp11
1327 : FormatStyle::LS_Cpp03;
1329 BinPackInconclusiveFunctions =
1330 HasBinPackedFunction || !HasOnePerLineFunction;
1333 virtual void consumeUnwrappedLine(const UnwrappedLine &TheLine) {
1334 assert(!UnwrappedLines.empty());
1335 UnwrappedLines.back().push_back(TheLine);
1338 virtual void finishRun() {
1339 UnwrappedLines.push_back(SmallVector<UnwrappedLine, 16>());
1344 SourceManager &SourceMgr;
1345 WhitespaceManager Whitespaces;
1346 SmallVector<CharSourceRange, 8> Ranges;
1347 SmallVector<SmallVector<UnwrappedLine, 16>, 2> UnwrappedLines;
1349 encoding::Encoding Encoding;
1350 bool BinPackInconclusiveFunctions;
1353 } // end anonymous namespace
1355 tooling::Replacements reformat(const FormatStyle &Style, Lexer &Lex,
1356 SourceManager &SourceMgr,
1357 std::vector<CharSourceRange> Ranges) {
1358 Formatter formatter(Style, Lex, SourceMgr, Ranges);
1359 return formatter.format();
1362 tooling::Replacements reformat(const FormatStyle &Style, StringRef Code,
1363 std::vector<tooling::Range> Ranges,
1364 StringRef FileName) {
1365 FileManager Files((FileSystemOptions()));
1366 DiagnosticsEngine Diagnostics(
1367 IntrusiveRefCntPtr<DiagnosticIDs>(new DiagnosticIDs),
1368 new DiagnosticOptions);
1369 SourceManager SourceMgr(Diagnostics, Files);
1370 llvm::MemoryBuffer *Buf = llvm::MemoryBuffer::getMemBuffer(Code, FileName);
1371 const clang::FileEntry *Entry =
1372 Files.getVirtualFile(FileName, Buf->getBufferSize(), 0);
1373 SourceMgr.overrideFileContents(Entry, Buf);
1375 SourceMgr.createFileID(Entry, SourceLocation(), clang::SrcMgr::C_User);
1376 Lexer Lex(ID, SourceMgr.getBuffer(ID), SourceMgr,
1377 getFormattingLangOpts(Style.Standard));
1378 SourceLocation StartOfFile = SourceMgr.getLocForStartOfFile(ID);
1379 std::vector<CharSourceRange> CharRanges;
1380 for (unsigned i = 0, e = Ranges.size(); i != e; ++i) {
1381 SourceLocation Start = StartOfFile.getLocWithOffset(Ranges[i].getOffset());
1382 SourceLocation End = Start.getLocWithOffset(Ranges[i].getLength());
1383 CharRanges.push_back(CharSourceRange::getCharRange(Start, End));
1385 return reformat(Style, Lex, SourceMgr, CharRanges);
1388 LangOptions getFormattingLangOpts(FormatStyle::LanguageStandard Standard) {
1389 LangOptions LangOpts;
1390 LangOpts.CPlusPlus = 1;
1391 LangOpts.CPlusPlus11 = Standard == FormatStyle::LS_Cpp03 ? 0 : 1;
1392 LangOpts.LineComment = 1;
1399 const char *StyleOptionHelpDescription =
1400 "Coding style, currently supports:\n"
1401 " LLVM, Google, Chromium, Mozilla, WebKit.\n"
1402 "Use -style=file to load style configuration from\n"
1403 ".clang-format file located in one of the parent\n"
1404 "directories of the source file (or current\n"
1405 "directory for stdin).\n"
1406 "Use -style=\"{key: value, ...}\" to set specific\n"
1407 "parameters, e.g.:\n"
1408 " -style=\"{BasedOnStyle: llvm, IndentWidth: 8}\"";
1410 FormatStyle getStyle(StringRef StyleName, StringRef FileName) {
1411 // Fallback style in case the rest of this function can't determine a style.
1412 StringRef FallbackStyle = "LLVM";
1414 getPredefinedStyle(FallbackStyle, &Style);
1416 if (StyleName.startswith("{")) {
1417 // Parse YAML/JSON style from the command line.
1418 if (llvm::error_code ec = parseConfiguration(StyleName, &Style)) {
1419 llvm::errs() << "Error parsing -style: " << ec.message() << ", using "
1420 << FallbackStyle << " style\n";
1425 if (!StyleName.equals_lower("file")) {
1426 if (!getPredefinedStyle(StyleName, &Style))
1427 llvm::errs() << "Invalid value for -style, using " << FallbackStyle
1432 SmallString<128> Path(FileName);
1433 llvm::sys::fs::make_absolute(Path);
1434 for (StringRef Directory = Path; !Directory.empty();
1435 Directory = llvm::sys::path::parent_path(Directory)) {
1436 if (!llvm::sys::fs::is_directory(Directory))
1438 SmallString<128> ConfigFile(Directory);
1440 llvm::sys::path::append(ConfigFile, ".clang-format");
1441 DEBUG(llvm::dbgs() << "Trying " << ConfigFile << "...\n");
1442 bool IsFile = false;
1443 // Ignore errors from is_regular_file: we only need to know if we can read
1445 llvm::sys::fs::is_regular_file(Twine(ConfigFile), IsFile);
1448 // Try _clang-format too, since dotfiles are not commonly used on Windows.
1449 ConfigFile = Directory;
1450 llvm::sys::path::append(ConfigFile, "_clang-format");
1451 DEBUG(llvm::dbgs() << "Trying " << ConfigFile << "...\n");
1452 llvm::sys::fs::is_regular_file(Twine(ConfigFile), IsFile);
1456 OwningPtr<llvm::MemoryBuffer> Text;
1457 if (llvm::error_code ec =
1458 llvm::MemoryBuffer::getFile(ConfigFile.c_str(), Text)) {
1459 llvm::errs() << ec.message() << "\n";
1462 if (llvm::error_code ec = parseConfiguration(Text->getBuffer(), &Style)) {
1463 llvm::errs() << "Error reading " << ConfigFile << ": " << ec.message()
1467 DEBUG(llvm::dbgs() << "Using configuration file " << ConfigFile << "\n");
1471 llvm::errs() << "Can't find usable .clang-format, using " << FallbackStyle
1476 } // namespace format
1477 } // namespace clang