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