format: Fix not getting to fixed point in one step

In https://gn-review.googlesource.com/c/gn/+/7140/ some styles of suffix
comments the formatter would wrap the suffix comments. But on reapplying
the formatter a second time, the parse tree is slightly different. The
second time through, the wrapped comment is the only thing on a line
separating two statements.

  a =                 1
    b + c  # x        2
           # y        3
  d = e               4

The ParseNode doesn't have a LocationRange that includes the suffix
comments, so when the formatter attempts to determine if there was a
blank line between two statements, it incorrectly decides there should
be an additional blank line added (because the end of the first
statement is not directly next to the start of the next one). That is,
the "end" of the "a=b+c" is line 2, not line 3.

I fiddled around with trying to amend the parse tree to make the
comments be included in the range of the node, but I didn't come up with
a reasonable way to do that. Instead, have the formatter calculate the
"real" range at formatting time, so instead of simply using line numbers
for A and B to determine if they're split, it walks down A looking for
suffix comments and finds the lowest down one and uses that instead. In
the example above, the walk will determine that "a=b+c" really ends on
line 3, so is adjacent to "d=e" on line 4 and no blank line should be
inserted.

This makes the recent Chromium test reformat
https://chromium-review.googlesource.com/c/chromium/src/+/2011169/
"stick" in that no further changes are made if the formatter is run on
it again.

Bug: gn:141
Change-Id: If320a87feec9671d2368a799e9e396866698561d
Reviewed-on: https://gn-review.googlesource.com/c/gn/+/7180
Commit-Queue: Scott Graham <scottmg@chromium.org>
Reviewed-by: Brett Wilson <brettw@chromium.org>
Reviewed-by: Nico Weber <thakis@chromium.org>
diff --git a/src/gn/command_format.cc b/src/gn/command_format.cc
index 623d8e2..dafc732 100644
--- a/src/gn/command_format.cc
+++ b/src/gn/command_format.cc
@@ -486,13 +486,92 @@
   }
 }
 
