Use a 1-byte enum class for TextDirection
[WebKit-https.git] / Source / WebCore / editing / Editing.cpp
1 /*
2  * Copyright (C) 2004-2007, 2016 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 "Editing.h"
28
29 #include "AXObjectCache.h"
30 #include "Document.h"
31 #include "Editor.h"
32 #include "Frame.h"
33 #include "HTMLBodyElement.h"
34 #include "HTMLDListElement.h"
35 #include "HTMLDivElement.h"
36 #include "HTMLElementFactory.h"
37 #include "HTMLInterchange.h"
38 #include "HTMLLIElement.h"
39 #include "HTMLNames.h"
40 #include "HTMLOListElement.h"
41 #include "HTMLParagraphElement.h"
42 #include "HTMLSpanElement.h"
43 #include "HTMLTableElement.h"
44 #include "HTMLTextFormControlElement.h"
45 #include "HTMLUListElement.h"
46 #include "NodeTraversal.h"
47 #include "PositionIterator.h"
48 #include "RenderBlock.h"
49 #include "RenderElement.h"
50 #include "RenderTableCell.h"
51 #include "ShadowRoot.h"
52 #include "Text.h"
53 #include "TextIterator.h"
54 #include "VisibleUnits.h"
55 #include <wtf/Assertions.h>
56 #include <wtf/StdLibExtras.h>
57 #include <wtf/text/StringBuilder.h>
58 #include <wtf/unicode/CharacterNames.h>
59
60 namespace WebCore {
61
62 using namespace HTMLNames;
63
64 static bool isVisiblyAdjacent(const Position&, const Position&);
65
66 bool canHaveChildrenForEditing(const Node& node)
67 {
68     return !is<Text>(node) && node.canContainRangeEndPoint();
69 }
70
71 // Atomic means that the node has no children, or has children which are ignored for the purposes of editing.
72 bool isAtomicNode(const Node* node)
73 {
74     return node && (!node->hasChildNodes() || editingIgnoresContent(*node));
75 }
76
77 // Compare two positions, taking into account the possibility that one or both
78 // could be inside a shadow tree. Only works for non-null values.
79 int comparePositions(const Position& a, const Position& b)
80 {
81     TreeScope* commonScope = commonTreeScope(a.containerNode(), b.containerNode());
82
83     if (!commonScope)
84         return 0;
85
86     Node* nodeA = commonScope->ancestorNodeInThisScope(a.containerNode());
87     ASSERT(nodeA);
88     bool hasDescendentA = nodeA != a.containerNode();
89     int offsetA = hasDescendentA ? 0 : a.computeOffsetInContainerNode();
90
91     Node* nodeB = commonScope->ancestorNodeInThisScope(b.containerNode());
92     ASSERT(nodeB);
93     bool hasDescendentB = nodeB != b.containerNode();
94     int offsetB = hasDescendentB ? 0 : b.computeOffsetInContainerNode();
95
96     int bias = 0;
97     if (nodeA == nodeB) {
98         if (hasDescendentA)
99             bias = -1;
100         else if (hasDescendentB)
101             bias = 1;
102     }
103
104     auto comparisonResult = Range::compareBoundaryPoints(nodeA, offsetA, nodeB, offsetB);
105     if (comparisonResult.hasException())
106         return bias;
107     auto result = comparisonResult.releaseReturnValue();
108     return result ? result : bias;
109 }
110
111 int comparePositions(const VisiblePosition& a, const VisiblePosition& b)
112 {
113     return comparePositions(a.deepEquivalent(), b.deepEquivalent());
114 }
115
116 ContainerNode* highestEditableRoot(const Position& position, EditableType editableType)
117 {
118     ContainerNode* highestEditableRoot = editableRootForPosition(position, editableType);
119     if (!highestEditableRoot)
120         return nullptr;
121
122     for (ContainerNode* node = highestEditableRoot; !is<HTMLBodyElement>(*node); ) {
123         node = node->parentNode();
124         if (!node)
125             break;
126         // FIXME: Can this ever be a Document or DocumentFragment? If not, this should return Element* instead.
127         if (hasEditableStyle(*node, editableType))
128             highestEditableRoot = node;
129     }
130
131     return highestEditableRoot;
132 }
133
134 Element* lowestEditableAncestor(Node* node)
135 {
136     for (; node; node = node->parentNode()) {
137         if (node->hasEditableStyle())
138             return node->rootEditableElement();
139         if (is<HTMLBodyElement>(*node))
140             break;
141     }
142     return nullptr;
143 }
144
145 static bool isEditableToAccessibility(const Node& node)
146 {
147     ASSERT(AXObjectCache::accessibilityEnabled());
148     ASSERT(node.document().existingAXObjectCache());
149
150     if (auto* cache = node.document().existingAXObjectCache())
151         return cache->rootAXEditableElement(&node);
152
153     return false;
154 }
155
156 static bool computeEditability(const Node& node, EditableType editableType, Node::ShouldUpdateStyle shouldUpdateStyle)
157 {
158     if (node.computeEditability(Node::UserSelectAllIsAlwaysNonEditable, shouldUpdateStyle) != Node::Editability::ReadOnly)
159         return true;
160
161     switch (editableType) {
162     case ContentIsEditable:
163         return false;
164     case HasEditableAXRole:
165         return isEditableToAccessibility(node);
166     }
167     ASSERT_NOT_REACHED();
168     return false;
169 }
170
171 bool hasEditableStyle(const Node& node, EditableType editableType)
172 {
173     return computeEditability(node, editableType, Node::ShouldUpdateStyle::DoNotUpdate);
174 }
175
176 bool isEditableNode(const Node& node)
177 {
178     return computeEditability(node, ContentIsEditable, Node::ShouldUpdateStyle::Update);
179 }
180
181 bool isEditablePosition(const Position& position, EditableType editableType)
182 {
183     Node* node = position.containerNode();
184     return node && computeEditability(*node, editableType, Node::ShouldUpdateStyle::Update);
185 }
186
187 bool isAtUnsplittableElement(const Position& position)
188 {
189     Node* node = position.containerNode();
190     return node == editableRootForPosition(position) || node == enclosingNodeOfType(position, isTableCell);
191 }
192
193 bool isRichlyEditablePosition(const Position& position)
194 {
195     auto* node = position.containerNode();
196     return node && node->hasRichlyEditableStyle();
197 }
198
199 Element* editableRootForPosition(const Position& position, EditableType editableType)
200 {
201     Node* node = position.containerNode();
202     if (!node)
203         return nullptr;
204
205     switch (editableType) {
206     case HasEditableAXRole:
207         if (auto* cache = node->document().existingAXObjectCache())
208             return const_cast<Element*>(cache->rootAXEditableElement(node));
209         FALLTHROUGH;
210     case ContentIsEditable:
211         return node->rootEditableElement();
212     }
213     return nullptr;
214 }
215
216 // Finds the enclosing element until which the tree can be split.
217 // When a user hits ENTER, he/she won't expect this element to be split into two.
218 // You may pass it as the second argument of splitTreeToNode.
219 Element* unsplittableElementForPosition(const Position& position)
220 {
221     // Since enclosingNodeOfType won't search beyond the highest root editable node,
222     // this code works even if the closest table cell was outside of the root editable node.
223     if (auto* enclosingCell = downcast<Element>(enclosingNodeOfType(position, &isTableCell)))
224         return enclosingCell;
225     return editableRootForPosition(position);
226 }
227
228 Position nextCandidate(const Position& position)
229 {
230     for (PositionIterator nextPosition = position; !nextPosition.atEnd(); ) {
231         nextPosition.increment();
232         if (nextPosition.isCandidate())
233             return nextPosition;
234     }
235     return { };
236 }
237
238 Position nextVisuallyDistinctCandidate(const Position& position)
239 {
240     // FIXME: Use PositionIterator instead.
241     Position nextPosition = position;
242     Position downstreamStart = nextPosition.downstream();
243     while (!nextPosition.atEndOfTree()) {
244         nextPosition = nextPosition.next(Character);
245         if (nextPosition.isCandidate() && nextPosition.downstream() != downstreamStart)
246             return nextPosition;
247         if (auto* node = nextPosition.containerNode()) {
248             if (!node->renderer())
249                 nextPosition = lastPositionInOrAfterNode(node);
250         }
251     }
252     return { };
253 }
254
255 Position previousCandidate(const Position& position)
256 {
257     PositionIterator previousPosition = position;
258     while (!previousPosition.atStart()) {
259         previousPosition.decrement();
260         if (previousPosition.isCandidate())
261             return previousPosition;
262     }
263     return { };
264 }
265
266 Position previousVisuallyDistinctCandidate(const Position& position)
267 {
268     // FIXME: Use PositionIterator instead.
269     Position previousPosition = position;
270     Position downstreamStart = previousPosition.downstream();
271     while (!previousPosition.atStartOfTree()) {
272         previousPosition = previousPosition.previous(Character);
273         if (previousPosition.isCandidate() && previousPosition.downstream() != downstreamStart)
274             return previousPosition;
275         if (auto* node = previousPosition.containerNode()) {
276             if (!node->renderer())
277                 previousPosition = firstPositionInOrBeforeNode(node);
278         }
279     }
280     return { };
281 }
282
283 Position firstEditablePositionAfterPositionInRoot(const Position& position, ContainerNode* highestRoot)
284 {
285     if (!highestRoot)
286         return { };
287
288     // position falls before highestRoot.
289     if (comparePositions(position, firstPositionInNode(highestRoot)) == -1 && highestRoot->hasEditableStyle())
290         return firstPositionInNode(highestRoot);
291
292     Position candidate = position;
293
294     if (&position.deprecatedNode()->treeScope() != &highestRoot->treeScope()) {
295         auto* shadowAncestor = highestRoot->treeScope().ancestorNodeInThisScope(position.deprecatedNode());
296         if (!shadowAncestor)
297             return { };
298
299         candidate = positionAfterNode(shadowAncestor);
300     }
301
302     while (candidate.deprecatedNode() && !isEditablePosition(candidate) && candidate.deprecatedNode()->isDescendantOf(*highestRoot))
303         candidate = isAtomicNode(candidate.deprecatedNode()) ? positionInParentAfterNode(candidate.deprecatedNode()) : nextVisuallyDistinctCandidate(candidate);
304
305     if (candidate.deprecatedNode() && candidate.deprecatedNode() != highestRoot && !candidate.deprecatedNode()->isDescendantOf(*highestRoot))
306         return { };
307
308     return candidate;
309 }
310
311 Position lastEditablePositionBeforePositionInRoot(const Position& position, ContainerNode* highestRoot)
312 {
313     if (!highestRoot)
314         return { };
315
316     // When position falls after highestRoot, the result is easy to compute.
317     if (comparePositions(position, lastPositionInNode(highestRoot)) == 1)
318         return lastPositionInNode(highestRoot);
319
320     Position candidate = position;
321
322     if (&position.deprecatedNode()->treeScope() != &highestRoot->treeScope()) {
323         auto* shadowAncestor = highestRoot->treeScope().ancestorNodeInThisScope(position.deprecatedNode());
324         if (!shadowAncestor)
325             return { };
326
327         candidate = firstPositionInOrBeforeNode(shadowAncestor);
328     }
329
330     while (candidate.deprecatedNode() && !isEditablePosition(candidate) && candidate.deprecatedNode()->isDescendantOf(*highestRoot))
331         candidate = isAtomicNode(candidate.deprecatedNode()) ? positionInParentBeforeNode(candidate.deprecatedNode()) : previousVisuallyDistinctCandidate(candidate);
332     
333     if (candidate.deprecatedNode() && candidate.deprecatedNode() != highestRoot && !candidate.deprecatedNode()->isDescendantOf(*highestRoot))
334         return { };
335     
336     return candidate;
337 }
338
339 // FIXME: The function name, comment, and code say three different things here!
340 // Whether or not content before and after this node will collapse onto the same line as it.
341 bool isBlock(const Node* node)
342 {
343     return node && node->renderer() && !node->renderer()->isInline() && !node->renderer()->isRubyText();
344 }
345
346 bool isInline(const Node* node)
347 {
348     return node && node->renderer() && node->renderer()->isInline();
349 }
350
351 // FIXME: Deploy this in all of the places where enclosingBlockFlow/enclosingBlockFlowOrTableElement are used.
352 // FIXME: Pass a position to this function. The enclosing block of [table, x] for example, should be the 
353 // block that contains the table and not the table, and this function should be the only one responsible for 
354 // knowing about these kinds of special cases.
355 Element* enclosingBlock(Node* node, EditingBoundaryCrossingRule rule)
356 {
357     Node* enclosingNode = enclosingNodeOfType(firstPositionInOrBeforeNode(node), isBlock, rule);
358     return is<Element>(enclosingNode) ? downcast<Element>(enclosingNode) : nullptr;
359 }
360
361 TextDirection directionOfEnclosingBlock(const Position& position)
362 {
363     auto block = enclosingBlock(position.containerNode());
364     if (!block)
365         return TextDirection::LTR;
366     auto renderer = block->renderer();
367     if (!renderer)
368         return TextDirection::LTR;
369     return renderer->style().direction();
370 }
371
372 // This method is used to create positions in the DOM. It returns the maximum valid offset
373 // in a node. It returns 1 for some elements even though they do not have children, which
374 // creates technically invalid DOM Positions. Be sure to call parentAnchoredEquivalent
375 // on a Position before using it to create a DOM Range, or an exception will be thrown.
376 int lastOffsetForEditing(const Node& node)
377 {
378     if (node.offsetInCharacters())
379         return node.maxCharacterOffset();
380
381     if (node.hasChildNodes())
382         return node.countChildNodes();
383
384     // NOTE: This should preempt the countChildNodes() for, e.g., select nodes.
385     // FIXME: What does the comment above mean?
386     if (editingIgnoresContent(node))
387         return 1;
388
389     return 0;
390 }
391
392 bool isAmbiguousBoundaryCharacter(UChar character)
393 {
394     // These are characters that can behave as word boundaries, but can appear within words.
395     // If they are just typed, i.e. if they are immediately followed by a caret, we want to delay text checking until the next character has been typed.
396     // FIXME: this is required until <rdar://problem/6853027> is fixed and text checking can do this for us.
397     return character == '\'' || character == '@' || character == rightSingleQuotationMark || character == hebrewPunctuationGershayim;
398 }
399
400 String stringWithRebalancedWhitespace(const String& string, bool startIsStartOfParagraph, bool endIsEndOfParagraph)
401 {
402     StringBuilder rebalancedString;
403
404     bool previousCharacterWasSpace = false;
405     unsigned length = string.length();
406     for (unsigned i = 0; i < length; ++i) {
407         auto character = string[i];
408         if (!deprecatedIsEditingWhitespace(character)) {
409             previousCharacterWasSpace = false;
410             continue;
411         }
412         LChar selectedWhitespaceCharacter;
413         if (previousCharacterWasSpace || (!i && startIsStartOfParagraph) || (i == length - 1 && endIsEndOfParagraph)) {
414             selectedWhitespaceCharacter = noBreakSpace;
415             previousCharacterWasSpace = false;
416         } else {
417             selectedWhitespaceCharacter = ' ';
418             previousCharacterWasSpace = true;
419         }
420         if (character == selectedWhitespaceCharacter)
421             continue;
422         rebalancedString.reserveCapacity(length);
423         rebalancedString.append(string, rebalancedString.length(), i - rebalancedString.length());
424         rebalancedString.append(selectedWhitespaceCharacter);
425     }
426
427     if (rebalancedString.isEmpty())
428         return string;
429
430     rebalancedString.reserveCapacity(length);
431     rebalancedString.append(string, rebalancedString.length(), length - rebalancedString.length());
432     return rebalancedString.toString();
433 }
434
435 bool isTableStructureNode(const Node* node)
436 {
437     auto* renderer = node->renderer();
438     return renderer && (renderer->isTableCell() || renderer->isTableRow() || renderer->isTableSection() || renderer->isRenderTableCol());
439 }
440
441 const String& nonBreakingSpaceString()
442 {
443     static NeverDestroyed<String> nonBreakingSpaceString(&noBreakSpace, 1);
444     return nonBreakingSpaceString;
445 }
446
447 static bool isSpecialHTMLElement(const Node* node)
448 {
449     if (!is<HTMLElement>(node))
450         return false;
451
452     if (downcast<HTMLElement>(*node).isLink())
453         return true;
454
455     auto* renderer = downcast<HTMLElement>(*node).renderer();
456     if (!renderer)
457         return false;
458
459     if (renderer->style().display() == DisplayType::Table || renderer->style().display() == DisplayType::InlineTable)
460         return true;
461
462     if (renderer->style().isFloating())
463         return true;
464
465     if (renderer->style().position() != PositionType::Static)
466         return true;
467
468     return false;
469 }
470
471 static HTMLElement* firstInSpecialElement(const Position& position)
472 {
473     auto* rootEditableElement = position.containerNode()->rootEditableElement();
474     for (Node* node = position.deprecatedNode(); node && node->rootEditableElement() == rootEditableElement; node = node->parentNode()) {
475         if (!isSpecialHTMLElement(node))
476             continue;
477         VisiblePosition vPos(position, DOWNSTREAM);
478         VisiblePosition firstInElement(firstPositionInOrBeforeNode(node), DOWNSTREAM);
479         if ((isRenderedTable(node) && vPos == firstInElement.next()) || vPos == firstInElement)
480             return &downcast<HTMLElement>(*node);
481     }
482     return nullptr;
483 }
484
485 static HTMLElement* lastInSpecialElement(const Position& position)
486 {
487     auto* rootEditableElement = position.containerNode()->rootEditableElement();
488     for (Node* node = position.deprecatedNode(); node && node->rootEditableElement() == rootEditableElement; node = node->parentNode()) {
489         if (!isSpecialHTMLElement(node))
490             continue;
491         VisiblePosition vPos(position, DOWNSTREAM);
492         VisiblePosition lastInElement(lastPositionInOrAfterNode(node), DOWNSTREAM);
493         if ((isRenderedTable(node) && vPos == lastInElement.previous()) || vPos == lastInElement)
494             return &downcast<HTMLElement>(*node);
495     }
496     return nullptr;
497 }
498
499 Position positionBeforeContainingSpecialElement(const Position& position, HTMLElement** containingSpecialElement)
500 {
501     auto* element = firstInSpecialElement(position);
502     if (!element)
503         return position;
504     Position result = positionInParentBeforeNode(element);
505     if (result.isNull() || result.deprecatedNode()->rootEditableElement() != position.deprecatedNode()->rootEditableElement())
506         return position;
507     if (containingSpecialElement)
508         *containingSpecialElement = element;
509     return result;
510 }
511
512 Position positionAfterContainingSpecialElement(const Position& position, HTMLElement** containingSpecialElement)
513 {
514     auto* element = lastInSpecialElement(position);
515     if (!element)
516         return position;
517     Position result = positionInParentAfterNode(element);
518     if (result.isNull() || result.deprecatedNode()->rootEditableElement() != position.deprecatedNode()->rootEditableElement())
519         return position;
520     if (containingSpecialElement)
521         *containingSpecialElement = element;
522     return result;
523 }
524
525 Element* isFirstPositionAfterTable(const VisiblePosition& position)
526 {
527     Position upstream(position.deepEquivalent().upstream());
528     auto* node = upstream.deprecatedNode();
529     if (!node)
530         return nullptr;
531     auto* renderer = node->renderer();
532     if (!renderer || !renderer->isTable() || !upstream.atLastEditingPositionForNode())
533         return nullptr;
534     return &downcast<Element>(*node);
535 }
536
537 Element* isLastPositionBeforeTable(const VisiblePosition& position)
538 {
539     Position downstream(position.deepEquivalent().downstream());
540     auto* node = downstream.deprecatedNode();
541     if (!node)
542         return nullptr;
543     auto* renderer = node->renderer();
544     if (!renderer || !renderer->isTable() || !downstream.atFirstEditingPositionForNode())
545         return nullptr;
546     return &downcast<Element>(*node);
547 }
548
549 // Returns the visible position at the beginning of a node
550 VisiblePosition visiblePositionBeforeNode(Node& node)
551 {
552     if (node.hasChildNodes())
553         return VisiblePosition(firstPositionInOrBeforeNode(&node), DOWNSTREAM);
554     ASSERT(node.parentNode());
555     ASSERT(!node.parentNode()->isShadowRoot());
556     return positionInParentBeforeNode(&node);
557 }
558
559 // Returns the visible position at the ending of a node
560 VisiblePosition visiblePositionAfterNode(Node& node)
561 {
562     if (node.hasChildNodes())
563         return VisiblePosition(lastPositionInOrAfterNode(&node), DOWNSTREAM);
564     ASSERT(node.parentNode());
565     ASSERT(!node.parentNode()->isShadowRoot());
566     return positionInParentAfterNode(&node);
567 }
568
569 bool isListHTMLElement(Node* node)
570 {
571     return node && (is<HTMLUListElement>(*node) || is<HTMLOListElement>(*node) || is<HTMLDListElement>(*node));
572 }
573
574 bool isListItem(const Node* node)
575 {
576     return node && (isListHTMLElement(node->parentNode()) || (node->renderer() && node->renderer()->isListItem()));
577 }
578
579 Element* enclosingElementWithTag(const Position& position, const QualifiedName& tagName)
580 {
581     auto* root = highestEditableRoot(position);
582     for (Node* node = position.deprecatedNode(); node; node = node->parentNode()) {
583         if (root && !node->hasEditableStyle())
584             continue;
585         if (!is<Element>(*node))
586             continue;
587         if (downcast<Element>(*node).hasTagName(tagName))
588             return &downcast<Element>(*node);
589         if (node == root)
590             return nullptr;
591     }
592     return nullptr;
593 }
594
595 Node* enclosingNodeOfType(const Position& position, bool (*nodeIsOfType)(const Node*), EditingBoundaryCrossingRule rule)
596 {
597     // FIXME: support CanSkipCrossEditingBoundary
598     ASSERT(rule == CanCrossEditingBoundary || rule == CannotCrossEditingBoundary);
599     auto* root = rule == CannotCrossEditingBoundary ? highestEditableRoot(position) : nullptr;
600     for (Node* n = position.deprecatedNode(); n; n = n->parentNode()) {
601         // Don't return a non-editable node if the input position was editable, since
602         // the callers from editing will no doubt want to perform editing inside the returned node.
603         if (root && !n->hasEditableStyle())
604             continue;
605         if (nodeIsOfType(n))
606             return n;
607         if (n == root)
608             return nullptr;
609     }
610     return nullptr;
611 }
612
613 Node* highestEnclosingNodeOfType(const Position& position, bool (*nodeIsOfType)(const Node*), EditingBoundaryCrossingRule rule, Node* stayWithin)
614 {
615     Node* highest = nullptr;
616     auto* root = rule == CannotCrossEditingBoundary ? highestEditableRoot(position) : nullptr;
617     for (Node* n = position.containerNode(); n && n != stayWithin; n = n->parentNode()) {
618         if (root && !n->hasEditableStyle())
619             continue;
620         if (nodeIsOfType(n))
621             highest = n;
622         if (n == root)
623             break;
624     }
625     return highest;
626 }
627
628 static bool hasARenderedDescendant(Node* node, Node* excludedNode)
629 {
630     for (Node* n = node->firstChild(); n;) {
631         if (n == excludedNode) {
632             n = NodeTraversal::nextSkippingChildren(*n, node);
633             continue;
634         }
635         if (n->renderer())
636             return true;
637         n = NodeTraversal::next(*n, node);
638     }
639     return false;
640 }
641
642 Node* highestNodeToRemoveInPruning(Node* node)
643 {
644     Node* previousNode = nullptr;
645     auto* rootEditableElement = node ? node->rootEditableElement() : nullptr;
646     for (; node; node = node->parentNode()) {
647         if (auto* renderer = node->renderer()) {
648             if (!renderer->canHaveChildren() || hasARenderedDescendant(node, previousNode) || rootEditableElement == node)
649                 return previousNode;
650         }
651         previousNode = node;
652     }
653     return nullptr;
654 }
655
656 Element* enclosingTableCell(const Position& position)
657 {
658     return downcast<Element>(enclosingNodeOfType(position, isTableCell));
659 }
660
661 Element* enclosingAnchorElement(const Position& p)
662 {
663     for (Node* node = p.deprecatedNode(); node; node = node->parentNode()) {
664         if (is<Element>(*node) && node->isLink())
665             return downcast<Element>(node);
666     }
667     return nullptr;
668 }
669
670 HTMLElement* enclosingList(Node* node)
671 {
672     if (!node)
673         return nullptr;
674         
675     auto* root = highestEditableRoot(firstPositionInOrBeforeNode(node));
676     
677     for (ContainerNode* ancestor = node->parentNode(); ancestor; ancestor = ancestor->parentNode()) {
678         if (is<HTMLUListElement>(*ancestor) || is<HTMLOListElement>(*ancestor))
679             return downcast<HTMLElement>(ancestor);
680         if (ancestor == root)
681             return nullptr;
682     }
683     
684     return nullptr;
685 }
686
687 Node* enclosingListChild(Node *node)
688 {
689     if (!node)
690         return nullptr;
691
692     // Check for a list item element, or for a node whose parent is a list element. Such a node
693     // will appear visually as a list item (but without a list marker)
694     auto* root = highestEditableRoot(firstPositionInOrBeforeNode(node));
695     
696     // FIXME: This function is inappropriately named since it starts with node instead of node->parentNode()
697     for (Node* n = node; n && n->parentNode(); n = n->parentNode()) {
698         if (is<HTMLLIElement>(*n) || (isListHTMLElement(n->parentNode()) && n != root))
699             return n;
700         if (n == root || isTableCell(n))
701             return nullptr;
702     }
703
704     return nullptr;
705 }
706
707 static HTMLElement* embeddedSublist(Node* listItem)
708 {
709     // Check the DOM so that we'll find collapsed sublists without renderers.
710     for (Node* n = listItem->firstChild(); n; n = n->nextSibling()) {
711         if (isListHTMLElement(n))
712             return downcast<HTMLElement>(n);
713     }
714     return nullptr;
715 }
716
717 static Node* appendedSublist(Node* listItem)
718 {
719     // Check the DOM so that we'll find collapsed sublists without renderers.
720     for (Node* n = listItem->nextSibling(); n; n = n->nextSibling()) {
721         if (isListHTMLElement(n))
722             return downcast<HTMLElement>(n);
723         if (isListItem(listItem))
724             return nullptr;
725     }
726     
727     return nullptr;
728 }
729
730 // FIXME: This function should not need to call isStartOfParagraph/isEndOfParagraph.
731 Node* enclosingEmptyListItem(const VisiblePosition& position)
732 {
733     // Check that position is on a line by itself inside a list item
734     auto* listChildNode = enclosingListChild(position.deepEquivalent().deprecatedNode());
735     if (!listChildNode || !isStartOfParagraph(position) || !isEndOfParagraph(position))
736         return nullptr;
737
738     VisiblePosition firstInListChild(firstPositionInOrBeforeNode(listChildNode));
739     VisiblePosition lastInListChild(lastPositionInOrAfterNode(listChildNode));
740
741     if (firstInListChild != position || lastInListChild != position)
742         return nullptr;
743
744     if (embeddedSublist(listChildNode) || appendedSublist(listChildNode))
745         return nullptr;
746
747     return listChildNode;
748 }
749
750 HTMLElement* outermostEnclosingList(Node* node, Node* rootList)
751 {
752     auto* list = enclosingList(node);
753     if (!list)
754         return nullptr;
755
756     while (auto* nextList = enclosingList(list)) {
757         if (nextList == rootList)
758             break;
759         list = nextList;
760     }
761
762     return list;
763 }
764
765 bool canMergeLists(Element* firstList, Element* secondList)
766 {
767     if (!is<HTMLElement>(firstList) || !is<HTMLElement>(secondList))
768         return false;
769
770     auto& first = downcast<HTMLElement>(*firstList);
771     auto& second = downcast<HTMLElement>(*secondList);
772
773     return first.localName() == second.localName() // make sure the list types match (ol vs. ul)
774         && first.hasEditableStyle() && second.hasEditableStyle() // both lists are editable
775         && first.rootEditableElement() == second.rootEditableElement() // don't cross editing boundaries
776         // Make sure there is no visible content between this li and the previous list.
777         && isVisiblyAdjacent(positionInParentAfterNode(&first), positionInParentBeforeNode(&second));
778 }
779
780 static Node* previousNodeConsideringAtomicNodes(const Node* node)
781 {
782     if (node->previousSibling()) {
783         Node* n = node->previousSibling();
784         while (!isAtomicNode(n) && n->lastChild())
785             n = n->lastChild();
786         return n;
787     }
788     if (node->parentNode())
789         return node->parentNode();
790     return nullptr;
791 }
792
793 static Node* nextNodeConsideringAtomicNodes(const Node* node)
794 {
795     if (!isAtomicNode(node) && node->firstChild())
796         return node->firstChild();
797     if (node->nextSibling())
798         return node->nextSibling();
799     const Node* n = node;
800     while (n && !n->nextSibling())
801         n = n->parentNode();
802     if (n)
803         return n->nextSibling();
804     return nullptr;
805 }
806
807 Node* previousLeafNode(const Node* node)
808 {
809     while ((node = previousNodeConsideringAtomicNodes(node))) {
810         if (isAtomicNode(node))
811             return const_cast<Node*>(node);
812     }
813     return nullptr;
814 }
815
816 Node* nextLeafNode(const Node* node)
817 {
818     while ((node = nextNodeConsideringAtomicNodes(node))) {
819         if (isAtomicNode(node))
820             return const_cast<Node*>(node);
821     }
822     return nullptr;
823 }
824
825 // FIXME: Do not require renderer, so that this can be used within fragments.
826 bool isRenderedTable(const Node* node)
827 {
828     if (!is<Element>(node))
829         return false;
830     auto* renderer = downcast<Element>(*node).renderer();
831     return renderer && renderer->isTable();
832 }
833
834 bool isTableCell(const Node* node)
835 {
836     auto* renderer = node->renderer();
837     if (!renderer)
838         return node->hasTagName(tdTag) || node->hasTagName(thTag);
839     return renderer->isTableCell();
840 }
841
842 bool isEmptyTableCell(const Node* node)
843 {
844     // Returns true IFF the passed in node is one of:
845     //   .) a table cell with no children,
846     //   .) a table cell with a single BR child, and which has no other child renderers, including :before and :after renderers
847     //   .) the BR child of such a table cell
848
849     // Find rendered node
850     while (node && !node->renderer())
851         node = node->parentNode();
852     if (!node)
853         return false;
854
855     // Make sure the rendered node is a table cell or <br>.
856     // If it's a <br>, then the parent node has to be a table cell.
857     auto* renderer = node->renderer();
858     if (renderer->isBR()) {
859         renderer = renderer->parent();
860         if (!renderer)
861             return false;
862     }
863     if (!is<RenderTableCell>(*renderer))
864         return false;
865
866     // Check that the table cell contains no child renderers except for perhaps a single <br>.
867     auto* childRenderer = downcast<RenderTableCell>(*renderer).firstChild();
868     if (!childRenderer)
869         return true;
870     if (!childRenderer->isBR())
871         return false;
872     return !childRenderer->nextSibling();
873 }
874
875 Ref<HTMLElement> createDefaultParagraphElement(Document& document)
876 {
877     switch (document.frame()->editor().defaultParagraphSeparator()) {
878     case EditorParagraphSeparatorIsDiv:
879         return HTMLDivElement::create(document);
880     case EditorParagraphSeparatorIsP:
881         break;
882     }
883     return HTMLParagraphElement::create(document);
884 }
885
886 Ref<HTMLElement> createHTMLElement(Document& document, const QualifiedName& name)
887 {
888     return HTMLElementFactory::createElement(name, document);
889 }
890
891 Ref<HTMLElement> createHTMLElement(Document& document, const AtomicString& tagName)
892 {
893     return createHTMLElement(document, QualifiedName(nullAtom(), tagName, xhtmlNamespaceURI));
894 }
895
896 bool isTabSpanNode(const Node* node)
897 {
898     return is<HTMLSpanElement>(node) && downcast<HTMLSpanElement>(*node).attributeWithoutSynchronization(classAttr) == AppleTabSpanClass;
899 }
900
901 bool isTabSpanTextNode(const Node* node)
902 {
903     return is<Text>(node) && isTabSpanNode(node->parentNode());
904 }
905
906 HTMLSpanElement* tabSpanNode(const Node* node)
907 {
908     return isTabSpanTextNode(node) ? downcast<HTMLSpanElement>(node->parentNode()) : nullptr;
909 }
910
911 static Ref<Element> createTabSpanElement(Document& document, Text& tabTextNode)
912 {
913     auto spanElement = HTMLSpanElement::create(document);
914
915     spanElement->setAttributeWithoutSynchronization(classAttr, AppleTabSpanClass);
916     spanElement->setAttribute(styleAttr, "white-space:pre");
917
918     spanElement->appendChild(tabTextNode);
919
920     return WTFMove(spanElement);
921 }
922
923 Ref<Element> createTabSpanElement(Document& document, const String& tabText)
924 {
925     return createTabSpanElement(document, document.createTextNode(tabText));
926 }
927
928 Ref<Element> createTabSpanElement(Document& document)
929 {
930     return createTabSpanElement(document, document.createEditingTextNode("\t"_s));
931 }
932
933 bool isNodeRendered(const Node& node)
934 {
935     auto* renderer = node.renderer();
936     return renderer && renderer->style().visibility() == Visibility::Visible;
937 }
938
939 unsigned numEnclosingMailBlockquotes(const Position& position)
940 {
941     unsigned count = 0;
942     for (Node* node = position.deprecatedNode(); node; node = node->parentNode()) {
943         if (isMailBlockquote(node))
944             ++count;
945     }
946     return count;
947 }
948
949 void updatePositionForNodeRemoval(Position& position, Node& node)
950 {
951     if (position.isNull())
952         return;
953     switch (position.anchorType()) {
954     case Position::PositionIsBeforeChildren:
955         if (node.containsIncludingShadowDOM(position.containerNode()))
956             position = positionInParentBeforeNode(&node);
957         break;
958     case Position::PositionIsAfterChildren:
959         if (node.containsIncludingShadowDOM(position.containerNode()))
960             position = positionInParentBeforeNode(&node);
961         break;
962     case Position::PositionIsOffsetInAnchor:
963         if (position.containerNode() == node.parentNode() && static_cast<unsigned>(position.offsetInContainerNode()) > node.computeNodeIndex())
964             position.moveToOffset(position.offsetInContainerNode() - 1);
965         else if (node.containsIncludingShadowDOM(position.containerNode()))
966             position = positionInParentBeforeNode(&node);
967         break;
968     case Position::PositionIsAfterAnchor:
969         if (node.containsIncludingShadowDOM(position.anchorNode()))
970             position = positionInParentAfterNode(&node);
971         break;
972     case Position::PositionIsBeforeAnchor:
973         if (node.containsIncludingShadowDOM(position.anchorNode()))
974             position = positionInParentBeforeNode(&node);
975         break;
976     }
977 }
978
979 bool isMailBlockquote(const Node* node)
980 {
981     ASSERT(node);
982     if (!node->hasTagName(blockquoteTag))
983         return false;
984     return downcast<HTMLElement>(*node).attributeWithoutSynchronization(typeAttr) == "cite";
985 }
986
987 int caretMinOffset(const Node& node)
988 {
989     auto* renderer = node.renderer();
990     ASSERT(!node.isCharacterDataNode() || !renderer || renderer->isText());
991     return renderer ? renderer->caretMinOffset() : 0;
992 }
993
994 // If a node can contain candidates for VisiblePositions, return the offset of the last candidate, otherwise 
995 // return the number of children for container nodes and the length for unrendered text nodes.
996 int caretMaxOffset(const Node& node)
997 {
998     // For rendered text nodes, return the last position that a caret could occupy.
999     if (is<Text>(node)) {
1000         if (auto* renderer = downcast<Text>(node).renderer())
1001             return renderer->caretMaxOffset();
1002     }
1003     return lastOffsetForEditing(node);
1004 }
1005
1006 bool lineBreakExistsAtVisiblePosition(const VisiblePosition& position)
1007 {
1008     return lineBreakExistsAtPosition(position.deepEquivalent().downstream());
1009 }
1010
1011 bool lineBreakExistsAtPosition(const Position& position)
1012 {
1013     if (position.isNull())
1014         return false;
1015
1016     if (position.anchorNode()->hasTagName(brTag) && position.atFirstEditingPositionForNode())
1017         return true;
1018
1019     if (!position.anchorNode()->renderer())
1020         return false;
1021
1022     if (!is<Text>(*position.anchorNode()) || !position.anchorNode()->renderer()->style().preserveNewline())
1023         return false;
1024     
1025     Text& textNode = downcast<Text>(*position.anchorNode());
1026     unsigned offset = position.offsetInContainerNode();
1027     return offset < textNode.length() && textNode.data()[offset] == '\n';
1028 }
1029
1030 // Modifies selections that have an end point at the edge of a table
1031 // that contains the other endpoint so that they don't confuse
1032 // code that iterates over selected paragraphs.
1033 VisibleSelection selectionForParagraphIteration(const VisibleSelection& original)
1034 {
1035     VisibleSelection newSelection(original);
1036     VisiblePosition startOfSelection(newSelection.visibleStart());
1037     VisiblePosition endOfSelection(newSelection.visibleEnd());
1038     
1039     // If the end of the selection to modify is just after a table, and
1040     // if the start of the selection is inside that table, then the last paragraph
1041     // that we'll want modify is the last one inside the table, not the table itself
1042     // (a table is itself a paragraph).
1043     if (auto* table = isFirstPositionAfterTable(endOfSelection)) {
1044         if (startOfSelection.deepEquivalent().deprecatedNode()->isDescendantOf(*table))
1045             newSelection = VisibleSelection(startOfSelection, endOfSelection.previous(CannotCrossEditingBoundary));
1046     }
1047     
1048     // If the start of the selection to modify is just before a table,
1049     // and if the end of the selection is inside that table, then the first paragraph
1050     // we'll want to modify is the first one inside the table, not the paragraph
1051     // containing the table itself.
1052     if (auto* table = isLastPositionBeforeTable(startOfSelection)) {
1053         if (endOfSelection.deepEquivalent().deprecatedNode()->isDescendantOf(*table))
1054             newSelection = VisibleSelection(startOfSelection.next(CannotCrossEditingBoundary), endOfSelection);
1055     }
1056     
1057     return newSelection;
1058 }
1059
1060 // FIXME: indexForVisiblePosition and visiblePositionForIndex use TextIterators to convert between 
1061 // VisiblePositions and indices. But TextIterator iteration using TextIteratorEmitsCharactersBetweenAllVisiblePositions 
1062 // does not exactly match VisiblePosition iteration, so using them to preserve a selection during an editing 
1063 // opertion is unreliable. TextIterator's TextIteratorEmitsCharactersBetweenAllVisiblePositions mode needs to be fixed, 
1064 // or these functions need to be changed to iterate using actual VisiblePositions.
1065 // FIXME: Deploy these functions everywhere that TextIterators are used to convert between VisiblePositions and indices.
1066 int indexForVisiblePosition(const VisiblePosition& visiblePosition, RefPtr<ContainerNode>& scope)
1067 {
1068     if (visiblePosition.isNull())
1069         return 0;
1070
1071     auto position = visiblePosition.deepEquivalent();
1072     auto& document = *position.document();
1073
1074     auto* editableRoot = highestEditableRoot(position, AXObjectCache::accessibilityEnabled() ? HasEditableAXRole : ContentIsEditable);
1075     if (editableRoot && !document.inDesignMode())
1076         scope = editableRoot;
1077     else {
1078         if (position.containerNode()->isInShadowTree())
1079             scope = position.containerNode()->containingShadowRoot();
1080         else
1081             scope = &document;
1082     }
1083
1084     auto range = Range::create(document, firstPositionInNode(scope.get()), position.parentAnchoredEquivalent());
1085     return TextIterator::rangeLength(range.ptr(), true);
1086 }
1087
1088 // FIXME: Merge this function with the one above.
1089 int indexForVisiblePosition(Node& node, const VisiblePosition& visiblePosition, bool forSelectionPreservation)
1090 {
1091     auto range = Range::create(node.document(), firstPositionInNode(&node), visiblePosition.deepEquivalent().parentAnchoredEquivalent());
1092     return TextIterator::rangeLength(range.ptr(), forSelectionPreservation);
1093 }
1094
1095 VisiblePosition visiblePositionForPositionWithOffset(const VisiblePosition& position, int offset)
1096 {
1097     RefPtr<ContainerNode> root;
1098     unsigned startIndex = indexForVisiblePosition(position, root);
1099     if (!root)
1100         return { };
1101
1102     return visiblePositionForIndex(startIndex + offset, root.get());
1103 }
1104
1105 VisiblePosition visiblePositionForIndex(int index, ContainerNode* scope)
1106 {
1107     auto range = TextIterator::rangeFromLocationAndLength(scope, index, 0, true);
1108     // Check for an invalid index. Certain editing operations invalidate indices because 
1109     // of problems with TextIteratorEmitsCharactersBetweenAllVisiblePositions.
1110     if (!range)
1111         return { };
1112     return { range->startPosition() };
1113 }
1114
1115 VisiblePosition visiblePositionForIndexUsingCharacterIterator(Node& node, int index)
1116 {
1117     if (index <= 0)
1118         return { firstPositionInOrBeforeNode(&node), DOWNSTREAM };
1119
1120     RefPtr<Range> range = Range::create(node.document());
1121     range->selectNodeContents(node);
1122     CharacterIterator it(*range);
1123     it.advance(index - 1);
1124     return { it.atEnd() ? range->endPosition() : it.range()->endPosition(), UPSTREAM };
1125 }
1126
1127 // Determines whether two positions are visibly next to each other (first then second)
1128 // while ignoring whitespaces and unrendered nodes
1129 static bool isVisiblyAdjacent(const Position& first, const Position& second)
1130 {
1131     return VisiblePosition(first) == VisiblePosition(second.upstream());
1132 }
1133
1134 // Determines whether a node is inside a range or visibly starts and ends at the boundaries of the range.
1135 // Call this function to determine whether a node is visibly fit inside selectedRange
1136 bool isNodeVisiblyContainedWithin(Node& node, const Range& range)
1137 {
1138     // If the node is inside the range, then it surely is contained within.
1139     auto comparisonResult = range.compareNode(node);
1140     if (!comparisonResult.hasException() && comparisonResult.releaseReturnValue() == Range::NODE_INSIDE)
1141         return true;
1142
1143     bool startIsVisuallySame = visiblePositionBeforeNode(node) == range.startPosition();
1144     if (startIsVisuallySame && comparePositions(positionInParentAfterNode(&node), range.endPosition()) < 0)
1145         return true;
1146
1147     bool endIsVisuallySame = visiblePositionAfterNode(node) == range.endPosition();
1148     if (endIsVisuallySame && comparePositions(range.startPosition(), positionInParentBeforeNode(&node)) < 0)
1149         return true;
1150
1151     return startIsVisuallySame && endIsVisuallySame;
1152 }
1153
1154 bool isRenderedAsNonInlineTableImageOrHR(const Node* node)
1155 {
1156     if (!node)
1157         return false;
1158     RenderObject* renderer = node->renderer();
1159     return renderer && ((renderer->isTable() && !renderer->isInline()) || (renderer->isImage() && !renderer->isInline()) || renderer->isHR());
1160 }
1161
1162 bool areIdenticalElements(const Node& first, const Node& second)
1163 {
1164     if (!is<Element>(first) || !is<Element>(second))
1165         return false;
1166     auto& firstElement = downcast<Element>(first);
1167     auto& secondElement = downcast<Element>(second);
1168     return firstElement.hasTagName(secondElement.tagQName()) && firstElement.hasEquivalentAttributes(&secondElement);
1169 }
1170
1171 bool isNonTableCellHTMLBlockElement(const Node* node)
1172 {
1173     return node->hasTagName(listingTag)
1174         || node->hasTagName(olTag)
1175         || node->hasTagName(preTag)
1176         || is<HTMLTableElement>(*node)
1177         || node->hasTagName(ulTag)
1178         || node->hasTagName(xmpTag)
1179         || node->hasTagName(h1Tag)
1180         || node->hasTagName(h2Tag)
1181         || node->hasTagName(h3Tag)
1182         || node->hasTagName(h4Tag)
1183         || node->hasTagName(h5Tag);
1184 }
1185
1186 Position adjustedSelectionStartForStyleComputation(const VisibleSelection& selection)
1187 {
1188     // This function is used by range style computations to avoid bugs like:
1189     // <rdar://problem/4017641> REGRESSION (Mail): you can only bold/unbold a selection starting from end of line once
1190     // It is important to skip certain irrelevant content at the start of the selection, so we do not wind up 
1191     // with a spurious "mixed" style.
1192
1193     auto visiblePosition = selection.visibleStart();
1194     if (visiblePosition.isNull())
1195         return { };
1196
1197     // if the selection is a caret, just return the position, since the style
1198     // behind us is relevant
1199     if (selection.isCaret())
1200         return visiblePosition.deepEquivalent();
1201
1202     // if the selection starts just before a paragraph break, skip over it
1203     if (isEndOfParagraph(visiblePosition))
1204         return visiblePosition.next().deepEquivalent().downstream();
1205
1206     // otherwise, make sure to be at the start of the first selected node,
1207     // instead of possibly at the end of the last node before the selection
1208     return visiblePosition.deepEquivalent().downstream();
1209 }
1210
1211 // FIXME: Should this be deprecated like deprecatedEnclosingBlockFlowElement is?
1212 bool isBlockFlowElement(const Node& node)
1213 {
1214     if (!node.isElementNode())
1215         return false;
1216     auto* renderer = downcast<Element>(node).renderer();
1217     return renderer && renderer->isRenderBlockFlow();
1218 }
1219
1220 Element* deprecatedEnclosingBlockFlowElement(Node* node)
1221 {
1222     if (!node)
1223         return nullptr;
1224     if (isBlockFlowElement(*node))
1225         return downcast<Element>(node);
1226     while ((node = node->parentNode())) {
1227         if (isBlockFlowElement(*node) || is<HTMLBodyElement>(*node))
1228             return downcast<Element>(node);
1229     }
1230     return nullptr;
1231 }
1232
1233 static inline bool caretRendersInsideNode(Node& node)
1234 {
1235     return !isRenderedTable(&node) && !editingIgnoresContent(node);
1236 }
1237
1238 RenderBlock* rendererForCaretPainting(Node* node)
1239 {
1240     if (!node)
1241         return nullptr;
1242
1243     auto* renderer = node->renderer();
1244     if (!renderer)
1245         return nullptr;
1246
1247     // If caretNode is a block and caret is inside it, then caret should be painted by that block.
1248     bool paintedByBlock = is<RenderBlockFlow>(*renderer) && caretRendersInsideNode(*node);
1249     return paintedByBlock ? downcast<RenderBlock>(renderer) : renderer->containingBlock();
1250 }
1251
1252 LayoutRect localCaretRectInRendererForCaretPainting(const VisiblePosition& caretPosition, RenderBlock*& caretPainter)
1253 {
1254     if (caretPosition.isNull())
1255         return LayoutRect();
1256
1257     ASSERT(caretPosition.deepEquivalent().deprecatedNode()->renderer());
1258
1259     // First compute a rect local to the renderer at the selection start.
1260     RenderObject* renderer;
1261     LayoutRect localRect = caretPosition.localCaretRect(renderer);
1262
1263     return localCaretRectInRendererForRect(localRect, caretPosition.deepEquivalent().deprecatedNode(), renderer, caretPainter);
1264 }
1265
1266 LayoutRect localCaretRectInRendererForRect(LayoutRect& localRect, Node* node, RenderObject* renderer, RenderBlock*& caretPainter)
1267 {
1268     // Get the renderer that will be responsible for painting the caret
1269     // (which is either the renderer we just found, or one of its containers).
1270     caretPainter = rendererForCaretPainting(node);
1271
1272     // Compute an offset between the renderer and the caretPainter.
1273     while (renderer != caretPainter) {
1274         RenderElement* containerObject = renderer->container();
1275         if (!containerObject)
1276             return LayoutRect();
1277         localRect.move(renderer->offsetFromContainer(*containerObject, localRect.location()));
1278         renderer = containerObject;
1279     }
1280
1281     return localRect;
1282 }
1283
1284 IntRect absoluteBoundsForLocalCaretRect(RenderBlock* rendererForCaretPainting, const LayoutRect& rect, bool* insideFixed)
1285 {
1286     if (insideFixed)
1287         *insideFixed = false;
1288
1289     if (!rendererForCaretPainting || rect.isEmpty())
1290         return IntRect();
1291
1292     LayoutRect localRect(rect);
1293     rendererForCaretPainting->flipForWritingMode(localRect);
1294     return rendererForCaretPainting->localToAbsoluteQuad(FloatRect(localRect), UseTransforms, insideFixed).enclosingBoundingBox();
1295 }
1296
1297 } // namespace WebCore