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