gn format: penalty-based line breaking WIP XXX

tools/gn/line_breaker.h

Index: tools/gn/line_breaker.h
diff --git a/tools/gn/line_breaker.h b/tools/gn/line_breaker.h
new file mode 100644
index 0000000000000000000000000000000000000000..f088b4ab3536b1e6f45e039d233b08d960251b59
--- /dev/null
+++ b/tools/gn/line_breaker.h
@@ -0,0 +1,114 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef TOOLS_GN_LINE_BREAKER_H_
+#define TOOLS_GN_LINE_BREAKER_H_
+
+#include <map>
+#include <string>
+#include <vector>
+
+#include "tools/gn/token.h"
+
+class ParseNode;
+
+namespace commands {
+
+enum { kIndentSize = 2 };
+enum { kMaximumWidth = 2 };
+
+enum Precedence {
+  kPrecedenceLowest,
+  kPrecedenceAssign,
+  kPrecedenceOr,
+  kPrecedenceAnd,
+  kPrecedenceCompare,
+  kPrecedenceAdd,
+  kPrecedenceSuffix,
+  kPrecedenceUnary,
+};
+
+// Gives the precedence for operators in a BinaryOpNode.
+Precedence GetPrecedence(const base::StringPiece op);
+
+class AnnotatedToken {
+ public:
+  enum Type {
+    UNDERLYING = Token::Type::NUM_TYPES,  // Nothing additional on top of the
+                                          // basic Token::Type;
+    LEFT_PAREN_FUNCTION_CALL,
+    LEFT_PAREN_GROUPING,
+    LEFT_BRACKET_LIST_LITERAL,
+    LEFT_BRACKET_ACCESSOR,
+  };
+
+  AnnotatedToken(const Token& token, Type type);
+  ~AnnotatedToken();
+
+  const base::StringPiece value() const { return token_.value(); }
+  Type type() const {
+    return type_ == UNDERLYING ? static_cast<Type>(token_.type()) : type_;
+  }
+
+ private:
+  Token token_;
+  Type type_;
+};
+
+std::vector<AnnotatedToken> BuildAnnotatedTokenList(const ParseNode* statement);
+
+// This takes a subset of the parse tree that is considered to be one
+// "statement-like" thing, as well as the column offset at which it must start.
+// This might be something like an assignment 'sources = ["x"]' or the condition
+// in an 'if' statement.
+//
+// The chunk is a flat list of tokens with extra information about what kind
+// they are (for example, distinguishing between the '(' to start a function
+// call, vs. a '(' in a parenthesized expression). If any line break is
+// necessary to fit, try a line break between each item, summing up a penalty
+// value depending on where it's broken. The set of line breaks with the lowest
+// penalty score is chosen.
+//
+// One wrinkle is that we can't just do an exhaustive search because there are
+// commonly very long statements in .gn files. For 'sources = ["0", "1", "2",
+// ... "999"]' there's ~2000 possible line breaks inside the list. Checking all
+// possible line breaks would be 2^2000 permutations, and ain't nobody got time
+// for that. However, the penalty for ([tokenN..end] laid out at column M) is a
+// cacheable value, which makes the problem tractable.
+class LineBreaker {
+ public:
+  LineBreaker(const std::vector<AnnotatedToken>& annotated_tokens,
+              int initial_column);
+  ~LineBreaker();
+
+  std::string GetBestLayout();
+
+ private:
+  struct LineState {
+    int column;
+    int next;
+  };
+  void Format(int index, int start_column);
+
+  int CalculatePenalty(LineState state, bool newline);
+  void AddTokenToState(bool newline, LineState* state);
+
+  struct CacheKey {
+    int token_index;  // The penalty is calculated from this token to the end of
+                      // the list.
+    int column;
+  };
+  typedef std::map<CacheKey, int> PenaltyCache;
+  PenaltyCache penalty_cache_;
+
+  const std::vector<AnnotatedToken>& annotated_tokens_;
+  int initial_column_;
+  int end_;
+
+  DISALLOW_COPY_AND_ASSIGN(LineBreaker);
+};
+
+}  // namespace commands
+
+#endif  // TOOLS_GN_LINE_BREAKER_H_