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