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