Reviewed by Trey
[WebKit-https.git] / WebCore / khtml / xml / dom_position.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 "dom_position.h"
27
28 #include "helper.h"
29 #include "htmltags.h"
30 #include "khtml_text_operations.h"
31 #include "qstring.h"
32 #include "rendering/render_block.h"
33 #include "rendering/render_line.h"
34 #include "rendering/render_object.h"
35 #include "rendering/render_style.h"
36 #include "rendering/render_text.h"
37 #include "xml/dom_positioniterator.h"
38 #include "xml/dom_elementimpl.h"
39 #include "xml/dom_nodeimpl.h"
40
41 #if APPLE_CHANGES
42 #include "KWQAssertions.h"
43 #include "KWQLogging.h"
44 #else
45 #define ASSERT(assertion) assert(assertion)
46 #define LOG(channel, formatAndArgs...) ((void)0)
47 #endif
48
49 using khtml::CharacterIterator;
50 using khtml::InlineBox;
51 using khtml::InlineFlowBox;
52 using khtml::InlineTextBox;
53 using khtml::RenderBlock;
54 using khtml::RenderObject;
55 using khtml::RenderText;
56 using khtml::RootInlineBox;
57 using khtml::SimplifiedBackwardsTextIterator;
58 using khtml::TextIterator;
59
60 namespace DOM {
61
62 static bool renderersOnDifferentLine(RenderObject *r1, long o1, RenderObject *r2, long o2)
63 {
64     InlineBox *b1 = r1 ? r1->inlineBox(o1) : 0;
65     InlineBox *b2 = r2 ? r2->inlineBox(o2) : 0;
66     return (b1 && b2 && b1->root() != b2->root());
67 }
68
69 static NodeImpl *nextRenderedEditable(NodeImpl *node)
70 {
71     while (1) {
72         node = node->nextEditable();
73         if (!node)
74             return 0;
75         if (!node->renderer())
76             continue;
77         if (node->renderer()->inlineBox(0))
78             return node;
79     }
80     return 0;
81 }
82
83 static NodeImpl *previousRenderedEditable(NodeImpl *node)
84 {
85     while (1) {
86         node = node->previousEditable();
87         if (!node)
88             return 0;
89         if (!node->renderer())
90             continue;
91         if (node->renderer()->inlineBox(0))
92             return node;
93     }
94     return 0;
95 }
96
97
98 Position::Position(NodeImpl *node, long offset) 
99     : m_node(0), m_offset(offset) 
100
101     if (node) {
102         m_node = node;
103         m_node->ref();
104     }
105 };
106
107 Position::Position(const Position &o)
108     : m_node(0), m_offset(o.offset()) 
109 {
110     if (o.node()) {
111         m_node = o.node();
112         m_node->ref();
113     }
114 }
115
116 Position::~Position() {
117     if (m_node) {
118         m_node->deref();
119     }
120 }
121
122 Position &Position::operator=(const Position &o)
123 {
124     if (m_node) {
125         m_node->deref();
126     }
127     m_node = o.node();
128     if (m_node) {
129         m_node->ref();
130     }
131
132     m_offset = o.offset();
133     
134     return *this;
135 }
136
137 ElementImpl *Position::element() const
138 {
139     if (isEmpty())
140         return 0;
141         
142     NodeImpl *n = node();
143     for (; n && !n->isElementNode(); n = n->parentNode()); //loop
144         
145     return static_cast<ElementImpl *>(n);
146 }
147
148 long Position::renderedOffset() const
149 {
150     if (!node()->isTextNode())
151         return offset();
152    
153     if (!node()->renderer())
154         return offset();
155                     
156     long result = 0;
157     RenderText *textRenderer = static_cast<RenderText *>(node()->renderer());
158     for (InlineTextBox *box = textRenderer->firstTextBox(); box; box = box->nextTextBox()) {
159         long start = box->m_start;
160         long end = box->m_start + box->m_len;
161         if (offset() < start)
162             return result;
163         if (offset() <= end) {
164             result += offset() - start;
165             return result;
166         }
167         result += box->m_len;
168     }
169     return result;
170 }
171
172 Position Position::equivalentLeafPosition() const
173 {
174     if (isEmpty())
175         return Position();
176
177     if (!node()->renderer() || !node()->renderer()->firstChild())
178         return *this;
179     
180     NodeImpl *n = node();
181     int count = 0;
182     while (1) {
183         n = n->nextLeafNode();
184         if (!n || !n->inSameContainingBlockFlowElement(node()))
185             return *this;
186         if (count + n->maxOffset() >= offset()) {
187             count = offset() - count;
188             break;
189         }
190         count += n->maxOffset();
191     }
192     return Position(n, count);
193 }
194
195 Position Position::previousRenderedEditablePosition() const
196 {
197     if (isEmpty())
198         return Position();
199
200     if (node()->isContentEditable() && node()->hasChildNodes() == false && inRenderedContent())
201         return *this;
202
203     NodeImpl *n = node();
204     while (1) {
205         n = n->previousEditable();
206         if (!n)
207             return Position();
208         if (n->renderer() && n->renderer()->style()->visibility() == khtml::VISIBLE)
209             break;
210     }
211     
212     return Position(n, 0);
213 }
214
215 Position Position::nextRenderedEditablePosition() const
216 {
217     if (isEmpty())
218         return Position();
219
220     if (node()->isContentEditable() && node()->hasChildNodes() == false && inRenderedContent())
221         return *this;
222
223     NodeImpl *n = node();
224     while (1) {
225         n = n->nextEditable();
226         if (!n)
227             return Position();
228         if (n->renderer() && n->renderer()->style()->visibility() == khtml::VISIBLE)
229             break;
230     }
231     
232     return Position(n, 0);
233 }
234
235 Position Position::previousCharacterPosition() const
236 {
237     if (isEmpty())
238         return Position();
239
240     NodeImpl *fromRootEditableElement = node()->rootEditableElement();
241     PositionIterator it(*this);
242
243     bool atStartOfLine = isFirstRenderedPositionOnLine();
244     bool rendered = inRenderedContent();
245     
246     while (!it.atStart()) {
247         Position pos = it.previous();
248
249         if (pos.node()->rootEditableElement() != fromRootEditableElement)
250             return *this;
251
252         if (atStartOfLine || !rendered) {
253             if (pos.inRenderedContent())
254                 return pos;
255         }
256         else if (rendersInDifferentPosition(pos))
257             return pos;
258     }
259     
260     return *this;
261 }
262
263 Position Position::nextCharacterPosition() const
264 {
265     if (isEmpty())
266         return Position();
267
268     NodeImpl *fromRootEditableElement = node()->rootEditableElement();
269     PositionIterator it(*this);
270
271     bool atEndOfLine = isLastRenderedPositionOnLine();
272     bool rendered = inRenderedContent();
273     
274     while (!it.atEnd()) {
275         Position pos = it.next();
276
277         if (pos.node()->rootEditableElement() != fromRootEditableElement)
278             return *this;
279
280         if (atEndOfLine || !rendered) {
281             if (pos.inRenderedContent())
282                 return pos;
283         }
284         else if (rendersInDifferentPosition(pos))
285             return pos;
286     }
287     
288     return *this;
289 }
290
291 Position Position::previousWordBoundary() const
292 {
293     if (isEmpty())
294         return Position();
295
296     Position pos = *this;
297     int tries = 0;
298     while (tries < 2) {
299         if (pos.node()->nodeType() == Node::TEXT_NODE || pos.node()->nodeType() == Node::CDATA_SECTION_NODE) {
300             DOMString t = pos.node()->nodeValue();
301             QChar *chars = t.unicode();
302             uint len = t.length();
303             int start, end;
304             khtml::findWordBoundary(chars, len, pos.offset(), &start, &end);
305             pos = Position(pos.node(), start);
306             if (pos != *this)
307                 return pos;
308             else
309                 pos = pos.previousCharacterPosition();
310         }
311         else {
312             pos = Position(pos.node(), pos.node()->caretMinOffset());
313             if (pos != *this)
314                 return pos;
315         }
316         tries++;
317     }
318     
319     return *this;
320 }
321
322 Position Position::nextWordBoundary() const
323 {
324     if (isEmpty())
325         return Position();
326
327     Position pos = *this;
328     int tries = 0;
329     while (tries < 2) {
330         if (pos.node()->nodeType() == Node::TEXT_NODE || pos.node()->nodeType() == Node::CDATA_SECTION_NODE) {
331             DOMString t = pos.node()->nodeValue();
332             QChar *chars = t.unicode();
333             uint len = t.length();
334             int start, end;
335             khtml::findWordBoundary(chars, len, pos.offset(), &start, &end);
336             pos = Position(pos.node(), end);
337             if (pos != *this)
338                 return pos;
339             else
340                 pos = pos.nextCharacterPosition();
341         }
342         else {
343             pos = Position(pos.node(), pos.node()->caretMaxOffset());
344             if (pos != *this)
345                 return pos;
346         }
347         tries++;
348     }
349     
350     return *this;
351 }
352
353 Position Position::previousWordPosition() const
354 {
355     if (isEmpty())
356         return Position();
357
358     Range searchRange(node()->getDocument());
359     searchRange.setStartBefore(node()->getDocument()->documentElement());
360     Position end(equivalentRangeCompliantPosition());
361     searchRange.setEnd(end.node(), end.offset());
362     SimplifiedBackwardsTextIterator it(searchRange);
363     QString string;
364     unsigned next = 0;
365     while (!it.atEnd() && it.length() > 0) {
366         // Keep asking the iterator for chunks until the nextWordFromIndex() function
367         // returns a non-zero value.
368         string.prepend(it.characters(), it.length());
369         next = khtml::nextWordFromIndex(const_cast<QChar *>(string.unicode()), string.length(), string.length(), false);
370         if (next != 0)
371             break;
372         it.advance();
373     }
374     
375     Position pos(*this);
376     if (it.atEnd() && next == 0) {
377         Range range(it.range());
378         pos = Position(range.startContainer().handle(), range.startOffset());
379     }
380     else if (!it.atEnd() && it.length() == 0) {
381         // Got a zero-length chunk.
382         // This means we have hit a replaced element.
383         // Make a check to see if the position should be before or after the replaced element
384         // by performing an additional check with a modified string which uses an "X" 
385         // character to stand in for the replaced element.
386         QChar chars[2];
387         chars[0] = 'X';
388         chars[1] = ' ';
389         string.prepend(chars, 2);
390         unsigned pastImage = khtml::nextWordFromIndex(const_cast<QChar *>(string.unicode()), string.length(), string.length(), false);
391         Range range(it.range());
392         if (pastImage == 0)
393             pos = Position(range.startContainer().handle(), range.startOffset());
394         else
395             pos = Position(range.endContainer().handle(), range.endOffset());
396     }
397     else if (next != 0) {
398         // The simpler iterator used in this function, as compared to the one used in 
399         // nextWordPosition(), gives us results we can use directly without having to 
400         // iterate again to translate the next value into a DOM position. 
401         NodeImpl *node = it.range().startContainer().handle();
402         if (node->isTextNode()) {
403             // The next variable contains a usable index into a text node
404             pos = Position(node, next);
405         }
406         else {
407             // If we are not in a text node, we ended on a node boundary, so the
408             // range start offset should be used.
409             pos = Position(node, it.range().startOffset());
410         }
411     }
412     pos = pos.equivalentDeepPosition().closestRenderedPosition(UPSTREAM);
413     return pos;
414 }
415
416 Position Position::nextWordPosition() const
417 {
418     if (isEmpty())
419         return Position();
420
421     Range searchRange(node()->getDocument());
422     Position start(equivalentRangeCompliantPosition());
423     searchRange.setStart(start.node(), start.offset());
424     searchRange.setEndAfter(node()->getDocument()->documentElement());
425     TextIterator it(searchRange);
426     QString string;
427     unsigned next = 0;
428     while (!it.atEnd() && it.length() > 0) {
429         // Keep asking the iterator for chunks until the nextWordFromIndex() function
430         // returns a value not equal to the length of the string passed to it.
431         string.append(it.characters(), it.length());
432         next = khtml::nextWordFromIndex(const_cast<QChar *>(string.unicode()), string.length(), 0, true);
433         if (next != string.length())
434             break;
435         it.advance();
436     }
437     
438     Position pos(*this);
439     if (it.atEnd() && next == string.length()) {
440         Range range(it.range());
441         pos = Position(range.startContainer().handle(), range.startOffset());
442     }
443     else if (!it.atEnd() && it.length() == 0) {
444         // Got a zero-length chunk.
445         // This means we have hit a replaced element.
446         // Make a check to see if the position should be before or after the replaced element
447         // by performing an additional check with a modified string which uses an "X" 
448         // character to stand in for the replaced element.
449         QChar chars[2];
450         chars[0] = ' ';
451         chars[1] = 'X';
452         string.append(chars, 2);
453         unsigned pastImage = khtml::nextWordFromIndex(const_cast<QChar *>(string.unicode()), string.length(), 0, true);
454         Range range(it.range());
455         if (next != pastImage)
456             pos = Position(range.endContainer().handle(), range.endOffset());
457         else
458             pos = Position(range.startContainer().handle(), range.startOffset());
459     }
460     else if (next != 0) {
461         // Use the character iterator to translate the next value into a DOM position.
462         CharacterIterator charIt(searchRange);
463         charIt.advance(next - 1);
464         pos = Position(charIt.range().endContainer().handle(), charIt.range().endOffset());
465     }
466     pos = pos.equivalentDeepPosition().closestRenderedPosition(UPSTREAM);
467     return pos;
468 }
469
470 Position Position::previousLinePosition(int x) const
471 {
472     if (!node())
473         return Position();
474
475     if (!node()->renderer())
476         return *this;
477
478     RenderBlock *containingBlock = 0;
479     RootInlineBox *root = 0;
480     InlineBox *box = node()->renderer()->inlineBox(offset());
481     if (box) {
482         root = box->root()->prevRootBox();
483         if (root)
484             containingBlock = node()->renderer()->containingBlock();
485     }
486
487     if (!root) {
488         // This containing editable block does not have a previous line.
489         // Need to move back to previous containing editable block in this root editable
490         // block and find the last root line box in that block.
491         NodeImpl *startBlock = node()->enclosingBlockFlowElement();
492         NodeImpl *n = node()->previousEditable();
493         while (n && startBlock == n->enclosingBlockFlowElement())
494             n = n->previousEditable();
495         while (n) {
496             if (!n->inSameRootEditableElement(node()))
497                 break;
498             Position pos(n, n->caretMaxOffset());
499             if (pos.inRenderedContent()) {
500                 ASSERT(n->renderer());
501                 box = n->renderer()->inlineBox(n->caretMaxOffset());
502                 if (box) {
503                     // previous root line box found
504                     root = box->root();
505                     containingBlock = n->renderer()->containingBlock();
506                     break;
507                 }
508                 else {
509                     return pos;
510                 }
511             }
512             n = n->previousEditable();
513         }
514     }
515     
516     if (root) {
517         int absx, absy;
518         containingBlock->absolutePosition(absx, absy);
519         RenderObject *renderer = root->closestLeafChildForXPos(x, absx)->object();
520         return renderer->positionForCoordinates(x, absy + root->topOverflow());
521     }
522     
523     return *this;
524 }
525
526 Position Position::nextLinePosition(int x) const
527 {
528     if (!node())
529         return Position();
530
531     if (!node()->renderer())
532         return *this;
533
534     RenderBlock *containingBlock = 0;
535     RootInlineBox *root = 0;
536     InlineBox *box = node()->renderer()->inlineBox(offset());
537     if (box) {
538         root = box->root()->nextRootBox();
539         if (root)
540             containingBlock = node()->renderer()->containingBlock();
541     }
542
543     if (!root) {
544         // This containing editable block does not have a next line.
545         // Need to move forward to next containing editable block in this root editable
546         // block and find the first root line box in that block.
547         NodeImpl *startBlock = node()->enclosingBlockFlowElement();
548         NodeImpl *n = node()->nextEditable();
549         while (n && startBlock == n->enclosingBlockFlowElement())
550             n = n->nextEditable();
551         while (n) {
552             if (!n->inSameRootEditableElement(node()))
553                 break;
554             Position pos(n, n->caretMinOffset());
555             if (pos.inRenderedContent()) {
556                 ASSERT(n->renderer());
557                 box = n->renderer()->inlineBox(n->caretMinOffset());
558                 if (box) {
559                     // next root line box found
560                     root = box->root();
561                     containingBlock = n->renderer()->containingBlock();
562                     break;
563                 }
564                 else {
565                     return pos;
566                 }
567             }
568             n = n->nextEditable();
569         }
570     }
571     
572     if (root) {
573         int absx, absy;
574         containingBlock->absolutePosition(absx, absy);
575         RenderObject *renderer = root->closestLeafChildForXPos(x, absx)->object();
576         return renderer->positionForCoordinates(x, absy + root->topOverflow());
577     }
578
579     return *this;
580 }
581
582 Position Position::equivalentUpstreamPosition() const
583 {
584     if (!node())
585         return Position();
586
587     NodeImpl *block = node()->enclosingBlockFlowElement();
588     
589     PositionIterator it(*this);            
590     for (; !it.atStart(); it.previous()) {   
591         NodeImpl *currentBlock = it.current().node()->enclosingBlockFlowElement();
592         if (block != currentBlock)
593             return it.next();
594
595         RenderObject *renderer = it.current().node()->renderer();
596         if (!renderer)
597             continue;
598
599         if (renderer->style()->visibility() != khtml::VISIBLE)
600             continue;
601
602         if (renderer->isBlockFlow() || renderer->isReplaced() || renderer->isBR()) {
603             if (it.current().offset() >= renderer->caretMaxOffset())
604                 return Position(it.current().node(), renderer->caretMaxOffset());
605             else
606                 continue;
607         }
608
609         if (renderer->isText() && static_cast<RenderText *>(renderer)->firstTextBox()) {
610             if (it.current().node() != node())
611                 return Position(it.current().node(), renderer->caretMaxOffset());
612
613             if (it.current().offset() < 0)
614                 continue;
615             uint textOffset = it.current().offset();
616
617             RenderText *textRenderer = static_cast<RenderText *>(renderer);
618             for (InlineTextBox *box = textRenderer->firstTextBox(); box; box = box->nextTextBox()) {
619                 if (textOffset > box->start() && textOffset <= box->start() + box->len())
620                     return it.current();
621                 else if (box != textRenderer->lastTextBox() && 
622                          !box->nextOnLine() && 
623                          textOffset == box->start() + box->len() + 1)
624                     return it.current();
625             }
626         }
627     }
628     
629     return it.current();
630 }
631
632 Position Position::equivalentDownstreamPosition() const
633 {
634     if (!node())
635         return Position();
636
637     NodeImpl *block = node()->enclosingBlockFlowElement();
638     
639     PositionIterator it(*this);            
640     for (; !it.atEnd(); it.next()) {   
641         NodeImpl *currentBlock = it.current().node()->enclosingBlockFlowElement();
642         if (block != currentBlock)
643             return it.previous();
644
645         RenderObject *renderer = it.current().node()->renderer();
646         if (!renderer)
647             continue;
648
649         if (renderer->style()->visibility() != khtml::VISIBLE)
650             continue;
651
652         if (renderer->isBlockFlow() || renderer->isReplaced() || renderer->isBR()) {
653             if (it.current().offset() <= renderer->caretMinOffset())
654                 return Position(it.current().node(), renderer->caretMinOffset());
655             else
656                 continue;
657         }
658
659         if (renderer->isText() && static_cast<RenderText *>(renderer)->firstTextBox()) {
660             if (it.current().node() != node())
661                 return Position(it.current().node(), renderer->caretMinOffset());
662
663             if (it.current().offset() < 0)
664                 continue;
665             uint textOffset = it.current().offset();
666
667             RenderText *textRenderer = static_cast<RenderText *>(renderer);
668             for (InlineTextBox *box = textRenderer->firstTextBox(); box; box = box->nextTextBox()) {
669                 if (textOffset >= box->start() && textOffset <= box->end())
670                     return it.current();
671                 else if (box != textRenderer->lastTextBox() && 
672                          !box->nextOnLine() && 
673                          textOffset == box->start() + box->len())
674                     return it.current();
675             }
676         }
677     }
678     
679     return it.current();
680 }
681
682 Position Position::equivalentRangeCompliantPosition() const
683 {
684     if (isEmpty())
685         return *this;
686
687     if (!node()->parentNode())
688         return *this;
689
690     RenderObject *renderer = node()->renderer();
691     if (!renderer)
692         return *this;
693         
694     if (!renderer->isReplaced() && !renderer->isBR())
695         return *this;
696     
697     int o = 0;
698     const NodeImpl *n = node();
699     while ((n = n->previousSibling()))
700         o++;
701     
702     return Position(node()->parentNode(), o + offset());
703 }
704
705 Position Position::equivalentShallowPosition() const
706 {
707     if (isEmpty())
708         return *this;
709
710     Position pos(*this);
711     while (pos.offset() == pos.node()->caretMinOffset() && pos.node()->parentNode() && pos.node() == pos.node()->parentNode()->firstChild())
712         pos = Position(pos.node()->parentNode(), 0);
713     return pos;
714 }
715
716 Position Position::equivalentDeepPosition() const
717 {
718     if (isEmpty() || node()->isAtomicNode())
719         return *this;
720
721     NodeImpl *child = 0;
722     Position pos(*this);
723     if (offset() >= (int)node()->childNodeCount()) {
724         child = node()->lastChild();
725         pos = Position(child, child->caretMaxOffset());
726         ASSERT(child);
727         while (!child->isAtomicNode() && pos.node()->hasChildNodes()) {
728             child = pos.node()->lastChild();
729             ASSERT(child);
730             pos = Position(child, child->caretMaxOffset());
731         }
732     }
733     else {
734         child = node()->childNode(offset());
735         ASSERT(child);
736         pos = Position(child, 0);
737         while (!child->isAtomicNode() && pos.node()->hasChildNodes()) {
738             child = pos.node()->firstChild();
739             ASSERT(child);
740             pos = Position(child, 0);
741         }
742     }
743     return pos;
744 }
745
746 Position Position::closestRenderedPosition(EAffinity affinity) const
747 {
748     if (isEmpty() || inRenderedContent())
749         return *this;
750
751     Position pos;
752     PositionIterator it(*this);
753     
754     switch (affinity) {
755         case UPSTREAM:
756             // look upstream first
757             it.setPosition(*this);
758             while (!it.atStart()) {
759                 it.previous();
760                 if (it.current().inRenderedContent())
761                     return it.current();
762             }
763             // if this does not find something rendered, look downstream
764             it.setPosition(*this);
765             while (!it.atEnd()) {
766                 it.next();
767                 if (it.current().inRenderedContent())
768                     return it.current();
769             }
770             break;
771         case DOWNSTREAM:
772             // look downstream first
773             it.setPosition(*this);
774             while (!it.atEnd()) {
775                 it.next();
776                 if (it.current().inRenderedContent())
777                     return it.current();
778             }
779             // if this does not find something rendered, look upstream
780             it.setPosition(*this);
781             while (!it.atStart()) {
782                 it.previous();
783                 if (it.current().inRenderedContent())
784                     return it.current();
785             }
786             break;
787     }
788     
789     return Position();
790 }
791
792 bool Position::atStartOfContainingEditableBlock() const
793 {
794     return renderedOffset() == 0 && inFirstEditableInContainingEditableBlock();
795 }
796
797 bool Position::atStartOfRootEditableElement() const
798 {
799     return renderedOffset() == 0 && inFirstEditableInRootEditableElement();
800 }
801
802 bool Position::inRenderedContent() const
803 {
804     if (isEmpty())
805         return false;
806         
807     RenderObject *renderer = node()->renderer();
808     if (!renderer)
809         return false;
810     
811     if (renderer->style()->visibility() != khtml::VISIBLE)
812         return false;
813
814     if (renderer->isBR() && static_cast<RenderText *>(renderer)->firstTextBox()) {
815         return offset() == 0;
816     }
817     else if (renderer->isText()) {
818         RenderText *textRenderer = static_cast<RenderText *>(renderer);
819         for (InlineTextBox *box = textRenderer->firstTextBox(); box; box = box->nextTextBox()) {
820             if (offset() >= box->m_start && offset() <= box->m_start + box->m_len) {
821                 return true;
822             }
823             else if (offset() < box->m_start) {
824                 // The offset we're looking for is before this node
825                 // this means the offset must be in content that is
826                 // not rendered. Return false.
827                 return false;
828             }
829         }
830     }
831     else if (offset() >= renderer->caretMinOffset() && offset() <= renderer->caretMaxOffset()) {
832         // don't return containing editable blocks unless they are empty
833         if (node()->enclosingBlockFlowElement() == node() && node()->firstChild())
834             return false;
835         return true;
836     }
837     
838     return false;
839 }
840
841 bool Position::inRenderedText() const
842 {
843     if (!node()->isTextNode())
844         return false;
845         
846     RenderObject *renderer = node()->renderer();
847     if (!renderer)
848         return false;
849     
850     RenderText *textRenderer = static_cast<RenderText *>(renderer);
851     for (InlineTextBox *box = textRenderer->firstTextBox(); box; box = box->nextTextBox()) {
852         if (offset() < box->m_start) {
853             // The offset we're looking for is before this node
854             // this means the offset must be in content that is
855             // not rendered. Return false.
856             return false;
857         }
858         if (offset() >= box->m_start && offset() <= box->m_start + box->m_len)
859             return true;
860     }
861     
862     return false;
863 }
864
865 bool Position::rendersOnSameLine(const Position &pos) const
866 {
867     if (isEmpty() || pos.isEmpty())
868         return false;
869
870     if (node() == pos.node() && offset() == pos.offset())
871         return true;
872
873     if (node()->enclosingBlockFlowElement() != pos.node()->enclosingBlockFlowElement())
874         return false;
875
876     RenderObject *renderer = node()->renderer();
877     if (!renderer)
878         return false;
879     
880     RenderObject *posRenderer = pos.node()->renderer();
881     if (!posRenderer)
882         return false;
883
884     if (renderer->style()->visibility() != khtml::VISIBLE ||
885         posRenderer->style()->visibility() != khtml::VISIBLE)
886         return false;
887
888     return renderersOnDifferentLine(renderer, offset(), posRenderer, pos.offset());
889 }
890
891 bool Position::rendersInDifferentPosition(const Position &pos) const
892 {
893     if (isEmpty() || pos.isEmpty())
894         return false;
895
896     RenderObject *renderer = node()->renderer();
897     if (!renderer)
898         return false;
899     
900     RenderObject *posRenderer = pos.node()->renderer();
901     if (!posRenderer)
902         return false;
903
904     if (renderer->style()->visibility() != khtml::VISIBLE ||
905         posRenderer->style()->visibility() != khtml::VISIBLE)
906         return false;
907     
908     if (node() == pos.node()) {
909         if (node()->id() == ID_BR)
910             return false;
911
912         if (offset() == pos.offset())
913             return false;
914             
915         if (!node()->isTextNode() && !pos.node()->isTextNode()) {
916             if (offset() != pos.offset())
917                 return true;
918         }
919     }
920     
921     if (node()->id() == ID_BR && pos.inRenderedContent())
922         return true;
923                 
924     if (pos.node()->id() == ID_BR && inRenderedContent())
925         return true;
926                 
927     if (node()->enclosingBlockFlowElement() != pos.node()->enclosingBlockFlowElement())
928         return true;
929
930     if (node()->isTextNode() && !inRenderedText())
931         return false;
932
933     if (pos.node()->isTextNode() && !pos.inRenderedText())
934         return false;
935
936     long thisRenderedOffset = renderedOffset();
937     long posRenderedOffset = pos.renderedOffset();
938
939     if (renderer == posRenderer && thisRenderedOffset == posRenderedOffset)
940         return false;
941
942     LOG(Editing, "onDifferentLine:        %s\n", renderersOnDifferentLine(renderer, offset(), posRenderer, pos.offset()) ? "YES" : "NO");
943     LOG(Editing, "renderer:               %p [%p]\n", renderer, renderer ? renderer->inlineBox(offset()) : 0);
944     LOG(Editing, "thisRenderedOffset:         %d\n", thisRenderedOffset);
945     LOG(Editing, "posRenderer:            %p [%p]\n", posRenderer, posRenderer ? posRenderer->inlineBox(offset()) : 0);
946     LOG(Editing, "posRenderedOffset:      %d\n", posRenderedOffset);
947     LOG(Editing, "node min/max:           %d:%d\n", node()->caretMinOffset(), node()->caretMaxRenderedOffset());
948     LOG(Editing, "pos node min/max:       %d:%d\n", pos.node()->caretMinOffset(), pos.node()->caretMaxRenderedOffset());
949     LOG(Editing, "----------------------------------------------------------------------\n");
950
951     InlineBox *b1 = renderer ? renderer->inlineBox(offset()) : 0;
952     InlineBox *b2 = posRenderer ? posRenderer->inlineBox(pos.offset()) : 0;
953
954     if (!b1 || !b2) {
955         return false;
956     }
957
958     if (b1->root() != b2->root()) {
959         return true;
960     }
961
962     if (nextRenderedEditable(node()) == pos.node() && 
963         thisRenderedOffset == (long)node()->caretMaxRenderedOffset() && posRenderedOffset == 0) {
964         return false;
965     }
966     
967     if (previousRenderedEditable(node()) == pos.node() && 
968         thisRenderedOffset == 0 && posRenderedOffset == (long)pos.node()->caretMaxRenderedOffset()) {
969         return false;
970     }
971
972     return true;
973 }
974
975 bool Position::isFirstRenderedPositionOnLine() const
976 {
977     if (isEmpty())
978         return false;
979
980     RenderObject *renderer = node()->renderer();
981     if (!renderer)
982         return false;
983
984     if (renderer->style()->visibility() != khtml::VISIBLE)
985         return false;
986     
987     if (!inRenderedContent())
988         return false;
989     
990     Position pos(node(), offset());
991     PositionIterator it(pos);
992     while (!it.atStart()) {
993         it.previous();
994         if (it.current().inRenderedContent())
995             return renderersOnDifferentLine(renderer, offset(), it.current().node()->renderer(), it.current().offset());
996     }
997     
998     return true;
999 }
1000
1001 bool Position::isLastRenderedPositionOnLine() const
1002 {
1003     if (isEmpty())
1004         return false;
1005
1006     RenderObject *renderer = node()->renderer();
1007     if (!renderer)
1008         return false;
1009
1010     if (renderer->style()->visibility() != khtml::VISIBLE)
1011         return false;
1012     
1013     if (!inRenderedContent())
1014         return false;
1015     
1016     if (node()->id() == ID_BR)
1017         return true;
1018     
1019     Position pos(node(), offset());
1020     PositionIterator it(pos);
1021     while (!it.atEnd()) {
1022         it.next();
1023         if (it.current().inRenderedContent())
1024             return renderersOnDifferentLine(renderer, offset(), it.current().node()->renderer(), it.current().offset());
1025     }
1026     
1027     return true;
1028 }
1029
1030 bool Position::isLastRenderedPositionInEditableBlock() const
1031 {
1032     if (isEmpty())
1033         return false;
1034
1035     RenderObject *renderer = node()->renderer();
1036     if (!renderer)
1037         return false;
1038
1039     if (renderer->style()->visibility() != khtml::VISIBLE)
1040         return false;
1041
1042     if (renderedOffset() != (long)node()->caretMaxRenderedOffset())
1043         return false;
1044
1045     Position pos(node(), offset());
1046     PositionIterator it(pos);
1047     while (!it.atEnd()) {
1048         it.next();
1049         if (!it.current().node()->inSameContainingBlockFlowElement(node()))
1050             return true;
1051         if (it.current().inRenderedContent())
1052             return false;
1053     }
1054     return true;
1055 }
1056
1057 bool Position::inFirstEditableInRootEditableElement() const
1058 {
1059     if (isEmpty() || !inRenderedContent())
1060         return false;
1061
1062     PositionIterator it(*this);
1063     while (!it.atStart()) {
1064         if (it.previous().inRenderedContent())
1065             return false;
1066     }
1067
1068     return true;
1069 }
1070
1071 bool Position::inLastEditableInRootEditableElement() const
1072 {
1073     if (isEmpty() || !inRenderedContent())
1074         return false;
1075
1076     PositionIterator it(*this);
1077     while (!it.atEnd()) {
1078         if (it.next().inRenderedContent())
1079             return false;
1080     }
1081
1082     return true;
1083 }
1084
1085 bool Position::inFirstEditableInContainingEditableBlock() const
1086 {
1087     if (isEmpty() || !inRenderedContent())
1088         return false;
1089     
1090     NodeImpl *block = node()->enclosingBlockFlowElement();
1091
1092     PositionIterator it(*this);
1093     while (!it.atStart()) {
1094         it.previous();
1095         if (!it.current().inRenderedContent())
1096             continue;
1097         return block != it.current().node()->enclosingBlockFlowElement();
1098     }
1099
1100     return true;
1101 }
1102
1103 bool Position::inLastEditableInContainingEditableBlock() const
1104 {
1105     if (isEmpty() || !inRenderedContent())
1106         return false;
1107     
1108     NodeImpl *block = node()->enclosingBlockFlowElement();
1109
1110     PositionIterator it(*this);
1111     while (!it.atEnd()) {
1112         it.next();
1113         if (!it.current().inRenderedContent())
1114             continue;
1115         return block != it.current().node()->enclosingBlockFlowElement();
1116     }
1117
1118     return true;
1119 }
1120
1121 void Position::debugPosition(const char *msg) const
1122 {
1123     if (isEmpty())
1124         fprintf(stderr, "Position [%s]: empty\n");
1125     else
1126         fprintf(stderr, "Position [%s]: %s [%p] at %d\n", msg, getTagName(node()->id()).string().latin1(), node(), offset());
1127 }
1128
1129 #ifndef NDEBUG
1130 #define FormatBufferSize 1024
1131 void Position::formatForDebugger(char *buffer, unsigned length) const
1132 {
1133     DOMString result;
1134     DOMString s;
1135     
1136     if (isEmpty()) {
1137         result = "<empty>";
1138     }
1139     else {
1140         char s[FormatBufferSize];
1141         result += "offset ";
1142         result += QString::number(m_offset);
1143         result += " of ";
1144         m_node->formatForDebugger(s, FormatBufferSize);
1145         result += s;
1146     }
1147           
1148     strncpy(buffer, result.string().latin1(), length - 1);
1149 }
1150 #undef FormatBufferSize
1151 #endif
1152
1153 } // namespace DOM