Format code around VCS conflict markers.

[djasper]

Looks good.

lib/Format/Format.cpp

1268

s/offset/Offset/

Also, offset of what? Consider adding a comment or using a more specific name.

1272

"LineOffset" carries very little meaning, or at least I can't understand what it means without carefully looking at the code. Maybe add a comment.

1285

..Size is not a good name for a bool. Here and below. Just remove "Size"?

1307–1309

I think a comment here would help what an expected conflict line together with the generated tokens would look like. Possibly here or at the start of the function.

1392

I liked this empty line.

1473

Just to make this even clearer:

// Index (in 'Tokens') of the last token that starts a new line.

lib/Format/FormatToken.h

70

While this order makes sense, I think we should keep this alphabetical.

lib/Format/UnwrappedLineParser.cpp

475

I think "Unreachable" needs some explanation...

1418–1431

This would be just 6 lines with if () ..

unittests/Format/FormatTest.cpp

15

Remove?

[klimek]

Applied review comments.

[djasper]

Still looks good.

lib/Format/UnwrappedLineParser.h

111–114

According to this comment, 'unreachable' does not seem like quite the right word. May "Active" or "ProcessBranch"?

[klimek]

(sending comments I had forgotten to send earlier...)

lib/Format/Format.cpp

1268

Done.

1272

Done.

1285

Changed to parse out the start of the line until the first whitespace and use that.

1307–1309

Done, hopefully...

1392

Done.

1473

Done.

lib/Format/FormatToken.h

70

Done.

lib/Format/UnwrappedLineParser.cpp

475

I think that generally the names are bad. I should rename them, but not in this CL. Added a comment that hopefully helps a bit.

1418–1431

Done.

unittests/Format/FormatTest.cpp

15

Done.

[klimek]

lib/Format/UnwrappedLineParser.h

111–114

Fully agreed - in a follow-up CL.

