[LayoutNG] Multi-exclusion aware layout opportunities

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 50281b32ce9846b65029ff0d7fb3dc2c3db65635..a5904534bad78af743ea79c743b399b18be73c7d 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
@@ -10,11 +10,6 @@
 
 namespace blink {
 
-static inline bool AscendingTopCompare(const NGExclusion& a,
-                                       const NGExclusion& b) {
-  return a.Top() > b.Top();
-}
-
 NGLayoutOpportunityIterator::NGLayoutOpportunityIterator(
     NGConstraintSpace* space,
     unsigned clear,
@@ -22,44 +17,50 @@ NGLayoutOpportunityIterator::NGLayoutOpportunityIterator(
     : constraint_space_(space),
       clear_(clear),
       for_inline_or_bfc_(for_inline_or_bfc),
-      current_exclusion_idx_(0) {
+      current_x_(0),
+      current_y_(0) {
+  FilterExclusions();
+  if (!IsValidPosition())
+    NextPosition();
+  ComputeOpportunitiesForPosition();
+}
+
+static inline bool AscendingTopLeftCompare(const NGExclusion& a,
+                                           const NGExclusion& b) {
+  if (a.Top() < b.Top())
+    return true;
+  if (a.Top() > b.Top())
+    return false;
+  return a.Left() < b.Left();
+}
+
+void NGLayoutOpportunityIterator::FilterExclusions() {
+  filtered_exclusions_.clear();
   for (const auto& item : constraint_space_->PhysicalSpace()->Exclusions())
     filtered_exclusions_.append(item);
-
   nonCopyingSort(filtered_exclusions_.begin(), filtered_exclusions_.end(),
-                 AscendingTopCompare);
+                 AscendingTopLeftCompare);
 
-  // TODO(eae): Set based on offset.
-  LayoutUnit left;
-  LayoutUnit top;
+  // TODO(eae): Writing modes.
+  LayoutUnit left = constraint_space_->Offset().inline_offset;
+  LayoutUnit top = constraint_space_->Offset().block_offset;
+  LayoutUnit right = left + constraint_space_->Size().inline_size;
+  LayoutUnit bottom = top + constraint_space_->Size().block_size;
 
-  unsigned i = filtered_exclusions_.size();
+  size_t i = filtered_exclusions_.size();
   while (i--) {
     const NGExclusion& exclusion = filtered_exclusions_[i];
 
-    // Remove items above OR to the left of the start offset as they have no
-    // effect on layout opportunities within this view.
-    if (exclusion.Right() <= left || exclusion.Bottom() <= top) {
+    // Remove items fully outside the view of the current constraint space.
+    if (exclusion.Right() < left || exclusion.Bottom() < top ||
+        exclusion.Left() > right || exclusion.Top() > bottom)
       filtered_exclusions_.remove(i);
-      continue;
-    }
-
-    // Remove items below AND to the right of the current exclusions as they're
-    // occluded and won't affect the layout opportunities.
-    for (unsigned j = filtered_exclusions_.size() - 1; j > i; j--) {
-      const NGExclusion& item = filtered_exclusions_[j];
-      if (item.Top() > exclusion.Top() && item.Left() > exclusion.Left())
-        filtered_exclusions_.remove(j);
-    }
   }
 }
 
 NGConstraintSpace* NGLayoutOpportunityIterator::Next() {
-  if (current_opportunities_.isEmpty() &&
-      current_exclusion_idx_ < filtered_exclusions_.size()) {
-    computeForExclusion(current_exclusion_idx_);
-    current_exclusion_idx_++;
-  }
+  if (current_opportunities_.isEmpty() && NextPosition())
+    ComputeOpportunitiesForPosition();
 
   if (!current_opportunities_.isEmpty()) {
     NGConstraintSpace* opportunity = current_opportunities_.last();
@@ -67,53 +68,129 @@ NGConstraintSpace* NGLayoutOpportunityIterator::Next() {
     return opportunity;
   }
 
-  if (filtered_exclusions_.isEmpty() && current_exclusion_idx_ == 0) {
-    current_exclusion_idx_++;
-    return new NGConstraintSpace(constraint_space_->WritingMode(),
-                                 constraint_space_->Direction(),
-                                 constraint_space_->PhysicalSpace());
-  }
-
   return nullptr;
 }
 
 static inline bool DescendingWidthCompare(const NGConstraintSpace* a,
                                           const NGConstraintSpace* b) {
-  return a->Size().inline_size > b->Size().inline_size;
+  return a->Size().inline_size < b->Size().inline_size;
 }
 
-void NGLayoutOpportunityIterator::computeForExclusion(unsigned index) {
-  current_opportunities_.clear();
-
-  // TODO(eae): Set based on index.
-  LayoutUnit left;
-  LayoutUnit top;
-
-  // TODO(eae): Writing modes.
+bool NGLayoutOpportunityIterator::NextPosition() {
   LayoutUnit right = constraint_space_->Size().inline_size;
   LayoutUnit bottom = constraint_space_->Size().block_size;
 
+  while (current_y_ < bottom) {
+    // Try to find a start position to the right of the current position by
+    // identifying the leftmost applicable right edge.
+    LayoutUnit minRight = right;
+    for (const NGExclusion& exclusion : filtered_exclusions_) {
+      if (exclusion.Top() <= current_y_ && exclusion.Bottom() > current_y_ &&
+          exclusion.Right() > current_x_ && exclusion.Right() < minRight)
+        minRight = exclusion.Right();
+    }
+    current_x_ = minRight;
+
+    // If no valid position was found to the right move down to the next "line".
+    // Reset current_x_ and set current_y_ to the top of the next exclusion down
+    // or the bottom of the closest exclusion, whichever is closest.
+    if (current_x_ == right) {
+      LayoutUnit minBottom = bottom;
+      for (const NGExclusion& exclusion : filtered_exclusions_) {
+        if (exclusion.Top() > current_y_ && exclusion.Top() < minBottom)
+          minBottom = exclusion.Top();
+        if (exclusion.Bottom() > current_y_ && exclusion.Bottom() < minBottom)
+          minBottom = exclusion.Bottom();
+      }
+      current_x_ = LayoutUnit();
+      current_y_ = minBottom;
+    }
+    if (IsValidPosition())
+      return true;
+  }
+
+  return false;
+}
+
+// Checks whether the current position is within an exclusion.
+bool NGLayoutOpportunityIterator::IsValidPosition() {
+  for (const NGExclusion& exclusion : filtered_exclusions_) {
+    if (exclusion.Top() >= current_y_ && exclusion.Bottom() < current_y_ &&
+        exclusion.Left() >= current_x_ && exclusion.Right() < current_x_) {
+      return false;
+    }
+  }
+
+  return true;
+}
+
+void NGLayoutOpportunityIterator::FilterForPosition(Vector<NGExclusion>& out) {
+  out.clear();
+  for (const auto& item : filtered_exclusions_)
+    out.append(item);
+  nonCopyingSort(out.begin(), out.end(), AscendingTopLeftCompare);
+
+  size_t len = out.size();
+  for (size_t i = 0; i < len; i++) {
+    const NGExclusion& exclusion = out[i];
+
+    // Remove items above OR to the left of the start offset as they have no
+    // effect on layout opportunities within this view.
+    if (exclusion.Right() <= current_x_ || exclusion.Bottom() <= current_y_) {
+      out.remove(i);
+      len--;
+      continue;
+    }
+
+    // Remove items below AND to the right of the current exclusions as they're
+    // occluded and won't affect the layout opportunities.
+    for (size_t j = out.size() - 1; j > i; j--) {
+      const NGExclusion& item = out[j];
+      if (item.Top() > exclusion.Top() && item.Left() >= exclusion.Left()) {
+        out.remove(j);
+        len--;
+      }
+    }
+  }
+}
+
+void NGLayoutOpportunityIterator::ComputeOpportunitiesForPosition() {
+  current_opportunities_.clear();
+
+  Vector<NGExclusion> exclusions_for_position;
+  FilterForPosition(exclusions_for_position);
+
   // TODO(eae): Filter based on clear_ and for_inline_or_bfc_. Return early for
   // now to make it clear neither are supported yet.
-  if (clear_ != NGClearNone || !for_inline_or_bfc_)
+  if (clear_ != NGClearNone || !for_inline_or_bfc_) {
     return;
+  }
+
+  // TODO(eae): Writing modes.
+  LayoutUnit left = current_x_;
+  LayoutUnit top = current_y_;
+  LayoutUnit right = constraint_space_->Size().inline_size;
+  LayoutUnit bottom = constraint_space_->Size().block_size;
 
   // Compute opportunity for the full width from the start position to the right
   // edge of the NGConstraintSpace.
-  LayoutUnit opportunityHeight = heightForOpportunity(left, top, right, bottom);
+  LayoutUnit opportunityHeight =
+      heightForOpportunity(exclusions_for_position, left, top, right, bottom);
   if (opportunityHeight && right > left)
-    addLayoutOpportunity(left, top, right - left, opportunityHeight);
+    addLayoutOpportunity(left, top, right, opportunityHeight + top);
 
   // Compute the maximum available height between the current position and the
   // left edge of each exclusion. The distance between the current horizontal
   // position and the left edge of the exclusion determines the width of the
   // opportunity.
-  for (const NGExclusion& exclusion : filtered_exclusions_) {
-    opportunityHeight =
-        heightForOpportunity(left, top, exclusion.Left(), bottom);
-    if (opportunityHeight && exclusion.Left() > left)
-      addLayoutOpportunity(left, top, exclusion.Left() - left,
-                           opportunityHeight);
+  for (const NGExclusion& exclusion : exclusions_for_position) {
+    if (exclusion.Right() > current_x_ && exclusion.Bottom() > current_y_) {
+      opportunityHeight = heightForOpportunity(exclusions_for_position, left,
+                                               top, exclusion.Left(), bottom);
+      if (opportunityHeight && exclusion.Left() > left)
+        addLayoutOpportunity(left, top, exclusion.Left(),
+                             opportunityHeight + top);
+    }
   }
 
   nonCopyingSort(current_opportunities_.begin(), current_opportunities_.end(),
@@ -124,12 +201,13 @@ void NGLayoutOpportunityIterator::computeForExclusion(unsigned index) {
 // it bounded by the highest exclusion in the filtered exclusion list within the
 // range. Returns 0-height for an invalid opportunity (which has zero area).
 LayoutUnit NGLayoutOpportunityIterator::heightForOpportunity(
+    const Vector<NGExclusion>& exclusions_for_position,
     LayoutUnit left,
     LayoutUnit top,
     LayoutUnit right,
     LayoutUnit bottom) {
   LayoutUnit lowestBottom = bottom;
-  for (const NGExclusion& exclusion : filtered_exclusions_) {
+  for (const NGExclusion& exclusion : exclusions_for_position) {
     if (exclusion.Left() < right && exclusion.Right() > left &&
         exclusion.Bottom() > top && exclusion.Top() <= lowestBottom)
       lowestBottom = exclusion.Top();