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 |