Use "= default" to denote default constructor or destructor
[WebKit-https.git] / Source / WebCore / dom / DocumentMarkerController.cpp
1 /*
2  * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
3  *           (C) 1999 Antti Koivisto (koivisto@kde.org)
4  *           (C) 2001 Dirk Mueller (mueller@kde.org)
5  *           (C) 2006 Alexey Proskuryakov (ap@webkit.org)
6  * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010 Apple Inc. All rights reserved.
7  * Copyright (C) 2008, 2009 Torch Mobile Inc. All rights reserved. (http://www.torchmobile.com/)
8  * Copyright (C) Research In Motion Limited 2010. All rights reserved.
9  *
10  * This library is free software; you can redistribute it and/or
11  * modify it under the terms of the GNU Library General Public
12  * License as published by the Free Software Foundation; either
13  * version 2 of the License, or (at your option) any later version.
14  *
15  * This library is distributed in the hope that it will be useful,
16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
18  * Library General Public License for more details.
19  *
20  * You should have received a copy of the GNU Library General Public License
21  * along with this library; see the file COPYING.LIB.  If not, write to
22  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
23  * Boston, MA 02110-1301, USA.
24  *
25  */
26
27 #include "config.h"
28 #include "DocumentMarkerController.h"
29
30 #include "Chrome.h"
31 #include "ChromeClient.h"
32 #include "MainFrame.h"
33 #include "NodeTraversal.h"
34 #include "Page.h"
35 #include "Range.h"
36 #include "RenderBlockFlow.h"
37 #include "RenderLayer.h"
38 #include "RenderText.h"
39 #include "RenderedDocumentMarker.h"
40 #include "TextIterator.h"
41 #include <stdio.h>
42
43 namespace WebCore {
44
45 inline bool DocumentMarkerController::possiblyHasMarkers(OptionSet<DocumentMarker::MarkerType> types)
46 {
47     return m_possiblyExistingMarkerTypes.contains(types);
48 }
49
50 DocumentMarkerController::DocumentMarkerController(Document& document)
51     : m_document(document)
52 {
53 }
54
55 DocumentMarkerController::~DocumentMarkerController() = default;
56
57 void DocumentMarkerController::detach()
58 {
59     m_markers.clear();
60     m_possiblyExistingMarkerTypes = { };
61 }
62
63 void DocumentMarkerController::addMarker(Range* range, DocumentMarker::MarkerType type, const String& description)
64 {
65     for (TextIterator markedText(range); !markedText.atEnd(); markedText.advance()) {
66         RefPtr<Range> textPiece = markedText.range();
67         addMarker(&textPiece->startContainer(), DocumentMarker(type, textPiece->startOffset(), textPiece->endOffset(), description));
68     }
69 }
70
71 void DocumentMarkerController::addMarker(Range* range, DocumentMarker::MarkerType type)
72 {
73     for (TextIterator markedText(range); !markedText.atEnd(); markedText.advance()) {
74         RefPtr<Range> textPiece = markedText.range();
75         addMarker(&textPiece->startContainer(), DocumentMarker(type, textPiece->startOffset(), textPiece->endOffset()));
76     }
77
78 }
79
80 void DocumentMarkerController::addMarkerToNode(Node* node, unsigned startOffset, unsigned length, DocumentMarker::MarkerType type)
81 {
82     addMarker(node, DocumentMarker(type, startOffset, startOffset + length));
83 }
84
85 void DocumentMarkerController::addMarkerToNode(Node* node, unsigned startOffset, unsigned length, DocumentMarker::MarkerType type, DocumentMarker::Data&& data)
86 {
87     addMarker(node, DocumentMarker(type, startOffset, startOffset + length, WTFMove(data)));
88 }
89
90 void DocumentMarkerController::addTextMatchMarker(const Range* range, bool activeMatch)
91 {
92     for (TextIterator markedText(range); !markedText.atEnd(); markedText.advance()) {
93         RefPtr<Range> textPiece = markedText.range();
94         unsigned startOffset = textPiece->startOffset();
95         unsigned endOffset = textPiece->endOffset();
96         addMarker(&textPiece->startContainer(), DocumentMarker(startOffset, endOffset, activeMatch));
97     }
98 }
99
100 #if PLATFORM(IOS)
101
102 void DocumentMarkerController::addMarker(Range* range, DocumentMarker::MarkerType type, const String& description, const Vector<String>& interpretations, const RetainPtr<id>& metadata)
103 {
104     for (TextIterator markedText(range); !markedText.atEnd(); markedText.advance()) {
105         RefPtr<Range> textPiece = markedText.range();
106         addMarker(&textPiece->startContainer(), DocumentMarker(type, textPiece->startOffset(), textPiece->endOffset(), description, interpretations, metadata));
107     }
108 }
109
110 void DocumentMarkerController::addDictationPhraseWithAlternativesMarker(Range* range, const Vector<String>& interpretations)
111 {
112     ASSERT(interpretations.size() > 1);
113     if (interpretations.size() <= 1)
114         return;
115
116     size_t numberOfAlternatives = interpretations.size() - 1;
117     for (TextIterator markedText(range); !markedText.atEnd(); markedText.advance()) {
118         RefPtr<Range> textPiece = markedText.range();
119         DocumentMarker marker(DocumentMarker::DictationPhraseWithAlternatives, textPiece->startOffset(), textPiece->endOffset(), emptyString(), Vector<String>(numberOfAlternatives), RetainPtr<id>());
120         for (size_t i = 0; i < numberOfAlternatives; ++i)
121             marker.setAlternative(interpretations[i + 1], i);
122         addMarker(&textPiece->startContainer(), marker);
123     }
124 }
125
126 void DocumentMarkerController::addDictationResultMarker(Range* range, const RetainPtr<id>& metadata)
127 {
128     for (TextIterator markedText(range); !markedText.atEnd(); markedText.advance()) {
129         RefPtr<Range> textPiece = markedText.range();
130         addMarker(&textPiece->startContainer(), DocumentMarker(DocumentMarker::DictationResult, textPiece->startOffset(), textPiece->endOffset(), String(), Vector<String>(), metadata));
131     }
132 }
133
134 #endif
135
136 void DocumentMarkerController::addDraggedContentMarker(RefPtr<Range> range)
137 {
138     for (TextIterator markedText(range.get()); !markedText.atEnd(); markedText.advance()) {
139         RefPtr<Range> textPiece = markedText.range();
140         DocumentMarker::DraggedContentData draggedContentData { markedText.node() };
141         addMarker(&textPiece->startContainer(), { DocumentMarker::DraggedContent, textPiece->startOffset(), textPiece->endOffset(), WTFMove(draggedContentData) });
142     }
143 }
144
145 void DocumentMarkerController::removeMarkers(Range* range, OptionSet<DocumentMarker::MarkerType> markerTypes, RemovePartiallyOverlappingMarkerOrNot shouldRemovePartiallyOverlappingMarker)
146 {
147     for (TextIterator markedText(range); !markedText.atEnd(); markedText.advance()) {
148         if (!possiblyHasMarkers(markerTypes))
149             return;
150         ASSERT(!m_markers.isEmpty());
151
152         RefPtr<Range> textPiece = markedText.range();
153         unsigned startOffset = textPiece->startOffset();
154         unsigned endOffset = textPiece->endOffset();
155         removeMarkers(&textPiece->startContainer(), startOffset, endOffset - startOffset, markerTypes, shouldRemovePartiallyOverlappingMarker);
156     }
157 }
158
159 static void updateRenderedRectsForMarker(RenderedDocumentMarker& marker, Node& node)
160 {
161     ASSERT(!node.document().view() || !node.document().view()->needsLayout());
162
163     // FIXME: We should refactor this so that we don't use Range (because we only have one Node), but still share code with absoluteTextQuads().
164     RefPtr<Range> markerRange = Range::create(node.document(), &node, marker.startOffset(), &node, marker.endOffset());
165     if (!markerRange)
166         return;
167     Vector<FloatQuad> absoluteMarkerQuads;
168     markerRange->absoluteTextQuads(absoluteMarkerQuads, true);
169
170     Vector<FloatRect> absoluteMarkerRects;
171     absoluteMarkerRects.reserveInitialCapacity(absoluteMarkerQuads.size());
172     for (const auto& quad : absoluteMarkerQuads)
173         absoluteMarkerRects.uncheckedAppend(quad.boundingBox());
174
175     marker.setUnclippedAbsoluteRects(absoluteMarkerRects);
176 }
177
178 void DocumentMarkerController::invalidateRectsForAllMarkers()
179 {
180     if (!hasMarkers())
181         return;
182
183     for (auto& markers : m_markers.values()) {
184         for (auto& marker : *markers)
185             marker.invalidate();
186     }
187
188     if (Page* page = m_document.page())
189         page->chrome().client().didInvalidateDocumentMarkerRects();
190 }
191
192 void DocumentMarkerController::invalidateRectsForMarkersInNode(Node& node)
193 {
194     if (!hasMarkers())
195         return;
196
197     MarkerList* markers = m_markers.get(&node);
198     ASSERT(markers);
199
200     for (auto& marker : *markers)
201         marker.invalidate();
202
203     if (Page* page = m_document.page())
204         page->chrome().client().didInvalidateDocumentMarkerRects();
205 }
206
207 static void updateMainFrameLayoutIfNeeded(Document& document)
208 {
209     Frame* frame = document.frame();
210     if (!frame)
211         return;
212
213     FrameView* mainFrameView = frame->mainFrame().view();
214     if (!mainFrameView)
215         return;
216
217     mainFrameView->updateLayoutAndStyleIfNeededRecursive();
218 }
219
220 void DocumentMarkerController::updateRectsForInvalidatedMarkersOfType(DocumentMarker::MarkerType markerType)
221 {
222     if (!possiblyHasMarkers(markerType))
223         return;
224     ASSERT(!(m_markers.isEmpty()));
225
226     bool needsLayoutIfAnyRectsAreDirty = true;
227
228     for (auto& nodeAndMarkers : m_markers) {
229         Node& node = *nodeAndMarkers.key;
230         for (auto& marker : *nodeAndMarkers.value) {
231             if (marker.type() != markerType)
232                 continue;
233
234             if (marker.isValid())
235                 continue;
236
237             // We'll do up to one layout per call if we have any dirty markers.
238             if (needsLayoutIfAnyRectsAreDirty) {
239                 updateMainFrameLayoutIfNeeded(m_document);
240                 needsLayoutIfAnyRectsAreDirty = false;
241             }
242
243             updateRenderedRectsForMarker(marker, node);
244         }
245     }
246 }
247
248 Vector<FloatRect> DocumentMarkerController::renderedRectsForMarkers(DocumentMarker::MarkerType markerType)
249 {
250     Vector<FloatRect> result;
251
252     if (!possiblyHasMarkers(markerType))
253         return result;
254     ASSERT(!(m_markers.isEmpty()));
255
256     RefPtr<Frame> frame = m_document.frame();
257     if (!frame)
258         return result;
259     FrameView* frameView = frame->view();
260     if (!frameView)
261         return result;
262
263     updateRectsForInvalidatedMarkersOfType(markerType);
264
265     bool isSubframe = !frame->isMainFrame();
266     IntRect subframeClipRect;
267     if (isSubframe)
268         subframeClipRect = frameView->windowToContents(frameView->windowClipRect());
269
270     for (auto& nodeAndMarkers : m_markers) {
271         Node& node = *nodeAndMarkers.key;
272         FloatRect overflowClipRect;
273         if (RenderObject* renderer = node.renderer())
274             overflowClipRect = renderer->absoluteClippedOverflowRect();
275         for (auto& marker : *nodeAndMarkers.value) {
276             if (marker.type() != markerType)
277                 continue;
278
279             auto renderedRects = marker.unclippedAbsoluteRects();
280
281             // Clip document markers by their overflow clip.
282             if (node.renderer()) {
283                 for (auto& rect : renderedRects)
284                     rect.intersect(overflowClipRect);
285             }
286
287             // Clip subframe document markers by their frame.
288             if (isSubframe) {
289                 for (auto& rect : renderedRects)
290                     rect.intersect(subframeClipRect);
291             }
292
293             for (const auto& rect : renderedRects) {
294                 if (!rect.isEmpty())
295                     result.append(rect);
296             }
297         }
298     }
299     
300     return result;
301 }
302
303 static bool shouldInsertAsSeparateMarker(const DocumentMarker& newMarker)
304 {
305 #if PLATFORM(IOS)
306     if (newMarker.type() == DocumentMarker::DictationPhraseWithAlternatives || newMarker.type() == DocumentMarker::DictationResult)
307         return true;
308 #endif
309     if (newMarker.type() == DocumentMarker::DraggedContent) {
310         if (auto targetNode = WTF::get<DocumentMarker::DraggedContentData>(newMarker.data()).targetNode)
311             return targetNode->renderer() && targetNode->renderer()->isRenderReplaced();
312     }
313
314     return false;
315 }
316
317 // Markers are stored in order sorted by their start offset.
318 // Markers of the same type do not overlap each other.
319
320 void DocumentMarkerController::addMarker(Node* node, const DocumentMarker& newMarker) 
321 {
322     ASSERT(newMarker.endOffset() >= newMarker.startOffset());
323     if (newMarker.endOffset() == newMarker.startOffset())
324         return;
325
326     if (auto* renderer = node->renderer()) {
327         // FIXME: Factor the marker painting code out of InlineTextBox and teach simple line layout to use it.
328         if (is<RenderText>(*renderer))
329             downcast<RenderText>(*renderer).ensureLineBoxes();
330         else if (is<RenderBlockFlow>(*renderer))
331             downcast<RenderBlockFlow>(*renderer).ensureLineBoxes();
332     }
333
334     m_possiblyExistingMarkerTypes |= newMarker.type();
335
336     std::unique_ptr<MarkerList>& list = m_markers.add(node, nullptr).iterator->value;
337
338     if (!list) {
339         list = std::make_unique<MarkerList>();
340         list->append(RenderedDocumentMarker(newMarker));
341     } else if (shouldInsertAsSeparateMarker(newMarker)) {
342         // We don't merge dictation markers.
343         size_t i;
344         size_t numberOfMarkers = list->size();
345         for (i = 0; i < numberOfMarkers; ++i) {
346             DocumentMarker marker = list->at(i);
347             if (marker.startOffset() > newMarker.startOffset())
348                 break;
349         }
350         list->insert(i, RenderedDocumentMarker(newMarker));
351     } else {
352         RenderedDocumentMarker toInsert(newMarker);
353         size_t numMarkers = list->size();
354         size_t i;
355         // Iterate over all markers whose start offset is less than or equal to the new marker's.
356         // If one of them is of the same type as the new marker and touches it or intersects with it
357         // (there is at most one), remove it and adjust the new marker's start offset to encompass it.
358         for (i = 0; i < numMarkers; ++i) {
359             DocumentMarker marker = list->at(i);
360             if (marker.startOffset() > toInsert.startOffset())
361                 break;
362             if (marker.type() == toInsert.type() && marker.endOffset() >= toInsert.startOffset()) {
363                 toInsert.setStartOffset(marker.startOffset());
364                 list->remove(i);
365                 numMarkers--;
366                 break;
367             }
368         }
369         size_t j = i;
370         // Iterate over all markers whose end offset is less than or equal to the new marker's,
371         // removing markers of the same type as the new marker which touch it or intersect with it,
372         // adjusting the new marker's end offset to cover them if necessary.
373         while (j < numMarkers) {
374             DocumentMarker marker = list->at(j);
375             if (marker.startOffset() > toInsert.endOffset())
376                 break;
377             if (marker.type() == toInsert.type()) {
378                 list->remove(j);
379                 if (toInsert.endOffset() <= marker.endOffset()) {
380                     toInsert.setEndOffset(marker.endOffset());
381                     break;
382                 }
383                 numMarkers--;
384             } else
385                 j++;
386         }
387         // At this point i points to the node before which we want to insert.
388         list->insert(i, RenderedDocumentMarker(toInsert));
389     }
390
391     if (node->renderer())
392         node->renderer()->repaint();
393
394     invalidateRectsForMarkersInNode(*node);
395 }
396
397 // copies markers from srcNode to dstNode, applying the specified shift delta to the copies.  The shift is
398 // useful if, e.g., the caller has created the dstNode from a non-prefix substring of the srcNode.
399 void DocumentMarkerController::copyMarkers(Node* srcNode, unsigned startOffset, int length, Node* dstNode, int delta)
400 {
401     if (length <= 0)
402         return;
403
404     if (!possiblyHasMarkers(DocumentMarker::allMarkers()))
405         return;
406     ASSERT(!m_markers.isEmpty());
407
408     MarkerList* list = m_markers.get(srcNode);
409     if (!list)
410         return;
411
412     bool docDirty = false;
413     unsigned endOffset = startOffset + length - 1;
414     for (auto& marker : *list) {
415         // stop if we are now past the specified range
416         if (marker.startOffset() > endOffset)
417             break;
418
419         // skip marker that is before the specified range or is the wrong type
420         if (marker.endOffset() < startOffset)
421             continue;
422
423         // pin the marker to the specified range and apply the shift delta
424         docDirty = true;
425         if (marker.startOffset() < startOffset)
426             marker.setStartOffset(startOffset);
427         if (marker.endOffset() > endOffset)
428             marker.setEndOffset(endOffset);
429         marker.shiftOffsets(delta);
430
431         addMarker(dstNode, marker);
432     }
433
434     if (docDirty && dstNode->renderer())
435         dstNode->renderer()->repaint();
436 }
437
438 void DocumentMarkerController::removeMarkers(Node* node, unsigned startOffset, int length, OptionSet<DocumentMarker::MarkerType> markerTypes, RemovePartiallyOverlappingMarkerOrNot shouldRemovePartiallyOverlappingMarker)
439 {
440     if (length <= 0)
441         return;
442
443     if (!possiblyHasMarkers(markerTypes))
444         return;
445     ASSERT(!(m_markers.isEmpty()));
446
447     MarkerList* list = m_markers.get(node);
448     if (!list)
449         return;
450
451     bool docDirty = false;
452     unsigned endOffset = startOffset + length;
453     for (size_t i = 0; i < list->size();) {
454         DocumentMarker marker = list->at(i);
455
456         // markers are returned in order, so stop if we are now past the specified range
457         if (marker.startOffset() >= endOffset)
458             break;
459
460         // skip marker that is wrong type or before target
461         if (marker.endOffset() <= startOffset || !markerTypes.contains(marker.type())) {
462             i++;
463             continue;
464         }
465
466         // at this point we know that marker and target intersect in some way
467         docDirty = true;
468
469         // pitch the old marker
470         list->remove(i);
471
472         if (shouldRemovePartiallyOverlappingMarker)
473             // Stop here. Don't add resulting slices back.
474             continue;
475
476         // add either of the resulting slices that are left after removing target
477         if (startOffset > marker.startOffset()) {
478             DocumentMarker newLeft = marker;
479             newLeft.setEndOffset(startOffset);
480             list->insert(i, RenderedDocumentMarker(newLeft));
481             // i now points to the newly-inserted node, but we want to skip that one
482             i++;
483         }
484         if (marker.endOffset() > endOffset) {
485             DocumentMarker newRight = marker;
486             newRight.setStartOffset(endOffset);
487             list->insert(i, RenderedDocumentMarker(newRight));
488             // i now points to the newly-inserted node, but we want to skip that one
489             i++;
490         }
491     }
492
493     if (list->isEmpty()) {
494         m_markers.remove(node);
495         if (m_markers.isEmpty())
496             m_possiblyExistingMarkerTypes = { };
497     }
498
499     if (docDirty && node->renderer())
500         node->renderer()->repaint();
501 }
502
503 DocumentMarker* DocumentMarkerController::markerContainingPoint(const LayoutPoint& point, DocumentMarker::MarkerType markerType)
504 {
505     if (!possiblyHasMarkers(markerType))
506         return nullptr;
507     ASSERT(!(m_markers.isEmpty()));
508
509     updateRectsForInvalidatedMarkersOfType(markerType);
510
511     for (auto& nodeAndMarkers : m_markers) {
512         for (auto& marker : *nodeAndMarkers.value) {
513             if (marker.type() != markerType)
514                 continue;
515
516             if (marker.contains(point))
517                 return &marker;
518         }
519     }
520
521     return nullptr;
522 }
523
524 Vector<RenderedDocumentMarker*> DocumentMarkerController::markersFor(Node* node, OptionSet<DocumentMarker::MarkerType> markerTypes)
525 {
526     if (!possiblyHasMarkers(markerTypes))
527         return { };
528
529     Vector<RenderedDocumentMarker*> result;
530     MarkerList* list = m_markers.get(node);
531     if (!list)
532         return result;
533
534     for (auto& marker : *list) {
535         if (markerTypes.contains(marker.type()))
536             result.append(&marker);
537     }
538
539     return result;
540 }
541
542 Vector<RenderedDocumentMarker*> DocumentMarkerController::markersInRange(Range& range, OptionSet<DocumentMarker::MarkerType> markerTypes)
543 {
544     if (!possiblyHasMarkers(markerTypes))
545         return Vector<RenderedDocumentMarker*>();
546
547     Vector<RenderedDocumentMarker*> foundMarkers;
548
549     Node& startContainer = range.startContainer();
550     Node& endContainer = range.endContainer();
551
552     Node* pastLastNode = range.pastLastNode();
553     for (Node* node = range.firstNode(); node != pastLastNode; node = NodeTraversal::next(*node)) {
554         for (auto* marker : markersFor(node)) {
555             if (!markerTypes.contains(marker->type()))
556                 continue;
557             if (node == &startContainer && marker->endOffset() <= range.startOffset())
558                 continue;
559             if (node == &endContainer && marker->startOffset() >= range.endOffset())
560                 continue;
561             foundMarkers.append(marker);
562         }
563     }
564     return foundMarkers;
565 }
566
567 void DocumentMarkerController::removeMarkers(Node* node, OptionSet<DocumentMarker::MarkerType> markerTypes)
568 {
569     if (!possiblyHasMarkers(markerTypes))
570         return;
571     ASSERT(!m_markers.isEmpty());
572     
573     auto iterator = m_markers.find(node);
574     if (iterator != m_markers.end())
575         removeMarkersFromList(iterator, markerTypes);
576 }
577
578 void DocumentMarkerController::removeMarkers(OptionSet<DocumentMarker::MarkerType> markerTypes)
579 {
580     if (!possiblyHasMarkers(markerTypes))
581         return;
582     ASSERT(!m_markers.isEmpty());
583
584     for (auto& node : copyToVector(m_markers.keys())) {
585         auto iterator = m_markers.find(node);
586         if (iterator != m_markers.end())
587             removeMarkersFromList(iterator, markerTypes);
588     }
589
590     m_possiblyExistingMarkerTypes -= markerTypes;
591 }
592
593 void DocumentMarkerController::removeMarkersFromList(MarkerMap::iterator iterator, OptionSet<DocumentMarker::MarkerType> markerTypes)
594 {
595     bool needsRepainting = false;
596     bool listCanBeRemoved;
597
598     if (markerTypes == DocumentMarker::allMarkers()) {
599         needsRepainting = true;
600         listCanBeRemoved = true;
601     } else {
602         MarkerList* list = iterator->value.get();
603
604         for (size_t i = 0; i != list->size(); ) {
605             DocumentMarker marker = list->at(i);
606
607             // skip nodes that are not of the specified type
608             if (!markerTypes.contains(marker.type())) {
609                 ++i;
610                 continue;
611             }
612
613             // pitch the old marker
614             list->remove(i);
615             needsRepainting = true;
616             // i now is the index of the next marker
617         }
618
619         listCanBeRemoved = list->isEmpty();
620     }
621
622     if (needsRepainting) {
623         if (auto renderer = iterator->key->renderer())
624             renderer->repaint();
625     }
626
627     if (listCanBeRemoved) {
628         m_markers.remove(iterator);
629         if (m_markers.isEmpty())
630             m_possiblyExistingMarkerTypes = { };
631     }
632 }
633
634 void DocumentMarkerController::repaintMarkers(OptionSet<DocumentMarker::MarkerType> markerTypes)
635 {
636     if (!possiblyHasMarkers(markerTypes))
637         return;
638     ASSERT(!m_markers.isEmpty());
639
640     // outer loop: process each markered node in the document
641     for (auto& marker : m_markers) {
642         Node* node = marker.key.get();
643
644         // inner loop: process each marker in the current node
645         bool nodeNeedsRepaint = false;
646         for (auto& documentMarker : *marker.value) {
647             if (markerTypes.contains(documentMarker.type())) {
648                 nodeNeedsRepaint = true;
649                 break;
650             }
651         }
652
653         if (!nodeNeedsRepaint)
654             continue;
655
656         // cause the node to be redrawn
657         if (auto renderer = node->renderer())
658             renderer->repaint();
659     }
660 }
661
662 void DocumentMarkerController::shiftMarkers(Node* node, unsigned startOffset, int delta)
663 {
664     if (!possiblyHasMarkers(DocumentMarker::allMarkers()))
665         return;
666     ASSERT(!m_markers.isEmpty());
667
668     MarkerList* list = m_markers.get(node);
669     if (!list)
670         return;
671
672     bool didShiftMarker = false;
673     for (size_t i = 0; i != list->size(); ) {
674         RenderedDocumentMarker& marker = list->at(i);
675         // FIXME: How can this possibly be iOS-specific code?
676 #if PLATFORM(IOS)
677         int targetStartOffset = marker.startOffset() + delta;
678         int targetEndOffset = marker.endOffset() + delta;
679         if (targetStartOffset >= node->maxCharacterOffset() || targetEndOffset <= 0) {
680             list->remove(i);
681             continue;
682         }
683 #endif
684         if (marker.startOffset() >= startOffset) {
685             ASSERT((int)marker.startOffset() + delta >= 0);
686             marker.shiftOffsets(delta);
687             didShiftMarker = true;
688 #if !PLATFORM(IOS)
689         }
690 #else
691         // FIXME: Inserting text inside a DocumentMarker does not grow the marker.
692         // See <https://bugs.webkit.org/show_bug.cgi?id=62504>.
693         } else if (marker.endOffset() > startOffset) {
694             if (marker.endOffset() + delta <= marker.startOffset()) {
695                 list->remove(i);
696                 continue;
697             }
698             marker.setEndOffset(targetEndOffset < node->maxCharacterOffset() ? targetEndOffset : node->maxCharacterOffset());
699             didShiftMarker = true;
700         }
701 #endif
702         ++i;
703     }
704
705     if (didShiftMarker) {
706         invalidateRectsForMarkersInNode(*node);
707
708         if (node->renderer())
709             node->renderer()->repaint();
710     }
711 }
712
713 void DocumentMarkerController::setMarkersActive(Range* range, bool active)
714 {
715     if (!possiblyHasMarkers(DocumentMarker::allMarkers()))
716         return;
717     ASSERT(!m_markers.isEmpty());
718
719     Node& startContainer = range->startContainer();
720     Node& endContainer = range->endContainer();
721
722     Node* pastLastNode = range->pastLastNode();
723
724     for (Node* node = range->firstNode(); node != pastLastNode; node = NodeTraversal::next(*node)) {
725         unsigned startOffset = node == &startContainer ? range->startOffset() : 0;
726         unsigned endOffset = node == &endContainer ? range->endOffset() : std::numeric_limits<unsigned>::max();
727         setMarkersActive(node, startOffset, endOffset, active);
728     }
729 }
730
731 void DocumentMarkerController::setMarkersActive(Node* node, unsigned startOffset, unsigned endOffset, bool active)
732 {
733     MarkerList* list = m_markers.get(node);
734     if (!list)
735         return;
736
737     bool didActivateMarker = false;
738     for (auto& marker : *list) {
739         // Markers are returned in order, so stop if we are now past the specified range.
740         if (marker.startOffset() >= endOffset)
741             break;
742
743         // Skip marker that is wrong type or before target.
744         if (marker.endOffset() < startOffset || marker.type() != DocumentMarker::TextMatch)
745             continue;
746
747         marker.setActiveMatch(active);
748         didActivateMarker = true;
749     }
750
751     if (didActivateMarker && node->renderer())
752         node->renderer()->repaint();
753 }
754
755 bool DocumentMarkerController::hasMarkers(Range& range, OptionSet<DocumentMarker::MarkerType> markerTypes)
756 {
757     if (!possiblyHasMarkers(markerTypes))
758         return false;
759     ASSERT(!m_markers.isEmpty());
760
761     Node& startContainer = range.startContainer();
762     Node& endContainer = range.endContainer();
763
764     Node* pastLastNode = range.pastLastNode();
765     for (Node* node = range.firstNode(); node != pastLastNode; node = NodeTraversal::next(*node)) {
766         for (auto* marker : markersFor(node)) {
767             if (!markerTypes.contains(marker->type()))
768                 continue;
769             if (node == &startContainer && marker->endOffset() <= static_cast<unsigned>(range.startOffset()))
770                 continue;
771             if (node == &endContainer && marker->startOffset() >= static_cast<unsigned>(range.endOffset()))
772                 continue;
773             return true;
774         }
775     }
776     return false;
777 }
778
779 void DocumentMarkerController::clearDescriptionOnMarkersIntersectingRange(Range& range, OptionSet<DocumentMarker::MarkerType> markerTypes)
780 {
781     if (!possiblyHasMarkers(markerTypes))
782         return;
783     ASSERT(!m_markers.isEmpty());
784
785     Node& startContainer = range.startContainer();
786     Node& endContainer = range.endContainer();
787
788     Node* pastLastNode = range.pastLastNode();
789     for (Node* node = range.firstNode(); node != pastLastNode; node = NodeTraversal::next(*node)) {
790         unsigned startOffset = node == &startContainer ? range.startOffset() : 0;
791         unsigned endOffset = node == &endContainer ? static_cast<unsigned>(range.endOffset()) : std::numeric_limits<unsigned>::max();
792         MarkerList* list = m_markers.get(node);
793         if (!list)
794             continue;
795
796         for (size_t i = 0; i < list->size(); ++i) {
797             DocumentMarker& marker = list->at(i);
798
799             // markers are returned in order, so stop if we are now past the specified range
800             if (marker.startOffset() >= endOffset)
801                 break;
802
803             // skip marker that is wrong type or before target
804             if (marker.endOffset() <= startOffset || !markerTypes.contains(marker.type())) {
805                 i++;
806                 continue;
807             }
808
809             marker.clearData();
810         }
811     }
812 }
813
814 #if ENABLE(TREE_DEBUGGING)
815 void DocumentMarkerController::showMarkers() const
816 {
817     fprintf(stderr, "%d nodes have markers:\n", m_markers.size());
818     for (auto& marker : m_markers) {
819         Node* node = marker.key.get();
820         fprintf(stderr, "%p", node);
821         for (auto& documentMarker : *marker.value)
822             fprintf(stderr, " %d:[%d:%d](%d)", documentMarker.type(), documentMarker.startOffset(), documentMarker.endOffset(), documentMarker.isActiveMatch());
823
824         fprintf(stderr, "\n");
825     }
826 }
827 #endif
828
829 } // namespace WebCore
830
831 #if ENABLE(TREE_DEBUGGING)
832 void showDocumentMarkers(const WebCore::DocumentMarkerController* controller)
833 {
834     if (controller)
835         controller->showMarkers();
836 }
837 #endif