Make NGInlineItemsBuilder construct whitespace-collapsed offset mapping

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

 // Copyright 2016 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 "core/layout/ng/inline/ng_inline_items_builder.h"
 
 #include "core/layout/LayoutObject.h"
 #include "core/layout/ng/inline/ng_inline_node.h"
 #include "core/style/ComputedStyle.h"
 
 namespace blink {
 
 NGInlineItemsBuilder::~NGInlineItemsBuilder() {
   DCHECK_EQ(0u, exits_.size());
   DCHECK_EQ(text_.length(), items_->IsEmpty() ? 0 : items_->back().EndOffset());
 }
 
 String NGInlineItemsBuilder::ToString() {
   // 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);
+  RemoveTrailingCollapsibleSpaceIfExists(
+      &next_start_offset,
+      input_strings_lengths_.size() ? input_strings_lengths_.back() : 0);
 
   return text_.ToString();
 }
 
 // Determine "Ambiguous" East Asian Width is Wide or Narrow.
 // Unicode East Asian Width
 // http://unicode.org/reports/tr11/
 static bool IsAmbiguosEastAsianWidthWide(const ComputedStyle* style) {
   UScriptCode script = style->GetFontDescription().GetScript();
   return script == USCRIPT_KATAKANA_OR_HIRAGANA ||
@@ skipping 81 matching lines @@
   return c == kSpaceCharacter || c == kTabulationCharacter ||
          c == kNewlineCharacter;
 }
 
 // Characters needing a separate control item than other text items.
 // It makes the line breaker easier to handle.
 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());
 
   EWhiteSpace whitespace = style->WhiteSpace();
   if (!ComputedStyle::CollapseWhiteSpace(whitespace))
     return AppendWithoutWhiteSpaceCollapsing(string, style, layout_object);
   if (ComputedStyle::PreserveNewline(whitespace) && !is_svgtext_)
     return AppendWithPreservingNewlines(string, style, layout_object);
 
   AppendWithWhiteSpaceCollapsing(string, 0, string.length(), style,
                                  layout_object);
 }
 
 void NGInlineItemsBuilder::AppendWithWhiteSpaceCollapsing(
     const String& string,
     unsigned start,
     unsigned end,
     const ComputedStyle* style,
     LayoutObject* layout_object) {
   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);
+        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;
     }
 
     if (c == kSpaceCharacter || c == kTabulationCharacter) {
       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;
     }
 
     if (last_collapsible_space_ == CollapsibleSpace::kNewline) {
       RemoveTrailingCollapsibleNewlineIfNeeded(&start_offset, string, i, style);
     }
 
     size_t end_of_non_space = string.Find(IsCollapsibleSpace, i + 1);
@@ skipping 36 matching lines @@
 
   last_collapsible_space_ = CollapsibleSpace::kNone;
 }
 
 void NGInlineItemsBuilder::AppendWithPreservingNewlines(
     const String& string,
     const ComputedStyle* style,
     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;
     }
 
     size_t end = string.find(kNewlineCharacter, start + 1);
     if (end == kNotFound)
       end = string.length();
     AppendWithWhiteSpaceCollapsing(string, start, end, style, layout_object);
     start = end;
   }
 }
 
 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);
 
   // Remove collapsible spaces immediately after a preserved newline.
   last_collapsible_space_ = CollapsibleSpace::kSpace;
 }
 
 void NGInlineItemsBuilder::Append(NGInlineItem::NGInlineItemType type,
                                   UChar character,
                                   const ComputedStyle* style,
@@ skipping 25 matching lines @@
     return;
 
   const ComputedStyle* before_style = after_style;
   if (!items_->IsEmpty()) {
     NGInlineItem& item = items_->back();
     if (text_.length() < item.EndOffset() + 2)
       before_style = item.Style();
   }
 
   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);
 
   unsigned new_size = text_.length() - 1;
   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;
 
   // Adjust the last item if the removed space is already appended.
   for (unsigned i = items_->size(); i > 0;) {
     NGInlineItem& item = (*items_)[--i];
     DCHECK_EQ(item.EndOffset(), new_size + 1);
     if (item.Type() == NGInlineItem::kText) {
       DCHECK_GE(item.Length(), 1u);
       if (item.Length() > 1)
         item.SetEndOffset(new_size);
       else
         items_->erase(i);
       break;
     }
     if (!item.Length()) {
       // Trailing spaces can be removed across non-character items.
       item.SetOffset(new_size, new_size);
       continue;
     }
     NOTREACHED();
     break;
   }
 }
 
+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) {
   Append(NGInlineItem::kBidiControl,
          style->Direction() == TextDirection::kRtl ? rtl : ltr);
 }
 
 void NGInlineItemsBuilder::EnterBlock(const ComputedStyle* style) {
   // Handle bidi-override on the block itself.
   switch (style->GetUnicodeBidi()) {
@@ skipping 76 matching lines @@
 }
 
 void NGInlineItemsBuilder::Exit(LayoutObject* node) {
   while (!exits_.IsEmpty() && exits_.back().node == node) {
     Append(NGInlineItem::kBidiControl, exits_.back().character);
     exits_.pop_back();
   }
 }
 
 }  // namespace blink