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..d61edeb8595624e7d437d622c16bee2e246a5391 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
@@ -10,6 +10,15 @@
 
 namespace blink {
 
+NGInlineItemsBuilder::NGInlineItemsBuilder(
+    Vector<NGInlineItem>* items,
+    Vector<Vector<unsigned>>* removed_indexes)
+    : items_(items),
+      removed_indexes_(removed_indexes),
+      input_strings_lengths_(Vector<unsigned>()) {
+  DCHECK(removed_indexes);
+}
+
 NGInlineItemsBuilder::~NGInlineItemsBuilder() {
   DCHECK_EQ(0u, exits_.size());
   DCHECK_EQ(text_.length(), items_->IsEmpty() ? 0 : items_->back().EndOffset());
@@ -22,7 +31,12 @@ String NGInlineItemsBuilder::ToString() {
   // [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);
+  bool trailing_space_removed =
+      RemoveTrailingCollapsibleSpaceIfExists(&next_start_offset);
+  if (trailing_space_removed && removed_indexes_) {
+    DCHECK(input_strings_lengths_);
+    AddLastTrailingSpaceToRemovedIndexes(input_strings_lengths_->back());
+  }
 
   return text_.ToString();
 }
@@ -124,9 +138,34 @@ static inline bool IsControlItemCharacter(UChar c) {
   return c == kTabulationCharacter || c == kNewlineCharacter;
 }
 
+// Returns the largest integer in [0, |max|) that is absent in |integers|, or
+// kNotFound if such an integer does not exist.
+static size_t GetLargestAbsentInteger(const Vector<unsigned>& integers,
+                                      unsigned max) {
+  DCHECK(integers.IsEmpty() || integers.back() < max);
+  if (!max || integers.size() == max)
+    return kNotFound;
+  if (integers.IsEmpty() || integers.back() + 1 < max)
+    return max - 1;
+  for (unsigned i = integers.size() - 1; i;) {
+    DCHECK_LT(integers[i - 1], integers[i]);
+    if (integers[i - 1] + 1 < integers[i] - 1)
+      return integers[i] - 1;
+    --i;
+  }
+  DCHECK_GT(integers[0], 0u);
+  return integers[0] - 1;
+}
+
 void NGInlineItemsBuilder::Append(const String& string,
                                   const ComputedStyle* style,
                                   LayoutObject* layout_object) {
+  if (removed_indexes_) {
+    DCHECK(input_strings_lengths_);
+    input_strings_lengths_->push_back(string.length());
+    removed_indexes_->emplace_back();
+  }
+
   if (string.IsEmpty())
     return;
   text_.ReserveCapacity(string.length());
@@ -153,12 +192,16 @@ void NGInlineItemsBuilder::AppendWithWhiteSpaceCollapsing(
     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);
+        bool trailing_space_removed = AppendForcedBreak(style, layout_object);
+        if (trailing_space_removed && removed_indexes_)
+          AddLastTrailingSpaceToRemovedIndexes(i);

[kojii, 2017/06/19 05:56:33]

Why don't we add to removed_indexes in RemoveTrailingCollapsibleSpaceIfExists()
but let it return the result and do here?

[Xiaocheng, 2017/06/19 17:53:01]

Updating |removed_indexes_| needs the number of characters in the current string
that have been processed (i.e., |i|).

Let me try passing in this parameter instead, and hope that the performance
impact is negligible.

         return;
       }
 
       if (last_collapsible_space_ == CollapsibleSpace::kNone)
         text_.Append(kSpaceCharacter);
+      else if (removed_indexes_)
+        removed_indexes_->back().push_back(i);
       last_collapsible_space_ = CollapsibleSpace::kNewline;
       i++;
       continue;
@@ -168,13 +211,18 @@ void NGInlineItemsBuilder::AppendWithWhiteSpaceCollapsing(
       if (last_collapsible_space_ == CollapsibleSpace::kNone) {
         text_.Append(kSpaceCharacter);
         last_collapsible_space_ = CollapsibleSpace::kSpace;
+      } else if (removed_indexes_) {
+        removed_indexes_->back().push_back(i);
       }
       i++;
       continue;
     }
 
     if (last_collapsible_space_ == CollapsibleSpace::kNewline) {
-      RemoveTrailingCollapsibleNewlineIfNeeded(&start_offset, string, i, style);
+      bool trailing_newline_removed = RemoveTrailingCollapsibleNewlineIfNeeded(
+          &start_offset, string, i, style);
+      if (trailing_newline_removed && removed_indexes_)
+        AddLastTrailingSpaceToRemovedIndexes(i);
     }
 
     size_t end_of_non_space = string.Find(IsCollapsibleSpace, i + 1);
@@ -224,7 +272,9 @@ void NGInlineItemsBuilder::AppendWithPreservingNewlines(
     LayoutObject* layout_object) {
   for (unsigned start = 0; start < string.length();) {
     if (string[start] == kNewlineCharacter) {
-      AppendForcedBreak(style, layout_object);
+      bool trailing_space_removed = AppendForcedBreak(style, layout_object);
+      if (trailing_space_removed && removed_indexes_)
+        AddLastTrailingSpaceToRemovedIndexes(start);
       start++;
       continue;
     }
@@ -237,16 +287,18 @@ void NGInlineItemsBuilder::AppendWithPreservingNewlines(
   }
 }
 
-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 trailing_space_removed =
+      RemoveTrailingCollapsibleSpaceIfExists(&start_offset);
 
   Append(NGInlineItem::kControl, kNewlineCharacter, style, layout_object);
 
   // Remove collapsible spaces immediately after a preserved newline.
   last_collapsible_space_ = CollapsibleSpace::kSpace;
+  return trailing_space_removed;
 }
 
 void NGInlineItemsBuilder::Append(NGInlineItem::NGInlineItemType type,
@@ -269,7 +321,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 +329,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 +338,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(
@@ -333,6 +390,29 @@ void NGInlineItemsBuilder::RemoveTrailingCollapsibleSpace(
   }
 }
 
+void NGInlineItemsBuilder::AddLastTrailingSpaceToRemovedIndexes(
+    unsigned last_string_end) {
+  DCHECK(removed_indexes_);
+  DCHECK(input_strings_lengths_);
+  DCHECK_EQ(removed_indexes_->size(), input_strings_lengths_->size());
+  for (unsigned i = removed_indexes_->size(); i;) {
+    Vector<unsigned>& indexes = (*removed_indexes_)[--i];
+    size_t last_unremoved =
+        GetLargestAbsentInteger(indexes, (i + 1) == removed_indexes_->size()
+                                             ? last_string_end
+                                             : (*input_strings_lengths_)[i]);
+    if (last_unremoved == kNotFound)
+      continue;
+
+    indexes.insert(
+        std::lower_bound(indexes.begin(), indexes.end(), last_unremoved) -
+            indexes.begin(),
+        last_unremoved);
+    return;
+  }
+  NOTREACHED();
+}
+
 void NGInlineItemsBuilder::AppendBidiControl(const ComputedStyle* style,
                                              UChar ltr,
                                              UChar rtl) {