Initial exclusion aware layout opportunities implementation

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

Index: third_party/WebKit/Source/core/layout/ng/ng_constraint_space.cc
diff --git a/third_party/WebKit/Source/core/layout/ng/ng_constraint_space.cc b/third_party/WebKit/Source/core/layout/ng/ng_constraint_space.cc
index c99af5ce609fdb19377b08686e1b8803c606ca16..1a082738c0b7a242a952796775fbe3fe6e05c500 100644
--- a/third_party/WebKit/Source/core/layout/ng/ng_constraint_space.cc
+++ b/third_party/WebKit/Source/core/layout/ng/ng_constraint_space.cc
@@ -5,6 +5,8 @@
 #include "core/layout/ng/ng_constraint_space.h"
 
 #include "core/layout/ng/ng_units.h"
+#include "wtf/NonCopyingSort.h"
+#include <climits>
 
 namespace blink {
 
@@ -114,10 +116,11 @@ void NGConstraintSpace::Subtract(const NGFragment*) {
   // TODO(layout-ng): Implement.
 }
 
-NGLayoutOpportunityIterator NGConstraintSpace::LayoutOpportunities(
+NGLayoutOpportunityIterator* NGConstraintSpace::LayoutOpportunities(
     unsigned clear,
     bool for_inline_or_bfc) {
-  NGLayoutOpportunityIterator iterator(this, clear, for_inline_or_bfc);
+  NGLayoutOpportunityIterator* iterator =
+      new NGLayoutOpportunityIterator(this, clear, for_inline_or_bfc);
   return iterator;
 }
 
@@ -162,12 +165,139 @@ String NGConstraintSpace::toString() const {
                         size_.block_size.toString().ascii().data());
 }
 
+static inline bool AscendingTopCompare(const NGExclusion& a,
+                                       const NGExclusion& b) {
+  return a.Top() > b.Top();
+}
+
+NGLayoutOpportunityIterator::NGLayoutOpportunityIterator(
+    NGConstraintSpace* space,
+    unsigned clear,
+    bool for_inline_or_bfc)
+    : constraint_space_(space),
+      clear_(clear),
+      for_inline_or_bfc_(for_inline_or_bfc),
+      current_exclusion_idx_(0) {
+  for (const auto& item : constraint_space_->PhysicalSpace()->Exclusions())
+    filtered_exclusions_.append(item);
+
+  nonCopyingSort(filtered_exclusions_.begin(), filtered_exclusions_.end(),
+                 AscendingTopCompare);
+
+  // TODO(eae): Set based on offset.
+  LayoutUnit left;
+  LayoutUnit top;
+
+  unsigned 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) {
+      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() {
-  auto* exclusions = constraint_space_->PhysicalSpace()->Exclusions();
-  if (!exclusions->head())
+  if (current_opportunities_.isEmpty() &&
+      current_exclusion_idx_ < filtered_exclusions_.size()) {
+    computeForExclusion(current_exclusion_idx_);
+    current_exclusion_idx_++;
+  }
+
+  if (!current_opportunities_.isEmpty()) {
+    NGConstraintSpace* opportunity = current_opportunities_.last();
+    current_opportunities_.removeLast();
+    return opportunity;
+  }
+
+  if (filtered_exclusions_.isEmpty() && current_exclusion_idx_ == 0) {
+    current_exclusion_idx_++;
     return new NGConstraintSpace(constraint_space_->WritingMode(),
                                  constraint_space_->PhysicalSpace());
+  }
+
   return nullptr;
 }
 
+static inline bool DescendingWidthCompare(const NGConstraintSpace* a,
+                                          const NGConstraintSpace* b) {
+  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.
+  LayoutUnit right = constraint_space_->Size().inline_size;
+  LayoutUnit bottom = constraint_space_->Size().block_size;
+
+  // 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_)
+    return;
+
+  // Compute opportunity for the full width from the start position to the right
+  // edge of the NGConstraintSpace.
+  LayoutUnit opportunityHeight = heightForOpportunity(left, top, right, bottom);
+  if (opportunityHeight && right > left)
+    addLayoutOpportunity(left, top, right - left, opportunityHeight);
+
+  // 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);
+  }
+
+  nonCopyingSort(current_opportunities_.begin(), current_opportunities_.end(),
+                 DescendingWidthCompare);
+}
+
+// For the given 2D range (opportunity), this will return a height which makes
+// 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(
+    LayoutUnit left,
+    LayoutUnit top,
+    LayoutUnit right,
+    LayoutUnit bottom) {
+  LayoutUnit lowestBottom = bottom;
+  for (const NGExclusion& exclusion : filtered_exclusions_) {
+    if (exclusion.Left() < right && exclusion.Right() > left &&
+        exclusion.Bottom() > top && exclusion.Top() <= lowestBottom)
+      lowestBottom = exclusion.Top();
+  }
+  return std::max(lowestBottom - top, LayoutUnit());
+}
+
+void NGLayoutOpportunityIterator::addLayoutOpportunity(LayoutUnit left,
+                                                       LayoutUnit top,
+                                                       LayoutUnit right,
+                                                       LayoutUnit bottom) {
+  current_opportunities_.append(
+      new NGConstraintSpace(*constraint_space_, NGLogicalOffset(left, top),
+                            NGLogicalSize(right - left, bottom - top)));
+}
+
 }  // namespace blink