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..e69b0575338d95be5ccf403daa9380b720e00935 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,11 +165,128 @@ String NGConstraintSpace::toString() const {
                         size_.block_size.toString().ascii().data());
 }
 
+static 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_(0) {
+  for (auto item : constraint_space_->PhysicalSpace()->Exclusions())
+    filtered_exclusions_.append(item);

[ikilpatrick, 2016/09/06 23:09:40]

I'm assuming:
filtered_exclusions_(constaint_space_->Phy()->Exclusions()) doesn't work b/c
it's a const reference?

[eae, 2016/09/06 23:30:53]

Correct

+
+  nonCopyingSort(filtered_exclusions_.begin(), filtered_exclusions_.end(),
+                 ascendingTopCompare);
+
+  // TODO: Set based on offset once that has been moved to NGConstraintSpace.
+  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) {

[ikilpatrick, 2016/09/06 23:09:40]

I think we'll eventually want to do this in logical b/c writing modes.

[eae, 2016/09/06 23:30:53]

Yeah, I think so too. At least for the inline case/bfc case.

+      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);
+    }
+  }
+}
+
+LayoutUnit NGLayoutOpportunityIterator::heightForOpportunity(

[ikilpatrick, 2016/09/06 23:09:40]

I'd comment this with:

For the given 2d range (opportunity); will return a height which makes it
bounded by the lowest exclusion in the filtered exclusion list

[eae, 2016/09/06 23:30:53]

Good one, done!

+    LayoutUnit left,
+    LayoutUnit top,
+    LayoutUnit right,
+    LayoutUnit bottom) {
+  LayoutUnit minBottom = bottom;

[ikilpatrick, 2016/09/06 23:09:40]

lowestBottom?

[eae, 2016/09/06 23:30:53]

Done.

+  for (const NGExclusion& exclusion : filtered_exclusions_) {
+    if (exclusion.Left() < right && exclusion.Right() > left &&
+        exclusion.Bottom() > top && exclusion.Top() <= minBottom)
+      minBottom = exclusion.Top();
+  }
+  return std::max(minBottom - top, LayoutUnit());
+}
+
+static 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_)

[ikilpatrick, 2016/09/06 23:09:40]

DCHECK? hmm... not sure.

[eae, 2016/09/06 23:30:53]

This is all very temporary...

+    return;
+
+  LayoutUnit opportunityHeight = heightForOpportunity(left, top, right, bottom);
+  if (opportunityHeight && right > left)

[ikilpatrick, 2016/09/06 23:09:40]

explain / rename variables for this magic.

+    addLayoutOpportunity(left, top, right - left, opportunityHeight);
+
+  for (const NGExclusion& exclusion : filtered_exclusions_) {

[ikilpatrick, 2016/09/06 23:09:40]

add comment here.

[eae, 2016/09/06 23:30:53]

Done.

+    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);
+}
+
+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)));
+}
+
 NGConstraintSpace* NGLayoutOpportunityIterator::Next() {

[ikilpatrick, 2016/09/06 23:09:40]

i'd place this right below the ctor, so people know which fn to read next; but
up to you.

[eae, 2016/09/06 23:30:52]

Good idea.

-  auto* exclusions = constraint_space_->PhysicalSpace()->Exclusions();
-  if (!exclusions->head())
+  if (!current_opportunities_.size() &&
+      current_exclusion_ < filtered_exclusions_.size()) {
+    computeForExclusion(current_exclusion_);
+    current_exclusion_++;
+  }
+
+  if (current_opportunities_.size()) {
+    NGConstraintSpace* opportunity = current_opportunities_.last();
+    current_opportunities_.removeLast();
+    return opportunity;
+  }
+
+  if (!filtered_exclusions_.size() && current_exclusion_ == 0) {
+    current_exclusion_++;
     return new NGConstraintSpace(constraint_space_->WritingMode(),
                                  constraint_space_->PhysicalSpace());
+  }
+
   return nullptr;
 }