src/third_party/WebKit/Source/core/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 "core/dom/DocumentMarkerController.h"
  29
  30 #include "core/dom/Node.h"
  31 #include "core/dom/NodeTraversal.h"
  32 #include "core/dom/Range.h"
  33 #include "core/dom/RenderedDocumentMarker.h"
  34 #include "core/dom/Text.h"
  35 #include "core/editing/TextIterator.h"
  36 #include "core/rendering/RenderObject.h"
  37
  38 #ifndef NDEBUG
  39 #include <stdio.h>
  40 #endif
  41
  42 namespace blink {
  43
  44 MarkerRemoverPredicate::MarkerRemoverPredicate(const Vector<String>& words)
  45     : m_words(words)
  46 {
  47 }
  48
  49 bool MarkerRemoverPredicate::operator()(const DocumentMarker& documentMarker, const Text& textNode) const
  50 {
  51     unsigned start  = documentMarker.startOffset();
  52     unsigned length = documentMarker.endOffset() - documentMarker.startOffset();
  53
  54     String markerText = textNode.data().substring(start, length);
  55     return m_words.contains(markerText);
  56 }
  57
  58 namespace {
  59
  60 DocumentMarker::MarkerTypeIndex MarkerTypeToMarkerIndex(DocumentMarker::MarkerType type)
  61 {
  62     switch (type) {
  63     case DocumentMarker::Spelling:
  64         return DocumentMarker::SpellingMarkerIndex;
  65     case DocumentMarker::Grammar:
  66         return DocumentMarker::GramarMarkerIndex;
  67     case DocumentMarker::TextMatch:
  68         return DocumentMarker::TextMatchMarkerIndex;
  69     case DocumentMarker::InvisibleSpellcheck:
  70         return DocumentMarker::InvisibleSpellcheckMarkerIndex;
  71     }
  72
  73     ASSERT_NOT_REACHED();
  74     return DocumentMarker::SpellingMarkerIndex;
  75 }
  76
  77 } // namespace
  78
  79 inline bool DocumentMarkerController::possiblyHasMarkers(DocumentMarker::MarkerTypes types)
  80 {
  81     return m_possiblyExistingMarkerTypes.intersects(types);
  82 }
  83
  84 DocumentMarkerController::DocumentMarkerController()
  85     : m_possiblyExistingMarkerTypes(0)
  86 {
  87 }
  88
  89 DEFINE_EMPTY_DESTRUCTOR_WILL_BE_REMOVED(DocumentMarkerController);
  90
  91 void DocumentMarkerController::clear()
  92 {
  93     m_markers.clear();
  94     m_possiblyExistingMarkerTypes = 0;
  95 }
  96
  97 void DocumentMarkerController::addMarker(Range* range, DocumentMarker::MarkerType type, const String& description, uint32_t hash)
  98 {
  99     // Use a TextIterator to visit the potentially multiple nodes the range covers.
 100     for (TextIterator markedText(range); !markedText.atEnd(); markedText.advance()) {
 101         addMarker(markedText.startContainer(), DocumentMarker(type, markedText.startOffset(), markedText.endOffset(), description, hash));
 102     }
 103 }
 104
 105 void DocumentMarkerController::addMarker(const Position& start, const Position& end, DocumentMarker::MarkerType type, const String& description, uint32_t hash)
 106 {
 107     // Use a TextIterator to visit the potentially multiple nodes the range covers.
 108     for (TextIterator markedText(start, end); !markedText.atEnd(); markedText.advance()) {
 109         addMarker(markedText.startContainer(), DocumentMarker(type, markedText.startOffset(), markedText.endOffset(), description, hash));
 110     }
 111 }
 112
 113 void DocumentMarkerController::addTextMatchMarker(const Range* range, bool activeMatch)
 114 {
 115     // Use a TextIterator to visit the potentially multiple nodes the range covers.
 116     for (TextIterator markedText(range); !markedText.atEnd(); markedText.advance()) {
 117         unsigned startOffset = markedText.startOffset();
 118         unsigned endOffset = markedText.endOffset();
 119         addMarker(markedText.startContainer(), DocumentMarker(startOffset, endOffset, activeMatch));
 120         if (endOffset > startOffset) {
 121             // Rendered rects for markers in WebKit are not populated until each time
 122             // the markers are painted. However, we need it to happen sooner, because
 123             // the whole purpose of tickmarks on the scrollbar is to show where
 124             // matches off-screen are (that haven't been painted yet).
 125             Node* node = markedText.startContainer();
 126             DocumentMarkerVector markers = markersFor(node);
 127             toRenderedDocumentMarker(markers[markers.size() - 1])->setRenderedRect(range->boundingBox());
 128         }
 129     }
 130 }
 131
 132 void DocumentMarkerController::prepareForDestruction()
 133 {
 134     clear();
 135 }
 136
 137 void DocumentMarkerController::removeMarkers(TextIterator& markedText, DocumentMarker::MarkerTypes markerTypes, RemovePartiallyOverlappingMarkerOrNot shouldRemovePartiallyOverlappingMarker)
 138 {
 139     for (; !markedText.atEnd(); markedText.advance()) {
 140         if (!possiblyHasMarkers(markerTypes))
 141             return;
 142         ASSERT(!m_markers.isEmpty());
 143
 144         int startOffset = markedText.startOffset();
 145         int endOffset = markedText.endOffset();
 146         removeMarkers(markedText.startContainer(), startOffset, endOffset - startOffset, markerTypes, shouldRemovePartiallyOverlappingMarker);
 147     }
 148 }
 149
 150 void DocumentMarkerController::removeMarkers(Range* range, DocumentMarker::MarkerTypes markerTypes, RemovePartiallyOverlappingMarkerOrNot shouldRemovePartiallyOverlappingMarker)
 151 {
 152     TextIterator markedText(range);
 153     DocumentMarkerController::removeMarkers(markedText, markerTypes, shouldRemovePartiallyOverlappingMarker);
 154 }
 155
 156 void DocumentMarkerController::removeMarkers(const Position& start, const Position& end, DocumentMarker::MarkerTypes markerTypes, RemovePartiallyOverlappingMarkerOrNot shouldRemovePartiallyOverlappingMarker)
 157 {
 158     TextIterator markedText(start, end);
 159     DocumentMarkerController::removeMarkers(markedText, markerTypes, shouldRemovePartiallyOverlappingMarker);
 160 }
 161
 162 static bool startsFurther(const OwnPtrWillBeMember<RenderedDocumentMarker>& lhv, const DocumentMarker* rhv)
 163 {
 164     return lhv->startOffset() < rhv->startOffset();
 165 }
 166
 167 static bool startsAfter(const OwnPtrWillBeMember<RenderedDocumentMarker>& marker, size_t startOffset)
 168 {
 169     return marker->startOffset() < startOffset;
 170 }
 171
 172 static bool endsBefore(size_t startOffset, const OwnPtrWillBeMember<RenderedDocumentMarker>& rhv)
 173 {
 174     return startOffset < rhv->endOffset();
 175 }
 176
 177 static bool compareByStart(const RawPtrWillBeMember<DocumentMarker>& lhv, const RawPtrWillBeMember<DocumentMarker>& rhv)
 178 {
 179     return lhv->startOffset() < rhv->startOffset();
 180 }
 181
 182 static bool doesNotOverlap(const OwnPtrWillBeMember<RenderedDocumentMarker>& lhv, const DocumentMarker* rhv)
 183 {
 184     return lhv->endOffset() < rhv->startOffset();
 185 }
 186
 187 static bool doesNotInclude(const OwnPtrWillBeMember<RenderedDocumentMarker>& marker, size_t startOffset)
 188 {
 189     return marker->endOffset() < startOffset;
 190 }
 191
 192 // Markers are stored in order sorted by their start offset.
 193 // Markers of the same type do not overlap each other.
 194
 195 void DocumentMarkerController::addMarker(Node* node, const DocumentMarker& newMarker)
 196 {
 197     ASSERT(newMarker.endOffset() >= newMarker.startOffset());
 198     if (newMarker.endOffset() == newMarker.startOffset())
 199         return;
 200
 201     m_possiblyExistingMarkerTypes.add(newMarker.type());
 202
 203     OwnPtrWillBeMember<MarkerLists>& markers = m_markers.add(node, nullptr).storedValue->value;
 204     if (!markers) {
 205         markers = adoptPtrWillBeNoop(new MarkerLists);
 206         markers->grow(DocumentMarker::MarkerTypeIndexesCount);
 207     }
 208
 209     DocumentMarker::MarkerTypeIndex markerListIndex = MarkerTypeToMarkerIndex(newMarker.type());
 210     if (!markers->at(markerListIndex)) {
 211         markers->insert(markerListIndex, adoptPtrWillBeNoop(new MarkerList));
 212     }
 213
 214     OwnPtrWillBeMember<MarkerList>& list = markers->at(markerListIndex);
 215     if (list->isEmpty() || list->last()->endOffset() < newMarker.startOffset()) {
 216         list->append(RenderedDocumentMarker::create(newMarker));
 217     } else {
 218         DocumentMarker toInsert(newMarker);
 219         if (toInsert.type() != DocumentMarker::TextMatch) {
 220             mergeOverlapping(list.get(), toInsert);
 221         } else {
 222             MarkerList::iterator pos = std::lower_bound(list->begin(), list->end(), &toInsert, startsFurther);
 223             list->insert(pos - list->begin(), RenderedDocumentMarker::create(toInsert));
 224         }
 225     }
 226
 227     // repaint the affected node
 228     if (node->renderer())
 229         node->renderer()->setShouldDoFullPaintInvalidation();
 230 }
 231
 232 void DocumentMarkerController::mergeOverlapping(MarkerList* list, DocumentMarker& toInsert)
 233 {
 234     MarkerList::iterator firstOverlapping = std::lower_bound(list->begin(), list->end(), &toInsert, doesNotOverlap);
 235     size_t index = firstOverlapping - list->begin();
 236     list->insert(index, RenderedDocumentMarker::create(toInsert));
 237     MarkerList::iterator inserted = list->begin() + index;
 238     firstOverlapping = inserted + 1;
 239     for (MarkerList::iterator i = firstOverlapping; i != list->end() && (*i)->startOffset() <= (*inserted)->endOffset(); ) {
 240         (*inserted)->setStartOffset(std::min((*inserted)->startOffset(), (*i)->startOffset()));
 241         (*inserted)->setEndOffset(std::max((*inserted)->endOffset(), (*i)->endOffset()));
 242         list->remove(i - list->begin());
 243     }
 244 }
 245
 246 // copies markers from srcNode to dstNode, applying the specified shift delta to the copies.  The shift is
 247 // useful if, e.g., the caller has created the dstNode from a non-prefix substring of the srcNode.
 248 void DocumentMarkerController::copyMarkers(Node* srcNode, unsigned startOffset, int length, Node* dstNode, int delta)
 249 {
 250     if (length <= 0)
 251         return;
 252
 253     if (!possiblyHasMarkers(DocumentMarker::AllMarkers()))
 254         return;
 255     ASSERT(!m_markers.isEmpty());
 256
 257     MarkerLists* markers = m_markers.get(srcNode);
 258     if (!markers)
 259         return;
 260
 261     bool docDirty = false;
 262     for (size_t markerListIndex = 0; markerListIndex < DocumentMarker::MarkerTypeIndexesCount; ++markerListIndex) {
 263         OwnPtrWillBeMember<MarkerList>& list = (*markers)[markerListIndex];
 264         if (!list)
 265             continue;
 266
 267         unsigned endOffset = startOffset + length - 1;
 268         MarkerList::iterator startPos = std::lower_bound(list->begin(), list->end(), startOffset, doesNotInclude);
 269         for (MarkerList::iterator i = startPos; i != list->end(); ++i) {
 270             DocumentMarker* marker = i->get();
 271
 272             // stop if we are now past the specified range
 273             if (marker->startOffset() > endOffset)
 274                 break;
 275
 276             // pin the marker to the specified range and apply the shift delta
 277             docDirty = true;
 278             if (marker->startOffset() < startOffset)
 279                 marker->setStartOffset(startOffset);
 280             if (marker->endOffset() > endOffset)
 281                 marker->setEndOffset(endOffset);
 282             marker->shiftOffsets(delta);
 283
 284             addMarker(dstNode, *marker);
 285         }
 286     }
 287
 288     // repaint the affected node
 289     if (docDirty && dstNode->renderer())
 290         dstNode->renderer()->setShouldDoFullPaintInvalidation();
 291 }
 292
 293 void DocumentMarkerController::removeMarkers(Node* node, unsigned startOffset, int length, DocumentMarker::MarkerTypes markerTypes, RemovePartiallyOverlappingMarkerOrNot shouldRemovePartiallyOverlappingMarker)
 294 {
 295     if (length <= 0)
 296         return;
 297
 298     if (!possiblyHasMarkers(markerTypes))
 299         return;
 300     ASSERT(!(m_markers.isEmpty()));
 301
 302     MarkerLists* markers = m_markers.get(node);
 303     if (!markers)
 304         return;
 305
 306     bool docDirty = false;
 307     size_t emptyListsCount = 0;
 308     for (size_t markerListIndex = 0; markerListIndex < DocumentMarker::MarkerTypeIndexesCount; ++markerListIndex) {
 309         OwnPtrWillBeMember<MarkerList>& list = (*markers)[markerListIndex];
 310         if (!list || list->isEmpty()) {
 311             if (list.get() && list->isEmpty())
 312                 list.clear();
 313             ++emptyListsCount;
 314             continue;
 315         }
 316         if (!markerTypes.contains((*list->begin())->type()))
 317             continue;
 318         unsigned endOffset = startOffset + length;
 319         MarkerList::iterator startPos = std::upper_bound(list->begin(), list->end(), startOffset, endsBefore);
 320         for (MarkerList::iterator i = startPos; i != list->end(); ) {
 321             DocumentMarker marker(*i->get());
 322
 323             // markers are returned in order, so stop if we are now past the specified range
 324             if (marker.startOffset() >= endOffset)
 325                 break;
 326
 327             // at this point we know that marker and target intersect in some way
 328             docDirty = true;
 329
 330             // pitch the old marker
 331             list->remove(i - list->begin());
 332
 333             if (shouldRemovePartiallyOverlappingMarker) {
 334                 // Stop here. Don't add resulting slices back.
 335                 continue;
 336             }
 337
 338             // add either of the resulting slices that are left after removing target
 339             if (startOffset > marker.startOffset()) {
 340                 DocumentMarker newLeft = marker;
 341                 newLeft.setEndOffset(startOffset);
 342                 size_t insertIndex = i - list->begin();
 343                 list->insert(insertIndex, RenderedDocumentMarker::create(newLeft));
 344                 // Move to the marker after the inserted one.
 345                 i = list->begin() + insertIndex + 1;
 346             }
 347             if (marker.endOffset() > endOffset) {
 348                 DocumentMarker newRight = marker;
 349                 newRight.setStartOffset(endOffset);
 350                 size_t insertIndex = i - list->begin();
 351                 list->insert(insertIndex, RenderedDocumentMarker::create(newRight));
 352                 // Move to the marker after the inserted one.
 353                 i = list->begin() + insertIndex + 1;
 354             }
 355         }
 356
 357         if (list->isEmpty()) {
 358             list.clear();
 359             ++emptyListsCount;
 360         }
 361     }
 362
 363     if (emptyListsCount == DocumentMarker::MarkerTypeIndexesCount) {
 364         m_markers.remove(node);
 365         if (m_markers.isEmpty())
 366             m_possiblyExistingMarkerTypes = 0;
 367     }
 368
 369     // repaint the affected node
 370     if (docDirty && node->renderer())
 371         node->renderer()->setShouldDoFullPaintInvalidation();
 372 }
 373
 374 DocumentMarker* DocumentMarkerController::markerContainingPoint(const LayoutPoint& point, DocumentMarker::MarkerType markerType)
 375 {
 376     if (!possiblyHasMarkers(markerType))
 377         return 0;
 378     ASSERT(!(m_markers.isEmpty()));
 379
 380     // outer loop: process each node that contains any markers
 381     MarkerMap::iterator end = m_markers.end();
 382     for (MarkerMap::iterator nodeIterator = m_markers.begin(); nodeIterator != end; ++nodeIterator) {
 383         // inner loop; process each marker in this node
 384         MarkerLists* markers = nodeIterator->value.get();
 385         OwnPtrWillBeMember<MarkerList>& list = (*markers)[MarkerTypeToMarkerIndex(markerType)];
 386         unsigned markerCount = list.get() ? list->size() : 0;
 387         for (unsigned markerIndex = 0; markerIndex < markerCount; ++markerIndex) {
 388             RenderedDocumentMarker* marker = list->at(markerIndex).get();
 389             if (marker->contains(point))
 390                 return marker;
 391         }
 392     }
 393
 394     return 0;
 395 }
 396
 397 DocumentMarkerVector DocumentMarkerController::markersFor(Node* node, DocumentMarker::MarkerTypes markerTypes)
 398 {
 399     DocumentMarkerVector result;
 400
 401     MarkerLists* markers = m_markers.get(node);
 402     if (!markers)
 403         return result;
 404
 405     for (size_t markerListIndex = 0; markerListIndex < DocumentMarker::MarkerTypeIndexesCount; ++markerListIndex) {
 406         OwnPtrWillBeMember<MarkerList>& list = (*markers)[markerListIndex];
 407         if (!list || list->isEmpty() || !markerTypes.contains((*list->begin())->type()))
 408             continue;
 409
 410         for (size_t i = 0; i < list->size(); ++i)
 411             result.append(list->at(i).get());
 412     }
 413
 414     std::sort(result.begin(), result.end(), compareByStart);
 415     return result;
 416 }
 417
 418 DocumentMarkerVector DocumentMarkerController::markers()
 419 {
 420     DocumentMarkerVector result;
 421     for (MarkerMap::iterator i = m_markers.begin(); i != m_markers.end(); ++i) {
 422         MarkerLists* markers = i->value.get();
 423         for (size_t markerListIndex = 0; markerListIndex < DocumentMarker::MarkerTypeIndexesCount; ++markerListIndex) {
 424             OwnPtrWillBeMember<MarkerList>& list = (*markers)[markerListIndex];
 425             for (size_t j = 0; list.get() && j < list->size(); ++j)
 426                 result.append(list->at(j).get());
 427         }
 428     }
 429     std::sort(result.begin(), result.end(), compareByStart);
 430     return result;
 431 }
 432
 433 DocumentMarkerVector DocumentMarkerController::markersInRange(Range* range, DocumentMarker::MarkerTypes markerTypes)
 434 {
 435     if (!possiblyHasMarkers(markerTypes))
 436         return DocumentMarkerVector();
 437
 438     DocumentMarkerVector foundMarkers;
 439
 440     Node* startContainer = range->startContainer();
 441     ASSERT(startContainer);
 442     Node* endContainer = range->endContainer();
 443     ASSERT(endContainer);
 444
 445     Node* pastLastNode = range->pastLastNode();
 446     for (Node* node = range->firstNode(); node != pastLastNode; node = NodeTraversal::next(*node)) {
 447         DocumentMarkerVector markers = markersFor(node);
 448         DocumentMarkerVector::const_iterator end = markers.end();
 449         for (DocumentMarkerVector::const_iterator it = markers.begin(); it != end; ++it) {
 450             DocumentMarker* marker = *it;
 451             if (!markerTypes.contains(marker->type()))
 452                 continue;
 453             if (node == startContainer && marker->endOffset() <= static_cast<unsigned>(range->startOffset()))
 454                 continue;
 455             if (node == endContainer && marker->startOffset() >= static_cast<unsigned>(range->endOffset()))
 456                 continue;
 457             foundMarkers.append(marker);
 458         }
 459     }
 460     return foundMarkers;
 461 }
 462
 463 Vector<IntRect> DocumentMarkerController::renderedRectsForMarkers(DocumentMarker::MarkerType markerType)
 464 {
 465     Vector<IntRect> result;
 466
 467     if (!possiblyHasMarkers(markerType))
 468         return result;
 469     ASSERT(!(m_markers.isEmpty()));
 470
 471     // outer loop: process each node
 472     MarkerMap::iterator end = m_markers.end();
 473     for (MarkerMap::iterator nodeIterator = m_markers.begin(); nodeIterator != end; ++nodeIterator) {
 474         // inner loop; process each marker in this node
 475         MarkerLists* markers = nodeIterator->value.get();
 476         for (size_t markerListIndex = 0; markerListIndex < DocumentMarker::MarkerTypeIndexesCount; ++markerListIndex) {
 477             OwnPtrWillBeMember<MarkerList>& list = (*markers)[markerListIndex];
 478             if (!list || list->isEmpty() || (*list->begin())->type() != markerType)
 479                 continue;
 480             for (unsigned markerIndex = 0; markerIndex < list->size(); ++markerIndex) {
 481                 RenderedDocumentMarker* marker = list->at(markerIndex).get();
 482                 if (!marker->isRendered())
 483                     continue;
 484                 result.append(marker->renderedRect());
 485             }
 486         }
 487     }
 488
 489     return result;
 490 }
 491
 492 void DocumentMarkerController::trace(Visitor* visitor)
 493 {
 494 #if ENABLE(OILPAN)
 495     visitor->trace(m_markers);
 496 #endif
 497 }
 498
 499 void DocumentMarkerController::removeMarkers(Node* node, DocumentMarker::MarkerTypes markerTypes)
 500 {
 501     if (!possiblyHasMarkers(markerTypes))
 502         return;
 503     ASSERT(!m_markers.isEmpty());
 504
 505     MarkerMap::iterator iterator = m_markers.find(node);
 506     if (iterator != m_markers.end())
 507         removeMarkersFromList(iterator, markerTypes);
 508 }
 509
 510 void DocumentMarkerController::removeMarkers(const MarkerRemoverPredicate& shouldRemoveMarker)
 511 {
 512     for (MarkerMap::iterator i = m_markers.begin(); i != m_markers.end(); ++i) {
 513         MarkerLists* markers = i->value.get();
 514         for (size_t markerListIndex = 0; markerListIndex < DocumentMarker::MarkerTypeIndexesCount; ++markerListIndex) {
 515             OwnPtrWillBeMember<MarkerList>& list = (*markers)[markerListIndex];
 516
 517             WillBeHeapVector<RawPtrWillBeMember<RenderedDocumentMarker> > markersToBeRemoved;
 518             for (size_t j = 0; list.get() && j < list->size(); ++j) {
 519                 if (i->key->isTextNode() && shouldRemoveMarker(*list->at(j).get(), static_cast<const Text&>(*i->key)))
 520                     markersToBeRemoved.append(list->at(j).get());
 521             }
 522
 523             for (size_t j = 0; j < markersToBeRemoved.size(); ++j)
 524                 list->remove(list->find(markersToBeRemoved[j].get()));
 525         }
 526     }
 527 }
 528
 529 void DocumentMarkerController::removeMarkers(DocumentMarker::MarkerTypes markerTypes)
 530 {
 531     if (!possiblyHasMarkers(markerTypes))
 532         return;
 533     ASSERT(!m_markers.isEmpty());
 534
 535     Vector<const Node*> nodesWithMarkers;
 536     copyKeysToVector(m_markers, nodesWithMarkers);
 537     unsigned size = nodesWithMarkers.size();
 538     for (unsigned i = 0; i < size; ++i) {
 539         MarkerMap::iterator iterator = m_markers.find(nodesWithMarkers[i]);
 540         if (iterator != m_markers.end())
 541             removeMarkersFromList(iterator, markerTypes);
 542     }
 543
 544     m_possiblyExistingMarkerTypes.remove(markerTypes);
 545 }
 546
 547 void DocumentMarkerController::removeMarkersFromList(MarkerMap::iterator iterator, DocumentMarker::MarkerTypes markerTypes)
 548 {
 549     bool needsRepainting = false;
 550     bool nodeCanBeRemoved;
 551
 552     size_t emptyListsCount = 0;
 553     if (markerTypes == DocumentMarker::AllMarkers()) {
 554         needsRepainting = true;
 555         nodeCanBeRemoved = true;
 556     } else {
 557         MarkerLists* markers = iterator->value.get();
 558
 559         for (size_t markerListIndex = 0; markerListIndex < DocumentMarker::MarkerTypeIndexesCount; ++markerListIndex) {
 560             OwnPtrWillBeMember<MarkerList>& list = (*markers)[markerListIndex];
 561             if (!list || list->isEmpty()) {
 562                 if (list.get() && list->isEmpty())
 563                     list.clear();
 564                 ++emptyListsCount;
 565                 continue;
 566             }
 567             if (markerTypes.contains((*list->begin())->type())) {
 568                 list->clear();
 569                 list.clear();
 570                 ++emptyListsCount;
 571                 needsRepainting = true;
 572             }
 573         }
 574
 575         nodeCanBeRemoved = emptyListsCount == DocumentMarker::MarkerTypeIndexesCount;
 576     }
 577
 578     if (needsRepainting) {
 579         if (RenderObject* renderer = iterator->key->renderer())
 580             renderer->setShouldDoFullPaintInvalidation();
 581     }
 582
 583     if (nodeCanBeRemoved) {
 584         m_markers.remove(iterator);
 585         if (m_markers.isEmpty())
 586             m_possiblyExistingMarkerTypes = 0;
 587     }
 588 }
 589
 590 void DocumentMarkerController::repaintMarkers(DocumentMarker::MarkerTypes markerTypes)
 591 {
 592     if (!possiblyHasMarkers(markerTypes))
 593         return;
 594     ASSERT(!m_markers.isEmpty());
 595
 596     // outer loop: process each markered node in the document
 597     MarkerMap::iterator end = m_markers.end();
 598     for (MarkerMap::iterator i = m_markers.begin(); i != end; ++i) {
 599         const Node* node = i->key;
 600
 601         // inner loop: process each marker in the current node
 602         MarkerLists* markers = i->value.get();
 603         for (size_t markerListIndex = 0; markerListIndex < DocumentMarker::MarkerTypeIndexesCount; ++markerListIndex) {
 604             OwnPtrWillBeMember<MarkerList>& list = (*markers)[markerListIndex];
 605             if (!list || list->isEmpty() || !markerTypes.contains((*list->begin())->type()))
 606                 continue;
 607
 608             // cause the node to be redrawn
 609             if (RenderObject* renderer = node->renderer()) {
 610                 renderer->setShouldDoFullPaintInvalidation();
 611                 break;
 612             }
 613         }
 614     }
 615 }
 616
 617 void DocumentMarkerController::invalidateRenderedRectsForMarkersInRect(const LayoutRect& r)
 618 {
 619     // outer loop: process each markered node in the document
 620     MarkerMap::iterator end = m_markers.end();
 621     for (MarkerMap::iterator i = m_markers.begin(); i != end; ++i) {
 622
 623         // inner loop: process each rect in the current node
 624         MarkerLists* markers = i->value.get();
 625         for (size_t markerListIndex = 0; markerListIndex < DocumentMarker::MarkerTypeIndexesCount; ++markerListIndex) {
 626             OwnPtrWillBeMember<MarkerList>& list = (*markers)[markerListIndex];
 627             for (size_t markerIndex = 0; list.get() && markerIndex < list->size(); ++markerIndex)
 628                 list->at(markerIndex)->invalidate(r);
 629         }
 630     }
 631 }
 632
 633 void DocumentMarkerController::shiftMarkers(Node* node, unsigned startOffset, int delta)
 634 {
 635     if (!possiblyHasMarkers(DocumentMarker::AllMarkers()))
 636         return;
 637     ASSERT(!m_markers.isEmpty());
 638
 639     MarkerLists* markers = m_markers.get(node);
 640     if (!markers)
 641         return;
 642
 643     bool docDirty = false;
 644     for (size_t markerListIndex = 0; markerListIndex < DocumentMarker::MarkerTypeIndexesCount; ++markerListIndex) {
 645         OwnPtrWillBeMember<MarkerList>& list = (*markers)[markerListIndex];
 646         if (!list)
 647             continue;
 648         MarkerList::iterator startPos = std::lower_bound(list->begin(), list->end(), startOffset, startsAfter);
 649         for (MarkerList::iterator marker = startPos; marker != list->end(); ++marker) {
 650 #if ENABLE(ASSERT)
 651             int startOffset = (*marker)->startOffset();
 652             ASSERT(startOffset + delta >= 0);
 653 #endif
 654             (*marker)->shiftOffsets(delta);
 655             docDirty = true;
 656
 657             // Marker moved, so previously-computed rendered rectangle is now invalid
 658             (*marker)->invalidate();
 659         }
 660     }
 661
 662     // repaint the affected node
 663     if (docDirty && node->renderer())
 664         node->renderer()->setShouldDoFullPaintInvalidation();
 665 }
 666
 667 void DocumentMarkerController::setMarkersActive(Range* range, bool active)
 668 {
 669     if (!possiblyHasMarkers(DocumentMarker::AllMarkers()))
 670         return;
 671     ASSERT(!m_markers.isEmpty());
 672
 673     Node* startContainer = range->startContainer();
 674     Node* endContainer = range->endContainer();
 675
 676     Node* pastLastNode = range->pastLastNode();
 677
 678     for (Node* node = range->firstNode(); node != pastLastNode; node = NodeTraversal::next(*node)) {
 679         int startOffset = node == startContainer ? range->startOffset() : 0;
 680         int endOffset = node == endContainer ? range->endOffset() : INT_MAX;
 681         setMarkersActive(node, startOffset, endOffset, active);
 682     }
 683 }
 684
 685 void DocumentMarkerController::setMarkersActive(Node* node, unsigned startOffset, unsigned endOffset, bool active)
 686 {
 687     MarkerLists* markers = m_markers.get(node);
 688     if (!markers)
 689         return;
 690
 691     bool docDirty = false;
 692     OwnPtrWillBeMember<MarkerList>& list = (*markers)[MarkerTypeToMarkerIndex(DocumentMarker::TextMatch)];
 693     if (!list)
 694         return;
 695     MarkerList::iterator startPos = std::upper_bound(list->begin(), list->end(), startOffset, endsBefore);
 696     for (MarkerList::iterator marker = startPos; marker != list->end(); ++marker) {
 697
 698         // Markers are returned in order, so stop if we are now past the specified range.
 699         if ((*marker)->startOffset() >= endOffset)
 700             break;
 701
 702         (*marker)->setActiveMatch(active);
 703         docDirty = true;
 704     }
 705
 706     // repaint the affected node
 707     if (docDirty && node->renderer())
 708         node->renderer()->setShouldDoFullPaintInvalidation();
 709 }
 710
 711 bool DocumentMarkerController::hasMarkers(Range* range, DocumentMarker::MarkerTypes markerTypes)
 712 {
 713     if (!possiblyHasMarkers(markerTypes))
 714         return false;
 715     ASSERT(!m_markers.isEmpty());
 716
 717     Node* startContainer = range->startContainer();
 718     ASSERT(startContainer);
 719     Node* endContainer = range->endContainer();
 720     ASSERT(endContainer);
 721
 722     Node* pastLastNode = range->pastLastNode();
 723     for (Node* node = range->firstNode(); node != pastLastNode; node = NodeTraversal::next(*node)) {
 724         DocumentMarkerVector markers = markersFor(node);
 725         DocumentMarkerVector::const_iterator end = markers.end();
 726         for (DocumentMarkerVector::const_iterator it = markers.begin(); it != end; ++it) {
 727             DocumentMarker* marker = *it;
 728             if (!markerTypes.contains(marker->type()))
 729                 continue;
 730             if (node == startContainer && marker->endOffset() <= static_cast<unsigned>(range->startOffset()))
 731                 continue;
 732             if (node == endContainer && marker->startOffset() >= static_cast<unsigned>(range->endOffset()))
 733                 continue;
 734             return true;
 735         }
 736     }
 737     return false;
 738 }
 739
 740 #ifndef NDEBUG
 741 void DocumentMarkerController::showMarkers() const
 742 {
 743     fprintf(stderr, "%d nodes have markers:\n", m_markers.size());
 744     MarkerMap::const_iterator end = m_markers.end();
 745     for (MarkerMap::const_iterator nodeIterator = m_markers.begin(); nodeIterator != end; ++nodeIterator) {
 746         const Node* node = nodeIterator->key;
 747         fprintf(stderr, "%p", node);
 748         MarkerLists* markers = m_markers.get(node);
 749         for (size_t markerListIndex = 0; markerListIndex < DocumentMarker::MarkerTypeIndexesCount; ++markerListIndex) {
 750             OwnPtrWillBeMember<MarkerList>& list = (*markers)[markerListIndex];
 751             for (unsigned markerIndex = 0; list.get() && markerIndex < list->size(); ++markerIndex) {
 752                 DocumentMarker* marker = list->at(markerIndex).get();
 753                 fprintf(stderr, " %d:[%d:%d](%d)", marker->type(), marker->startOffset(), marker->endOffset(), marker->activeMatch());
 754             }
 755         }
 756
 757         fprintf(stderr, "\n");
 758     }
 759 }
 760 #endif
 761
 762 } // namespace blink
 763
 764 #ifndef NDEBUG
 765 void showDocumentMarkers(const blink::DocumentMarkerController* controller)
 766 {
 767     if (controller)
 768         controller->showMarkers();
 769 }
 770 #endif