third_party/WebKit/Source/core/layout/ng/exclusions/ng_exclusion_space.cc - chromium/src - Git at Google

 // Copyright 2017 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/exclusions/ng_exclusion_space.h"

 #include "core/layout/ng/ng_exclusion.h"

 namespace blink {

 namespace {

 // Inserts a layout opportunity into the completed list. The list is ordered by
 // block-start, then by inline-size (shrinking) / block-size (growing).
 //
 // We don't explicitly check the inline-size/block-size of the opportunity as
 // they are always produced in the order.
 void InsertOpportunity(const NGLayoutOpportunity& opportunity,
                        Vector<NGLayoutOpportunity>* opportunities) {
   if (opportunities->IsEmpty()) {
     opportunities->push_back(opportunity);
     return;
   }

   // We go backwards through the list as there is a higher probability that a
   // new opportunity will be at the end of the list.
   for (size_t j = opportunities->size() - 1; j >= 0; --j) {
     const NGLayoutOpportunity& other = opportunities->at(j);
     if (other.rect.BlockStartOffset() <= opportunity.rect.BlockStartOffset()) {
 #if DCHECK_IS_ON()
       // If we have the same block-start offset ensure that the size of the
       // opportunity doesn't violate the order.
       if (other.rect.BlockStartOffset() ==
           opportunity.rect.BlockStartOffset()) {
         DCHECK_LE(other.rect.BlockSize(), opportunity.rect.BlockSize());
         DCHECK_GE(other.rect.InlineSize(), opportunity.rect.InlineSize());
       }
 #endif

       opportunities->insert(j + 1, opportunity);
       return;
     }
   }

   NOTREACHED();
 }

 // Returns true if there is at least one edge between block_start and block_end.
 bool HasSolidEdges(const Vector<scoped_refptr<const NGExclusion>, 1>& edges,
                    LayoutUnit block_start,
                    LayoutUnit block_end) {
   // If there aren't any adjacent exclusions, we must be the initial shelf.
   // This always has "solid" edges on either side.
   if (edges.IsEmpty())
     return true;

   for (const auto& edge : edges) {
     if (edge->rect.BlockEndOffset() > block_start &&
         edge->rect.BlockStartOffset() < block_end)
       return true;
   }

   return false;
 }

 // Adds any edges (other exclusions) which are within the range:
 // (block_offset, LayoutUnit::Max())
 // to the given out_edges vector.
 void CollectSolidEdges(const Vector<scoped_refptr<const NGExclusion>, 1>& edges,
                        LayoutUnit block_offset,
                        Vector<scoped_refptr<const NGExclusion>, 1>* out_edges) {
   for (const auto& edge : edges) {
     if (edge->rect.BlockEndOffset() > block_offset)
       out_edges->push_back(edge);
   }
 }

 // Returns true if the area defined by the given offset and inline_size
 // intersects with the opportunity.
 //
 // We only need to check the block-end of the opportunity is below the given
 // offset, as the given area extends to a block-end of infinity.
 bool Intersects(const NGLayoutOpportunity& opportunity,
                 const NGBfcOffset& offset,
                 const LayoutUnit inline_size) {
   return opportunity.rect.LineEndOffset() > offset.line_offset &&
          opportunity.rect.LineStartOffset() <
              offset.line_offset + inline_size &&
          opportunity.rect.BlockEndOffset() > offset.block_offset;
 }

 // Returns true if the area defined by the given offset and inline_size
 // intersects with the shelfs area.
 //
 // No checks for the block direction are needed as the given area (defined by
 // offset and inline_size) extends to a block-end of infinity, and a shelf also
 // has a block-end of infinity.
 //
 // If the shelf is at -Infinity or +Infinity at either end, the given area
 // always intersects.
 bool Intersects(const NGExclusionSpace::NGShelf& shelf,
                 const NGBfcOffset& offset,
                 const LayoutUnit inline_size) {
   return (shelf.line_right == LayoutUnit::Max() ||
           shelf.line_right > offset.line_offset) &&
          (shelf.line_left == LayoutUnit::Min() ||
           shelf.line_left < offset.line_offset + inline_size);
 }

 // Creates a new layout opportunity. The given layout opportunity *must*
 // intersect with the given area (defined by offset and inline_size).
 NGLayoutOpportunity CreateLayoutOpportunity(const NGLayoutOpportunity& other,
                                             const NGBfcOffset& offset,
                                             const LayoutUnit inline_size) {
   DCHECK(Intersects(other, offset, inline_size));

   NGBfcOffset start_offset(
       std::max(other.rect.LineStartOffset(), offset.line_offset),
       std::max(other.rect.start_offset.block_offset, offset.block_offset));

   NGBfcOffset end_offset(
       std::min(other.rect.LineEndOffset(), offset.line_offset + inline_size),
       other.rect.BlockEndOffset());

   return NGLayoutOpportunity(NGBfcRect(start_offset, end_offset));
 }

 // Creates a new layout opportunity. The given shelf *must* intersect with the
 // given area (defined by offset and inline_size).
 NGLayoutOpportunity CreateLayoutOpportunity(
     const NGExclusionSpace::NGShelf& shelf,
     const NGBfcOffset& offset,
     const LayoutUnit inline_size) {
   DCHECK(Intersects(shelf, offset, inline_size));

   NGBfcOffset start_offset(std::max(shelf.line_left, offset.line_offset),
                            std::max(shelf.block_offset, offset.block_offset));

   NGBfcOffset end_offset(
       std::min(shelf.line_right, offset.line_offset + inline_size),
       LayoutUnit::Max());

   return NGLayoutOpportunity(NGBfcRect(start_offset, end_offset));
 }

 }  // namespace

 NGExclusionSpace::NGExclusionSpace()
     : last_float_block_start_(LayoutUnit::Min()),
       left_float_clear_offset_(LayoutUnit::Min()),
       right_float_clear_offset_(LayoutUnit::Min()),
       has_left_float_(false),
       has_right_float_(false) {
   // The exclusion space must always have at least one shelf, at -Infinity.
   shelves_.push_back(NGShelf(/* block_offset */ LayoutUnit::Min()));
 }

 void NGExclusionSpace::Add(scoped_refptr<const NGExclusion> exclusion) {
   last_float_block_start_ =
       std::max(last_float_block_start_, exclusion->rect.BlockStartOffset());

   const LayoutUnit exclusion_end_offset = exclusion->rect.BlockEndOffset();

   // Update the members used for clearance calculations.
   if (exclusion->type == EFloat::kLeft) {
     has_left_float_ = true;
     left_float_clear_offset_ =
         std::max(left_float_clear_offset_, exclusion->rect.BlockEndOffset());
   } else if (exclusion->type == EFloat::kRight) {
     has_right_float_ = true;
     right_float_clear_offset_ =
         std::max(right_float_clear_offset_, exclusion->rect.BlockEndOffset());
   }

 #if DCHECK_IS_ON()
   bool inserted = false;
 #endif
   // Modify the shelves and opportunities given this new exclusion.
   //
   // NOTE: This could potentially be done lazily when we query the exclusion
   // space for a layout opportunity.
   for (size_t i = 0; i < shelves_.size();) {
     // We modify the current shelf in-place. However we need to keep a copy of
     // the shelf if we need to insert a new shelf later in the loop.
     NGShelf shelf_copy(shelves_[i]);

     bool is_between_shelves;
     bool removed_shelf = false;

     // A new scope is created as shelf may be removed.
     {
       NGShelf& shelf = shelves_[i];

       // Check if the new exclusion will be below this shelf. E.g.
       //
       //    0 1 2 3 4 5 6 7 8
       // 0  +---+
       //    |xxx|
       // 10 |xxx|
       //    X---------------X
       // 20          +---+
       //             |NEW|
       //             +---+
       bool is_below = exclusion->rect.BlockStartOffset() > shelf.block_offset;

       if (is_below) {
         // We may have created a new opportunity, by closing off an area.
         // However we need to check the "edges" of the opportunity are solid.
         //
         //    0 1 2 3 4 5 6 7 8
         // 0  +---+  X----X+---+
         //    |xxx|  .     |xxx|
         // 10 |xxx|  .     |xxx|
         //    +---+  .     +---+
         // 20        .     .
         //      +---+. .+---+
         // 30   |xxx|   |NEW|
         //      |xxx|   +---+
         // 40   +---+
         //
         // In the above example we have three exclusions placed in the space.
         // And we are adding the "NEW" right exclusion.
         //
         // The drawn "shelf" has the internal values:
         // {
         //   block_offset: 0,
         //   line_left: 35,
         //   line_right: 60,
         //   line_left_edges: [{25, 40}],
         //   line_right_edges: [{0, 15}],
         // }
         // The hypothetical opportunity starts at (35,0), and ends at (60,25).
         //
         // The new exclusion *doesn't* create a new layout opportunity, as the
         // left edge doesn't have a solid "edge", i.e. there are no floats
         // against that edge.
         bool has_solid_edges =
             HasSolidEdges(shelf.line_left_edges, shelf.block_offset,
                           exclusion->rect.BlockStartOffset()) &&
             HasSolidEdges(shelf.line_right_edges, shelf.block_offset,
                           exclusion->rect.BlockStartOffset());

         // This just checks if the exclusion overlaps the bounds of the shelf.
         //
         //    0 1 2 3 4 5 6 7 8
         // 0  +---+X------X+---+
         //    |xxx|        |xxx|
         // 10 |xxx|        |xxx|
         //    +---+        +---+
         // 20
         //                  +---+
         // 30               |NEW|
         //                  +---+
         //
         // In the above example the "NEW" exclusion *doesn't* overlap with the
         // above drawn shelf, and a new opportunity hasn't been created.
         bool is_overlapping =
             exclusion->rect.LineStartOffset() < shelf.line_right &&
             exclusion->rect.LineEndOffset() > shelf.line_left;

         // Insert a closed-off layout opportunity if needed.
         if (has_solid_edges && is_overlapping) {
           NGLayoutOpportunity opportunity(NGBfcRect(
               /* start_offset */ {shelf.line_left, shelf.block_offset},
               /* end_offset */ {shelf.line_right,
                                 exclusion->rect.BlockStartOffset()}));

           InsertOpportunity(opportunity, &opportunities_);
         }
       }

       // Check if the new exclusion is going to "cut" (intersect) with this
       // shelf. E.g.
       //
       //    0 1 2 3 4 5 6 7 8
       // 0  +---+
       //    |xxx|
       // 10 |xxx|    +---+
       //    X--------|NEW|--X
       //             +---+
       bool is_intersecting =
           !is_below && exclusion_end_offset > shelf.block_offset;

       // Check if we need to insert a new shelf between two other shelves. E.g.
       // two other shelves. E.g.
       //
       //    0 1 2 3 4 5 6 7 8
       // 0  +-----+X----X+---+
       //    |xxxxx|      |xxx|
       // 10 +-----+      |xxx|
       //      +---+      |xxx|
       // 20   |NEW|      |xxx|
       //    X-----------X|xxx|
       // 30              |xxx|
       //    X----------------X
       //
       // In the above example the "NEW" left exclusion creates a shelf between
       // the two other shelves drawn.
       //
       // NOTE: We calculate this before we need it as the next if-statement
       // block may remove the shelf that we need to check against.
       //
       // NOTE: If there is no "next" shelf, we consider this between shelves.
       is_between_shelves =
           exclusion_end_offset >= shelf.block_offset &&
           (i + 1 >= shelves_.size() ||
            exclusion_end_offset < shelves_[i + 1].block_offset);

       // We need to reduce the size of the shelf.
       if (is_below || is_intersecting) {
         if (exclusion->type == EFloat::kLeft) {
           if (exclusion->rect.LineEndOffset() >= shelf.line_left) {
             // The edges need to be cleared if it pushes the shelf edge in.
             if (exclusion->rect.LineEndOffset() > shelf.line_left)
               shelf.line_left_edges.clear();
             shelf.line_left = exclusion->rect.LineEndOffset();
             shelf.line_left_edges.push_back(exclusion);
           }
         } else {
           DCHECK_EQ(exclusion->type, EFloat::kRight);
           if (exclusion->rect.LineStartOffset() <= shelf.line_right) {
             // The edges need to be cleared if it pushes the shelf edge in.
             if (exclusion->rect.LineStartOffset() < shelf.line_right)
               shelf.line_right_edges.clear();
             shelf.line_right = exclusion->rect.LineStartOffset();
             shelf.line_right_edges.push_back(exclusion);
           }
         }

         // We can end up in a situation where a shelf is the same as the
         // previous one. For example:
         //
         //    0 1 2 3 4 5 6 7 8
         // 0  +---+X----------X
         //    |xxx|
         // 10 |xxx|
         //    X---------------X
         // 20
         //      +---+
         // 30   |NEW|
         //      +---+
         //
         // In the above example "NEW" will shrink the two shelves by the same
         // amount. We remove the current shelf we are working on.
         bool is_same_as_previous =
             (i > 0) && shelf.line_left == shelves_[i - 1].line_left &&
             shelf.line_right == shelves_[i - 1].line_right;

         // The shelf also may now be non-existent.
         bool shelf_has_zero_size = shelf.line_right <= shelf.line_left;

         if (is_same_as_previous || shelf_has_zero_size) {
           shelves_.EraseAt(i);
           removed_shelf = true;
         }
       }
     }

     if (is_between_shelves) {
 #if DCHECK_IS_ON()
       DCHECK(!inserted);
       inserted = true;
 #endif

       // We only want to add the shelf if it's at a different block offset.
       if (exclusion_end_offset != shelf_copy.block_offset) {
         NGShelf new_shelf(/* block_offset */ exclusion_end_offset);

         CollectSolidEdges(shelf_copy.line_left_edges, new_shelf.block_offset,
                           &new_shelf.line_left_edges);

         CollectSolidEdges(shelf_copy.line_right_edges, new_shelf.block_offset,
                           &new_shelf.line_right_edges);

         // If we didn't find any edges, the line_left/line_right of the shelf
         // are pushed out to be the minimum/maximum.
         new_shelf.line_left = new_shelf.line_left_edges.IsEmpty()
                                   ? LayoutUnit::Min()
                                   : shelf_copy.line_left;
         new_shelf.line_right = new_shelf.line_right_edges.IsEmpty()
                                    ? LayoutUnit::Max()
                                    : shelf_copy.line_right;

         size_t insert_index = removed_shelf ? i : i + 1;
         shelves_.insert(insert_index, new_shelf);
       }

       // It's safe to early exit out of this loop now. This exclusion won't
       // have any effect on subsequent shelves.
       break;
     }

     if (!removed_shelf)
       ++i;
   }

 #if DCHECK_IS_ON()
   // We must have performed a new shelf insertion.
   DCHECK(inserted);
 #endif

   exclusions_.push_back(std::move(exclusion));
 }

 NGLayoutOpportunity NGExclusionSpace::FindLayoutOpportunity(
     const NGBfcOffset& offset,
     const LayoutUnit available_inline_size,
     const NGLogicalSize& minimum_size) const {
   // TODO(ikilpatrick): Determine what to do for a -ve available_inline_size.
   // TODO(ikilpatrick): Change this so that it iterates over the
   // shelves/opportunities instead for querying for all of them.
   Vector<NGLayoutOpportunity> opportunities =
       AllLayoutOpportunities(offset, available_inline_size);

   for (const auto& opportunity : opportunities) {
     // Determine if this opportunity will fit the given size.
     //
     // NOTE: There are cases where the available_inline_size may be smaller
     // than the minimum_size.inline_size. In such cases if the opportunity is
     // the same as the available_inline_size, it pretends that it "fits".
     if ((opportunity.rect.InlineSize() >= minimum_size.inline_size ||
          opportunity.rect.InlineSize() == available_inline_size) &&
         opportunity.rect.BlockSize() >= minimum_size.block_size)
       return opportunity;
   }

   NOTREACHED();
   return NGLayoutOpportunity();
 }

 Vector<NGLayoutOpportunity> NGExclusionSpace::AllLayoutOpportunities(
     const NGBfcOffset& offset,
     const LayoutUnit available_inline_size) const {
   Vector<NGLayoutOpportunity> opportunities;

   auto shelves_it = shelves_.begin();
   auto opps_it = opportunities_.begin();

   const auto shelves_end = shelves_.end();
   const auto opps_end = opportunities_.end();

   while (shelves_it != shelves_end || opps_it != opps_end) {
     // We should never exhaust the opportunities list before the shelves list,
     // as there is always an infinitely sized shelf at the very end.
     DCHECK_NE(shelves_it, shelves_end);
     const NGShelf& shelf = *shelves_it;

     if (!Intersects(shelf, offset, available_inline_size)) {
       ++shelves_it;
       continue;
     }

     if (opps_it != opps_end) {
       const NGLayoutOpportunity& opportunity = *opps_it;

       if (!Intersects(opportunity, offset, available_inline_size)) {
         ++opps_it;
         continue;
       }

       // We always perfer the closed-off opportunity, instead of the shelf
       // opportunity if they exist at the some offset.
       if (opportunity.rect.BlockStartOffset() <= shelf.block_offset) {
         opportunities.push_back(CreateLayoutOpportunity(opportunity, offset,
                                                         available_inline_size));
         ++opps_it;
         continue;
       }
     }

     // We may fall through to here from the above if-statement.
     bool has_solid_edges =
         HasSolidEdges(shelf.line_left_edges, offset.block_offset,
                       LayoutUnit::Max()) &&
         HasSolidEdges(shelf.line_right_edges, offset.block_offset,
                       LayoutUnit::Max());
     if (has_solid_edges) {
       opportunities.push_back(
           CreateLayoutOpportunity(shelf, offset, available_inline_size));
     }
     ++shelves_it;
   }

   return opportunities;
 }

 LayoutUnit NGExclusionSpace::ClearanceOffset(EClear clear_type) const {
   switch (clear_type) {
     case EClear::kNone:
       return LayoutUnit::Min();  // Nothing to do here.
     case EClear::kLeft:
       return left_float_clear_offset_;
     case EClear::kRight:
       return right_float_clear_offset_;
     case EClear::kBoth:
       return std::max(left_float_clear_offset_, right_float_clear_offset_);
     default:
       NOTREACHED();
   }

   return LayoutUnit::Min();
 }

 bool NGExclusionSpace::operator==(const NGExclusionSpace& other) const {
   return exclusions_ == other.exclusions_;
 }

 }  // namespace blink
	// Copyright 2017 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/exclusions/ng_exclusion_space.h"

	#include "core/layout/ng/ng_exclusion.h"

	namespace blink {

	namespace {

	// Inserts a layout opportunity into the completed list. The list is ordered by
	// block-start, then by inline-size (shrinking) / block-size (growing).
	//
	// We don't explicitly check the inline-size/block-size of the opportunity as
	// they are always produced in the order.
	void InsertOpportunity(const NGLayoutOpportunity& opportunity,
	Vector<NGLayoutOpportunity>* opportunities) {
	if (opportunities->IsEmpty()) {
	opportunities->push_back(opportunity);
	return;
	}

	// We go backwards through the list as there is a higher probability that a
	// new opportunity will be at the end of the list.
	for (size_t j = opportunities->size() - 1; j >= 0; --j) {
	const NGLayoutOpportunity& other = opportunities->at(j);
	if (other.rect.BlockStartOffset() <= opportunity.rect.BlockStartOffset()) {
	#if DCHECK_IS_ON()
	// If we have the same block-start offset ensure that the size of the
	// opportunity doesn't violate the order.
	if (other.rect.BlockStartOffset() ==
	opportunity.rect.BlockStartOffset()) {
	DCHECK_LE(other.rect.BlockSize(), opportunity.rect.BlockSize());
	DCHECK_GE(other.rect.InlineSize(), opportunity.rect.InlineSize());
	}
	#endif

	opportunities->insert(j + 1, opportunity);
	return;
	}
	}

	NOTREACHED();
	}

	// Returns true if there is at least one edge between block_start and block_end.
	bool HasSolidEdges(const Vector<scoped_refptr<const NGExclusion>, 1>& edges,
	LayoutUnit block_start,
	LayoutUnit block_end) {
	// If there aren't any adjacent exclusions, we must be the initial shelf.
	// This always has "solid" edges on either side.
	if (edges.IsEmpty())
	return true;

	for (const auto& edge : edges) {
	if (edge->rect.BlockEndOffset() > block_start &&
	edge->rect.BlockStartOffset() < block_end)
	return true;
	}

	return false;
	}

	// Adds any edges (other exclusions) which are within the range:
	// (block_offset, LayoutUnit::Max())
	// to the given out_edges vector.
	void CollectSolidEdges(const Vector<scoped_refptr<const NGExclusion>, 1>& edges,
	LayoutUnit block_offset,
	Vector<scoped_refptr<const NGExclusion>, 1>* out_edges) {
	for (const auto& edge : edges) {
	if (edge->rect.BlockEndOffset() > block_offset)
	out_edges->push_back(edge);
	}
	}

	// Returns true if the area defined by the given offset and inline_size
	// intersects with the opportunity.
	//
	// We only need to check the block-end of the opportunity is below the given
	// offset, as the given area extends to a block-end of infinity.
	bool Intersects(const NGLayoutOpportunity& opportunity,
	const NGBfcOffset& offset,
	const LayoutUnit inline_size) {
	return opportunity.rect.LineEndOffset() > offset.line_offset &&
	opportunity.rect.LineStartOffset() <
	offset.line_offset + inline_size &&
	opportunity.rect.BlockEndOffset() > offset.block_offset;
	}

	// Returns true if the area defined by the given offset and inline_size
	// intersects with the shelfs area.
	//
	// No checks for the block direction are needed as the given area (defined by
	// offset and inline_size) extends to a block-end of infinity, and a shelf also
	// has a block-end of infinity.
	//
	// If the shelf is at -Infinity or +Infinity at either end, the given area
	// always intersects.
	bool Intersects(const NGExclusionSpace::NGShelf& shelf,
	const NGBfcOffset& offset,
	const LayoutUnit inline_size) {
	return (shelf.line_right == LayoutUnit::Max() \|\|
	shelf.line_right > offset.line_offset) &&
	(shelf.line_left == LayoutUnit::Min() \|\|
	shelf.line_left < offset.line_offset + inline_size);
	}

	// Creates a new layout opportunity. The given layout opportunity must
	// intersect with the given area (defined by offset and inline_size).
	NGLayoutOpportunity CreateLayoutOpportunity(const NGLayoutOpportunity& other,
	const NGBfcOffset& offset,
	const LayoutUnit inline_size) {
	DCHECK(Intersects(other, offset, inline_size));

	NGBfcOffset start_offset(
	std::max(other.rect.LineStartOffset(), offset.line_offset),
	std::max(other.rect.start_offset.block_offset, offset.block_offset));

	NGBfcOffset end_offset(
	std::min(other.rect.LineEndOffset(), offset.line_offset + inline_size),
	other.rect.BlockEndOffset());

	return NGLayoutOpportunity(NGBfcRect(start_offset, end_offset));
	}

	// Creates a new layout opportunity. The given shelf must intersect with the
	// given area (defined by offset and inline_size).
	NGLayoutOpportunity CreateLayoutOpportunity(
	const NGExclusionSpace::NGShelf& shelf,
	const NGBfcOffset& offset,
	const LayoutUnit inline_size) {
	DCHECK(Intersects(shelf, offset, inline_size));

	NGBfcOffset start_offset(std::max(shelf.line_left, offset.line_offset),
	std::max(shelf.block_offset, offset.block_offset));

	NGBfcOffset end_offset(
	std::min(shelf.line_right, offset.line_offset + inline_size),
	LayoutUnit::Max());

	return NGLayoutOpportunity(NGBfcRect(start_offset, end_offset));
	}

	} // namespace

	NGExclusionSpace::NGExclusionSpace()
	: last_float_block_start_(LayoutUnit::Min()),
	left_float_clear_offset_(LayoutUnit::Min()),
	right_float_clear_offset_(LayoutUnit::Min()),
	has_left_float_(false),
	has_right_float_(false) {
	// The exclusion space must always have at least one shelf, at -Infinity.
	shelves_.push_back(NGShelf(/* block_offset */ LayoutUnit::Min()));
	}

	void NGExclusionSpace::Add(scoped_refptr<const NGExclusion> exclusion) {
	last_float_block_start_ =
	std::max(last_float_block_start_, exclusion->rect.BlockStartOffset());

	const LayoutUnit exclusion_end_offset = exclusion->rect.BlockEndOffset();

	// Update the members used for clearance calculations.
	if (exclusion->type == EFloat::kLeft) {
	has_left_float_ = true;
	left_float_clear_offset_ =
	std::max(left_float_clear_offset_, exclusion->rect.BlockEndOffset());
	} else if (exclusion->type == EFloat::kRight) {
	has_right_float_ = true;
	right_float_clear_offset_ =
	std::max(right_float_clear_offset_, exclusion->rect.BlockEndOffset());
	}

	#if DCHECK_IS_ON()
	bool inserted = false;
	#endif
	// Modify the shelves and opportunities given this new exclusion.
	//
	// NOTE: This could potentially be done lazily when we query the exclusion
	// space for a layout opportunity.
	for (size_t i = 0; i < shelves_.size();) {
	// We modify the current shelf in-place. However we need to keep a copy of
	// the shelf if we need to insert a new shelf later in the loop.
	NGShelf shelf_copy(shelves_[i]);

	bool is_between_shelves;
	bool removed_shelf = false;

	// A new scope is created as shelf may be removed.
	{
	NGShelf& shelf = shelves_[i];

	// Check if the new exclusion will be below this shelf. E.g.
	//
	// 0 1 2 3 4 5 6 7 8
	// 0 +---+
	// \|xxx\|
	// 10 \|xxx\|
	// X---------------X
	// 20 +---+
	// \|NEW\|
	// +---+
	bool is_below = exclusion->rect.BlockStartOffset() > shelf.block_offset;

	if (is_below) {
	// We may have created a new opportunity, by closing off an area.
	// However we need to check the "edges" of the opportunity are solid.
	//
	// 0 1 2 3 4 5 6 7 8
	// 0 +---+ X----X+---+
	// \|xxx\| . \|xxx\|
	// 10 \|xxx\| . \|xxx\|
	// +---+ . +---+
	// 20 . .
	// +---+. .+---+
	// 30 \|xxx\| \|NEW\|
	// \|xxx\| +---+
	// 40 +---+
	//
	// In the above example we have three exclusions placed in the space.
	// And we are adding the "NEW" right exclusion.
	//
	// The drawn "shelf" has the internal values:
	// {
	// block_offset: 0,
	// line_left: 35,
	// line_right: 60,
	// line_left_edges: [{25, 40}],
	// line_right_edges: [{0, 15}],
	// }
	// The hypothetical opportunity starts at (35,0), and ends at (60,25).
	//
	// The new exclusion doesn't create a new layout opportunity, as the
	// left edge doesn't have a solid "edge", i.e. there are no floats
	// against that edge.
	bool has_solid_edges =
	HasSolidEdges(shelf.line_left_edges, shelf.block_offset,
	exclusion->rect.BlockStartOffset()) &&
	HasSolidEdges(shelf.line_right_edges, shelf.block_offset,
	exclusion->rect.BlockStartOffset());

	// This just checks if the exclusion overlaps the bounds of the shelf.
	//
	// 0 1 2 3 4 5 6 7 8
	// 0 +---+X------X+---+
	// \|xxx\| \|xxx\|
	// 10 \|xxx\| \|xxx\|
	// +---+ +---+
	// 20
	// +---+
	// 30 \|NEW\|
	// +---+
	//
	// In the above example the "NEW" exclusion doesn't overlap with the
	// above drawn shelf, and a new opportunity hasn't been created.
	bool is_overlapping =
	exclusion->rect.LineStartOffset() < shelf.line_right &&
	exclusion->rect.LineEndOffset() > shelf.line_left;

	// Insert a closed-off layout opportunity if needed.
	if (has_solid_edges && is_overlapping) {
	NGLayoutOpportunity opportunity(NGBfcRect(
	/* start_offset */ {shelf.line_left, shelf.block_offset},
	/* end_offset */ {shelf.line_right,
	exclusion->rect.BlockStartOffset()}));

	InsertOpportunity(opportunity, &opportunities_);
	}
	}

	// Check if the new exclusion is going to "cut" (intersect) with this
	// shelf. E.g.
	//
	// 0 1 2 3 4 5 6 7 8
	// 0 +---+
	// \|xxx\|
	// 10 \|xxx\| +---+
	// X--------\|NEW\|--X
	// +---+
	bool is_intersecting =
	!is_below && exclusion_end_offset > shelf.block_offset;

	// Check if we need to insert a new shelf between two other shelves. E.g.
	// two other shelves. E.g.
	//
	// 0 1 2 3 4 5 6 7 8
	// 0 +-----+X----X+---+
	// \|xxxxx\| \|xxx\|
	// 10 +-----+ \|xxx\|
	// +---+ \|xxx\|
	// 20 \|NEW\| \|xxx\|
	// X-----------X\|xxx\|
	// 30 \|xxx\|
	// X----------------X
	//
	// In the above example the "NEW" left exclusion creates a shelf between
	// the two other shelves drawn.
	//
	// NOTE: We calculate this before we need it as the next if-statement
	// block may remove the shelf that we need to check against.
	//
	// NOTE: If there is no "next" shelf, we consider this between shelves.
	is_between_shelves =
	exclusion_end_offset >= shelf.block_offset &&
	(i + 1 >= shelves_.size() \|\|
	exclusion_end_offset < shelves_[i + 1].block_offset);

	// We need to reduce the size of the shelf.
	if (is_below \|\| is_intersecting) {
	if (exclusion->type == EFloat::kLeft) {
	if (exclusion->rect.LineEndOffset() >= shelf.line_left) {
	// The edges need to be cleared if it pushes the shelf edge in.
	if (exclusion->rect.LineEndOffset() > shelf.line_left)
	shelf.line_left_edges.clear();
	shelf.line_left = exclusion->rect.LineEndOffset();
	shelf.line_left_edges.push_back(exclusion);
	}
	} else {
	DCHECK_EQ(exclusion->type, EFloat::kRight);
	if (exclusion->rect.LineStartOffset() <= shelf.line_right) {
	// The edges need to be cleared if it pushes the shelf edge in.
	if (exclusion->rect.LineStartOffset() < shelf.line_right)
	shelf.line_right_edges.clear();
	shelf.line_right = exclusion->rect.LineStartOffset();
	shelf.line_right_edges.push_back(exclusion);
	}
	}

	// We can end up in a situation where a shelf is the same as the
	// previous one. For example:
	//
	// 0 1 2 3 4 5 6 7 8
	// 0 +---+X----------X
	// \|xxx\|
	// 10 \|xxx\|
	// X---------------X
	// 20
	// +---+
	// 30 \|NEW\|
	// +---+
	//
	// In the above example "NEW" will shrink the two shelves by the same
	// amount. We remove the current shelf we are working on.
	bool is_same_as_previous =
	(i > 0) && shelf.line_left == shelves_[i - 1].line_left &&
	shelf.line_right == shelves_[i - 1].line_right;

	// The shelf also may now be non-existent.
	bool shelf_has_zero_size = shelf.line_right <= shelf.line_left;

	if (is_same_as_previous \|\| shelf_has_zero_size) {
	shelves_.EraseAt(i);
	removed_shelf = true;
	}
	}
	}

	if (is_between_shelves) {
	#if DCHECK_IS_ON()
	DCHECK(!inserted);
	inserted = true;
	#endif

	// We only want to add the shelf if it's at a different block offset.
	if (exclusion_end_offset != shelf_copy.block_offset) {
	NGShelf new_shelf(/* block_offset */ exclusion_end_offset);

	CollectSolidEdges(shelf_copy.line_left_edges, new_shelf.block_offset,
	&new_shelf.line_left_edges);

	CollectSolidEdges(shelf_copy.line_right_edges, new_shelf.block_offset,
	&new_shelf.line_right_edges);

	// If we didn't find any edges, the line_left/line_right of the shelf
	// are pushed out to be the minimum/maximum.
	new_shelf.line_left = new_shelf.line_left_edges.IsEmpty()
	? LayoutUnit::Min()
	: shelf_copy.line_left;
	new_shelf.line_right = new_shelf.line_right_edges.IsEmpty()
	? LayoutUnit::Max()
	: shelf_copy.line_right;

	size_t insert_index = removed_shelf ? i : i + 1;
	shelves_.insert(insert_index, new_shelf);
	}

	// It's safe to early exit out of this loop now. This exclusion won't
	// have any effect on subsequent shelves.
	break;
	}

	if (!removed_shelf)
	++i;
	}

	#if DCHECK_IS_ON()
	// We must have performed a new shelf insertion.
	DCHECK(inserted);
	#endif

	exclusions_.push_back(std::move(exclusion));
	}

	NGLayoutOpportunity NGExclusionSpace::FindLayoutOpportunity(
	const NGBfcOffset& offset,
	const LayoutUnit available_inline_size,
	const NGLogicalSize& minimum_size) const {
	// TODO(ikilpatrick): Determine what to do for a -ve available_inline_size.
	// TODO(ikilpatrick): Change this so that it iterates over the
	// shelves/opportunities instead for querying for all of them.
	Vector<NGLayoutOpportunity> opportunities =
	AllLayoutOpportunities(offset, available_inline_size);

	for (const auto& opportunity : opportunities) {
	// Determine if this opportunity will fit the given size.
	//
	// NOTE: There are cases where the available_inline_size may be smaller
	// than the minimum_size.inline_size. In such cases if the opportunity is
	// the same as the available_inline_size, it pretends that it "fits".
	if ((opportunity.rect.InlineSize() >= minimum_size.inline_size \|\|
	opportunity.rect.InlineSize() == available_inline_size) &&
	opportunity.rect.BlockSize() >= minimum_size.block_size)
	return opportunity;
	}

	NOTREACHED();
	return NGLayoutOpportunity();
	}

	Vector<NGLayoutOpportunity> NGExclusionSpace::AllLayoutOpportunities(
	const NGBfcOffset& offset,
	const LayoutUnit available_inline_size) const {
	Vector<NGLayoutOpportunity> opportunities;

	auto shelves_it = shelves_.begin();
	auto opps_it = opportunities_.begin();

	const auto shelves_end = shelves_.end();
	const auto opps_end = opportunities_.end();

	while (shelves_it != shelves_end \|\| opps_it != opps_end) {
	// We should never exhaust the opportunities list before the shelves list,
	// as there is always an infinitely sized shelf at the very end.
	DCHECK_NE(shelves_it, shelves_end);
	const NGShelf& shelf = *shelves_it;

	if (!Intersects(shelf, offset, available_inline_size)) {
	++shelves_it;
	continue;
	}

	if (opps_it != opps_end) {
	const NGLayoutOpportunity& opportunity = *opps_it;

	if (!Intersects(opportunity, offset, available_inline_size)) {
	++opps_it;
	continue;
	}

	// We always perfer the closed-off opportunity, instead of the shelf
	// opportunity if they exist at the some offset.
	if (opportunity.rect.BlockStartOffset() <= shelf.block_offset) {
	opportunities.push_back(CreateLayoutOpportunity(opportunity, offset,
	available_inline_size));
	++opps_it;
	continue;
	}
	}

	// We may fall through to here from the above if-statement.
	bool has_solid_edges =
	HasSolidEdges(shelf.line_left_edges, offset.block_offset,
	LayoutUnit::Max()) &&
	HasSolidEdges(shelf.line_right_edges, offset.block_offset,
	LayoutUnit::Max());
	if (has_solid_edges) {
	opportunities.push_back(
	CreateLayoutOpportunity(shelf, offset, available_inline_size));
	}
	++shelves_it;
	}

	return opportunities;
	}

	LayoutUnit NGExclusionSpace::ClearanceOffset(EClear clear_type) const {
	switch (clear_type) {
	case EClear::kNone:
	return LayoutUnit::Min(); // Nothing to do here.
	case EClear::kLeft:
	return left_float_clear_offset_;
	case EClear::kRight:
	return right_float_clear_offset_;
	case EClear::kBoth:
	return std::max(left_float_clear_offset_, right_float_clear_offset_);
	default:
	NOTREACHED();
	}

	return LayoutUnit::Min();
	}

	bool NGExclusionSpace::operator==(const NGExclusionSpace& other) const {
	return exclusions_ == other.exclusions_;
	}

	} // namespace blink