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