OLD | NEW |
1 // Copyright 2017 The Chromium Authors. All rights reserved. | 1 // Copyright 2017 The Chromium Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "core/editing/markers/DocumentMarkerListEditor.h" | 5 #include "core/editing/markers/DocumentMarkerListEditor.h" |
6 | 6 |
7 #include "core/editing/markers/SpellCheckMarkerListImpl.h" | 7 #include "core/editing/markers/SpellCheckMarkerListImpl.h" |
8 | 8 |
9 namespace blink { | 9 namespace blink { |
10 | 10 |
(...skipping 54 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
65 MarkerList::iterator end_pos = std::lower_bound( | 65 MarkerList::iterator end_pos = std::lower_bound( |
66 list->begin(), list->end(), end_offset, | 66 list->begin(), list->end(), end_offset, |
67 [](const Member<DocumentMarker>& marker, size_t end_offset) { | 67 [](const Member<DocumentMarker>& marker, size_t end_offset) { |
68 return marker->StartOffset() < end_offset; | 68 return marker->StartOffset() < end_offset; |
69 }); | 69 }); |
70 | 70 |
71 list->erase(start_pos - list->begin(), end_pos - start_pos); | 71 list->erase(start_pos - list->begin(), end_pos - start_pos); |
72 return start_pos != end_pos; | 72 return start_pos != end_pos; |
73 } | 73 } |
74 | 74 |
75 // TODO(rlanday): make this not take O(n^2) time when all the markers are | |
76 // removed | |
77 bool DocumentMarkerListEditor::ShiftMarkersContentDependent( | 75 bool DocumentMarkerListEditor::ShiftMarkersContentDependent( |
78 MarkerList* list, | 76 MarkerList* list, |
79 unsigned offset, | 77 unsigned offset, |
80 unsigned old_length, | 78 unsigned old_length, |
81 unsigned new_length) { | 79 unsigned new_length) { |
| 80 // Find first marker that ends after the start of the region being edited. |
| 81 // Markers before this one can be left untouched. This saves us some time over |
| 82 // scanning the entire list linearly if the edit region is near the end of the |
| 83 // text node. |
| 84 const MarkerList::iterator& shift_range_begin = |
| 85 std::upper_bound(list->begin(), list->end(), offset, |
| 86 [](size_t offset, const Member<DocumentMarker>& marker) { |
| 87 return offset < marker->EndOffset(); |
| 88 }); |
| 89 |
| 90 MarkerList::iterator erase_range_end = shift_range_begin; |
| 91 |
82 bool did_shift_marker = false; | 92 bool did_shift_marker = false; |
83 for (MarkerList::iterator it = list->begin(); it != list->end(); ++it) { | 93 for (MarkerList::iterator it = shift_range_begin; it != list->end(); ++it) { |
84 DocumentMarker& marker = **it; | 94 DocumentMarker& marker = **it; |
85 | 95 |
86 // marked text is neither changed nor shifted | |
87 if (marker.EndOffset() <= offset) | |
88 continue; | |
89 | |
90 // marked text is (potentially) changed by edit, remove marker | 96 // marked text is (potentially) changed by edit, remove marker |
91 if (marker.StartOffset() < offset + old_length) { | 97 if (marker.StartOffset() < offset + old_length) { |
92 list->erase(it - list->begin()); | 98 erase_range_end = std::next(it); |
93 --it; | |
94 did_shift_marker = true; | 99 did_shift_marker = true; |
95 continue; | 100 continue; |
96 } | 101 } |
97 | 102 |
98 // marked text is shifted but not changed | 103 // marked text is shifted but not changed |
99 marker.ShiftOffsets(new_length - old_length); | 104 marker.ShiftOffsets(new_length - old_length); |
100 did_shift_marker = true; | 105 did_shift_marker = true; |
101 } | 106 } |
102 | 107 |
| 108 // Note: shift_range_begin could point at a marker being shifted instead of |
| 109 // deleted, but if this is the case, we don't need to delete any markers, and |
| 110 // erase() will get 0 for the length param |
| 111 list->erase(shift_range_begin - list->begin(), |
| 112 erase_range_end - shift_range_begin); |
103 return did_shift_marker; | 113 return did_shift_marker; |
104 } | 114 } |
105 | 115 |
106 // TODO(rlanday): make this not take O(n^2) time when all the markers are | |
107 // removed | |
108 bool DocumentMarkerListEditor::ShiftMarkersContentIndependent( | 116 bool DocumentMarkerListEditor::ShiftMarkersContentIndependent( |
109 MarkerList* list, | 117 MarkerList* list, |
110 unsigned offset, | 118 unsigned offset, |
111 unsigned old_length, | 119 unsigned old_length, |
112 unsigned new_length) { | 120 unsigned new_length) { |
| 121 // Find first marker that ends after the start of the region being edited. |
| 122 // Markers before this one can be left untouched. This saves us some time over |
| 123 // scanning the entire list linearly if the edit region is near the end of the |
| 124 // text node. |
| 125 const MarkerList::iterator& shift_range_begin = |
| 126 std::upper_bound(list->begin(), list->end(), offset, |
| 127 [](size_t offset, const Member<DocumentMarker>& marker) { |
| 128 return offset < marker->EndOffset(); |
| 129 }); |
| 130 |
| 131 MarkerList::iterator erase_range_begin = list->end(); |
| 132 MarkerList::iterator erase_range_end = list->end(); |
| 133 |
113 bool did_shift_marker = false; | 134 bool did_shift_marker = false; |
114 for (MarkerList::iterator it = list->begin(); it != list->end(); ++it) { | 135 for (MarkerList::iterator it = shift_range_begin; it != list->end(); ++it) { |
115 DocumentMarker& marker = **it; | 136 DocumentMarker& marker = **it; |
116 Optional<DocumentMarker::MarkerOffsets> result = | 137 Optional<DocumentMarker::MarkerOffsets> result = |
117 marker.ComputeOffsetsAfterShift(offset, old_length, new_length); | 138 marker.ComputeOffsetsAfterShift(offset, old_length, new_length); |
118 if (result == WTF::nullopt) { | 139 if (result == WTF::nullopt) { |
119 list->erase(it - list->begin()); | 140 if (erase_range_begin == list->end()) |
120 --it; | 141 erase_range_begin = it; |
| 142 erase_range_end = std::next(it); |
121 did_shift_marker = true; | 143 did_shift_marker = true; |
122 continue; | 144 continue; |
123 } | 145 } |
124 | 146 |
125 if (marker.StartOffset() != result.value().start_offset || | 147 if (marker.StartOffset() != result.value().start_offset || |
126 marker.EndOffset() != result.value().end_offset) { | 148 marker.EndOffset() != result.value().end_offset) { |
127 did_shift_marker = true; | 149 did_shift_marker = true; |
128 marker.SetStartOffset(result.value().start_offset); | 150 marker.SetStartOffset(result.value().start_offset); |
129 marker.SetEndOffset(result.value().end_offset); | 151 marker.SetEndOffset(result.value().end_offset); |
130 } | 152 } |
131 } | 153 } |
132 | 154 |
| 155 list->erase(erase_range_begin - list->begin(), |
| 156 erase_range_end - erase_range_begin); |
133 return did_shift_marker; | 157 return did_shift_marker; |
134 } | 158 } |
135 | 159 |
136 } // namespace blink | 160 } // namespace blink |
OLD | NEW |