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