path: root/chromium/third_party/blink/renderer/core/layout/ng/inline/ng_fragment_items_builder.cc

// Copyright 2019 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_fragment_items_builder.h"

#include "third_party/blink/renderer/core/layout/geometry/writing_mode_converter.h"
#include "third_party/blink/renderer/core/layout/ng/inline/ng_fragment_items.h"
#include "third_party/blink/renderer/core/layout/ng/inline/ng_inline_cursor.h"
#include "third_party/blink/renderer/core/layout/ng/ng_box_fragment_builder.h"
#include "third_party/blink/renderer/core/layout/ng/ng_physical_box_fragment.h"

namespace blink {

NGFragmentItemsBuilder::NGFragmentItemsBuilder(
    WritingDirectionMode writing_direction)
    : node_(nullptr), writing_direction_(writing_direction) {}

NGFragmentItemsBuilder::NGFragmentItemsBuilder(
    const NGInlineNode& node,
    WritingDirectionMode writing_direction)
    : node_(node), writing_direction_(writing_direction) {
  const NGInlineItemsData& items_data = node.ItemsData(false);
  text_content_ = items_data.text_content;
  const NGInlineItemsData& first_line = node.ItemsData(true);
  if (&items_data != &first_line)
    first_line_text_content_ = first_line.text_content;

  // For a very large inline formatting context, the vector reallocation becomes
  // hot. Estimate the number of items by assuming 40 characters can fit in a
  // line, and each line contains 3 items; a line box, an inline box, and a
  // text. If it will require more than one reallocations, make an initial
  // reservation here.
  const wtf_size_t estimated_item_count = text_content_.length() / 40 * 3;
  if (UNLIKELY(estimated_item_count > items_.capacity() * 2))
    items_.ReserveInitialCapacity(estimated_item_count);
}

NGFragmentItemsBuilder::~NGFragmentItemsBuilder() {
  ReleaseCurrentLogicalLineItems();

  // Delete leftovers that were associated, but were not added.
  for (const auto& i : line_items_map_) {
    if (i.value != line_items_pool_)
      delete i.value;
  }
}

void NGFragmentItemsBuilder::AddLogicalLineItemsPool(
    NGLogicalLineItems* line_items) {
  DCHECK(line_items);
  DCHECK(!line_items_pool_);
  line_items_pool_ = line_items;
  DCHECK(!is_line_items_pool_acquired_);
}

void NGFragmentItemsBuilder::ReleaseCurrentLogicalLineItems() {
  if (!current_line_items_)
    return;
  if (current_line_items_ == line_items_pool_) {
    DCHECK(is_line_items_pool_acquired_);
    is_line_items_pool_acquired_ = false;
  } else {
    delete current_line_items_;
  }
  current_line_items_ = nullptr;
}

void NGFragmentItemsBuilder::MoveCurrentLogicalLineItemsToMap() {
  if (!current_line_items_) {
    DCHECK(!current_line_fragment_);
    return;
  }
  DCHECK(current_line_fragment_);
  line_items_map_.insert(current_line_fragment_, current_line_items_);
  current_line_fragment_ = nullptr;
  current_line_items_ = nullptr;
}

NGLogicalLineItems* NGFragmentItemsBuilder::AcquireLogicalLineItems() {
  if (line_items_pool_ && !is_line_items_pool_acquired_) {
    is_line_items_pool_acquired_ = true;
    return line_items_pool_;
  }
  MoveCurrentLogicalLineItemsToMap();
  DCHECK(!current_line_items_);
  current_line_items_ = new NGLogicalLineItems();
  return current_line_items_;
}

void NGFragmentItemsBuilder::AssociateLogicalLineItems(
    NGLogicalLineItems* line_items,
    const NGPhysicalFragment& line_fragment) {
  DCHECK(!current_line_items_ || current_line_items_ == line_items);
  current_line_items_ = line_items;
  DCHECK(!current_line_fragment_);
  current_line_fragment_ = &line_fragment;
}

void NGFragmentItemsBuilder::AddLine(
    const NGPhysicalLineBoxFragment& line_fragment,
    const LogicalOffset& offset) {
  DCHECK(!is_converted_to_physical_);
  if (&line_fragment == current_line_fragment_) {
    DCHECK(current_line_items_);
    current_line_fragment_ = nullptr;
  } else {
    MoveCurrentLogicalLineItemsToMap();
    DCHECK(!current_line_items_);
    current_line_items_ = line_items_map_.Take(&line_fragment);
    DCHECK(current_line_items_);
  }
  NGLogicalLineItems* line_items = current_line_items_;

  // Reserve the capacity for (children + line box item).
  const wtf_size_t size_before = items_.size();
  const wtf_size_t estimated_size = size_before + line_items->size() + 1;
  const wtf_size_t old_capacity = items_.capacity();
  if (estimated_size > old_capacity)
    items_.ReserveCapacity(std::max(estimated_size, old_capacity * 2));

  // Add an empty item so that the start of the line can be set later.
  const wtf_size_t line_start_index = items_.size();
  items_.emplace_back(offset, line_fragment);

  AddItems(line_items->begin(), line_items->end());

  // All children are added. Create an item for the start of the line.
  NGFragmentItem& line_item = items_[line_start_index].item;
  const wtf_size_t item_count = items_.size() - line_start_index;
  DCHECK_EQ(line_item.DescendantsCount(), 1u);
  line_item.SetDescendantsCount(item_count);

  // Keep children's offsets relative to |line|. They will be adjusted later in
  // |ConvertToPhysical()|.

  ReleaseCurrentLogicalLineItems();

  DCHECK_LE(items_.size(), estimated_size);
}

void NGFragmentItemsBuilder::AddItems(NGLogicalLineItem* child_begin,
                                      NGLogicalLineItem* child_end) {
  DCHECK(!is_converted_to_physical_);

  const WritingMode writing_mode = GetWritingMode();
  for (NGLogicalLineItem* child_iter = child_begin; child_iter != child_end;) {
    NGLogicalLineItem& child = *child_iter;
    // OOF children should have been added to their parent box fragments.
    DCHECK(!child.out_of_flow_positioned_box);
    if (!child.CanCreateFragmentItem()) {
      ++child_iter;
      continue;
    }

    if (child.children_count <= 1) {
      items_.emplace_back(child.rect.offset, std::move(child), writing_mode);
      ++child_iter;
      continue;
    }

    const unsigned children_count = child.children_count;
    // Children of inline boxes are flattened and added to |items_|, with the
    // count of descendant items to preserve the tree structure.
    //
    // Add an empty item so that the start of the box can be set later.
    const wtf_size_t box_start_index = items_.size();
    items_.emplace_back(child.rect.offset, std::move(child), writing_mode);

    // Add all children, including their desendants, skipping this item.
    CHECK_GE(children_count, 1u);  // 0 will loop infinitely.
    NGLogicalLineItem* end_child_iter = child_iter + children_count;
    CHECK_LE(end_child_iter - child_begin, child_end - child_begin);
    AddItems(child_iter + 1, end_child_iter);
    child_iter = end_child_iter;

    // All children are added. Compute how many items are actually added. The
    // number of items added may be different from |children_count|.
    const wtf_size_t item_count = items_.size() - box_start_index;
    NGFragmentItem& box_item = items_[box_start_index].item;
    DCHECK_EQ(box_item.DescendantsCount(), 1u);
    box_item.SetDescendantsCount(item_count);
  }
}

void NGFragmentItemsBuilder::AddListMarker(
    const NGPhysicalBoxFragment& marker_fragment,
    const LogicalOffset& offset) {
  DCHECK(!is_converted_to_physical_);

  // Resolved direction matters only for inline items, and outside list markers
  // are not inline.
  const TextDirection resolved_direction = TextDirection::kLtr;
  items_.emplace_back(offset, marker_fragment, resolved_direction);
}

NGFragmentItemsBuilder::AddPreviousItemsResult
NGFragmentItemsBuilder::AddPreviousItems(
    const NGPhysicalBoxFragment& container,
    const NGFragmentItems& items,
    NGBoxFragmentBuilder* container_builder,
    const NGFragmentItem* end_item,
    wtf_size_t max_lines) {
  if (end_item) {
    DCHECK(node_);
    DCHECK(container_builder);
    DCHECK(text_content_);

    if (UNLIKELY(items.FirstLineText() && !first_line_text_content_)) {
      // Don't reuse previous items if they have different `::first-line` style
      // but |this| doesn't. Reaching here means that computed style doesn't
      // change, but |NGFragmentItem| has wrong |NGStyleVariant|.
      return AddPreviousItemsResult();
    }
  } else {
    DCHECK(!container_builder);
    DCHECK(!text_content_);
    text_content_ = items.NormalText();
    first_line_text_content_ = items.FirstLineText();
  }

  DCHECK(items_.IsEmpty());
  const NGFragmentItems::Span source_items = items.Items();
  const wtf_size_t estimated_size = source_items.size();
  items_.ReserveCapacity(estimated_size);

  // Convert offsets to logical. The logic is opposite to |ConvertToPhysical|.
  // This is needed because the container size may be different, in that case,
  // the physical offsets are different when `writing-mode: vertial-rl`.
  DCHECK(!is_converted_to_physical_);
  const WritingModeConverter converter(GetWritingDirection(), container.Size());
  const WritingMode writing_mode = GetWritingMode();
  WritingModeConverter line_converter(
      {ToLineWritingMode(writing_mode), TextDirection::kLtr});

  const NGInlineBreakToken* last_break_token = nullptr;
  const NGInlineItemsData* items_data = nullptr;
  LayoutUnit used_block_size;
  wtf_size_t line_count = 0;

  for (NGInlineCursor cursor(container, items); cursor;) {
    DCHECK(cursor.Current().Item());
    const NGFragmentItem& item = *cursor.Current().Item();
    if (&item == end_item)
      break;
    DCHECK(!item.IsDirty());

    const LogicalOffset item_offset =
        converter.ToLogical(item.OffsetInContainerFragment(), item.Size());

    if (item.Type() == NGFragmentItem::kLine) {
      DCHECK(item.LineBoxFragment());
      if (end_item) {
        // Check if this line has valid item_index and offset.
        const NGPhysicalLineBoxFragment* line_fragment = item.LineBoxFragment();
        const NGInlineBreakToken* break_token =
            To<NGInlineBreakToken>(line_fragment->BreakToken());
        DCHECK(break_token);
        const NGInlineItemsData* current_items_data;
        if (UNLIKELY(break_token->UseFirstLineStyle()))
          current_items_data = &node_.ItemsData(true);
        else if (items_data)
          current_items_data = items_data;
        else
          current_items_data = items_data = &node_.ItemsData(false);
        if (UNLIKELY(!current_items_data->IsValidOffset(
                break_token->ItemIndex(), break_token->TextOffset()))) {
          NOTREACHED();
          break;
        }

        last_break_token = break_token;
        container_builder->AddChild(*line_fragment, item_offset);
        used_block_size +=
            item.Size().ConvertToLogical(writing_mode).block_size;
      }

      items_.emplace_back(item_offset, item);
      const PhysicalRect line_box_bounds = item.RectInContainerFragment();
      line_converter.SetOuterSize(line_box_bounds.size);
      for (NGInlineCursor line = cursor.CursorForDescendants(); line;
           line.MoveToNext()) {
        const NGFragmentItem& line_child = *line.Current().Item();
        DCHECK(line_child.CanReuse());
        items_.emplace_back(
            line_converter.ToLogical(
                line_child.OffsetInContainerFragment() - line_box_bounds.offset,
                line_child.Size()),
            line_child);
      }
      if (++line_count == max_lines)
        break;
      cursor.MoveToNextSkippingChildren();
      continue;
    }

    DCHECK_NE(item.Type(), NGFragmentItem::kLine);
    DCHECK(!end_item);
    items_.emplace_back(item_offset, item);
    cursor.MoveToNext();
  }
  DCHECK_LE(items_.size(), estimated_size);

  if (end_item && last_break_token) {
    DCHECK_GT(line_count, 0u);
    DCHECK(!max_lines || line_count <= max_lines);
    return AddPreviousItemsResult{last_break_token, used_block_size, line_count,
                                  true};
  }
  return AddPreviousItemsResult();
}

const NGFragmentItemsBuilder::ItemWithOffsetList& NGFragmentItemsBuilder::Items(
    const PhysicalSize& outer_size) {
  ConvertToPhysical(outer_size);
  return items_;
}

// Convert internal logical offsets to physical. Items are kept with logical
// offset until outer box size is determined.
void NGFragmentItemsBuilder::ConvertToPhysical(const PhysicalSize& outer_size) {
  if (is_converted_to_physical_)
    return;

  const WritingModeConverter converter(GetWritingDirection(), outer_size);
  // Children of lines have line-relative offsets. Use line-writing mode to
  // convert their logical offsets. Use `kLtr` because inline items are after
  // bidi-reoder, and that their offset is visual, not logical.
  WritingModeConverter line_converter(
      {ToLineWritingMode(GetWritingMode()), TextDirection::kLtr});

  for (ItemWithOffset* iter = items_.begin(); iter != items_.end(); ++iter) {
    NGFragmentItem* item = &iter->item;
    item->SetOffset(converter.ToPhysical(iter->offset, item->Size()));

    // Transform children of lines separately from children of the block,
    // because they may have different directions from the block. To do
    // this, their offsets are relative to their containing line box.
    if (item->Type() == NGFragmentItem::kLine) {
      unsigned descendants_count = item->DescendantsCount();
      DCHECK(descendants_count);
      if (descendants_count) {
        const PhysicalRect line_box_bounds = item->RectInContainerFragment();
        line_converter.SetOuterSize(line_box_bounds.size);
        while (--descendants_count) {
          ++iter;
          DCHECK_NE(iter, items_.end());
          item = &iter->item;
          item->SetOffset(
              line_converter.ToPhysical(iter->offset, item->Size()) +
              line_box_bounds.offset);
        }
      }
    }
  }

  is_converted_to_physical_ = true;
}

base::Optional<LogicalOffset> NGFragmentItemsBuilder::LogicalOffsetFor(
    const LayoutObject& layout_object) const {
  for (const ItemWithOffset& item : items_) {
    if (item->GetLayoutObject() == &layout_object)
      return item.offset;
  }
  return base::nullopt;
}

void NGFragmentItemsBuilder::MoveChildrenInBlockDirection(LayoutUnit delta) {
  DCHECK(!is_converted_to_physical_);
  for (ItemWithOffset* iter = items_.begin(); iter != items_.end(); ++iter) {
    if (iter->item->Type() == NGFragmentItem::kLine) {
      iter->offset.block_offset += delta;
      std::advance(iter, iter->item->DescendantsCount() - 1);
      DCHECK_LE(iter, items_.end());
      continue;
    }
    iter->offset.block_offset += delta;
  }
}

void NGFragmentItemsBuilder::ToFragmentItems(const PhysicalSize& outer_size,
                                             void* data) {
  DCHECK(text_content_);
  ConvertToPhysical(outer_size);
  new (data) NGFragmentItems(this);
}

}  // namespace blink