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 {
namespace {

// Collects all opportunities from leaves of Layout Opportunity spatial tree.
void CollectAllOpportunities(const NGLayoutOpportunityTreeNode* node,
                             NGLayoutOpportunities& opportunities) {
  if (!node)
    return;
  if (node->IsLeafNode())
    opportunities.append(node->opportunity);
  CollectAllOpportunities(node->left, opportunities);
  CollectAllOpportunities(node->bottom, opportunities);
  CollectAllOpportunities(node->right, opportunities);
}

// Whether 2 edges overlap with each other.
bool IsOverlapping(const NGEdge& edge1, const NGEdge& edge2) {
  return std::max(edge1.start, edge2.start) <= std::min(edge1.end, edge2.end);
}

// Whether the exclusion is out of bounds of the LayoutNG constraint space.
bool IsExclusionWithinSpace(const NGLayoutOpportunity& opportunity,
                            const NGExclusion& exclusion) {
  LayoutUnit left = opportunity.offset.inline_offset;
  LayoutUnit top = opportunity.offset.block_offset;
  LayoutUnit right = left + opportunity.size.inline_size;
  LayoutUnit bottom = top + opportunity.size.block_size;

  return !(exclusion.Right() <= left || exclusion.Bottom() <= top ||
           exclusion.Left() >= right || exclusion.Top() >= bottom);
}

// Creates the *BOTTOM* positioned Layout Opportunity tree node by splitting
// the parent node with the exclusion.
//
// @param parent_node Node that needs to be split.
// @param exclusion Exclusion existed in the parent node constraint space.
// @return New node or nullptr if the new block size == 0.
NGLayoutOpportunityTreeNode* CreateBottomNGLayoutOpportunityTreeNode(
    const NGLayoutOpportunityTreeNode* parent_node,
    const NGExclusion& exclusion) {
  const NGLayoutOpportunity& parent_opportunity = parent_node->opportunity;
  LayoutUnit left = parent_opportunity.offset.inline_offset;
  LayoutUnit top = exclusion.Bottom();
  LayoutUnit right = left + parent_opportunity.size.inline_size;
  LayoutUnit bottom = parent_opportunity.offset.block_offset +
                      parent_opportunity.size.block_size;

  NGEdge exclusion_edge = {exclusion.Left(), exclusion.Right()};
  LayoutUnit block_size = bottom - top;
  if (block_size > 0) {
    NGLayoutOpportunity opportunity(left, top, right - left, block_size);
    return new NGLayoutOpportunityTreeNode(opportunity, exclusion_edge);
  }
  return nullptr;
}

// Creates the *LEFT* positioned Layout Opportunity tree node by splitting
// the parent node with the exclusion.
//
// @param parent_node Node that needs to be split.
// @param exclusion Exclusion existed in the parent node constraint space.
// @return New node or nullptr if the new inline size == 0 or the parent's
// exclusion edge doesn't limit the new node's constraint space.
NGLayoutOpportunityTreeNode* CreateLeftNGLayoutOpportunityTreeNode(
    const NGLayoutOpportunityTreeNode* parent_node,
    const NGExclusion& exclusion) {
  const NGLayoutOpportunity& parent_opportunity = parent_node->opportunity;
  LayoutUnit left = parent_opportunity.offset.inline_offset;
  LayoutUnit top = parent_opportunity.offset.block_offset;
  LayoutUnit right = exclusion.Left();
  LayoutUnit bottom = top + parent_opportunity.size.block_size;

  NGEdge node_edge = {left, right};
  LayoutUnit inline_size = right - left;
  if (inline_size > 0 &&
      IsOverlapping(parent_node->exclusion_edge, node_edge)) {
    NGLayoutOpportunity opportunity(left, top, inline_size, bottom - top);
    return new NGLayoutOpportunityTreeNode(opportunity);
  }
  return nullptr;
}

// Creates the *RIGHT* positioned Layout Opportunity tree node by splitting
// the parent node with the exclusion.
//
// @param parent_node Node that needs to be split.
// @param exclusion Exclusion existed in the parent node constraint space.
// @return New node or nullptr if the new inline size == 0 or the parent's
// exclusion edge doesn't limit the new node's constraint space.
NGLayoutOpportunityTreeNode* CreateRightNGLayoutOpportunityTreeNode(
    const NGLayoutOpportunityTreeNode* parent_node,
    const NGExclusion& exclusion) {
  const NGLayoutOpportunity& parent_opportunity = parent_node->opportunity;
  LayoutUnit left = exclusion.Right();
  LayoutUnit top = parent_opportunity.offset.block_offset;
  LayoutUnit right = parent_opportunity.offset.inline_offset +
                     parent_opportunity.size.inline_size;
  LayoutUnit bottom = top + parent_opportunity.size.block_size;

  NGEdge node_edge = {left, right};
  LayoutUnit inline_size = right - left;
  if (inline_size > 0 &&
      IsOverlapping(parent_node->exclusion_edge, node_edge)) {
    NGLayoutOpportunity opportunity(left, top, inline_size, bottom - top);
    return new NGLayoutOpportunityTreeNode(opportunity);
  }
  return nullptr;
}

// Gets/Creates the "TOP" positioned constraint space by splitting
// the parent node with the exclusion.
//
// @param parent_node Node that needs to be split.
// @param exclusion Exclusion existed in the parent node constraint space.
// @return New node or nullptr if the new block size == 0.
NGLayoutOpportunity GetTopSpace(const NGLayoutOpportunity& rect,
                                const NGExclusion& exclusion) {
  LayoutUnit left = rect.offset.inline_offset;
  LayoutUnit top = rect.offset.block_offset;
  LayoutUnit right = left + rect.size.inline_size;
  LayoutUnit bottom = exclusion.Top();

  LayoutUnit block_size = bottom - top;
  if (block_size > 0)
    return NGLayoutOpportunity(left, top, right - left, block_size);

  return NGLayoutOpportunity();
}

// Inserts the exclusion into the Layout Opportunity tree.
void InsertExclusion(NGLayoutOpportunityTreeNode* node,
                     const NGExclusion* exclusion,
                     NGLayoutOpportunities& opportunities) {
  // Base case: there is no node.
  if (!node)
    return;

  // Base case: exclusion is not in the node's constraint space.
  if (!IsExclusionWithinSpace(node->opportunity, *exclusion))
    return;

  if (node->exclusion) {
    InsertExclusion(node->left, exclusion, opportunities);
    InsertExclusion(node->bottom, exclusion, opportunities);
    InsertExclusion(node->right, exclusion, opportunities);
    return;
  }

  // Split the current node.
  node->left = CreateLeftNGLayoutOpportunityTreeNode(node, *exclusion);
  node->right = CreateRightNGLayoutOpportunityTreeNode(node, *exclusion);
  node->bottom = CreateBottomNGLayoutOpportunityTreeNode(node, *exclusion);

  NGLayoutOpportunity top_layout_opp =
      GetTopSpace(node->opportunity, *exclusion);
  if (!top_layout_opp.IsEmpty())
    opportunities.append(top_layout_opp);

  node->exclusion = exclusion;
}

// Compares exclusions by their top position.
bool CompareNGExclusionsByTopAsc(const Member<const NGExclusion>& lhs,
                                 const Member<const NGExclusion>& rhs) {
  return rhs->Top() > lhs->Top();
}

// Compares Layout Opportunities by Start Point.
// Start point is a TopLeft position from where inline content can potentially
// start positioning itself.
bool CompareNGLayoutOpportunitesByStartPoint(const NGLayoutOpportunity& lhs,
                                             const NGLayoutOpportunity& rhs) {
  // sort by TOP.
  if (rhs.offset.block_offset > lhs.offset.block_offset) {
    return true;
  }
  if (rhs.offset.block_offset < lhs.offset.block_offset) {
    return false;
  }

  // TOP is the same -> Sort by LEFT
  if (rhs.offset.inline_offset > lhs.offset.inline_offset) {
    return true;
  }
  if (rhs.offset.inline_offset < lhs.offset.inline_offset) {
    return false;
  }

  // TOP and LEFT are the same -> Sort by width
  return rhs.size.inline_size < lhs.size.inline_size;
}

}  // namespace

NGLayoutOpportunityIterator::NGLayoutOpportunityIterator(
    NGConstraintSpace* space,
    const NGLogicalOrigin origin_point,
    const NGLogicalLeader leader_point)
    : constraint_space_(space),
      origin_point_(origin_point),
      leader_point_(leader_point) {
  // TODO(chrome-layout-team): Combine exclusions that shadow each other.
  auto exclusions = constraint_space_->PhysicalSpace()->Exclusions();
  DCHECK(std::is_sorted(exclusions.begin(), exclusions.end(),
                        &CompareNGExclusionsByTopAsc))
      << "Exclusions are expected to be sorted by TOP";

  opportunity_tree_root_ = new NGLayoutOpportunityTreeNode(NGLayoutOpportunity(
      space->Offset().inline_offset, space->Offset().block_offset,
      space->Size().inline_size, space->Size().block_size));

  for (const auto exclusion : exclusions) {
    InsertExclusion(MutableOpportunityTreeRoot(), exclusion, opportunities_);
  }
  CollectAllOpportunities(OpportunityTreeRoot(), opportunities_);
  std::sort(opportunities_.begin(), opportunities_.end(),
            &CompareNGLayoutOpportunitesByStartPoint);
  opportunity_iter_ = opportunities_.begin();
}

const NGLayoutOpportunity NGLayoutOpportunityIterator::Next() {
  if (opportunity_iter_ == opportunities_.end())
    return NGLayoutOpportunity();
  auto* opportunity = opportunity_iter_;
  opportunity_iter_++;
  return NGLayoutOpportunity(*opportunity);
}

}  // namespace blink