52f194a372ed31f16fd3625572cc9f39b42f3ecf
[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(QString(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         string.prepend("X ");
387         unsigned pastImage = khtml::nextWordFromIndex(const_cast<QChar *>(string.unicode()), string.length(), string.length(), false);
388         Range range(it.range());
389         if (pastImage == 0)
390             pos = Position(range.startContainer().handle(), range.startOffset());
391         else
392             pos = Position(range.endContainer().handle(), range.endOffset());
393     }
394     else if (next != 0) {
395         // The simpler iterator used in this function, as compared to the one used in 
396         // nextWordPosition(), gives us results we can use directly without having to 
397         // iterate again to translate the next value into a DOM position. 
398         NodeImpl *node = it.range().startContainer().handle();
399         if (node->isTextNode()) {
400             // The next variable contains a usable index into a text node
401             pos = Position(node, next);
402         }
403         else {
404             // If we are not in a text node, we ended on a node boundary, so the
405             // range start offset should be used.
406             pos = Position(node, it.range().startOffset());
407         }
408     }
409     pos = pos.equivalentDeepPosition().closestRenderedPosition(UPSTREAM);
410     return pos;
411 }
412
413 Position Position::nextWordPosition() const
414 {
415     if (isEmpty())
416         return Position();
417
418     Range searchRange(node()->getDocument());
419     Position start(equivalentRangeCompliantPosition());
420     searchRange.setStart(start.node(), start.offset());
421     searchRange.setEndAfter(node()->getDocument()->documentElement());
422     TextIterator it(searchRange);
423     QString string;
424     unsigned next = 0;
425     while (!it.atEnd() && it.length() > 0) {
426         // Keep asking the iterator for chunks until the nextWordFromIndex() function
427         // returns a value not equal to the length of the string passed to it.
428         string += QString(it.characters(), it.length());
429         next = khtml::nextWordFromIndex(const_cast<QChar *>(string.unicode()), string.length(), 0, true);
430         if (next != string.length())
431             break;
432         it.advance();
433     }
434     
435     Position pos(*this);
436     if (it.atEnd() && next == string.length()) {
437         Range range(it.range());
438         pos = Position(range.startContainer().handle(), range.startOffset());
439     }
440     else if (!it.atEnd() && it.length() == 0) {
441         // Got a zero-length chunk.
442         // This means we have hit a replaced element.
443         // Make a check to see if the position should be before or after the replaced element
444         // by performing an additional check with a modified string which uses an "X" 
445         // character to stand in for the replaced element.
446         string += " X";
447         unsigned pastImage = khtml::nextWordFromIndex(const_cast<QChar *>(string.unicode()), string.length(), 0, true);
448         Range range(it.range());
449         if (next != pastImage)
450             pos = Position(range.endContainer().handle(), range.endOffset());
451         else
452             pos = Position(range.startContainer().handle(), range.startOffset());
453     }
454     else if (next != 0) {
455         // Use the character iterator to translate the next value into a DOM position.
456         CharacterIterator charIt(searchRange);
457         charIt.advance(next - 1);
458         pos = Position(charIt.range().endContainer().handle(), charIt.range().endOffset());
459     }
460     pos = pos.equivalentDeepPosition().closestRenderedPosition(UPSTREAM);
461     return pos;
462 }
463
464 Position Position::previousLinePosition(int x) const
465 {
466     if (!node())
467         return Position();
468
469     if (!node()->renderer())
470         return *this;
471
472     RenderBlock *containingBlock = 0;
473     RootInlineBox *root = 0;
474     InlineBox *box = node()->renderer()->inlineBox(offset());
475     if (box) {
476         root = box->root()->prevRootBox();
477         if (root)
478             containingBlock = node()->renderer()->containingBlock();
479     }
480
481     if (!root) {
482         // This containing editable block does not have a previous line.
483         // Need to move back to previous containing editable block in this root editable
484         // block and find the last root line box in that block.
485         NodeImpl *startBlock = node()->enclosingBlockFlowElement();
486         NodeImpl *n = node()->previousEditable();
487         while (n && startBlock == n->enclosingBlockFlowElement())
488             n = n->previousEditable();
489         while (n) {
490             if (!n->inSameRootEditableElement(node()))
491                 break;
492             Position pos(n, n->caretMaxOffset());
493             if (pos.inRenderedContent()) {
494                 ASSERT(n->renderer());
495                 box = n->renderer()->inlineBox(n->caretMaxOffset());
496                 if (box) {
497                     // previous root line box found
498                     root = box->root();
499                     containingBlock = n->renderer()->containingBlock();
500                     break;
501                 }
502                 else {
503                     return pos;
504                 }
505             }
506             n = n->previousEditable();
507         }
508     }
509     
510     if (root) {
511         int absx, absy;
512         containingBlock->absolutePosition(absx, absy);
513         RenderObject *renderer = root->closestLeafChildForXPos(x, absx)->object();
514         return renderer->positionForCoordinates(x, absy + root->topOverflow());
515     }
516     
517     return *this;
518 }
519
520 Position Position::nextLinePosition(int x) const
521 {
522     if (!node())
523         return Position();
524
525     if (!node()->renderer())
526         return *this;
527
528     RenderBlock *containingBlock = 0;
529     RootInlineBox *root = 0;
530     InlineBox *box = node()->renderer()->inlineBox(offset());
531     if (box) {
532         root = box->root()->nextRootBox();
533         if (root)
534             containingBlock = node()->renderer()->containingBlock();
535     }
536
537     if (!root) {
538         // This containing editable block does not have a next line.
539         // Need to move forward to next containing editable block in this root editable
540         // block and find the first root line box in that block.
541         NodeImpl *startBlock = node()->enclosingBlockFlowElement();
542         NodeImpl *n = node()->nextEditable();
543         while (n && startBlock == n->enclosingBlockFlowElement())
544             n = n->nextEditable();
545         while (n) {
546             if (!n->inSameRootEditableElement(node()))
547                 break;
548             Position pos(n, n->caretMinOffset());
549             if (pos.inRenderedContent()) {
550                 ASSERT(n->renderer());
551                 box = n->renderer()->inlineBox(n->caretMinOffset());
552                 if (box) {
553                     // next root line box found
554                     root = box->root();
555                     containingBlock = n->renderer()->containingBlock();
556                     break;
557                 }
558                 else {
559                     return pos;
560                 }
561             }
562             n = n->nextEditable();
563         }
564     }
565     
566     if (root) {
567         int absx, absy;
568         containingBlock->absolutePosition(absx, absy);
569         RenderObject *renderer = root->closestLeafChildForXPos(x, absx)->object();
570         return renderer->positionForCoordinates(x, absy + root->topOverflow());
571     }
572
573     return *this;
574 }
575
576 Position Position::equivalentUpstreamPosition() const
577 {
578     if (!node())
579         return Position();
580
581     NodeImpl *block = node()->enclosingBlockFlowElement();
582     
583     PositionIterator it(*this);            
584     for (; !it.atStart(); it.previous()) {   
585         NodeImpl *currentBlock = it.current().node()->enclosingBlockFlowElement();
586         if (block != currentBlock)
587             return it.next();
588
589         RenderObject *renderer = it.current().node()->renderer();
590         if (!renderer)
591             continue;
592
593         if (renderer->style()->visibility() != khtml::VISIBLE)
594             continue;
595
596         if (renderer->isBlockFlow() || renderer->isReplaced() || renderer->isBR()) {
597             if (it.current().offset() >= renderer->caretMaxOffset())
598                 return Position(it.current().node(), renderer->caretMaxOffset());
599             else
600                 continue;
601         }
602
603         if (renderer->isText() && static_cast<RenderText *>(renderer)->firstTextBox()) {
604             if (it.current().node() != node())
605                 return Position(it.current().node(), renderer->caretMaxOffset());
606
607             if (it.current().offset() < 0)
608                 continue;
609             uint textOffset = it.current().offset();
610
611             RenderText *textRenderer = static_cast<RenderText *>(renderer);
612             for (InlineTextBox *box = textRenderer->firstTextBox(); box; box = box->nextTextBox()) {
613                 if (textOffset > box->start() && textOffset <= box->start() + box->len())
614                     return it.current();
615                 else if (box != textRenderer->lastTextBox() && 
616                          !box->nextOnLine() && 
617                          textOffset == box->start() + box->len() + 1)
618                     return it.current();
619             }
620         }
621     }
622     
623     return it.current();
624 }
625
626 Position Position::equivalentDownstreamPosition() const
627 {
628     if (!node())
629         return Position();
630
631     NodeImpl *block = node()->enclosingBlockFlowElement();
632     
633     PositionIterator it(*this);            
634     for (; !it.atEnd(); it.next()) {   
635         NodeImpl *currentBlock = it.current().node()->enclosingBlockFlowElement();
636         if (block != currentBlock)
637             return it.previous();
638
639         RenderObject *renderer = it.current().node()->renderer();
640         if (!renderer)
641             continue;
642
643         if (renderer->style()->visibility() != khtml::VISIBLE)
644             continue;
645
646         if (renderer->isBlockFlow() || renderer->isReplaced() || renderer->isBR()) {
647             if (it.current().offset() <= renderer->caretMinOffset())
648                 return Position(it.current().node(), renderer->caretMinOffset());
649             else
650                 continue;
651         }
652
653         if (renderer->isText() && static_cast<RenderText *>(renderer)->firstTextBox()) {
654             if (it.current().node() != node())
655                 return Position(it.current().node(), renderer->caretMinOffset());
656
657             if (it.current().offset() < 0)
658                 continue;
659             uint textOffset = it.current().offset();
660
661             RenderText *textRenderer = static_cast<RenderText *>(renderer);
662             for (InlineTextBox *box = textRenderer->firstTextBox(); box; box = box->nextTextBox()) {
663                 if (textOffset >= box->start() && textOffset <= box->end())
664                     return it.current();
665                 else if (box != textRenderer->lastTextBox() && 
666                          !box->nextOnLine() && 
667                          textOffset == box->start() + box->len())
668                     return it.current();
669             }
670         }
671     }
672     
673     return it.current();
674 }
675
676 Position Position::equivalentRangeCompliantPosition() const
677 {
678     if (isEmpty())
679         return *this;
680
681     if (!node()->parentNode())
682         return *this;
683
684     RenderObject *renderer = node()->renderer();
685     if (!renderer)
686         return *this;
687         
688     if (!renderer->isReplaced() && !renderer->isBR())
689         return *this;
690     
691     int o = 0;
692     const NodeImpl *n = node();
693     while ((n = n->previousSibling()))
694         o++;
695     
696     return Position(node()->parentNode(), o + offset());
697 }
698
699 Position Position::equivalentShallowPosition() const
700 {
701     if (isEmpty())
702         return *this;
703
704     Position pos(*this);
705     while (pos.offset() == pos.node()->caretMinOffset() && pos.node()->parentNode() && pos.node() == pos.node()->parentNode()->firstChild())
706         pos = Position(pos.node()->parentNode(), 0);
707     return pos;
708 }
709
710 Position Position::equivalentDeepPosition() const
711 {
712     if (isEmpty() || node()->isAtomicNode())
713         return *this;
714
715     NodeImpl *child = 0;
716     Position pos(*this);
717     if (offset() >= (int)node()->childNodeCount()) {
718         child = node()->lastChild();
719         pos = Position(child, child->caretMaxOffset());
720         ASSERT(child);
721         while (!child->isAtomicNode() && pos.node()->hasChildNodes()) {
722             child = pos.node()->lastChild();
723             ASSERT(child);
724             pos = Position(child, child->caretMaxOffset());
725         }
726     }
727     else {
728         child = node()->childNode(offset());
729         ASSERT(child);
730         pos = Position(child, 0);
731         while (!child->isAtomicNode() && pos.node()->hasChildNodes()) {
732             child = pos.node()->firstChild();
733             ASSERT(child);
734             pos = Position(child, 0);
735         }
736     }
737     return pos;
738 }
739
740 Position Position::closestRenderedPosition(EAffinity affinity) const
741 {
742     if (isEmpty() || inRenderedContent())
743         return *this;
744
745     Position pos;
746     PositionIterator it(*this);
747     
748     switch (affinity) {
749         case UPSTREAM:
750             // look upstream first
751             it.setPosition(*this);
752             while (!it.atStart()) {
753                 it.previous();
754                 if (it.current().inRenderedContent())
755                     return it.current();
756             }
757             // if this does not find something rendered, look downstream
758             it.setPosition(*this);
759             while (!it.atEnd()) {
760                 it.next();
761                 if (it.current().inRenderedContent())
762                     return it.current();
763             }
764             break;
765         case DOWNSTREAM:
766             // look downstream first
767             it.setPosition(*this);
768             while (!it.atEnd()) {
769                 it.next();
770                 if (it.current().inRenderedContent())
771                     return it.current();
772             }
773             // if this does not find something rendered, look upstream
774             it.setPosition(*this);
775             while (!it.atStart()) {
776                 it.previous();
777                 if (it.current().inRenderedContent())
778                     return it.current();
779             }
780             break;
781     }
782     
783     return Position();
784 }
785
786 bool Position::atStartOfContainingEditableBlock() const
787 {
788     return renderedOffset() == 0 && inFirstEditableInContainingEditableBlock();
789 }
790
791 bool Position::atStartOfRootEditableElement() const
792 {
793     return renderedOffset() == 0 && inFirstEditableInRootEditableElement();
794 }
795
796 bool Position::inRenderedContent() const
797 {
798     if (isEmpty())
799         return false;
800         
801     RenderObject *renderer = node()->renderer();
802     if (!renderer)
803         return false;
804     
805     if (renderer->style()->visibility() != khtml::VISIBLE)
806         return false;
807
808     if (renderer->isBR() && static_cast<RenderText *>(renderer)->firstTextBox()) {
809         return offset() == 0;
810     }
811     else if (renderer->isText()) {
812         RenderText *textRenderer = static_cast<RenderText *>(renderer);
813         for (InlineTextBox *box = textRenderer->firstTextBox(); box; box = box->nextTextBox()) {
814             if (offset() >= box->m_start && offset() <= box->m_start + box->m_len) {
815                 return true;
816             }
817             else if (offset() < box->m_start) {
818                 // The offset we're looking for is before this node
819                 // this means the offset must be in content that is
820                 // not rendered. Return false.
821                 return false;
822             }
823         }
824     }
825     else if (offset() >= renderer->caretMinOffset() && offset() <= renderer->caretMaxOffset()) {
826         // don't return containing editable blocks unless they are empty
827         if (node()->enclosingBlockFlowElement() == node() && node()->firstChild())
828             return false;
829         return true;
830     }
831     
832     return false;
833 }
834
835 bool Position::inRenderedText() const
836 {
837     if (!node()->isTextNode())
838         return false;
839         
840     RenderObject *renderer = node()->renderer();
841     if (!renderer)
842         return false;
843     
844     RenderText *textRenderer = static_cast<RenderText *>(renderer);
845     for (InlineTextBox *box = textRenderer->firstTextBox(); box; box = box->nextTextBox()) {
846         if (offset() < box->m_start) {
847             // The offset we're looking for is before this node
848             // this means the offset must be in content that is
849             // not rendered. Return false.
850             return false;
851         }
852         if (offset() >= box->m_start && offset() <= box->m_start + box->m_len)
853             return true;
854     }
855     
856     return false;
857 }
858
859 bool Position::rendersOnSameLine(const Position &pos) const
860 {
861     if (isEmpty() || pos.isEmpty())
862         return false;
863
864     if (node() == pos.node() && offset() == pos.offset())
865         return true;
866
867     if (node()->enclosingBlockFlowElement() != pos.node()->enclosingBlockFlowElement())
868         return false;
869
870     RenderObject *renderer = node()->renderer();
871     if (!renderer)
872         return false;
873     
874     RenderObject *posRenderer = pos.node()->renderer();
875     if (!posRenderer)
876         return false;
877
878     if (renderer->style()->visibility() != khtml::VISIBLE ||
879         posRenderer->style()->visibility() != khtml::VISIBLE)
880         return false;
881
882     return renderersOnDifferentLine(renderer, offset(), posRenderer, pos.offset());
883 }
884
885 bool Position::rendersInDifferentPosition(const Position &pos) const
886 {
887     if (isEmpty() || pos.isEmpty())
888         return false;
889
890     RenderObject *renderer = node()->renderer();
891     if (!renderer)
892         return false;
893     
894     RenderObject *posRenderer = pos.node()->renderer();
895     if (!posRenderer)
896         return false;
897
898     if (renderer->style()->visibility() != khtml::VISIBLE ||
899         posRenderer->style()->visibility() != khtml::VISIBLE)
900         return false;
901     
902     if (node() == pos.node()) {
903         if (node()->id() == ID_BR)
904             return false;
905
906         if (offset() == pos.offset())
907             return false;
908             
909         if (!node()->isTextNode() && !pos.node()->isTextNode()) {
910             if (offset() != pos.offset())
911                 return true;
912         }
913     }
914     
915     if (node()->id() == ID_BR && pos.inRenderedContent())
916         return true;
917                 
918     if (pos.node()->id() == ID_BR && inRenderedContent())
919         return true;
920                 
921     if (node()->enclosingBlockFlowElement() != pos.node()->enclosingBlockFlowElement())
922         return true;
923
924     if (node()->isTextNode() && !inRenderedText())
925         return false;
926
927     if (pos.node()->isTextNode() && !pos.inRenderedText())
928         return false;
929
930     long thisRenderedOffset = renderedOffset();
931     long posRenderedOffset = pos.renderedOffset();
932
933     if (renderer == posRenderer && thisRenderedOffset == posRenderedOffset)
934         return false;
935
936     LOG(Editing, "onDifferentLine:        %s\n", renderersOnDifferentLine(renderer, offset(), posRenderer, pos.offset()) ? "YES" : "NO");
937     LOG(Editing, "renderer:               %p [%p]\n", renderer, renderer ? renderer->inlineBox(offset()) : 0);
938     LOG(Editing, "thisRenderedOffset:         %d\n", thisRenderedOffset);
939     LOG(Editing, "posRenderer:            %p [%p]\n", posRenderer, posRenderer ? posRenderer->inlineBox(offset()) : 0);
940     LOG(Editing, "posRenderedOffset:      %d\n", posRenderedOffset);
941     LOG(Editing, "node min/max:           %d:%d\n", node()->caretMinOffset(), node()->caretMaxRenderedOffset());
942     LOG(Editing, "pos node min/max:       %d:%d\n", pos.node()->caretMinOffset(), pos.node()->caretMaxRenderedOffset());
943     LOG(Editing, "----------------------------------------------------------------------\n");
944
945     InlineBox *b1 = renderer ? renderer->inlineBox(offset()) : 0;
946     InlineBox *b2 = posRenderer ? posRenderer->inlineBox(pos.offset()) : 0;
947
948     if (!b1 || !b2) {
949         return false;
950     }
951
952     if (b1->root() != b2->root()) {
953         return true;
954     }
955
956     if (nextRenderedEditable(node()) == pos.node() && 
957         thisRenderedOffset == (long)node()->caretMaxRenderedOffset() && posRenderedOffset == 0) {
958         return false;
959     }
960     
961     if (previousRenderedEditable(node()) == pos.node() && 
962         thisRenderedOffset == 0 && posRenderedOffset == (long)pos.node()->caretMaxRenderedOffset()) {
963         return false;
964     }
965
966     return true;
967 }
968
969 bool Position::isFirstRenderedPositionOnLine() const
970 {
971     if (isEmpty())
972         return false;
973
974     RenderObject *renderer = node()->renderer();
975     if (!renderer)
976         return false;
977
978     if (renderer->style()->visibility() != khtml::VISIBLE)
979         return false;
980     
981     if (!inRenderedContent())
982         return false;
983     
984     Position pos(node(), offset());
985     PositionIterator it(pos);
986     while (!it.atStart()) {
987         it.previous();
988         if (it.current().inRenderedContent())
989             return renderersOnDifferentLine(renderer, offset(), it.current().node()->renderer(), it.current().offset());
990     }
991     
992     return true;
993 }
994
995 bool Position::isLastRenderedPositionOnLine() const
996 {
997     if (isEmpty())
998         return false;
999
1000     RenderObject *renderer = node()->renderer();
1001     if (!renderer)
1002         return false;
1003
1004     if (renderer->style()->visibility() != khtml::VISIBLE)
1005         return false;
1006     
1007     if (!inRenderedContent())
1008         return false;
1009     
1010     if (node()->id() == ID_BR)
1011         return true;
1012     
1013     Position pos(node(), offset());
1014     PositionIterator it(pos);
1015     while (!it.atEnd()) {
1016         it.next();
1017         if (it.current().inRenderedContent())
1018             return renderersOnDifferentLine(renderer, offset(), it.current().node()->renderer(), it.current().offset());
1019     }
1020     
1021     return true;
1022 }
1023
1024 bool Position::isLastRenderedPositionInEditableBlock() const
1025 {
1026     if (isEmpty())
1027         return false;
1028
1029     RenderObject *renderer = node()->renderer();
1030     if (!renderer)
1031         return false;
1032
1033     if (renderer->style()->visibility() != khtml::VISIBLE)
1034         return false;
1035
1036     if (renderedOffset() != (long)node()->caretMaxRenderedOffset())
1037         return false;
1038
1039     Position pos(node(), offset());
1040     PositionIterator it(pos);
1041     while (!it.atEnd()) {
1042         it.next();
1043         if (!it.current().node()->inSameContainingBlockFlowElement(node()))
1044             return true;
1045         if (it.current().inRenderedContent())
1046             return false;
1047     }
1048     return true;
1049 }
1050
1051 bool Position::inFirstEditableInRootEditableElement() const
1052 {
1053     if (isEmpty() || !inRenderedContent())
1054         return false;
1055
1056     PositionIterator it(*this);
1057     while (!it.atStart()) {
1058         if (it.previous().inRenderedContent())
1059             return false;
1060     }
1061
1062     return true;
1063 }
1064
1065 bool Position::inLastEditableInRootEditableElement() const
1066 {
1067     if (isEmpty() || !inRenderedContent())
1068         return false;
1069
1070     PositionIterator it(*this);
1071     while (!it.atEnd()) {
1072         if (it.next().inRenderedContent())
1073             return false;
1074     }
1075
1076     return true;
1077 }
1078
1079 bool Position::inFirstEditableInContainingEditableBlock() const
1080 {
1081     if (isEmpty() || !inRenderedContent())
1082         return false;
1083     
1084     NodeImpl *block = node()->enclosingBlockFlowElement();
1085
1086     PositionIterator it(*this);
1087     while (!it.atStart()) {
1088         it.previous();
1089         if (!it.current().inRenderedContent())
1090             continue;
1091         return block != it.current().node()->enclosingBlockFlowElement();
1092     }
1093
1094     return true;
1095 }
1096
1097 bool Position::inLastEditableInContainingEditableBlock() const
1098 {
1099     if (isEmpty() || !inRenderedContent())
1100         return false;
1101     
1102     NodeImpl *block = node()->enclosingBlockFlowElement();
1103
1104     PositionIterator it(*this);
1105     while (!it.atEnd()) {
1106         it.next();
1107         if (!it.current().inRenderedContent())
1108             continue;
1109         return block != it.current().node()->enclosingBlockFlowElement();
1110     }
1111
1112     return true;
1113 }
1114
1115 void Position::debugPosition(const char *msg) const
1116 {
1117     if (isEmpty())
1118         fprintf(stderr, "Position [%s]: empty\n");
1119     else
1120         fprintf(stderr, "Position [%s]: %s [%p] at %d\n", msg, getTagName(node()->id()).string().latin1(), node(), offset());
1121 }
1122
1123 #ifndef NDEBUG
1124 #define FormatBufferSize 1024
1125 void Position::formatForDebugger(char *buffer, unsigned length) const
1126 {
1127     DOMString result;
1128     DOMString s;
1129     
1130     if (isEmpty()) {
1131         result = "<empty>";
1132     }
1133     else {
1134         char s[FormatBufferSize];
1135         result += "offset ";
1136         result += QString::number(m_offset);
1137         result += " of ";
1138         m_node->formatForDebugger(s, FormatBufferSize);
1139         result += s;
1140     }
1141           
1142     strncpy(buffer, result.string().latin1(), length - 1);
1143 }
1144 #undef FormatBufferSize
1145 #endif
1146
1147 } // namespace DOM