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