1 //===--- UnwrappedLineFormatter.h - Format C++ code -------------*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 /// 10 /// \file 11 /// \brief Implements a combinartorial exploration of all the different 12 /// linebreaks unwrapped lines can be formatted in. 13 /// 14 //===----------------------------------------------------------------------===// 15 16 #ifndef LLVM_CLANG_LIB_FORMAT_UNWRAPPEDLINEFORMATTER_H 17 #define LLVM_CLANG_LIB_FORMAT_UNWRAPPEDLINEFORMATTER_H 18 19 #include "ContinuationIndenter.h" 20 #include "clang/Format/Format.h" 21 #include <map> 22 #include <queue> 23 #include <string> 24 25 namespace clang { 26 namespace format { 27 28 class ContinuationIndenter; 29 class WhitespaceManager; 30 31 class UnwrappedLineFormatter { 32 public: UnwrappedLineFormatter(ContinuationIndenter * Indenter,WhitespaceManager * Whitespaces,const FormatStyle & Style)33 UnwrappedLineFormatter(ContinuationIndenter *Indenter, 34 WhitespaceManager *Whitespaces, 35 const FormatStyle &Style) 36 : Indenter(Indenter), Whitespaces(Whitespaces), Style(Style) {} 37 38 unsigned format(const SmallVectorImpl<AnnotatedLine *> &Lines, bool DryRun, 39 int AdditionalIndent = 0, bool FixBadIndentation = false); 40 41 private: 42 /// \brief Formats an \c AnnotatedLine and returns the penalty. 43 /// 44 /// If \p DryRun is \c false, directly applies the changes. 45 unsigned format(const AnnotatedLine &Line, unsigned FirstIndent, 46 bool DryRun); 47 48 /// \brief An edge in the solution space from \c Previous->State to \c State, 49 /// inserting a newline dependent on the \c NewLine. 50 struct StateNode { StateNodeStateNode51 StateNode(const LineState &State, bool NewLine, StateNode *Previous) 52 : State(State), NewLine(NewLine), Previous(Previous) {} 53 LineState State; 54 bool NewLine; 55 StateNode *Previous; 56 }; 57 58 /// \brief A pair of <penalty, count> that is used to prioritize the BFS on. 59 /// 60 /// In case of equal penalties, we want to prefer states that were inserted 61 /// first. During state generation we make sure that we insert states first 62 /// that break the line as late as possible. 63 typedef std::pair<unsigned, unsigned> OrderedPenalty; 64 65 /// \brief An item in the prioritized BFS search queue. The \c StateNode's 66 /// \c State has the given \c OrderedPenalty. 67 typedef std::pair<OrderedPenalty, StateNode *> QueueItem; 68 69 /// \brief The BFS queue type. 70 typedef std::priority_queue<QueueItem, std::vector<QueueItem>, 71 std::greater<QueueItem> > QueueType; 72 73 /// \brief Get the offset of the line relatively to the level. 74 /// 75 /// For example, 'public:' labels in classes are offset by 1 or 2 76 /// characters to the left from their level. getIndentOffset(const FormatToken & RootToken)77 int getIndentOffset(const FormatToken &RootToken) { 78 if (Style.Language == FormatStyle::LK_Java) 79 return 0; 80 if (RootToken.isAccessSpecifier(false) || RootToken.isObjCAccessSpecifier()) 81 return Style.AccessModifierOffset; 82 return 0; 83 } 84 85 /// \brief Add a new line and the required indent before the first Token 86 /// of the \c UnwrappedLine if there was no structural parsing error. 87 void formatFirstToken(FormatToken &RootToken, 88 const AnnotatedLine *PreviousLine, unsigned IndentLevel, 89 unsigned Indent, bool InPPDirective); 90 91 /// \brief Get the indent of \p Level from \p IndentForLevel. 92 /// 93 /// \p IndentForLevel must contain the indent for the level \c l 94 /// at \p IndentForLevel[l], or a value < 0 if the indent for 95 /// that level is unknown. 96 unsigned getIndent(ArrayRef<int> IndentForLevel, unsigned Level); 97 98 void join(AnnotatedLine &A, const AnnotatedLine &B); 99 getColumnLimit(bool InPPDirective)100 unsigned getColumnLimit(bool InPPDirective) const { 101 // In preprocessor directives reserve two chars for trailing " \" 102 return Style.ColumnLimit - (InPPDirective ? 2 : 0); 103 } 104 105 struct CompareLineStatePointers { operatorCompareLineStatePointers106 bool operator()(LineState *obj1, LineState *obj2) const { 107 return *obj1 < *obj2; 108 } 109 }; 110 111 /// \brief Analyze the entire solution space starting from \p InitialState. 112 /// 113 /// This implements a variant of Dijkstra's algorithm on the graph that spans 114 /// the solution space (\c LineStates are the nodes). The algorithm tries to 115 /// find the shortest path (the one with lowest penalty) from \p InitialState 116 /// to a state where all tokens are placed. Returns the penalty. 117 /// 118 /// If \p DryRun is \c false, directly applies the changes. 119 unsigned analyzeSolutionSpace(LineState &InitialState, bool DryRun = false); 120 121 void reconstructPath(LineState &State, StateNode *Current); 122 123 /// \brief Add the following state to the analysis queue \c Queue. 124 /// 125 /// Assume the current state is \p PreviousNode and has been reached with a 126 /// penalty of \p Penalty. Insert a line break if \p NewLine is \c true. 127 void addNextStateToQueue(unsigned Penalty, StateNode *PreviousNode, 128 bool NewLine, unsigned *Count, QueueType *Queue); 129 130 /// \brief If the \p State's next token is an r_brace closing a nested block, 131 /// format the nested block before it. 132 /// 133 /// Returns \c true if all children could be placed successfully and adapts 134 /// \p Penalty as well as \p State. If \p DryRun is false, also directly 135 /// creates changes using \c Whitespaces. 136 /// 137 /// The crucial idea here is that children always get formatted upon 138 /// encountering the closing brace right after the nested block. Now, if we 139 /// are currently trying to keep the "}" on the same line (i.e. \p NewLine is 140 /// \c false), the entire block has to be kept on the same line (which is only 141 /// possible if it fits on the line, only contains a single statement, etc. 142 /// 143 /// If \p NewLine is true, we format the nested block on separate lines, i.e. 144 /// break after the "{", format all lines with correct indentation and the put 145 /// the closing "}" on yet another new line. 146 /// 147 /// This enables us to keep the simple structure of the 148 /// \c UnwrappedLineFormatter, where we only have two options for each token: 149 /// break or don't break. 150 bool formatChildren(LineState &State, bool NewLine, bool DryRun, 151 unsigned &Penalty); 152 153 ContinuationIndenter *Indenter; 154 WhitespaceManager *Whitespaces; 155 FormatStyle Style; 156 157 llvm::SpecificBumpPtrAllocator<StateNode> Allocator; 158 159 // Cache to store the penalty of formatting a vector of AnnotatedLines 160 // starting from a specific additional offset. Improves performance if there 161 // are many nested blocks. 162 std::map<std::pair<const SmallVectorImpl<AnnotatedLine *> *, unsigned>, 163 unsigned> PenaltyCache; 164 }; 165 } // end namespace format 166 } // end namespace clang 167 168 #endif // LLVM_CLANG_LIB_FORMAT_UNWRAPPEDLINEFORMATTER_H 169