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