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

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

 // Copyright 2016 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 "core/layout/ng/ng_layout_opportunity_iterator.h"
 
 #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->exclusion)
+  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");
@@ skipping 111 matching lines @@
     NGLayoutOpportunity opportunity;
     opportunity.offset.inline_offset = exclusion.InlineEndOffset();
     opportunity.offset.block_offset = parent_opportunity.BlockStartOffset();
     opportunity.size.inline_size = right_opportunity_inline_size;
     opportunity.size.block_size = parent_opportunity.BlockSize();
     return new NGLayoutOpportunityTreeNode(opportunity);
   }
   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.
 //
 // @param parent_opportunity Parent opportunity that is being split.
 // @param exclusion Exclusion existed in the parent node constraint space.
 // @return New node or nullptr if the new block size == 0.
 NGLayoutOpportunity GetTopSpace(const NGLayoutOpportunity& parent_opportunity,
                                 const NGLogicalRect& exclusion) {
   LayoutUnit top_opportunity_block_size =
       exclusion.BlockStartOffset() - parent_opportunity.BlockStartOffset();
@@ skipping 17 matching lines @@
     return;
 
   // Base case: there is no node.
   if (!node)
     return;
 
   // Base case: exclusion is not in the node's constraint space.
   if (!exclusion->rect.IsContained(node->opportunity))
     return;
 
-  if (node->exclusion) {
+  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;
+  }
+
+  DCHECK(!node->exclusions.isEmpty());
+
+  if (node->combined_exclusion->MaybeCombineWith(*exclusion)) {
+    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);
-    return;
   }
-
-  // Split the current node.
-  node->left = CreateLeftNGLayoutOpportunityTreeNode(node, exclusion->rect);
-  node->right = CreateRightNGLayoutOpportunityTreeNode(node, exclusion->rect);
-  node->bottom = CreateBottomNGLayoutOpportunityTreeNode(node, exclusion->rect);
-
-  NGLayoutOpportunity top_layout_opp =
-      GetTopSpace(node->opportunity, exclusion->rect);
-  if (!top_layout_opp.IsEmpty())
-    opportunities.push_back(top_layout_opp);
-
-  node->exclusion = exclusion;
 }
 
 // Compares exclusions by their top position.
 bool CompareNGExclusionsByTopAsc(
     const std::unique_ptr<const NGExclusion>& lhs,
     const std::unique_ptr<const NGExclusion>& rhs) {
   return rhs->rect.offset.block_offset > lhs->rect.offset.block_offset;
 }
 
 // Compares Layout Opportunities by Start Point.
@@ skipping 82 matching lines @@
 #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