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             // This somewhat complicated code is needed to handle the case where there is a
311             // whole line selected (like when the user clicks at the start of a line and hits shift+down-arrow),
312             // and then hits an (unshifted) down arrow. Since the whole-line selection considers its
313             // ending point to be the start of the next line, it may be necessary to juggle the 
314             // position to use as the VisiblePosition to pass to nextLinePosition(). If this juggling
315             // is not done, you can wind up skipping a line. See these two bugs for more information:
316             // <rdar://problem/3875618> REGRESSION (Mail): Hitting down arrow with full line selected skips line (br case)
317             // <rdar://problem/3875641> REGRESSION (Mail): Hitting down arrow with full line selected skips line (div case)
318             if (isCaret()) {
319                 pos = VisiblePosition(m_end);
320             }
321             else if (isRange()) {
322                 Position p(m_end.upstream());
323                 if (p.node()->id() == ID_BR)
324                     pos = VisiblePosition(Position(p.node(), 0));
325                 else
326                     pos = VisiblePosition(p);
327             }
328             pos = nextLinePosition(pos, m_affinity, xPosForVerticalArrowNavigation(END, isRange()));
329             break;
330         }
331         case LINE_BOUNDARY:
332             pos = VisiblePosition(selectionForLine(m_end, m_affinity).end());
333             break;
334         case PARAGRAPH_BOUNDARY:
335             pos = endOfParagraph(VisiblePosition(m_end));
336             break;
337         case DOCUMENT_BOUNDARY: {
338             NodeImpl *de = m_start.node()->getDocument()->documentElement();
339             pos = VisiblePosition(de, de ? de->childNodeCount() : 0);
340             break;
341         }
342     }
343     return pos;
344 }
345
346 VisiblePosition Selection::modifyExtendingLeftBackward(ETextGranularity granularity)
347 {
348     VisiblePosition pos(m_extent);
349     switch (granularity) {
350         case CHARACTER:
351             pos = pos.previous();
352             break;
353         case WORD:
354             pos = previousWordPosition(pos);
355             break;
356         case PARAGRAPH:
357             pos = previousParagraphPosition(pos, m_affinity, xPosForVerticalArrowNavigation(EXTENT));
358             break;
359         case LINE:
360             pos = previousLinePosition(pos, m_affinity, xPosForVerticalArrowNavigation(EXTENT));
361             break;
362         case LINE_BOUNDARY:
363             pos = VisiblePosition(selectionForLine(m_start, m_affinity).start());
364             break;
365         case PARAGRAPH_BOUNDARY:
366             pos = startOfParagraph(VisiblePosition(m_start));
367             break;
368         case DOCUMENT_BOUNDARY:
369             pos = VisiblePosition(m_start.node()->getDocument()->documentElement(), 0);
370             break;
371     }
372     return pos;
373 }
374
375 VisiblePosition Selection::modifyMovingLeftBackward(ETextGranularity granularity)
376 {
377     VisiblePosition pos;
378     switch (granularity) {
379         case CHARACTER:
380             if (isRange()) 
381                 pos = VisiblePosition(m_start);
382             else
383                 pos = VisiblePosition(m_extent).previous();
384             break;
385         case WORD:
386             pos = previousWordPosition(VisiblePosition(m_extent));
387             break;
388         case PARAGRAPH:
389             pos = previousParagraphPosition(VisiblePosition(m_start), m_affinity, xPosForVerticalArrowNavigation(START, isRange()));
390             break;
391         case LINE:
392             pos = previousLinePosition(VisiblePosition(m_start), m_affinity, xPosForVerticalArrowNavigation(START, isRange()));
393             break;
394         case LINE_BOUNDARY:
395             pos = VisiblePosition(selectionForLine(m_start, m_affinity).start());
396             break;
397         case PARAGRAPH_BOUNDARY:
398             pos = startOfParagraph(VisiblePosition(m_start));
399             break;
400         case DOCUMENT_BOUNDARY:
401             pos = VisiblePosition(m_start.node()->getDocument()->documentElement(), 0);
402             break;
403     }
404     return pos;
405 }
406
407 bool Selection::modify(EAlter alter, EDirection dir, ETextGranularity granularity)
408 {
409     setModifyBias(alter, dir);
410
411     VisiblePosition pos;
412
413     switch (dir) {
414         // EDIT FIXME: These need to handle bidi
415         case RIGHT:
416         case FORWARD:
417             if (alter == EXTEND)
418                 pos = modifyExtendingRightForward(granularity);
419             else
420                 pos = modifyMovingRightForward(granularity);
421             break;
422         case LEFT:
423         case BACKWARD:
424             if (alter == EXTEND)
425                 pos = modifyExtendingLeftBackward(granularity);
426             else
427                 pos = modifyMovingLeftBackward(granularity);
428             break;
429     }
430
431     if (pos.isNull())
432         return false;
433
434     // Save and restore affinity here before calling setAffinity. 
435     // The moveTo() and setExtent() calls reset affinity and this 
436     // is undesirable here.
437     EAffinity savedAffinity = m_affinity;
438     switch (alter) {
439         case MOVE:
440             moveTo(pos.deepEquivalent());
441             break;
442         case EXTEND:
443             setExtent(pos.deepEquivalent());
444             break;
445     }
446     m_affinity = savedAffinity;
447     modifyAffinity(alter, dir, granularity);
448
449     return true;
450 }
451
452 // FIXME: Maybe baseline would be better?
453 static bool caretY(const VisiblePosition &c, int &y)
454 {
455     Position p = c.deepEquivalent();
456     NodeImpl *n = p.node();
457     if (!n)
458         return false;
459     RenderObject *r = p.node()->renderer();
460     if (!r)
461         return false;
462     QRect rect = r->caretRect(p.offset());
463     if (rect.isEmpty())
464         return false;
465     y = rect.y() + rect.height() / 2;
466     return true;
467 }
468
469 bool Selection::modify(EAlter alter, int verticalDistance)
470 {
471     if (verticalDistance == 0)
472         return false;
473
474     bool up = verticalDistance < 0;
475     if (up)
476         verticalDistance = -verticalDistance;
477
478     m_affinity = UPSTREAM;
479     setModifyBias(alter, up ? BACKWARD : FORWARD);
480
481     VisiblePosition pos;
482     int xPos = 0; /* initialized only to make compiler happy */
483
484     switch (alter) {
485         case MOVE:
486             pos = VisiblePosition(up ? m_start : m_end);
487             xPos = xPosForVerticalArrowNavigation(up ? START : END, isRange());
488             break;
489         case EXTEND:
490             pos = VisiblePosition(m_extent);
491             xPos = xPosForVerticalArrowNavigation(EXTENT);
492             break;
493     }
494
495     int startY;
496     if (!caretY(pos, startY))
497         return false;
498     if (up)
499         startY = -startY;
500     int lastY = startY;
501
502     VisiblePosition result;
503
504     VisiblePosition next;
505     for (VisiblePosition p = pos; ; p = next) {
506         next = (up ? previousLinePosition : nextLinePosition)(p, m_affinity, xPos);
507         if (next.isNull() || next == p)
508             break;
509         int nextY;
510         if (!caretY(next, nextY))
511             break;
512         if (up)
513             nextY = -nextY;
514         if (nextY - startY > verticalDistance)
515             break;
516         if (nextY >= lastY) {
517             lastY = nextY;
518             result = next;
519         }
520     }
521
522     if (result.isNull())
523         return false;
524
525     switch (alter) {
526         case MOVE:
527             moveTo(result.deepEquivalent());
528             break;
529         case EXTEND:
530             setExtent(result.deepEquivalent());
531             break;
532     }
533
534     return true;
535 }
536
537 bool Selection::expandUsingGranularity(ETextGranularity granularity)
538 {
539     if (isNone())
540         return false;
541     validate(granularity);
542     return true;
543 }
544
545 int Selection::xPosForVerticalArrowNavigation(EPositionType type, bool recalc) const
546 {
547     int x = 0;
548
549     if (isNone())
550         return x;
551
552     Position pos;
553     switch (type) {
554         case START:
555             pos = m_start;
556             break;
557         case END:
558             pos = m_end;
559             break;
560         case BASE:
561             pos = m_base;
562             break;
563         case EXTENT:
564             pos = m_extent;
565             break;
566     }
567
568     KHTMLPart *part = pos.node()->getDocument()->part();
569     if (!part)
570         return x;
571         
572     if (recalc || part->xPosForVerticalArrowNavigation() == KHTMLPart::NoXPosForVerticalArrowNavigation) {
573         switch (m_affinity) {
574             case DOWNSTREAM:
575                 pos = VisiblePosition(pos).downstreamDeepEquivalent();
576                 break;
577             case UPSTREAM:
578                 pos = VisiblePosition(pos).deepEquivalent();
579                 break;
580         }
581         x = pos.node()->renderer()->caretRect(pos.offset(), m_affinity).x();
582         part->setXPosForVerticalArrowNavigation(x);
583     }
584     else {
585         x = part->xPosForVerticalArrowNavigation();
586     }
587     return x;
588 }
589
590 void Selection::clear()
591 {
592     m_affinity = UPSTREAM;
593     m_base.clear();
594     m_extent.clear();
595     validate();
596 }
597
598 void Selection::setBase(const Position &pos)
599 {
600     m_affinity = UPSTREAM;
601     m_base = pos;
602     validate();
603 }
604
605 void Selection::setExtent(const Position &pos)
606 {
607     m_affinity = UPSTREAM;
608     m_extent = pos;
609     validate();
610 }
611
612 void Selection::setBaseAndExtent(const Position &base, const Position &extent)
613 {
614     m_affinity = UPSTREAM;
615     m_base = base;
616     m_extent = extent;
617     validate();
618 }
619
620 void Selection::setNeedsLayout(bool flag)
621 {
622     m_needsLayout = flag;
623 }
624
625 Range Selection::toRange() const
626 {
627     if (isNone())
628         return Range();
629
630     // Make sure we have an updated layout since this function is called
631     // in the course of running edit commands which modify the DOM.
632     // Failing to call this can result in equivalentXXXPosition calls returning
633     // incorrect results.
634     m_start.node()->getDocument()->updateLayout();
635
636     Position s, e;
637     if (isCaret()) {
638         // If the selection is a caret, move the range start upstream. This helps us match
639         // the conventions of text editors tested, which make style determinations based
640         // on the character before the caret, if any. 
641         s = m_start.upstream(StayInBlock).equivalentRangeCompliantPosition();
642         e = s;
643     }
644     else {
645         // If the selection is a range, select the minimum range that encompasses the selection.
646         // Again, this is to match the conventions of text editors tested, which make style 
647         // determinations based on the first character of the selection. 
648         // For instance, this operation helps to make sure that the "X" selected below is the 
649         // only thing selected. The range should not be allowed to "leak" out to the end of the 
650         // previous text node, or to the beginning of the next text node, each of which has a 
651         // different style.
652         // 
653         // On a treasure map, <b>X</b> marks the spot.
654         //                       ^ selected
655         //
656         ASSERT(isRange());
657         s = m_start.downstream(StayInBlock);
658         e = m_end.upstream(StayInBlock);
659         if (RangeImpl::compareBoundaryPoints(s.node(), s.offset(), e.node(), e.offset()) > 0) {
660             // Make sure the start is before the end.
661             // The end can wind up before the start if collapsed whitespace is the only thing selected.
662             Position tmp = s;
663             s = e;
664             e = tmp;
665         }
666         s = s.equivalentRangeCompliantPosition();
667         e = e.equivalentRangeCompliantPosition();
668     }
669
670     // Use this roundabout way of creating the Range in order to have defined behavior
671     // when there is a DOM exception.
672     int exceptionCode = 0;
673     Range result(s.node()->getDocument());
674     RangeImpl *handle = result.handle();
675     ASSERT(handle);
676     handle->setStart(s.node(), s.offset(), exceptionCode);
677     if (exceptionCode) {
678         ERROR("Exception setting Range start from Selection: %d", exceptionCode);
679         return Range();
680     }
681     handle->setEnd(e.node(), e.offset(), exceptionCode);
682     if (exceptionCode) {
683         ERROR("Exception setting Range end from Selection: %d", exceptionCode);
684         return Range();
685     }
686     return result;
687 }
688
689 void Selection::layout()
690 {
691     if (isNone() || !m_start.node()->inDocument() || !m_end.node()->inDocument()) {
692         m_caretRect = QRect();
693         m_expectedVisibleRect = QRect();
694         return;
695     }
696
697     m_start.node()->getDocument()->updateRendering();
698         
699     if (isCaret()) {
700         Position pos = m_start;
701         switch (m_affinity) {
702             case DOWNSTREAM:
703                 pos = VisiblePosition(m_start).downstreamDeepEquivalent();
704                 break;
705             case UPSTREAM:
706                 pos = VisiblePosition(m_start).deepEquivalent();
707                 break;
708         }
709         if (pos.isNotNull()) {
710             ASSERT(pos.node()->renderer());
711             m_caretRect = pos.node()->renderer()->caretRect(pos.offset(), m_affinity);
712             m_expectedVisibleRect = m_caretRect;
713         }
714         else {
715             m_caretRect = QRect();
716             m_expectedVisibleRect = QRect();
717         }
718     }
719     else {
720         // Calculate which position to use based on whether the base is the start.
721         // We want the position, start or end, that was calculated using the extent. 
722         // This makes the selection follow the extent position while scrolling as a 
723         // result of arrow navigation. 
724         //
725         // Note: no need to get additional help from VisiblePosition. The m_start and
726         // m_end positions should already be visible, and we're only interested in 
727         // a rectangle for m_expectedVisibleRect, hence affinity is not a factor
728         // like it is when drawing a caret.
729         //
730         Position pos = m_baseIsStart ? m_end : m_start;
731         ASSERT(pos.node()->renderer()); 
732         m_expectedVisibleRect = pos.node()->renderer()->caretRect(pos.offset(), m_affinity);
733         m_caretRect = QRect();
734     }
735
736     m_needsLayout = false;
737 }
738
739 QRect Selection::caretRect() const
740 {
741     if (m_needsLayout) {
742         const_cast<Selection *>(this)->layout();
743     }
744
745     return m_caretRect;
746 }
747
748 QRect Selection::expectedVisibleRect() const
749 {
750     if (m_needsLayout) {
751         const_cast<Selection *>(this)->layout();
752     }
753
754     return m_expectedVisibleRect;
755 }
756
757 QRect Selection::caretRepaintRect() const
758 {
759     // FIXME: Add one pixel of slop on each side to make sure we don't leave behind artifacts.
760     QRect r = caretRect();
761     if (r.isEmpty())
762         return QRect();
763     return QRect(r.left() - 1, r.top() - 1, r.width() + 2, r.height() + 2);
764 }
765
766 void Selection::needsCaretRepaint()
767 {
768     if (!isCaret())
769         return;
770
771     if (!m_start.node()->getDocument())
772         return;
773
774     KHTMLView *v = m_start.node()->getDocument()->view();
775     if (!v)
776         return;
777
778     if (m_needsLayout) {
779         // repaint old position and calculate new position
780         v->updateContents(caretRepaintRect(), false);
781         layout();
782         
783         // EDIT FIXME: This is an unfortunate hack.
784         // Basically, we can't trust this layout position since we 
785         // can't guarantee that the check to see if we are in unrendered 
786         // content will work at this point. We may have to wait for
787         // a layout and re-render of the document to happen. So, resetting this
788         // flag will cause another caret layout to happen the first time
789         // that we try to paint the caret after this call. That one will work since
790         // it happens after the document has accounted for any editing
791         // changes which may have been done.
792         // And, we need to leave this layout here so the caret moves right 
793         // away after clicking.
794         m_needsLayout = true;
795     }
796     v->updateContents(caretRepaintRect(), false);
797 }
798
799 void Selection::paintCaret(QPainter *p, const QRect &rect)
800 {
801     if (m_state != CARET)
802         return;
803
804     if (m_needsLayout)
805         layout();
806
807     if (m_caretRect.isValid())
808         p->fillRect(m_caretRect & rect, QBrush());
809 }
810
811 void Selection::validate(ETextGranularity granularity)
812 {
813     // Move the selection to rendered positions, if possible.
814     Position originalBase(m_base);
815     bool baseAndExtentEqual = m_base == m_extent;
816     bool updatedLayout = false;
817     if (m_base.isNotNull()) {
818         m_base.node()->getDocument()->updateLayout();
819         updatedLayout = true;
820         m_base = VisiblePosition(m_base).deepEquivalent();
821         if (baseAndExtentEqual)
822             m_extent = m_base;
823     }
824     if (m_extent.isNotNull() && !baseAndExtentEqual) {
825         if (!updatedLayout)
826             m_extent.node()->getDocument()->updateLayout();
827         m_extent = VisiblePosition(m_extent).deepEquivalent();
828     }
829
830     // Make sure we do not have a dangling start or end
831     if (m_base.isNull() && m_extent.isNull()) {
832         // Move the position to the enclosingBlockFlowElement of the original base, if possible.
833         // This has the effect of flashing the caret somewhere when a rendered position for
834         // the base and extent cannot be found.
835         if (originalBase.isNotNull()) {
836             Position pos(originalBase.node()->enclosingBlockFlowElement(), 0);
837             m_base = pos;
838             m_extent = pos;
839         }
840         else {
841             // We have no position to work with. See if the BODY element of the page
842             // is contentEditable. If it is, put the caret there.
843             //NodeImpl *node = document()
844             m_start.clear();
845             m_end.clear();
846         }
847         m_baseIsStart = true;
848     }
849     else if (m_base.isNull()) {
850         m_base = m_extent;
851         m_baseIsStart = true;
852     }
853     else if (m_extent.isNull()) {
854         m_extent = m_base;
855         m_baseIsStart = true;
856     }
857     else {
858         m_baseIsStart = RangeImpl::compareBoundaryPoints(m_base.node(), m_base.offset(), m_extent.node(), m_extent.offset()) <= 0;
859     }
860
861     m_start.clear();
862     m_end.clear();
863
864     // calculate the correct start and end positions
865     switch (granularity) {
866         case CHARACTER:
867             if (m_baseIsStart) {
868                 m_start = m_base;
869                 m_end = m_extent;
870             } else {
871                 m_start = m_extent;
872                 m_end = m_base;
873             }
874             break;
875         case WORD:
876             if (m_baseIsStart) {
877                 m_end = endOfWord(VisiblePosition(m_extent)).deepEquivalent();
878                 // If at the end of the document, expand to the left.
879                 EWordSide side = (m_end == m_extent) ? LeftWordIfOnBoundary : RightWordIfOnBoundary;
880                 m_start = startOfWord(VisiblePosition(m_base), side).deepEquivalent();
881             } else {
882                 m_start = startOfWord(VisiblePosition(m_extent)).deepEquivalent();
883                 m_end = endOfWord(VisiblePosition(m_base)).deepEquivalent();
884             }
885             break;
886         case LINE:
887         case LINE_BOUNDARY: {
888             Selection baseSelection = *this;
889             Selection extentSelection = *this;
890             Selection baseLine = selectionForLine(m_base, m_affinity);
891             if (baseLine.isCaretOrRange()) {
892                 baseSelection = baseLine;
893             }
894             Selection extentLine = selectionForLine(m_extent, m_affinity);
895             if (extentLine.isCaretOrRange()) {
896                 extentSelection = extentLine;
897             }
898             if (m_baseIsStart) {
899                 m_start = baseSelection.m_start;
900                 m_end = extentSelection.m_end;
901             } else {
902                 m_start = extentSelection.m_start;
903                 m_end = baseSelection.m_end;
904             }
905             break;
906         }
907         case PARAGRAPH:
908             if (m_baseIsStart) {
909                 m_start = startOfParagraph(VisiblePosition(m_base)).deepEquivalent();
910                 m_end = endOfParagraph(VisiblePosition(m_extent), IncludeLineBreak).deepEquivalent();
911             } else {
912                 m_start = startOfParagraph(VisiblePosition(m_extent)).deepEquivalent();
913                 m_end = endOfParagraph(VisiblePosition(m_base), IncludeLineBreak).deepEquivalent();
914             }
915             break;
916         case DOCUMENT_BOUNDARY: {
917             NodeImpl *de = m_start.node()->getDocument()->documentElement();
918             m_start = VisiblePosition(de, 0).deepEquivalent();
919             m_end = VisiblePosition(de, de ? de->childNodeCount() : 0).deepEquivalent();
920             break;
921         }
922         case PARAGRAPH_BOUNDARY:
923             if (m_baseIsStart) {
924                 m_start = startOfParagraph(VisiblePosition(m_base)).deepEquivalent();
925                 m_end = endOfParagraph(VisiblePosition(m_extent)).deepEquivalent();
926             } else {
927                 m_start = startOfParagraph(VisiblePosition(m_extent)).deepEquivalent();
928                 m_end = endOfParagraph(VisiblePosition(m_base)).deepEquivalent();
929             }
930             break;
931     }
932
933     // adjust the state
934     if (m_start.isNull()) {
935         ASSERT(m_end.isNull());
936         m_state = NONE;
937     }
938     else if (m_start == m_end || m_start.upstream(StayInBlock) == m_end.upstream(StayInBlock)) {
939         m_state = CARET;
940     }
941     else {
942         m_state = RANGE;
943         // "Constrain" the selection to be the smallest equivalent range of nodes.
944         // This is a somewhat arbitrary choice, but experience shows that it is
945         // useful to make to make the selection "canonical" (if only for
946         // purposes of comparing selections). This is an ideal point of the code
947         // to do this operation, since all selection changes that result in a RANGE 
948         // come through here before anyone uses it.
949         m_start = m_start.downstream(StayInBlock);
950         m_end = m_end.upstream(StayInBlock);
951     }
952
953     m_needsLayout = true;
954     
955 #if EDIT_DEBUG
956     debugPosition();
957 #endif
958 }
959
960 static Position startOfFirstRunAt(RenderObject *renderNode, int y)
961 {
962     for (RenderObject *n = renderNode; n; n = n->nextSibling()) {
963         if (n->isText()) {
964             RenderText *textRenderer = static_cast<RenderText *>(n);
965             for (InlineTextBox* box = textRenderer->firstTextBox(); box; box = box->nextTextBox()) {
966                 int absx, absy;
967                 n->absolutePosition(absx, absy);
968                 int top = absy + box->root()->topOverflow();
969                 if (top == y)
970                     return Position(textRenderer->element(), box->m_start);
971             }
972         }
973         
974         Position position = startOfFirstRunAt(n->firstChild(), y);
975         if (position.isNotNull())
976             return position;
977     }
978     
979     return Position();
980 }
981
982 static Position endOfLastRunAt(RenderObject *renderNode, int y)
983 {
984     RenderObject *n = renderNode;
985     if (!n)
986         return Position();
987     if (RenderObject *parent = n->parent())
988         n = parent->lastChild();
989     
990     while (1) {
991         Position position = endOfLastRunAt(n->firstChild(), y);
992         if (position.isNotNull())
993             return position;
994         
995         if (n->isText() && !n->isBR()) {
996             RenderText *textRenderer = static_cast<RenderText *>(n);
997             for (InlineTextBox* box = textRenderer->lastTextBox(); box; box = box->prevTextBox()) {
998                 int absx, absy;
999                 n->absolutePosition(absx, absy);
1000                 int top = absy + box->root()->topOverflow();
1001                 if (top == y)
1002                     return Position(textRenderer->element(), box->m_start + box->m_len);
1003             }
1004         }
1005         
1006         if (n == renderNode)
1007             return Position();
1008         
1009         n = n->previousSibling();
1010     }
1011 }
1012
1013 static Selection selectionForLine(const Position &position, EAffinity affinity)
1014 {
1015     NodeImpl *node = position.node();
1016     if (!node || !node->renderer())
1017         return Selection();
1018     
1019     QRect rect = node->renderer()->caretRect(position.offset(), affinity);
1020     int selectionPointY = rect.y();
1021     
1022     // Go up to first non-inline element.
1023     RenderObject *renderNode = node->renderer();
1024     while (renderNode && renderNode->isInline())
1025         renderNode = renderNode->parent();
1026     renderNode = renderNode->firstChild();
1027     
1028     // Look for all the first child in the block that is on the same line
1029     // as the selection point.
1030     Position start = startOfFirstRunAt(renderNode, selectionPointY);
1031     if (start.isNull())
1032         return Selection();
1033
1034     // Look for all the last child in the block that is on the same line
1035     // as the selection point.
1036     Position end = endOfLastRunAt(renderNode, selectionPointY);
1037     if (end.isNull())
1038         return Selection();
1039     
1040     return Selection(start, end);
1041 }
1042
1043 void Selection::debugRenderer(RenderObject *r, bool selected) const
1044 {
1045     if (r->node()->isElementNode()) {
1046         ElementImpl *element = static_cast<ElementImpl *>(r->node());
1047         fprintf(stderr, "%s%s\n", selected ? "==> " : "    ", element->tagName().string().latin1());
1048     }
1049     else if (r->isText()) {
1050         RenderText *textRenderer = static_cast<RenderText *>(r);
1051         if (textRenderer->stringLength() == 0 || !textRenderer->firstTextBox()) {
1052             fprintf(stderr, "%s#text (empty)\n", selected ? "==> " : "    ");
1053             return;
1054         }
1055         
1056         static const int max = 36;
1057         QString text = DOMString(textRenderer->string()).string();
1058         int textLength = text.length();
1059         if (selected) {
1060             int offset = 0;
1061             if (r->node() == m_start.node())
1062                 offset = m_start.offset();
1063             else if (r->node() == m_end.node())
1064                 offset = m_end.offset();
1065                 
1066             int pos;
1067             InlineTextBox *box = textRenderer->findNextInlineTextBox(offset, pos);
1068             text = text.mid(box->m_start, box->m_len);
1069             
1070             QString show;
1071             int mid = max / 2;
1072             int caret = 0;
1073             
1074             // text is shorter than max
1075             if (textLength < max) {
1076                 show = text;
1077                 caret = pos;
1078             }
1079             
1080             // too few characters to left
1081             else if (pos - mid < 0) {
1082                 show = text.left(max - 3) + "...";
1083                 caret = pos;
1084             }
1085             
1086             // enough characters on each side
1087             else if (pos - mid >= 0 && pos + mid <= textLength) {
1088                 show = "..." + text.mid(pos - mid + 3, max - 6) + "...";
1089                 caret = mid;
1090             }
1091             
1092             // too few characters on right
1093             else {
1094                 show = "..." + text.right(max - 3);
1095                 caret = pos - (textLength - show.length());
1096             }
1097             
1098             show.replace('\n', ' ');
1099             show.replace('\r', ' ');
1100             fprintf(stderr, "==> #text : \"%s\" at offset %d\n", show.latin1(), pos);
1101             fprintf(stderr, "           ");
1102             for (int i = 0; i < caret; i++)
1103                 fprintf(stderr, " ");
1104             fprintf(stderr, "^\n");
1105         }
1106         else {
1107             if ((int)text.length() > max)
1108                 text = text.left(max - 3) + "...";
1109             else
1110                 text = text.left(max);
1111             fprintf(stderr, "    #text : \"%s\"\n", text.latin1());
1112         }
1113     }
1114 }
1115
1116 void Selection::debugPosition() const
1117 {
1118     if (!m_start.node())
1119         return;
1120
1121     //static int context = 5;
1122     
1123     //RenderObject *r = 0;
1124
1125     fprintf(stderr, "Selection =================\n");
1126
1127     if (m_start == m_end) {
1128         Position pos = m_start;
1129         Position upstream = pos.upstream();
1130         Position downstream = pos.downstream();
1131         fprintf(stderr, "upstream:   %s %p:%d\n", getTagName(upstream.node()->id()).string().latin1(), upstream.node(), upstream.offset());
1132         fprintf(stderr, "pos:        %s %p:%d\n", getTagName(pos.node()->id()).string().latin1(), pos.node(), pos.offset());
1133         fprintf(stderr, "downstream: %s %p:%d\n", getTagName(downstream.node()->id()).string().latin1(), downstream.node(), downstream.offset());
1134     }
1135     else {
1136         Position pos = m_start;
1137         Position upstream = pos.upstream();
1138         Position downstream = pos.downstream();
1139         fprintf(stderr, "upstream:   %s %p:%d\n", getTagName(upstream.node()->id()).string().latin1(), upstream.node(), upstream.offset());
1140         fprintf(stderr, "start:      %s %p:%d\n", getTagName(pos.node()->id()).string().latin1(), pos.node(), pos.offset());
1141         fprintf(stderr, "downstream: %s %p:%d\n", getTagName(downstream.node()->id()).string().latin1(), downstream.node(), downstream.offset());
1142         fprintf(stderr, "-----------------------------------\n");
1143         pos = m_end;
1144         upstream = pos.upstream();
1145         downstream = pos.downstream();
1146         fprintf(stderr, "upstream:   %s %p:%d\n", getTagName(upstream.node()->id()).string().latin1(), upstream.node(), upstream.offset());
1147         fprintf(stderr, "end:        %s %p:%d\n", getTagName(pos.node()->id()).string().latin1(), pos.node(), pos.offset());
1148         fprintf(stderr, "downstream: %s %p:%d\n", getTagName(downstream.node()->id()).string().latin1(), downstream.node(), downstream.offset());
1149         fprintf(stderr, "-----------------------------------\n");
1150     }
1151           
1152 #if 0
1153     int back = 0;
1154     r = m_start.node()->renderer();
1155     for (int i = 0; i < context; i++, back++) {
1156         if (r->previousRenderer())
1157             r = r->previousRenderer();
1158         else
1159             break;
1160     }
1161     for (int i = 0; i < back; i++) {
1162         debugRenderer(r, false);
1163         r = r->nextRenderer();
1164     }
1165
1166
1167     fprintf(stderr, "\n");
1168
1169     if (m_start.node() == m_end.node())
1170         debugRenderer(m_start.node()->renderer(), true);
1171     else
1172         for (r = m_start.node()->renderer(); r && r != m_end.node()->renderer(); r = r->nextRenderer())
1173             debugRenderer(r, true);
1174     
1175     fprintf(stderr, "\n");
1176     
1177     r = m_end.node()->renderer();
1178     for (int i = 0; i < context; i++) {
1179         if (r->nextRenderer()) {
1180             r = r->nextRenderer();
1181             debugRenderer(r, false);
1182         }
1183         else
1184             break;
1185     }
1186 #endif
1187
1188     fprintf(stderr, "================================\n");
1189 }
1190
1191 #ifndef NDEBUG
1192 #define FormatBufferSize 1024
1193 void Selection::formatForDebugger(char *buffer, unsigned length) const
1194 {
1195     DOMString result;
1196     DOMString s;
1197     
1198     if (isNone()) {
1199         result = "<none>";
1200     }
1201     else {
1202         char s[FormatBufferSize];
1203         result += "from ";
1204         m_start.formatForDebugger(s, FormatBufferSize);
1205         result += s;
1206         result += " to ";
1207         m_end.formatForDebugger(s, FormatBufferSize);
1208         result += s;
1209     }
1210           
1211     strncpy(buffer, result.string().latin1(), length - 1);
1212 }
1213 #undef FormatBufferSize
1214 #endif
1215
1216 } // namespace DOM