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