third_party/WebKit/Source/core/layout/ng/ng_layout_opportunity_iterator.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_layout_opportunity_iterator.h"

#include "core/layout/ng/ng_physical_constraint_space.h"
#include "core/layout/ng/ng_units.h"
#include "wtf/NonCopyingSort.h"

namespace blink {

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() {
  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