f1834d8b71adc0775bebbd46c631cb87d8e31965
[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 "CharacterNames.h"
31 #include "Logging.h"
32 #include "PositionIterator.h"
33 #include "RenderBlock.h"
34 #include "Text.h"
35 #include "TextIterator.h"
36 #include "VisiblePosition.h"
37 #include "htmlediting.h"
38 #include "visible_units.h"
39 #include <stdio.h>
40 #include <wtf/text/CString.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 Position::Position(PassRefPtr<Node> anchorNode, int offset)
77     : m_anchorNode(anchorNode)
78     , m_offset(offset)
79     , m_anchorType(anchorTypeForLegacyEditingPosition(m_anchorNode.get(), m_offset))
80     , m_isLegacyEditingPosition(true)
81 {
82 }
83
84 Position::Position(PassRefPtr<Node> anchorNode, AnchorType anchorType)
85     : m_anchorNode(anchorNode)
86     , m_offset(0)
87     , m_anchorType(anchorType)
88     , m_isLegacyEditingPosition(false)
89 {
90     ASSERT(anchorType != PositionIsOffsetInAnchor);
91 }
92
93 Position::Position(PassRefPtr<Node> anchorNode, int offset, AnchorType anchorType)
94     : m_anchorNode(anchorNode)
95     , m_offset(offset)
96     , m_anchorType(anchorType)
97     , m_isLegacyEditingPosition(false)
98 {
99     ASSERT(anchorType == PositionIsOffsetInAnchor);
100 }
101
102 void Position::moveToPosition(PassRefPtr<Node> node, int offset)
103 {
104     ASSERT(anchorType() == PositionIsOffsetInAnchor || m_isLegacyEditingPosition);
105     m_anchorNode = node;
106     m_offset = offset;
107     if (m_isLegacyEditingPosition)
108         m_anchorType = anchorTypeForLegacyEditingPosition(m_anchorNode.get(), m_offset);
109 }
110 void Position::moveToOffset(int offset)
111 {
112     ASSERT(anchorType() == PositionIsOffsetInAnchor || m_isLegacyEditingPosition);
113     m_offset = offset;
114     if (m_isLegacyEditingPosition)
115         m_anchorType = anchorTypeForLegacyEditingPosition(m_anchorNode.get(), m_offset);
116 }
117
118 Node* Position::containerNode() const
119 {
120     if (!m_anchorNode)
121         return 0;
122
123     switch (anchorType()) {
124     case PositionIsOffsetInAnchor:
125         return m_anchorNode.get();
126     case PositionIsBeforeAnchor:
127     case PositionIsAfterAnchor:
128         return m_anchorNode->parentNode();
129     }
130     ASSERT_NOT_REACHED();
131     return 0;
132 }
133
134 int Position::computeOffsetInContainerNode() const
135 {
136     if (!m_anchorNode)
137         return 0;
138
139     switch (anchorType()) {
140     case PositionIsOffsetInAnchor:
141         return std::min(lastOffsetInNode(m_anchorNode.get()), m_offset);
142     case PositionIsBeforeAnchor:
143         return m_anchorNode->nodeIndex();
144     case PositionIsAfterAnchor:
145         return m_anchorNode->nodeIndex() + 1;
146     }
147     ASSERT_NOT_REACHED();
148     return 0;
149 }
150
151 Node* Position::computeNodeBeforePosition() const
152 {
153     if (!m_anchorNode)
154         return 0;
155
156     switch (anchorType()) {
157     case PositionIsOffsetInAnchor:
158         return m_anchorNode->childNode(m_offset - 1); // -1 converts to childNode((unsigned)-1) and returns null.
159     case PositionIsBeforeAnchor:
160         return m_anchorNode->previousSibling();
161     case PositionIsAfterAnchor:
162         return m_anchorNode.get();
163     }
164     ASSERT_NOT_REACHED();
165     return 0;
166 }
167
168 Node* Position::computeNodeAfterPosition() const
169 {
170     if (!m_anchorNode)
171         return 0;
172
173     switch (anchorType()) {
174     case PositionIsOffsetInAnchor:
175         return m_anchorNode->childNode(m_offset);
176     case PositionIsBeforeAnchor:
177         return m_anchorNode.get();
178     case PositionIsAfterAnchor:
179         return m_anchorNode->nextSibling();
180     }
181     ASSERT_NOT_REACHED();
182     return 0;
183 }
184
185 Position::AnchorType Position::anchorTypeForLegacyEditingPosition(Node* anchorNode, int offset)
186 {
187     if (anchorNode && editingIgnoresContent(anchorNode)) {
188         if (offset == 0)
189             return Position::PositionIsBeforeAnchor;
190         return Position::PositionIsAfterAnchor;
191     }
192     return Position::PositionIsOffsetInAnchor;
193 }
194
195 // FIXME: This method is confusing (does it return anchorNode() or containerNode()?) and should be renamed or removed
196 Element* Position::element() const
197 {
198     Node* n = anchorNode();
199     while (n && !n->isElementNode())
200         n = n->parentNode();
201     return static_cast<Element*>(n);
202 }
203
204 PassRefPtr<CSSComputedStyleDeclaration> Position::computedStyle() const
205 {
206     Element* elem = element();
207     if (!elem)
208         return 0;
209     return WebCore::computedStyle(elem);
210 }
211
212 Position Position::previous(PositionMoveType moveType) const
213 {
214     Node* n = node();
215     if (!n)
216         return *this;
217     
218     int o = m_offset;
219     // FIXME: Negative offsets shouldn't be allowed. We should catch this earlier.
220     ASSERT(o >= 0);
221
222     if (o > 0) {
223         Node* child = n->childNode(o - 1);
224         if (child)
225             return lastDeepEditingPositionForNode(child);
226
227         // There are two reasons child might be 0:
228         //   1) The node is node like a text node that is not an element, and therefore has no children.
229         //      Going backward one character at a time is correct.
230         //   2) The old offset was a bogus offset like (<br>, 1), and there is no child.
231         //      Going from 1 to 0 is correct.
232         switch (moveType) {
233         case CodePoint:
234             return Position(n, o - 1);
235         case Character:
236             return Position(n, uncheckedPreviousOffset(n, o));
237         case BackwardDeletion:
238             return Position(n, uncheckedPreviousOffsetForBackwardDeletion(n, o));
239         }
240     }
241
242     ContainerNode* parent = n->parentNode();
243     if (!parent)
244         return *this;
245
246     return Position(parent, n->nodeIndex());
247 }
248
249 Position Position::next(PositionMoveType moveType) const
250 {
251     ASSERT(moveType != BackwardDeletion);
252
253     Node* n = node();
254     if (!n)
255         return *this;
256     
257     int o = m_offset;
258     // FIXME: Negative offsets shouldn't be allowed. We should catch this earlier.
259     ASSERT(o >= 0);
260
261     Node* child = n->childNode(o);
262     if (child || (!n->hasChildNodes() && o < lastOffsetForEditing(n))) {
263         if (child)
264             return firstDeepEditingPositionForNode(child);
265
266         // There are two reasons child might be 0:
267         //   1) The node is node like a text node that is not an element, and therefore has no children.
268         //      Going forward one character at a time is correct.
269         //   2) The new offset is a bogus offset like (<br>, 1), and there is no child.
270         //      Going from 0 to 1 is correct.
271         return Position(n, (moveType == Character) ? uncheckedNextOffset(n, o) : o + 1);
272     }
273
274     ContainerNode* parent = n->parentNode();
275     if (!parent)
276         return *this;
277
278     return Position(parent, n->nodeIndex() + 1);
279 }
280
281 int Position::uncheckedPreviousOffset(const Node* n, int current)
282 {
283     return n->renderer() ? n->renderer()->previousOffset(current) : current - 1;
284 }
285
286 int Position::uncheckedPreviousOffsetForBackwardDeletion(const Node* n, int current)
287 {
288     return n->renderer() ? n->renderer()->previousOffsetForBackwardDeletion(current) : current - 1;
289 }
290
291 int Position::uncheckedNextOffset(const Node* n, int current)
292 {
293     return n->renderer() ? n->renderer()->nextOffset(current) : current + 1;
294 }
295
296 bool Position::atFirstEditingPositionForNode() const
297 {
298     if (isNull())
299         return true;
300     return m_offset <= 0;
301 }
302
303 bool Position::atLastEditingPositionForNode() const
304 {
305     if (isNull())
306         return true;
307     return m_offset >= lastOffsetForEditing(node());
308 }
309
310 // A position is considered at editing boundary if one of the following is true:
311 // 1. It is the first position in the node and the next visually equivalent position
312 //    is non editable.
313 // 2. It is the last position in the node and the previous visually equivalent position
314 //    is non editable.
315 // 3. It is an editable position and both the next and previous visually equivalent
316 //    positions are both non editable.
317 bool Position::atEditingBoundary() const
318 {
319     Position nextPosition = downstream(CanCrossEditingBoundary);
320     if (atFirstEditingPositionForNode() && nextPosition.isNotNull() && !nextPosition.node()->isContentEditable())
321         return true;
322         
323     Position prevPosition = upstream(CanCrossEditingBoundary);
324     if (atLastEditingPositionForNode() && prevPosition.isNotNull() && !prevPosition.node()->isContentEditable())
325         return true;
326         
327     return nextPosition.isNotNull() && !nextPosition.node()->isContentEditable()
328         && prevPosition.isNotNull() && !prevPosition.node()->isContentEditable();
329 }
330
331 Node* Position::parentEditingBoundary() const
332 {
333     if (!m_anchorNode || !m_anchorNode->document())
334         return 0;
335
336     Node* documentElement = m_anchorNode->document()->documentElement();
337     if (!documentElement)
338         return 0;
339
340     Node* boundary = m_anchorNode.get();
341     while (boundary != documentElement && boundary->parentNode() && m_anchorNode->isContentEditable() == boundary->parentNode()->isContentEditable())
342         boundary = boundary->parentNode();
343     
344     return boundary;
345 }
346
347
348 bool Position::atStartOfTree() const
349 {
350     if (isNull())
351         return true;
352     return !node()->parentNode() && m_offset <= 0;
353 }
354
355 bool Position::atEndOfTree() const
356 {
357     if (isNull())
358         return true;
359     return !node()->parentNode() && m_offset >= lastOffsetForEditing(node());
360 }
361
362 int Position::renderedOffset() const
363 {
364     if (!node()->isTextNode())
365         return m_offset;
366    
367     if (!node()->renderer())
368         return m_offset;
369                     
370     int result = 0;
371     RenderText *textRenderer = toRenderText(node()->renderer());
372     for (InlineTextBox *box = textRenderer->firstTextBox(); box; box = box->nextTextBox()) {
373         int start = box->start();
374         int end = box->start() + box->len();
375         if (m_offset < start)
376             return result;
377         if (m_offset <= end) {
378             result += m_offset - start;
379             return result;
380         }
381         result += box->len();
382     }
383     return result;
384 }
385
386 // return first preceding DOM position rendered at a different location, or "this"
387 Position Position::previousCharacterPosition(EAffinity affinity) const
388 {
389     if (isNull())
390         return Position();
391
392     Node *fromRootEditableElement = node()->rootEditableElement();
393
394     bool atStartOfLine = isStartOfLine(VisiblePosition(*this, affinity));
395     bool rendered = isCandidate();
396     
397     Position currentPos = *this;
398     while (!currentPos.atStartOfTree()) {
399         currentPos = currentPos.previous();
400
401         if (currentPos.node()->rootEditableElement() != fromRootEditableElement)
402             return *this;
403
404         if (atStartOfLine || !rendered) {
405             if (currentPos.isCandidate())
406                 return currentPos;
407         } else if (rendersInDifferentPosition(currentPos))
408             return currentPos;
409     }
410     
411     return *this;
412 }
413
414 // return first following position rendered at a different location, or "this"
415 Position Position::nextCharacterPosition(EAffinity affinity) const
416 {
417     if (isNull())
418         return Position();
419
420     Node *fromRootEditableElement = node()->rootEditableElement();
421
422     bool atEndOfLine = isEndOfLine(VisiblePosition(*this, affinity));
423     bool rendered = isCandidate();
424     
425     Position currentPos = *this;
426     while (!currentPos.atEndOfTree()) {
427         currentPos = currentPos.next();
428
429         if (currentPos.node()->rootEditableElement() != fromRootEditableElement)
430             return *this;
431
432         if (atEndOfLine || !rendered) {
433             if (currentPos.isCandidate())
434                 return currentPos;
435         } else if (rendersInDifferentPosition(currentPos))
436             return currentPos;
437     }
438     
439     return *this;
440 }
441
442 // Whether or not [node, 0] and [node, lastOffsetForEditing(node)] are their own VisiblePositions.
443 // If true, adjacent candidates are visually distinct.
444 // FIXME: Disregard nodes with renderers that have no height, as we do in isCandidate.
445 // FIXME: Share code with isCandidate, if possible.
446 static bool endsOfNodeAreVisuallyDistinctPositions(Node* node)
447 {
448     if (!node || !node->renderer())
449         return false;
450         
451     if (!node->renderer()->isInline())
452         return true;
453         
454     // Don't include inline tables.
455     if (node->hasTagName(tableTag))
456         return false;
457     
458     // There is a VisiblePosition inside an empty inline-block container.
459     return node->renderer()->isReplaced() && canHaveChildrenForEditing(node) && toRenderBox(node->renderer())->height() != 0 && !node->firstChild();
460 }
461
462 static Node* enclosingVisualBoundary(Node* node)
463 {
464     while (node && !endsOfNodeAreVisuallyDistinctPositions(node))
465         node = node->parentNode();
466         
467     return node;
468 }
469
470 // upstream() and downstream() want to return positions that are either in a
471 // text node or at just before a non-text node.  This method checks for that.
472 static bool isStreamer(const PositionIterator& pos)
473 {
474     if (!pos.node())
475         return true;
476         
477     if (isAtomicNode(pos.node()))
478         return true;
479         
480     return pos.atStartOfNode();
481 }
482
483 // This function and downstream() are used for moving back and forth between visually equivalent candidates.
484 // For example, for the text node "foo     bar" where whitespace is collapsible, there are two candidates 
485 // that map to the VisiblePosition between 'b' and the space.  This function will return the left candidate 
486 // and downstream() will return the right one.
487 // Also, upstream() will return [boundary, 0] for any of the positions from [boundary, 0] to the first candidate
488 // in boundary, where endsOfNodeAreVisuallyDistinctPositions(boundary) is true.
489 Position Position::upstream(EditingBoundaryCrossingRule rule) const
490 {
491     Node* startNode = node();
492     if (!startNode)
493         return Position();
494     
495     // iterate backward from there, looking for a qualified position
496     Node* boundary = enclosingVisualBoundary(startNode);
497     PositionIterator lastVisible = *this;
498     PositionIterator currentPos = lastVisible;
499     bool startEditable = startNode->isContentEditable();
500     Node* lastNode = startNode;
501     bool boundaryCrossed = false;
502     for (; !currentPos.atStart(); currentPos.decrement()) {
503         Node* currentNode = currentPos.node();
504         
505         // Don't check for an editability change if we haven't moved to a different node,
506         // to avoid the expense of computing isContentEditable().
507         if (currentNode != lastNode) {
508             // Don't change editability.
509             bool currentEditable = currentNode->isContentEditable();
510             if (startEditable != currentEditable) {
511                 if (rule == CannotCrossEditingBoundary)
512                     break;
513                 boundaryCrossed = true;
514             }
515             lastNode = currentNode;
516         }
517
518         // If we've moved to a position that is visually distinct, return the last saved position. There 
519         // is code below that terminates early if we're *about* to move to a visually distinct position.
520         if (endsOfNodeAreVisuallyDistinctPositions(currentNode) && currentNode != boundary)
521             return lastVisible;
522
523         // skip position in unrendered or invisible node
524         RenderObject* renderer = currentNode->renderer();
525         if (!renderer || renderer->style()->visibility() != VISIBLE)
526             continue;
527                  
528         if (rule == CanCrossEditingBoundary && boundaryCrossed) {
529             lastVisible = currentPos;
530             break;
531         }
532         
533         // track last visible streamer position
534         if (isStreamer(currentPos))
535             lastVisible = currentPos;
536         
537         // Don't move past a position that is visually distinct.  We could rely on code above to terminate and 
538         // return lastVisible on the next iteration, but we terminate early to avoid doing a nodeIndex() call.
539         if (endsOfNodeAreVisuallyDistinctPositions(currentNode) && currentPos.atStartOfNode())
540             return lastVisible;
541
542         // Return position after tables and nodes which have content that can be ignored.
543         if (editingIgnoresContent(currentNode) || isTableElement(currentNode)) {
544             if (currentPos.atEndOfNode())
545                 return lastDeepEditingPositionForNode(currentNode);
546             continue;
547         }
548
549         // return current position if it is in rendered text
550         if (renderer->isText() && toRenderText(renderer)->firstTextBox()) {
551             if (currentNode != startNode) {
552                 // This assertion fires in layout tests in the case-transform.html test because
553                 // of a mix-up between offsets in the text in the DOM tree with text in the
554                 // render tree which can have a different length due to case transformation.
555                 // Until we resolve that, disable this so we can run the layout tests!
556                 //ASSERT(currentOffset >= renderer->caretMaxOffset());
557                 return Position(currentNode, renderer->caretMaxOffset());
558             }
559
560             unsigned textOffset = currentPos.offsetInLeafNode();
561             RenderText* textRenderer = toRenderText(renderer);
562             InlineTextBox* lastTextBox = textRenderer->lastTextBox();
563             for (InlineTextBox* box = textRenderer->firstTextBox(); box; box = box->nextTextBox()) {
564                 if (textOffset <= box->start() + box->len()) {
565                     if (textOffset > box->start())
566                         return currentPos;
567                     continue;
568                 }
569
570                 if (box == lastTextBox || textOffset != box->start() + box->len() + 1)
571                     continue;
572
573                 // The text continues on the next line only if the last text box is not on this line and
574                 // none of the boxes on this line have a larger start offset.
575
576                 bool continuesOnNextLine = true;
577                 InlineBox* otherBox = box;
578                 while (continuesOnNextLine) {
579                     otherBox = otherBox->nextLeafChild();
580                     if (!otherBox)
581                         break;
582                     if (otherBox == lastTextBox || (otherBox->renderer() == textRenderer && static_cast<InlineTextBox*>(otherBox)->start() > textOffset))
583                         continuesOnNextLine = false;
584                 }
585
586                 otherBox = box;
587                 while (continuesOnNextLine) {
588                     otherBox = otherBox->prevLeafChild();
589                     if (!otherBox)
590                         break;
591                     if (otherBox == lastTextBox || (otherBox->renderer() == textRenderer && static_cast<InlineTextBox*>(otherBox)->start() > textOffset))
592                         continuesOnNextLine = false;
593                 }
594
595                 if (continuesOnNextLine)
596                     return currentPos;
597             }
598         }
599     }
600
601     return lastVisible;
602 }
603
604 // This function and upstream() are used for moving back and forth between visually equivalent candidates.
605 // For example, for the text node "foo     bar" where whitespace is collapsible, there are two candidates 
606 // that map to the VisiblePosition between 'b' and the space.  This function will return the right candidate 
607 // and upstream() will return the left one.
608 // Also, downstream() will return the last position in the last atomic node in boundary for all of the positions
609 // in boundary after the last candidate, where endsOfNodeAreVisuallyDistinctPositions(boundary).
610 Position Position::downstream(EditingBoundaryCrossingRule rule) const
611 {
612     Node* startNode = node();
613     if (!startNode)
614         return Position();
615
616     // iterate forward from there, looking for a qualified position
617     Node* boundary = enclosingVisualBoundary(startNode);
618     PositionIterator lastVisible = *this;
619     PositionIterator currentPos = lastVisible;
620     bool startEditable = startNode->isContentEditable();
621     Node* lastNode = startNode;
622     bool boundaryCrossed = false;
623     for (; !currentPos.atEnd(); currentPos.increment()) {   
624         Node* currentNode = currentPos.node();
625         
626         // Don't check for an editability change if we haven't moved to a different node,
627         // to avoid the expense of computing isContentEditable().
628         if (currentNode != lastNode) {
629             // Don't change editability.
630             bool currentEditable = currentNode->isContentEditable();
631             if (startEditable != currentEditable) {
632                 if (rule == CannotCrossEditingBoundary)
633                     break;
634                 boundaryCrossed = true;
635             }
636                 
637             lastNode = currentNode;
638         }
639
640         // stop before going above the body, up into the head
641         // return the last visible streamer position
642         if (currentNode->hasTagName(bodyTag) && currentPos.atEndOfNode())
643             break;
644             
645         // Do not move to a visually distinct position.
646         if (endsOfNodeAreVisuallyDistinctPositions(currentNode) && currentNode != boundary)
647             return lastVisible;
648         // Do not move past a visually disinct position.
649         // Note: The first position after the last in a node whose ends are visually distinct
650         // positions will be [boundary->parentNode(), originalBlock->nodeIndex() + 1].
651         if (boundary && boundary->parentNode() == currentNode)
652             return lastVisible;
653
654         // skip position in unrendered or invisible node
655         RenderObject* renderer = currentNode->renderer();
656         if (!renderer || renderer->style()->visibility() != VISIBLE)
657             continue;
658             
659         if (rule == CanCrossEditingBoundary && boundaryCrossed) {
660             lastVisible = currentPos;
661             break;
662         }
663         
664         // track last visible streamer position
665         if (isStreamer(currentPos))
666             lastVisible = currentPos;
667
668         // Return position before tables and nodes which have content that can be ignored.
669         if (editingIgnoresContent(currentNode) || isTableElement(currentNode)) {
670             if (currentPos.offsetInLeafNode() <= renderer->caretMinOffset())
671                 return Position(currentNode, renderer->caretMinOffset());
672             continue;
673         }
674
675         // return current position if it is in rendered text
676         if (renderer->isText() && toRenderText(renderer)->firstTextBox()) {
677             if (currentNode != startNode) {
678                 ASSERT(currentPos.atStartOfNode());
679                 return Position(currentNode, renderer->caretMinOffset());
680             }
681
682             unsigned textOffset = currentPos.offsetInLeafNode();
683             RenderText* textRenderer = toRenderText(renderer);
684             InlineTextBox* lastTextBox = textRenderer->lastTextBox();
685             for (InlineTextBox* box = textRenderer->firstTextBox(); box; box = box->nextTextBox()) {
686                 if (textOffset <= box->end()) {
687                     if (textOffset >= box->start())
688                         return currentPos;
689                     continue;
690                 }
691
692                 if (box == lastTextBox || textOffset != box->start() + box->len())
693                     continue;
694
695                 // The text continues on the next line only if the last text box is not on this line and
696                 // none of the boxes on this line have a larger start offset.
697
698                 bool continuesOnNextLine = true;
699                 InlineBox* otherBox = box;
700                 while (continuesOnNextLine) {
701                     otherBox = otherBox->nextLeafChild();
702                     if (!otherBox)
703                         break;
704                     if (otherBox == lastTextBox || (otherBox->renderer() == textRenderer && static_cast<InlineTextBox*>(otherBox)->start() >= textOffset))
705                         continuesOnNextLine = false;
706                 }
707
708                 otherBox = box;
709                 while (continuesOnNextLine) {
710                     otherBox = otherBox->prevLeafChild();
711                     if (!otherBox)
712                         break;
713                     if (otherBox == lastTextBox || (otherBox->renderer() == textRenderer && static_cast<InlineTextBox*>(otherBox)->start() >= textOffset))
714                         continuesOnNextLine = false;
715                 }
716
717                 if (continuesOnNextLine)
718                     return currentPos;
719             }
720         }
721     }
722     
723     return lastVisible;
724 }
725
726 bool Position::hasRenderedNonAnonymousDescendantsWithHeight(RenderObject* renderer)
727 {
728     RenderObject* stop = renderer->nextInPreOrderAfterChildren();
729     for (RenderObject *o = renderer->firstChild(); o && o != stop; o = o->nextInPreOrder())
730         if (o->node()) {
731             if ((o->isText() && toRenderText(o)->linesBoundingBox().height()) ||
732                 (o->isBox() && toRenderBox(o)->borderBoundingBox().height()))
733                 return true;
734         }
735     return false;
736 }
737
738 bool Position::nodeIsUserSelectNone(Node* node)
739 {
740     return node && node->renderer() && node->renderer()->style()->userSelect() == SELECT_NONE;
741 }
742
743 bool Position::isCandidate() const
744 {
745     if (isNull())
746         return false;
747         
748     RenderObject *renderer = node()->renderer();
749     if (!renderer)
750         return false;
751     
752     if (renderer->style()->visibility() != VISIBLE)
753         return false;
754
755     if (renderer->isBR())
756         return m_offset == 0 && !nodeIsUserSelectNone(node()->parent());
757
758     if (renderer->isText())
759         return !nodeIsUserSelectNone(node()) && inRenderedText();
760
761     if (isTableElement(node()) || editingIgnoresContent(node()))
762         return (atFirstEditingPositionForNode() || atLastEditingPositionForNode()) && !nodeIsUserSelectNone(node()->parent());
763
764     if (m_anchorNode->hasTagName(htmlTag))
765         return false;
766         
767     if (renderer->isBlockFlow()) {
768         if (toRenderBlock(renderer)->height() || m_anchorNode->hasTagName(bodyTag)) {
769             if (!Position::hasRenderedNonAnonymousDescendantsWithHeight(renderer))
770                 return atFirstEditingPositionForNode() && !Position::nodeIsUserSelectNone(node());
771             return m_anchorNode->isContentEditable() && !Position::nodeIsUserSelectNone(node()) && atEditingBoundary();
772         }
773     } else
774         return m_anchorNode->isContentEditable() && !Position::nodeIsUserSelectNone(node()) && atEditingBoundary();
775
776     return false;
777 }
778
779 bool Position::inRenderedText() const
780 {
781     if (isNull() || !node()->isTextNode())
782         return false;
783         
784     RenderObject *renderer = node()->renderer();
785     if (!renderer)
786         return false;
787     
788     RenderText *textRenderer = toRenderText(renderer);
789     for (InlineTextBox *box = textRenderer->firstTextBox(); box; box = box->nextTextBox()) {
790         if (m_offset < static_cast<int>(box->start()) && !textRenderer->containsReversedText()) {
791             // The offset we're looking for is before this node
792             // this means the offset must be in content that is
793             // not rendered. Return false.
794             return false;
795         }
796         if (box->containsCaretOffset(m_offset))
797             // Return false for offsets inside composed characters.
798             return m_offset == 0 || m_offset == textRenderer->nextOffset(textRenderer->previousOffset(m_offset));
799     }
800     
801     return false;
802 }
803
804 static unsigned caretMaxRenderedOffset(const Node* n)
805 {
806     RenderObject* r = n->renderer();
807     if (r)
808         return r->caretMaxRenderedOffset();
809     
810     if (n->isCharacterDataNode())
811         return static_cast<const CharacterData*>(n)->length();
812     return 1;
813 }
814
815 bool Position::isRenderedCharacter() const
816 {
817     if (isNull() || !node()->isTextNode())
818         return false;
819         
820     RenderObject* renderer = node()->renderer();
821     if (!renderer)
822         return false;
823     
824     RenderText* textRenderer = toRenderText(renderer);
825     for (InlineTextBox* box = textRenderer->firstTextBox(); box; box = box->nextTextBox()) {
826         if (m_offset < static_cast<int>(box->start()) && !textRenderer->containsReversedText()) {
827             // The offset we're looking for is before this node
828             // this means the offset must be in content that is
829             // not rendered. Return false.
830             return false;
831         }
832         if (m_offset >= static_cast<int>(box->start()) && m_offset < static_cast<int>(box->start() + box->len()))
833             return true;
834     }
835     
836     return false;
837 }
838
839 bool Position::rendersInDifferentPosition(const Position &pos) const
840 {
841     if (isNull() || pos.isNull())
842         return false;
843
844     RenderObject *renderer = node()->renderer();
845     if (!renderer)
846         return false;
847     
848     RenderObject *posRenderer = pos.node()->renderer();
849     if (!posRenderer)
850         return false;
851
852     if (renderer->style()->visibility() != VISIBLE ||
853         posRenderer->style()->visibility() != VISIBLE)
854         return false;
855     
856     if (node() == pos.node()) {
857         if (node()->hasTagName(brTag))
858             return false;
859
860         if (m_offset == pos.deprecatedEditingOffset())
861             return false;
862             
863         if (!node()->isTextNode() && !pos.node()->isTextNode()) {
864             if (m_offset != pos.deprecatedEditingOffset())
865                 return true;
866         }
867     }
868     
869     if (node()->hasTagName(brTag) && pos.isCandidate())
870         return true;
871                 
872     if (pos.node()->hasTagName(brTag) && isCandidate())
873         return true;
874                 
875     if (node()->enclosingBlockFlowElement() != pos.node()->enclosingBlockFlowElement())
876         return true;
877
878     if (node()->isTextNode() && !inRenderedText())
879         return false;
880
881     if (pos.node()->isTextNode() && !pos.inRenderedText())
882         return false;
883
884     int thisRenderedOffset = renderedOffset();
885     int posRenderedOffset = pos.renderedOffset();
886
887     if (renderer == posRenderer && thisRenderedOffset == posRenderedOffset)
888         return false;
889
890     int ignoredCaretOffset;
891     InlineBox* b1;
892     getInlineBoxAndOffset(DOWNSTREAM, b1, ignoredCaretOffset);
893     InlineBox* b2;
894     pos.getInlineBoxAndOffset(DOWNSTREAM, b2, ignoredCaretOffset);
895
896     LOG(Editing, "renderer:               %p [%p]\n", renderer, b1);
897     LOG(Editing, "thisRenderedOffset:         %d\n", thisRenderedOffset);
898     LOG(Editing, "posRenderer:            %p [%p]\n", posRenderer, b2);
899     LOG(Editing, "posRenderedOffset:      %d\n", posRenderedOffset);
900     LOG(Editing, "node min/max:           %d:%d\n", caretMinOffset(node()), caretMaxRenderedOffset(node()));
901     LOG(Editing, "pos node min/max:       %d:%d\n", caretMinOffset(pos.node()), caretMaxRenderedOffset(pos.node()));
902     LOG(Editing, "----------------------------------------------------------------------\n");
903
904     if (!b1 || !b2) {
905         return false;
906     }
907
908     if (b1->root() != b2->root()) {
909         return true;
910     }
911
912     if (nextRenderedEditable(node()) == pos.node() && 
913         thisRenderedOffset == (int)caretMaxRenderedOffset(node()) && posRenderedOffset == 0) {
914         return false;
915     }
916     
917     if (previousRenderedEditable(node()) == pos.node() && 
918         thisRenderedOffset == 0 && posRenderedOffset == (int)caretMaxRenderedOffset(pos.node())) {
919         return false;
920     }
921
922     return true;
923 }
924
925 // This assumes that it starts in editable content.
926 Position Position::leadingWhitespacePosition(EAffinity affinity, bool considerNonCollapsibleWhitespace) const
927 {
928     ASSERT(isEditablePosition(*this));
929     if (isNull())
930         return Position();
931     
932     if (upstream().node()->hasTagName(brTag))
933         return Position();
934
935     Position prev = previousCharacterPosition(affinity);
936     if (prev != *this && prev.node()->inSameContainingBlockFlowElement(node()) && prev.node()->isTextNode()) {
937         String string = static_cast<Text *>(prev.node())->data();
938         UChar c = string[prev.deprecatedEditingOffset()];
939         if (considerNonCollapsibleWhitespace ? (isSpaceOrNewline(c) || c == noBreakSpace) : isCollapsibleWhitespace(c))
940             if (isEditablePosition(prev))
941                 return prev;
942     }
943
944     return Position();
945 }
946
947 // This assumes that it starts in editable content.
948 Position Position::trailingWhitespacePosition(EAffinity, bool considerNonCollapsibleWhitespace) const
949 {
950     ASSERT(isEditablePosition(*this));
951     if (isNull())
952         return Position();
953     
954     VisiblePosition v(*this);
955     UChar c = v.characterAfter();
956     // The space must not be in another paragraph and it must be editable.
957     if (!isEndOfParagraph(v) && v.next(true).isNotNull())
958         if (considerNonCollapsibleWhitespace ? (isSpaceOrNewline(c) || c == noBreakSpace) : isCollapsibleWhitespace(c))
959             return *this;
960     
961     return Position();
962 }
963
964 void Position::getInlineBoxAndOffset(EAffinity affinity, InlineBox*& inlineBox, int& caretOffset) const
965 {
966     getInlineBoxAndOffset(affinity, primaryDirection(), inlineBox, caretOffset);
967 }
968
969 static bool isNonTextLeafChild(RenderObject* object)
970 {
971     if (object->firstChild())
972         return false;
973     if (object->isText())
974         return false;
975     return true;
976 }
977
978 static InlineTextBox* searchAheadForBetterMatch(RenderObject* renderer)
979 {
980     RenderBlock* container = renderer->containingBlock();
981     RenderObject* next = renderer;
982     while ((next = next->nextInPreOrder(container))) {
983         if (next->isRenderBlock())
984             return 0;
985         if (next->isBR())
986             return 0;
987         if (isNonTextLeafChild(next))
988             return 0;
989         if (next->isText()) {
990             InlineTextBox* match = 0;
991             int minOffset = INT_MAX;
992             for (InlineTextBox* box = toRenderText(next)->firstTextBox(); box; box = box->nextTextBox()) {
993                 int caretMinOffset = box->caretMinOffset();
994                 if (caretMinOffset < minOffset) {
995                     match = box;
996                     minOffset = caretMinOffset;
997                 }
998             }
999             if (match)
1000                 return match;
1001         }
1002     }
1003     return 0;
1004 }
1005
1006 static Position downstreamIgnoringEditingBoundaries(Position position)
1007 {
1008     Position lastPosition;
1009     while (position != lastPosition) {
1010         lastPosition = position;
1011         position = position.downstream(Position::CanCrossEditingBoundary);
1012     }
1013     return position;
1014 }
1015
1016 static Position upstreamIgnoringEditingBoundaries(Position position)
1017 {
1018     Position lastPosition;
1019     while (position != lastPosition) {
1020         lastPosition = position;
1021         position = position.upstream(Position::CanCrossEditingBoundary);
1022     }
1023     return position;
1024 }
1025
1026 void Position::getInlineBoxAndOffset(EAffinity affinity, TextDirection primaryDirection, InlineBox*& inlineBox, int& caretOffset) const
1027 {
1028     caretOffset = m_offset;
1029     RenderObject* renderer = node()->renderer();
1030
1031     if (!renderer->isText()) {
1032         inlineBox = 0;
1033         if (canHaveChildrenForEditing(node()) && renderer->isBlockFlow() && hasRenderedNonAnonymousDescendantsWithHeight(renderer)) {
1034             // Try a visually equivalent position with possibly opposite editability. This helps in case |this| is in
1035             // an editable block but surrounded by non-editable positions. It acts to negate the logic at the beginning
1036             // of RenderObject::createVisiblePosition().
1037             Position equivalent = downstreamIgnoringEditingBoundaries(*this);
1038             if (equivalent == *this) {
1039                 equivalent = upstreamIgnoringEditingBoundaries(*this);
1040                 if (equivalent == *this || downstreamIgnoringEditingBoundaries(equivalent) == *this)
1041                     return;
1042             }
1043
1044             equivalent.getInlineBoxAndOffset(UPSTREAM, primaryDirection, inlineBox, caretOffset);
1045             return;
1046         }
1047         if (renderer->isBox()) {
1048             inlineBox = toRenderBox(renderer)->inlineBoxWrapper();
1049             if (!inlineBox || (caretOffset > inlineBox->caretMinOffset() && caretOffset < inlineBox->caretMaxOffset()))
1050                 return;
1051         }
1052     } else {
1053         RenderText* textRenderer = toRenderText(renderer);
1054
1055         InlineTextBox* box;
1056         InlineTextBox* candidate = 0;
1057
1058         for (box = textRenderer->firstTextBox(); box; box = box->nextTextBox()) {
1059             int caretMinOffset = box->caretMinOffset();
1060             int caretMaxOffset = box->caretMaxOffset();
1061
1062             if (caretOffset < caretMinOffset || caretOffset > caretMaxOffset || (caretOffset == caretMaxOffset && box->isLineBreak()))
1063                 continue;
1064
1065             if (caretOffset > caretMinOffset && caretOffset < caretMaxOffset) {
1066                 inlineBox = box;
1067                 return;
1068             }
1069
1070             if (((caretOffset == caretMaxOffset) ^ (affinity == DOWNSTREAM))
1071                 || ((caretOffset == caretMinOffset) ^ (affinity == UPSTREAM)))
1072                 break;
1073
1074             candidate = box;
1075         }
1076         if (candidate && candidate == textRenderer->lastTextBox() && affinity == DOWNSTREAM) {
1077             box = searchAheadForBetterMatch(textRenderer);
1078             if (box)
1079                 caretOffset = box->caretMinOffset();
1080         }
1081         inlineBox = box ? box : candidate;
1082     }
1083
1084     if (!inlineBox)
1085         return;
1086
1087     unsigned char level = inlineBox->bidiLevel();
1088
1089     if (inlineBox->direction() == primaryDirection) {
1090         if (caretOffset == inlineBox->caretRightmostOffset()) {
1091             InlineBox* nextBox = inlineBox->nextLeafChild();
1092             if (!nextBox || nextBox->bidiLevel() >= level)
1093                 return;
1094
1095             level = nextBox->bidiLevel();
1096             InlineBox* prevBox = inlineBox;
1097             do {
1098                 prevBox = prevBox->prevLeafChild();
1099             } while (prevBox && prevBox->bidiLevel() > level);
1100
1101             if (prevBox && prevBox->bidiLevel() == level)   // For example, abc FED 123 ^ CBA
1102                 return;
1103
1104             // For example, abc 123 ^ CBA
1105             while (InlineBox* nextBox = inlineBox->nextLeafChild()) {
1106                 if (nextBox->bidiLevel() < level)
1107                     break;
1108                 inlineBox = nextBox;
1109             }
1110             caretOffset = inlineBox->caretRightmostOffset();
1111         } else {
1112             InlineBox* prevBox = inlineBox->prevLeafChild();
1113             if (!prevBox || prevBox->bidiLevel() >= level)
1114                 return;
1115
1116             level = prevBox->bidiLevel();
1117             InlineBox* nextBox = inlineBox;
1118             do {
1119                 nextBox = nextBox->nextLeafChild();
1120             } while (nextBox && nextBox->bidiLevel() > level);
1121
1122             if (nextBox && nextBox->bidiLevel() == level)
1123                 return;
1124
1125             while (InlineBox* prevBox = inlineBox->prevLeafChild()) {
1126                 if (prevBox->bidiLevel() < level)
1127                     break;
1128                 inlineBox = prevBox;
1129             }
1130             caretOffset = inlineBox->caretLeftmostOffset();
1131         }
1132         return;
1133     }
1134
1135     if (caretOffset == inlineBox->caretLeftmostOffset()) {
1136         InlineBox* prevBox = inlineBox->prevLeafChild();
1137         if (!prevBox || prevBox->bidiLevel() < level) {
1138             // Left edge of a secondary run. Set to the right edge of the entire run.
1139             while (InlineBox* nextBox = inlineBox->nextLeafChild()) {
1140                 if (nextBox->bidiLevel() < level)
1141                     break;
1142                 inlineBox = nextBox;
1143             }
1144             caretOffset = inlineBox->caretRightmostOffset();
1145         } else if (prevBox->bidiLevel() > level) {
1146             // Right edge of a "tertiary" run. Set to the left edge of that run.
1147             while (InlineBox* tertiaryBox = inlineBox->prevLeafChild()) {
1148                 if (tertiaryBox->bidiLevel() <= level)
1149                     break;
1150                 inlineBox = tertiaryBox;
1151             }
1152             caretOffset = inlineBox->caretLeftmostOffset();
1153         }
1154     } else {
1155         InlineBox* nextBox = inlineBox->nextLeafChild();
1156         if (!nextBox || nextBox->bidiLevel() < level) {
1157             // Right edge of a secondary run. Set to the left edge of the entire run.
1158             while (InlineBox* prevBox = inlineBox->prevLeafChild()) {
1159                 if (prevBox->bidiLevel() < level)
1160                     break;
1161                 inlineBox = prevBox;
1162             }
1163             caretOffset = inlineBox->caretLeftmostOffset();
1164         } else if (nextBox->bidiLevel() > level) {
1165             // Left edge of a "tertiary" run. Set to the right edge of that run.
1166             while (InlineBox* tertiaryBox = inlineBox->nextLeafChild()) {
1167                 if (tertiaryBox->bidiLevel() <= level)
1168                     break;
1169                 inlineBox = tertiaryBox;
1170             }
1171             caretOffset = inlineBox->caretRightmostOffset();
1172         }
1173     }
1174 }
1175
1176 TextDirection Position::primaryDirection() const
1177 {
1178     TextDirection primaryDirection = LTR;
1179     for (const RenderObject* r = m_anchorNode->renderer(); r; r = r->parent()) {
1180         if (r->isBlockFlow()) {
1181             primaryDirection = r->style()->direction();
1182             break;
1183         }
1184     }
1185
1186     return primaryDirection;
1187 }
1188
1189
1190 void Position::debugPosition(const char* msg) const
1191 {
1192     if (isNull())
1193         fprintf(stderr, "Position [%s]: null\n", msg);
1194     else
1195         fprintf(stderr, "Position [%s]: %s [%p] at %d\n", msg, node()->nodeName().utf8().data(), node(), m_offset);
1196 }
1197
1198 #ifndef NDEBUG
1199
1200 void Position::formatForDebugger(char* buffer, unsigned length) const
1201 {
1202     String result;
1203     
1204     if (isNull())
1205         result = "<null>";
1206     else {
1207         char s[1024];
1208         result += "offset ";
1209         result += String::number(m_offset);
1210         result += " of ";
1211         node()->formatForDebugger(s, sizeof(s));
1212         result += s;
1213     }
1214           
1215     strncpy(buffer, result.utf8().data(), length - 1);
1216 }
1217
1218 void Position::showTreeForThis() const
1219 {
1220     if (node()) {
1221         node()->showTreeForThis();
1222         fprintf(stderr, "offset: %d\n", m_offset);
1223     }
1224 }
1225
1226 #endif
1227
1228
1229
1230 } // namespace WebCore
1231
1232 #ifndef NDEBUG
1233
1234 void showTree(const WebCore::Position& pos)
1235 {
1236     pos.showTreeForThis();
1237 }
1238
1239 void showTree(const WebCore::Position* pos)
1240 {
1241     if (pos)
1242         pos->showTreeForThis();
1243 }
1244
1245 #endif