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