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