gn format: penalty-based line breaking WIP XXX

tools/gn/line_breaker.cc

Index: tools/gn/line_breaker.cc
diff --git a/tools/gn/line_breaker.cc b/tools/gn/line_breaker.cc
new file mode 100644
index 0000000000000000000000000000000000000000..a3015fe26ebed570257b971c159a78efab4d098a
--- /dev/null
+++ b/tools/gn/line_breaker.cc
@@ -0,0 +1,204 @@
+// 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.
+
+#include "tools/gn/line_breaker.h"
+
+#include "tools/gn/parse_tree.h"
+
+namespace commands {
+
+const int kExcessCharacterPenalty = 1000000;
+
+Precedence GetPrecedence(const base::StringPiece op) {
+  if (op == "=" || op == "+=" || op == "-=")
+    return kPrecedenceAssign;
+  if (op == "||")
+    return kPrecedenceOr;
+  if (op == "&&")
+    return kPrecedenceAnd;
+  if (op == "<" || op == ">" || op == "==" || op == "!=" || op == "<=" ||
+      op == ">=") {
+    return kPrecedenceCompare;
+  }
+  if (op == "+" || op == "-")
+    return kPrecedenceAdd;
+  if (op == "!")
+    return kPrecedenceUnary;
+  DCHECK(false);
+  return kPrecedenceLowest;
+}
+
+AnnotatedToken::AnnotatedToken(const Token& token, Type type)
+    : token_(token), type_(type) {
+}
+
+AnnotatedToken::~AnnotatedToken() {
+}
+
+void AddParen(int prec,
+              int outer_prec,
+              bool* parenthesized,
+              std::vector<AnnotatedToken>* result) {
+  if (prec < outer_prec) {
+    result->push_back(AnnotatedToken(Token(Location(), Token::LEFT_PAREN, "("),
+                                     AnnotatedToken::LEFT_PAREN_GROUPING));
+    *parenthesized = true;
+  }
+}
+
+void FlattenUntilNextChunk(const ParseNode* root,
+                           int outer_prec,
+                           std::vector<AnnotatedToken>* result) {
+  if (root) {
+    bool parenthesized = false;
+    if (const AccessorNode* accessor = root->AsAccessor()) {
+      AddParen(kPrecedenceSuffix, outer_prec, &parenthesized, result);
+      if (accessor->member()) {
+        result->push_back(AnnotatedToken(Token(Location(), Token::DOT, "."),
+                                         AnnotatedToken::UNDERLYING));
+        FlattenUntilNextChunk(accessor->member(), kPrecedenceLowest, result);
+      } else {
+        result->push_back(
+            AnnotatedToken(Token(Location(), Token::LEFT_BRACKET, "["),
+                           AnnotatedToken::LEFT_BRACKET_ACCESSOR));
+        FlattenUntilNextChunk(accessor->index(), kPrecedenceLowest, result);
+        result->push_back(
+            AnnotatedToken(Token(Location(), Token::RIGHT_BRACKET, "]"),
+                           AnnotatedToken::UNDERLYING));
+      }
+    } else if (const BinaryOpNode* binop = root->AsBinaryOp()) {
+      Precedence prec = GetPrecedence(binop->op().value());
+      AddParen(prec, outer_prec, &parenthesized, result);
+      FlattenUntilNextChunk(binop->left(), prec, result);
+      result->push_back(
+          AnnotatedToken(binop->op(), AnnotatedToken::UNDERLYING));
+      FlattenUntilNextChunk(binop->right(), prec + 1, result);
+    } else if (const BlockNode* block = root->AsBlock()) {
+      if (block->begin_token().type() != Token::INVALID) {
+        result->push_back(
+            AnnotatedToken(block->begin_token(), AnnotatedToken::UNDERLYING));
+      }
+      // Don't walk rest after first.
+      for (const auto& statement : block->statements()) {
+        FlattenUntilNextChunk(statement, kPrecedenceLowest, result);
+        break;
+      }
+    } else if (const ConditionNode* condition = root->AsConditionNode()) {
+      FlattenUntilNextChunk(condition->condition(), kPrecedenceLowest, result);
+      // Don't traverse into true/false as those count as breaks.
+    } else if (const FunctionCallNode* func_call = root->AsFunctionCall()) {
+      result->push_back(
+          AnnotatedToken(func_call->function(), AnnotatedToken::UNDERLYING));
+      result->push_back(
+          AnnotatedToken(func_call->args()->begin_token(),
+                         AnnotatedToken::LEFT_PAREN_FUNCTION_CALL));
+      size_t i = 0;
+      for (const auto& node : func_call->args()->contents()) {
+        FlattenUntilNextChunk(node, kPrecedenceLowest, result);
+        if (i < func_call->args()->contents().size() - 1) {
+          result->push_back(AnnotatedToken(Token(Location(), Token::COMMA, ","),
+                                           AnnotatedToken::UNDERLYING));
+        }
+        ++i;
+      }
+      FlattenUntilNextChunk(func_call->args()->End(), kPrecedenceLowest,
+                            result);
+    } else if (const IdentifierNode* identifier = root->AsIdentifier()) {
+      result->push_back(
+          AnnotatedToken(identifier->value(), AnnotatedToken::UNDERLYING));
+    } else if (const ListNode* list = root->AsList()) {
+      result->push_back(AnnotatedToken(
+          list->begin_token(), AnnotatedToken::LEFT_BRACKET_LIST_LITERAL));
+      size_t i = 0;
+      for (const auto& node : list->contents()) {
+        FlattenUntilNextChunk(node, kPrecedenceLowest, result);
+        if (i < list->contents().size() - 1) {
+          result->push_back(AnnotatedToken(Token(Location(), Token::COMMA, ","),
+                                           AnnotatedToken::UNDERLYING));
+        }
+        ++i;
+      }
+      FlattenUntilNextChunk(list->End(), kPrecedenceLowest, result);
+    } else if (const LiteralNode* literal = root->AsLiteral()) {
+      result->push_back(
+          AnnotatedToken(literal->value(), AnnotatedToken::UNDERLYING));
+    } else if (const UnaryOpNode* unaryop = root->AsUnaryOp()) {
+      FlattenUntilNextChunk(unaryop->operand(), kPrecedenceUnary, result);
+    } else if (const BlockCommentNode* comment = root->AsBlockComment()) {
+      result->push_back(
+          AnnotatedToken(comment->comment(), AnnotatedToken::UNDERLYING));
+    } else if (const EndNode* end = root->AsEnd()) {
+      result->push_back(
+          AnnotatedToken(end->value(), AnnotatedToken::UNDERLYING));
+    } else {
+      CHECK(false) << "Unhandled case in FlattenUntilNextChunk.";
+    }
+
+    if (parenthesized) {
+      result->push_back(
+          AnnotatedToken(Token(Location(), Token::RIGHT_PAREN, ")"),
+                         AnnotatedToken::UNDERLYING));
+    }
+  }
+}
+
+std::vector<AnnotatedToken> BuildAnnotatedTokenList(
+    const ParseNode* statement) {
+  std::vector<AnnotatedToken> result;
+  FlattenUntilNextChunk(statement, kPrecedenceLowest, &result);
+  return result;
+}
+
+LineBreaker::LineBreaker(const std::vector<AnnotatedToken>& annotated_tokens,
+                         int initial_column)
+    : annotated_tokens_(annotated_tokens),
+      initial_column_(initial_column),
+      end_(static_cast<int>(annotated_tokens.size())) {
+}
+
+LineBreaker::~LineBreaker() {
+}
+
+std::string LineBreaker::GetBestLayout() {
+  Format(0, initial_column_);
+  return std::string();
+}
+
+void LineBreaker::Format(int index, int start_column) {
+  LineState state;
+  state.column = start_column;
+  state.next = index + 1;
+
+  // todo move past first, it's already in place
+
+  while (state.next < end_) {
+
+  }
+}
+
+int LineBreaker::CalculatePenalty(LineState state, bool newline) {
+  if (state.next == end_)
+    return 0;
+
+  int penalty = 0;
+
+  AddTokenToState(newline, &state);
+
+  // Assign penalty for being too long.
+  if (state.column > kMaximumWidth) {
+    int excess_characters = state.column - kMaximumWidth;
+    penalty += excess_characters * kExcessCharacterPenalty;
+  }
+
+  int no_break = CalculatePenalty(state, false);
+  int with_break = CalculatePenalty(state, true);
+  int result = std::min(no_break, with_break);
+  //penalty_cache_[state] = result;
+  return result + penalty;
+}
+
+void LineBreaker::AddTokenToState(bool newline, LineState* state) {
+}
+
+}  // namespace commands