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