contrib/llvm/tools/clang/lib/Format/UnwrappedLineFormatter.h

   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       : 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 {
  51     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.
  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
 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 {
 106     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