tools/gn/command_format.cc - chromium/src.git - Git at Google

 // 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 <sstream>

 #include "base/command_line.h"
 #include "base/file_util.h"
 #include "base/strings/string_split.h"
 #include "tools/gn/commands.h"
 #include "tools/gn/filesystem_utils.h"
 #include "tools/gn/input_file.h"
 #include "tools/gn/parser.h"
 #include "tools/gn/scheduler.h"
 #include "tools/gn/setup.h"
 #include "tools/gn/source_file.h"
 #include "tools/gn/tokenizer.h"

 namespace commands {

 const char kSwitchDumpTree[] = "dump-tree";
 const char kSwitchInPlace[] = "in-place";
 const char kSwitchStdin[] = "stdin";

 const char kFormat[] = "format";
 const char kFormat_HelpShort[] =
     "format: Format .gn file. (ALPHA, WILL DESTROY DATA!)";
 const char kFormat_Help[] =
     "gn format [--dump-tree] [--in-place] [--stdin] BUILD.gn\n"
     "\n"
     "  Formats .gn file to a standard format. THIS IS NOT FULLY IMPLEMENTED\n"
     "  YET! IT WILL EAT YOUR BEAUTIFUL .GN FILES. AND YOUR LAUNDRY.\n"
     "  At a minimum, make sure everything is `git commit`d so you can\n"
     "  `git checkout -f` to recover.\n"
     "\n"
     "Arguments\n"
     "  --dump-tree\n"
     "      For debugging only, dumps the parse tree.\n"
     "\n"
     "  --in-place\n"
     "      Instead writing the formatted file to stdout, replace the input\n"
     "      with the formatted output.\n"
     "\n"
     "  --stdin\n"
     "      Read input from stdin (and write to stdout). Not compatible with\n"
     "      --in-place of course.\n"
     "\n"
     "Examples\n"
     "  gn format //some/BUILD.gn\n"
     "  gn format some\\BUILD.gn\n"
     "  gn format /abspath/some/BUILD.gn\n"
     "  gn format --stdin\n";

 namespace {

 const int kIndentSize = 2;
 const int kMaximumWidth = 80;

 enum Precedence {
   kPrecedenceLowest,
   kPrecedenceAssign,
   kPrecedenceOr,
   kPrecedenceAnd,
   kPrecedenceCompare,
   kPrecedenceAdd,
   kPrecedenceSuffix,
   kPrecedenceUnary,
 };

 class Printer {
  public:
   Printer();
   ~Printer();

   void Block(const ParseNode* file);

   std::string String() const { return output_; }

  private:
   // Format a list of values using the given style.
   enum SequenceStyle {
     kSequenceStyleList,
     kSequenceStyleBlock,
     kSequenceStyleBracedBlock,
   };

   enum ExprStyle {
     kExprStyleRegular,
     kExprStyleComment,
   };

   struct Metrics {
     Metrics() : first_length(-1), longest_length(-1), multiline(false) {}
     int first_length;
     int longest_length;
     bool multiline;
   };

   // Add to output.
   void Print(base::StringPiece str);

   // Add the current margin (as spaces) to the output.
   void PrintMargin();

   void TrimAndPrintToken(const Token& token);

   // End the current line, flushing end of line comments.
   void Newline();

   // Remove trailing spaces from the current line.
   void Trim();

   // Whether there's a blank separator line at the current position.
   bool HaveBlankLine();

   bool IsAssignment(const ParseNode* node);

   // Heuristics to decide if there should be a blank line added between two
   // items. For various "small" items, it doesn't look nice if there's too much
   // vertical whitespace added.
   bool ShouldAddBlankLineInBetween(const ParseNode* a, const ParseNode* b);

   // Get the 0-based x position on the current line.
   int CurrentColumn();

   // Adds an opening ( if prec is less than the outers (to maintain evalution
   // order for a subexpression). If an opening paren is emitted, *parenthesized
   // will be set so it can be closed at the end of the expression.
   void AddParen(int prec, int outer_prec, bool* parenthesized);

   // Print the expression to the output buffer. Returns the type of element
   // added to the output. The value of outer_prec gives the precedence of the
   // operator outside this Expr. If that operator binds tighter than root's,
   // Expr must introduce parentheses.
   ExprStyle Expr(const ParseNode* root, int outer_prec);

   // Use a sub-Printer recursively to figure out the size that an expression
   // would be before actually adding it to the output.
   Metrics GetLengthOfExpr(const ParseNode* expr, int outer_prec);

   // Format a list of values using the given style.
   // |end| holds any trailing comments to be printed just before the closing
   // bracket.
   template <class PARSENODE>  // Just for const covariance.
   void Sequence(SequenceStyle style,
                 const std::vector<PARSENODE*>& list,
                 const ParseNode* end);

   void FunctionCall(const FunctionCallNode* func_call);

   std::string output_;           // Output buffer.
   std::vector<Token> comments_;  // Pending end-of-line comments.
   int margin_;                   // Left margin (number of spaces).

   // Gives the precedence for operators in a BinaryOpNode.
   std::map<base::StringPiece, Precedence> precedence_;

   DISALLOW_COPY_AND_ASSIGN(Printer);
 };

 Printer::Printer() : margin_(0) {
   output_.reserve(100 << 10);
   precedence_["="] = kPrecedenceAssign;
   precedence_["+="] = kPrecedenceAssign;
   precedence_["-="] = kPrecedenceAssign;
   precedence_["||"] = kPrecedenceOr;
   precedence_["&&"] = kPrecedenceAnd;
   precedence_["<"] = kPrecedenceCompare;
   precedence_[">"] = kPrecedenceCompare;
   precedence_["=="] = kPrecedenceCompare;
   precedence_["!="] = kPrecedenceCompare;
   precedence_["<="] = kPrecedenceCompare;
   precedence_[">="] = kPrecedenceCompare;
   precedence_["+"] = kPrecedenceAdd;
   precedence_["-"] = kPrecedenceAdd;
   precedence_["!"] = kPrecedenceUnary;
 }

 Printer::~Printer() {
 }

 void Printer::Print(base::StringPiece str) {
   str.AppendToString(&output_);
 }

 void Printer::PrintMargin() {
   output_ += std::string(margin_, ' ');
 }

 void Printer::TrimAndPrintToken(const Token& token) {
   std::string trimmed;
   TrimWhitespaceASCII(token.value().as_string(), base::TRIM_ALL, &trimmed);
   Print(trimmed);
 }

 void Printer::Newline() {
   if (!comments_.empty()) {
     Print("  ");
     int i = 0;
     // Save the margin, and temporarily set it to where the first comment
     // starts so that multiple suffix comments are vertically aligned. This
     // will need to be fancier once we enforce 80 col.
     int old_margin = margin_;
     for (const auto& c : comments_) {
       if (i == 0)
         margin_ = CurrentColumn();
       else {
         Trim();
         Print("\n");
         PrintMargin();
       }
       TrimAndPrintToken(c);
       ++i;
     }
     margin_ = old_margin;
     comments_.clear();
   }
   Trim();
   Print("\n");
   PrintMargin();
 }

 void Printer::Trim() {
   size_t n = output_.size();
   while (n > 0 && output_[n - 1] == ' ')
     --n;
   output_.resize(n);
 }

 bool Printer::HaveBlankLine() {
   size_t n = output_.size();
   while (n > 0 && output_[n - 1] == ' ')
     --n;
   return n > 2 && output_[n - 1] == '\n' && output_[n - 2] == '\n';
 }

 bool Printer::IsAssignment(const ParseNode* node) {
   return node->AsBinaryOp() && (node->AsBinaryOp()->op().value() == "=" ||
                                 node->AsBinaryOp()->op().value() == "+=" ||
                                 node->AsBinaryOp()->op().value() == "-=");
 }

 bool Printer::ShouldAddBlankLineInBetween(const ParseNode* a,
                                           const ParseNode* b) {
   if ((IsAssignment(a) || a->AsFunctionCall()) &&
       (!a->comments() || a->comments()->after().size() == 0) &&
       (IsAssignment(b) || b->AsFunctionCall()) &&
       (!b->comments() || b->comments()->before().size() == 0)) {
     Metrics first = GetLengthOfExpr(a, kPrecedenceLowest);
     Metrics second = GetLengthOfExpr(b, kPrecedenceLowest);
     if (!first.multiline || !second.multiline)
       return false;
   }
   return true;
 }

 int Printer::CurrentColumn() {
   int n = 0;
   while (n < static_cast<int>(output_.size()) &&
          output_[output_.size() - 1 - n] != '\n') {
     ++n;
   }
   return n;
 }

 void Printer::Block(const ParseNode* root) {
   const BlockNode* block = root->AsBlock();

   if (block->comments()) {
     for (const auto& c : block->comments()->before()) {
       TrimAndPrintToken(c);
       Newline();
     }
   }

   size_t i = 0;
   for (const auto& stmt : block->statements()) {
     Expr(stmt, kPrecedenceLowest);
     Newline();
     if (stmt->comments()) {
       // Why are before() not printed here too? before() are handled inside
       // Expr(), as are suffix() which are queued to the next Newline().
       // However, because it's a general expression handler, it doesn't insert
       // the newline itself, which only happens between block statements. So,
       // the after are handled explicitly here.
       for (const auto& c : stmt->comments()->after()) {
         TrimAndPrintToken(c);
         Newline();
       }
     }
     if (i < block->statements().size() - 1 &&
         (ShouldAddBlankLineInBetween(block->statements()[i],
                                      block->statements()[i + 1]))) {
       Newline();
     }
     ++i;
   }

   if (block->comments()) {
     for (const auto& c : block->comments()->after()) {
       TrimAndPrintToken(c);
       Newline();
     }
   }
 }

 Printer::Metrics Printer::GetLengthOfExpr(const ParseNode* expr,
                                           int outer_prec) {
   Metrics result;
   Printer sub;
   sub.Expr(expr, outer_prec);
   std::vector<std::string> lines;
   base::SplitStringDontTrim(sub.String(), '\n', &lines);
   result.multiline = lines.size() > 1;
   result.first_length = static_cast<int>(lines[0].size());
   for (const auto& line : lines) {
     result.longest_length =
         std::max(result.longest_length, static_cast<int>(line.size()));
   }
   return result;
 }

 void Printer::AddParen(int prec, int outer_prec, bool* parenthesized) {
   if (prec < outer_prec) {
     Print("(");
     *parenthesized = true;
   }
 }

 Printer::ExprStyle Printer::Expr(const ParseNode* root, int outer_prec) {
   ExprStyle result = kExprStyleRegular;
   if (root->comments()) {
     if (!root->comments()->before().empty()) {
       Trim();
       // If there's already other text on the line, start a new line.
       if (CurrentColumn() > 0)
         Print("\n");
       // We're printing a line comment, so we need to be at the current margin.
       PrintMargin();
       for (const auto& c : root->comments()->before()) {
         TrimAndPrintToken(c);
         Newline();
       }
     }
   }

   bool parenthesized = false;

   if (const AccessorNode* accessor = root->AsAccessor()) {
     AddParen(kPrecedenceSuffix, outer_prec, &parenthesized);
     Print(accessor->base().value());
     if (accessor->member()) {
       Print(".");
       Expr(accessor->member(), kPrecedenceLowest);
     } else {
       CHECK(accessor->index());
       Print("[");
       Expr(accessor->index(), kPrecedenceLowest);
       Print("]");
     }
   } else if (const BinaryOpNode* binop = root->AsBinaryOp()) {
     CHECK(precedence_.find(binop->op().value()) != precedence_.end());
     Precedence prec = precedence_[binop->op().value()];
     AddParen(prec, outer_prec, &parenthesized);
     Metrics right = GetLengthOfExpr(binop->right(), prec + 1);
     int op_length = static_cast<int>(binop->op().value().size()) + 2;
     Expr(binop->left(), prec);
     if (CurrentColumn() + op_length + right.first_length <= kMaximumWidth) {
       // If it just fits normally, put it here.
       Print(" ");
       Print(binop->op().value());
       Print(" ");
       Expr(binop->right(), prec + 1);
     } else {
       // Otherwise, put first argument and op, and indent next.
       Print(" ");
       Print(binop->op().value());
       int old_margin = margin_;
       margin_ += kIndentSize * 2;
       Newline();
       Expr(binop->right(), prec + 1);
       margin_ = old_margin;
     }
   } else if (const BlockNode* block = root->AsBlock()) {
     Sequence(kSequenceStyleBracedBlock, block->statements(), block->End());
   } else if (const ConditionNode* condition = root->AsConditionNode()) {
     Print("if (");
     Expr(condition->condition(), kPrecedenceLowest);
     Print(") ");
     Sequence(kSequenceStyleBracedBlock,
              condition->if_true()->statements(),
              condition->if_true()->End());
     if (condition->if_false()) {
       Print(" else ");
       // If it's a block it's a bare 'else', otherwise it's an 'else if'. See
       // ConditionNode::Execute.
       bool is_else_if = condition->if_false()->AsBlock() == NULL;
       if (is_else_if) {
         Expr(condition->if_false(), kPrecedenceLowest);
       } else {
         Sequence(kSequenceStyleBracedBlock,
                  condition->if_false()->AsBlock()->statements(),
                  condition->if_false()->AsBlock()->End());
       }
     }
   } else if (const FunctionCallNode* func_call = root->AsFunctionCall()) {
     FunctionCall(func_call);
   } else if (const IdentifierNode* identifier = root->AsIdentifier()) {
     Print(identifier->value().value());
   } else if (const ListNode* list = root->AsList()) {
     Sequence(kSequenceStyleList, list->contents(), list->End());
   } else if (const LiteralNode* literal = root->AsLiteral()) {
     // TODO(scottmg): Quoting?
     Print(literal->value().value());
   } else if (const UnaryOpNode* unaryop = root->AsUnaryOp()) {
     Print(unaryop->op().value());
     Expr(unaryop->operand(), kPrecedenceUnary);
   } else if (const BlockCommentNode* block_comment = root->AsBlockComment()) {
     Print(block_comment->comment().value());
     result = kExprStyleComment;
   } else if (const EndNode* end = root->AsEnd()) {
     Print(end->value().value());
   } else {
     CHECK(false) << "Unhandled case in Expr.";
   }

   if (parenthesized)
     Print(")");

   // Defer any end of line comment until we reach the newline.
   if (root->comments() && !root->comments()->suffix().empty()) {
     std::copy(root->comments()->suffix().begin(),
               root->comments()->suffix().end(),
               std::back_inserter(comments_));
   }

   return result;
 }

 template <class PARSENODE>
 void Printer::Sequence(SequenceStyle style,
                        const std::vector<PARSENODE*>& list,
                        const ParseNode* end) {
   bool force_multiline = false;
   if (style == kSequenceStyleList)
     Print("[");
   else if (style == kSequenceStyleBracedBlock)
     Print("{");

   if (style == kSequenceStyleBlock || style == kSequenceStyleBracedBlock)
     force_multiline = true;

   if (end && end->comments() && !end->comments()->before().empty())
     force_multiline = true;

   // If there's before line comments, make sure we have a place to put them.
   for (const auto& i : list) {
     if (i->comments() && !i->comments()->before().empty())
       force_multiline = true;
   }

   if (list.size() == 0 && !force_multiline) {
     // No elements, and not forcing newlines, print nothing.
   } else if (list.size() == 1 && !force_multiline) {
     Print(" ");
     Expr(list[0], kPrecedenceLowest);
     CHECK(!list[0]->comments() || list[0]->comments()->after().empty());
     Print(" ");
   } else {
     margin_ += kIndentSize;
     size_t i = 0;
     for (const auto& x : list) {
       Newline();
       // If:
       // - we're going to output some comments, and;
       // - we haven't just started this multiline list, and;
       // - there isn't already a blank line here;
       // Then: insert one.
       if (i != 0 && x->comments() && !x->comments()->before().empty() &&
           !HaveBlankLine()) {
         Newline();
       }
       ExprStyle expr_style = Expr(x, kPrecedenceLowest);
       CHECK(!x->comments() || x->comments()->after().empty());
       if (i < list.size() - 1 || style == kSequenceStyleList) {
         if (style == kSequenceStyleList && expr_style == kExprStyleRegular) {
           Print(",");
         } else {
           if (i < list.size() - 1 &&
               ShouldAddBlankLineInBetween(list[i], list[i + 1]))
             Newline();
         }
       }
       ++i;
     }

     // Trailing comments.
     if (end->comments()) {
       if (!list.empty())
         Newline();
       for (const auto& c : end->comments()->before()) {
         Newline();
         TrimAndPrintToken(c);
       }
     }

     margin_ -= kIndentSize;
     Newline();
   }

   if (style == kSequenceStyleList)
     Print("]");
   else if (style == kSequenceStyleBracedBlock)
     Print("}");
 }

 void Printer::FunctionCall(const FunctionCallNode* func_call) {
   Print(func_call->function().value());
   Print("(");

   int old_margin = margin_;
   bool have_block = func_call->block() != nullptr;
   bool force_multiline = false;

   const std::vector<const ParseNode*>& list = func_call->args()->contents();
   const ParseNode* end = func_call->args()->End();

   if (end && end->comments() && !end->comments()->before().empty())
     force_multiline = true;

   // If there's before line comments, make sure we have a place to put them.
   for (const auto& i : list) {
     if (i->comments() && !i->comments()->before().empty())
       force_multiline = true;
   }

   // Calculate the length of the items for function calls so we can decide to
   // compress them in various nicer ways.
   std::vector<int> natural_lengths;
   bool fits_on_current_line = true;
   int max_item_width = 0;
   int total_length = 0;
   natural_lengths.reserve(list.size());
   std::string terminator = ")";
   if (have_block)
     terminator += " {";
   for (size_t i = 0; i < list.size(); ++i) {
     Metrics sub = GetLengthOfExpr(list[i], kPrecedenceLowest);
     if (sub.multiline)
       fits_on_current_line = false;
     natural_lengths.push_back(sub.longest_length);
     total_length += sub.longest_length;
     if (i < list.size() - 1) {
       total_length += static_cast<int>(strlen(", "));
     }
   }
   fits_on_current_line =
       fits_on_current_line &&
       CurrentColumn() + total_length + terminator.size() <= kMaximumWidth;
   if (natural_lengths.size() > 0) {
     max_item_width =
         *std::max_element(natural_lengths.begin(), natural_lengths.end());
   }

   if (list.size() == 0 && !force_multiline) {
     // No elements, and not forcing newlines, print nothing.
   } else if (list.size() == 1 && !force_multiline && fits_on_current_line) {
     Expr(list[0], kPrecedenceLowest);
     CHECK(!list[0]->comments() || list[0]->comments()->after().empty());
   } else {
     // Function calls get to be single line even with multiple arguments, if
     // they fit inside the maximum width.
     if (!force_multiline && fits_on_current_line) {
       for (size_t i = 0; i < list.size(); ++i) {
         Expr(list[i], kPrecedenceLowest);
         if (i < list.size() - 1)
           Print(", ");
       }
     } else {
       bool should_break_to_next_line = true;
       int indent = kIndentSize * 2;
       if (CurrentColumn() + max_item_width + terminator.size() <=
               kMaximumWidth ||
           CurrentColumn() < margin_ + indent) {
         should_break_to_next_line = false;
         margin_ = CurrentColumn();
       } else {
         margin_ += indent;
       }
       size_t i = 0;
       for (const auto& x : list) {
         // Function calls where all the arguments would fit at the current
         // position should do that instead of going back to margin+4.
         if (i > 0 || should_break_to_next_line)
           Newline();
         ExprStyle expr_style = Expr(x, kPrecedenceLowest);
         CHECK(!x->comments() || x->comments()->after().empty());
         if (i < list.size() - 1) {
           if (expr_style == kExprStyleRegular) {
             Print(",");
           } else {
             Newline();
           }
         }
         ++i;
       }

       // Trailing comments.
       if (end->comments()) {
         if (!list.empty())
           Newline();
         for (const auto& c : end->comments()->before()) {
           Newline();
           TrimAndPrintToken(c);
         }
         if (!end->comments()->before().empty())
           Newline();
       }
     }
   }

   Print(")");
   margin_ = old_margin;

   if (have_block) {
     Print(" ");
     Sequence(kSequenceStyleBracedBlock,
              func_call->block()->statements(),
              func_call->block()->End());
   }
 }

 void DoFormat(const ParseNode* root, bool dump_tree, std::string* output) {
   if (dump_tree) {
     std::ostringstream os;
     root->Print(os, 0);
     printf("----------------------\n");
     printf("-- PARSE TREE --------\n");
     printf("----------------------\n");
     printf("%s", os.str().c_str());
     printf("----------------------\n");
   }
   Printer pr;
   pr.Block(root);
   *output = pr.String();
 }

 std::string ReadStdin() {
   static const int kBufferSize = 256;
   char buffer[kBufferSize];
   std::string result;
   while (true) {
     char* input = NULL;
     input = fgets(buffer, kBufferSize, stdin);
     if (input == NULL && feof(stdin))
       return result;
     int length = static_cast<int>(strlen(buffer));
     if (length == 0)
       return result;
     else
       result += std::string(buffer, length);
   }
 }

 }  // namespace

 bool FormatFileToString(Setup* setup,
                         const SourceFile& file,
                         bool dump_tree,
                         std::string* output) {
   Err err;
   const ParseNode* parse_node =
       setup->scheduler().input_file_manager()->SyncLoadFile(
           LocationRange(), &setup->build_settings(), file, &err);
   if (err.has_error()) {
     err.PrintToStdout();
     return false;
   }
   DoFormat(parse_node, dump_tree, output);
   return true;
 }

 bool FormatStringToString(const std::string& input,
                           bool dump_tree,
                           std::string* output) {
   SourceFile source_file;
   InputFile file(source_file);
   file.SetContents(input);
   Err err;
   // Tokenize.
   std::vector<Token> tokens = Tokenizer::Tokenize(&file, &err);
   if (err.has_error()) {
     err.PrintToStdout();
     return false;
   }

   // Parse.
   scoped_ptr<ParseNode> parse_node = Parser::Parse(tokens, &err);
   if (err.has_error()) {
     err.PrintToStdout();
     return false;
   }

   DoFormat(parse_node.get(), dump_tree, output);
   return true;
 }

 int RunFormat(const std::vector<std::string>& args) {
   bool dump_tree =
       base::CommandLine::ForCurrentProcess()->HasSwitch(kSwitchDumpTree);

   bool from_stdin =
       base::CommandLine::ForCurrentProcess()->HasSwitch(kSwitchStdin);

   if (from_stdin) {
     if (args.size() != 0) {
       Err(Location(), "Expecting no arguments when reading from stdin.\n")
           .PrintToStdout();
       return 1;
     }
     std::string input = ReadStdin();
     std::string output;
     if (!FormatStringToString(input, dump_tree, &output))
       return 1;
     printf("%s", output.c_str());
     return 0;
   }

   // TODO(scottmg): Eventually, this should be a list/spec of files, and they
   // should all be done in parallel.
   if (args.size() != 1) {
     Err(Location(), "Expecting exactly one argument, see `gn help format`.\n")
         .PrintToStdout();
     return 1;
   }

   Setup setup;
   SourceDir source_dir =
       SourceDirForCurrentDirectory(setup.build_settings().root_path());
   SourceFile file = source_dir.ResolveRelativeFile(args[0]);

   std::string output_string;
   if (FormatFileToString(&setup, file, dump_tree, &output_string)) {
     bool in_place =
         base::CommandLine::ForCurrentProcess()->HasSwitch(kSwitchInPlace);
     if (in_place) {
       base::FilePath to_write = setup.build_settings().GetFullPath(file);
       if (base::WriteFile(to_write,
                           output_string.data(),
                           static_cast<int>(output_string.size())) == -1) {
         Err(Location(),
             std::string("Failed to write formatted output back to \"") +
                 to_write.AsUTF8Unsafe() + std::string("\".")).PrintToStdout();
         return 1;
       }
       printf("Wrote formatted to '%s'.\n", to_write.AsUTF8Unsafe().c_str());
     } else {
       printf("%s", output_string.c_str());
     }
   }

   return 0;
 }

 }  // namespace commands
	// 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 <sstream>

	#include "base/command_line.h"
	#include "base/file_util.h"
	#include "base/strings/string_split.h"
	#include "tools/gn/commands.h"
	#include "tools/gn/filesystem_utils.h"
	#include "tools/gn/input_file.h"
	#include "tools/gn/parser.h"
	#include "tools/gn/scheduler.h"
	#include "tools/gn/setup.h"
	#include "tools/gn/source_file.h"
	#include "tools/gn/tokenizer.h"

	namespace commands {

	const char kSwitchDumpTree[] = "dump-tree";
	const char kSwitchInPlace[] = "in-place";
	const char kSwitchStdin[] = "stdin";

	const char kFormat[] = "format";
	const char kFormat_HelpShort[] =
	"format: Format .gn file. (ALPHA, WILL DESTROY DATA!)";
	const char kFormat_Help[] =
	"gn format [--dump-tree] [--in-place] [--stdin] BUILD.gn\n"
	"\n"
	" Formats .gn file to a standard format. THIS IS NOT FULLY IMPLEMENTED\n"
	" YET! IT WILL EAT YOUR BEAUTIFUL .GN FILES. AND YOUR LAUNDRY.\n"
	" At a minimum, make sure everything is `git commit`d so you can\n"
	" `git checkout -f` to recover.\n"
	"\n"
	"Arguments\n"
	" --dump-tree\n"
	" For debugging only, dumps the parse tree.\n"
	"\n"
	" --in-place\n"
	" Instead writing the formatted file to stdout, replace the input\n"
	" with the formatted output.\n"
	"\n"
	" --stdin\n"
	" Read input from stdin (and write to stdout). Not compatible with\n"
	" --in-place of course.\n"
	"\n"
	"Examples\n"
	" gn format //some/BUILD.gn\n"
	" gn format some\\BUILD.gn\n"
	" gn format /abspath/some/BUILD.gn\n"
	" gn format --stdin\n";

	namespace {

	const int kIndentSize = 2;
	const int kMaximumWidth = 80;

	enum Precedence {
	kPrecedenceLowest,
	kPrecedenceAssign,
	kPrecedenceOr,
	kPrecedenceAnd,
	kPrecedenceCompare,
	kPrecedenceAdd,
	kPrecedenceSuffix,
	kPrecedenceUnary,
	};

	class Printer {
	public:
	Printer();
	~Printer();

	void Block(const ParseNode* file);

	std::string String() const { return output_; }

	private:
	// Format a list of values using the given style.
	enum SequenceStyle {
	kSequenceStyleList,
	kSequenceStyleBlock,
	kSequenceStyleBracedBlock,
	};

	enum ExprStyle {
	kExprStyleRegular,
	kExprStyleComment,
	};

	struct Metrics {
	Metrics() : first_length(-1), longest_length(-1), multiline(false) {}
	int first_length;
	int longest_length;
	bool multiline;
	};

	// Add to output.
	void Print(base::StringPiece str);

	// Add the current margin (as spaces) to the output.
	void PrintMargin();

	void TrimAndPrintToken(const Token& token);

	// End the current line, flushing end of line comments.
	void Newline();

	// Remove trailing spaces from the current line.
	void Trim();

	// Whether there's a blank separator line at the current position.
	bool HaveBlankLine();

	bool IsAssignment(const ParseNode* node);

	// Heuristics to decide if there should be a blank line added between two
	// items. For various "small" items, it doesn't look nice if there's too much
	// vertical whitespace added.
	bool ShouldAddBlankLineInBetween(const ParseNode* a, const ParseNode* b);

	// Get the 0-based x position on the current line.
	int CurrentColumn();

	// Adds an opening ( if prec is less than the outers (to maintain evalution
	// order for a subexpression). If an opening paren is emitted, *parenthesized
	// will be set so it can be closed at the end of the expression.
	void AddParen(int prec, int outer_prec, bool* parenthesized);

	// Print the expression to the output buffer. Returns the type of element
	// added to the output. The value of outer_prec gives the precedence of the
	// operator outside this Expr. If that operator binds tighter than root's,
	// Expr must introduce parentheses.
	ExprStyle Expr(const ParseNode* root, int outer_prec);

	// Use a sub-Printer recursively to figure out the size that an expression
	// would be before actually adding it to the output.
	Metrics GetLengthOfExpr(const ParseNode* expr, int outer_prec);

	// Format a list of values using the given style.
	// \|end\| holds any trailing comments to be printed just before the closing
	// bracket.
	template <class PARSENODE> // Just for const covariance.
	void Sequence(SequenceStyle style,
	const std::vector<PARSENODE*>& list,
	const ParseNode* end);

	void FunctionCall(const FunctionCallNode* func_call);

	std::string output_; // Output buffer.
	std::vector<Token> comments_; // Pending end-of-line comments.
	int margin_; // Left margin (number of spaces).

	// Gives the precedence for operators in a BinaryOpNode.
	std::map<base::StringPiece, Precedence> precedence_;

	DISALLOW_COPY_AND_ASSIGN(Printer);
	};

	Printer::Printer() : margin_(0) {
	output_.reserve(100 << 10);
	precedence_["="] = kPrecedenceAssign;
	precedence_["+="] = kPrecedenceAssign;
	precedence_["-="] = kPrecedenceAssign;
	precedence_["\|\|"] = kPrecedenceOr;
	precedence_["&&"] = kPrecedenceAnd;
	precedence_["<"] = kPrecedenceCompare;
	precedence_[">"] = kPrecedenceCompare;
	precedence_["=="] = kPrecedenceCompare;
	precedence_["!="] = kPrecedenceCompare;
	precedence_["<="] = kPrecedenceCompare;
	precedence_[">="] = kPrecedenceCompare;
	precedence_["+"] = kPrecedenceAdd;
	precedence_["-"] = kPrecedenceAdd;
	precedence_["!"] = kPrecedenceUnary;
	}

	Printer::~Printer() {
	}

	void Printer::Print(base::StringPiece str) {
	str.AppendToString(&output_);
	}

	void Printer::PrintMargin() {
	output_ += std::string(margin_, ' ');
	}

	void Printer::TrimAndPrintToken(const Token& token) {
	std::string trimmed;
	TrimWhitespaceASCII(token.value().as_string(), base::TRIM_ALL, &trimmed);
	Print(trimmed);
	}

	void Printer::Newline() {
	if (!comments_.empty()) {
	Print(" ");
	int i = 0;
	// Save the margin, and temporarily set it to where the first comment
	// starts so that multiple suffix comments are vertically aligned. This
	// will need to be fancier once we enforce 80 col.
	int old_margin = margin_;
	for (const auto& c : comments_) {
	if (i == 0)
	margin_ = CurrentColumn();
	else {
	Trim();
	Print("\n");
	PrintMargin();
	}
	TrimAndPrintToken(c);
	++i;
	}
	margin_ = old_margin;
	comments_.clear();
	}
	Trim();
	Print("\n");
	PrintMargin();
	}

	void Printer::Trim() {
	size_t n = output_.size();
	while (n > 0 && output_[n - 1] == ' ')
	--n;
	output_.resize(n);
	}

	bool Printer::HaveBlankLine() {
	size_t n = output_.size();
	while (n > 0 && output_[n - 1] == ' ')
	--n;
	return n > 2 && output_[n - 1] == '\n' && output_[n - 2] == '\n';
	}

	bool Printer::IsAssignment(const ParseNode* node) {
	return node->AsBinaryOp() && (node->AsBinaryOp()->op().value() == "=" \|\|
	node->AsBinaryOp()->op().value() == "+=" \|\|
	node->AsBinaryOp()->op().value() == "-=");
	}

	bool Printer::ShouldAddBlankLineInBetween(const ParseNode* a,
	const ParseNode* b) {
	if ((IsAssignment(a) \|\| a->AsFunctionCall()) &&
	(!a->comments() \|\| a->comments()->after().size() == 0) &&
	(IsAssignment(b) \|\| b->AsFunctionCall()) &&
	(!b->comments() \|\| b->comments()->before().size() == 0)) {
	Metrics first = GetLengthOfExpr(a, kPrecedenceLowest);
	Metrics second = GetLengthOfExpr(b, kPrecedenceLowest);
	if (!first.multiline \|\| !second.multiline)
	return false;
	}
	return true;
	}

	int Printer::CurrentColumn() {
	int n = 0;
	while (n < static_cast<int>(output_.size()) &&
	output_[output_.size() - 1 - n] != '\n') {
	++n;
	}
	return n;
	}

	void Printer::Block(const ParseNode* root) {
	const BlockNode* block = root->AsBlock();

	if (block->comments()) {
	for (const auto& c : block->comments()->before()) {
	TrimAndPrintToken(c);
	Newline();
	}
	}

	size_t i = 0;
	for (const auto& stmt : block->statements()) {
	Expr(stmt, kPrecedenceLowest);
	Newline();
	if (stmt->comments()) {
	// Why are before() not printed here too? before() are handled inside
	// Expr(), as are suffix() which are queued to the next Newline().
	// However, because it's a general expression handler, it doesn't insert
	// the newline itself, which only happens between block statements. So,
	// the after are handled explicitly here.
	for (const auto& c : stmt->comments()->after()) {
	TrimAndPrintToken(c);
	Newline();
	}
	}
	if (i < block->statements().size() - 1 &&
	(ShouldAddBlankLineInBetween(block->statements()[i],
	block->statements()[i + 1]))) {
	Newline();
	}
	++i;
	}

	if (block->comments()) {
	for (const auto& c : block->comments()->after()) {
	TrimAndPrintToken(c);
	Newline();
	}
	}
	}

	Printer::Metrics Printer::GetLengthOfExpr(const ParseNode* expr,
	int outer_prec) {
	Metrics result;
	Printer sub;
	sub.Expr(expr, outer_prec);
	std::vector<std::string> lines;
	base::SplitStringDontTrim(sub.String(), '\n', &lines);
	result.multiline = lines.size() > 1;
	result.first_length = static_cast<int>(lines[0].size());
	for (const auto& line : lines) {
	result.longest_length =
	std::max(result.longest_length, static_cast<int>(line.size()));
	}
	return result;
	}

	void Printer::AddParen(int prec, int outer_prec, bool* parenthesized) {
	if (prec < outer_prec) {
	Print("(");
	*parenthesized = true;
	}
	}

	Printer::ExprStyle Printer::Expr(const ParseNode* root, int outer_prec) {
	ExprStyle result = kExprStyleRegular;
	if (root->comments()) {
	if (!root->comments()->before().empty()) {
	Trim();
	// If there's already other text on the line, start a new line.
	if (CurrentColumn() > 0)
	Print("\n");
	// We're printing a line comment, so we need to be at the current margin.
	PrintMargin();
	for (const auto& c : root->comments()->before()) {
	TrimAndPrintToken(c);
	Newline();
	}
	}
	}

	bool parenthesized = false;

	if (const AccessorNode* accessor = root->AsAccessor()) {
	AddParen(kPrecedenceSuffix, outer_prec, &parenthesized);
	Print(accessor->base().value());
	if (accessor->member()) {
	Print(".");
	Expr(accessor->member(), kPrecedenceLowest);
	} else {
	CHECK(accessor->index());
	Print("[");
	Expr(accessor->index(), kPrecedenceLowest);
	Print("]");
	}
	} else if (const BinaryOpNode* binop = root->AsBinaryOp()) {
	CHECK(precedence_.find(binop->op().value()) != precedence_.end());
	Precedence prec = precedence_[binop->op().value()];
	AddParen(prec, outer_prec, &parenthesized);
	Metrics right = GetLengthOfExpr(binop->right(), prec + 1);
	int op_length = static_cast<int>(binop->op().value().size()) + 2;
	Expr(binop->left(), prec);
	if (CurrentColumn() + op_length + right.first_length <= kMaximumWidth) {
	// If it just fits normally, put it here.
	Print(" ");
	Print(binop->op().value());
	Print(" ");
	Expr(binop->right(), prec + 1);
	} else {
	// Otherwise, put first argument and op, and indent next.
	Print(" ");
	Print(binop->op().value());
	int old_margin = margin_;
	margin_ += kIndentSize * 2;
	Newline();
	Expr(binop->right(), prec + 1);
	margin_ = old_margin;
	}
	} else if (const BlockNode* block = root->AsBlock()) {
	Sequence(kSequenceStyleBracedBlock, block->statements(), block->End());
	} else if (const ConditionNode* condition = root->AsConditionNode()) {
	Print("if (");
	Expr(condition->condition(), kPrecedenceLowest);
	Print(") ");
	Sequence(kSequenceStyleBracedBlock,
	condition->if_true()->statements(),
	condition->if_true()->End());
	if (condition->if_false()) {
	Print(" else ");
	// If it's a block it's a bare 'else', otherwise it's an 'else if'. See
	// ConditionNode::Execute.
	bool is_else_if = condition->if_false()->AsBlock() == NULL;
	if (is_else_if) {
	Expr(condition->if_false(), kPrecedenceLowest);
	} else {
	Sequence(kSequenceStyleBracedBlock,
	condition->if_false()->AsBlock()->statements(),
	condition->if_false()->AsBlock()->End());
	}
	}
	} else if (const FunctionCallNode* func_call = root->AsFunctionCall()) {
	FunctionCall(func_call);
	} else if (const IdentifierNode* identifier = root->AsIdentifier()) {
	Print(identifier->value().value());
	} else if (const ListNode* list = root->AsList()) {
	Sequence(kSequenceStyleList, list->contents(), list->End());
	} else if (const LiteralNode* literal = root->AsLiteral()) {
	// TODO(scottmg): Quoting?
	Print(literal->value().value());
	} else if (const UnaryOpNode* unaryop = root->AsUnaryOp()) {
	Print(unaryop->op().value());
	Expr(unaryop->operand(), kPrecedenceUnary);
	} else if (const BlockCommentNode* block_comment = root->AsBlockComment()) {
	Print(block_comment->comment().value());
	result = kExprStyleComment;
	} else if (const EndNode* end = root->AsEnd()) {
	Print(end->value().value());
	} else {
	CHECK(false) << "Unhandled case in Expr.";
	}

	if (parenthesized)
	Print(")");

	// Defer any end of line comment until we reach the newline.
	if (root->comments() && !root->comments()->suffix().empty()) {
	std::copy(root->comments()->suffix().begin(),
	root->comments()->suffix().end(),
	std::back_inserter(comments_));
	}

	return result;
	}

	template <class PARSENODE>
	void Printer::Sequence(SequenceStyle style,
	const std::vector<PARSENODE*>& list,
	const ParseNode* end) {
	bool force_multiline = false;
	if (style == kSequenceStyleList)
	Print("[");
	else if (style == kSequenceStyleBracedBlock)
	Print("{");

	if (style == kSequenceStyleBlock \|\| style == kSequenceStyleBracedBlock)
	force_multiline = true;

	if (end && end->comments() && !end->comments()->before().empty())
	force_multiline = true;

	// If there's before line comments, make sure we have a place to put them.
	for (const auto& i : list) {
	if (i->comments() && !i->comments()->before().empty())
	force_multiline = true;
	}

	if (list.size() == 0 && !force_multiline) {
	// No elements, and not forcing newlines, print nothing.
	} else if (list.size() == 1 && !force_multiline) {
	Print(" ");
	Expr(list[0], kPrecedenceLowest);
	CHECK(!list[0]->comments() \|\| list[0]->comments()->after().empty());
	Print(" ");
	} else {
	margin_ += kIndentSize;
	size_t i = 0;
	for (const auto& x : list) {
	Newline();
	// If:
	// - we're going to output some comments, and;
	// - we haven't just started this multiline list, and;
	// - there isn't already a blank line here;
	// Then: insert one.
	if (i != 0 && x->comments() && !x->comments()->before().empty() &&
	!HaveBlankLine()) {
	Newline();
	}
	ExprStyle expr_style = Expr(x, kPrecedenceLowest);
	CHECK(!x->comments() \|\| x->comments()->after().empty());
	if (i < list.size() - 1 \|\| style == kSequenceStyleList) {
	if (style == kSequenceStyleList && expr_style == kExprStyleRegular) {
	Print(",");
	} else {
	if (i < list.size() - 1 &&
	ShouldAddBlankLineInBetween(list[i], list[i + 1]))
	Newline();
	}
	}
	++i;
	}

	// Trailing comments.
	if (end->comments()) {
	if (!list.empty())
	Newline();
	for (const auto& c : end->comments()->before()) {
	Newline();
	TrimAndPrintToken(c);
	}
	}

	margin_ -= kIndentSize;
	Newline();
	}

	if (style == kSequenceStyleList)
	Print("]");
	else if (style == kSequenceStyleBracedBlock)
	Print("}");
	}

	void Printer::FunctionCall(const FunctionCallNode* func_call) {
	Print(func_call->function().value());
	Print("(");

	int old_margin = margin_;
	bool have_block = func_call->block() != nullptr;
	bool force_multiline = false;

	const std::vector<const ParseNode*>& list = func_call->args()->contents();
	const ParseNode* end = func_call->args()->End();

	if (end && end->comments() && !end->comments()->before().empty())
	force_multiline = true;

	// If there's before line comments, make sure we have a place to put them.
	for (const auto& i : list) {
	if (i->comments() && !i->comments()->before().empty())
	force_multiline = true;
	}

	// Calculate the length of the items for function calls so we can decide to
	// compress them in various nicer ways.
	std::vector<int> natural_lengths;
	bool fits_on_current_line = true;
	int max_item_width = 0;
	int total_length = 0;
	natural_lengths.reserve(list.size());
	std::string terminator = ")";
	if (have_block)
	terminator += " {";
	for (size_t i = 0; i < list.size(); ++i) {
	Metrics sub = GetLengthOfExpr(list[i], kPrecedenceLowest);
	if (sub.multiline)
	fits_on_current_line = false;
	natural_lengths.push_back(sub.longest_length);
	total_length += sub.longest_length;
	if (i < list.size() - 1) {
	total_length += static_cast<int>(strlen(", "));
	}
	}
	fits_on_current_line =
	fits_on_current_line &&
	CurrentColumn() + total_length + terminator.size() <= kMaximumWidth;
	if (natural_lengths.size() > 0) {
	max_item_width =
	*std::max_element(natural_lengths.begin(), natural_lengths.end());
	}

	if (list.size() == 0 && !force_multiline) {
	// No elements, and not forcing newlines, print nothing.
	} else if (list.size() == 1 && !force_multiline && fits_on_current_line) {
	Expr(list[0], kPrecedenceLowest);
	CHECK(!list[0]->comments() \|\| list[0]->comments()->after().empty());
	} else {
	// Function calls get to be single line even with multiple arguments, if
	// they fit inside the maximum width.
	if (!force_multiline && fits_on_current_line) {
	for (size_t i = 0; i < list.size(); ++i) {
	Expr(list[i], kPrecedenceLowest);
	if (i < list.size() - 1)
	Print(", ");
	}
	} else {
	bool should_break_to_next_line = true;
	int indent = kIndentSize * 2;
	if (CurrentColumn() + max_item_width + terminator.size() <=
	kMaximumWidth \|\|
	CurrentColumn() < margin_ + indent) {
	should_break_to_next_line = false;
	margin_ = CurrentColumn();
	} else {
	margin_ += indent;
	}
	size_t i = 0;
	for (const auto& x : list) {
	// Function calls where all the arguments would fit at the current
	// position should do that instead of going back to margin+4.
	if (i > 0 \|\| should_break_to_next_line)
	Newline();
	ExprStyle expr_style = Expr(x, kPrecedenceLowest);
	CHECK(!x->comments() \|\| x->comments()->after().empty());
	if (i < list.size() - 1) {
	if (expr_style == kExprStyleRegular) {
	Print(",");
	} else {
	Newline();
	}
	}
	++i;
	}

	// Trailing comments.
	if (end->comments()) {
	if (!list.empty())
	Newline();
	for (const auto& c : end->comments()->before()) {
	Newline();
	TrimAndPrintToken(c);
	}
	if (!end->comments()->before().empty())
	Newline();
	}
	}
	}

	Print(")");
	margin_ = old_margin;

	if (have_block) {
	Print(" ");
	Sequence(kSequenceStyleBracedBlock,
	func_call->block()->statements(),
	func_call->block()->End());
	}
	}

	void DoFormat(const ParseNode* root, bool dump_tree, std::string* output) {
	if (dump_tree) {
	std::ostringstream os;
	root->Print(os, 0);
	printf("----------------------\n");
	printf("-- PARSE TREE --------\n");
	printf("----------------------\n");
	printf("%s", os.str().c_str());
	printf("----------------------\n");
	}
	Printer pr;
	pr.Block(root);
	*output = pr.String();
	}

	std::string ReadStdin() {
	static const int kBufferSize = 256;
	char buffer[kBufferSize];
	std::string result;
	while (true) {
	char* input = NULL;
	input = fgets(buffer, kBufferSize, stdin);
	if (input == NULL && feof(stdin))
	return result;
	int length = static_cast<int>(strlen(buffer));
	if (length == 0)
	return result;
	else
	result += std::string(buffer, length);
	}
	}

	} // namespace

	bool FormatFileToString(Setup* setup,
	const SourceFile& file,
	bool dump_tree,
	std::string* output) {
	Err err;
	const ParseNode* parse_node =
	setup->scheduler().input_file_manager()->SyncLoadFile(
	LocationRange(), &setup->build_settings(), file, &err);
	if (err.has_error()) {
	err.PrintToStdout();
	return false;
	}
	DoFormat(parse_node, dump_tree, output);
	return true;
	}

	bool FormatStringToString(const std::string& input,
	bool dump_tree,
	std::string* output) {
	SourceFile source_file;
	InputFile file(source_file);
	file.SetContents(input);
	Err err;
	// Tokenize.
	std::vector<Token> tokens = Tokenizer::Tokenize(&file, &err);
	if (err.has_error()) {
	err.PrintToStdout();
	return false;
	}

	// Parse.
	scoped_ptr<ParseNode> parse_node = Parser::Parse(tokens, &err);
	if (err.has_error()) {
	err.PrintToStdout();
	return false;
	}

	DoFormat(parse_node.get(), dump_tree, output);
	return true;
	}

	int RunFormat(const std::vector<std::string>& args) {
	bool dump_tree =
	base::CommandLine::ForCurrentProcess()->HasSwitch(kSwitchDumpTree);

	bool from_stdin =
	base::CommandLine::ForCurrentProcess()->HasSwitch(kSwitchStdin);

	if (from_stdin) {
	if (args.size() != 0) {
	Err(Location(), "Expecting no arguments when reading from stdin.\n")
	.PrintToStdout();
	return 1;
	}
	std::string input = ReadStdin();
	std::string output;
	if (!FormatStringToString(input, dump_tree, &output))
	return 1;
	printf("%s", output.c_str());
	return 0;
	}

	// TODO(scottmg): Eventually, this should be a list/spec of files, and they
	// should all be done in parallel.
	if (args.size() != 1) {
	Err(Location(), "Expecting exactly one argument, see `gn help format`.\n")
	.PrintToStdout();
	return 1;
	}

	Setup setup;
	SourceDir source_dir =
	SourceDirForCurrentDirectory(setup.build_settings().root_path());
	SourceFile file = source_dir.ResolveRelativeFile(args[0]);

	std::string output_string;
	if (FormatFileToString(&setup, file, dump_tree, &output_string)) {
	bool in_place =
	base::CommandLine::ForCurrentProcess()->HasSwitch(kSwitchInPlace);
	if (in_place) {
	base::FilePath to_write = setup.build_settings().GetFullPath(file);
	if (base::WriteFile(to_write,
	output_string.data(),
	static_cast<int>(output_string.size())) == -1) {
	Err(Location(),
	std::string("Failed to write formatted output back to \"") +
	to_write.AsUTF8Unsafe() + std::string("\".")).PrintToStdout();
	return 1;
	}
	printf("Wrote formatted to '%s'.\n", to_write.AsUTF8Unsafe().c_str());
	} else {
	printf("%s", output_string.c_str());
	}
	}

	return 0;
	}

	} // namespace commands