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