Fix two issues of TextOffsetMap merge

- If two characters on an identical offset were removed, their two
  entries should be merged.
- If a character was expanded twice, their two entries should be merged.

Variables `length_diff_NN` are renamed to `offset_diff_NN` to
distinguish from `chunk_length_diff_NN`.

Bug: 1520775
Change-Id: Ic5d6ca32c9c9ff7c6528e0854aa6382a182be1ff
Reviewed-on: https://chromium-review.googlesource.com/c/chromium/src/+/5232351
Reviewed-by: Koji Ishii <kojii@chromium.org>
Auto-Submit: Kent Tamura <tkent@chromium.org>
Commit-Queue: Koji Ishii <kojii@chromium.org>
Cr-Commit-Position: refs/heads/main@{#1251883}
diff --git a/third_party/blink/renderer/platform/wtf/text/text_offset_map.cc b/third_party/blink/renderer/platform/wtf/text/text_offset_map.cc
index 65869df8..cf3081b 100644
--- a/third_party/blink/renderer/platform/wtf/text/text_offset_map.cc
+++ b/third_party/blink/renderer/platform/wtf/text/text_offset_map.cc
@@ -8,6 +8,28 @@
 
 namespace WTF {
 
+namespace {
+
+// Returns a negative value:
+//     The specified entry represents a removal of characters.
+// Returns a positive value:
+//     The specified entry represents an addition of characters.
+// Returns zero:
+//     The specified entry is redundant.
+int ChunkLengthDifference(const Vector<TextOffsetMap::Entry>& entries,
+                          wtf_size_t index) {
+  wtf_size_t previous_source = 0;
+  wtf_size_t previous_target = 0;
+  if (index > 0) {
+    previous_source = entries[index - 1].source;
+    previous_target = entries[index - 1].target;
+  }
+  const TextOffsetMap::Entry& entry = entries[index];
+  return (entry.target - previous_target) - (entry.source - previous_source);
+}
+
+}  // namespace
+
 std::ostream& operator<<(std::ostream& stream,
                          const TextOffsetMap::Entry& entry) {
   return stream << "{" << entry.source << ", " << entry.target << "}";
@@ -39,33 +61,48 @@
   const wtf_size_t size12 = map12.entries_.size();
   const wtf_size_t size23 = map23.entries_.size();
   wtf_size_t index12 = 0, index23 = 0;
-  int length_diff_12 = 0, length_diff_23 = 0;
+  int offset_diff_12 = 0, offset_diff_23 = 0;
   while (index12 < size12 && index23 < size23) {
     const Entry& entry12 = map12.entries_[index12];
     const Entry& entry23 = map23.entries_[index23];
-    if (entry12.target < entry23.source) {
-      Append(entry12.source, entry12.target + length_diff_23);
-      length_diff_12 = entry12.target - entry12.source;
+    int chunk_length_diff_12 = ChunkLengthDifference(map12.entries_, index12);
+    int chunk_length_diff_23 = ChunkLengthDifference(map23.entries_, index23);
+    if (chunk_length_diff_12 < 0 && chunk_length_diff_23 < 0 &&
+        entry12.target + offset_diff_23 == entry23.target) {
+      // No need to handle entry12 because it was overwritten by entry23.
+      offset_diff_12 = entry12.target - entry12.source;
+      ++index12;
+    } else if (chunk_length_diff_12 > 0 && chunk_length_diff_23 > 0 &&
+               entry12.source == entry23.source - offset_diff_12) {
+      offset_diff_12 = entry12.target - entry12.source;
+      offset_diff_23 = entry23.target - entry23.source;
+      Append(entry12.source, entry23.target + chunk_length_diff_12);
+      ++index12;
+      ++index23;
+
+    } else if (entry12.target < entry23.source) {
+      Append(entry12.source, entry12.target + offset_diff_23);
+      offset_diff_12 = entry12.target - entry12.source;
       ++index12;
     } else if (entry12.target == entry23.source) {
       Append(entry12.source, entry23.target);
-      length_diff_12 = entry12.target - entry12.source;
-      length_diff_23 = entry23.target - entry23.source;
+      offset_diff_12 = entry12.target - entry12.source;
+      offset_diff_23 = entry23.target - entry23.source;
       ++index12;
       ++index23;
     } else {
-      Append(entry23.source - length_diff_12, entry23.target);
-      length_diff_23 = entry23.target - entry23.source;
+      Append(entry23.source - offset_diff_12, entry23.target);
+      offset_diff_23 = entry23.target - entry23.source;
       ++index23;
     }
   }
   for (; index12 < size12; ++index12) {
     const Entry& entry12 = map12.entries_[index12];
-    Append(entry12.source, entry12.target + length_diff_23);
+    Append(entry12.source, entry12.target + offset_diff_23);
   }
   for (; index23 < size23; ++index23) {
     const Entry& entry23 = map23.entries_[index23];
-    Append(entry23.source - length_diff_12, entry23.target);
+    Append(entry23.source - offset_diff_12, entry23.target);
   }
 }
 
diff --git a/third_party/blink/renderer/platform/wtf/text/text_offset_map_test.cc b/third_party/blink/renderer/platform/wtf/text/text_offset_map_test.cc
index 8516f5e2..4ee557f 100644
--- a/third_party/blink/renderer/platform/wtf/text/text_offset_map_test.cc
+++ b/third_party/blink/renderer/platform/wtf/text/text_offset_map_test.cc
@@ -29,6 +29,12 @@
       {{{1, 2}, {2, 4}, {4, 7}}, {{5, 6}}, {{1, 2}, {2, 4}, {3, 6}, {4, 8}}},
       // "abcde" -> "abde" -> "aabdde"
       {{{3, 2}}, {{1, 2}, {3, 5}}, {{1, 2}, {3, 3}, {4, 5}}},
+
+      // crbug.com/1520775
+      // "ABabCDcdE" -> "ABbCDdE" -> "ABCDE"
+      {{{3, 2}, {7, 5}}, {{3, 2}, {6, 4}}, {{4, 2}, {8, 4}}},
+      // "ABC" -> "AaBCc" -> "AbaBCdc"
+      {{{1, 2}, {3, 5}}, {{1, 2}, {4, 6}}, {{1, 3}, {3, 7}}},
   };
 
   for (const auto& data : kTestData) {