lib/Format/Format.cpp

 };
 
 class FormatTokenLexer {
 public:
   FormatTokenLexer(Lexer &Lex, SourceManager &SourceMgr, FormatStyle &Style,
                    encoding::Encoding Encoding)
       : FormatTok(NULL), IsFirstToken(true), GreaterStashed(false), Column(0),
         TrailingWhitespace(0), Lex(Lex), SourceMgr(SourceMgr), Style(Style),
-        IdentTable(getFormattingLangOpts()), Encoding(Encoding) {
+        IdentTable(getFormattingLangOpts()), Encoding(Encoding),
+        FirstInLineIndex(0) {
     Lex.SetKeepWhitespaceMode(true);
 
     for (const std::string& ForEachMacro : Style.ForEachMacros)
       ForEachMacros.push_back(&IdentTable.get(ForEachMacro));
     std::sort(ForEachMacros.begin(), ForEachMacros.end());
   }
 
   ArrayRef<FormatToken *> lex() {
     assert(Tokens.empty());
+    assert(FirstInLineIndex == 0);
     do {
       Tokens.push_back(getNextToken());
       tryMergePreviousTokens();
+      if (Tokens.back()->NewlinesBefore > 0)
+        FirstInLineIndex = Tokens.size() - 1;
     } while (Tokens.back()->Tok.isNot(tok::eof));
     return Tokens;
   }
 
   IdentifierTable &getIdentTable() { return IdentTable; }
 
 private:
   void tryMergePreviousTokens() {
     if (tryMerge_TMacro())
       return;
+    if (tryMergeConflictMarkers())
+      return;
 
     if (Style.Language == FormatStyle::LK_JavaScript) {
       static tok::TokenKind JSIdentity[] = { tok::equalequal, tok::equal };
       static tok::TokenKind JSNotIdentity[] = { tok::exclaimequal, tok::equal };
       static tok::TokenKind JSShiftEqual[] = { tok::greater, tok::greater,
                                                tok::greaterequal };
       // FIXME: We probably need to change token type to mimic operator with the
       // correct priority.
bool tryMerge_TMacro() {
 
     Tokens.pop_back();
     Tokens.pop_back();
     Tokens.pop_back();
     Tokens.back() = String;
     return true;
   }
 
+  bool tryMergeConflictMarkers() {
+    if (Tokens.back()->NewlinesBefore == 0 && Tokens.back()->isNot(tok::eof))
+      return false;
+
+    // Conflict lines look like:
+    // <marker> <text from the vcs>
+    // For example:
+    // >>>>>>> /file/in/file/system at revision 1234
+    //
+    // We merge all tokens in a line that starts with a conflict marker
+    // into a single token with a special token type that the unwrapped line
+    // parser will use to correctly rebuild the underlying code.
+
+    FileID ID;
+    // Get the position of the first token in the line.
+    unsigned FirstInLineOffset;
+    std::tie(ID, FirstInLineOffset) = SourceMgr.getDecomposedLoc(
+        Tokens[FirstInLineIndex]->getStartOfNonWhitespace());
+    StringRef Buffer = SourceMgr.getBuffer(ID)->getBuffer();
+    // Calculate the offset of the start of the current line.
+    auto LineOffset = Buffer.rfind('\n', FirstInLineOffset);
+    if (LineOffset == StringRef::npos) {
+      LineOffset = 0;
+    } else {
+      ++LineOffset;
+    }
+
+    auto FirstSpace = Buffer.find_first_of(" \n", LineOffset);
+    StringRef LineStart;
+    if (FirstSpace == StringRef::npos) {
+      LineStart = Buffer.substr(LineOffset);
+    } else {
+      LineStart = Buffer.substr(LineOffset, FirstSpace - LineOffset);
+    }
+
+    TokenType Type = TT_Unknown;
+    if (LineStart == "<<<<<<<" || LineStart == ">>>>") {
+      Type = TT_ConflictStart;
+    } else if (LineStart == "|||||||" || LineStart == "=======" ||
+               LineStart == "====") {
+      Type = TT_ConflictAlternative;
+    } else if (LineStart == ">>>>>>>" || LineStart == "<<<<") {
+      Type = TT_ConflictEnd;
+    }
+
+    if (Type != TT_Unknown) {
+      FormatToken *Next = Tokens.back();
+
+      Tokens.resize(FirstInLineIndex + 1);
+      // We do not need to build a complete token here, as we will skip it
+      // during parsing anyway (as we must not touch whitespace around conflict
+      // markers).
+      Tokens.back()->Type = Type;
+      Tokens.back()->Tok.setKind(tok::kw___unknown_anytype);
+
+      Tokens.push_back(Next);
+      return true;
+    }
+
+    return false;
+  }
+
   FormatToken *getNextToken() {
     if (GreaterStashed) {
       // Create a synthesized second '>' token.
       // FIXME: Increment Column and set OriginalColumn.
       Token Greater = FormatTok->Tok;
       FormatTok = new (Allocator.Allocate()) FormatToken;
       FormatTok->Tok = Greater;
       SourceLocation GreaterLocation =
FormatToken *getNextToken() {
     }
 
     FormatTok->IsForEachMacro =
         std::binary_search(ForEachMacros.begin(), ForEachMacros.end(),
                            FormatTok->Tok.getIdentifierInfo());
 
     return FormatTok;
   }
 
   FormatToken *FormatTok;
   bool IsFirstToken;
   bool GreaterStashed;
   unsigned Column;
   unsigned TrailingWhitespace;
   Lexer &Lex;
   SourceManager &SourceMgr;
   FormatStyle &Style;
   IdentifierTable IdentTable;
   encoding::Encoding Encoding;
   llvm::SpecificBumpPtrAllocator<FormatToken> Allocator;
+  // Index (in 'Tokens') of the last token that starts a new line.
+  unsigned FirstInLineIndex;
   SmallVector<FormatToken *, 16> Tokens;
   SmallVector<IdentifierInfo*, 8> ForEachMacros;
 
   void readRawToken(FormatToken &Tok) {
     Lex.LexFromRawLexer(Tok.Tok);
     Tok.TokenText = StringRef(SourceMgr.getCharacterData(Tok.Tok.getLocation()),
                               Tok.Tok.getLength());
     // For formatting, treat unterminated string literals like normal string

lib/Format/FormatToken.h

enum TokenType {
   TT_ArrayInitializerLSquare,
   TT_ArraySubscriptLSquare,
   TT_AttributeParen,
   TT_BinaryOperator,
   TT_BitFieldColon,
   TT_BlockComment,
   TT_CastRParen,
   TT_ConditionalExpr,
+  TT_ConflictAlternative,
+  TT_ConflictEnd,
+  TT_ConflictStart,
   TT_CtorInitializerColon,
   TT_CtorInitializerComma,
   TT_DesignatedInitializerPeriod,
   TT_DictLiteral,
-  TT_ImplicitStringLiteral,
-  TT_InlineASMColon,
-  TT_InheritanceColon,
   TT_FunctionLBrace,
   TT_FunctionTypeLParen,
+  TT_ImplicitStringLiteral,
+  TT_InheritanceColon,
+  TT_InlineASMColon,
   TT_LambdaLSquare,
   TT_LineComment,
-  TT_ObjCBlockLParen,
   TT_ObjCBlockLBrace,
+  TT_ObjCBlockLParen,
   TT_ObjCDecl,
   TT_ObjCForIn,
   TT_ObjCMethodExpr,
   TT_ObjCMethodSpecifier,
   TT_ObjCProperty,
   TT_ObjCSelectorName,
   TT_OverloadedOperator,
   TT_OverloadedOperatorLParen,
   TT_PointerOrReference,
   TT_PureVirtualSpecifier,
   TT_RangeBasedForLoopColon,
   TT_StartOfName,
   TT_TemplateCloser,
   TT_TemplateOpener,
   TT_TrailingAnnotation,
   TT_TrailingReturnArrow,
   TT_TrailingUnaryOperator,
   TT_UnaryOperator,
   TT_Unknown
 };
 
 // Represents what type of block a set of braces open.
 enum BraceBlockKind {
   BK_Unknown,
   BK_Block,
   BK_BracedInit
 };

lib/Format/UnwrappedLineParser.h

private:
   bool tryToParseLambdaIntroducer();
   void addUnwrappedLine();
   bool eof() const;
   void nextToken();
   void readToken();
   void flushComments(bool NewlineBeforeNext);
   void pushToken(FormatToken *Tok);
   void calculateBraceTypes();
-  void pushPPConditional();
+
+  // Marks a conditional compilation edge (for example, an '#if', '#ifdef',
+  // '#else' or merge conflict marker). If 'Unreachable' is true, assumes
+  // this branch either cannot be taken (for example '#if false'), or should
+  // not be taken in this round.
+  void conditionalCompilationCondition(bool Unreachable);
+  void conditionalCompilationStart(bool Unreachable);
+  void conditionalCompilationAlternative();
+  void conditionalCompilationEnd();
+
   bool isOnNewLine(const FormatToken& FormatTok);
 
   // FIXME: We are constantly running into bugs where Line.Level is incorrectly
   // subtracted from beyond 0. Introduce a method to subtract from Line.Level
   // and use that everywhere in the Parser.
   std::unique_ptr<UnwrappedLine> Line;
 
   // Comments are sorted into unwrapped lines by whether they are in the same

lib/Format/UnwrappedLineParser.cpp

case tok::pp_endif:
     parsePPEndIf();
     break;
   default:
     parsePPUnknown();
     break;
   }
 }
 
-void UnwrappedLineParser::pushPPConditional() {
-  if (!PPStack.empty() && PPStack.back() == PP_Unreachable)
+void UnwrappedLineParser::conditionalCompilationCondition(bool Unreachable) {
+  if (Unreachable || (!PPStack.empty() && PPStack.back() == PP_Unreachable))
     PPStack.push_back(PP_Unreachable);
   else
     PPStack.push_back(PP_Conditional);
 }
 
-void UnwrappedLineParser::parsePPIf(bool IfDef) {
+void UnwrappedLineParser::conditionalCompilationStart(bool Unreachable) {
   ++PPBranchLevel;
   assert(PPBranchLevel >= 0 && PPBranchLevel <= (int)PPLevelBranchIndex.size());
   if (PPBranchLevel == (int)PPLevelBranchIndex.size()) {
     PPLevelBranchIndex.push_back(0);
     PPLevelBranchCount.push_back(0);
   }
   PPChainBranchIndex.push(0);
-  nextToken();
-  bool IsLiteralFalse = (FormatTok->Tok.isLiteral() &&
-                         StringRef(FormatTok->Tok.getLiteralData(),
-                                   FormatTok->Tok.getLength()) == "0") ||
-                        FormatTok->Tok.is(tok::kw_false);
-  if ((!IfDef && IsLiteralFalse) || PPLevelBranchIndex[PPBranchLevel] > 0) {
-    PPStack.push_back(PP_Unreachable);
-  } else {
-    pushPPConditional();
-  }
-  parsePPUnknown();
+  bool Skip = PPLevelBranchIndex[PPBranchLevel] > 0;
+  conditionalCompilationCondition(Unreachable || Skip);
 }
 
-void UnwrappedLineParser::parsePPElse() {
+void UnwrappedLineParser::conditionalCompilationAlternative() {
   if (!PPStack.empty())
     PPStack.pop_back();
   assert(PPBranchLevel < (int)PPLevelBranchIndex.size());
   if (!PPChainBranchIndex.empty())
     ++PPChainBranchIndex.top();
-  if (PPBranchLevel >= 0 && !PPChainBranchIndex.empty() &&
-      PPLevelBranchIndex[PPBranchLevel] != PPChainBranchIndex.top()) {
-    PPStack.push_back(PP_Unreachable);
-  } else {
-    pushPPConditional();
-  }
-  parsePPUnknown();
+  conditionalCompilationCondition(
+      PPBranchLevel >= 0 && !PPChainBranchIndex.empty() &&
+      PPLevelBranchIndex[PPBranchLevel] != PPChainBranchIndex.top());
 }
 
-void UnwrappedLineParser::parsePPElIf() { parsePPElse(); }
-
-void UnwrappedLineParser::parsePPEndIf() {
+void UnwrappedLineParser::conditionalCompilationEnd() {
   assert(PPBranchLevel < (int)PPLevelBranchIndex.size());
   if (PPBranchLevel >= 0 && !PPChainBranchIndex.empty()) {
     if (PPChainBranchIndex.top() + 1 > PPLevelBranchCount[PPBranchLevel]) {
       PPLevelBranchCount[PPBranchLevel] = PPChainBranchIndex.top() + 1;
     }
   }
   // Guard against #endif's without #if.
   if (PPBranchLevel > 0)
     --PPBranchLevel;
   if (!PPChainBranchIndex.empty())
     PPChainBranchIndex.pop();
   if (!PPStack.empty())
     PPStack.pop_back();
+}
+
+void UnwrappedLineParser::parsePPIf(bool IfDef) {
+  nextToken();
+  bool IsLiteralFalse = (FormatTok->Tok.isLiteral() &&
+                         StringRef(FormatTok->Tok.getLiteralData(),
+                                   FormatTok->Tok.getLength()) == "0") ||
+                        FormatTok->Tok.is(tok::kw_false);
+  conditionalCompilationStart(!IfDef && IsLiteralFalse);
+  parsePPUnknown();
+}
+
+void UnwrappedLineParser::parsePPElse() {
+  conditionalCompilationAlternative();
+  parsePPUnknown();
+}
+
+void UnwrappedLineParser::parsePPElIf() { parsePPElse(); }
+
+void UnwrappedLineParser::parsePPEndIf() {
+  conditionalCompilationEnd();
   parsePPUnknown();
 }
 
 void UnwrappedLineParser::parsePPDefine() {
   nextToken();
 
   if (FormatTok->Tok.getKind() != tok::identifier) {
     parsePPUnknown();
while (!Line->InPPDirective && FormatTok->Tok.is(tok::hash) &&
           !Line->Tokens.empty() && CurrentLines == &Lines;
       ScopedLineState BlockState(*this, SwitchToPreprocessorLines);
       // Comments stored before the preprocessor directive need to be output
       // before the preprocessor directive, at the same level as the
       // preprocessor directive, as we consider them to apply to the directive.
       flushComments(isOnNewLine(*FormatTok));
       parsePPDirective();
     }
+    while (FormatTok->Type == TT_ConflictStart ||
+           FormatTok->Type == TT_ConflictEnd ||
+           FormatTok->Type == TT_ConflictAlternative) {
+      if (FormatTok->Type == TT_ConflictStart) {
+        conditionalCompilationStart(/*Unreachable=*/false);
+      } else if (FormatTok->Type == TT_ConflictAlternative) {
+        conditionalCompilationAlternative();
+      } else if(FormatTok->Type == TT_ConflictEnd) {
+        conditionalCompilationEnd();
+      }
+      FormatTok = Tokens->getNextToken();
+      FormatTok->MustBreakBefore = true;
+    }
 
     if (!PPStack.empty() && (PPStack.back() == PP_Unreachable) &&
         !Line->InPPDirective) {
       continue;
     }
 
     if (!FormatTok->Tok.is(tok::comment))
       return;
     if (isOnNewLine(*FormatTok) || FormatTok->IsFirst) {
       CommentsInCurrentLine = false;
     }
     if (CommentsInCurrentLine) {

unittests/Format/FormatTest.cpp

 //===- unittest/Format/FormatTest.cpp - Formatting unit tests -------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #define DEBUG_TYPE "format-test"
 
 #include "FormatTestUtils.h"
 #include "clang/Format/Format.h"
 #include "llvm/Support/Debug.h"
 #include "gtest/gtest.h"
 
 namespace clang {
 namespace format {
 
 FormatStyle getGoogleStyle() {
   return getGoogleStyle(FormatStyle::LK_Cpp);
 }