[LayoutNG] Initial support for the 'vertical-align' property

third_party/WebKit/Source/core/layout/ng/inline/ng_inline_layout_algorithm.cc

Index: third_party/WebKit/Source/core/layout/ng/inline/ng_inline_layout_algorithm.cc
diff --git a/third_party/WebKit/Source/core/layout/ng/inline/ng_inline_layout_algorithm.cc b/third_party/WebKit/Source/core/layout/ng/inline/ng_inline_layout_algorithm.cc
index d78d6b0761ca57ea16f2a0389a06c37edbcd456c..b8466de1d6513e7e0c37d33319b49c208d77b7a6 100644
--- a/third_party/WebKit/Source/core/layout/ng/inline/ng_inline_layout_algorithm.cc
+++ b/third_party/WebKit/Source/core/layout/ng/inline/ng_inline_layout_algorithm.cc
@@ -271,6 +271,11 @@ bool NGInlineLayoutAlgorithm::CreateLineUpToLastBreakOpportunity() {
   // |last_break_opportunity|.
   start_index_ = last_break_opportunity_index_;
   start_offset_ = last_break_opportunity_offset_;
+  // If the offset is at the end of the item, move to the next item.
+  if (start_offset_ == items[start_index_].EndOffset() &&
+      start_index_ < items.size() - 1) {
+    start_index_++;
+  }
   DCHECK_GE(end_position_, last_break_opportunity_position_);
   end_position_ -= last_break_opportunity_position_;
   last_break_opportunity_position_ = LayoutUnit();
@@ -304,8 +309,9 @@ void NGInlineLayoutAlgorithm::BidiReorder(
   // runs instead of characters.
   Vector<UBiDiLevel, 32> levels;
   levels.ReserveInitialCapacity(line_item_chunks->size());
+  const Vector<NGLayoutInlineItem>& items = Node()->Items();
   for (const auto& chunk : *line_item_chunks)
-    levels.push_back(Node()->Items()[chunk.index].BidiLevel());
+    levels.push_back(items[chunk.index].BidiLevel());
   Vector<int32_t, 32> indices_in_visual_order(line_item_chunks->size());
   NGBidiParagraph::IndicesInVisualOrder(levels, &indices_in_visual_order);
 
@@ -318,6 +324,23 @@ void NGInlineLayoutAlgorithm::BidiReorder(
     line_item_chunks_in_visual_order[visual_index] =
         (*line_item_chunks)[logical_index];
   }
+
+  // Keep Open before Close in the visual order.
+  HashMap<LayoutObject*, unsigned> first_index;
+  for (unsigned i = 0; i < line_item_chunks_in_visual_order.size(); i++) {
+    LineItemChunk& chunk = line_item_chunks_in_visual_order[i];
+    const NGLayoutInlineItem& item = items[chunk.index];
+    if (item.Type() != NGLayoutInlineItem::kOpenTag &&
+        item.Type() != NGLayoutInlineItem::kCloseTag) {
+      continue;
+    }
+    auto result = first_index.insert(item.GetLayoutObject(), i);
+    if (!result.is_new_entry && item.Type() == NGLayoutInlineItem::kOpenTag) {
+      std::swap(line_item_chunks_in_visual_order[i],
+                line_item_chunks_in_visual_order[result.stored_value->value]);
+    }
+  }
+
   line_item_chunks->Swap(line_item_chunks_in_visual_order);
 }
 
@@ -383,35 +406,29 @@ bool NGInlineLayoutAlgorithm::PlaceItems(
   // Compute heights of all inline items by placing the dominant baseline at 0.
   // The baseline is adjusted after the height of the line box is computed.
   NGTextFragmentBuilder text_builder(Node());
+  NGInlineBoxState* box = OnBeginPlaceItems();
   LayoutUnit inline_size;
   for (const auto& line_item_chunk : line_item_chunks) {
     const NGLayoutInlineItem& item = items[line_item_chunk.index];
-    // Skip bidi controls.
-    if (!item.GetLayoutObject())
-      continue;
-
-    LayoutUnit block_start;
+    LayoutUnit line_top;
     if (item.Type() == NGLayoutInlineItem::kText) {
       DCHECK(item.GetLayoutObject()->IsText());
-      const ComputedStyle* style = item.Style();
-      // The direction of a fragment is the CSS direction to resolve logical
-      // properties, not the resolved bidi direction.
-      text_builder.SetDirection(style->Direction())
-          .SetInlineSize(line_item_chunk.inline_size);
-
-      // |InlineTextBoxPainter| sets the baseline at |top +
-      // ascent-of-primary-font|. Compute |top| to match.
-      NGLineHeightMetrics metrics(*style, baseline_type_);
-      block_start = -metrics.ascent;
-      metrics.AddLeading(style->ComputedLineHeightAsFixed());
-      text_builder.SetBlockSize(metrics.LineHeight());
-      line_box.UniteMetrics(metrics);
-
+      if (box->text_metrics.IsEmpty())
+        box->ComputeTextMetrics(item, baseline_type_);
+      line_top = box->text_top;
+      text_builder.SetSize(
+          {line_item_chunk.inline_size, box->text_metrics.LineHeight()});
       // Take all used fonts into account if 'line-height: normal'.
-      if (style->LineHeight().IsNegative())
+      if (box->include_used_fonts)
         AccumulateUsedFonts(item, line_item_chunk, &line_box);
+    } else if (item.Type() == NGLayoutInlineItem::kOpenTag) {
+      box = OnOpenTag(item, &line_box, &text_builder);
+      continue;
+    } else if (item.Type() == NGLayoutInlineItem::kCloseTag) {
+      box = OnCloseTag(item, &line_box, box);
+      continue;
     } else if (item.Type() == NGLayoutInlineItem::kAtomicInline) {
-      block_start = PlaceAtomicInline(item, &line_box, &text_builder);
+      line_top = PlaceAtomicInline(item, &line_box, &text_builder);
     } else if (item.Type() == NGLayoutInlineItem::kOutOfFlowPositioned) {
       // TODO(layout-dev): Report the correct static position for the out of
       // flow descendant. We can't do this here yet as it doesn't know the
@@ -435,7 +452,7 @@ bool NGInlineLayoutAlgorithm::PlaceItems(
     NGLogicalOffset logical_offset(
         inline_size + current_opportunity_.InlineStartOffset() -
             ConstraintSpace().BfcOffset().inline_offset,
-        block_start);
+        line_top);
     line_box.AddChild(std::move(text_fragment), logical_offset);
     inline_size += line_item_chunk.inline_size;
   }
@@ -444,6 +461,8 @@ bool NGInlineLayoutAlgorithm::PlaceItems(
     return true;  // The line was empty.
   }
 
+  OnEndPlaceItems(&line_box);
+
   // The baselines are always placed at pixel boundaries. Not doing so results
   // in incorrect layout of text decorations, most notably underlines.
   LayoutUnit baseline = content_size_ + line_box.Metrics().ascent;
@@ -480,6 +499,166 @@ bool NGInlineLayoutAlgorithm::PlaceItems(
   return true;
 }
 
+// Initialize the box state stack for a new line.
+// @return The initial box state for the line.
+NGInlineBoxState* NGInlineLayoutAlgorithm::OnBeginPlaceItems() {
+  if (box_states_.IsEmpty()) {
+    // For the first line, push a box state for the line itself.
+    box_states_.Resize(1);
+    NGInlineBoxState* box = &box_states_.back();
+    box->fragment_start = 0;
+    box->style = &LineStyle();
+    return box;
+  }
+
+  // For the following lines, clear states that are not shared across lines.
+  for (auto& box : box_states_) {
+    box.fragment_start = 0;
+    box.metrics = NGLineHeightMetrics();
+    DCHECK(box.pending_descendants.IsEmpty());
+  }
+  return &box_states_.back();
+}
+
+// Push a box state stack.
+NGInlineBoxState* NGInlineLayoutAlgorithm::OnOpenTag(
+    const NGLayoutInlineItem& item,
+    NGLineBoxFragmentBuilder* line_box,
+    NGTextFragmentBuilder* text_builder) {
+  box_states_.Resize(box_states_.size() + 1);
+  NGInlineBoxState* box = &box_states_.back();
+  box->fragment_start = line_box->Children().size();
+  box->style = item.Style();
+  text_builder->SetDirection(box->style->Direction());
+  return box;
+}
+
+// Pop a box state stack.
+NGInlineBoxState* NGInlineLayoutAlgorithm::OnCloseTag(
+    const NGLayoutInlineItem& item,
+    NGLineBoxFragmentBuilder* line_box,
+    NGInlineBoxState* box) {
+  EndBoxState(box, line_box);
+  // TODO(kojii): When the algorithm restarts from a break token, the stack may
+  // underflow. We need either synthesize a missing box state, or push all
+  // parents on initialize.
+  box_states_.pop_back();
+  return &box_states_.back();
+}
+
+// Compute all the pending positioning at the end of a line.
+void NGInlineLayoutAlgorithm::OnEndPlaceItems(
+    NGLineBoxFragmentBuilder* line_box) {
+  for (auto it = box_states_.rbegin(); it != box_states_.rend(); ++it) {
+    NGInlineBoxState* box = &(*it);
+    EndBoxState(box, line_box);
+  }
+  line_box->UniteMetrics(box_states_.front().metrics);
+}
+
+// End of a box state, either explicitly by close tag, or implicitly at the end
+// of a line.
+void NGInlineLayoutAlgorithm::EndBoxState(NGInlineBoxState* box,
+                                          NGLineBoxFragmentBuilder* line_box) {
+  ApplyBaselineShift(box, line_box);
+
+  // Unite the metrics to the parent box.
+  if (box != box_states_.begin()) {
+    box[-1].metrics.Unite(box->metrics);
+  }
+}
+
+// Compute vertical position for the 'vertical-align' property.
+// The timing to apply varies by values; some values apply at the layout of
+// the box was computed. Other values apply when the layout of the parent or
+// the line box was computed.
+// https://www.w3.org/TR/CSS22/visudet.html#propdef-vertical-align
+// https://www.w3.org/TR/css-inline-3/#propdef-vertical-align
+void NGInlineLayoutAlgorithm::ApplyBaselineShift(
+    NGInlineBoxState* box,
+    NGLineBoxFragmentBuilder* line_box) {
+  // Compute descendants that depend on the layout size of this box if any.
+  LayoutUnit baseline_shift;
+  if (!box->pending_descendants.IsEmpty()) {
+    for (const auto& child : box->pending_descendants) {
+      switch (child.vertical_align) {
+        case EVerticalAlign::kTextTop:
+        case EVerticalAlign::kTop:
+          baseline_shift = child.metrics.ascent - box->metrics.ascent;
+          break;
+        case EVerticalAlign::kTextBottom:
+        case EVerticalAlign::kBottom:
+          baseline_shift = box->metrics.descent - child.metrics.descent;
+          break;
+        default:
+          NOTREACHED();
+          continue;
+      }
+      line_box->MoveChildrenInBlockDirection(
+          baseline_shift, child.fragment_start, child.fragment_end);
+    }
+    box->pending_descendants.Clear();
+  }
+
+  const ComputedStyle& style = *box->style;
+  EVerticalAlign vertical_align = style.VerticalAlign();
+  if (vertical_align == EVerticalAlign::kBaseline)
+    return;
+
+  // 'vertical-align' aplies only to inline-level elements.
+  if (box == box_states_.begin())
+    return;
+
+  // Check if there are any fragments to move.
+  unsigned fragment_end = line_box->Children().size();
+  if (box->fragment_start == fragment_end)
+    return;
+
+  switch (vertical_align) {
+    case EVerticalAlign::kSub:
+      baseline_shift = style.ComputedFontSizeAsFixed() / 5 + 1;
+      break;
+    case EVerticalAlign::kSuper:
+      baseline_shift = -(style.ComputedFontSizeAsFixed() / 3 + 1);
+      break;
+    case EVerticalAlign::kLength: {
+      // 'Percentages: refer to the 'line-height' of the element itself'.
+      // https://www.w3.org/TR/CSS22/visudet.html#propdef-vertical-align
+      const Length& length = style.GetVerticalAlignLength();
+      LayoutUnit line_height = length.IsPercentOrCalc()
+                                   ? style.ComputedLineHeightAsFixed()
+                                   : box->text_metrics.LineHeight();
+      baseline_shift = -ValueForLength(length, line_height);
+      break;
+    }
+    case EVerticalAlign::kMiddle:
+      baseline_shift = (box->metrics.ascent - box->metrics.descent) / 2;
+      if (const SimpleFontData* font_data = style.GetFont().PrimaryFont()) {
+        baseline_shift -= LayoutUnit::FromFloatRound(
+            font_data->GetFontMetrics().XHeight() / 2);
+      }
+      break;
+    case EVerticalAlign::kBaselineMiddle:
+      baseline_shift = (box->metrics.ascent - box->metrics.descent) / 2;
+      break;
+    case EVerticalAlign::kTop:
+    case EVerticalAlign::kBottom:
+      // 'top' and 'bottom' require the layout size of the line box.
+      box_states_.front().pending_descendants.push_back(NGPendingPositions{
+          box->fragment_start, fragment_end, box->metrics, vertical_align});
+      return;
+    default:
+      // Other values require the layout size of the parent box.
+      SECURITY_CHECK(box != box_states_.begin());
+      box[-1].pending_descendants.push_back(NGPendingPositions{
+          box->fragment_start, fragment_end, box->metrics, vertical_align});
+      return;
+  }
+  box->metrics.Move(baseline_shift);
+  line_box->MoveChildrenInBlockDirection(baseline_shift, box->fragment_start,
+                                         fragment_end);
+}
+
 void NGInlineLayoutAlgorithm::AccumulateUsedFonts(
     const NGLayoutInlineItem& item,
     const LineItemChunk& line_item_chunk,
@@ -508,21 +687,23 @@ LayoutUnit NGInlineLayoutAlgorithm::PlaceAtomicInline(
   // TODO(kojii): Try to eliminate the wrapping text fragment and use the
   // |fragment| directly. Currently |CopyFragmentDataToLayoutBlockFlow|
   // requires a text fragment.
-  text_builder->SetInlineSize(fragment.InlineSize()).SetBlockSize(block_size);
+  text_builder->SetSize({fragment.InlineSize(), block_size});
 
   // TODO(kojii): Add baseline position to NGPhysicalFragment.
-  LayoutBox* box = ToLayoutBox(item.GetLayoutObject());
+  LayoutBox* layout_box = ToLayoutBox(item.GetLayoutObject());
   LineDirectionMode line_direction_mode =
       IsHorizontalWritingMode() ? LineDirectionMode::kHorizontalLine
                                 : LineDirectionMode::kVerticalLine;
-  LayoutUnit baseline_offset(box->BaselinePosition(
+  LayoutUnit baseline_offset(layout_box->BaselinePosition(
       baseline_type_, IsFirstLine(), line_direction_mode));
-  line_box->UniteMetrics({baseline_offset, block_size - baseline_offset});
+
+  NGLineHeightMetrics metrics(baseline_offset, block_size - baseline_offset);
+  box_states_.back().metrics.Unite(metrics);
 
   // TODO(kojii): Figure out what to do with OOF in NGLayoutResult.
   // Floats are ok because atomic inlines are BFC?
 
-  return -baseline_offset;
+  return -metrics.ascent;
 }
 
 void NGInlineLayoutAlgorithm::FindNextLayoutOpportunity() {