Reviewed by John
[WebKit-https.git] / WebCore / khtml / editing / selection.cpp
1 /*
2  * Copyright (C) 2004 Apple Computer, Inc.  All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE COMPUTER, INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
24  */
25   
26 #include "selection.h"
27
28 #include <qevent.h>
29 #include <qpainter.h>
30 #include <qrect.h>
31
32 #include "dom/dom_node.h"
33 #include "dom/dom_string.h"
34 #include "khtml_part.h"
35 #include "khtmlview.h"
36 #include "misc/htmltags.h"
37 #include "rendering/render_object.h"
38 #include "rendering/render_style.h"
39 #include "rendering/render_text.h"
40 #include "visible_position.h"
41 #include "visible_units.h"
42 #include "xml/dom_docimpl.h"
43 #include "xml/dom_elementimpl.h"
44 #include "xml/dom_nodeimpl.h"
45 #include "xml/dom_positioniterator.h"
46 #include "xml/dom_textimpl.h"
47 #include "xml/dom2_rangeimpl.h"
48
49 #if APPLE_CHANGES
50 #include "KWQAssertions.h"
51 #else
52 #define ASSERT(assertion) assert(assertion)
53 #endif
54
55 #define EDIT_DEBUG 0
56
57 using DOM::DOMString;
58 using DOM::ElementImpl;
59 using DOM::Node;
60 using DOM::NodeImpl;
61 using DOM::Position;
62 using DOM::Range;
63 using DOM::RangeImpl;
64 using DOM::StayInBlock;
65
66 namespace khtml {
67
68 static Selection selectionForLine(const Position &position, EAffinity affinity);
69
70 Selection::Selection()
71 {
72     init();
73 }
74
75 Selection::Selection(const Position &pos)
76     : m_base(pos), m_extent(pos)
77 {
78     init();
79     validate();
80 }
81
82 Selection::Selection(const Range &r)
83     : m_base(startPosition(r)), m_extent(endPosition(r))
84 {
85     init();
86     validate();
87 }
88
89 Selection::Selection(const Position &base, const Position &extent)
90     : m_base(base), m_extent(extent)
91 {
92     init();
93     validate();
94 }
95
96 Selection::Selection(const VisiblePosition &base, const VisiblePosition &extent)
97     : m_base(base.position()), m_extent(extent.position())
98 {
99     init();
100     validate();
101 }
102
103 Selection::Selection(const Selection &o)
104     : m_base(o.m_base), m_extent(o.m_extent)
105     , m_start(o.m_start), m_end(o.m_end)
106     , m_state(o.m_state), m_affinity(o.m_affinity)
107     , m_baseIsStart(o.m_baseIsStart)
108     , m_needsLayout(o.m_needsLayout)
109     , m_modifyBiasSet(o.m_modifyBiasSet)
110 {
111     // Only copy the coordinates over if the other object
112     // has had a layout, otherwise keep the current
113     // coordinates. This prevents drawing artifacts from
114     // remaining when the caret is painted and then moves,
115     // and the old rectangle needs to be repainted.
116     if (!m_needsLayout) {
117         m_caretRect = o.m_caretRect;
118         m_expectedVisibleRect = o.m_expectedVisibleRect;
119     }
120 }
121
122 void Selection::init()
123 {
124     m_state = NONE; 
125     m_affinity = UPSTREAM;
126     m_baseIsStart = true;
127     m_needsLayout = true;
128     m_modifyBiasSet = false;
129 }
130
131 Selection &Selection::operator=(const Selection &o)
132 {
133     m_base = o.m_base;
134     m_extent = o.m_extent;
135     m_start = o.m_start;
136     m_end = o.m_end;
137
138     m_state = o.m_state;
139     m_affinity = o.m_affinity;
140
141     m_baseIsStart = o.m_baseIsStart;
142     m_needsLayout = o.m_needsLayout;
143     m_modifyBiasSet = o.m_modifyBiasSet;
144     
145     // Only copy the coordinates over if the other object
146     // has had a layout, otherwise keep the current
147     // coordinates. This prevents drawing artifacts from
148     // remaining when the caret is painted and then moves,
149     // and the old rectangle needs to be repainted.
150     if (!m_needsLayout) {
151         m_caretRect = o.m_caretRect;
152         m_expectedVisibleRect = o.m_expectedVisibleRect;
153     }
154     
155     return *this;
156 }
157
158 void Selection::setAffinity(EAffinity affinity)
159 {
160     if (affinity == m_affinity)
161         return;
162         
163     m_affinity = affinity;
164     setNeedsLayout();
165 }
166
167 void Selection::modifyAffinity(EAlter alter, EDirection dir, ETextGranularity granularity)
168 {
169     switch (granularity) {
170         case CHARACTER:
171         case WORD:
172             m_affinity = DOWNSTREAM;
173             break;
174         case PARAGRAPH:
175         case LINE:
176             if (dir == BACKWARD || dir == LEFT)
177                 m_affinity = UPSTREAM;
178             break;
179         case PARAGRAPH_BOUNDARY:
180         case DOCUMENT_BOUNDARY:
181             // These granularities should not change affinity.
182             break;
183         case LINE_BOUNDARY: {
184             // When extending, leave affinity unchanged.
185             if (alter == MOVE) {
186                 switch (dir) {
187                     case FORWARD:
188                     case RIGHT:
189                         m_affinity = UPSTREAM;
190                         break;
191                     case BACKWARD:
192                     case LEFT:
193                         m_affinity = DOWNSTREAM;
194                         break;
195                 }
196             }
197             break;
198         }
199     }
200     setNeedsLayout();
201 }
202
203 void Selection::moveTo(const Range &r)
204 {
205     m_affinity = UPSTREAM;
206     m_base = startPosition(r);
207     m_extent = endPosition(r);
208     validate();
209 }
210
211 void Selection::moveTo(const Selection &o)
212 {
213     m_affinity = UPSTREAM;
214     m_base = o.m_start;
215     m_extent = o.m_end;
216     validate();
217 }
218
219 void Selection::moveTo(const Position &pos)
220 {
221     m_affinity = UPSTREAM;
222     m_base = pos;
223     m_extent = pos;
224     validate();
225 }
226
227 void Selection::moveTo(const Position &base, const Position &extent)
228 {
229     m_affinity = UPSTREAM;
230     m_base = base;
231     m_extent = extent;
232     validate();
233 }
234
235 void Selection::setModifyBias(EAlter alter, EDirection direction)
236 {
237     switch (alter) {
238         case MOVE:
239             m_modifyBiasSet = false;
240             break;
241         case EXTEND:
242             if (!m_modifyBiasSet) {
243                 m_modifyBiasSet = true;
244                 switch (direction) {
245                     // FIXME: right for bidi?
246                     case RIGHT:
247                     case FORWARD:
248                         m_base = m_start;
249                         m_extent = m_end;
250                         break;
251                     case LEFT:
252                     case BACKWARD:
253                         m_base = m_end;
254                         m_extent = m_start;
255                         break;
256                 }
257             }
258             break;
259     }
260 }
261
262 VisiblePosition Selection::modifyExtendingRightForward(ETextGranularity granularity)
263 {
264     VisiblePosition pos(m_extent);
265     switch (granularity) {
266         case CHARACTER:
267             pos = pos.next();
268             break;
269         case WORD:
270             pos = nextWordPosition(pos);
271             break;
272         case PARAGRAPH:
273             pos = nextParagraphPosition(pos, m_affinity, xPosForVerticalArrowNavigation(EXTENT));
274             break;
275         case LINE:
276             pos = nextLinePosition(pos, m_affinity, xPosForVerticalArrowNavigation(EXTENT));
277             break;
278         case LINE_BOUNDARY:
279             pos = VisiblePosition(selectionForLine(m_end, m_affinity).end());
280             break;
281         case PARAGRAPH_BOUNDARY:
282             pos = endOfParagraph(VisiblePosition(m_end));
283             break;
284         case DOCUMENT_BOUNDARY: {
285             NodeImpl *de = m_start.node()->getDocument()->documentElement();
286             pos = VisiblePosition(de, de ? de->childNodeCount() : 0);
287             break;
288         }
289     }
290     return pos;
291 }
292
293 VisiblePosition Selection::modifyMovingRightForward(ETextGranularity granularity)
294 {
295     VisiblePosition pos;
296     switch (granularity) {
297         case CHARACTER:
298             if (isRange()) 
299                 pos = VisiblePosition(m_end);
300             else
301                 pos = VisiblePosition(m_extent).next();
302             break;
303         case WORD:
304             pos = nextWordPosition(VisiblePosition(m_extent));
305             break;
306         case PARAGRAPH:
307             pos = nextParagraphPosition(VisiblePosition(m_end), m_affinity, xPosForVerticalArrowNavigation(END, isRange()));
308             break;
309         case LINE:
310             pos = nextLinePosition(VisiblePosition(m_end), m_affinity, xPosForVerticalArrowNavigation(END, isRange()));
311             break;
312         case LINE_BOUNDARY:
313             pos = VisiblePosition(selectionForLine(m_end, m_affinity).end());
314             break;
315         case PARAGRAPH_BOUNDARY:
316             pos = endOfParagraph(VisiblePosition(m_end));
317             break;
318         case DOCUMENT_BOUNDARY: {
319             NodeImpl *de = m_start.node()->getDocument()->documentElement();
320             pos = VisiblePosition(de, de ? de->childNodeCount() : 0);
321             break;
322         }
323     }
324     return pos;
325 }
326
327 VisiblePosition Selection::modifyExtendingLeftBackward(ETextGranularity granularity)
328 {
329     VisiblePosition pos(m_extent);
330     switch (granularity) {
331         case CHARACTER:
332             pos = pos.previous();
333             break;
334         case WORD:
335             pos = previousWordPosition(pos);
336             break;
337         case PARAGRAPH:
338             pos = previousParagraphPosition(pos, m_affinity, xPosForVerticalArrowNavigation(EXTENT));
339             break;
340         case LINE:
341             pos = previousLinePosition(pos, m_affinity, xPosForVerticalArrowNavigation(EXTENT));
342             break;
343         case LINE_BOUNDARY:
344             pos = VisiblePosition(selectionForLine(m_start, m_affinity).start());
345             break;
346         case PARAGRAPH_BOUNDARY:
347             pos = startOfParagraph(VisiblePosition(m_start));
348             break;
349         case DOCUMENT_BOUNDARY:
350             pos = VisiblePosition(m_start.node()->getDocument()->documentElement(), 0);
351             break;
352     }
353     return pos;
354 }
355
356 VisiblePosition Selection::modifyMovingLeftBackward(ETextGranularity granularity)
357 {
358     VisiblePosition pos;
359     switch (granularity) {
360         case CHARACTER:
361             if (isRange()) 
362                 pos = VisiblePosition(m_start);
363             else
364                 pos = VisiblePosition(m_extent).previous();
365             break;
366         case WORD:
367             pos = previousWordPosition(VisiblePosition(m_extent));
368             break;
369         case PARAGRAPH:
370             pos = previousParagraphPosition(VisiblePosition(m_start), m_affinity, xPosForVerticalArrowNavigation(START, isRange()));
371             break;
372         case LINE:
373             pos = previousLinePosition(VisiblePosition(m_start), m_affinity, xPosForVerticalArrowNavigation(START, isRange()));
374             break;
375         case LINE_BOUNDARY:
376             pos = VisiblePosition(selectionForLine(m_start, m_affinity).start());
377             break;
378         case PARAGRAPH_BOUNDARY:
379             pos = startOfParagraph(VisiblePosition(m_start));
380             break;
381         case DOCUMENT_BOUNDARY:
382             pos = VisiblePosition(m_start.node()->getDocument()->documentElement(), 0);
383             break;
384     }
385     return pos;
386 }
387
388 bool Selection::modify(EAlter alter, EDirection dir, ETextGranularity granularity)
389 {
390     setModifyBias(alter, dir);
391
392     VisiblePosition pos;
393
394     switch (dir) {
395         // EDIT FIXME: These need to handle bidi
396         case RIGHT:
397         case FORWARD:
398             if (alter == EXTEND)
399                 pos = modifyExtendingRightForward(granularity);
400             else
401                 pos = modifyMovingRightForward(granularity);
402             break;
403         case LEFT:
404         case BACKWARD:
405             if (alter == EXTEND)
406                 pos = modifyExtendingLeftBackward(granularity);
407             else
408                 pos = modifyMovingLeftBackward(granularity);
409             break;
410     }
411
412     if (pos.isNull())
413         return false;
414
415     // Save and restore affinity here before calling setAffinity. 
416     // The moveTo() and setExtent() calls reset affinity and this 
417     // is undesirable here.
418     EAffinity savedAffinity = m_affinity;
419     switch (alter) {
420         case MOVE:
421             moveTo(pos.deepEquivalent());
422             break;
423         case EXTEND:
424             setExtent(pos.deepEquivalent());
425             break;
426     }
427     m_affinity = savedAffinity;
428     modifyAffinity(alter, dir, granularity);
429
430     return true;
431 }
432
433 // FIXME: Maybe baseline would be better?
434 static bool caretY(const VisiblePosition &c, int &y)
435 {
436     Position p = c.deepEquivalent();
437     NodeImpl *n = p.node();
438     if (!n)
439         return false;
440     RenderObject *r = p.node()->renderer();
441     if (!r)
442         return false;
443     QRect rect = r->caretRect(p.offset());
444     if (rect.isEmpty())
445         return false;
446     y = rect.y() + rect.height() / 2;
447     return true;
448 }
449
450 bool Selection::modify(EAlter alter, int verticalDistance)
451 {
452     if (verticalDistance == 0)
453         return false;
454
455     bool up = verticalDistance < 0;
456     if (up)
457         verticalDistance = -verticalDistance;
458
459     m_affinity = UPSTREAM;
460     setModifyBias(alter, up ? BACKWARD : FORWARD);
461
462     VisiblePosition pos;
463     int xPos = 0; /* initialized only to make compiler happy */
464
465     switch (alter) {
466         case MOVE:
467             pos = VisiblePosition(up ? m_start : m_end);
468             xPos = xPosForVerticalArrowNavigation(up ? START : END, isRange());
469             break;
470         case EXTEND:
471             pos = VisiblePosition(m_extent);
472             xPos = xPosForVerticalArrowNavigation(EXTENT);
473             break;
474     }
475
476     int startY;
477     if (!caretY(pos, startY))
478         return false;
479     if (up)
480         startY = -startY;
481     int lastY = startY;
482
483     VisiblePosition result;
484
485     VisiblePosition next;
486     for (VisiblePosition p = pos; ; p = next) {
487         next = (up ? previousLinePosition : nextLinePosition)(p, m_affinity, xPos);
488         if (next.isNull() || next == p)
489             break;
490         int nextY;
491         if (!caretY(next, nextY))
492             break;
493         if (up)
494             nextY = -nextY;
495         if (nextY - startY > verticalDistance)
496             break;
497         if (nextY >= lastY) {
498             lastY = nextY;
499             result = next;
500         }
501     }
502
503     if (result.isNull())
504         return false;
505
506     switch (alter) {
507         case MOVE:
508             moveTo(result.deepEquivalent());
509             break;
510         case EXTEND:
511             setExtent(result.deepEquivalent());
512             break;
513     }
514
515     return true;
516 }
517
518 bool Selection::expandUsingGranularity(ETextGranularity granularity)
519 {
520     if (isNone())
521         return false;
522     validate(granularity);
523     return true;
524 }
525
526 int Selection::xPosForVerticalArrowNavigation(EPositionType type, bool recalc) const
527 {
528     int x = 0;
529
530     if (isNone())
531         return x;
532
533     Position pos;
534     switch (type) {
535         case START:
536             pos = m_start;
537             break;
538         case END:
539             pos = m_end;
540             break;
541         case BASE:
542             pos = m_base;
543             break;
544         case EXTENT:
545             pos = m_extent;
546             break;
547     }
548
549     KHTMLPart *part = pos.node()->getDocument()->part();
550     if (!part)
551         return x;
552         
553     if (recalc || part->xPosForVerticalArrowNavigation() == KHTMLPart::NoXPosForVerticalArrowNavigation) {
554         switch (m_affinity) {
555             case DOWNSTREAM:
556                 pos = VisiblePosition(pos).downstreamDeepEquivalent();
557                 break;
558             case UPSTREAM:
559                 pos = VisiblePosition(pos).deepEquivalent();
560                 break;
561         }
562         x = pos.node()->renderer()->caretRect(pos.offset(), m_affinity).x();
563         part->setXPosForVerticalArrowNavigation(x);
564     }
565     else {
566         x = part->xPosForVerticalArrowNavigation();
567     }
568     return x;
569 }
570
571 void Selection::clear()
572 {
573     m_affinity = UPSTREAM;
574     m_base.clear();
575     m_extent.clear();
576     validate();
577 }
578
579 void Selection::setBase(const Position &pos)
580 {
581     m_affinity = UPSTREAM;
582     m_base = pos;
583     validate();
584 }
585
586 void Selection::setExtent(const Position &pos)
587 {
588     m_affinity = UPSTREAM;
589     m_extent = pos;
590     validate();
591 }
592
593 void Selection::setBaseAndExtent(const Position &base, const Position &extent)
594 {
595     m_affinity = UPSTREAM;
596     m_base = base;
597     m_extent = extent;
598     validate();
599 }
600
601 void Selection::setNeedsLayout(bool flag)
602 {
603     m_needsLayout = flag;
604 }
605
606 Range Selection::toRange() const
607 {
608     if (isNone())
609         return Range();
610
611     // Make sure we have an updated layout since this function is called
612     // in the course of running edit commands which modify the DOM.
613     // Failing to call this can result in equivalentXXXPosition calls returning
614     // incorrect results.
615     m_start.node()->getDocument()->updateLayout();
616
617     Position s, e;
618     if (isCaret()) {
619         // If the selection is a caret, move the range start upstream. This helps us match
620         // the conventions of text editors tested, which make style determinations based
621         // on the character before the caret, if any. 
622         s = m_start.upstream(StayInBlock).equivalentRangeCompliantPosition();
623         e = s;
624     }
625     else {
626         // If the selection is a range, select the minimum range that encompasses the selection.
627         // Again, this is to match the conventions of text editors tested, which make style 
628         // determinations based on the first character of the selection. 
629         // For instance, this operation helps to make sure that the "X" selected below is the 
630         // only thing selected. The range should not be allowed to "leak" out to the end of the 
631         // previous text node, or to the beginning of the next text node, each of which has a 
632         // different style.
633         // 
634         // On a treasure map, <b>X</b> marks the spot.
635         //                       ^ selected
636         //
637         ASSERT(isRange());
638         s = m_start.downstream();
639         e = m_end.upstream();
640         if (RangeImpl::compareBoundaryPoints(s.node(), s.offset(), e.node(), e.offset()) > 0) {
641             // Make sure the start is before the end.
642             // The end can wind up before the start if collapsed whitespace is the only thing selected.
643             Position tmp = s;
644             s = e;
645             e = tmp;
646         }
647         s = s.equivalentRangeCompliantPosition();
648         e = e.equivalentRangeCompliantPosition();
649     }
650
651     // Use this roundabout way of creating the Range in order to have defined behavior
652     // when there is a DOM exception.
653     int exceptionCode = 0;
654     Range result(s.node()->getDocument());
655     RangeImpl *handle = result.handle();
656     ASSERT(handle);
657     handle->setStart(s.node(), s.offset(), exceptionCode);
658     if (exceptionCode) {
659         ERROR("Exception setting Range start from Selection: %d", exceptionCode);
660         return Range();
661     }
662     handle->setEnd(e.node(), e.offset(), exceptionCode);
663     if (exceptionCode) {
664         ERROR("Exception setting Range end from Selection: %d", exceptionCode);
665         return Range();
666     }
667     return result;
668 }
669
670 void Selection::layout()
671 {
672     if (isNone() || !m_start.node()->inDocument() || !m_end.node()->inDocument()) {
673         m_caretRect = QRect();
674         m_expectedVisibleRect = QRect();
675         return;
676     }
677
678     m_start.node()->getDocument()->updateRendering();
679         
680     if (isCaret()) {
681         Position pos = m_start;
682         switch (m_affinity) {
683             case DOWNSTREAM:
684                 pos = VisiblePosition(m_start).downstreamDeepEquivalent();
685                 break;
686             case UPSTREAM:
687                 pos = VisiblePosition(m_start).deepEquivalent();
688                 break;
689         }
690         if (pos.isNotNull()) {
691             ASSERT(pos.node()->renderer());
692             m_caretRect = pos.node()->renderer()->caretRect(pos.offset(), m_affinity);
693             m_expectedVisibleRect = m_caretRect;
694         }
695         else {
696             m_caretRect = QRect();
697             m_expectedVisibleRect = QRect();
698         }
699     }
700     else {
701         // Calculate which position to use based on whether the base is the start.
702         // We want the position, start or end, that was calculated using the extent. 
703         // This makes the selection follow the extent position while scrolling as a 
704         // result of arrow navigation. 
705         //
706         // Note: no need to get additional help from VisiblePosition. The m_start and
707         // m_end positions should already be visible, and we're only interested in 
708         // a rectangle for m_expectedVisibleRect, hence affinity is not a factor
709         // like it is when drawing a caret.
710         //
711         Position pos = m_baseIsStart ? m_end : m_start;
712         ASSERT(pos.node()->renderer()); 
713         m_expectedVisibleRect = pos.node()->renderer()->caretRect(pos.offset(), m_affinity);
714         m_caretRect = QRect();
715     }
716
717     m_needsLayout = false;
718 }
719
720 QRect Selection::caretRect() const
721 {
722     if (m_needsLayout) {
723         const_cast<Selection *>(this)->layout();
724     }
725
726     return m_caretRect;
727 }
728
729 QRect Selection::expectedVisibleRect() const
730 {
731     if (m_needsLayout) {
732         const_cast<Selection *>(this)->layout();
733     }
734
735     return m_expectedVisibleRect;
736 }
737
738 QRect Selection::caretRepaintRect() const
739 {
740     // FIXME: Add one pixel of slop on each side to make sure we don't leave behind artifacts.
741     QRect r = caretRect();
742     if (r.isEmpty())
743         return QRect();
744     return QRect(r.left() - 1, r.top() - 1, r.width() + 2, r.height() + 2);
745 }
746
747 void Selection::needsCaretRepaint()
748 {
749     if (!isCaret())
750         return;
751
752     if (!m_start.node()->getDocument())
753         return;
754
755     KHTMLView *v = m_start.node()->getDocument()->view();
756     if (!v)
757         return;
758
759     if (m_needsLayout) {
760         // repaint old position and calculate new position
761         v->updateContents(caretRepaintRect(), false);
762         layout();
763         
764         // EDIT FIXME: This is an unfortunate hack.
765         // Basically, we can't trust this layout position since we 
766         // can't guarantee that the check to see if we are in unrendered 
767         // content will work at this point. We may have to wait for
768         // a layout and re-render of the document to happen. So, resetting this
769         // flag will cause another caret layout to happen the first time
770         // that we try to paint the caret after this call. That one will work since
771         // it happens after the document has accounted for any editing
772         // changes which may have been done.
773         // And, we need to leave this layout here so the caret moves right 
774         // away after clicking.
775         m_needsLayout = true;
776     }
777     v->updateContents(caretRepaintRect(), false);
778 }
779
780 void Selection::paintCaret(QPainter *p, const QRect &rect)
781 {
782     if (m_state != CARET)
783         return;
784
785     if (m_needsLayout)
786         layout();
787
788     if (m_caretRect.isValid())
789         p->fillRect(m_caretRect & rect, QBrush());
790 }
791
792 void Selection::validate(ETextGranularity granularity)
793 {
794     // Move the selection to rendered positions, if possible.
795     Position originalBase(m_base);
796     bool baseAndExtentEqual = m_base == m_extent;
797     bool updatedLayout = false;
798     if (m_base.isNotNull()) {
799         m_base.node()->getDocument()->updateLayout();
800         updatedLayout = true;
801         m_base = VisiblePosition(m_base).deepEquivalent();
802         if (baseAndExtentEqual)
803             m_extent = m_base;
804     }
805     if (m_extent.isNotNull() && !baseAndExtentEqual) {
806         if (!updatedLayout)
807             m_extent.node()->getDocument()->updateLayout();
808         m_extent = VisiblePosition(m_extent).deepEquivalent();
809     }
810
811     // Make sure we do not have a dangling start or end
812     if (m_base.isNull() && m_extent.isNull()) {
813         // Move the position to the enclosingBlockFlowElement of the original base, if possible.
814         // This has the effect of flashing the caret somewhere when a rendered position for
815         // the base and extent cannot be found.
816         if (originalBase.isNotNull()) {
817             Position pos(originalBase.node()->enclosingBlockFlowElement(), 0);
818             m_base = pos;
819             m_extent = pos;
820         }
821         else {
822             // We have no position to work with. See if the BODY element of the page
823             // is contentEditable. If it is, put the caret there.
824             //NodeImpl *node = document()
825             m_start.clear();
826             m_end.clear();
827         }
828         m_baseIsStart = true;
829     }
830     else if (m_base.isNull()) {
831         m_base = m_extent;
832         m_baseIsStart = true;
833     }
834     else if (m_extent.isNull()) {
835         m_extent = m_base;
836         m_baseIsStart = true;
837     }
838     else {
839         m_baseIsStart = RangeImpl::compareBoundaryPoints(m_base.node(), m_base.offset(), m_extent.node(), m_extent.offset()) <= 0;
840     }
841
842     m_start.clear();
843     m_end.clear();
844
845     // calculate the correct start and end positions
846     switch (granularity) {
847         case CHARACTER:
848             if (m_baseIsStart) {
849                 m_start = m_base;
850                 m_end = m_extent;
851             } else {
852                 m_start = m_extent;
853                 m_end = m_base;
854             }
855             break;
856         case WORD:
857             if (m_baseIsStart) {
858                 m_end = endOfWord(VisiblePosition(m_extent)).deepEquivalent();
859                 // If at the end of the document, expand to the left.
860                 EWordSide side = (m_end == m_extent) ? LeftWordIfOnBoundary : RightWordIfOnBoundary;
861                 m_start = startOfWord(VisiblePosition(m_base), side).deepEquivalent();
862             } else {
863                 m_start = startOfWord(VisiblePosition(m_extent)).deepEquivalent();
864                 m_end = endOfWord(VisiblePosition(m_base)).deepEquivalent();
865             }
866             break;
867         case LINE:
868         case LINE_BOUNDARY: {
869             Selection baseSelection = *this;
870             Selection extentSelection = *this;
871             Selection baseLine = selectionForLine(m_base, m_affinity);
872             if (baseLine.isCaretOrRange()) {
873                 baseSelection = baseLine;
874             }
875             Selection extentLine = selectionForLine(m_extent, m_affinity);
876             if (extentLine.isCaretOrRange()) {
877                 extentSelection = extentLine;
878             }
879             if (m_baseIsStart) {
880                 m_start = baseSelection.m_start;
881                 m_end = extentSelection.m_end;
882             } else {
883                 m_start = extentSelection.m_start;
884                 m_end = baseSelection.m_end;
885             }
886             break;
887         }
888         case PARAGRAPH:
889             if (m_baseIsStart) {
890                 m_start = startOfParagraph(VisiblePosition(m_base)).deepEquivalent();
891                 m_end = endOfParagraph(VisiblePosition(m_extent), IncludeLineBreak).deepEquivalent();
892             } else {
893                 m_start = startOfParagraph(VisiblePosition(m_extent)).deepEquivalent();
894                 m_end = endOfParagraph(VisiblePosition(m_base), IncludeLineBreak).deepEquivalent();
895             }
896             break;
897         case DOCUMENT_BOUNDARY: {
898             NodeImpl *de = m_start.node()->getDocument()->documentElement();
899             m_start = VisiblePosition(de, 0).deepEquivalent();
900             m_end = VisiblePosition(de, de ? de->childNodeCount() : 0).deepEquivalent();
901             break;
902         }
903         case PARAGRAPH_BOUNDARY:
904             if (m_baseIsStart) {
905                 m_start = startOfParagraph(VisiblePosition(m_base)).deepEquivalent();
906                 m_end = endOfParagraph(VisiblePosition(m_extent)).deepEquivalent();
907             } else {
908                 m_start = startOfParagraph(VisiblePosition(m_extent)).deepEquivalent();
909                 m_end = endOfParagraph(VisiblePosition(m_base)).deepEquivalent();
910             }
911             break;
912     }
913
914     // adjust the state
915     if (m_start.isNull()) {
916         ASSERT(m_end.isNull());
917         m_state = NONE;
918     }
919     else if (m_start == m_end || m_start.upstream(StayInBlock) == m_end.upstream(StayInBlock)) {
920         m_state = CARET;
921     }
922     else {
923         m_state = RANGE;
924         // "Constrain" the selection to be the smallest equivalent range of nodes.
925         // This is a somewhat arbitrary choice, but experience shows that it is
926         // useful to make to make the selection "canonical" (if only for
927         // purposes of comparing selections). This is an ideal point of the code
928         // to do this operation, since all selection changes that result in a RANGE 
929         // come through here before anyone uses it.
930         m_start = m_start.downstream(StayInBlock);
931         m_end = m_end.upstream(StayInBlock);
932     }
933
934     m_needsLayout = true;
935     
936 #if EDIT_DEBUG
937     debugPosition();
938 #endif
939 }
940
941 static Position startOfFirstRunAt(RenderObject *renderNode, int y)
942 {
943     for (RenderObject *n = renderNode; n; n = n->nextSibling()) {
944         if (n->isText()) {
945             RenderText *textRenderer = static_cast<RenderText *>(n);
946             for (InlineTextBox* box = textRenderer->firstTextBox(); box; box = box->nextTextBox()) {
947                 int absx, absy;
948                 n->absolutePosition(absx, absy);
949                 int top = absy + box->root()->topOverflow();
950                 if (top == y)
951                     return Position(textRenderer->element(), box->m_start);
952             }
953         }
954         
955         Position position = startOfFirstRunAt(n->firstChild(), y);
956         if (position.isNotNull())
957             return position;
958     }
959     
960     return Position();
961 }
962
963 static Position endOfLastRunAt(RenderObject *renderNode, int y)
964 {
965     RenderObject *n = renderNode;
966     if (!n)
967         return Position();
968     if (RenderObject *parent = n->parent())
969         n = parent->lastChild();
970     
971     while (1) {
972         Position position = endOfLastRunAt(n->firstChild(), y);
973         if (position.isNotNull())
974             return position;
975         
976         if (n->isText() && !n->isBR()) {
977             RenderText *textRenderer = static_cast<RenderText *>(n);
978             for (InlineTextBox* box = textRenderer->lastTextBox(); box; box = box->prevTextBox()) {
979                 int absx, absy;
980                 n->absolutePosition(absx, absy);
981                 int top = absy + box->root()->topOverflow();
982                 if (top == y)
983                     return Position(textRenderer->element(), box->m_start + box->m_len);
984             }
985         }
986         
987         if (n == renderNode)
988             return Position();
989         
990         n = n->previousSibling();
991     }
992 }
993
994 static Selection selectionForLine(const Position &position, EAffinity affinity)
995 {
996     NodeImpl *node = position.node();
997     if (!node || !node->renderer())
998         return Selection();
999     
1000     QRect rect = node->renderer()->caretRect(position.offset(), affinity);
1001     int selectionPointY = rect.y();
1002     
1003     // Go up to first non-inline element.
1004     RenderObject *renderNode = node->renderer();
1005     while (renderNode && renderNode->isInline())
1006         renderNode = renderNode->parent();
1007     renderNode = renderNode->firstChild();
1008     
1009     // Look for all the first child in the block that is on the same line
1010     // as the selection point.
1011     Position start = startOfFirstRunAt(renderNode, selectionPointY);
1012     if (start.isNull())
1013         return Selection();
1014
1015     // Look for all the last child in the block that is on the same line
1016     // as the selection point.
1017     Position end = endOfLastRunAt(renderNode, selectionPointY);
1018     if (end.isNull())
1019         return Selection();
1020     
1021     return Selection(start, end);
1022 }
1023
1024 void Selection::debugRenderer(RenderObject *r, bool selected) const
1025 {
1026     if (r->node()->isElementNode()) {
1027         ElementImpl *element = static_cast<ElementImpl *>(r->node());
1028         fprintf(stderr, "%s%s\n", selected ? "==> " : "    ", element->tagName().string().latin1());
1029     }
1030     else if (r->isText()) {
1031         RenderText *textRenderer = static_cast<RenderText *>(r);
1032         if (textRenderer->stringLength() == 0 || !textRenderer->firstTextBox()) {
1033             fprintf(stderr, "%s#text (empty)\n", selected ? "==> " : "    ");
1034             return;
1035         }
1036         
1037         static const int max = 36;
1038         QString text = DOMString(textRenderer->string()).string();
1039         int textLength = text.length();
1040         if (selected) {
1041             int offset = 0;
1042             if (r->node() == m_start.node())
1043                 offset = m_start.offset();
1044             else if (r->node() == m_end.node())
1045                 offset = m_end.offset();
1046                 
1047             int pos;
1048             InlineTextBox *box = textRenderer->findNextInlineTextBox(offset, pos);
1049             text = text.mid(box->m_start, box->m_len);
1050             
1051             QString show;
1052             int mid = max / 2;
1053             int caret = 0;
1054             
1055             // text is shorter than max
1056             if (textLength < max) {
1057                 show = text;
1058                 caret = pos;
1059             }
1060             
1061             // too few characters to left
1062             else if (pos - mid < 0) {
1063                 show = text.left(max - 3) + "...";
1064                 caret = pos;
1065             }
1066             
1067             // enough characters on each side
1068             else if (pos - mid >= 0 && pos + mid <= textLength) {
1069                 show = "..." + text.mid(pos - mid + 3, max - 6) + "...";
1070                 caret = mid;
1071             }
1072             
1073             // too few characters on right
1074             else {
1075                 show = "..." + text.right(max - 3);
1076                 caret = pos - (textLength - show.length());
1077             }
1078             
1079             show.replace('\n', ' ');
1080             show.replace('\r', ' ');
1081             fprintf(stderr, "==> #text : \"%s\" at offset %d\n", show.latin1(), pos);
1082             fprintf(stderr, "           ");
1083             for (int i = 0; i < caret; i++)
1084                 fprintf(stderr, " ");
1085             fprintf(stderr, "^\n");
1086         }
1087         else {
1088             if ((int)text.length() > max)
1089                 text = text.left(max - 3) + "...";
1090             else
1091                 text = text.left(max);
1092             fprintf(stderr, "    #text : \"%s\"\n", text.latin1());
1093         }
1094     }
1095 }
1096
1097 void Selection::debugPosition() const
1098 {
1099     if (!m_start.node())
1100         return;
1101
1102     //static int context = 5;
1103     
1104     //RenderObject *r = 0;
1105
1106     fprintf(stderr, "Selection =================\n");
1107
1108     if (m_start == m_end) {
1109         Position pos = m_start;
1110         Position upstream = pos.upstream();
1111         Position downstream = pos.downstream();
1112         fprintf(stderr, "upstream:   %s %p:%d\n", getTagName(upstream.node()->id()).string().latin1(), upstream.node(), upstream.offset());
1113         fprintf(stderr, "pos:        %s %p:%d\n", getTagName(pos.node()->id()).string().latin1(), pos.node(), pos.offset());
1114         fprintf(stderr, "downstream: %s %p:%d\n", getTagName(downstream.node()->id()).string().latin1(), downstream.node(), downstream.offset());
1115     }
1116     else {
1117         Position pos = m_start;
1118         Position upstream = pos.upstream();
1119         Position downstream = pos.downstream();
1120         fprintf(stderr, "upstream:   %s %p:%d\n", getTagName(upstream.node()->id()).string().latin1(), upstream.node(), upstream.offset());
1121         fprintf(stderr, "start:      %s %p:%d\n", getTagName(pos.node()->id()).string().latin1(), pos.node(), pos.offset());
1122         fprintf(stderr, "downstream: %s %p:%d\n", getTagName(downstream.node()->id()).string().latin1(), downstream.node(), downstream.offset());
1123         fprintf(stderr, "-----------------------------------\n");
1124         pos = m_end;
1125         upstream = pos.upstream();
1126         downstream = pos.downstream();
1127         fprintf(stderr, "upstream:   %s %p:%d\n", getTagName(upstream.node()->id()).string().latin1(), upstream.node(), upstream.offset());
1128         fprintf(stderr, "end:        %s %p:%d\n", getTagName(pos.node()->id()).string().latin1(), pos.node(), pos.offset());
1129         fprintf(stderr, "downstream: %s %p:%d\n", getTagName(downstream.node()->id()).string().latin1(), downstream.node(), downstream.offset());
1130         fprintf(stderr, "-----------------------------------\n");
1131     }
1132           
1133 #if 0
1134     int back = 0;
1135     r = m_start.node()->renderer();
1136     for (int i = 0; i < context; i++, back++) {
1137         if (r->previousRenderer())
1138             r = r->previousRenderer();
1139         else
1140             break;
1141     }
1142     for (int i = 0; i < back; i++) {
1143         debugRenderer(r, false);
1144         r = r->nextRenderer();
1145     }
1146
1147
1148     fprintf(stderr, "\n");
1149
1150     if (m_start.node() == m_end.node())
1151         debugRenderer(m_start.node()->renderer(), true);
1152     else
1153         for (r = m_start.node()->renderer(); r && r != m_end.node()->renderer(); r = r->nextRenderer())
1154             debugRenderer(r, true);
1155     
1156     fprintf(stderr, "\n");
1157     
1158     r = m_end.node()->renderer();
1159     for (int i = 0; i < context; i++) {
1160         if (r->nextRenderer()) {
1161             r = r->nextRenderer();
1162             debugRenderer(r, false);
1163         }
1164         else
1165             break;
1166     }
1167 #endif
1168
1169     fprintf(stderr, "================================\n");
1170 }
1171
1172 #ifndef NDEBUG
1173 #define FormatBufferSize 1024
1174 void Selection::formatForDebugger(char *buffer, unsigned length) const
1175 {
1176     DOMString result;
1177     DOMString s;
1178     
1179     if (isNone()) {
1180         result = "<none>";
1181     }
1182     else {
1183         char s[FormatBufferSize];
1184         result += "from ";
1185         m_start.formatForDebugger(s, FormatBufferSize);
1186         result += s;
1187         result += " to ";
1188         m_end.formatForDebugger(s, FormatBufferSize);
1189         result += s;
1190     }
1191           
1192     strncpy(buffer, result.string().latin1(), length - 1);
1193 }
1194 #undef FormatBufferSize
1195 #endif
1196
1197 } // namespace DOM