Make NGInlineItemsBuilder construct whitespace-collapsed offset mapping

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

Index: third_party/WebKit/Source/core/layout/ng/inline/ng_inline_items_builder.cc
diff --git a/third_party/WebKit/Source/core/layout/ng/inline/ng_inline_items_builder.cc b/third_party/WebKit/Source/core/layout/ng/inline/ng_inline_items_builder.cc
index 1038485901038a4a211dbd51b71fa06440c5c91e..49490f85df0dc26a1f85a3dae1b9f33c9bfc456d 100644
--- a/third_party/WebKit/Source/core/layout/ng/inline/ng_inline_items_builder.cc
+++ b/third_party/WebKit/Source/core/layout/ng/inline/ng_inline_items_builder.cc
@@ -15,15 +15,17 @@ NGInlineItemsBuilder::~NGInlineItemsBuilder() {
   DCHECK_EQ(text_.length(), items_->IsEmpty() ? 0 : items_->back().EndOffset());
 }
 
-String NGInlineItemsBuilder::ToString() {
+bool NGInlineItemsBuilder::Finalize() {
   // Segment Break Transformation Rules[1] defines to keep trailing new lines,
   // but it will be removed in Phase II[2]. We prefer not to add trailing new
   // lines and collapsible spaces in Phase I.
   // [1] https://drafts.csswg.org/css-text-3/#line-break-transform
   // [2] https://drafts.csswg.org/css-text-3/#white-space-phase-2
   unsigned next_start_offset = text_.length();
-  RemoveTrailingCollapsibleSpaceIfExists(&next_start_offset);
+  return RemoveTrailingCollapsibleSpaceIfExists(&next_start_offset);
+}
 
+String NGInlineItemsBuilder::ToString() {
   return text_.ToString();
 }
 
@@ -124,11 +126,34 @@ static inline bool IsControlItemCharacter(UChar c) {
   return c == kTabulationCharacter || c == kNewlineCharacter;
 }
 
-void NGInlineItemsBuilder::Append(const String& string,
-                                  const ComputedStyle* style,
-                                  LayoutObject* layout_object) {
+static inline size_t GetLastAppendedCharacterIndex(
+    const Vector<unsigned>& collapsed_indexes,
+    unsigned start,
+    unsigned end) {
+  if (start == end || collapsed_indexes.size() == end - start)
+    return kNotFound;
+  if (collapsed_indexes.IsEmpty())
+    return end - 1;
+  DCHECK_GT(end, collapsed_indexes.back());
+  if (collapsed_indexes.back() + 1 < end)
+    return collapsed_indexes.back() + 1;
+  for (unsigned i = collapsed_indexes.size(); i > 1;) {
+    unsigned current_collapsed = collapsed_indexes[--i];
+    unsigned last_collapsed = collapsed_indexes[i - 1];
+    DCHECK_GT(current_collapsed, last_collapsed);
+    if (last_collapsed + 1 < current_collapsed)
+      return last_collapsed + 1;
+  }
+  DCHECK_GT(collapsed_indexes[0], start);
+  return collapsed_indexes[0] - 1;
+}
+
+NGInlineItemsBuilder::AppendResult NGInlineItemsBuilder::Append(
+    const String& string,
+    const ComputedStyle* style,
+    LayoutObject* layout_object) {
   if (string.IsEmpty())
-    return;
+    return AppendResult(false, {});
   text_.ReserveCapacity(string.length());
 
   EWhiteSpace whitespace = style->WhiteSpace();
@@ -137,28 +162,30 @@ void NGInlineItemsBuilder::Append(const String& string,
   if (ComputedStyle::PreserveNewline(whitespace) && !is_svgtext_)
     return AppendWithPreservingNewlines(string, style, layout_object);
 
-  AppendWithWhiteSpaceCollapsing(string, 0, string.length(), style,
-                                 layout_object);
+  return AppendWithWhiteSpaceCollapsing(string, 0, string.length(), style,
+                                        layout_object);
 }
 
-void NGInlineItemsBuilder::AppendWithWhiteSpaceCollapsing(
+NGInlineItemsBuilder::AppendResult
+NGInlineItemsBuilder::AppendWithWhiteSpaceCollapsing(
     const String& string,
     unsigned start,
     unsigned end,
     const ComputedStyle* style,
     LayoutObject* layout_object) {
+  AppendResult result(false, {});
   unsigned start_offset = text_.length();
   for (unsigned i = start; i < end;) {
     UChar c = string[i];
     if (c == kNewlineCharacter) {
       // LayoutBR does not set preserve_newline, but should be preserved.
-      if (!i && end == 1 && layout_object && layout_object->IsBR()) {
-        AppendForcedBreak(style, layout_object);
-        return;
-      }
+      if (!i && end == 1 && layout_object && layout_object->IsBR())
+        return AppendResult(AppendForcedBreak(style, layout_object), {});
 
       if (last_collapsible_space_ == CollapsibleSpace::kNone)
         text_.Append(kSpaceCharacter);
+      else
+        result.second.push_back(i);
       last_collapsible_space_ = CollapsibleSpace::kNewline;
       i++;
       continue;
@@ -168,13 +195,26 @@ void NGInlineItemsBuilder::AppendWithWhiteSpaceCollapsing(
       if (last_collapsible_space_ == CollapsibleSpace::kNone) {
         text_.Append(kSpaceCharacter);
         last_collapsible_space_ = CollapsibleSpace::kSpace;
+      } else {
+        result.second.push_back(i);
       }
       i++;
       continue;
     }
 
     if (last_collapsible_space_ == CollapsibleSpace::kNewline) {
-      RemoveTrailingCollapsibleNewlineIfNeeded(&start_offset, string, i, style);
+      bool removed = RemoveTrailingCollapsibleNewlineIfNeeded(&start_offset,
+                                                              string, i, style);
+      if (removed) {
+        const size_t last_appended =
+            GetLastAppendedCharacterIndex(result.second, start, i);
+        if (last_appended == kNotFound) {
+          result.first = true;
+        } else {
+          result.second.push_back(last_appended);
+          std::sort(result.second.begin(), result.second.end());
+        }
+      }
     }
 
     size_t end_of_non_space = string.Find(IsCollapsibleSpace, i + 1);
@@ -189,11 +229,14 @@ void NGInlineItemsBuilder::AppendWithWhiteSpaceCollapsing(
     AppendItem(items_, NGInlineItem::kText, start_offset, text_.length(), style,
                layout_object);
   }
+
+  return result;
 }
 
 // Even when without whitespace collapsing, control characters (newlines and
 // tabs) are in their own control items to make the line breaker easier.
-void NGInlineItemsBuilder::AppendWithoutWhiteSpaceCollapsing(
+NGInlineItemsBuilder::AppendResult
+NGInlineItemsBuilder::AppendWithoutWhiteSpaceCollapsing(
     const String& string,
     const ComputedStyle* style,
     LayoutObject* layout_object) {
@@ -216,15 +259,27 @@ void NGInlineItemsBuilder::AppendWithoutWhiteSpaceCollapsing(
   }
 
   last_collapsible_space_ = CollapsibleSpace::kNone;
+  return AppendResult(false, {});
 }
 
-void NGInlineItemsBuilder::AppendWithPreservingNewlines(
+NGInlineItemsBuilder::AppendResult
+NGInlineItemsBuilder::AppendWithPreservingNewlines(
     const String& string,
     const ComputedStyle* style,
     LayoutObject* layout_object) {
+  AppendResult result(false, {});
   for (unsigned start = 0; start < string.length();) {
     if (string[start] == kNewlineCharacter) {
-      AppendForcedBreak(style, layout_object);
+      if (AppendForcedBreak(style, layout_object)) {
+        const size_t last_appended =
+            GetLastAppendedCharacterIndex(result.second, 0, start);
+        if (last_appended == kNotFound) {
+          result.first = true;
+        } else {
+          result.second.push_back(last_appended);
+          std::sort(result.second.begin(), result.second.end());
+        }
+      }
       start++;
       continue;
     }
@@ -232,21 +287,35 @@ void NGInlineItemsBuilder::AppendWithPreservingNewlines(
     size_t end = string.find(kNewlineCharacter, start + 1);
     if (end == kNotFound)
       end = string.length();
-    AppendWithWhiteSpaceCollapsing(string, start, end, style, layout_object);
+    AppendResult run_result = AppendWithWhiteSpaceCollapsing(
+        string, start, end, style, layout_object);
+    if (run_result.first) {
+      const size_t last_appended =
+          GetLastAppendedCharacterIndex(result.second, 0, start);
+      if (last_appended == kNotFound) {
+        result.first = true;
+      } else {
+        result.second.push_back(last_appended);
+        std::sort(result.second.begin(), result.second.end());
+      }
+    }
+    result.second.AppendVector(run_result.second);
     start = end;
   }
+  return result;
 }
 
-void NGInlineItemsBuilder::AppendForcedBreak(const ComputedStyle* style,
+bool NGInlineItemsBuilder::AppendForcedBreak(const ComputedStyle* style,
                                              LayoutObject* layout_object) {
   // Remove collapsible spaces immediately before a preserved newline.
   unsigned start_offset = text_.length();
-  RemoveTrailingCollapsibleSpaceIfExists(&start_offset);
+  bool result = RemoveTrailingCollapsibleSpaceIfExists(&start_offset);
 
   Append(NGInlineItem::kControl, kNewlineCharacter, style, layout_object);
 
   // Remove collapsible spaces immediately after a preserved newline.
   last_collapsible_space_ = CollapsibleSpace::kSpace;
+  return result;
 }
 
 void NGInlineItemsBuilder::Append(NGInlineItem::NGInlineItemType type,
@@ -269,7 +338,7 @@ void NGInlineItemsBuilder::Append(NGInlineItem::NGInlineItemType type,
   AppendItem(items_, type, end_offset, end_offset, style, layout_object);
 }
 
-void NGInlineItemsBuilder::RemoveTrailingCollapsibleNewlineIfNeeded(
+bool NGInlineItemsBuilder::RemoveTrailingCollapsibleNewlineIfNeeded(
     unsigned* next_start_offset,
     const String& after,
     unsigned after_index,
@@ -277,7 +346,7 @@ void NGInlineItemsBuilder::RemoveTrailingCollapsibleNewlineIfNeeded(
   DCHECK_EQ(last_collapsible_space_, CollapsibleSpace::kNewline);
 
   if (text_.IsEmpty() || text_[text_.length() - 1] != kSpaceCharacter)
-    return;
+    return false;
 
   const ComputedStyle* before_style = after_style;
   if (!items_->IsEmpty()) {
@@ -286,15 +355,20 @@ void NGInlineItemsBuilder::RemoveTrailingCollapsibleNewlineIfNeeded(
       before_style = item.Style();
   }
 
-  if (ShouldRemoveNewline(text_, before_style, after, after_index, after_style))
-    RemoveTrailingCollapsibleSpace(next_start_offset);
+  if (!ShouldRemoveNewline(text_, before_style, after, after_index,
+                           after_style))
+    return false;
+  RemoveTrailingCollapsibleSpace(next_start_offset);
+  return true;
 }
 
-void NGInlineItemsBuilder::RemoveTrailingCollapsibleSpaceIfExists(
+bool NGInlineItemsBuilder::RemoveTrailingCollapsibleSpaceIfExists(
     unsigned* next_start_offset) {
-  if (last_collapsible_space_ != CollapsibleSpace::kNone && !text_.IsEmpty() &&
-      text_[text_.length() - 1] == kSpaceCharacter)
-    RemoveTrailingCollapsibleSpace(next_start_offset);
+  if (last_collapsible_space_ == CollapsibleSpace::kNone || text_.IsEmpty() ||
+      text_[text_.length() - 1] != kSpaceCharacter)
+    return false;
+  RemoveTrailingCollapsibleSpace(next_start_offset);
+  return true;
 }
 
 void NGInlineItemsBuilder::RemoveTrailingCollapsibleSpace(