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