Initial exclusion aware layout opportunities implementation

third_party/WebKit/Source/core/layout/ng/ng_constraint_space.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_constraint_space.h"
 
 #include "core/layout/ng/ng_units.h"
+#include "wtf/NonCopyingSort.h"
+#include <climits>
 
 namespace blink {
 
 // TODO: This should set the size of the NGPhysicalConstraintSpace. Or we could
 // remove it requiring that a NGConstraintSpace is created from a
 // NGPhysicalConstraintSpace.
 NGConstraintSpace::NGConstraintSpace(NGWritingMode writing_mode,
                                      NGLogicalSize container_size)
     : physical_space_(new NGPhysicalConstraintSpace(
           container_size.ConvertToPhysical(writing_mode))),
@@ skipping 89 matching lines @@
   return static_cast<NGFragmentationType>(
       writing_mode_ == HorizontalTopBottom
           ? physical_space_->height_direction_fragmentation_type_
           : physical_space_->width_direction_fragmentation_type_);
 }
 
 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;
 }
 
 void NGConstraintSpace::SetOverflowTriggersScrollbar(bool inline_triggers,
                                                      bool block_triggers) {
   if (writing_mode_ == HorizontalTopBottom) {
     physical_space_->width_direction_triggers_scrollbar_ = inline_triggers;
     physical_space_->height_direction_triggers_scrollbar_ = block_triggers;
   } else {
     physical_space_->width_direction_triggers_scrollbar_ = block_triggers;
@@ skipping 24 matching lines @@
     physical_space_->width_direction_triggers_scrollbar_ = type;
   }
 }
 
 String NGConstraintSpace::toString() const {
   return String::format("Size: %s, %s",
                         size_.inline_size.toString().ascii().data(),
                         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;
 }
 
 }  // namespace blink