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