// 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 "third_party/blink/renderer/core/layout/ng/exclusions/ng_exclusion_space.h"

#include "third_party/blink/renderer/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) {
  if (shelf.line_right >= offset.line_offset &&
      shelf.line_left <= offset.line_offset + inline_size)
    return true;
  // Negative available space creates a zero-width opportunity at the inline-end
  // of the shelf. Consider such shelf intersects.
  // TODO(kojii): This is correct to find layout opportunities for zero-width
  // in-flow inline or block objects (e.g., <br>,) but not correct for
  // zero-width floats.
  if (UNLIKELY(shelf.line_left > offset.line_offset ||
               shelf.line_right < offset.line_offset + inline_size))
    return true;
  return false;
}

// 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),
                             other.shape_exclusions);
}

// 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));

  // Max with |start_offset.line_offset| in case the shelf has a negative
  // inline-size.
  NGBfcOffset end_offset(
      std::max(std::min(shelf.line_right, offset.line_offset + inline_size),
               start_offset.line_offset),
      LayoutUnit::Max());

  return NGLayoutOpportunity(
      NGBfcRect(start_offset, end_offset),
      shelf.has_shape_exclusions
          ? base::AdoptRef(new NGShapeExclusions(*shelf.shape_exclusions))
          : nullptr);
}

}  // namespace

NGExclusionSpace::NGExclusionSpace()
    : last_float_block_start_(LayoutUnit::Min()),
      left_float_clear_offset_(LayoutUnit::Min()),
      right_float_clear_offset_(LayoutUnit::Min()) {
  // 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) {
    left_float_clear_offset_ =
        std::max(left_float_clear_offset_, exclusion->rect.BlockEndOffset());
  } else if (exclusion->type == EFloat::kRight) {
    right_float_clear_offset_ =
        std::max(right_float_clear_offset_, exclusion->rect.BlockEndOffset());
  }

  // If the exclusion takes up no inline space, we shouldn't pay any further
  // attention to it. The only thing it can affect is block-axis positioning of
  // subsequent floats (dealt with above).
  if (exclusion->rect.LineEndOffset() <= exclusion->rect.LineStartOffset())
    return;

#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()}),
              shelf.has_shape_exclusions ? base::AdoptRef(new NGShapeExclusions(
                                               *shelf.shape_exclusions))
                                         : nullptr);

          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);
          }
          shelf.shape_exclusions->line_left_shapes.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);
          }
          shelf.shape_exclusions->line_right_shapes.push_back(exclusion);
        }

        // We collect all exclusions in shape_exclusions (even if they don't
        // have any shape data associated with them - normal floats need to be
        // included in the shape line algorithm). We use this bool to track
        // if the shape exclusions should be copied to the resulting layout
        // opportunity.
        if (exclusion->shape_data)
          shelf.has_shape_exclusions = true;

        // Just in case the shelf has a negative inline-size.
        shelf.line_right = std::max(shelf.line_left, shelf.line_right);

        // 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;
        if (is_same_as_previous) {
          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();

  auto* const shelves_end = shelves_.end();
  auto* const 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 prefer 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