Combine 2 exclusions in Layout Opportunity Tree if they shadow each other

third_party/WebKit/Source/core/layout/ng/ng_layout_opportunity_iterator.cc

Index: third_party/WebKit/Source/core/layout/ng/ng_layout_opportunity_iterator.cc
diff --git a/third_party/WebKit/Source/core/layout/ng/ng_layout_opportunity_iterator.cc b/third_party/WebKit/Source/core/layout/ng/ng_layout_opportunity_iterator.cc
index b04dc468c1a84e2540659cd76719c3487e23a2ff..185d53ab4b38e5bcb82f2cc0d0dc0874f0892ac0 100644
--- a/third_party/WebKit/Source/core/layout/ng/ng_layout_opportunity_iterator.cc
+++ b/third_party/WebKit/Source/core/layout/ng/ng_layout_opportunity_iterator.cc
@@ -6,10 +6,41 @@
 
 #include "core/layout/ng/ng_exclusion.h"
 #include "wtf/NonCopyingSort.h"
+#include "wtf/text/StringBuilder.h"
 
 namespace blink {
 namespace {
 
+void AppendNodeToString(const NGLayoutOpportunityTreeNode* node,
+                        StringBuilder* string_builder,
+                        unsigned indent = 0) {
+  DCHECK(string_builder);
+  if (!node) {
+    string_builder->append("'null'\n");
+    return;
+  }
+
+  string_builder->append(node->ToString());
+  string_builder->append("\n");
+
+  StringBuilder indent_builder;
+  for (unsigned i = 0; i < indent; i++)
+    indent_builder.append("\t");
+
+  if (node->IsLeafNode())
+    return;
+
+  string_builder->append(indent_builder.toString());
+  string_builder->append("Left:\t");
+  AppendNodeToString(node->left, string_builder, indent + 2);
+  string_builder->append(indent_builder.toString());
+  string_builder->append("Right:\t");
+  AppendNodeToString(node->right, string_builder, indent + 2);
+  string_builder->append(indent_builder.toString());
+  string_builder->append("Bottom:\t");
+  AppendNodeToString(node->bottom, string_builder, indent + 2);
+}
+
 // Collects all opportunities from leaves of Layout Opportunity spatial tree.
 void CollectAllOpportunities(const NGLayoutOpportunityTreeNode* node,
                              NGLayoutOpportunities& opportunities) {
@@ -128,6 +159,13 @@ NGLayoutOpportunityTreeNode* CreateRightNGLayoutOpportunityTreeNode(
   return nullptr;
 }
 
+void SplitNGLayoutOpportunityTreeNode(const NGLogicalRect& rect,
+                                      NGLayoutOpportunityTreeNode* node) {
+  node->left = CreateLeftNGLayoutOpportunityTreeNode(node, rect);
+  node->right = CreateRightNGLayoutOpportunityTreeNode(node, rect);
+  node->bottom = CreateBottomNGLayoutOpportunityTreeNode(node, rect);
+}
+
 // Gets/Creates the "TOP" positioned constraint space by splitting
 // the parent node with the exclusion.
 //
@@ -149,6 +187,55 @@ NGLayoutOpportunity GetTopSpace(const NGLayoutOpportunity& parent_opportunity,
   return NGLayoutOpportunity();
 }
 
+// Combines 2 exclusions if possible.
+// We can combine 2 exclusions if they
+// - adjoining to each other and have the same exclusion type
+// - new exclusion shadows the old one. That's because it's not allowed to
+//   position anything in the shadowed area.
+//
+//   Example:
+//   <div id="SS" style="float: left; height: 10px; width: 10px"></div>
+//   <div id="BB" style="float: left; height: 20px; width: 20px"></div>
+//   +----------------+
+//   |SSBB
+//   |**BB
+//   We combine SS and BB exclusions including the shadowed area (**).
+bool MaybeCombineExclusions(const NGExclusion& in_exclusion,

[cbiesinger, 2017/03/07 19:10:42]

I had a bit of a hard time keeping track of in and out and which one is which.
May I suggest:

  MaybeCombineExclusionInto(const NGExclusion& new_exclusion,
                            NGExclusion* into_exclusion)

or something like that?

+                            NGExclusion* out_exclusion) {
+  NGLogicalRect in_rect = in_exclusion.rect;
+  NGLogicalRect& out_rect = out_exclusion->rect;
+
+  switch (in_exclusion.type) {
+    case NGExclusion::kFloatLeft: {
+      NGLogicalOffset out_rect_top_right = {out_rect.InlineEndOffset(),
+                                            out_rect.BlockStartOffset()};
+      if (out_exclusion->type == NGExclusion::kFloatLeft &&
+          in_rect.offset == out_rect_top_right &&
+          in_rect.BlockEndOffset() >= out_rect.BlockEndOffset()) {
+        out_rect.size = {in_rect.InlineSize() + out_rect.InlineSize(),
+                         in_rect.BlockSize()};
+        return true;
+      }
+    }
+    case NGExclusion::kFloatRight: {
+      NGLogicalOffset in_rect_top_right = {in_rect.InlineEndOffset(),
+                                           in_rect.BlockStartOffset()};
+      if (out_exclusion->type == NGExclusion::kFloatRight &&
+          out_rect.offset == in_rect_top_right &&
+          in_rect.BlockEndOffset() >= out_rect.BlockEndOffset()) {
+        out_rect.offset = in_rect.offset;
+        out_rect.size = {in_rect.InlineSize() + out_rect.InlineSize(),
+                         in_rect.BlockSize()};
+        return true;
+      }
+    }
+    default:
+      NOTREACHED();
+      return false;
+  }
+  return false;
+}
+
 // Inserts the exclusion into the Layout Opportunity tree.
 void InsertExclusion(NGLayoutOpportunityTreeNode* node,
                      const NGExclusion* exclusion,
@@ -165,24 +252,29 @@ void InsertExclusion(NGLayoutOpportunityTreeNode* node,
   if (!exclusion->rect.IsContained(node->opportunity))
     return;
 
-  if (node->exclusion) {
-    InsertExclusion(node->left, exclusion, opportunities);
-    InsertExclusion(node->bottom, exclusion, opportunities);
-    InsertExclusion(node->right, exclusion, opportunities);
+  if (node->exclusions.isEmpty()) {
+    SplitNGLayoutOpportunityTreeNode(exclusion->rect, node);
+
+    NGLayoutOpportunity top_layout_opp =
+        GetTopSpace(node->opportunity, exclusion->rect);
+    if (!top_layout_opp.IsEmpty())
+      opportunities.push_back(top_layout_opp);
+
+    node->exclusions.push_back(exclusion);
+    node->combined_exclusion = WTF::makeUnique<NGExclusion>(*exclusion);
     return;
   }
 
-  // Split the current node.
-  node->left = CreateLeftNGLayoutOpportunityTreeNode(node, exclusion->rect);
-  node->right = CreateRightNGLayoutOpportunityTreeNode(node, exclusion->rect);
-  node->bottom = CreateBottomNGLayoutOpportunityTreeNode(node, exclusion->rect);
+  DCHECK(!node->exclusions.isEmpty());
 
-  NGLayoutOpportunity top_layout_opp =
-      GetTopSpace(node->opportunity, exclusion->rect);
-  if (!top_layout_opp.IsEmpty())
-    opportunities.push_back(top_layout_opp);
-
-  node->exclusion = exclusion;
+  if (MaybeCombineExclusions(*exclusion, node->combined_exclusion.get())) {
+    SplitNGLayoutOpportunityTreeNode(node->combined_exclusion->rect, node);
+    node->exclusions.push_back(exclusion);
+  } else {
+    InsertExclusion(node->left, exclusion, opportunities);
+    InsertExclusion(node->bottom, exclusion, opportunities);
+    InsertExclusion(node->right, exclusion, opportunities);
+  }
 }
 
 // Compares exclusions by their top position.
@@ -275,4 +367,13 @@ const NGLayoutOpportunity NGLayoutOpportunityIterator::Next() {
   return NGLayoutOpportunity(*opportunity);
 }
 
+#ifndef NDEBUG
+void NGLayoutOpportunityIterator::ShowLayoutOpportunityTree() const {
+  StringBuilder string_builder;
+  string_builder.append("\n.:: LayoutOpportunity Tree ::.\n\nRoot Node: ");
+  AppendNodeToString(opportunity_tree_root_.get(), &string_builder);
+  fprintf(stderr, "%s\n", string_builder.toString().utf8().data());
+}
+#endif
+
 }  // namespace blink