| // Copyright 2017 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/editing/markers/DocumentMarkerListEditor.h" |
| |
| #include "core/editing/markers/SpellCheckMarkerListImpl.h" |
| |
| namespace blink { |
| |
| void DocumentMarkerListEditor::AddMarkerWithoutMergingOverlapping( |
| MarkerList* list, |
| DocumentMarker* marker) { |
| if (list->IsEmpty() || list->back()->EndOffset() <= marker->StartOffset()) { |
| list->push_back(marker); |
| return; |
| } |
| |
| const auto pos = std::lower_bound( |
| list->begin(), list->end(), marker, |
| [](const Member<DocumentMarker>& marker_in_list, |
| const DocumentMarker* marker_to_insert) { |
| return marker_in_list->StartOffset() < marker_to_insert->StartOffset(); |
| }); |
| |
| // DCHECK that we're not trying to add a marker that overlaps an existing one |
| // (this method only works for lists which don't allow overlapping markers) |
| if (pos != list->end()) |
| DCHECK_LE(marker->EndOffset(), (*pos)->StartOffset()); |
| |
| if (pos != list->begin()) |
| DCHECK_GE(marker->StartOffset(), (*std::prev(pos))->EndOffset()); |
| |
| list->insert(pos - list->begin(), marker); |
| } |
| |
| bool DocumentMarkerListEditor::MoveMarkers(MarkerList* src_list, |
| int length, |
| DocumentMarkerList* dst_list) { |
| DCHECK_GT(length, 0); |
| bool didMoveMarker = false; |
| unsigned end_offset = length - 1; |
| |
| MarkerList::iterator it; |
| for (it = src_list->begin(); it != src_list->end(); ++it) { |
| DocumentMarker& marker = **it; |
| if (marker.StartOffset() > end_offset) |
| break; |
| |
| // Trim the marker to fit in dst_list's text node |
| if (marker.EndOffset() > end_offset) |
| marker.SetEndOffset(end_offset); |
| |
| dst_list->Add(&marker); |
| didMoveMarker = true; |
| } |
| |
| // Remove the range of markers that were moved to dstNode |
| src_list->erase(0, it - src_list->begin()); |
| |
| return didMoveMarker; |
| } |
| |
| bool DocumentMarkerListEditor::RemoveMarkers(MarkerList* list, |
| unsigned start_offset, |
| int length) { |
| const unsigned end_offset = start_offset + length; |
| MarkerList::iterator start_pos = std::upper_bound( |
| list->begin(), list->end(), start_offset, |
| [](size_t start_offset, const Member<DocumentMarker>& marker) { |
| return start_offset < marker->EndOffset(); |
| }); |
| |
| MarkerList::iterator end_pos = std::lower_bound( |
| list->begin(), list->end(), end_offset, |
| [](const Member<DocumentMarker>& marker, size_t end_offset) { |
| return marker->StartOffset() < end_offset; |
| }); |
| |
| list->erase(start_pos - list->begin(), end_pos - start_pos); |
| return start_pos != end_pos; |
| } |
| |
| bool DocumentMarkerListEditor::ShiftMarkersContentDependent( |
| MarkerList* list, |
| unsigned offset, |
| unsigned old_length, |
| unsigned new_length) { |
| // Find first marker that ends after the start of the region being edited. |
| // Markers before this one can be left untouched. This saves us some time over |
| // scanning the entire list linearly if the edit region is near the end of the |
| // text node. |
| const MarkerList::iterator& shift_range_begin = |
| std::upper_bound(list->begin(), list->end(), offset, |
| [](size_t offset, const Member<DocumentMarker>& marker) { |
| return offset < marker->EndOffset(); |
| }); |
| |
| MarkerList::iterator erase_range_end = shift_range_begin; |
| |
| bool did_shift_marker = false; |
| for (MarkerList::iterator it = shift_range_begin; it != list->end(); ++it) { |
| DocumentMarker& marker = **it; |
| |
| // marked text is (potentially) changed by edit, remove marker |
| if (marker.StartOffset() < offset + old_length) { |
| erase_range_end = std::next(it); |
| did_shift_marker = true; |
| continue; |
| } |
| |
| // marked text is shifted but not changed |
| marker.ShiftOffsets(new_length - old_length); |
| did_shift_marker = true; |
| } |
| |
| // Note: shift_range_begin could point at a marker being shifted instead of |
| // deleted, but if this is the case, we don't need to delete any markers, and |
| // erase() will get 0 for the length param |
| list->erase(shift_range_begin - list->begin(), |
| erase_range_end - shift_range_begin); |
| return did_shift_marker; |
| } |
| |
| bool DocumentMarkerListEditor::ShiftMarkersContentIndependent( |
| MarkerList* list, |
| unsigned offset, |
| unsigned old_length, |
| unsigned new_length) { |
| // Find first marker that ends after the start of the region being edited. |
| // Markers before this one can be left untouched. This saves us some time over |
| // scanning the entire list linearly if the edit region is near the end of the |
| // text node. |
| const MarkerList::iterator& shift_range_begin = |
| std::upper_bound(list->begin(), list->end(), offset, |
| [](size_t offset, const Member<DocumentMarker>& marker) { |
| return offset < marker->EndOffset(); |
| }); |
| |
| MarkerList::iterator erase_range_begin = list->end(); |
| MarkerList::iterator erase_range_end = list->end(); |
| |
| bool did_shift_marker = false; |
| for (MarkerList::iterator it = shift_range_begin; it != list->end(); ++it) { |
| DocumentMarker& marker = **it; |
| Optional<DocumentMarker::MarkerOffsets> result = |
| marker.ComputeOffsetsAfterShift(offset, old_length, new_length); |
| if (result == WTF::nullopt) { |
| if (erase_range_begin == list->end()) |
| erase_range_begin = it; |
| erase_range_end = std::next(it); |
| did_shift_marker = true; |
| continue; |
| } |
| |
| if (marker.StartOffset() != result.value().start_offset || |
| marker.EndOffset() != result.value().end_offset) { |
| did_shift_marker = true; |
| marker.SetStartOffset(result.value().start_offset); |
| marker.SetEndOffset(result.value().end_offset); |
| } |
| } |
| |
| list->erase(erase_range_begin - list->begin(), |
| erase_range_end - erase_range_begin); |
| return did_shift_marker; |
| } |
| |
| DocumentMarker* DocumentMarkerListEditor::FirstMarkerIntersectingRange( |
| const MarkerList& list, |
| unsigned start_offset, |
| unsigned end_offset) { |
| DCHECK_LE(start_offset, end_offset); |
| |
| const auto& marker_it = |
| std::lower_bound(list.begin(), list.end(), start_offset, |
| [](const DocumentMarker* marker, unsigned start_offset) { |
| return marker->EndOffset() <= start_offset; |
| }); |
| if (marker_it == list.end()) |
| return nullptr; |
| |
| DocumentMarker* marker = *marker_it; |
| if (marker->StartOffset() >= end_offset) |
| return nullptr; |
| return marker; |
| } |
| |
| HeapVector<Member<DocumentMarker>> |
| DocumentMarkerListEditor::MarkersIntersectingRange(const MarkerList& list, |
| unsigned start_offset, |
| unsigned end_offset) { |
| DCHECK_LE(start_offset, end_offset); |
| |
| const auto& start_it = |
| std::lower_bound(list.begin(), list.end(), start_offset, |
| [](const DocumentMarker* marker, unsigned start_offset) { |
| return marker->EndOffset() <= start_offset; |
| }); |
| const auto& end_it = |
| std::upper_bound(list.begin(), list.end(), end_offset, |
| [](unsigned end_offset, const DocumentMarker* marker) { |
| return end_offset <= marker->StartOffset(); |
| }); |
| |
| HeapVector<Member<DocumentMarker>> results; |
| std::copy(start_it, end_it, std::back_inserter(results)); |
| return results; |
| } |
| |
| } // namespace blink |