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..f10990f6830b22aba52a457c0fd26f8b6017a2e7 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
@@ -22,7 +22,9 @@ 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);
+  RemoveTrailingCollapsibleSpaceIfExists(
+      &next_start_offset,
+      input_strings_lengths_.size() ? input_strings_lengths_.back() : 0);
 
   return text_.ToString();
 }
@@ -124,9 +126,33 @@ 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 (collapsed_indexes_) {
+    input_strings_lengths_.push_back(string.length());
+    collapsed_indexes_->emplace_back();
+  }
+
   if (string.IsEmpty())
     return;
   text_.ReserveCapacity(string.length());
@@ -153,12 +179,14 @@ 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);
+        AppendForcedBreak(style, layout_object, i);
         return;
       }
 
       if (last_collapsible_space_ == CollapsibleSpace::kNone)
         text_.Append(kSpaceCharacter);
+      else if (collapsed_indexes_)
+        collapsed_indexes_->back().push_back(i);
       last_collapsible_space_ = CollapsibleSpace::kNewline;
       i++;
       continue;
@@ -168,6 +196,8 @@ void NGInlineItemsBuilder::AppendWithWhiteSpaceCollapsing(
       if (last_collapsible_space_ == CollapsibleSpace::kNone) {
         text_.Append(kSpaceCharacter);
         last_collapsible_space_ = CollapsibleSpace::kSpace;
+      } else if (collapsed_indexes_) {
+        collapsed_indexes_->back().push_back(i);
       }
       i++;
       continue;
@@ -224,7 +254,7 @@ void NGInlineItemsBuilder::AppendWithPreservingNewlines(
     LayoutObject* layout_object) {
   for (unsigned start = 0; start < string.length();) {
     if (string[start] == kNewlineCharacter) {
-      AppendForcedBreak(style, layout_object);
+      AppendForcedBreak(style, layout_object, start);
       start++;
       continue;
     }
@@ -238,10 +268,11 @@ void NGInlineItemsBuilder::AppendWithPreservingNewlines(
 }
 
 void NGInlineItemsBuilder::AppendForcedBreak(const ComputedStyle* style,
-                                             LayoutObject* layout_object) {
+                                             LayoutObject* layout_object,
+                                             unsigned index) {
   // Remove collapsible spaces immediately before a preserved newline.
   unsigned start_offset = text_.length();
-  RemoveTrailingCollapsibleSpaceIfExists(&start_offset);
+  RemoveTrailingCollapsibleSpaceIfExists(&start_offset, index);
 
   Append(NGInlineItem::kControl, kNewlineCharacter, style, layout_object);
 
@@ -287,18 +318,20 @@ void NGInlineItemsBuilder::RemoveTrailingCollapsibleNewlineIfNeeded(
   }
 
   if (ShouldRemoveNewline(text_, before_style, after, after_index, after_style))
-    RemoveTrailingCollapsibleSpace(next_start_offset);
+    RemoveTrailingCollapsibleSpace(next_start_offset, after_index);
 }
 
 void NGInlineItemsBuilder::RemoveTrailingCollapsibleSpaceIfExists(
-    unsigned* next_start_offset) {
+    unsigned* next_start_offset,
+    unsigned after_index) {
   if (last_collapsible_space_ != CollapsibleSpace::kNone && !text_.IsEmpty() &&
       text_[text_.length() - 1] == kSpaceCharacter)
-    RemoveTrailingCollapsibleSpace(next_start_offset);
+    RemoveTrailingCollapsibleSpace(next_start_offset, after_index);
 }
 
 void NGInlineItemsBuilder::RemoveTrailingCollapsibleSpace(
-    unsigned* next_start_offset) {
+    unsigned* next_start_offset,
+    unsigned after_index) {
   DCHECK_NE(last_collapsible_space_, CollapsibleSpace::kNone);
   DCHECK(!text_.IsEmpty());
   DCHECK_EQ(text_[text_.length() - 1], kSpaceCharacter);
@@ -307,6 +340,9 @@ void NGInlineItemsBuilder::RemoveTrailingCollapsibleSpace(
   text_.Resize(new_size);
   last_collapsible_space_ = CollapsibleSpace::kNone;
 
+  if (collapsed_indexes_)
+    AddLastTrailingSpaceToRemovedIndexes(after_index);
+
   if (*next_start_offset <= new_size)
     return;
   *next_start_offset = new_size;
@@ -333,6 +369,28 @@ void NGInlineItemsBuilder::RemoveTrailingCollapsibleSpace(
   }
 }
 
+void NGInlineItemsBuilder::AddLastTrailingSpaceToRemovedIndexes(

[yosin_UTC9, 2017/06/20 05:39:09]

nit: %s/RemovedIndexes/CollapsedIndexes/

[kojii, 2017/06/21 09:47:13]

This may depend on above, but I can't understand what this function is doing.
Can you explain?

[Xiaocheng, 2017/06/21 18:15:06]

This function is called when RemoveTrailingCollapsibleSpace() removes a trailing
space that was previously appended.

It finds the index of this space in its string, which may or may not be the
current string being appended, and adds it to |collapsed_indexes_|.

+    unsigned last_string_appended_length) {
+  DCHECK(collapsed_indexes_);
+  DCHECK_EQ(collapsed_indexes_->size(), input_strings_lengths_.size());
+  for (unsigned i = collapsed_indexes_->size(); i;) {
+    Vector<unsigned>& indexes = (*collapsed_indexes_)[--i];
+    size_t last_unremoved =
+        GetLargestAbsentInteger(indexes, (i + 1) == collapsed_indexes_->size()
+                                             ? last_string_appended_length
+                                             : 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) {