+namespace {
+
+int SuffixCommentTreeWalk(const ParseNode* node) {
+  // Check all the children for suffix comments. This is conceptually simple,
+  // but ugly as there's not a generic parse tree walker. This walker goes
+  // lowest child first so that if it's valid that's returned.
+  if (!node)
+    return -1;
+
+#define RETURN_IF_SET(x)             \
+  if (int result = (x); result >= 0) \
+    return result;
+
+  if (const AccessorNode* accessor = node->AsAccessor()) {
+    RETURN_IF_SET(SuffixCommentTreeWalk(accessor->index()));
+    RETURN_IF_SET(SuffixCommentTreeWalk(accessor->member()));
+  } else if (const BinaryOpNode* binop = node->AsBinaryOp()) {
+    RETURN_IF_SET(SuffixCommentTreeWalk(binop->right()));
+  } else if (const BlockNode* block = node->AsBlock()) {
+    RETURN_IF_SET(SuffixCommentTreeWalk(block->End()));
+  } else if (const ConditionNode* condition = node->AsConditionNode()) {
+    RETURN_IF_SET(SuffixCommentTreeWalk(condition->if_false()));
+    RETURN_IF_SET(SuffixCommentTreeWalk(condition->if_true()));
+    RETURN_IF_SET(SuffixCommentTreeWalk(condition->condition()));
+  } else if (const FunctionCallNode* func_call = node->AsFunctionCall()) {
+    RETURN_IF_SET(SuffixCommentTreeWalk(func_call->block()));
+    RETURN_IF_SET(SuffixCommentTreeWalk(func_call->args()));
+  } else if (node->AsIdentifier()) {
+    // Nothing.
+  } else if (const ListNode* list = node->AsList()) {
+    RETURN_IF_SET(SuffixCommentTreeWalk(list->End()));
+  } else if (node->AsLiteral()) {
+    // Nothing.
+  } else if (const UnaryOpNode* unaryop = node->AsUnaryOp()) {
+    RETURN_IF_SET(SuffixCommentTreeWalk(unaryop->operand()));
+  } else if (node->AsBlockComment()) {
+    // Nothing.
+  } else if (node->AsEnd()) {
+    // Nothing.
+  } else {
+    CHECK(false) << "Unhandled case in SuffixCommentTreeWalk.";
+  }
+
+#undef RETURN_IF_SET
+
+  // Check this node if there are no child comments.
+  if (node->comments() && !node->comments()->suffix().empty()) {
+    return node->comments()->suffix().back().location().line_number();
+  }
+
+  return -1;
+};
+
+// If there are suffix comments on the first node or its children, they might
+// carry down multiple lines. Otherwise, use the node's normal end range. This
+// function is needed because the parse tree doesn't include comments in the
+// location ranges, and it's not a straightforword change to add them. So this
+// is effectively finding the "real" range for |root| including suffix comments.
+// Note that it's not enough to simply look at |root|'s suffix comments because
+// in the case of:
+//
+//   a =
+//       b + c  # something
+//              # or other
+//   x = y
+//
+// the comments are attached to a BinOp+ which is a child of BinOp=, not
+// directly to the BinOp= which will be what's being used to determine if there
+// should be a blank line inserted before the |x| line.
+int FindLowestSuffixComment(const ParseNode* root) {
+  LocationRange range = root->GetRange();
+  int end = range.end().line_number();
+  int result = SuffixCommentTreeWalk(root);
+  return (result == -1 || result < end) ? end : result;
+}
+
+}  // namespace
+
 bool Printer::ShouldAddBlankLineInBetween(const ParseNode* a,
                                           const ParseNode* b) {
-  LocationRange a_range = a->GetRange();
   LocationRange b_range = b->GetRange();
+  int a_end = FindLowestSuffixComment(a);
+
   // If they're already separated by 1 or more lines, then we want to keep a
   // blank line.
-  return (b_range.begin().line_number() > a_range.end().line_number() + 1) ||
+  return (b_range.begin().line_number() > a_end + 1) ||
          // Always put a blank line before a block comment.
          b->AsBlockComment();
 }
diff --git a/src/gn/command_format_unittest.cc b/src/gn/command_format_unittest.cc
index 4dcf3bb..5f814b9 100644
--- a/src/gn/command_format_unittest.cc
+++ b/src/gn/command_format_unittest.cc
@@ -125,3 +125,4 @@
 FORMAT_TEST(078)
 FORMAT_TEST(079)
 FORMAT_TEST(080)
+FORMAT_TEST(081)
diff --git a/src/gn/format_test_data/081.gn b/src/gn/format_test_data/081.gn
new file mode 100644
index 0000000..d9d494e
--- /dev/null
+++ b/src/gn/format_test_data/081.gn
@@ -0,0 +1,18 @@
+inputs = idl_lexer_parser_files + idl_compiler_files # to be explicit (covered by parsetab)
+inputs += "hi"
+
+if (true) {
+  if (true) {
+    inputs = idl_lexer_parser_files + idl_compiler_files # to be explicit (covered by parsetab)
+    inputs += "hi"
+  }
+}
+
+if (true) {
+  if (something) {
+    a = b
+  } else {  # !is_chromeos
+    os_category = current_os
+  }
+  no_blank_here = true
+}
diff --git a/src/gn/format_test_data/081.golden b/src/gn/format_test_data/081.golden
new file mode 100644
index 0000000..c4ee25f
--- /dev/null
+++ b/src/gn/format_test_data/081.golden
@@ -0,0 +1,21 @@
+inputs = idl_lexer_parser_files + idl_compiler_files  # to be explicit (covered
+                                                      # by parsetab)
+inputs += "hi"
+
+if (true) {
+  if (true) {
+    inputs =
+        idl_lexer_parser_files + idl_compiler_files  # to be explicit (covered
+                                                     # by parsetab)
+    inputs += "hi"
+  }
+}
+
+if (true) {
+  if (something) {
+    a = b
+  } else {  # !is_chromeos
+    os_category = current_os
+  }
+  no_blank_here = true
+}