Reversion should not be marked as misspelled.
[WebKit.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 "Node.h"
31 #include "Range.h"
32 #include "TextIterator.h"
33
34 namespace WebCore {
35
36 static IntRect placeholderRectForMarker()
37 {
38     return IntRect(-1, -1, -1, -1);
39 }
40
41 void DocumentMarkerController::detach()
42 {
43     if (m_markers.isEmpty())
44         return;
45     deleteAllValues(m_markers);
46     m_markers.clear();
47 }
48
49 void DocumentMarkerController::addMarker(Range* range, DocumentMarker::MarkerType type, String description)
50 {
51     // Use a TextIterator to visit the potentially multiple nodes the range covers.
52     for (TextIterator markedText(range); !markedText.atEnd(); markedText.advance()) {
53         RefPtr<Range> textPiece = markedText.range();
54         int exception = 0;
55         DocumentMarker marker = {type, textPiece->startOffset(exception), textPiece->endOffset(exception), description, false};
56         addMarker(textPiece->startContainer(exception), marker);
57     }
58 }
59
60 void DocumentMarkerController::removeMarkers(Range* range, DocumentMarker::MarkerTypes markerTypes, RemovePartiallyOverlappingMarkerOrNot shouldRemovePartiallyOverlappingMarker)
61 {
62     if (m_markers.isEmpty())
63         return;
64
65     for (TextIterator markedText(range); !markedText.atEnd(); markedText.advance()) {
66         RefPtr<Range> textPiece = markedText.range();
67         int startOffset = textPiece->startOffset();
68         int endOffset = textPiece->endOffset();
69         removeMarkers(textPiece->startContainer(), startOffset, endOffset - startOffset, markerTypes, shouldRemovePartiallyOverlappingMarker);
70     }
71 }
72
73 // Markers are stored in order sorted by their start offset.
74 // Markers of the same type do not overlap each other.
75
76 void DocumentMarkerController::addMarker(Node* node, DocumentMarker newMarker) 
77 {
78     ASSERT(newMarker.endOffset >= newMarker.startOffset);
79     if (newMarker.endOffset == newMarker.startOffset)
80         return;
81
82     MarkerMapVectorPair* vectorPair = m_markers.get(node);
83
84     if (!vectorPair) {
85         vectorPair = new MarkerMapVectorPair;
86         vectorPair->first.append(newMarker);
87         vectorPair->second.append(placeholderRectForMarker());
88         m_markers.set(node, vectorPair);
89     } else {
90         Vector<DocumentMarker>& markers = vectorPair->first;
91         Vector<IntRect>& rects = vectorPair->second;
92         size_t numMarkers = markers.size();
93         ASSERT(numMarkers == rects.size());
94         size_t i;
95         // Iterate over all markers whose start offset is less than or equal to the new marker's.
96         // If one of them is of the same type as the new marker and touches it or intersects with it
97         // (there is at most one), remove it and adjust the new marker's start offset to encompass it.
98         for (i = 0; i < numMarkers; ++i) {
99             DocumentMarker marker = markers[i];
100             if (marker.startOffset > newMarker.startOffset)
101                 break;
102             if (marker.type == newMarker.type && marker.endOffset >= newMarker.startOffset) {
103                 newMarker.startOffset = marker.startOffset;
104                 markers.remove(i);
105                 rects.remove(i);
106                 numMarkers--;
107                 break;
108             }
109         }
110         size_t j = i;
111         // Iterate over all markers whose end offset is less than or equal to the new marker's,
112         // removing markers of the same type as the new marker which touch it or intersect with it,
113         // adjusting the new marker's end offset to cover them if necessary.
114         while (j < numMarkers) {
115             DocumentMarker marker = markers[j];
116             if (marker.startOffset > newMarker.endOffset)
117                 break;
118             if (marker.type == newMarker.type) {
119                 markers.remove(j);
120                 rects.remove(j);
121                 if (newMarker.endOffset <= marker.endOffset) {
122                     newMarker.endOffset = marker.endOffset;
123                     break;
124                 }
125                 numMarkers--;
126             } else
127                 j++;
128         }
129         // At this point i points to the node before which we want to insert.
130         markers.insert(i, newMarker);
131         rects.insert(i, placeholderRectForMarker());
132     }
133
134     // repaint the affected node
135     if (node->renderer())
136         node->renderer()->repaint();
137 }
138
139 // copies markers from srcNode to dstNode, applying the specified shift delta to the copies.  The shift is
140 // useful if, e.g., the caller has created the dstNode from a non-prefix substring of the srcNode.
141 void DocumentMarkerController::copyMarkers(Node* srcNode, unsigned startOffset, int length, Node* dstNode, int delta, DocumentMarker::MarkerType markerType)
142 {
143     if (length <= 0)
144         return;
145
146     MarkerMapVectorPair* vectorPair = m_markers.get(srcNode);
147     if (!vectorPair)
148         return;
149
150     ASSERT(vectorPair->first.size() == vectorPair->second.size());
151
152     bool docDirty = false;
153     unsigned endOffset = startOffset + length - 1;
154     Vector<DocumentMarker>& markers = vectorPair->first;
155     for (size_t i = 0; i != markers.size(); ++i) {
156         DocumentMarker marker = markers[i];
157
158         // stop if we are now past the specified range
159         if (marker.startOffset > endOffset)
160             break;
161
162         // skip marker that is before the specified range or is the wrong type
163         if (marker.endOffset < startOffset || (marker.type != markerType && markerType != DocumentMarker::AllMarkers))
164             continue;
165
166         // pin the marker to the specified range and apply the shift delta
167         docDirty = true;
168         if (marker.startOffset < startOffset)
169             marker.startOffset = startOffset;
170         if (marker.endOffset > endOffset)
171             marker.endOffset = endOffset;
172         marker.startOffset += delta;
173         marker.endOffset += delta;
174
175         addMarker(dstNode, marker);
176     }
177
178     // repaint the affected node
179     if (docDirty && dstNode->renderer())
180         dstNode->renderer()->repaint();
181 }
182
183 void DocumentMarkerController::removeMarkers(Node* node, unsigned startOffset, int length, DocumentMarker::MarkerTypes markerTypes, RemovePartiallyOverlappingMarkerOrNot shouldRemovePartiallyOverlappingMarker)
184 {
185     if (length <= 0)
186         return;
187
188     MarkerMapVectorPair* vectorPair = m_markers.get(node);
189     if (!vectorPair)
190         return;
191
192     Vector<DocumentMarker>& markers = vectorPair->first;
193     Vector<IntRect>& rects = vectorPair->second;
194     ASSERT(markers.size() == rects.size());
195     bool docDirty = false;
196     unsigned endOffset = startOffset + length;
197     for (size_t i = 0; i < markers.size();) {
198         DocumentMarker marker = markers[i];
199
200         // markers are returned in order, so stop if we are now past the specified range
201         if (marker.startOffset >= endOffset)
202             break;
203
204         // skip marker that is wrong type or before target
205         if (marker.endOffset <= startOffset || !(marker.type & markerTypes)) {
206             i++;
207             continue;
208         }
209
210         // at this point we know that marker and target intersect in some way
211         docDirty = true;
212
213         // pitch the old marker and any associated rect
214         markers.remove(i);
215         rects.remove(i);
216
217         if (shouldRemovePartiallyOverlappingMarker)
218             // Stop here. Don't add resulting slices back.
219             continue;
220
221         // add either of the resulting slices that are left after removing target
222         if (startOffset > marker.startOffset) {
223             DocumentMarker newLeft = marker;
224             newLeft.endOffset = startOffset;
225             markers.insert(i, newLeft);
226             rects.insert(i, placeholderRectForMarker());
227             // i now points to the newly-inserted node, but we want to skip that one
228             i++;
229         }
230         if (marker.endOffset > endOffset) {
231             DocumentMarker newRight = marker;
232             newRight.startOffset = endOffset;
233             markers.insert(i, newRight);
234             rects.insert(i, placeholderRectForMarker());
235             // i now points to the newly-inserted node, but we want to skip that one
236             i++;
237         }
238     }
239
240     if (markers.isEmpty()) {
241         ASSERT(rects.isEmpty());
242         m_markers.remove(node);
243         delete vectorPair;
244     }
245
246     // repaint the affected node
247     if (docDirty && node->renderer())
248         node->renderer()->repaint();
249 }
250
251 DocumentMarker* DocumentMarkerController::markerContainingPoint(const IntPoint& point, DocumentMarker::MarkerType markerType)
252 {
253     // outer loop: process each node that contains any markers
254     MarkerMap::iterator end = m_markers.end();
255     for (MarkerMap::iterator nodeIterator = m_markers.begin(); nodeIterator != end; ++nodeIterator) {
256         // inner loop; process each marker in this node
257         MarkerMapVectorPair* vectorPair = nodeIterator->second;
258         Vector<DocumentMarker>& markers = vectorPair->first;
259         Vector<IntRect>& rects = vectorPair->second;
260         ASSERT(markers.size() == rects.size());
261         unsigned markerCount = markers.size();
262         for (unsigned markerIndex = 0; markerIndex < markerCount; ++markerIndex) {
263             DocumentMarker& marker = markers[markerIndex];
264
265             // skip marker that is wrong type
266             if (marker.type != markerType && markerType != DocumentMarker::AllMarkers)
267                 continue;
268
269             IntRect& r = rects[markerIndex];
270
271             // skip placeholder rects
272             if (r == placeholderRectForMarker())
273                 continue;
274
275             if (r.contains(point))
276                 return &marker;
277         }
278     }
279
280     return 0;
281 }
282
283 Vector<DocumentMarker> DocumentMarkerController::markersForNode(Node* node)
284 {
285     MarkerMapVectorPair* vectorPair = m_markers.get(node);
286     if (vectorPair)
287         return vectorPair->first;
288     return Vector<DocumentMarker>();
289 }
290
291 Vector<IntRect> DocumentMarkerController::renderedRectsForMarkers(DocumentMarker::MarkerType markerType)
292 {
293     Vector<IntRect> result;
294
295     // outer loop: process each node
296     MarkerMap::iterator end = m_markers.end();
297     for (MarkerMap::iterator nodeIterator = m_markers.begin(); nodeIterator != end; ++nodeIterator) {
298         // inner loop; process each marker in this node
299         MarkerMapVectorPair* vectorPair = nodeIterator->second;
300         Vector<DocumentMarker>& markers = vectorPair->first;
301         Vector<IntRect>& rects = vectorPair->second;
302         ASSERT(markers.size() == rects.size());
303         unsigned markerCount = markers.size();
304         for (unsigned markerIndex = 0; markerIndex < markerCount; ++markerIndex) {
305             DocumentMarker marker = markers[markerIndex];
306
307             // skip marker that is wrong type
308             if (marker.type != markerType && markerType != DocumentMarker::AllMarkers)
309                 continue;
310
311             IntRect r = rects[markerIndex];
312             // skip placeholder rects
313             if (r == placeholderRectForMarker())
314                 continue;
315
316             result.append(r);
317         }
318     }
319
320     return result;
321 }
322
323 void DocumentMarkerController::removeMarkers(Node* node, DocumentMarker::MarkerTypes markerTypes)
324 {
325     MarkerMap::iterator iterator = m_markers.find(node);
326     if (iterator != m_markers.end())
327         removeMarkersFromMarkerMapVectorPair(node, iterator->second, markerTypes);
328 }
329
330 void DocumentMarkerController::removeMarkers(DocumentMarker::MarkerTypes markerTypes)
331 {
332     // outer loop: process each markered node in the document
333     MarkerMap markerMapCopy = m_markers;
334     MarkerMap::iterator end = markerMapCopy.end();
335     for (MarkerMap::iterator i = markerMapCopy.begin(); i != end; ++i) {
336         Node* node = i->first.get();
337         MarkerMapVectorPair* vectorPair = i->second;
338         removeMarkersFromMarkerMapVectorPair(node, vectorPair, markerTypes);
339     }
340 }
341
342 // This function may release node and vectorPair.
343 void DocumentMarkerController::removeMarkersFromMarkerMapVectorPair(Node* node, MarkerMapVectorPair* vectorPair, DocumentMarker::MarkerTypes markerTypes)
344 {
345     if (!~(markerTypes & DocumentMarker::AllMarkers)) {
346         delete vectorPair;
347         m_markers.remove(node);
348         if (RenderObject* renderer = node->renderer())
349             renderer->repaint();
350     } else {
351         bool needsRepaint = false;
352         Vector<DocumentMarker>& markers = vectorPair->first;
353         Vector<IntRect>& rects = vectorPair->second;
354         ASSERT(markers.size() == rects.size());
355         for (size_t i = 0; i != markers.size();) {
356             DocumentMarker marker = markers[i];
357
358             // skip nodes that are not of the specified type
359             if (!(marker.type & markerTypes)) {
360                 ++i;
361                 continue;
362             }
363
364             // pitch the old marker
365             markers.remove(i);
366             rects.remove(i);
367             needsRepaint = true;
368             // i now is the index of the next marker
369         }
370
371         // Redraw the node if it changed. Do this before the node is removed from m_markers, since
372         // m_markers might contain the last reference to the node.
373         if (needsRepaint) {
374             RenderObject* renderer = node->renderer();
375             if (renderer)
376                 renderer->repaint();
377         }
378
379         // delete the node's list if it is now empty
380         if (markers.isEmpty()) {
381             ASSERT(rects.isEmpty());
382             m_markers.remove(node);
383             delete vectorPair;
384         }
385     }
386 }
387
388 void DocumentMarkerController::repaintMarkers(DocumentMarker::MarkerType markerType)
389 {
390     // outer loop: process each markered node in the document
391     MarkerMap::iterator end = m_markers.end();
392     for (MarkerMap::iterator i = m_markers.begin(); i != end; ++i) {
393         Node* node = i->first.get();
394
395         // inner loop: process each marker in the current node
396         MarkerMapVectorPair* vectorPair = i->second;
397         Vector<DocumentMarker>& markers = vectorPair->first;
398         bool nodeNeedsRepaint = false;
399         for (size_t i = 0; i != markers.size(); ++i) {
400             DocumentMarker marker = markers[i];
401
402             // skip nodes that are not of the specified type
403             if (marker.type == markerType || markerType == DocumentMarker::AllMarkers) {
404                 nodeNeedsRepaint = true;
405                 break;
406             }
407         }
408
409         if (!nodeNeedsRepaint)
410             continue;
411
412         // cause the node to be redrawn
413         if (RenderObject* renderer = node->renderer())
414             renderer->repaint();
415     }
416 }
417
418 void DocumentMarkerController::setRenderedRectForMarker(Node* node, const DocumentMarker& marker, const IntRect& r)
419 {
420     MarkerMapVectorPair* vectorPair = m_markers.get(node);
421     if (!vectorPair) {
422         ASSERT_NOT_REACHED(); // shouldn't be trying to set the rect for a marker we don't already know about
423         return;
424     }
425
426     Vector<DocumentMarker>& markers = vectorPair->first;
427     ASSERT(markers.size() == vectorPair->second.size());
428     unsigned markerCount = markers.size();
429     for (unsigned markerIndex = 0; markerIndex < markerCount; ++markerIndex) {
430         DocumentMarker m = markers[markerIndex];
431         if (m == marker) {
432             vectorPair->second[markerIndex] = r;
433             return;
434         }
435     }
436
437     ASSERT_NOT_REACHED(); // shouldn't be trying to set the rect for a marker we don't already know about
438 }
439
440 void DocumentMarkerController::invalidateRenderedRectsForMarkersInRect(const IntRect& r)
441 {
442     // outer loop: process each markered node in the document
443     MarkerMap::iterator end = m_markers.end();
444     for (MarkerMap::iterator i = m_markers.begin(); i != end; ++i) {
445
446         // inner loop: process each rect in the current node
447         MarkerMapVectorPair* vectorPair = i->second;
448         Vector<IntRect>& rects = vectorPair->second;
449
450         unsigned rectCount = rects.size();
451         for (unsigned rectIndex = 0; rectIndex < rectCount; ++rectIndex)
452             if (rects[rectIndex].intersects(r))
453                 rects[rectIndex] = placeholderRectForMarker();
454     }
455 }
456
457 void DocumentMarkerController::shiftMarkers(Node* node, unsigned startOffset, int delta, DocumentMarker::MarkerType markerType)
458 {
459     MarkerMapVectorPair* vectorPair = m_markers.get(node);
460     if (!vectorPair)
461         return;
462
463     Vector<DocumentMarker>& markers = vectorPair->first;
464     Vector<IntRect>& rects = vectorPair->second;
465     ASSERT(markers.size() == rects.size());
466
467     bool docDirty = false;
468     for (size_t i = 0; i != markers.size(); ++i) {
469         DocumentMarker& marker = markers[i];
470         if (marker.startOffset >= startOffset && (markerType == DocumentMarker::AllMarkers || marker.type == markerType)) {
471             ASSERT((int)marker.startOffset + delta >= 0);
472             marker.startOffset += delta;
473             marker.endOffset += delta;
474             docDirty = true;
475
476             // Marker moved, so previously-computed rendered rectangle is now invalid
477             rects[i] = placeholderRectForMarker();
478         }
479     }
480
481     // repaint the affected node
482     if (docDirty && node->renderer())
483         node->renderer()->repaint();
484 }
485
486 void DocumentMarkerController::setMarkersActive(Range* range, bool active)
487 {
488     if (m_markers.isEmpty())
489         return;
490
491     ExceptionCode ec = 0;
492     Node* startContainer = range->startContainer(ec);
493     Node* endContainer = range->endContainer(ec);
494
495     Node* pastLastNode = range->pastLastNode();
496     for (Node* node = range->firstNode(); node != pastLastNode; node = node->traverseNextNode()) {
497         int startOffset = node == startContainer ? range->startOffset(ec) : 0;
498         int endOffset = node == endContainer ? range->endOffset(ec) : INT_MAX;
499         setMarkersActive(node, startOffset, endOffset, active);
500     }
501 }
502
503 void DocumentMarkerController::setMarkersActive(Node* node, unsigned startOffset, unsigned endOffset, bool active)
504 {
505     MarkerMapVectorPair* vectorPair = m_markers.get(node);
506     if (!vectorPair)
507         return;
508
509     Vector<DocumentMarker>& markers = vectorPair->first;
510     ASSERT(markers.size() == vectorPair->second.size());
511
512     bool docDirty = false;
513     for (size_t i = 0; i != markers.size(); ++i) {
514         DocumentMarker& marker = markers[i];
515
516         // Markers are returned in order, so stop if we are now past the specified range.
517         if (marker.startOffset >= endOffset)
518             break;
519
520         // Skip marker that is wrong type or before target.
521         if (marker.endOffset < startOffset || marker.type != DocumentMarker::TextMatch)
522             continue;
523
524         marker.activeMatch = active;
525         docDirty = true;
526     }
527
528     // repaint the affected node
529     if (docDirty && node->renderer())
530         node->renderer()->repaint();
531 }
532
533 bool DocumentMarkerController::hasMarkers(Range* range, DocumentMarker::MarkerTypes markerTypes)
534 {
535     if (m_markers.isEmpty())
536         return false;
537
538     Node* startContainer = range->startContainer();
539     ASSERT(startContainer);
540     Node* endContainer = range->endContainer();
541     ASSERT(endContainer);
542
543     Node* pastLastNode = range->pastLastNode();
544     for (Node* node = range->firstNode(); node != pastLastNode; node = node->traverseNextNode()) {
545         Vector<DocumentMarker> markers = markersForNode(node);
546         Vector<DocumentMarker>::const_iterator end = markers.end();
547         for (Vector<DocumentMarker>::const_iterator it = markers.begin(); it != end; ++it) {
548             if (!(markerTypes & it->type))
549                 continue;
550             if (node == startContainer && node == endContainer) {
551                 // The range spans only one node.
552                 if (it->endOffset > static_cast<unsigned>(range->startOffset()) && it->startOffset < static_cast<unsigned>(range->endOffset()))
553                     return true;
554             } else {
555                 if (node == startContainer) {
556                     if (it->endOffset > static_cast<unsigned>(range->startOffset()))
557                         return true;
558                 } else if (node == endContainer) {
559                     if (it->startOffset < static_cast<unsigned>(range->endOffset()))
560                         return true;
561                 } else
562                     return true;
563             }
564         }
565     }
566     return false;
567 }
568 #ifndef NDEBUG
569 void DocumentMarkerController::showMarkers() const
570 {
571     fprintf(stderr, "%d nodes have markers:\n", m_markers.size());
572     MarkerMap::const_iterator end = m_markers.end();
573     for (MarkerMap::const_iterator nodeIterator = m_markers.begin(); nodeIterator != end; ++nodeIterator) {
574         Node* node = nodeIterator->first.get();
575         fprintf(stderr, "%p", node);
576         MarkerMapVectorPair* vectorPair = nodeIterator->second;
577         Vector<DocumentMarker>& markers = vectorPair->first;
578         unsigned markerCount = markers.size();
579         for (unsigned markerIndex = 0; markerIndex < markerCount; ++markerIndex)
580             fprintf(stderr, " %d:[%d:%d](%d)", markers[markerIndex].type, markers[markerIndex].startOffset, markers[markerIndex].endOffset, markers[markerIndex].activeMatch);
581         fprintf(stderr, "\n");
582     }
583 }
584 #endif
585
586 } // namespace WebCore
587
588
589 #ifndef NDEBUG
590 void showDocumentMarkers(const WebCore::DocumentMarkerController* controller)
591 {
592     if (controller)
593         controller->showMarkers();
594 }
595 #endif