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