Reviewed by Hyatt
[WebKit-https.git] / WebCore / khtml / editing / selection.cpp
1 /*
2  * Copyright (C) 2003 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 "dom_selection.h"
27
28 #include "htmltags.h"
29 #include "khtml_part.h"
30 #include "khtmlview.h"
31 #include "qevent.h"
32 #include "qpainter.h"
33 #include "qrect.h"
34 #include "dom/dom2_range.h"
35 #include "dom/dom_node.h"
36 #include "dom/dom_position.h"
37 #include "dom/dom_string.h"
38 #include "rendering/render_object.h"
39 #include "rendering/render_style.h"
40 #include "rendering/render_text.h"
41 #include "xml/dom_docimpl.h"
42 #include "xml/dom_edititerator.h"
43 #include "xml/dom_elementimpl.h"
44 #include "xml/dom_nodeimpl.h"
45 #include "xml/dom_textimpl.h"
46
47 #if APPLE_CHANGES
48 #include <KWQAssertions.h>
49 #include <KWQTextUtilities.h>
50 #include <CoreServices/CoreServices.h>
51
52 #define EDIT_DEBUG 0
53 #endif
54
55 namespace DOM {
56
57 using khtml::InlineTextBox;
58 using khtml::RenderObject;
59 using khtml::RenderText;
60
61 #if APPLE_CHANGES
62 static bool firstRunAt(RenderObject *renderNode, int y, NodeImpl *&startNode, long &startOffset);
63 static bool lastRunAt(RenderObject *renderNode, int y, NodeImpl *&endNode, long &endOffset);
64 static bool startAndEndLineNodesIncludingNode(DOM::NodeImpl *node, int offset, Selection &selection);
65 #endif
66
67
68 Selection::Selection()
69 {
70     init();
71 }
72
73 Selection::Selection(NodeImpl *node, long offset)
74 {
75     init();
76
77         setBaseNode(node);
78         setExtentNode(node);
79         setBaseOffset(offset);
80         setExtentOffset(offset);
81
82     validate();
83 }
84
85 Selection::Selection(const Position &pos)
86 {
87     init();
88
89         setBaseNode(pos.node());
90         setExtentNode(pos.node());
91         setBaseOffset(pos.offset());
92         setExtentOffset(pos.offset());
93
94     validate();
95 }
96
97 Selection::Selection(const Position &base, const Position &extent)
98 {
99     init();
100
101         setBaseNode(base.node());
102         setExtentNode(extent.node());
103         setBaseOffset(base.offset());
104         setExtentOffset(extent.offset());
105
106     validate();
107 }
108
109 Selection::Selection(NodeImpl *baseNode, long baseOffset, NodeImpl *endNode, long endOffset)
110 {
111     init();
112
113         setBaseNode(baseNode);
114         setExtentNode(endNode);
115         setBaseOffset(baseOffset);
116         setExtentOffset(endOffset);
117
118     validate();
119 }
120
121 Selection::Selection(const Selection &o)
122 {
123     init();
124     
125         setBaseNode(o.baseNode());
126         setExtentNode(o.extentNode());
127         setBaseOffset(o.baseOffset());
128         setExtentOffset(o.extentOffset());
129
130         setStartNode(o.startNode());
131         setEndNode(o.endNode());
132         setStartOffset(o.startOffset());
133         setEndOffset(o.endOffset());
134
135     m_state = o.m_state;
136
137     m_baseIsStart = o.m_baseIsStart;
138     m_needsCaretLayout = o.m_needsCaretLayout;
139     m_modifyBiasSet = o.m_modifyBiasSet;
140     
141     // Only copy the coordinates over if the other object
142     // has had a layout, otherwise keep the current
143     // coordinates. This prevents drawing artifacts from
144     // remaining when the caret is painted and then moves,
145     // and the old rectangle needs to be repainted.
146     if (!m_needsCaretLayout) {
147         m_caretX = o.m_caretX;
148         m_caretY = o.m_caretY;
149         m_caretSize = o.m_caretSize;
150     }
151 }
152
153 void Selection::init()
154 {
155     m_baseNode = 0;
156     m_baseOffset = 0;
157     m_extentNode = 0; 
158     m_extentOffset = 0;
159     m_startNode = 0;
160     m_startOffset = 0;
161     m_endNode = 0;
162     m_endOffset = 0;
163     m_state = NONE; 
164     m_caretX = 0;
165     m_caretY = 0;
166     m_caretSize = 0;
167     m_baseIsStart = true;
168     m_needsCaretLayout = true;
169     m_modifyBiasSet = false;
170 }
171
172 Selection::~Selection()
173 {
174     if (m_baseNode)
175         m_baseNode->deref();
176     if (m_extentNode)
177         m_extentNode->deref();
178     if (m_startNode)
179         m_startNode->deref();
180     if (m_endNode)
181         m_endNode->deref();
182 }
183
184 Selection &Selection::operator=(const Selection &o)
185 {
186         setBaseNode(o.baseNode());
187         setExtentNode(o.extentNode());
188         setBaseOffset(o.baseOffset());
189         setExtentOffset(o.extentOffset());
190
191         setStartNode(o.startNode());
192         setEndNode(o.endNode());
193         setStartOffset(o.startOffset());
194         setEndOffset(o.endOffset());
195
196     m_state = o.m_state;
197
198     m_baseIsStart = o.m_baseIsStart;
199     m_needsCaretLayout = o.m_needsCaretLayout;
200     m_modifyBiasSet = o.m_modifyBiasSet;
201     
202     // Only copy the coordinates over if the other object
203     // has had a layout, otherwise keep the current
204     // coordinates. This prevents drawing artifacts from
205     // remaining when the caret is painted and then moves,
206     // and the old rectangle needs to be repainted.
207     if (!m_needsCaretLayout) {
208         m_caretX = o.m_caretX;
209         m_caretY = o.m_caretY;
210         m_caretSize = o.m_caretSize;
211     }
212     
213     return *this;
214 }
215
216 void Selection::moveTo(DOM::NodeImpl *node, long offset)
217 {
218     moveTo(node, offset, node, offset);
219 }
220
221 void Selection::moveTo(const DOM::Range &r)
222 {
223         moveTo(r.startContainer().handle(), r.startOffset(), 
224                 r.endContainer().handle(), r.endOffset());
225 }
226
227 void Selection::moveTo(const DOM::Position &pos)
228 {
229         moveTo(pos.node(), pos.offset());
230 }
231
232 void Selection::moveTo(const Selection &o)
233 {
234         moveTo(o.baseNode(), o.baseOffset(), o.extentNode(), o.extentOffset());
235 }
236
237 void Selection::moveTo(DOM::NodeImpl *baseNode, long baseOffset, DOM::NodeImpl *extentNode, long extentOffset)
238 {
239         setBaseNode(baseNode);
240         setExtentNode(extentNode);
241         setBaseOffset(baseOffset);
242         setExtentOffset(extentOffset);
243         validate();
244 }
245
246 bool Selection::modify(EAlter alter, EDirection dir, ETextGranularity granularity)
247 {
248     Position pos;
249     
250     switch (dir) {
251         // EDIT FIXME: This needs to handle bidi
252         case RIGHT:
253         case FORWARD:
254             if (alter == EXTEND) {
255                 if (!m_modifyBiasSet) {
256                     m_modifyBiasSet = true;
257                     setBaseNode(startNode());
258                     setBaseOffset(startOffset());
259                     setExtentNode(endNode());
260                     setExtentOffset(endOffset());
261                 }
262                 if (granularity == CHARACTER)
263                     pos = extentPosition().nextCharacterPosition();
264                 else if (granularity == WORD)
265                     pos = extentPosition().nextWordPosition();
266             }
267             else {
268                 m_modifyBiasSet = false;
269                 if (state() == RANGE) {
270                     if (granularity == CHARACTER)
271                         pos = endPosition();
272                     else if (granularity == WORD)
273                         pos = extentPosition().nextWordPosition();
274                 }
275                 else {
276                     if (granularity == CHARACTER)
277                         pos = extentPosition().nextCharacterPosition();
278                     else if (granularity == WORD)
279                         pos = extentPosition().nextWordPosition();
280                 }
281             }
282             break;
283         // EDIT FIXME: This needs to handle bidi
284         case LEFT:
285         case BACKWARD:
286             if (alter == EXTEND) {
287                 if (!m_modifyBiasSet) {
288                     m_modifyBiasSet = true;
289                     setBaseNode(endNode());
290                     setBaseOffset(endOffset());
291                     setExtentNode(startNode());
292                     setExtentOffset(startOffset());
293                 }
294                 if (granularity == CHARACTER)
295                     pos = extentPosition().previousCharacterPosition();
296                 else if (granularity == WORD)
297                     pos = extentPosition().previousWordPosition();
298             }
299             else {
300                 m_modifyBiasSet = false;
301                 if (state() == RANGE) {
302                     if (granularity == CHARACTER)
303                         pos = startPosition();
304                     else if (granularity == WORD)
305                         pos = extentPosition().previousWordPosition();
306                 }
307                 else {
308                     if (granularity == CHARACTER)
309                         pos = extentPosition().previousCharacterPosition();
310                     else if (granularity == WORD)
311                         pos = extentPosition().previousWordPosition();
312                 }
313             }
314             break;
315         case UP:
316             if (alter == EXTEND) {
317                 if (!m_modifyBiasSet) {
318                     m_modifyBiasSet = true;
319                     setBaseNode(endNode());
320                     setBaseOffset(endOffset());
321                     setExtentNode(startNode());
322                     setExtentOffset(startOffset());
323                 }
324                 pos = extentPosition().previousLinePosition(xPosForVerticalArrowNavigation(EXTENT));
325             }
326             else {
327                 m_modifyBiasSet = false;
328                 pos = startPosition().previousLinePosition(xPosForVerticalArrowNavigation(START, state()==RANGE));
329             }
330             break;
331         case DOWN:
332             if (alter == EXTEND) {
333                 if (!m_modifyBiasSet) {
334                     m_modifyBiasSet = true;
335                     setBaseNode(startNode());
336                     setBaseOffset(startOffset());
337                     setExtentNode(endNode());
338                     setExtentOffset(endOffset());
339                 }
340                 pos = extentPosition().nextLinePosition(xPosForVerticalArrowNavigation(EXTENT));
341             }
342             else {
343                 m_modifyBiasSet = false;
344                 pos = endPosition().nextLinePosition(xPosForVerticalArrowNavigation(END, state()==RANGE));
345             }
346             break;
347     }
348     
349     if (pos.isEmpty())
350         return false;
351     
352     if (alter == MOVE)
353         moveTo(pos.node(), pos.offset());
354     else // alter == EXTEND
355         setExtent(pos.node(), pos.offset());
356     
357     return true;
358 }
359
360 bool Selection::expandUsingGranularity(ETextGranularity granularity)
361 {
362     if (state() == NONE)
363         return false;
364         
365     validate(granularity);
366     return true;
367 }
368
369 int Selection::xPosForVerticalArrowNavigation(EPositionType type, bool recalc) const
370 {
371     int x = 0;
372
373     if (state() == NONE)
374         return x;
375
376     Position pos;
377     switch (type) {
378         case START:
379             pos = startPosition();
380             break;
381         case END:
382             pos = endPosition();
383             break;
384         case BASE:
385             pos = basePosition();
386             break;
387         case EXTENT:
388             pos = extentPosition();
389             break;
390     }
391
392     KHTMLPart *part = pos.node()->getDocument()->part();
393     if (!part)
394         return x;
395         
396     if (recalc || part->xPosForVerticalArrowNavigation() == KHTMLPart::NoXPosForVerticalArrowNavigation) {
397         int y, w, h;
398         pos.node()->renderer()->caretPos(pos.offset(), true, x, y, w, h);
399         part->setXPosForVerticalArrowNavigation(x);
400     }
401     else {
402         x = part->xPosForVerticalArrowNavigation();
403     }
404
405     return x;
406 }
407
408 void Selection::clear()
409 {
410         setBaseNode(0);
411         setExtentNode(0);
412         setBaseOffset(0);
413         setExtentOffset(0);
414         validate();
415 }
416
417 void Selection::setBase(DOM::NodeImpl *node, long offset)
418 {
419         setBaseNode(node);
420         setBaseOffset(offset);
421         validate();
422 }
423
424 void Selection::setExtent(DOM::NodeImpl *node, long offset)
425 {
426         setExtentNode(node);
427         setExtentOffset(offset);
428         validate();
429 }
430
431 void Selection::setNeedsLayout(bool flag)
432 {
433     m_needsCaretLayout = flag;
434 }
435
436 Range Selection::toRange() const
437 {
438     if (isEmpty())
439         return Range();
440
441     return Range(Node(startNode()), startOffset(), Node(endNode()), endOffset());
442 }
443
444 void Selection::layoutCaret()
445 {
446     if (isEmpty() || !startNode()->renderer()) {
447         m_caretX = m_caretY = m_caretSize = 0;
448     }
449     else {
450         int w;
451         startNode()->renderer()->caretPos(startOffset(), true, m_caretX, m_caretY, w, m_caretSize);
452     }
453
454     m_needsCaretLayout = false;
455 }
456
457 QRect Selection::getRepaintRect()
458 {
459     // EDIT FIXME: fudge a bit to make sure we don't leave behind artifacts
460     return QRect(m_caretX - 1, m_caretY - 1, 3, m_caretSize + 2);
461 }
462
463 void Selection::needsCaretRepaint()
464 {
465     if (isEmpty())
466         return;
467
468     if (!startNode()->getDocument())
469         return;
470
471     KHTMLView *v = startNode()->getDocument()->view();
472     if (!v)
473         return;
474
475     if (m_needsCaretLayout) {
476         // repaint old position and calculate new position
477         v->updateContents(getRepaintRect(), false);
478         layoutCaret();
479         
480         // EDIT FIXME: This is an unfortunate hack.
481         // Basically, we can't trust this layout position since we 
482         // can't guarantee that the check to see if we are in unrendered 
483         // content will work at this point. We may have to wait for
484         // a layout and re-render of the document to happen. So, resetting this
485         // flag will cause another caret layout to happen the first time
486         // that we try to paint the caret after this call. That one will work since
487         // it happens after the document has accounted for any editing
488         // changes which may have been done.
489         // And, we need to leave this layout here so the caret moves right 
490         // away after clicking.
491         m_needsCaretLayout = true;
492     }
493     v->updateContents(getRepaintRect(), false);
494 }
495
496 void Selection::paintCaret(QPainter *p, const QRect &rect)
497 {
498     if (isEmpty())
499         return;
500
501     if (m_state != CARET)
502         return;
503
504     if (m_needsCaretLayout) {
505         Position pos = Position(startNode(), startOffset());
506         if (!pos.inRenderedContent()) {
507             moveToRenderedContent();
508         }
509         layoutCaret();
510     }
511
512     QRect caretRect(m_caretX, m_caretY, 1, m_caretSize);
513     if (caretRect.intersects(rect)) {
514         QPen pen = p->pen();
515         pen.setStyle(Qt::SolidLine);
516         pen.setColor(Qt::black);
517         pen.setWidth(1);
518         p->setPen(pen);
519         p->drawLine(caretRect.left(), caretRect.top(), caretRect.left(), caretRect.bottom());
520     }
521 }
522
523 void Selection::setBaseNode(DOM::NodeImpl *node)
524 {
525         if (m_baseNode == node)
526                 return;
527
528         if (m_baseNode)
529                 m_baseNode->deref();
530         
531         m_baseNode = node;
532         
533         if (m_baseNode)
534                 m_baseNode->ref();
535 }
536
537 void Selection::setBaseOffset(long offset)
538 {
539         m_baseOffset = offset;
540 }
541
542 void Selection::setExtentNode(DOM::NodeImpl *node)
543 {
544         if (m_extentNode == node)
545                 return;
546
547         if (m_extentNode)
548                 m_extentNode->deref();
549         
550         m_extentNode = node;
551         
552         if (m_extentNode)
553                 m_extentNode->ref();
554 }
555         
556 void Selection::setExtentOffset(long offset)
557 {
558         m_extentOffset = offset;
559 }
560
561 void Selection::setStartNode(DOM::NodeImpl *node)
562 {
563         if (m_startNode == node)
564                 return;
565
566         if (m_startNode)
567                 m_startNode->deref();
568         
569         m_startNode = node;
570         
571         if (m_startNode)
572                 m_startNode->ref();
573 }
574
575 void Selection::setStartOffset(long offset)
576 {
577         m_startOffset = offset;
578 }
579
580 void Selection::setEndNode(DOM::NodeImpl *node)
581 {
582         if (m_endNode == node)
583                 return;
584
585         if (m_endNode)
586                 m_endNode->deref();
587         
588         m_endNode = node;
589         
590         if (m_endNode)
591                 m_endNode->ref();
592 }
593         
594 void Selection::setEndOffset(long offset)
595 {
596         m_endOffset = offset;
597 }
598
599 void Selection::validate(ETextGranularity granularity)
600 {
601     // move the base and extent nodes to their equivalent leaf positions
602     bool baseAndExtentEqual = m_baseNode == m_extentNode && m_baseOffset == m_extentOffset;
603     if (m_baseNode) {
604         Position pos = basePosition().equivalentLeafPosition();
605         m_baseNode = pos.node();
606         m_baseOffset = pos.offset();
607         if (baseAndExtentEqual) {
608             m_extentNode = pos.node();
609             m_extentOffset = pos.offset();
610         }
611     }
612     if (m_extentNode && !baseAndExtentEqual) {
613         Position pos = extentPosition().equivalentLeafPosition();
614         m_extentNode = pos.node();
615         m_extentOffset = pos.offset();
616     }
617
618     // make sure we do not have a dangling start or end
619         if (!m_baseNode && !m_extentNode) {
620         setBaseOffset(0);
621         setExtentOffset(0);
622         m_baseIsStart = true;
623     }
624         else if (!m_baseNode) {
625                 setBaseNode(m_extentNode);
626                 setBaseOffset(m_extentOffset);
627         m_baseIsStart = true;
628         }
629         else if (!m_extentNode) {
630                 setExtentNode(m_baseNode);
631                 setExtentOffset(m_baseOffset);
632         m_baseIsStart = true;
633         }
634     else {
635         // adjust m_baseIsStart as needed
636         if (m_baseNode == m_extentNode) {
637             if (m_baseOffset > m_extentOffset)
638                 m_baseIsStart = false;
639             else 
640                 m_baseIsStart = true;
641         }
642         else if (nodeIsBeforeNode(m_baseNode, m_extentNode))
643             m_baseIsStart = true;
644         else
645             m_baseIsStart = false;
646     }
647
648     // calculate the correct start and end positions
649 #if !APPLE_CHANGES
650     if (m_baseIsStart) {
651         setStartNode(m_baseNode);
652         setStartOffset(m_baseOffset);
653         setEndNode(m_extentNode);
654         setEndOffset(m_extentOffset);
655     }
656     else {
657         setStartNode(m_extentNode);
658         setStartOffset(m_extentOffset);
659         setEndNode(m_baseNode);
660         setEndOffset(m_baseOffset);
661     }
662 #else
663     if (granularity == CHARACTER) {
664         if (m_baseIsStart) {
665             setStartNode(m_baseNode);
666             setStartOffset(m_baseOffset);
667             setEndNode(m_extentNode);
668             setEndOffset(m_extentOffset);
669         }
670         else {
671             setStartNode(m_extentNode);
672             setStartOffset(m_extentOffset);
673             setEndNode(m_baseNode);
674             setEndOffset(m_baseOffset);
675         }
676     }
677     else if (granularity == WORD) {
678         int baseStartOffset = m_baseOffset;
679         int baseEndOffset = m_baseOffset;
680         int extentStartOffset = m_extentOffset;
681         int extentEndOffset = m_extentOffset;
682         if (m_baseNode && (m_baseNode->nodeType() == Node::TEXT_NODE || m_baseNode->nodeType() == Node::CDATA_SECTION_NODE)) {
683             DOMString t = m_baseNode->nodeValue();
684             QChar *chars = t.unicode();
685             uint len = t.length();
686             KWQFindWordBoundary(chars, len, m_baseOffset, &baseStartOffset, &baseEndOffset);
687         }
688         if (m_extentNode && (m_extentNode->nodeType() == Node::TEXT_NODE || m_extentNode->nodeType() == Node::CDATA_SECTION_NODE)) {
689             DOMString t = m_extentNode->nodeValue();
690             QChar *chars = t.unicode();
691             uint len = t.length();
692             KWQFindWordBoundary(chars, len, m_extentOffset, &extentStartOffset, &extentEndOffset);
693         }
694         if (m_baseIsStart) {
695             setStartNode(m_baseNode);
696             setStartOffset(baseStartOffset);
697             setEndNode(m_extentNode);
698             setEndOffset(extentEndOffset);
699         }
700         else {
701             setStartNode(m_extentNode);
702             setStartOffset(extentStartOffset);
703             setEndNode(m_baseNode);
704             setEndOffset(baseEndOffset);
705         }
706     }
707     else {  // granularity == LINE
708         Selection baseSelection = *this;
709         Selection extentSelection = *this;
710         if (m_baseNode && (m_baseNode->nodeType() == Node::TEXT_NODE || m_baseNode->nodeType() == Node::CDATA_SECTION_NODE)) {
711             if (startAndEndLineNodesIncludingNode(m_baseNode, m_baseOffset, baseSelection)) {
712                 setStartNode(baseSelection.baseNode());
713                 setStartOffset(baseSelection.baseOffset());
714                 setEndNode(baseSelection.extentNode());
715                 setEndOffset(baseSelection.extentOffset());
716             }
717         }
718         if (m_extentNode && (m_extentNode->nodeType() == Node::TEXT_NODE || m_extentNode->nodeType() == Node::CDATA_SECTION_NODE)) {
719             if (startAndEndLineNodesIncludingNode(m_extentNode, m_extentOffset, extentSelection)) {
720                 setStartNode(extentSelection.baseNode());
721                 setStartOffset(extentSelection.baseOffset());
722                 setEndNode(extentSelection.extentNode());
723                 setEndOffset(extentSelection.extentOffset());
724             }
725         }
726         if (m_baseIsStart) {
727             setStartNode(baseSelection.startNode());
728             setStartOffset(baseSelection.startOffset());
729             setEndNode(extentSelection.endNode());
730             setEndOffset(extentSelection.endOffset());
731         }
732         else {
733             setStartNode(extentSelection.startNode());
734             setStartOffset(extentSelection.startOffset());
735             setEndNode(baseSelection.endNode());
736             setEndOffset(baseSelection.endOffset());
737         }
738     }
739 #endif  // APPLE_CHANGES
740
741         // adjust the state
742         if (!m_startNode && !m_endNode)
743                 m_state = NONE;
744         else if (m_startNode == m_endNode && m_startOffset == m_endOffset)
745                 m_state = CARET;
746         else
747                 m_state = RANGE;
748
749     m_needsCaretLayout = true;
750     
751 #if EDIT_DEBUG
752     debugPosition();
753 #endif
754 }
755
756 bool Selection::moveToRenderedContent()
757 {
758     if (isEmpty())
759         return false;
760         
761     if (m_state != CARET)
762         return false;
763
764     Position pos = Position(startNode(), startOffset());
765     if (pos.inRenderedContent())
766         return true;
767         
768     // not currently rendered, try moving to prev
769     Position prev = pos.previousCharacterPosition();
770     if (prev != pos && prev.node()->inSameContainingEditableBlock(pos.node())) {
771         moveTo(prev);
772         return true;
773     }
774
775     // could not be moved to prev, try next
776     Position next = pos.nextCharacterPosition();
777     if (next != pos && next.node()->inSameContainingEditableBlock(pos.node())) {
778         moveTo(next);
779         return true;
780     }
781     
782     return false;
783 }
784
785 Position Selection::basePosition() const
786 {
787     return Position(baseNode(), baseOffset());
788 }
789
790 Position Selection::extentPosition() const
791 {
792     return Position(extentNode(), extentOffset());
793 }
794
795 Position Selection::startPosition() const
796 {
797     return Position(startNode(), startOffset());
798 }
799
800 Position Selection::endPosition() const
801 {
802     return Position(endNode(), endOffset());
803 }
804
805 bool Selection::nodeIsBeforeNode(NodeImpl *n1, NodeImpl *n2) 
806 {
807         if (!n1 || !n2) 
808                 return true;
809  
810         if (n1 == n2)
811                 return true;
812  
813         bool result = false;
814     int n1Depth = 0;
815     int n2Depth = 0;
816
817     // First we find the depths of the two nodes in the tree (n1Depth, n2Depth)
818     DOM::NodeImpl *n = n1;
819     while (n->parentNode()) {
820         n = n->parentNode();
821         n1Depth++;
822     }
823     n = n2;
824     while (n->parentNode()) {
825         n = n->parentNode();
826         n2Depth++;
827     }
828     // Climb up the tree with the deeper node, until both nodes have equal depth
829     while (n2Depth > n1Depth) {
830         n2 = n2->parentNode();
831         n2Depth--;
832     }
833     while (n1Depth > n2Depth) {
834         n1 = n1->parentNode();
835         n1Depth--;
836     }
837     // Climb the tree with both n1 and n2 until they have the same parent
838     while (n1->parentNode() != n2->parentNode()) {
839         n1 = n1->parentNode();
840         n2 = n2->parentNode();
841     }
842     // Iterate through the parent's children until n1 or n2 is found
843     n = n1->parentNode() ? n1->parentNode()->firstChild() : n1->firstChild();
844     while (n) {
845         if (n == n1) {
846             result = true;
847             break;
848         }
849         else if (n == n2) {
850             result = false;
851             break;
852         }
853         n = n->nextSibling();
854     }
855         return result;
856 }
857
858 #if APPLE_CHANGES
859
860 static bool firstRunAt(RenderObject *renderNode, int y, NodeImpl *&startNode, long &startOffset)
861 {
862     for (RenderObject *n = renderNode; n; n = n->nextSibling()) {
863         if (n->isText()) {
864             RenderText *textRenderer = static_cast<khtml::RenderText *>(n);
865             for (InlineTextBox* box = textRenderer->firstTextBox(); box; box = box->nextTextBox()) {
866                 if (box->m_y == y) {
867                     startNode = textRenderer->element();
868                     startOffset = box->m_start;
869                     return true;
870                 }
871             }
872         }
873         
874         if (firstRunAt(n->firstChild(), y, startNode, startOffset)) {
875             return true;
876         }
877     }
878     
879     return false;
880 }
881
882 static bool lastRunAt(RenderObject *renderNode, int y, NodeImpl *&endNode, long &endOffset)
883 {
884     RenderObject *n = renderNode;
885     if (!n) {
886         return false;
887     }
888     RenderObject *next;
889     while ((next = n->nextSibling())) {
890         n = next;
891     }
892     
893     while (1) {
894         if (lastRunAt(n->firstChild(), y, endNode, endOffset)) {
895             return true;
896         }
897     
898         if (n->isText()) {
899             RenderText *textRenderer =  static_cast<khtml::RenderText *>(n);
900             for (InlineTextBox* box = textRenderer->lastTextBox(); box; box = box->prevTextBox()) {
901                 if (box->m_y == y) {
902                     endNode = textRenderer->element();
903                     endOffset = box->m_start + box->m_len;
904                     return true;
905                 }
906             }
907         }
908         
909         if (n == renderNode) {
910             return false;
911         }
912         
913         n = n->previousSibling();
914     }
915 }
916
917 static bool startAndEndLineNodesIncludingNode(DOM::NodeImpl *node, int offset, Selection &selection)
918 {
919     if (node && (node->nodeType() == Node::TEXT_NODE || node->nodeType() == Node::CDATA_SECTION_NODE)) {
920         int pos;
921         int selectionPointY;
922         RenderText *renderer = static_cast<RenderText *>(node->renderer());
923         InlineTextBox * run = renderer->findNextInlineTextBox( offset, pos );
924         DOMString t = node->nodeValue();
925         
926         if (!run)
927             return false;
928             
929         selectionPointY = run->m_y;
930         
931         // Go up to first non-inline element.
932         khtml::RenderObject *renderNode = renderer;
933         while (renderNode && renderNode->isInline())
934             renderNode = renderNode->parent();
935         
936         renderNode = renderNode->firstChild();
937         
938         DOM::NodeImpl *startNode = 0;
939         DOM::NodeImpl *endNode = 0;
940         long startOffset;
941         long endOffset;
942         
943         // Look for all the first child in the block that is on the same line
944         // as the selection point.
945         if (!firstRunAt (renderNode, selectionPointY, startNode, startOffset))
946             return false;
947     
948         // Look for all the last child in the block that is on the same line
949         // as the selection point.
950         if (!lastRunAt (renderNode, selectionPointY, endNode, endOffset))
951             return false;
952         
953         selection.moveTo(startNode, startOffset, endNode, endOffset);
954         
955         return true;
956     }
957     return false;
958 }
959
960 void Selection::debugRenderer(RenderObject *r, bool selected) const
961 {
962     if (r->node()->isElementNode()) {
963         ElementImpl *element = static_cast<ElementImpl *>(r->node());
964         fprintf(stderr, "%s%s\n", selected ? "==> " : "    ", element->tagName().string().latin1());
965     }
966     else if (r->isText()) {
967         RenderText *textRenderer = static_cast<RenderText *>(r);
968         if (textRenderer->stringLength() == 0 || !textRenderer->firstTextBox()) {
969             fprintf(stderr, "%s#text (empty)\n", selected ? "==> " : "    ");
970             return;
971         }
972         
973         static const int max = 36;
974         QString text = DOMString(textRenderer->string()).string();
975         int textLength = text.length();
976         if (selected) {
977             int offset = 0;
978             if (r->node() == startNode())
979                 offset = startOffset();
980             else if (r->node() == endNode())
981                 offset = endOffset();
982                 
983             int pos;
984             InlineTextBox *box = textRenderer->findNextInlineTextBox(offset, pos);
985             text = text.mid(box->m_start, box->m_len);
986             
987             QString show;
988             int mid = max / 2;
989             int caret = 0;
990             
991             // text is shorter than max
992             if (textLength < max) {
993                 show = text;
994                 caret = pos;
995             }
996             
997             // too few characters to left
998             else if (pos - mid < 0) {
999                 show = text.left(max - 3) + "...";
1000                 caret = pos;
1001             }
1002             
1003             // enough characters on each side
1004             else if (pos - mid >= 0 && pos + mid <= textLength) {
1005                 show = "..." + text.mid(pos - mid + 3, max - 6) + "...";
1006                 caret = mid;
1007             }
1008             
1009             // too few characters on right
1010             else {
1011                 show = "..." + text.right(max - 3);
1012                 caret = pos - (textLength - show.length());
1013             }
1014             
1015             show = show.replace("\n", " ");
1016             show = show.replace("\r", " ");
1017             fprintf(stderr, "==> #text : \"%s\" at offset %d\n", show.latin1(), pos);
1018             fprintf(stderr, "           ");
1019             for (int i = 0; i < caret; i++)
1020                 fprintf(stderr, " ");
1021             fprintf(stderr, "^\n");
1022         }
1023         else {
1024             if ((int)text.length() > max)
1025                 text = text.left(max - 3) + "...";
1026             else
1027                 text = text.left(max);
1028             fprintf(stderr, "    #text : \"%s\"\n", text.latin1());
1029         }
1030     }
1031 }
1032
1033 void Selection::debugPosition() const
1034 {
1035     if (!startNode())
1036         return;
1037
1038     //static int context = 5;
1039     
1040     //RenderObject *r = 0;
1041
1042     fprintf(stderr, "Selection =================\n");
1043
1044     if (startPosition() == endPosition()) {
1045         Position pos = startPosition();
1046         Position upstream = pos.equivalentUpstreamPosition();
1047         Position downstream = pos.equivalentDownstreamPosition();
1048         fprintf(stderr, "upstream:   %s %p:%d\n", getTagName(upstream.node()->id()).string().latin1(), upstream.node(), upstream.offset());
1049         fprintf(stderr, "pos:        %s %p:%d\n", getTagName(pos.node()->id()).string().latin1(), pos.node(), pos.offset());
1050         fprintf(stderr, "downstream: %s %p:%d\n", getTagName(downstream.node()->id()).string().latin1(), downstream.node(), downstream.offset());
1051     }
1052     else {
1053         Position pos = startPosition();
1054         Position upstream = pos.equivalentUpstreamPosition();
1055         Position downstream = pos.equivalentDownstreamPosition();
1056         fprintf(stderr, "upstream:   %s %p:%d\n", getTagName(upstream.node()->id()).string().latin1(), upstream.node(), upstream.offset());
1057         fprintf(stderr, "start:      %s %p:%d\n", getTagName(pos.node()->id()).string().latin1(), pos.node(), pos.offset());
1058         fprintf(stderr, "downstream: %s %p:%d\n", getTagName(downstream.node()->id()).string().latin1(), downstream.node(), downstream.offset());
1059         fprintf(stderr, "-----------------------------------\n");
1060         pos = endPosition();
1061         upstream = pos.equivalentUpstreamPosition();
1062         downstream = pos.equivalentDownstreamPosition();
1063         fprintf(stderr, "upstream:   %s %p:%d\n", getTagName(upstream.node()->id()).string().latin1(), upstream.node(), upstream.offset());
1064         fprintf(stderr, "end:        %s %p:%d\n", getTagName(pos.node()->id()).string().latin1(), pos.node(), pos.offset());
1065         fprintf(stderr, "downstream: %s %p:%d\n", getTagName(downstream.node()->id()).string().latin1(), downstream.node(), downstream.offset());
1066         fprintf(stderr, "-----------------------------------\n");
1067     }
1068           
1069 #if 0
1070     int back = 0;
1071     r = startNode()->renderer();
1072     for (int i = 0; i < context; i++, back++) {
1073         if (r->previousRenderer())
1074             r = r->previousRenderer();
1075         else
1076             break;
1077     }
1078     for (int i = 0; i < back; i++) {
1079         debugRenderer(r, false);
1080         r = r->nextRenderer();
1081     }
1082
1083
1084     fprintf(stderr, "\n");
1085
1086     if (startNode() == endNode())
1087         debugRenderer(startNode()->renderer(), true);
1088     else
1089         for (r = startNode()->renderer(); r && r != endNode()->renderer(); r = r->nextRenderer())
1090             debugRenderer(r, true);
1091     
1092     fprintf(stderr, "\n");
1093     
1094     r = endNode()->renderer();
1095     for (int i = 0; i < context; i++) {
1096         if (r->nextRenderer()) {
1097             r = r->nextRenderer();
1098             debugRenderer(r, false);
1099         }
1100         else
1101             break;
1102     }
1103 #endif
1104
1105     fprintf(stderr, "================================\n");
1106 }
1107
1108 #endif
1109
1110 } // namespace DOM