path: root/chromium/third_party/blink/renderer/core/layout/ng/inline/ng_line_breaker.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 "third_party/blink/renderer/core/layout/ng/inline/ng_line_breaker.h"

#include "base/containers/adapters.h"
#include "third_party/blink/renderer/core/layout/ng/inline/ng_bidi_paragraph.h"
#include "third_party/blink/renderer/core/layout/ng/inline/ng_inline_break_token.h"
#include "third_party/blink/renderer/core/layout/ng/inline/ng_inline_node.h"
#include "third_party/blink/renderer/core/layout/ng/inline/ng_ruby_utils.h"
#include "third_party/blink/renderer/core/layout/ng/inline/ng_text_fragment_builder.h"
#include "third_party/blink/renderer/core/layout/ng/ng_block_break_token.h"
#include "third_party/blink/renderer/core/layout/ng/ng_constraint_space.h"
#include "third_party/blink/renderer/core/layout/ng/ng_floats_utils.h"
#include "third_party/blink/renderer/core/layout/ng/ng_fragment.h"
#include "third_party/blink/renderer/core/layout/ng/ng_length_utils.h"
#include "third_party/blink/renderer/core/layout/ng/ng_positioned_float.h"
#include "third_party/blink/renderer/core/layout/ng/ng_unpositioned_float.h"
#include "third_party/blink/renderer/core/style/computed_style.h"
#include "third_party/blink/renderer/platform/fonts/shaping/shape_result_view.h"
#include "third_party/blink/renderer/platform/fonts/shaping/shaping_line_breaker.h"

