6a305b99b4c89f680211008b90f4ec593b738d08
[WebKit-https.git] / WebCore / dom / Position.cpp
1 /*
2  * Copyright (C) 2004, 2005, 2006, 2009 Apple 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 "config.h"
27 #include "Position.h"
28
29 #include "CSSComputedStyleDeclaration.h"
30 #include "CString.h"
31 #include "CharacterNames.h"
32 #include "Logging.h"
33 #include "PositionIterator.h"
34 #include "RenderBlock.h"
35 #include "Text.h"
36 #include "TextIterator.h"
37 #include "VisiblePosition.h"
38 #include "htmlediting.h"
39 #include "visible_units.h"
40 #include <stdio.h>
41   
42 namespace WebCore {
43
44 using namespace HTMLNames;
45
46 static Node* nextRenderedEditable(Node* node)
47 {
48     while (1) {
49         node = node->nextEditable();
50         if (!node)
51             return 0;
52         RenderObject* renderer = node->renderer();
53         if (!renderer)
54             continue;
55         if ((renderer->isBox() && toRenderBox(renderer)->inlineBoxWrapper()) || (renderer->isText() && toRenderText(renderer)->firstTextBox()))
56             return node;
57     }
58     return 0;
59 }
60
61 static Node* previousRenderedEditable(Node* node)
62 {
63     while (1) {
64         node = node->previousEditable();
65         if (!node)
66             return 0;
67         RenderObject* renderer = node->renderer();
68         if (!renderer)
69             continue;
70         if ((renderer->isBox() && toRenderBox(renderer)->inlineBoxWrapper()) || (renderer->isText() && toRenderText(renderer)->firstTextBox()))
71             return node;
72     }
73     return 0;
74 }
75
76 Element* Position::documentElement() const
77 {
78     if (Node* n = node())
79         if (Element* e = n->document()->documentElement())
80             return e;
81     return 0;
82 }
83
84 Element *Position::element() const
85 {
86     Node *n;
87     for (n = node(); n && !n->isElementNode(); n = n->parentNode())
88         ; // empty loop body
89     return static_cast<Element *>(n);
90 }
91
92 PassRefPtr<CSSComputedStyleDeclaration> Position::computedStyle() const
93 {
94     Element* elem = element();
95     if (!elem)
96         return 0;
97     return WebCore::computedStyle(elem);
98 }
99
100 Position Position::previous(PositionMoveType moveType) const
101 {
102     Node* n = node();
103     if (!n)
104         return *this;
105     
106     int o = offset();
107     // FIXME: Negative offsets shouldn't be allowed. We should catch this earlier.
108     ASSERT(o >= 0);
109
110     if (o > 0) {
111         Node* child = n->childNode(o - 1);
112         if (child)
113             return Position(child, maxDeepOffset(child));
114
115         // There are two reasons child might be 0:
116         //   1) The node is node like a text node that is not an element, and therefore has no children.
117         //      Going backward one character at a time is correct.
118         //   2) The old offset was a bogus offset like (<br>, 1), and there is no child.
119         //      Going from 1 to 0 is correct.
120         switch (moveType) {
121         case CodePoint:
122             return Position(n, o - 1);
123         case Character:
124             return Position(n, uncheckedPreviousOffset(n, o));
125         case BackwardDeletion:
126             return Position(n, uncheckedPreviousOffsetForBackwardDeletion(n, o));
127         }
128     }
129
130     Node* parent = n->parentNode();
131     if (!parent)
132         return *this;
133
134     return Position(parent, n->nodeIndex());
135 }
136
137 Position Position::next(PositionMoveType moveType) const
138 {
139     ASSERT(moveType != BackwardDeletion);
140
141     Node* n = node();
142     if (!n)
143         return *this;
144     
145     int o = offset();
146     // FIXME: Negative offsets shouldn't be allowed. We should catch this earlier.
147     ASSERT(o >= 0);
148
149     Node* child = n->childNode(o);
150     if (child || !n->hasChildNodes() && o < maxDeepOffset(n)) {
151         if (child)
152             return Position(child, 0);
153             
154         // There are two reasons child might be 0:
155         //   1) The node is node like a text node that is not an element, and therefore has no children.
156         //      Going forward one character at a time is correct.
157         //   2) The new offset is a bogus offset like (<br>, 1), and there is no child.
158         //      Going from 0 to 1 is correct.
159         return Position(n, (moveType == Character) ? uncheckedNextOffset(n, o) : o + 1);
160     }
161
162     Node* parent = n->parentNode();
163     if (!parent)
164         return *this;
165
166     return Position(parent, n->nodeIndex() + 1);
167 }
168
169 int Position::uncheckedPreviousOffset(const Node* n, int current)
170 {
171     return n->renderer() ? n->renderer()->previousOffset(current) : current - 1;
172 }
173
174 int Position::uncheckedPreviousOffsetForBackwardDeletion(const Node* n, int current)
175 {
176     return n->renderer() ? n->renderer()->previousOffsetForBackwardDeletion(current) : current - 1;
177 }
178
179 int Position::uncheckedNextOffset(const Node* n, int current)
180 {
181     return n->renderer() ? n->renderer()->nextOffset(current) : current + 1;
182 }
183
184 bool Position::atStart() const
185 {
186     Node *n = node();
187     if (!n)
188         return true;
189     
190     return offset() <= 0 && n->parent() == 0;
191 }
192
193 bool Position::atEnd() const
194 {
195     Node *n = node();
196     if (!n)
197         return true;
198     
199     return n->parent() == 0 && offset() >= maxDeepOffset(n);
200 }
201
202 int Position::renderedOffset() const
203 {
204     if (!node()->isTextNode())
205         return offset();
206    
207     if (!node()->renderer())
208         return offset();
209                     
210     int result = 0;
211     RenderText *textRenderer = toRenderText(node()->renderer());
212     for (InlineTextBox *box = textRenderer->firstTextBox(); box; box = box->nextTextBox()) {
213         int start = box->start();
214         int end = box->start() + box->len();
215         if (offset() < start)
216             return result;
217         if (offset() <= end) {
218             result += offset() - start;
219             return result;
220         }
221         result += box->len();
222     }
223     return result;
224 }
225
226 // return first preceding DOM position rendered at a different location, or "this"
227 Position Position::previousCharacterPosition(EAffinity affinity) const
228 {
229     if (isNull())
230         return Position();
231
232     Node *fromRootEditableElement = node()->rootEditableElement();
233
234     bool atStartOfLine = isStartOfLine(VisiblePosition(*this, affinity));
235     bool rendered = isCandidate();
236     
237     Position currentPos = *this;
238     while (!currentPos.atStart()) {
239         currentPos = currentPos.previous();
240
241         if (currentPos.node()->rootEditableElement() != fromRootEditableElement)
242             return *this;
243
244         if (atStartOfLine || !rendered) {
245             if (currentPos.isCandidate())
246                 return currentPos;
247         } else if (rendersInDifferentPosition(currentPos))
248             return currentPos;
249     }
250     
251     return *this;
252 }
253
254 // return first following position rendered at a different location, or "this"
255 Position Position::nextCharacterPosition(EAffinity affinity) const
256 {
257     if (isNull())
258         return Position();
259
260     Node *fromRootEditableElement = node()->rootEditableElement();
261
262     bool atEndOfLine = isEndOfLine(VisiblePosition(*this, affinity));
263     bool rendered = isCandidate();
264     
265     Position currentPos = *this;
266     while (!currentPos.atEnd()) {
267         currentPos = currentPos.next();
268
269         if (currentPos.node()->rootEditableElement() != fromRootEditableElement)
270             return *this;
271
272         if (atEndOfLine || !rendered) {
273             if (currentPos.isCandidate())
274                 return currentPos;
275         } else if (rendersInDifferentPosition(currentPos))
276             return currentPos;
277     }
278     
279     return *this;
280 }
281
282 // Whether or not [node, 0] and [node, maxDeepOffset(node)] are their own VisiblePositions.
283 // If true, adjacent candidates are visually distinct.
284 // FIXME: Disregard nodes with renderers that have no height, as we do in isCandidate.
285 // FIXME: Share code with isCandidate, if possible.
286 static bool endsOfNodeAreVisuallyDistinctPositions(Node* node)
287 {
288     if (!node || !node->renderer())
289         return false;
290         
291     if (!node->renderer()->isInline())
292         return true;
293         
294     // Don't include inline tables.
295     if (node->hasTagName(tableTag))
296         return false;
297     
298     // There is a VisiblePosition inside an empty inline-block container.
299     return node->renderer()->isReplaced() && canHaveChildrenForEditing(node) && toRenderBox(node->renderer())->height() != 0 && !node->firstChild();
300 }
301
302 static Node* enclosingVisualBoundary(Node* node)
303 {
304     while (node && !endsOfNodeAreVisuallyDistinctPositions(node))
305         node = node->parentNode();
306         
307     return node;
308 }
309
310 // upstream() and downstream() want to return positions that are either in a
311 // text node or at just before a non-text node.  This method checks for that.
312 static bool isStreamer(const PositionIterator& pos)
313 {
314     if (!pos.node())
315         return true;
316         
317     if (isAtomicNode(pos.node()))
318         return true;
319         
320     return pos.atStartOfNode();
321 }
322
323 // This function and downstream() are used for moving back and forth between visually equivalent candidates.
324 // For example, for the text node "foo     bar" where whitespace is collapsible, there are two candidates 
325 // that map to the VisiblePosition between 'b' and the space.  This function will return the left candidate 
326 // and downstream() will return the right one.
327 // Also, upstream() will return [boundary, 0] for any of the positions from [boundary, 0] to the first candidate
328 // in boundary, where endsOfNodeAreVisuallyDistinctPositions(boundary) is true.
329 Position Position::upstream() const
330 {
331     Node* startNode = node();
332     if (!startNode)
333         return Position();
334     
335     // iterate backward from there, looking for a qualified position
336     Node* boundary = enclosingVisualBoundary(startNode);
337     PositionIterator lastVisible = *this;
338     PositionIterator currentPos = lastVisible;
339     bool startEditable = startNode->isContentEditable();
340     Node* lastNode = startNode;
341     for (; !currentPos.atStart(); currentPos.decrement()) {
342         Node* currentNode = currentPos.node();
343         
344         // Don't check for an editability change if we haven't moved to a different node,
345         // to avoid the expense of computing isContentEditable().
346         if (currentNode != lastNode) {
347             // Don't change editability.
348             bool currentEditable = currentNode->isContentEditable();
349             if (startEditable != currentEditable)
350                 break;
351             lastNode = currentNode;
352         }
353
354         // If we've moved to a position that is visually disinct, return the last saved position. There 
355         // is code below that terminates early if we're *about* to move to a visually distinct position.
356         if (endsOfNodeAreVisuallyDistinctPositions(currentNode) && currentNode != boundary)
357             return lastVisible;
358
359         // skip position in unrendered or invisible node
360         RenderObject* renderer = currentNode->renderer();
361         if (!renderer || renderer->style()->visibility() != VISIBLE)
362             continue;
363                  
364         // track last visible streamer position
365         if (isStreamer(currentPos))
366             lastVisible = currentPos;
367         
368         // Don't move past a position that is visually distinct.  We could rely on code above to terminate and 
369         // return lastVisible on the next iteration, but we terminate early to avoid doing a nodeIndex() call.
370         if (endsOfNodeAreVisuallyDistinctPositions(currentNode) && currentPos.atStartOfNode())
371             return lastVisible;
372
373         // Return position after tables and nodes which have content that can be ignored.
374         if (editingIgnoresContent(currentNode) || isTableElement(currentNode)) {
375             if (currentPos.atEndOfNode())
376                 return Position(currentNode, maxDeepOffset(currentNode));
377             continue;
378         }
379
380         // return current position if it is in rendered text
381         if (renderer->isText() && toRenderText(renderer)->firstTextBox()) {
382             if (currentNode != startNode) {
383                 // This assertion fires in layout tests in the case-transform.html test because
384                 // of a mix-up between offsets in the text in the DOM tree with text in the
385                 // render tree which can have a different length due to case transformation.
386                 // Until we resolve that, disable this so we can run the layout tests!
387                 //ASSERT(currentOffset >= renderer->caretMaxOffset());
388                 return Position(currentNode, renderer->caretMaxOffset());
389             }
390
391             unsigned textOffset = currentPos.offsetInLeafNode();
392             RenderText* textRenderer = toRenderText(renderer);
393             InlineTextBox* lastTextBox = textRenderer->lastTextBox();
394             for (InlineTextBox* box = textRenderer->firstTextBox(); box; box = box->nextTextBox()) {
395                 if (textOffset <= box->start() + box->len()) {
396                     if (textOffset > box->start())
397                         return currentPos;
398                     continue;
399                 }
400
401                 if (box == lastTextBox || textOffset != box->start() + box->len() + 1)
402                     continue;
403
404                 // The text continues on the next line only if the last text box is not on this line and
405                 // none of the boxes on this line have a larger start offset.
406
407                 bool continuesOnNextLine = true;
408                 InlineBox* otherBox = box;
409                 while (continuesOnNextLine) {
410                     otherBox = otherBox->nextLeafChild();
411                     if (!otherBox)
412                         break;
413                     if (otherBox == lastTextBox || otherBox->renderer() == textRenderer && static_cast<InlineTextBox*>(otherBox)->start() > textOffset)
414                         continuesOnNextLine = false;
415                 }
416
417                 otherBox = box;
418                 while (continuesOnNextLine) {
419                     otherBox = otherBox->prevLeafChild();
420                     if (!otherBox)
421                         break;
422                     if (otherBox == lastTextBox || otherBox->renderer() == textRenderer && static_cast<InlineTextBox*>(otherBox)->start() > textOffset)
423                         continuesOnNextLine = false;
424                 }
425
426                 if (continuesOnNextLine)
427                     return currentPos;
428             }
429         }
430     }
431
432     return lastVisible;
433 }
434
435 // This function and upstream() are used for moving back and forth between visually equivalent candidates.
436 // For example, for the text node "foo     bar" where whitespace is collapsible, there are two candidates 
437 // that map to the VisiblePosition between 'b' and the space.  This function will return the right candidate 
438 // and upstream() will return the left one.
439 // Also, downstream() will return the last position in the last atomic node in boundary for all of the positions
440 // in boundary after the last candidate, where endsOfNodeAreVisuallyDistinctPositions(boundary).
441 Position Position::downstream() const
442 {
443     Node* startNode = node();
444     if (!startNode)
445         return Position();
446
447     // iterate forward from there, looking for a qualified position
448     Node* boundary = enclosingVisualBoundary(startNode);
449     PositionIterator lastVisible = *this;
450     PositionIterator currentPos = lastVisible;
451     bool startEditable = startNode->isContentEditable();
452     Node* lastNode = startNode;
453     for (; !currentPos.atEnd(); currentPos.increment()) {   
454         Node* currentNode = currentPos.node();
455         
456         // Don't check for an editability change if we haven't moved to a different node,
457         // to avoid the expense of computing isContentEditable().
458         if (currentNode != lastNode) {
459             // Don't change editability.
460             bool currentEditable = currentNode->isContentEditable();
461             if (startEditable != currentEditable)
462                 break;
463             lastNode = currentNode;
464         }
465
466         // stop before going above the body, up into the head
467         // return the last visible streamer position
468         if (currentNode->hasTagName(bodyTag) && currentPos.atEndOfNode())
469             break;
470             
471         // Do not move to a visually distinct position.
472         if (endsOfNodeAreVisuallyDistinctPositions(currentNode) && currentNode != boundary)
473             return lastVisible;
474         // Do not move past a visually disinct position.
475         // Note: The first position after the last in a node whose ends are visually distinct
476         // positions will be [boundary->parentNode(), originalBlock->nodeIndex() + 1].
477         if (boundary && boundary->parentNode() == currentNode)
478             return lastVisible;
479
480         // skip position in unrendered or invisible node
481         RenderObject* renderer = currentNode->renderer();
482         if (!renderer || renderer->style()->visibility() != VISIBLE)
483             continue;
484             
485         // track last visible streamer position
486         if (isStreamer(currentPos))
487             lastVisible = currentPos;
488
489         // Return position before tables and nodes which have content that can be ignored.
490         if (editingIgnoresContent(currentNode) || isTableElement(currentNode)) {
491             if (currentPos.offsetInLeafNode() <= renderer->caretMinOffset())
492                 return Position(currentNode, renderer->caretMinOffset());
493             continue;
494         }
495
496         // return current position if it is in rendered text
497         if (renderer->isText() && toRenderText(renderer)->firstTextBox()) {
498             if (currentNode != startNode) {
499                 ASSERT(currentPos.atStartOfNode());
500                 return Position(currentNode, renderer->caretMinOffset());
501             }
502
503             unsigned textOffset = currentPos.offsetInLeafNode();
504             RenderText* textRenderer = toRenderText(renderer);
505             InlineTextBox* lastTextBox = textRenderer->lastTextBox();
506             for (InlineTextBox* box = textRenderer->firstTextBox(); box; box = box->nextTextBox()) {
507                 if (textOffset <= box->end()) {
508                     if (textOffset >= box->start())
509                         return currentPos;
510                     continue;
511                 }
512
513                 if (box == lastTextBox || textOffset != box->start() + box->len())
514                     continue;
515
516                 // The text continues on the next line only if the last text box is not on this line and
517                 // none of the boxes on this line have a larger start offset.
518
519                 bool continuesOnNextLine = true;
520                 InlineBox* otherBox = box;
521                 while (continuesOnNextLine) {
522                     otherBox = otherBox->nextLeafChild();
523                     if (!otherBox)
524                         break;
525                     if (otherBox == lastTextBox || otherBox->renderer() == textRenderer && static_cast<InlineTextBox*>(otherBox)->start() >= textOffset)
526                         continuesOnNextLine = false;
527                 }
528
529                 otherBox = box;
530                 while (continuesOnNextLine) {
531                     otherBox = otherBox->prevLeafChild();
532                     if (!otherBox)
533                         break;
534                     if (otherBox == lastTextBox || otherBox->renderer() == textRenderer && static_cast<InlineTextBox*>(otherBox)->start() >= textOffset)
535                         continuesOnNextLine = false;
536                 }
537
538                 if (continuesOnNextLine)
539                     return currentPos;
540             }
541         }
542     }
543     
544     return lastVisible;
545 }
546
547 bool Position::hasRenderedNonAnonymousDescendantsWithHeight(RenderObject* renderer)
548 {
549     RenderObject* stop = renderer->nextInPreOrderAfterChildren();
550     for (RenderObject *o = renderer->firstChild(); o && o != stop; o = o->nextInPreOrder())
551         if (o->node()) {
552             if ((o->isText() && toRenderText(o)->linesBoundingBox().height()) ||
553                 (o->isBox() && toRenderBox(o)->borderBoundingBox().height()))
554                 return true;
555         }
556     return false;
557 }
558
559 bool Position::nodeIsUserSelectNone(Node* node)
560 {
561     return node && node->renderer() && node->renderer()->style()->userSelect() == SELECT_NONE;
562 }
563
564 bool Position::isCandidate() const
565 {
566     if (isNull())
567         return false;
568         
569     RenderObject *renderer = node()->renderer();
570     if (!renderer)
571         return false;
572     
573     if (renderer->style()->visibility() != VISIBLE)
574         return false;
575
576     if (renderer->isBR())
577         return offset() == 0 && !nodeIsUserSelectNone(node()->parent());
578
579     if (renderer->isText())
580         return inRenderedText() && !nodeIsUserSelectNone(node());
581
582     if (isTableElement(node()) || editingIgnoresContent(node()))
583         return (offset() == 0 || offset() == maxDeepOffset(node())) && !nodeIsUserSelectNone(node()->parent());
584
585     if (!node()->hasTagName(htmlTag) && renderer->isBlockFlow() && !hasRenderedNonAnonymousDescendantsWithHeight(renderer) &&
586        (toRenderBox(renderer)->height() || node()->hasTagName(bodyTag)))
587         return offset() == 0 && !nodeIsUserSelectNone(node());
588     
589     return false;
590 }
591
592 bool Position::inRenderedText() const
593 {
594     if (isNull() || !node()->isTextNode())
595         return false;
596         
597     RenderObject *renderer = node()->renderer();
598     if (!renderer)
599         return false;
600     
601     RenderText *textRenderer = toRenderText(renderer);
602     for (InlineTextBox *box = textRenderer->firstTextBox(); box; box = box->nextTextBox()) {
603         if (offset() < static_cast<int>(box->start()) && !textRenderer->containsReversedText()) {
604             // The offset we're looking for is before this node
605             // this means the offset must be in content that is
606             // not rendered. Return false.
607             return false;
608         }
609         if (box->containsCaretOffset(offset()))
610             // Return false for offsets inside composed characters.
611             return offset() == 0 || offset() == textRenderer->nextOffset(textRenderer->previousOffset(offset()));
612     }
613     
614     return false;
615 }
616
617 static unsigned caretMaxRenderedOffset(const Node* n)
618 {
619     RenderObject* r = n->renderer();
620     if (r)
621         return r->caretMaxRenderedOffset();
622     
623     if (n->isCharacterDataNode())
624         return static_cast<const CharacterData*>(n)->length();
625     return 1;
626 }
627
628 bool Position::isRenderedCharacter() const
629 {
630     if (isNull() || !node()->isTextNode())
631         return false;
632         
633     RenderObject* renderer = node()->renderer();
634     if (!renderer)
635         return false;
636     
637     RenderText* textRenderer = toRenderText(renderer);
638     for (InlineTextBox* box = textRenderer->firstTextBox(); box; box = box->nextTextBox()) {
639         if (offset() < static_cast<int>(box->start()) && !textRenderer->containsReversedText()) {
640             // The offset we're looking for is before this node
641             // this means the offset must be in content that is
642             // not rendered. Return false.
643             return false;
644         }
645         if (offset() >= static_cast<int>(box->start()) && offset() < static_cast<int>(box->start() + box->len()))
646             return true;
647     }
648     
649     return false;
650 }
651
652 bool Position::rendersInDifferentPosition(const Position &pos) const
653 {
654     if (isNull() || pos.isNull())
655         return false;
656
657     RenderObject *renderer = node()->renderer();
658     if (!renderer)
659         return false;
660     
661     RenderObject *posRenderer = pos.node()->renderer();
662     if (!posRenderer)
663         return false;
664
665     if (renderer->style()->visibility() != VISIBLE ||
666         posRenderer->style()->visibility() != VISIBLE)
667         return false;
668     
669     if (node() == pos.node()) {
670         if (node()->hasTagName(brTag))
671             return false;
672
673         if (offset() == pos.offset())
674             return false;
675             
676         if (!node()->isTextNode() && !pos.node()->isTextNode()) {
677             if (offset() != pos.offset())
678                 return true;
679         }
680     }
681     
682     if (node()->hasTagName(brTag) && pos.isCandidate())
683         return true;
684                 
685     if (pos.node()->hasTagName(brTag) && isCandidate())
686         return true;
687                 
688     if (node()->enclosingBlockFlowElement() != pos.node()->enclosingBlockFlowElement())
689         return true;
690
691     if (node()->isTextNode() && !inRenderedText())
692         return false;
693
694     if (pos.node()->isTextNode() && !pos.inRenderedText())
695         return false;
696
697     int thisRenderedOffset = renderedOffset();
698     int posRenderedOffset = pos.renderedOffset();
699
700     if (renderer == posRenderer && thisRenderedOffset == posRenderedOffset)
701         return false;
702
703     int ignoredCaretOffset;
704     InlineBox* b1;
705     getInlineBoxAndOffset(DOWNSTREAM, b1, ignoredCaretOffset);
706     InlineBox* b2;
707     pos.getInlineBoxAndOffset(DOWNSTREAM, b2, ignoredCaretOffset);
708
709     LOG(Editing, "renderer:               %p [%p]\n", renderer, b1);
710     LOG(Editing, "thisRenderedOffset:         %d\n", thisRenderedOffset);
711     LOG(Editing, "posRenderer:            %p [%p]\n", posRenderer, b2);
712     LOG(Editing, "posRenderedOffset:      %d\n", posRenderedOffset);
713     LOG(Editing, "node min/max:           %d:%d\n", caretMinOffset(node()), caretMaxRenderedOffset(node()));
714     LOG(Editing, "pos node min/max:       %d:%d\n", caretMinOffset(pos.node()), caretMaxRenderedOffset(pos.node()));
715     LOG(Editing, "----------------------------------------------------------------------\n");
716
717     if (!b1 || !b2) {
718         return false;
719     }
720
721     if (b1->root() != b2->root()) {
722         return true;
723     }
724
725     if (nextRenderedEditable(node()) == pos.node() && 
726         thisRenderedOffset == (int)caretMaxRenderedOffset(node()) && posRenderedOffset == 0) {
727         return false;
728     }
729     
730     if (previousRenderedEditable(node()) == pos.node() && 
731         thisRenderedOffset == 0 && posRenderedOffset == (int)caretMaxRenderedOffset(pos.node())) {
732         return false;
733     }
734
735     return true;
736 }
737
738 // This assumes that it starts in editable content.
739 Position Position::leadingWhitespacePosition(EAffinity affinity, bool considerNonCollapsibleWhitespace) const
740 {
741     ASSERT(isEditablePosition(*this));
742     if (isNull())
743         return Position();
744     
745     if (upstream().node()->hasTagName(brTag))
746         return Position();
747
748     Position prev = previousCharacterPosition(affinity);
749     if (prev != *this && prev.node()->inSameContainingBlockFlowElement(node()) && prev.node()->isTextNode()) {
750         String string = static_cast<Text *>(prev.node())->data();
751         UChar c = string[prev.offset()];
752         if (considerNonCollapsibleWhitespace ? (isSpaceOrNewline(c) || c == noBreakSpace) : isCollapsibleWhitespace(c))
753             if (isEditablePosition(prev))
754                 return prev;
755     }
756
757     return Position();
758 }
759
760 // This assumes that it starts in editable content.
761 Position Position::trailingWhitespacePosition(EAffinity, bool considerNonCollapsibleWhitespace) const
762 {
763     ASSERT(isEditablePosition(*this));
764     if (isNull())
765         return Position();
766     
767     VisiblePosition v(*this);
768     UChar c = v.characterAfter();
769     // The space must not be in another paragraph and it must be editable.
770     if (!isEndOfParagraph(v) && v.next(true).isNotNull())
771         if (considerNonCollapsibleWhitespace ? (isSpaceOrNewline(c) || c == noBreakSpace) : isCollapsibleWhitespace(c))
772             return *this;
773     
774     return Position();
775 }
776
777 void Position::getInlineBoxAndOffset(EAffinity affinity, InlineBox*& inlineBox, int& caretOffset) const
778 {
779     TextDirection primaryDirection = LTR;
780     for (RenderObject* r = node()->renderer(); r; r = r->parent()) {
781         if (r->isBlockFlow()) {
782             primaryDirection = r->style()->direction();
783             break;
784         }
785     }
786     getInlineBoxAndOffset(affinity, primaryDirection, inlineBox, caretOffset);
787 }
788
789 static bool isNonTextLeafChild(RenderObject* object)
790 {
791     if (object->firstChild())
792         return false;
793     if (object->isText())
794         return false;
795     return true;
796 }
797
798 static InlineTextBox* searchAheadForBetterMatch(RenderObject* renderer)
799 {
800     InlineTextBox* match = 0;
801     int minOffset = INT_MAX;
802     RenderBlock* container = renderer->containingBlock();
803     RenderObject* next = renderer;
804     while ((next = next->nextInPreOrder(container))) {
805         if (next->isRenderBlock())
806             break;
807         if (next->isBR())
808             break;
809         if (isNonTextLeafChild(next))
810             break;
811         if (next->isText()) {
812             for (InlineTextBox* box = toRenderText(next)->firstTextBox(); box; box = box->nextTextBox()) {
813                 int caretMinOffset = box->caretMinOffset();
814                 if (caretMinOffset < minOffset) {
815                     match = box;
816                     minOffset = caretMinOffset;
817                 }
818             }
819         }
820     }
821     return match;
822 }
823
824 void Position::getInlineBoxAndOffset(EAffinity affinity, TextDirection primaryDirection, InlineBox*& inlineBox, int& caretOffset) const
825 {
826     caretOffset = offset();
827     RenderObject* renderer = node()->renderer();
828     if (!renderer->isText()) {
829         inlineBox = renderer->isBox() ? toRenderBox(renderer)->inlineBoxWrapper() : 0;
830         if (!inlineBox || caretOffset > inlineBox->caretMinOffset() && caretOffset < inlineBox->caretMaxOffset())
831             return;
832     } else {
833         RenderText* textRenderer = toRenderText(renderer);
834
835         InlineTextBox* box;
836         InlineTextBox* candidate = 0;
837
838         for (box = textRenderer->firstTextBox(); box; box = box->nextTextBox()) {
839             int caretMinOffset = box->caretMinOffset();
840             int caretMaxOffset = box->caretMaxOffset();
841
842             if (caretOffset < caretMinOffset || caretOffset > caretMaxOffset || caretOffset == caretMaxOffset && box->isLineBreak())
843                 continue;
844
845             if (caretOffset > caretMinOffset && caretOffset < caretMaxOffset) {
846                 inlineBox = box;
847                 return;
848             }
849
850             if ((caretOffset == caretMinOffset) ^ (affinity == UPSTREAM))
851                 break;
852
853             candidate = box;
854         }
855         if (candidate && !box && affinity == DOWNSTREAM) {
856             box = searchAheadForBetterMatch(textRenderer);
857             if (box)
858                 caretOffset = box->caretMinOffset();
859         }
860         inlineBox = box ? box : candidate;
861     }
862
863     if (!inlineBox)
864         return;
865
866     unsigned char level = inlineBox->bidiLevel();
867
868     if (inlineBox->direction() == primaryDirection) {
869         if (caretOffset == inlineBox->caretRightmostOffset()) {
870             InlineBox* nextBox = inlineBox->nextLeafChild();
871             if (!nextBox || nextBox->bidiLevel() >= level)
872                 return;
873
874             level = nextBox->bidiLevel();
875             InlineBox* prevBox = inlineBox;
876             do {
877                 prevBox = prevBox->prevLeafChild();
878             } while (prevBox && prevBox->bidiLevel() > level);
879
880             if (prevBox && prevBox->bidiLevel() == level)   // For example, abc FED 123 ^ CBA
881                 return;
882
883             // For example, abc 123 ^ CBA
884             while (InlineBox* nextBox = inlineBox->nextLeafChild()) {
885                 if (nextBox->bidiLevel() < level)
886                     break;
887                 inlineBox = nextBox;
888             }
889             caretOffset = inlineBox->caretRightmostOffset();
890         } else {
891             InlineBox* prevBox = inlineBox->prevLeafChild();
892             if (!prevBox || prevBox->bidiLevel() >= level)
893                 return;
894
895             level = prevBox->bidiLevel();
896             InlineBox* nextBox = inlineBox;
897             do {
898                 nextBox = nextBox->nextLeafChild();
899             } while (nextBox && nextBox->bidiLevel() > level);
900
901             if (nextBox && nextBox->bidiLevel() == level)
902                 return;
903
904             while (InlineBox* prevBox = inlineBox->prevLeafChild()) {
905                 if (prevBox->bidiLevel() < level)
906                     break;
907                 inlineBox = prevBox;
908             }
909             caretOffset = inlineBox->caretLeftmostOffset();
910         }
911         return;
912     }
913
914     if (caretOffset == inlineBox->caretLeftmostOffset()) {
915         InlineBox* prevBox = inlineBox->prevLeafChild();
916         if (!prevBox || prevBox->bidiLevel() < level) {
917             // Left edge of a secondary run. Set to the right edge of the entire run.
918             while (InlineBox* nextBox = inlineBox->nextLeafChild()) {
919                 if (nextBox->bidiLevel() < level)
920                     break;
921                 inlineBox = nextBox;
922             }
923             caretOffset = inlineBox->caretRightmostOffset();
924         } else if (prevBox->bidiLevel() > level) {
925             // Right edge of a "tertiary" run. Set to the left edge of that run.
926             while (InlineBox* tertiaryBox = inlineBox->prevLeafChild()) {
927                 if (tertiaryBox->bidiLevel() <= level)
928                     break;
929                 inlineBox = tertiaryBox;
930             }
931             caretOffset = inlineBox->caretLeftmostOffset();
932         }
933     } else {
934         InlineBox* nextBox = inlineBox->nextLeafChild();
935         if (!nextBox || nextBox->bidiLevel() < level) {
936             // Right edge of a secondary run. Set to the left edge of the entire run.
937             while (InlineBox* prevBox = inlineBox->prevLeafChild()) {
938                 if (prevBox->bidiLevel() < level)
939                     break;
940                 inlineBox = prevBox;
941             }
942             caretOffset = inlineBox->caretLeftmostOffset();
943         } else if (nextBox->bidiLevel() > level) {
944             // Left edge of a "tertiary" run. Set to the right edge of that run.
945             while (InlineBox* tertiaryBox = inlineBox->nextLeafChild()) {
946                 if (tertiaryBox->bidiLevel() <= level)
947                     break;
948                 inlineBox = tertiaryBox;
949             }
950             caretOffset = inlineBox->caretRightmostOffset();
951         }
952     }
953 }
954
955 void Position::debugPosition(const char* msg) const
956 {
957     if (isNull())
958         fprintf(stderr, "Position [%s]: null\n", msg);
959     else
960         fprintf(stderr, "Position [%s]: %s [%p] at %d\n", msg, node()->nodeName().utf8().data(), node(), offset());
961 }
962
963 #ifndef NDEBUG
964
965 void Position::formatForDebugger(char* buffer, unsigned length) const
966 {
967     String result;
968     
969     if (isNull())
970         result = "<null>";
971     else {
972         char s[1024];
973         result += "offset ";
974         result += String::number(offset());
975         result += " of ";
976         node()->formatForDebugger(s, sizeof(s));
977         result += s;
978     }
979           
980     strncpy(buffer, result.utf8().data(), length - 1);
981 }
982
983 void Position::showTreeForThis() const
984 {
985     if (node())
986         node()->showTreeForThis();
987 }
988
989 #endif
990
991 Position startPosition(const Range* r)
992 {
993     return r ? r->startPosition() : Position();
994 }
995
996 Position endPosition(const Range* r)
997 {
998     return r ? r->endPosition() : Position();
999 }
1000
1001 } // namespace WebCore
1002
1003 #ifndef NDEBUG
1004
1005 void showTree(const WebCore::Position& pos)
1006 {
1007     pos.showTreeForThis();
1008 }
1009
1010 void showTree(const WebCore::Position* pos)
1011 {
1012     if (pos)
1013         pos->showTreeForThis();
1014 }
1015
1016 #endif