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) {