namespace blink {

namespace {

// CSS-defined white space characters, excluding the newline character.
// In most cases, the line breaker consider break opportunities are before
// spaces because it handles trailing spaces differently from other normal
// characters, but breaking before newline characters is not desired.
inline bool IsBreakableSpace(UChar c) {
  return c == kSpaceCharacter || c == kTabulationCharacter;
}

inline bool IsAllBreakableSpaces(const String& string,
                                 unsigned start,
                                 unsigned end) {
  DCHECK_GE(end, start);
  return StringView(string, start, end - start)
      .IsAllSpecialCharacters<IsBreakableSpace>();
}

// True if the item is "trailable". Trailable items should be included in the
// line if they are after the soft wrap point.
//
// Note that some items are ambiguous; e.g., text is trailable if it has leading
// spaces, and open tags are trailable if spaces follow. This function returns
// true for such cases.
inline bool IsTrailableItemType(NGInlineItem::NGInlineItemType type) {
  return type != NGInlineItem::kAtomicInline &&
         type != NGInlineItem::kOutOfFlowPositioned &&
         type != NGInlineItem::kListMarker;
}

inline bool CanBreakAfterLast(const NGInlineItemResults& item_results) {
  return !item_results.IsEmpty() && item_results.back().can_break_after;
}

inline bool ShouldCreateLineBox(const NGInlineItemResults& item_results) {
  return !item_results.IsEmpty() && item_results.back().should_create_line_box;
}

inline bool HasUnpositionedFloats(const NGInlineItemResults& item_results) {
  return !item_results.IsEmpty() && item_results.back().has_unpositioned_floats;
}

LayoutUnit ComputeInlineEndSize(const NGConstraintSpace& space,
                                const ComputedStyle* style) {
  DCHECK(style);
  NGBoxStrut margins = ComputeMarginsForSelf(space, *style);
  NGBoxStrut borders = ComputeBordersForInline(*style);
  NGBoxStrut paddings = ComputePadding(space, *style);

  return margins.inline_end + borders.inline_end + paddings.inline_end;
}

bool NeedsAccurateEndPosition(const NGInlineItem& line_end_item) {
  DCHECK(line_end_item.Type() == NGInlineItem::kText ||
         line_end_item.Type() == NGInlineItem::kControl);
  DCHECK(line_end_item.Style());
  const ComputedStyle& line_end_style = *line_end_item.Style();
  return line_end_style.HasBoxDecorationBackground() ||
         !line_end_style.AppliedTextDecorations().IsEmpty();
}

inline bool NeedsAccurateEndPosition(const NGLineInfo& line_info,
                                     const NGInlineItem& line_end_item) {
  return line_info.NeedsAccurateEndPosition() ||
         NeedsAccurateEndPosition(line_end_item);
}

inline void ComputeCanBreakAfter(NGInlineItemResult* item_result,
                                 bool auto_wrap,
                                 const LazyLineBreakIterator& break_iterator) {
  item_result->can_break_after =
      auto_wrap && break_iterator.IsBreakable(item_result->EndOffset());
}

inline void RemoveLastItem(NGLineInfo* line_info) {
  NGInlineItemResults* item_results = line_info->MutableResults();
  DCHECK_GT(item_results->size(), 0u);
  item_results->Shrink(item_results->size() - 1);
}

// To correctly determine if a float is allowed to be on the same line as its
// content, we need to determine if it has any ancestors with inline-end
// padding, border, or margin.
// The inline-end size from all of these ancestors contribute to the "used
// size" of the float, and may cause the float to be pushed down.
LayoutUnit ComputeFloatAncestorInlineEndSize(const NGConstraintSpace& space,
                                             const Vector<NGInlineItem>& items,
                                             wtf_size_t item_index) {
  LayoutUnit inline_end_size;
  for (const NGInlineItem *cur = items.begin() + item_index, *end = items.end();
       cur != end; ++cur) {
    const NGInlineItem& item = *cur;

    if (item.Type() == NGInlineItem::kCloseTag) {
      if (item.HasEndEdge())
        inline_end_size += ComputeInlineEndSize(space, item.Style());
      continue;
    }

    // For this calculation, any open tag (even if its empty) stops this
    // calculation, and allows the float to appear on the same line. E.g.
    // <span style="padding-right: 20px;"><f></f><span></span></span>
    //
    // Any non-empty item also allows the float to be on the same line.
    if (item.Type() == NGInlineItem::kOpenTag || !item.IsEmptyItem())
      break;
  }
  return inline_end_size;
}

void CreateHyphen(NGInlineNode node,
                  WritingMode writing_mode,
                  const NGInlineItem& item,
                  NGInlineItemResult* item_result) {
  DCHECK(item.Style());
  const ComputedStyle& style = *item.Style();
  TextDirection direction = style.Direction();
  item_result->hyphen_string = style.HyphenString();
  HarfBuzzShaper shaper(item_result->hyphen_string);
  item_result->hyphen_shape_result = shaper.Shape(&style.GetFont(), direction);
}

inline void ClearNeedsLayout(const NGInlineItem& item) {
  LayoutObject* layout_object = item.GetLayoutObject();
  if (layout_object->NeedsLayout())
    layout_object->ClearNeedsLayout();
}

}  // namespace

LayoutUnit NGLineBreaker::ComputeAvailableWidth() const {
  LayoutUnit available_width = line_opportunity_.AvailableInlineSize();
  // Available width must be smaller than |LayoutUnit::Max()| so that the
  // position can be larger.
  available_width = std::min(available_width, LayoutUnit::NearlyMax());
  return available_width;
}

NGLineBreaker::NGLineBreaker(NGInlineNode node,
                             NGLineBreakerMode mode,
                             const NGConstraintSpace& space,
                             const NGLineLayoutOpportunity& line_opportunity,
                             const NGPositionedFloatVector& leading_floats,
                             unsigned handled_leading_floats_index,
                             const NGInlineBreakToken* break_token,
                             NGExclusionSpace* exclusion_space)
    : line_opportunity_(line_opportunity),
      node_(node),
      mode_(mode),
      is_first_formatted_line_((!break_token || (!break_token->ItemIndex() &&
                                                 !break_token->TextOffset())) &&
                               node.CanContainFirstFormattedLine()),
      use_first_line_style_(is_first_formatted_line_ &&
                            node.UseFirstLineStyle()),
      in_line_height_quirks_mode_(node.InLineHeightQuirksMode()),
      sticky_images_quirk_(mode != NGLineBreakerMode::kContent &&
                           node.IsStickyImagesQuirkForContentSize()),
      items_data_(node.ItemsData(use_first_line_style_)),
      text_content_(
          !sticky_images_quirk_
              ? items_data_.text_content
              : NGInlineNode::TextContentForStickyImagesQuirk(items_data_)),
      constraint_space_(space),
      exclusion_space_(exclusion_space),
      break_token_(break_token),
      break_iterator_(text_content_),
      shaper_(text_content_),
      spacing_(text_content_),
      leading_floats_(leading_floats),
      handled_leading_floats_index_(handled_leading_floats_index),
      base_direction_(node_.BaseDirection()) {
  available_width_ = ComputeAvailableWidth();
  break_iterator_.SetBreakSpace(BreakSpaceType::kBeforeSpaceRun);

  if (!break_token)
    return;

  const ComputedStyle* line_initial_style = break_token->Style();
  if (UNLIKELY(!line_initial_style)) {
    // Usually an inline break token has the line initial style, but class C
    // breaks and last-resort breaks require a break token to start from the
    // beginning of the block. In that case, the line is still the first
    // formatted line, and the line initial style should be computed from the
    // containing block.
    DCHECK_EQ(break_token->ItemIndex(), 0u);
    DCHECK_EQ(break_token->TextOffset(), 0u);
    DCHECK(!break_token->IsForcedBreak());
    DCHECK_EQ(item_index_, break_token->ItemIndex());
    DCHECK_EQ(offset_, break_token->TextOffset());
    DCHECK_EQ(is_after_forced_break_, break_token->IsForcedBreak());
    return;
  }

  item_index_ = break_token->ItemIndex();
  offset_ = break_token->TextOffset();
  break_iterator_.SetStartOffset(offset_);
  is_after_forced_break_ = break_token->IsForcedBreak();
  items_data_.AssertOffset(item_index_, offset_);
  SetCurrentStyle(*line_initial_style);
}

// Define the destructor here, so that we can forward-declare more in the
// header.
NGLineBreaker::~NGLineBreaker() = default;

inline NGInlineItemResult* NGLineBreaker::AddItem(const NGInlineItem& item,
                                                  unsigned end_offset,
                                                  NGLineInfo* line_info) {
  DCHECK_GE(offset_, item.StartOffset());
  DCHECK_GE(end_offset, offset_);
  DCHECK_LE(end_offset, item.EndOffset());
  NGInlineItemResults* item_results = line_info->MutableResults();
  return &item_results->emplace_back(
      &item, item_index_, NGTextOffset(offset_, end_offset),
      break_anywhere_if_overflow_, ShouldCreateLineBox(*item_results),
      HasUnpositionedFloats(*item_results));
}

inline NGInlineItemResult* NGLineBreaker::AddItem(const NGInlineItem& item,
                                                  NGLineInfo* line_info) {
  return AddItem(item, item.EndOffset(), line_info);
}

// Call |HandleOverflow()| if the position is beyond the available space.
inline bool NGLineBreaker::HandleOverflowIfNeeded(NGLineInfo* line_info) {
  if (state_ == LineBreakState::kContinue && !CanFitOnLine()) {
    HandleOverflow(line_info);
    return true;
  }
  return false;
}

void NGLineBreaker::SetIntrinsicSizeOutputs(
    MaxSizeCache* max_size_cache,
    bool* depends_on_percentage_block_size_out) {
  DCHECK_NE(mode_, NGLineBreakerMode::kContent);
  DCHECK(max_size_cache);
  max_size_cache_ = max_size_cache;
  depends_on_percentage_block_size_out_ = depends_on_percentage_block_size_out;
}

// Compute the base direction for bidi algorithm for this line.
void NGLineBreaker::ComputeBaseDirection() {
  // If 'unicode-bidi' is not 'plaintext', use the base direction of the block.
  if (!previous_line_had_forced_break_ ||
      node_.Style().GetUnicodeBidi() != UnicodeBidi::kPlaintext)
    return;
  // If 'unicode-bidi: plaintext', compute the base direction for each paragraph
  // (separated by forced break.)
  const String& text = Text();
  if (text.Is8Bit())
    return;
  wtf_size_t end_offset = text.find(kNewlineCharacter, offset_);
  base_direction_ = NGBidiParagraph::BaseDirectionForString(
      end_offset == kNotFound
          ? StringView(text, offset_)
          : StringView(text, offset_, end_offset - offset_));
}

// Initialize internal states for the next line.
void NGLineBreaker::PrepareNextLine(NGLineInfo* line_info) {
  // NGLineInfo is not supposed to be re-used because it's not much gain and to
  // avoid rare code path.
  const NGInlineItemResults& item_results = line_info->Results();
  DCHECK(item_results.IsEmpty());

  if (item_index_) {
    // We're past the first line
    previous_line_had_forced_break_ = is_after_forced_break_;
    is_after_forced_break_ = false;
    is_first_formatted_line_ = false;
    use_first_line_style_ = false;
  }

  line_info->SetStartOffset(offset_);
  line_info->SetLineStyle(node_, items_data_, use_first_line_style_);

  DCHECK(!line_info->TextIndent());
  if (line_info->LineStyle().ShouldUseTextIndent(
          is_first_formatted_line_, previous_line_had_forced_break_)) {
    const Length& length = line_info->LineStyle().TextIndent();
    LayoutUnit maximum_value;
    // Ignore percentages (resolve to 0) when calculating min/max intrinsic
    // sizes.
    if (length.IsPercentOrCalc() && mode_ == NGLineBreakerMode::kContent)
      maximum_value = constraint_space_.AvailableSize().inline_size;
    line_info->SetTextIndent(MinimumValueForLength(length, maximum_value));
  }

  // Set the initial style of this line from the line style, if the style from
  // the end of previous line is not available. Example:
  //   <p>...<span>....</span></p>
  // When the line wraps in <span>, the 2nd line needs to start with the style
  // of the <span>.
  if (!current_style_)
    SetCurrentStyle(line_info->LineStyle());
  ComputeBaseDirection();
  line_info->SetBaseDirection(base_direction_);

  // Use 'text-indent' as the initial position. This lets tab positions to align
  // regardless of 'text-indent'.
  position_ = line_info->TextIndent();

  ResetRewindLoopDetector();
}

void NGLineBreaker::NextLine(
    LayoutUnit percentage_resolution_block_size_for_min_max,
    NGLineInfo* line_info) {
  PrepareNextLine(line_info);
  BreakLine(percentage_resolution_block_size_for_min_max, line_info);
  RemoveTrailingCollapsibleSpace(line_info);

  const NGInlineItemResults& item_results = line_info->Results();
#if DCHECK_IS_ON()
  for (const auto& result : item_results)
    result.CheckConsistency(mode_ == NGLineBreakerMode::kMinContent);
#endif

  // We should create a line-box when:
  //  - We have an item which needs a line box (text, etc).
  //  - A list-marker is present, and it would be the last line or last line
  //    before a forced new-line.
  //  - During min/max content sizing (to correctly determine the line width).
  //
  // TODO(kojii): There are cases where we need to PlaceItems() without creating
  // line boxes. These cases need to be reviewed.
  bool should_create_line_box = ShouldCreateLineBox(item_results) ||
                                (has_list_marker_ && line_info->IsLastLine()) ||
                                mode_ != NGLineBreakerMode::kContent ||
                                node_.HasLineEvenIfEmpty();

  if (!should_create_line_box)
    line_info->SetIsEmptyLine();
  line_info->SetEndItemIndex(item_index_);
  DCHECK_NE(trailing_whitespace_, WhitespaceState::kUnknown);
  if (trailing_whitespace_ == WhitespaceState::kPreserved)
    line_info->SetHasTrailingSpaces();

  ComputeLineLocation(line_info);
}

void NGLineBreaker::BreakLine(
    LayoutUnit percentage_resolution_block_size_for_min_max,
    NGLineInfo* line_info) {
  DCHECK(!line_info->IsLastLine());
  const Vector<NGInlineItem>& items = Items();
  state_ = LineBreakState::kContinue;
  trailing_whitespace_ = WhitespaceState::kLeading;
  while (state_ != LineBreakState::kDone) {
    // If we reach at the end of the block, this is the last line.
    DCHECK_LE(item_index_, items.size());
    if (item_index_ == items.size()) {
      // Still check overflow because the last item may have overflowed.
      if (HandleOverflowIfNeeded(line_info) && item_index_ != items.size())
        continue;
      line_info->SetIsLastLine(true);
      return;
    }

    // If |state_| is overflow, break at the earliest break opportunity.
    const NGInlineItemResults& item_results = line_info->Results();
    if (UNLIKELY(state_ == LineBreakState::kOverflow &&
                 CanBreakAfterLast(item_results))) {
      state_ = LineBreakState::kTrailing;
    }

    // Handle trailable items first. These items may not be break before.
    // They (or part of them) may also overhang the available width.
    const NGInlineItem& item = items[item_index_];
    if (item.Type() == NGInlineItem::kText) {
      if (item.Length())
        HandleText(item, line_info);
      else
        HandleEmptyText(item, line_info);
#if DCHECK_IS_ON()
      if (!item_results.IsEmpty())
        item_results.back().CheckConsistency(true);
#endif
      continue;
    }
    if (item.Type() == NGInlineItem::kOpenTag) {
      HandleOpenTag(item, line_info);
      continue;
    }
    if (item.Type() == NGInlineItem::kCloseTag) {
      HandleCloseTag(item, line_info);
      continue;
    }
    if (item.Type() == NGInlineItem::kControl) {
      HandleControlItem(item, line_info);
      continue;
    }
    if (item.Type() == NGInlineItem::kFloating) {
      HandleFloat(item, line_info);
      continue;
    }
    if (item.Type() == NGInlineItem::kBidiControl) {
      HandleBidiControlItem(item, line_info);
      continue;
    }

    // Items after this point are not trailable. If we're trailing, break before
    // any non-trailable items
    DCHECK(!IsTrailableItemType(item.Type()));
    if (state_ == LineBreakState::kTrailing) {
      DCHECK(!line_info->IsLastLine());
      return;
    }

    if (item.Type() == NGInlineItem::kAtomicInline) {
      HandleAtomicInline(item, percentage_resolution_block_size_for_min_max,
                         line_info);
      continue;
    }
    if (item.Type() == NGInlineItem::kOutOfFlowPositioned) {
      HandleOutOfFlowPositioned(item, line_info);
    } else if (item.Length()) {
      NOTREACHED();
      // For other items with text (e.g., bidi controls), use their text to
      // determine the break opportunity.
      NGInlineItemResult* item_result = AddItem(item, line_info);
      item_result->can_break_after =
          break_iterator_.IsBreakable(item_result->EndOffset());
      MoveToNextOf(item);
    } else if (item.Type() == NGInlineItem::kListMarker) {
      NGInlineItemResult* item_result = AddItem(item, line_info);
      has_list_marker_ = true;
      DCHECK(!item_result->can_break_after);
      MoveToNextOf(item);
    } else {
      NOTREACHED();
      MoveToNextOf(item);
    }
  }
}

void NGLineBreaker::ComputeLineLocation(NGLineInfo* line_info) const {
  // Negative margins can make the position negative, but the inline size is
  // always positive or 0.
  LayoutUnit available_width = AvailableWidth();

  // Text measurement is done using floats which may introduce small rounding
  // errors for near-saturated values.
  DCHECK_EQ(position_.Round(), line_info->ComputeWidth().Round());

  line_info->SetWidth(available_width, position_);
  line_info->SetBfcOffset(
      {line_opportunity_.line_left_offset, line_opportunity_.bfc_block_offset});
  if (mode_ == NGLineBreakerMode::kContent)
    line_info->UpdateTextAlign();
}

// Atomic inlines have break opportunities before and after, even when the
// adjacent character is U+00A0 NO-BREAK SPACE character.
bool NGLineBreaker::ShouldForceCanBreakAfter(
    const NGInlineItemResult& item_result) const {
  DCHECK(auto_wrap_);
  DCHECK_EQ(item_result.item->Type(), NGInlineItem::kText);
  const String& text = Text();
  DCHECK_GE(text.length(), item_result.EndOffset());
  if (text.length() <= item_result.EndOffset() ||
      text[item_result.EndOffset()] != kObjectReplacementCharacter)
    return false;
  // This kObjectReplacementCharacter can be any objects, such as a floating or
  // an OOF object. Check if it's really an atomic inline.
  const Vector<NGInlineItem>& items = Items();
  for (const NGInlineItem* item = std::next(item_result.item);
       item != items.end(); ++item) {
    DCHECK_EQ(item->StartOffset(), item_result.EndOffset());
    if (item->Type() == NGInlineItem::kAtomicInline) {
      // Except when sticky images quirk was applied.
      if (UNLIKELY(text[item->StartOffset()] == kNoBreakSpaceCharacter))
        return false;
      return !item->IsRubyRun();
    }
    if (item->EndOffset() > item_result.EndOffset())
      break;
  }
  return false;
}

void NGLineBreaker::HandleText(const NGInlineItem& item,
                               const ShapeResult& shape_result,
                               NGLineInfo* line_info) {
  DCHECK(item.Type() == NGInlineItem::kText ||
         (item.Type() == NGInlineItem::kControl &&
          Text()[item.StartOffset()] == kTabulationCharacter));
  DCHECK_EQ(auto_wrap_, item.Style()->AutoWrap());

  // If we're trailing, only trailing spaces can be included in this line.
  if (UNLIKELY(state_ == LineBreakState::kTrailing)) {
    HandleTrailingSpaces(item, shape_result, line_info);
    return;
  }

  // Skip leading collapsible spaces.
  // Most cases such spaces are handled as trailing spaces of the previous line,
  // but there are some cases doing so is too complex.
  if (trailing_whitespace_ == WhitespaceState::kLeading) {
    if (item.Style()->CollapseWhiteSpace() &&
        Text()[offset_] == kSpaceCharacter) {
      // Skipping one whitespace removes all collapsible spaces because
      // collapsible spaces are collapsed to single space in
      // NGInlineItemBuilder.
      ++offset_;
      if (offset_ == item.EndOffset()) {
        ClearNeedsLayout(item);
        MoveToNextOf(item);
        return;
      }
    }
    // |trailing_whitespace_| will be updated as we read the text.
  }

  // Go to |HandleOverflow()| if the last item overflowed, and we're adding
  // text.
  if (state_ == LineBreakState::kContinue && !CanFitOnLine()) {
    // |HandleOverflow()| expects all trailable items are added. If this text
    // starts with trailable spaces, add them. TODO(kojii): This can be
    // optimzied further. This is necesasry only if |HandleOverflow()| does not
    // rewind, but in most cases it will rewind.
    const String& text = Text();
    if (auto_wrap_ && IsBreakableSpace(text[offset_])) {
      HandleTrailingSpaces(item, shape_result, line_info);
      if (state_ != LineBreakState::kDone) {
        state_ = LineBreakState::kContinue;
        return;
      }
    }
    HandleOverflow(line_info);
    return;
  }

  NGInlineItemResult* item_result = AddItem(item, line_info);
  item_result->should_create_line_box = true;
  // Try to commit |pending_end_overhang_| of a prior NGInlineItemResult.
  // |pending_end_overhang_| doesn't work well with bidi reordering. It's
  // difficult to compute overhang after bidi reordering because it affect
  // line breaking.
  if (maybe_have_end_overhang_)
    position_ -= CommitPendingEndOverhang(line_info);

  if (auto_wrap_) {
    if (mode_ == NGLineBreakerMode::kMinContent &&
        HandleTextForFastMinContent(item_result, item, shape_result,
                                    line_info)) {
      return;
    }

    // Try to break inside of this text item.
    const LayoutUnit available_width = RemainingAvailableWidth();
    BreakResult break_result =
        BreakText(item_result, item, shape_result, available_width,
                  available_width, line_info);
    DCHECK(item_result->shape_result ||
           (break_result == kOverflow && break_anywhere_if_overflow_ &&
            !override_break_anywhere_));
    position_ += item_result->inline_size;
    DCHECK_EQ(break_result == kSuccess, CanFitOnLine());
    MoveToNextOf(*item_result);

    if (break_result == kSuccess) {
      DCHECK(item_result->shape_result);

      // If the break is at the middle of a text item, we know no trailable
      // items follow, only trailable spaces if any. This is very common that
      // shortcut to handling trailing spaces.
      if (item_result->EndOffset() < item.EndOffset())
        return HandleTrailingSpaces(item, shape_result, line_info);

      // The break point found at the end of this text item. Continue looking
      // next items, because the next item maybe trailable, or can prohibit
      // breaking before.
      return;
    }
    DCHECK_EQ(break_result, kOverflow);

    // Handle `overflow-wrap` if it is enabled and if this text item overflows.
    if (UNLIKELY(!item_result->shape_result)) {
      DCHECK(break_anywhere_if_overflow_ && !override_break_anywhere_);
      HandleOverflow(line_info);
      return;
    }

    // If we're seeking for the first break opportunity, update the state.
    if (UNLIKELY(state_ == LineBreakState::kOverflow)) {
      if (item_result->can_break_after)
        state_ = LineBreakState::kTrailing;
      return;
    }

    // If this is all trailable spaces, this item is trailable, and next item
    // maybe too. Don't go to |HandleOverflow()| yet.
    if (IsAllBreakableSpaces(Text(), item_result->StartOffset(),
                             item_result->EndOffset()))
      return;

    HandleOverflow(line_info);
    return;
  }

  // Add until the end of the item if !auto_wrap. In most cases, it's the whole
  // item.
  DCHECK_EQ(item_result->EndOffset(), item.EndOffset());
  if (item_result->StartOffset() == item.StartOffset()) {
    item_result->inline_size =
        shape_result.SnappedWidth().ClampNegativeToZero();
    item_result->shape_result = ShapeResultView::Create(&shape_result);
  } else {
    // <wbr> can wrap even if !auto_wrap. Spaces after that will be leading
    // spaces and thus be collapsed.
    DCHECK(trailing_whitespace_ == WhitespaceState::kLeading &&
           item_result->StartOffset() >= item.StartOffset());
    item_result->shape_result = ShapeResultView::Create(
        &shape_result, item_result->StartOffset(), item_result->EndOffset());
    item_result->inline_size =
        item_result->shape_result->SnappedWidth().ClampNegativeToZero();
  }

  DCHECK(!item_result->may_break_inside);
  DCHECK(!item_result->can_break_after);
  trailing_whitespace_ = WhitespaceState::kUnknown;
  position_ += item_result->inline_size;
  MoveToNextOf(item);
}

NGLineBreaker::BreakResult NGLineBreaker::BreakText(
    NGInlineItemResult* item_result,
    const NGInlineItem& item,
    const ShapeResult& item_shape_result,
    LayoutUnit available_width,
    LayoutUnit available_width_with_hyphens,
    NGLineInfo* line_info) {
  DCHECK(item.Type() == NGInlineItem::kText ||
         (item.Type() == NGInlineItem::kControl &&
          Text()[item.StartOffset()] == kTabulationCharacter));
  DCHECK(&item_shape_result);
  item.AssertOffset(item_result->StartOffset());

  DCHECK_EQ(item_shape_result.StartIndex(), item.StartOffset());
  DCHECK_EQ(item_shape_result.EndIndex(), item.EndOffset());
  struct ShapeCallbackContext {
    STACK_ALLOCATED();

   public:
    NGLineBreaker* line_breaker;
    const NGInlineItem& item;
  } shape_callback_context{this, item};
  const ShapingLineBreaker::ShapeCallback shape_callback =
      [](void* untyped_context, unsigned start, unsigned end) {
        ShapeCallbackContext* context =
            static_cast<ShapeCallbackContext*>(untyped_context);
        return context->line_breaker->ShapeText(context->item, start, end);
      };
  ShapingLineBreaker breaker(&item_shape_result, &break_iterator_, hyphenation_,
                             shape_callback, &shape_callback_context);
  if (!enable_soft_hyphen_)
    breaker.DisableSoftHyphen();

  // Use kStartShouldBeSafe if at the beginning of a line.
  unsigned options = ShapingLineBreaker::kDefaultOptions;
  if (item_result->StartOffset() != line_info->StartOffset())
    options |= ShapingLineBreaker::kDontReshapeStart;

  // Reshaping between the last character and trailing spaces is needed only
  // when we need accurate end position, because kerning between trailing spaces
  // is not visible.
  if (!NeedsAccurateEndPosition(*line_info, item))
    options |= ShapingLineBreaker::kDontReshapeEndIfAtSpace;

  // Use kNoResultIfOverflow if 'break-word' and we're trying to break normally
  // because if this item overflows, we will rewind and break line again. The
  // overflowing ShapeResult is not needed.
  if (break_anywhere_if_overflow_ && !override_break_anywhere_)
    options |= ShapingLineBreaker::kNoResultIfOverflow;

#if DCHECK_IS_ON()
  unsigned try_count = 0;
#endif
  LayoutUnit inline_size;
  ShapingLineBreaker::Result result;
  while (true) {
#if DCHECK_IS_ON()
    ++try_count;
    DCHECK_LE(try_count, 2u);
#endif
    scoped_refptr<const ShapeResultView> shape_result = breaker.ShapeLine(
        item_result->StartOffset(), available_width.ClampNegativeToZero(),
        options, &result);

    // If this item overflows and 'break-word' is set, this line will be
    // rewinded. Making this item long enough to overflow is enough.
    if (!shape_result) {
      DCHECK(options & ShapingLineBreaker::kNoResultIfOverflow);
      item_result->inline_size = available_width_with_hyphens + 1;
      item_result->text_offset.end = item.EndOffset();
      item_result->text_offset.AssertNotEmpty();
      return kOverflow;
    }
    DCHECK_EQ(shape_result->NumCharacters(),
              result.break_offset - item_result->StartOffset());
    // It is critical to move the offset forward, or NGLineBreaker may keep
    // adding NGInlineItemResult until all the memory is consumed.
    CHECK_GT(result.break_offset, item_result->StartOffset());

    inline_size = shape_result->SnappedWidth().ClampNegativeToZero();
    if (UNLIKELY(result.is_hyphenated)) {
      const WritingMode writing_mode = constraint_space_.GetWritingMode();
      CreateHyphen(node_, writing_mode, item, item_result);
      DCHECK(item_result->hyphen_shape_result);
      DCHECK(item_result->hyphen_string);
      LayoutUnit hyphen_inline_size = item_result->HyphenInlineSize();
      // If the hyphen overflows, retry with the reduced available width.
      if (!result.is_overflow && inline_size <= available_width) {
        LayoutUnit space_for_hyphen =
            available_width_with_hyphens - inline_size;
        if (space_for_hyphen >= 0 && hyphen_inline_size > space_for_hyphen) {
          available_width -= hyphen_inline_size;
          continue;
        }
      }
      inline_size += hyphen_inline_size;
    } else if (UNLIKELY(item_result->hyphen_shape_result)) {
      item_result->hyphen_shape_result = nullptr;
      item_result->hyphen_string = String();
    }
    item_result->inline_size = inline_size;
    item_result->text_offset.end = result.break_offset;
    item_result->text_offset.AssertNotEmpty();
    item_result->shape_result = std::move(shape_result);
    break;
  }

  // * If width <= available_width:
  //   * If offset < item.EndOffset(): the break opportunity to fit is found.
  //   * If offset == item.EndOffset(): the break opportunity at the end fits,
  //     or the first break opportunity is beyond the end.
  //     There may be room for more characters.
  // * If width > available_width: The first break opportunity does not fit.
  //   offset is the first break opportunity, either inside, at the end, or
  //   beyond the end.
  if (item_result->EndOffset() < item.EndOffset()) {
    item_result->can_break_after = true;

    if (UNLIKELY(break_iterator_.BreakType() ==
                 LineBreakType::kBreakCharacter)) {
      trailing_whitespace_ = WhitespaceState::kUnknown;
    } else {
      trailing_whitespace_ = WhitespaceState::kNone;
    }
  } else {
    DCHECK_EQ(item_result->EndOffset(), item.EndOffset());
    item_result->can_break_after =
        break_iterator_.IsBreakable(item_result->EndOffset());
    if (!item_result->can_break_after && item.Type() == NGInlineItem::kText &&
        ShouldForceCanBreakAfter(*item_result))
      item_result->can_break_after = true;
    trailing_whitespace_ = WhitespaceState::kUnknown;
  }

  // This result is not breakable any further if overflow. This information is
  // useful to optimize |HandleOverflow()|.
  item_result->may_break_inside = !result.is_overflow;

  // TODO(crbug.com/1003742): We should use |result.is_overflow| here. For now,
  // use |inline_size| because some tests rely on this behavior.
  return inline_size <= available_width ? kSuccess : kOverflow;
}

// Breaks the text item at the previous break opportunity from
// |item_result->text_offset.end|. Returns false if there were no previous break
// opportunities.
bool NGLineBreaker::BreakTextAtPreviousBreakOpportunity(
    NGInlineItemResult* item_result) {
  DCHECK(item_result->item);
  DCHECK(item_result->may_break_inside);
  const NGInlineItem& item = *item_result->item;
  DCHECK_EQ(item.Type(), NGInlineItem::kText);
  DCHECK(item.Style() && item.Style()->AutoWrap());

  unsigned break_opportunity = break_iterator_.PreviousBreakOpportunity(
      item_result->EndOffset() - 1, item_result->StartOffset());
  if (break_opportunity <= item_result->StartOffset())
    return false;
  item_result->text_offset.end = break_opportunity;
  item_result->text_offset.AssertNotEmpty();
  item_result->shape_result = ShapeResultView::Create(
      item.TextShapeResult(), item_result->StartOffset(),
      item_result->EndOffset());
  item_result->inline_size =
      item_result->shape_result->SnappedWidth().ClampNegativeToZero();
  item_result->can_break_after = true;
  return true;
}

// This function handles text item for min-content. The specialized logic is
// because min-content is very expensive by breaking at every break opportunity
// and producing as many lines as the number of break opportunities.
//
// This function breaks the text in NGInlineItem at every break opportunity,
// computes the maximum width of all words, and creates one NGInlineItemResult
// that has the maximum width. For example, for a text item of "1 2 34 5 6",
// only the width of "34" matters for min-content.
//
// The first word and the last word, "1" and "6" in the example above, are
// handled in normal |HandleText()| because they may form a word with the
// previous/next item.
bool NGLineBreaker::HandleTextForFastMinContent(NGInlineItemResult* item_result,
                                                const NGInlineItem& item,
                                                const ShapeResult& shape_result,
                                                NGLineInfo* line_info) {
  DCHECK_EQ(mode_, NGLineBreakerMode::kMinContent);
  DCHECK(auto_wrap_);
  DCHECK(item.Type() == NGInlineItem::kText ||
         (item.Type() == NGInlineItem::kControl &&
          Text()[item.StartOffset()] == kTabulationCharacter));
  DCHECK(&shape_result);

  // If this is the first part of the text, it may form a word with the previous
  // item. Fallback to |HandleText()|.
  unsigned start_offset = item_result->StartOffset();
  DCHECK_LT(start_offset, item.EndOffset());
  if (start_offset != line_info->StartOffset() &&
      start_offset == item.StartOffset())
    return false;
  // If this is the last part of the text, it may form a word with the next
  // item. Fallback to |HandleText()|.
  if (fast_min_content_item_ == &item)
    return false;

  // Hyphenation is not supported yet.
  if (hyphenation_)
    return false;

  base::Optional<LineBreakType> saved_line_break_type;
  if (break_anywhere_if_overflow_ && !override_break_anywhere_) {
    saved_line_break_type = break_iterator_.BreakType();
    break_iterator_.SetBreakType(LineBreakType::kBreakCharacter);
  }

  // Break the text at every break opportunity and measure each word.
  DCHECK_EQ(shape_result.StartIndex(), item.StartOffset());
  DCHECK_GE(start_offset, shape_result.StartIndex());
  shape_result.EnsurePositionData();
  const String& text = Text();
  float min_width = 0;
  unsigned last_end_offset = 0;
  while (start_offset < item.EndOffset()) {
    unsigned end_offset = break_iterator_.NextBreakOpportunity(
        start_offset + 1, item.EndOffset());
    if (end_offset >= item.EndOffset())
      break;

    // Inserting a hyphenation character is not supported yet.
    if (text[end_offset - 1] == kSoftHyphenCharacter)
      return false;

    float start_position = shape_result.CachedPositionForOffset(
        start_offset - shape_result.StartIndex());
    float end_position = shape_result.CachedPositionForOffset(
        end_offset - shape_result.StartIndex());
    float word_width = IsLtr(shape_result.Direction())
                           ? end_position - start_position
                           : start_position - end_position;
    min_width = std::max(word_width, min_width);

    last_end_offset = end_offset;
    start_offset = end_offset;
    while (start_offset < item.EndOffset() &&
           IsBreakableSpace(text[start_offset])) {
      ++start_offset;
    }
  }

  if (saved_line_break_type.has_value())
    break_iterator_.SetBreakType(*saved_line_break_type);

  // If there was only one break opportunity in this item, it may form a word
  // with previous and/or next item. Fallback to |HandleText()|.
  if (!last_end_offset)
    return false;

  // Create an NGInlineItemResult that has the max of widths of all words.
  item_result->text_offset.end = last_end_offset;
  item_result->text_offset.AssertNotEmpty();
  item_result->inline_size = LayoutUnit::FromFloatCeil(min_width);
  item_result->can_break_after = true;

  trailing_whitespace_ = WhitespaceState::kUnknown;
  position_ += item_result->inline_size;
  state_ = LineBreakState::kTrailing;
  fast_min_content_item_ = &item;
  MoveToNextOf(*item_result);
  return true;
}

void NGLineBreaker::HandleEmptyText(const NGInlineItem& item,
                                    NGLineInfo* line_info) {
  // Fully collapsed text is not needed for line breaking/layout, but it may
  // have |SelfNeedsLayout()| set. Mark it was laid out.
  ClearNeedsLayout(item);
  MoveToNextOf(item);
}

// Re-shape the specified range of |NGInlineItem|.
scoped_refptr<ShapeResult> NGLineBreaker::ShapeText(const NGInlineItem& item,
                                                    unsigned start,
                                                    unsigned end) {
  scoped_refptr<ShapeResult> shape_result;
  if (!items_data_.segments) {
    RunSegmenter::RunSegmenterRange segment_range =
        item.CreateRunSegmenterRange();
    shape_result = shaper_.Shape(&item.Style()->GetFont(), item.Direction(),
                                 start, end, segment_range);
  } else {
    shape_result = items_data_.segments->ShapeText(
        &shaper_, &item.Style()->GetFont(), item.Direction(), start, end,
        &item - items_data_.items.begin());
  }
  if (UNLIKELY(spacing_.HasSpacing()))
    shape_result->ApplySpacing(spacing_);
  return shape_result;
}

// Compute a new ShapeResult for the specified end offset.
// The end is re-shaped if it is not safe-to-break.
scoped_refptr<ShapeResultView> NGLineBreaker::TruncateLineEndResult(
    const NGLineInfo& line_info,
    const NGInlineItemResult& item_result,
    unsigned end_offset) {
  DCHECK(item_result.item);
  const NGInlineItem& item = *item_result.item;

  // Check given offsets require to truncate |item_result.shape_result|.
  const unsigned start_offset = item_result.StartOffset();
  const ShapeResultView* source_result = item_result.shape_result.get();
  DCHECK(source_result);
  DCHECK_GE(start_offset, source_result->StartIndex());
  DCHECK_LE(end_offset, source_result->EndIndex());
  DCHECK(start_offset > source_result->StartIndex() ||
         end_offset < source_result->EndIndex());

  if (!NeedsAccurateEndPosition(line_info, item)) {
    return ShapeResultView::Create(source_result, start_offset, end_offset);
  }

  unsigned last_safe = source_result->PreviousSafeToBreakOffset(end_offset);
  DCHECK_LE(last_safe, end_offset);
  if (last_safe == end_offset || last_safe <= start_offset) {
    return ShapeResultView::Create(source_result, start_offset, end_offset);
  }

  scoped_refptr<ShapeResult> end_result =
      ShapeText(item, std::max(last_safe, start_offset), end_offset);
  DCHECK_EQ(end_result->Direction(), source_result->Direction());
  ShapeResultView::Segment segments[2];
  segments[0] = {source_result, start_offset, last_safe};
  segments[1] = {end_result.get(), 0, end_offset};
  return ShapeResultView::Create(&segments[0], 2);
}

// Update |ShapeResult| in |item_result| to match to its |start_offset| and
// |end_offset|. The end is re-shaped if it is not safe-to-break.
void NGLineBreaker::UpdateShapeResult(const NGLineInfo& line_info,
                                      NGInlineItemResult* item_result) {
  DCHECK(item_result);
  item_result->shape_result =
      TruncateLineEndResult(line_info, *item_result, item_result->EndOffset());
  DCHECK(item_result->shape_result);
  item_result->inline_size = item_result->shape_result->SnappedWidth();
}

inline void NGLineBreaker::HandleTrailingSpaces(const NGInlineItem& item,
                                                NGLineInfo* line_info) {
  const ShapeResult* shape_result = item.TextShapeResult();
  DCHECK(shape_result);
  HandleTrailingSpaces(item, *shape_result, line_info);
}

void NGLineBreaker::HandleTrailingSpaces(const NGInlineItem& item,
                                         const ShapeResult& shape_result,
                                         NGLineInfo* line_info) {
  DCHECK(item.Type() == NGInlineItem::kText ||
         (item.Type() == NGInlineItem::kControl &&
          Text()[item.StartOffset()] == kTabulationCharacter));
  DCHECK(&shape_result);
  DCHECK_GE(offset_, item.StartOffset());
  DCHECK_LT(offset_, item.EndOffset());
  const String& text = Text();
  DCHECK(item.Style());
  const ComputedStyle& style = *item.Style();

  if (!auto_wrap_) {
    state_ = LineBreakState::kDone;
    return;
  }

  if (style.CollapseWhiteSpace()) {
    if (text[offset_] != kSpaceCharacter) {
      state_ = LineBreakState::kDone;
      return;
    }

    // Skipping one whitespace removes all collapsible spaces because
    // collapsible spaces are collapsed to single space in NGInlineItemBuilder.
    offset_++;
    trailing_whitespace_ = WhitespaceState::kCollapsed;

    // Make the last item breakable after, even if it was nowrap.
    NGInlineItemResults* item_results = line_info->MutableResults();
    DCHECK(!item_results->IsEmpty());
    item_results->back().can_break_after = true;
  } else if (style.WhiteSpace() != EWhiteSpace::kBreakSpaces) {
    // Find the end of the run of space characters in this item.
    // Other white space characters (e.g., tab) are not included in this item.
    DCHECK(style.BreakOnlyAfterWhiteSpace());
    unsigned end = offset_;
    while (end < item.EndOffset() && IsBreakableSpace(text[end]))
      end++;
    if (end == offset_) {
      state_ = LineBreakState::kDone;
      return;
    }

    NGInlineItemResult* item_result = AddItem(item, end, line_info);
    item_result->has_only_trailing_spaces = true;
    item_result->shape_result = ShapeResultView::Create(&shape_result);
    if (item_result->StartOffset() == item.StartOffset() &&
        item_result->EndOffset() == item.EndOffset())
      item_result->inline_size = item_result->shape_result->SnappedWidth();
    else
      UpdateShapeResult(*line_info, item_result);
    position_ += item_result->inline_size;
    item_result->can_break_after =
        end < text.length() && !IsBreakableSpace(text[end]);
    offset_ = end;
    trailing_whitespace_ = WhitespaceState::kPreserved;
  }

  // If non-space characters follow, the line is done.
  // Otherwise keep checking next items for the break point.
  DCHECK_LE(offset_, item.EndOffset());
  if (offset_ < item.EndOffset()) {
    state_ = LineBreakState::kDone;
    return;
  }
  ClearNeedsLayout(item);
  item_index_++;
  state_ = LineBreakState::kTrailing;
}

// Remove trailing collapsible spaces in |line_info|.
// https://drafts.csswg.org/css-text-3/#white-space-phase-2
void NGLineBreaker::RemoveTrailingCollapsibleSpace(NGLineInfo* line_info) {
  // Remove trailing open tags. Open tags are included as trailable items
  // because they are ambiguous. When the line ends, and if the end of line has
  // open tags, they are not trailable.
  // TODO(crbug.com/1009936): Open tags and trailing space items can interleave,
  // but the current code supports only one trailing space item. Multiple
  // trailing space items and interleaved open/close tags should be supported.
  const NGInlineItemResults& item_results = line_info->Results();
  for (const NGInlineItemResult& item_result : base::Reversed(item_results)) {
    DCHECK(item_result.item);
    if (item_result.item->Type() != NGInlineItem::kOpenTag) {
      unsigned end_index = &item_result - item_results.begin() + 1;
      if (end_index < item_results.size()) {
        const NGInlineItemResult& end_item_result = item_results[end_index];
        unsigned end_item_index = end_item_result.item_index;
        unsigned end_offset = end_item_result.StartOffset();
        ResetRewindLoopDetector();
        Rewind(end_index, line_info);
        item_index_ = end_item_index;
        offset_ = end_offset;
        items_data_.AssertOffset(item_index_, offset_);
      }
      break;
    }
  }

  ComputeTrailingCollapsibleSpace(line_info);
  if (!trailing_collapsible_space_.has_value()) {
    return;
  }

  // We have a trailing collapsible space. Remove it.
  NGInlineItemResult* item_result = trailing_collapsible_space_->item_result;
  position_ -= item_result->inline_size;
  if (scoped_refptr<const ShapeResultView>& collapsed_shape_result =
          trailing_collapsible_space_->collapsed_shape_result) {
    --item_result->text_offset.end;
    item_result->text_offset.AssertNotEmpty();
    item_result->shape_result = collapsed_shape_result;
    item_result->inline_size = item_result->shape_result->SnappedWidth();
    position_ += item_result->inline_size;
  } else {
    ClearNeedsLayout(*item_result->item);
    line_info->MutableResults()->erase(item_result);
  }
  trailing_collapsible_space_.reset();
  trailing_whitespace_ = WhitespaceState::kCollapsed;
}

// Compute the width of trailing spaces without removing it.
LayoutUnit NGLineBreaker::TrailingCollapsibleSpaceWidth(NGLineInfo* line_info) {
  ComputeTrailingCollapsibleSpace(line_info);
  if (!trailing_collapsible_space_.has_value())
    return LayoutUnit();

  // Normally, the width of new_reuslt is smaller, but technically it can be
  // larger. In such case, it means the trailing spaces has negative width.
  NGInlineItemResult* item_result = trailing_collapsible_space_->item_result;
  if (scoped_refptr<const ShapeResultView>& collapsed_shape_result =
          trailing_collapsible_space_->collapsed_shape_result) {
    return item_result->inline_size - collapsed_shape_result->SnappedWidth();
  }
  return item_result->inline_size;
}

// Find trailing collapsible space if exists. The result is cached to
// |trailing_collapsible_space_|.
void NGLineBreaker::ComputeTrailingCollapsibleSpace(NGLineInfo* line_info) {
  if (trailing_whitespace_ == WhitespaceState::kLeading ||
      trailing_whitespace_ == WhitespaceState::kNone ||
      trailing_whitespace_ == WhitespaceState::kCollapsed ||
      trailing_whitespace_ == WhitespaceState::kPreserved) {
    trailing_collapsible_space_.reset();
    return;
  }
  DCHECK(trailing_whitespace_ == WhitespaceState::kUnknown ||
         trailing_whitespace_ == WhitespaceState::kCollapsible);

  trailing_whitespace_ = WhitespaceState::kNone;
  const String& text = Text();
  NGInlineItemResults* item_results = line_info->MutableResults();
  for (auto it = item_results->rbegin(); it != item_results->rend(); ++it) {
    NGInlineItemResult& item_result = *it;
    DCHECK(item_result.item);
    const NGInlineItem& item = *item_result.item;
    if (item.EndCollapseType() == NGInlineItem::kOpaqueToCollapsing)
      continue;
    if (item.Type() == NGInlineItem::kText) {
      DCHECK_GT(item_result.EndOffset(), 0u);
      DCHECK(item.Style());
      if (!IsBreakableSpace(text[item_result.EndOffset() - 1]))
        break;
      if (!item.Style()->CollapseWhiteSpace()) {
        trailing_whitespace_ = WhitespaceState::kPreserved;
        break;
      }
      // |shape_result| is nullptr if this is an overflow because BreakText()
      // uses kNoResultIfOverflow option.
      if (!item_result.shape_result)
        break;

      if (!trailing_collapsible_space_.has_value() ||
          trailing_collapsible_space_->item_result != &item_result) {
        trailing_collapsible_space_.emplace();
        trailing_collapsible_space_->item_result = &item_result;
        if (item_result.EndOffset() - 1 > item_result.StartOffset()) {
          trailing_collapsible_space_->collapsed_shape_result =
              TruncateLineEndResult(*line_info, item_result,
                                    item_result.EndOffset() - 1);
        }
      }
      trailing_whitespace_ = WhitespaceState::kCollapsible;
      return;
    }
    if (item.Type() == NGInlineItem::kControl) {
      if (item.TextType() == NGTextType::kForcedLineBreak) {
        DCHECK_EQ(text[item.StartOffset()], kNewlineCharacter);
        continue;
      }
      trailing_whitespace_ = WhitespaceState::kPreserved;
      trailing_collapsible_space_.reset();
      return;
    }
    break;
  }

  trailing_collapsible_space_.reset();
}

// Measure control items; new lines and tab, that are similar to text, affect
// layout, but do not need shaping/painting.
void NGLineBreaker::HandleControlItem(const NGInlineItem& item,
                                      NGLineInfo* line_info) {
  DCHECK_GE(item.Length(), 1u);
  if (item.TextType() == NGTextType::kForcedLineBreak) {
    DCHECK_EQ(Text()[item.StartOffset()], kNewlineCharacter);

    // Check overflow, because the last item may have overflowed.
    if (HandleOverflowIfNeeded(line_info))
      return;

    NGInlineItemResult* item_result = AddItem(item, line_info);
    item_result->should_create_line_box = true;
    item_result->has_only_trailing_spaces = true;
    MoveToNextOf(item);

    // Include following close tags. The difference is visible when they have
    // margin/border/padding.
    //
    // This is not a defined behavior, but legacy/WebKit do this for preserved
    // newlines and <br>s. Gecko does this only for preserved newlines (but
    // not for <br>s).
    const Vector<NGInlineItem>& items = Items();
    while (item_index_ < items.size()) {
      const NGInlineItem& next_item = items[item_index_];
      if (next_item.Type() == NGInlineItem::kCloseTag) {
        HandleCloseTag(next_item, line_info);
        continue;
      }
      break;
    }

    is_after_forced_break_ = true;
    line_info->SetIsLastLine(true);
    state_ = LineBreakState::kDone;
    return;
  }
  DCHECK_EQ(item.TextType(), NGTextType::kFlowControl);
  UChar character = Text()[item.StartOffset()];
  switch (character) {
    case kTabulationCharacter: {
      DCHECK(item.Style());
      const ComputedStyle& style = *item.Style();
      scoped_refptr<const ShapeResult> shape_result =
          ShapeResult::CreateForTabulationCharacters(
              &style.GetFont(), item.Direction(), style.GetTabSize(), position_,
              item.StartOffset(), item.Length());
      HandleText(item, *shape_result, line_info);
      return;
    }
    case kZeroWidthSpaceCharacter: {
      // <wbr> tag creates break opportunities regardless of auto_wrap.
      NGInlineItemResult* item_result = AddItem(item, line_info);
      // A generated break opportunity doesn't generate fragments, but we still
      // need to add this for rewind to find this opportunity. This will be
      // discarded in |NGInlineLayoutAlgorithm| when it generates fragments.
      if (!item.IsGeneratedForLineBreak())
        item_result->should_create_line_box = true;
      item_result->can_break_after = true;
      break;
    }
    case kCarriageReturnCharacter:
    case kFormFeedCharacter:
      // Ignore carriage return and form feed.
      // https://drafts.csswg.org/css-text-3/#white-space-processing
      // https://github.com/w3c/csswg-drafts/issues/855
      HandleEmptyText(item, line_info);
      return;
    default:
      NOTREACHED();
      HandleEmptyText(item, line_info);
      return;
  }
  MoveToNextOf(item);
}

void NGLineBreaker::HandleBidiControlItem(const NGInlineItem& item,
                                          NGLineInfo* line_info) {
  DCHECK_EQ(item.Length(), 1u);

  // Bidi control characters have enter/exit semantics. Handle "enter"
  // characters simialr to open-tag, while "exit" (pop) characters similar to
  // close-tag.
  UChar character = Text()[item.StartOffset()];
  bool is_pop = character == kPopDirectionalIsolateCharacter ||
                character == kPopDirectionalFormattingCharacter;
  NGInlineItemResults* item_results = line_info->MutableResults();
  if (is_pop) {
    if (!item_results->IsEmpty()) {
      NGInlineItemResult* item_result = AddItem(item, line_info);
      NGInlineItemResult* last = &(*item_results)[item_results->size() - 2];
      // Honor the last |can_break_after| if it's true, in case it was
      // artificially set to true for break-after-space.
      if (last->can_break_after) {
        item_result->can_break_after = last->can_break_after;
        last->can_break_after = false;
      } else {
        // Otherwise compute from the text. |LazyLineBreakIterator| knows how to
        // break around bidi control characters.
        ComputeCanBreakAfter(item_result, auto_wrap_, break_iterator_);
      }
    } else {
      AddItem(item, line_info);
    }
  } else {
    if (state_ == LineBreakState::kTrailing &&
        CanBreakAfterLast(*item_results)) {
      DCHECK(!line_info->IsLastLine());
      MoveToNextOf(item);
      state_ = LineBreakState::kDone;
      return;
    }
    NGInlineItemResult* item_result = AddItem(item, line_info);
    DCHECK(!item_result->can_break_after);
  }
  MoveToNextOf(item);
}

void NGLineBreaker::HandleAtomicInline(
    const NGInlineItem& item,
    LayoutUnit percentage_resolution_block_size_for_min_max,
    NGLineInfo* line_info) {
  DCHECK_EQ(item.Type(), NGInlineItem::kAtomicInline);
  DCHECK(item.Style());
  const ComputedStyle& style = *item.Style();

  const LayoutUnit remaining_width = RemainingAvailableWidth();
  bool ignore_overflow_if_negative_margin = false;
  if (state_ == LineBreakState::kContinue && remaining_width < 0) {
    const unsigned item_index = item_index_;
    DCHECK_EQ(item_index, static_cast<unsigned>(&item - Items().begin()));
    DCHECK(!line_info->HasOverflow());
    HandleOverflow(line_info);
    if (!line_info->HasOverflow() || item_index != item_index_)
      return;
    // Compute margins if this line overflows. Negative margins can put the
    // position back.
    DCHECK_NE(state_, LineBreakState::kContinue);
    ignore_overflow_if_negative_margin = true;
  }

  // Compute margins before computing overflow, because even when the current
  // position is beyond the end, negative margins can bring this item back to on
  // the current line.
  NGInlineItemResult* item_result = AddItem(item, line_info);
  item_result->margins =
      ComputeLineMarginsForVisualContainer(constraint_space_, style);
  LayoutUnit inline_margins = item_result->margins.InlineSum();
  if (UNLIKELY(ignore_overflow_if_negative_margin)) {
    DCHECK_LT(remaining_width, 0);
    // The margin isn't negative, or the negative margin isn't large enough to
    // put the position back. Break this line before this item.
    if (inline_margins >= remaining_width) {
      RemoveLastItem(line_info);
      return;
    }
    // This line once overflowed, but the negative margin puts the position
    // back.
    state_ = LineBreakState::kContinue;
    line_info->SetHasOverflow(false);
  }

  // When we're just computing min/max content sizes, we can skip the full
  // layout and just compute those sizes. On the other hand, for regular
  // layout we need to do the full layout and get the layout result.
  // Doing a full layout for min/max content can also have undesirable
  // side effects when that falls back to legacy layout.
  if (mode_ == NGLineBreakerMode::kContent) {
    item_result->layout_result =
        NGBlockNode(ToLayoutBox(item.GetLayoutObject()))
            .LayoutAtomicInline(constraint_space_, node_.Style(),
                                line_info->UseFirstLineStyle());
    item_result->inline_size =
        NGFragment(constraint_space_.GetWritingMode(),
                   item_result->layout_result->PhysicalFragment())
            .InlineSize();
    item_result->inline_size += inline_margins;
  } else if (mode_ == NGLineBreakerMode::kMaxContent && max_size_cache_) {
    unsigned item_index = &item - Items().begin();
    item_result->inline_size = (*max_size_cache_)[item_index];
  } else {
    DCHECK(mode_ == NGLineBreakerMode::kMinContent || !max_size_cache_);
    NGBlockNode child(ToLayoutBox(item.GetLayoutObject()));
    MinMaxSizesInput input(percentage_resolution_block_size_for_min_max,
                           MinMaxSizesType::kContent);
    MinMaxSizesResult result =
        ComputeMinAndMaxContentContribution(node_.Style(), child, input);
    if (mode_ == NGLineBreakerMode::kMinContent) {
      item_result->inline_size = result.sizes.min_size + inline_margins;
      if (depends_on_percentage_block_size_out_) {
        *depends_on_percentage_block_size_out_ |=
            result.depends_on_percentage_block_size;
      }
      if (max_size_cache_) {
        if (max_size_cache_->IsEmpty())
          max_size_cache_->resize(Items().size());
        unsigned item_index = &item - Items().begin();
        (*max_size_cache_)[item_index] = result.sizes.max_size + inline_margins;
      }
    } else {
      item_result->inline_size = result.sizes.max_size + inline_margins;
    }
  }

  item_result->should_create_line_box = true;
  // Atomic inlines have break opportunities before and after, even when the
  // adjacent character is U+00A0 NO-BREAK SPACE character, except when sticky
  // images quirk is applied.
  item_result->can_break_after =
      auto_wrap_ && !(sticky_images_quirk_ && item.IsImage());

  position_ += item_result->inline_size;

  if (item.IsRubyRun()) {
    // Overrides can_break_after.
    ComputeCanBreakAfter(item_result, auto_wrap_, break_iterator_);

    NGAnnotationOverhang overhang = GetOverhang(*item_result);
    if (overhang.end > LayoutUnit()) {
      item_result->pending_end_overhang = overhang.end;
      maybe_have_end_overhang_ = true;
    }

    if (CanApplyStartOverhang(*line_info, overhang.start)) {
      DCHECK_EQ(item_result->margins.inline_start, LayoutUnit());
      item_result->margins.inline_start = -overhang.start;
      item_result->inline_size -= overhang.start;
      position_ -= overhang.start;
    }
  }

  trailing_whitespace_ = WhitespaceState::kNone;
  MoveToNextOf(item);
}

// Performs layout and positions a float.
//
// If there is a known available_width (e.g. something has resolved the
// container BFC block offset) it will attempt to position the float on the
// current line.
// Additionally updates the available_width for the line as the float has
// (probably) consumed space.
//
// If the float is too wide *or* we already have UnpositionedFloats we add it
// as an UnpositionedFloat. This should be positioned *immediately* after we
// are done with the current line.
// We have this check if there are already UnpositionedFloats as we aren't
// allowed to position a float "above" another float which has come before us
// in the document.
void NGLineBreaker::HandleFloat(const NGInlineItem& item,
                                NGLineInfo* line_info) {
  // When rewind occurs, an item may be handled multiple times.
  // Since floats are put into a separate list, avoid handling same floats
  // twice.
  // Ideally rewind can take floats out of floats list, but the difference is
  // sutble compared to the complexity.
  //
  // Additionally, we need to skip floats if we're retrying a line after a
  // fragmentainer break. In that case the floats associated with this line will
  // already have been processed.
  NGInlineItemResult* item_result = AddItem(item, line_info);
  item_result->can_break_after = auto_wrap_;
  MoveToNextOf(item);

  // If we are currently computing our min/max-content size, simply append the
  // unpositioned floats to |NGLineInfo| and abort.
  if (mode_ != NGLineBreakerMode::kContent)
    return;

  // Make sure we populate the positioned_float inside the |item_result|.
  if (item_index_ <= handled_leading_floats_index_ &&
      !leading_floats_.IsEmpty()) {
    DCHECK_LT(leading_floats_index_, leading_floats_.size());
    item_result->positioned_float = leading_floats_[leading_floats_index_++];

    // Don't break after leading floats if indented.
    if (position_ != 0)
      item_result->can_break_after = false;
    return;
  }

  // TODO(ikilpatrick): Add support for float break tokens inside an inline
  // layout context.

  LayoutUnit bfc_block_offset = line_opportunity_.bfc_block_offset;
  NGUnpositionedFloat unpositioned_float(
      NGBlockNode(ToLayoutBox(item.GetLayoutObject())),
      /* break_token */ nullptr, constraint_space_.AvailableSize(),
      constraint_space_.PercentageResolutionSize(),
      constraint_space_.ReplacedPercentageResolutionSize(),
      {constraint_space_.BfcOffset().line_offset, bfc_block_offset},
      constraint_space_, node_.Style());

  LayoutUnit inline_margin_size =
      ComputeMarginBoxInlineSizeForUnpositionedFloat(&unpositioned_float);

  LayoutUnit used_size = position_ + inline_margin_size +
                         ComputeFloatAncestorInlineEndSize(
                             constraint_space_, Items(), item_index_);
  bool can_fit_float =
      used_size <= line_opportunity_.AvailableFloatInlineSize().AddEpsilon();
  if (!can_fit_float) {
    // Floats need to know the current line width to determine whether to put it
    // into the current line or to the next line. Trailing spaces will be
    // removed if this line breaks here because they should be collapsed across
    // floats, but they are still included in the current line position at this
    // point. Exclude it when computing whether this float can fit or not.
    can_fit_float = used_size - TrailingCollapsibleSpaceWidth(line_info) <=
                    line_opportunity_.AvailableFloatInlineSize().AddEpsilon();
  }

  // The float should be positioned after the current line if:
  //  - It can't fit within the non-shape area. (Assuming the current position
  //    also is strictly within the non-shape area).
  //  - It will be moved down due to block-start edge alignment.
  //  - It will be moved down due to clearance.
  bool float_after_line =
      !can_fit_float ||
      exclusion_space_->LastFloatBlockStart() > bfc_block_offset ||
      exclusion_space_->ClearanceOffset(unpositioned_float.ClearType(
          constraint_space_.Direction())) > bfc_block_offset;

  // Check if we already have a pending float. That's because a float cannot be
  // higher than any block or floated box generated before.
  if (HasUnpositionedFloats(line_info->Results()) || float_after_line) {
    item_result->has_unpositioned_floats = true;
  } else {
    NGPositionedFloat positioned_float =
        PositionFloat(&unpositioned_float, exclusion_space_);
    item_result->positioned_float = positioned_float;

    NGLayoutOpportunity opportunity = exclusion_space_->FindLayoutOpportunity(
        {constraint_space_.BfcOffset().line_offset, bfc_block_offset},
        constraint_space_.AvailableSize().inline_size);

    DCHECK_EQ(bfc_block_offset, opportunity.rect.BlockStartOffset());

    line_opportunity_ = opportunity.ComputeLineLayoutOpportunity(
        constraint_space_, line_opportunity_.line_block_size, LayoutUnit());
    available_width_ = ComputeAvailableWidth();

    DCHECK_GE(AvailableWidth(), LayoutUnit());
  }
}

void NGLineBreaker::HandleOutOfFlowPositioned(const NGInlineItem& item,
                                              NGLineInfo* line_info) {
  DCHECK_EQ(item.Type(), NGInlineItem::kOutOfFlowPositioned);
  NGInlineItemResult* item_result = AddItem(item, line_info);

  // Break opportunity after OOF is not well-defined nor interoperable. Using
  // |kObjectReplacementCharacter|, except when this is a leading OOF, seems to
  // produce reasonable and interoperable results in common cases.
  DCHECK(!item_result->can_break_after);
  if (item_result->should_create_line_box)
    ComputeCanBreakAfter(item_result, auto_wrap_, break_iterator_);

  MoveToNextOf(item);
}

bool NGLineBreaker::ComputeOpenTagResult(
    const NGInlineItem& item,
    const NGConstraintSpace& constraint_space,
    NGInlineItemResult* item_result) {
  DCHECK_EQ(item.Type(), NGInlineItem::kOpenTag);
  DCHECK(item.Style());
  const ComputedStyle& style = *item.Style();
  item_result->has_edge = item.HasStartEdge();
  if (item.ShouldCreateBoxFragment() &&
      (style.HasBorder() || style.MayHavePadding() ||
       (style.MayHaveMargin() && item_result->has_edge))) {
    item_result->borders = ComputeLineBorders(style);
    item_result->padding = ComputeLinePadding(constraint_space, style);
    if (item_result->has_edge) {
      item_result->margins = ComputeLineMarginsForSelf(constraint_space, style);
      item_result->inline_size = item_result->margins.inline_start +
                                 item_result->borders.inline_start +
                                 item_result->padding.inline_start;
      return true;
    }
  }
  return false;
}

void NGLineBreaker::HandleOpenTag(const NGInlineItem& item,
                                  NGLineInfo* line_info) {
  DCHECK_EQ(item.Type(), NGInlineItem::kOpenTag);

  NGInlineItemResult* item_result = AddItem(item, line_info);
  if (ComputeOpenTagResult(item, constraint_space_, item_result)) {
    // Negative margins on open tags may bring the position back. Update
    // |state_| if that happens.
    if (UNLIKELY(item_result->inline_size < 0 &&
                 state_ == LineBreakState::kTrailing)) {
      LayoutUnit available_width = AvailableWidthToFit();
      if (position_ > available_width &&
          position_ + item_result->inline_size <= available_width) {
        state_ = LineBreakState::kContinue;
      }
    }

    position_ += item_result->inline_size;

    // While the spec defines "non-zero margins, padding, or borders" prevents
    // line boxes to be zero-height, tests indicate that only inline direction
    // of them do so. See should_create_line_box_.
    // Force to create a box, because such inline boxes affect line heights.
    if (!item_result->should_create_line_box && !item.IsEmptyItem())
      item_result->should_create_line_box = true;
  }

  bool was_auto_wrap = auto_wrap_;
  DCHECK(item.Style());
  const ComputedStyle& style = *item.Style();
  SetCurrentStyle(style);
  MoveToNextOf(item);

  DCHECK(!item_result->can_break_after);
  const NGInlineItemResults& item_results = line_info->Results();
  if (UNLIKELY(!was_auto_wrap && auto_wrap_ && item_results.size() >= 2)) {
    ComputeCanBreakAfter(std::prev(item_result), auto_wrap_, break_iterator_);
  }
}

void NGLineBreaker::HandleCloseTag(const NGInlineItem& item,
                                   NGLineInfo* line_info) {
  NGInlineItemResult* item_result = AddItem(item, line_info);

  item_result->has_edge = item.HasEndEdge();
  if (item_result->has_edge) {
    item_result->inline_size =
        ComputeInlineEndSize(constraint_space_, item.Style());
    position_ += item_result->inline_size;

    if (!item_result->should_create_line_box && !item.IsEmptyItem())
      item_result->should_create_line_box = true;
  }
  DCHECK(item.GetLayoutObject() && item.GetLayoutObject()->Parent());
  bool was_auto_wrap = auto_wrap_;
  SetCurrentStyle(item.GetLayoutObject()->Parent()->StyleRef());
  MoveToNextOf(item);

  // If the line can break after the previous item, prohibit it and allow break
  // after this close tag instead. Even when the close tag has "nowrap", break
  // after it is allowed if the line is breakable after the previous item.
  const NGInlineItemResults& item_results = line_info->Results();
  if (item_results.size() >= 2) {
    NGInlineItemResult* last = std::prev(item_result);
    if (was_auto_wrap || last->can_break_after) {
      item_result->can_break_after = last->can_break_after;
      last->can_break_after = false;
      return;
    }
  }
  if (was_auto_wrap)
    return;

  DCHECK(!item_result->can_break_after);
  if (!auto_wrap_)
    return;

  // When auto-wrap follows no-wrap, the boundary is determined by the break
  // iterator. However, when space characters follow the boundary, the break
  // iterator cannot compute this because it considers break opportunities are
  // before a run of spaces.
  const String& text = Text();
  if (item_result->EndOffset() < text.length() &&
      IsBreakableSpace(text[item_result->EndOffset()])) {
    item_result->can_break_after = true;
    return;
  }
  ComputeCanBreakAfter(item_result, auto_wrap_, break_iterator_);
}

// Handles when the last item overflows.
// At this point, item_results does not fit into the current line, and there
// are no break opportunities in item_results.back().
void NGLineBreaker::HandleOverflow(NGLineInfo* line_info) {
  // Compute the width needing to rewind. When |width_to_rewind| goes negative,
  // items can fit within the line.
  LayoutUnit available_width = AvailableWidthToFit();
  LayoutUnit width_to_rewind = position_ - available_width;
  DCHECK_GT(width_to_rewind, 0);

  // Keep track of the shortest break opportunity.
  unsigned break_before = 0;

  // True if there is at least one item that has `break-word`.
  bool has_break_anywhere_if_overflow = break_anywhere_if_overflow_;

  // Search for a break opportunity that can fit.
  NGInlineItemResults* item_results = line_info->MutableResults();
  for (unsigned i = item_results->size(); i;) {
    NGInlineItemResult* item_result = &(*item_results)[--i];
    has_break_anywhere_if_overflow |= item_result->break_anywhere_if_overflow;

    // Try to break after this item.
    if (i < item_results->size() - 1 && item_result->can_break_after) {
      if (width_to_rewind <= 0) {
        position_ = available_width + width_to_rewind;
        RewindOverflow(i + 1, line_info);
        return;
      }
      break_before = i + 1;
    }

    // Compute the position after this item was removed entirely.
    width_to_rewind -= item_result->inline_size;

    // Try next if still does not fit.
    if (width_to_rewind > 0)
      continue;

    DCHECK(item_result->item);
    const NGInlineItem& item = *item_result->item;
    if (item.Type() == NGInlineItem::kText) {
      DCHECK(item_result->shape_result ||
             (item_result->break_anywhere_if_overflow &&
              !override_break_anywhere_) ||
             // |HandleTextForFastMinContent| can produce an item without
             // |ShapeResult|. In this case, it is not breakable.
             (mode_ == NGLineBreakerMode::kMinContent &&
              !item_result->may_break_inside));
      // If space is available, and if this text is breakable, part of the text
      // may fit. Try to break this item.
      if (width_to_rewind < 0 && item_result->may_break_inside) {
        const LayoutUnit item_available_width = -width_to_rewind;
        // Make sure the available width is smaller than the current width. The
        // break point must not be at the end when e.g., the text fits but its
        // right margin does not or following items do not.
        const LayoutUnit min_available_width = item_result->inline_size - 1;
        // If |inline_size| is zero (e.g., `font-size: 0`), |BreakText| cannot
        // make it shorter. Take the previous break opportunity.
        if (UNLIKELY(min_available_width <= 0)) {
          if (BreakTextAtPreviousBreakOpportunity(item_result)) {
            RewindOverflow(i + 1, line_info);
            return;
          }
          continue;
        }
        scoped_refptr<const ComputedStyle> was_current_style = current_style_;
        SetCurrentStyle(*item.Style());
        const NGInlineItemResult item_result_before = *item_result;
        BreakText(item_result, item, *item.TextShapeResult(),
                  std::min(item_available_width, min_available_width),
                  item_available_width, line_info);
        DCHECK_LE(item_result->EndOffset(), item_result_before.EndOffset());
#if DCHECK_IS_ON()
        item_result->CheckConsistency(true);
#endif

        // If BreakText() changed this item small enough to fit, break here.
        if (item_result->can_break_after &&
            item_result->inline_size <= item_available_width &&
            item_result->EndOffset() < item_result_before.EndOffset()) {
          DCHECK_LT(item_result->EndOffset(), item.EndOffset());

          // If this is the last item, adjust it to accommodate the change.
          const unsigned new_end = i + 1;
          DCHECK_LE(new_end, item_results->size());
          if (new_end == item_results->size()) {
            position_ =
                available_width + width_to_rewind + item_result->inline_size;
            DCHECK_EQ(position_, line_info->ComputeWidth());
            item_index_ = item_result->item_index;
            offset_ = item_result->EndOffset();
            items_data_.AssertOffset(item_index_, offset_);
            HandleTrailingSpaces(item, line_info);
            return;
          }

          Rewind(new_end, line_info);
          if (new_end < item_results->size())
            state_ = LineBreakState::kTrailing;
          else
            HandleTrailingSpaces(item, line_info);
          return;
        }

        // Failed to break to fit. Restore to the original state.
        *item_result = std::move(item_result_before);
        SetCurrentStyle(*was_current_style);
      }
    }
  }

  // Reaching here means that the rewind point was not found.

  if (!override_break_anywhere_ && has_break_anywhere_if_overflow) {
    override_break_anywhere_ = true;
    break_iterator_.SetBreakType(LineBreakType::kBreakCharacter);
    // TODO(kojii): Not all items need to rewind, but such case is rare and
    // rewinding all items simplifes the code.
    if (!item_results->IsEmpty())
      Rewind(0, line_info);
    state_ = LineBreakState::kContinue;
    ResetRewindLoopDetector();
    return;
  }

  // Let this line overflow.
  line_info->SetHasOverflow();

  // If there was a break opportunity, the overflow should stop there.
  if (break_before) {
    RewindOverflow(break_before, line_info);
    return;
  }

  if (CanBreakAfterLast(*item_results)) {
    state_ = LineBreakState::kTrailing;
    return;
  }

  // No break opportunities. Break at the earliest break opportunity.
  DCHECK(std::all_of(item_results->begin(), item_results->end(),
                     [](const NGInlineItemResult& item_result) {
                       return !item_result.can_break_after;
                     }));
  state_ = LineBreakState::kOverflow;
}

// Rewind to |new_end| on overflow. If trailable items follow at |new_end|, they
// are included (not rewound).
void NGLineBreaker::RewindOverflow(unsigned new_end, NGLineInfo* line_info) {
  const Vector<NGInlineItem>& items = Items();
  const NGInlineItemResults& item_results = line_info->Results();
  DCHECK_LT(new_end, item_results.size());

  unsigned open_tag_count = 0;
  const String& text = Text();
  for (unsigned index = new_end; index < item_results.size(); index++) {
    const NGInlineItemResult& item_result = item_results[index];
    DCHECK(item_result.item);
    const NGInlineItem& item = *item_result.item;
    if (item.Type() == NGInlineItem::kText) {
      // Text items are trailable if they start with trailable spaces.
      DCHECK_GT(item_result.Length(), 0u);
      if (item_result.shape_result ||  // kNoResultIfOverflow if 'break-word'
          (break_anywhere_if_overflow_ && !override_break_anywhere_)) {
        DCHECK(item.Style());
        const EWhiteSpace white_space = item.Style()->WhiteSpace();
        if (ComputedStyle::AutoWrap(white_space) &&
            white_space != EWhiteSpace::kBreakSpaces &&
            IsBreakableSpace(text[item_result.StartOffset()])) {
          // If all characters are trailable spaces, check the next item.
          if (item_result.shape_result &&
              IsAllBreakableSpaces(text, item_result.StartOffset() + 1,
                                   item_result.EndOffset())) {
            continue;
          }
          // If this item starts with spaces followed by non-space characters,
          // rewind to before this item. |HandleText()| will include the spaces
          // and break there.
          // TODO: optimize more?
          Rewind(index, line_info);
          DCHECK_EQ(static_cast<unsigned>(&item - items.begin()), item_index_);
          HandleTrailingSpaces(item, line_info);
#if DCHECK_IS_ON()
          item_results.back().CheckConsistency(false);
#endif
          return;
        }
      }
    } else if (item.Type() == NGInlineItem::kControl) {
      // All control characters except newline are trailable if auto_wrap. We
      // should not have rewound if there was a newline, so safe to assume all
      // controls are trailable.
      DCHECK_NE(text[item_result.StartOffset()], kNewlineCharacter);
      DCHECK(item.Style());
      EWhiteSpace white_space = item.Style()->WhiteSpace();
      if (ComputedStyle::AutoWrap(white_space) &&
          white_space != EWhiteSpace::kBreakSpaces)
        continue;
    } else if (item.Type() == NGInlineItem::kOpenTag) {
      // Open tags are ambiguous. This open tag is not trailable:
      //   <span>text
      // but these are trailable:
      //   <span> text
      //   <span></span>text
      //   <span> </span>text
      // Count the nest-level and mark where the nest-level was 0.
      if (!open_tag_count)
        new_end = index;
      open_tag_count++;
      continue;
    } else if (item.Type() == NGInlineItem::kCloseTag) {
      if (open_tag_count > 0)
        open_tag_count--;
      continue;
    } else if (IsTrailableItemType(item.Type())) {
      continue;
    }

    // Found a non-trailable item. Rewind to before the item, or to before the
    // open tag if the nest-level is not zero.
    if (open_tag_count)
      index = new_end;
    state_ = LineBreakState::kDone;
    DCHECK(!line_info->IsLastLine());
    Rewind(index, line_info);
    return;
  }

  // The open tag turned out to be non-trailable if the nest-level is not zero.
  // Rewind to before the open tag.
  if (open_tag_count) {
    state_ = LineBreakState::kDone;
    DCHECK(!line_info->IsLastLine());
    Rewind(new_end, line_info);
    return;
  }

  // All items are trailable. Done without rewinding.
  trailing_whitespace_ = WhitespaceState::kUnknown;
  position_ = line_info->ComputeWidth();
  state_ = LineBreakState::kDone;
  DCHECK(!line_info->IsLastLine());
  if (item_index_ == items.size())
    line_info->SetIsLastLine(true);
}

void NGLineBreaker::Rewind(unsigned new_end, NGLineInfo* line_info) {
#if DCHECK_IS_ON()
  // Detect rewind-loop. If we're trying to rewind to the same index twice,
  // we're in the infinite loop.
  DCHECK(item_index_ != last_rewind_from_item_index_ ||
         new_end != last_rewind_to_item_index_)
      << item_index_ << ", " << offset_ << "->" << new_end;
  last_rewind_from_item_index_ = item_index_;
  last_rewind_to_item_index_ = new_end;
#endif

  NGInlineItemResults& item_results = *line_info->MutableResults();
  DCHECK_LT(new_end, item_results.size());

  // Avoid rewinding floats if possible. They will be added back anyway while
  // processing trailing items even when zero available width. Also this saves
  // most cases where our support for rewinding positioned floats is not great
  // yet (see below.)
  while (item_results[new_end].item->Type() == NGInlineItem::kFloating) {
    // We assume floats can break after, or this may cause an infinite loop.
    DCHECK(item_results[new_end].can_break_after);
    ++new_end;
    if (new_end == item_results.size()) {
      position_ = line_info->ComputeWidth();
      return;
    }
  }

  // Because floats are added to |positioned_floats_| or |unpositioned_floats_|,
  // rewinding them needs to remove from these lists too.
  for (unsigned i = item_results.size(); i > new_end;) {
    NGInlineItemResult& rewind = item_results[--i];
    if (rewind.positioned_float) {
      // We assume floats can break after, or this may cause an infinite loop.
      DCHECK(rewind.can_break_after);
      // TODO(kojii): We do not have mechanism to remove once positioned floats
      // yet, and that rewinding them may lay it out twice. For now, prohibit
      // rewinding positioned floats. This may results in incorrect layout, but
      // still better than rewinding them.
      new_end = i + 1;
      if (new_end == item_results.size()) {
        position_ = line_info->ComputeWidth();
        return;
      }
      break;
    }
  }

  if (new_end) {
    // Use |results[new_end - 1].end_offset| because it may have been truncated
    // and may not be equal to |results[new_end].start_offset|.
    MoveToNextOf(item_results[new_end - 1]);
    trailing_whitespace_ = WhitespaceState::kUnknown;
  } else {
    // When rewinding all items, use |results[0].start_offset|.
    const NGInlineItemResult& first_remove = item_results[new_end];
    item_index_ = first_remove.item_index;
    offset_ = first_remove.StartOffset();
    trailing_whitespace_ = WhitespaceState::kLeading;
    maybe_have_end_overhang_ = false;
  }
  SetCurrentStyle(ComputeCurrentStyle(new_end, line_info));

  item_results.Shrink(new_end);

  trailing_collapsible_space_.reset();
  position_ = line_info->ComputeWidth();
}

// Returns the style to use for |item_result_index|. Normally when handling
// items sequentially, the current style is updated on open/close tag. When
// rewinding, this function computes the style for the specified item.
const ComputedStyle& NGLineBreaker::ComputeCurrentStyle(
    unsigned item_result_index,
    NGLineInfo* line_info) const {
  const NGInlineItemResults& item_results = line_info->Results();

  // Use the current item if it can compute the current style.
  const NGInlineItem* item = item_results[item_result_index].item;
  DCHECK(item);
  if (item->Type() == NGInlineItem::kText ||
      item->Type() == NGInlineItem::kCloseTag) {
    DCHECK(item->Style());
    return *item->Style();
  }

  // Otherwise look back an item that can compute the current style.
  while (item_result_index) {
    item = item_results[--item_result_index].item;
    if (item->Type() == NGInlineItem::kText ||
        item->Type() == NGInlineItem::kOpenTag) {
      DCHECK(item->Style());
      return *item->Style();
    }
    if (item->Type() == NGInlineItem::kCloseTag)
      return item->GetLayoutObject()->Parent()->StyleRef();
  }

  // Use the style at the beginning of the line if no items are available.
  if (break_token_) {
    DCHECK(break_token_->Style());
    return *break_token_->Style();
  }
  return line_info->LineStyle();
}

void NGLineBreaker::SetCurrentStyle(const ComputedStyle& style) {
  if (&style == current_style_.get()) {
#if DCHECK_IS_ON()
    // Check that cache fields are already setup correctly.
    DCHECK_EQ(auto_wrap_, style.AutoWrap());
    if (auto_wrap_) {
      DCHECK_EQ(enable_soft_hyphen_, style.GetHyphens() != Hyphens::kNone);
      DCHECK_EQ(break_iterator_.Locale(), style.LocaleForLineBreakIterator());
    }
    ShapeResultSpacing<String> spacing(spacing_.Text());
    spacing.SetSpacing(style.GetFontDescription());
    DCHECK_EQ(spacing.LetterSpacing(), spacing_.LetterSpacing());
    DCHECK_EQ(spacing.WordSpacing(), spacing_.WordSpacing());
#endif
    return;
  }
  current_style_ = &style;

  auto_wrap_ = style.AutoWrap();

  if (auto_wrap_) {
    LineBreakType line_break_type;
    EWordBreak word_break = style.WordBreak();
    switch (word_break) {
      case EWordBreak::kNormal:
        line_break_type = LineBreakType::kNormal;
        break;
      case EWordBreak::kBreakAll:
        line_break_type = LineBreakType::kBreakAll;
        break;
      case EWordBreak::kBreakWord:
        line_break_type = LineBreakType::kNormal;
        break;
      case EWordBreak::kKeepAll:
        line_break_type = LineBreakType::kKeepAll;
        break;
    }
    EOverflowWrap overflow_wrap = style.OverflowWrap();
    break_anywhere_if_overflow_ =
        word_break == EWordBreak::kBreakWord ||
        overflow_wrap == EOverflowWrap::kAnywhere ||
        // `overflow-/word-wrap: break-word` affects layout but not min-content.
        (overflow_wrap == EOverflowWrap::kBreakWord &&
         mode_ == NGLineBreakerMode::kContent);
    if (UNLIKELY((override_break_anywhere_ && break_anywhere_if_overflow_) ||
                 style.GetLineBreak() == LineBreak::kAnywhere)) {
      line_break_type = LineBreakType::kBreakCharacter;
    }
    break_iterator_.SetBreakType(line_break_type);

    enable_soft_hyphen_ = style.GetHyphens() != Hyphens::kNone;
    hyphenation_ = style.GetHyphenation();

    if (style.WhiteSpace() == EWhiteSpace::kBreakSpaces)
      break_iterator_.SetBreakSpace(BreakSpaceType::kAfterEverySpace);

    break_iterator_.SetLocale(style.LocaleForLineBreakIterator());
  }

  spacing_.SetSpacing(style.GetFontDescription());
}

void NGLineBreaker::MoveToNextOf(const NGInlineItem& item) {
  offset_ = item.EndOffset();
  item_index_++;
#if DCHECK_IS_ON()
  const Vector<NGInlineItem>& items = Items();
  if (item_index_ < items.size()) {
    items[item_index_].AssertOffset(offset_);
  } else {
    DCHECK_EQ(offset_, Text().length());
  }
#endif
}

void NGLineBreaker::MoveToNextOf(const NGInlineItemResult& item_result) {
  offset_ = item_result.EndOffset();
  item_index_ = item_result.item_index;
  DCHECK(item_result.item);
  if (offset_ == item_result.item->EndOffset())
    item_index_++;
}

scoped_refptr<NGInlineBreakToken> NGLineBreaker::CreateBreakToken(
    const NGLineInfo& line_info) const {
  DCHECK(current_style_);
  const Vector<NGInlineItem>& items = Items();
  DCHECK_LE(item_index_, items.size());
  if (item_index_ >= items.size())
    return NGInlineBreakToken::Create(node_);
  return NGInlineBreakToken::Create(
      node_, current_style_.get(), item_index_, offset_,
      ((is_after_forced_break_ ? NGInlineBreakToken::kIsForcedBreak : 0) |
       (line_info.UseFirstLineStyle() ? NGInlineBreakToken::kUseFirstLineStyle
                                      : 0)));
}

}  // namespace blink