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/v8/ExceptionState.h"
30#include "bindings/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/HTMLTableCellElement.h"
54#include "core/html/HTMLUListElement.h"
55#include "core/rendering/RenderObject.h"
56#include "core/rendering/RenderTableCell.h"
57#include "wtf/Assertions.h"
58#include "wtf/StdLibExtras.h"
59#include "wtf/text/StringBuilder.h"
60
61namespace WebCore {
62
63using namespace HTMLNames;
64
65// Atomic means that the node has no children, or has children which are ignored for the
66// purposes of editing.
67bool isAtomicNode(const Node *node)
68{
69    return node && (!node->hasChildren() || editingIgnoresContent(node));
70}
71
72// Compare two positions, taking into account the possibility that one or both
73// could be inside a shadow tree. Only works for non-null values.
74int comparePositions(const Position& a, const Position& b)
75{
76    ASSERT(a.isNotNull());
77    ASSERT(b.isNotNull());
78    TreeScope* commonScope = commonTreeScope(a.containerNode(), b.containerNode());
79
80    ASSERT(commonScope);
81    if (!commonScope)
82        return 0;
83
84    Node* nodeA = commonScope->ancestorInThisScope(a.containerNode());
85    ASSERT(nodeA);
86    bool hasDescendentA = nodeA != a.containerNode();
87    int offsetA = hasDescendentA ? 0 : a.computeOffsetInContainerNode();
88
89    Node* nodeB = commonScope->ancestorInThisScope(b.containerNode());
90    ASSERT(nodeB);
91    bool hasDescendentB = nodeB != b.containerNode();
92    int offsetB = hasDescendentB ? 0 : b.computeOffsetInContainerNode();
93
94    int bias = 0;
95    if (nodeA == nodeB) {
96        if (hasDescendentA)
97            bias = -1;
98        else if (hasDescendentB)
99            bias = 1;
100    }
101
102    int result = Range::compareBoundaryPoints(nodeA, offsetA, nodeB, offsetB, IGNORE_EXCEPTION);
103    return result ? result : bias;
104}
105
106int comparePositions(const PositionWithAffinity& a, const PositionWithAffinity& b)
107{
108    return comparePositions(a.position(), b.position());
109}
110
111int comparePositions(const VisiblePosition& a, const VisiblePosition& b)
112{
113    return comparePositions(a.deepEquivalent(), b.deepEquivalent());
114}
115
116Node* highestEditableRoot(const Position& position, EditableType editableType)
117{
118    Node* node = position.deprecatedNode();
119    if (!node)
120        return 0;
121
122    Node* highestRoot = editableRootForPosition(position, editableType);
123    if (!highestRoot)
124        return 0;
125
126    if (isHTMLBodyElement(*highestRoot))
127        return highestRoot;
128
129    node = highestRoot->parentNode();
130    while (node) {
131        if (node->rendererIsEditable(editableType))
132            highestRoot = node;
133        if (isHTMLBodyElement(*node))
134            break;
135        node = node->parentNode();
136    }
137
138    return highestRoot;
139}
140
141Node* lowestEditableAncestor(Node* node)
142{
143    while (node) {
144        if (node->rendererIsEditable())
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 (isRenderedTableElement(node))
165        node = node->parentNode();
166
167    return node->rendererIsEditable(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 (isRenderedTableElement(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 (isRenderedTableElement(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, Node* highestRoot)
262{
263    // position falls before highestRoot.
264    if (comparePositions(position, firstPositionInNode(highestRoot)) == -1 && highestRoot->rendererIsEditable())
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, Node* 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
337TextDirection directionOfEnclosingBlock(const Position& position)
338{
339    Node* enclosingBlockNode = enclosingBlock(position.containerNode());
340    if (!enclosingBlockNode)
341        return LTR;
342    RenderObject* renderer = enclosingBlockNode->renderer();
343    return renderer ? renderer->style()->direction() : LTR;
344}
345
346// This method is used to create positions in the DOM. It returns the maximum valid offset
347// in a node. It returns 1 for some elements even though they do not have children, which
348// creates technically invalid DOM Positions. Be sure to call parentAnchoredEquivalent
349// on a Position before using it to create a DOM Range, or an exception will be thrown.
350int lastOffsetForEditing(const Node* node)
351{
352    ASSERT(node);
353    if (!node)
354        return 0;
355    if (node->offsetInCharacters())
356        return node->maxCharacterOffset();
357
358    if (node->hasChildren())
359        return node->countChildren();
360
361    // NOTE: This should preempt the childNodeCount for, e.g., select nodes
362    if (editingIgnoresContent(node))
363        return 1;
364
365    return 0;
366}
367
368String stringWithRebalancedWhitespace(const String& string, bool startIsStartOfParagraph, bool endIsEndOfParagraph)
369{
370    unsigned length = string.length();
371
372    StringBuilder rebalancedString;
373    rebalancedString.reserveCapacity(length);
374
375    bool previousCharacterWasSpace = false;
376    for (size_t i = 0; i < length; i++) {
377        UChar c = string[i];
378        if (!isWhitespace(c)) {
379            rebalancedString.append(c);
380            previousCharacterWasSpace = false;
381            continue;
382        }
383
384        if (previousCharacterWasSpace || (!i && startIsStartOfParagraph) || (i + 1 == length && endIsEndOfParagraph)) {
385            rebalancedString.append(noBreakSpace);
386            previousCharacterWasSpace = false;
387        } else {
388            rebalancedString.append(' ');
389            previousCharacterWasSpace = true;
390        }
391    }
392
393    ASSERT(rebalancedString.length() == length);
394
395    return rebalancedString.toString();
396}
397
398bool isTableStructureNode(const Node *node)
399{
400    RenderObject* renderer = node->renderer();
401    return (renderer && (renderer->isTableCell() || renderer->isTableRow() || renderer->isTableSection() || renderer->isRenderTableCol()));
402}
403
404const String& nonBreakingSpaceString()
405{
406    DEFINE_STATIC_LOCAL(String, nonBreakingSpaceString, (&noBreakSpace, 1));
407    return nonBreakingSpaceString;
408}
409
410// FIXME: need to dump this
411bool isSpecialElement(const Node *n)
412{
413    if (!n)
414        return false;
415
416    if (!n->isHTMLElement())
417        return false;
418
419    if (n->isLink())
420        return true;
421
422    RenderObject* renderer = n->renderer();
423    if (!renderer)
424        return false;
425
426    if (renderer->style()->display() == TABLE || renderer->style()->display() == INLINE_TABLE)
427        return true;
428
429    if (renderer->style()->isFloating())
430        return true;
431
432    return false;
433}
434
435static Node* firstInSpecialElement(const Position& pos)
436{
437    Node* rootEditableElement = pos.containerNode()->rootEditableElement();
438    for (Node* n = pos.deprecatedNode(); n && n->rootEditableElement() == rootEditableElement; n = n->parentNode())
439        if (isSpecialElement(n)) {
440            VisiblePosition vPos = VisiblePosition(pos, DOWNSTREAM);
441            VisiblePosition firstInElement = VisiblePosition(firstPositionInOrBeforeNode(n), DOWNSTREAM);
442            if (isRenderedTable(n) && vPos == firstInElement.next())
443                return n;
444            if (vPos == firstInElement)
445                return n;
446        }
447    return 0;
448}
449
450static Node* lastInSpecialElement(const Position& pos)
451{
452    Node* rootEditableElement = pos.containerNode()->rootEditableElement();
453    for (Node* n = pos.deprecatedNode(); n && n->rootEditableElement() == rootEditableElement; n = n->parentNode())
454        if (isSpecialElement(n)) {
455            VisiblePosition vPos = VisiblePosition(pos, DOWNSTREAM);
456            VisiblePosition lastInElement = VisiblePosition(lastPositionInOrAfterNode(n), DOWNSTREAM);
457            if (isRenderedTable(n) && vPos == lastInElement.previous())
458                return n;
459            if (vPos == lastInElement)
460                return n;
461        }
462    return 0;
463}
464
465Position positionBeforeContainingSpecialElement(const Position& pos, Node** containingSpecialElement)
466{
467    Node* n = firstInSpecialElement(pos);
468    if (!n)
469        return pos;
470    Position result = positionInParentBeforeNode(*n);
471    if (result.isNull() || result.deprecatedNode()->rootEditableElement() != pos.deprecatedNode()->rootEditableElement())
472        return pos;
473    if (containingSpecialElement)
474        *containingSpecialElement = n;
475    return result;
476}
477
478Position positionAfterContainingSpecialElement(const Position& pos, Node **containingSpecialElement)
479{
480    Node* n = lastInSpecialElement(pos);
481    if (!n)
482        return pos;
483    Position result = positionInParentAfterNode(*n);
484    if (result.isNull() || result.deprecatedNode()->rootEditableElement() != pos.deprecatedNode()->rootEditableElement())
485        return pos;
486    if (containingSpecialElement)
487        *containingSpecialElement = n;
488    return result;
489}
490
491Node* isFirstPositionAfterTable(const VisiblePosition& visiblePosition)
492{
493    Position upstream(visiblePosition.deepEquivalent().upstream());
494    if (isRenderedTable(upstream.deprecatedNode()) && upstream.atLastEditingPositionForNode())
495        return upstream.deprecatedNode();
496
497    return 0;
498}
499
500Node* isLastPositionBeforeTable(const VisiblePosition& visiblePosition)
501{
502    Position downstream(visiblePosition.deepEquivalent().downstream());
503    if (isRenderedTable(downstream.deprecatedNode()) && downstream.atFirstEditingPositionForNode())
504        return downstream.deprecatedNode();
505
506    return 0;
507}
508
509// Returns the visible position at the beginning of a node
510VisiblePosition visiblePositionBeforeNode(Node& node)
511{
512    if (node.hasChildren())
513        return VisiblePosition(firstPositionInOrBeforeNode(&node), DOWNSTREAM);
514    ASSERT(node.parentNode());
515    ASSERT(!node.parentNode()->isShadowRoot());
516    return VisiblePosition(positionInParentBeforeNode(node));
517}
518
519// Returns the visible position at the ending of a node
520VisiblePosition visiblePositionAfterNode(Node& node)
521{
522    if (node.hasChildren())
523        return VisiblePosition(lastPositionInOrAfterNode(&node), DOWNSTREAM);
524    ASSERT(node.parentNode());
525    ASSERT(!node.parentNode()->isShadowRoot());
526    return VisiblePosition(positionInParentAfterNode(node));
527}
528
529// Create a range object with two visible positions, start and end.
530// create(Document*, const Position&, const Position&); will use deprecatedEditingOffset
531// Use this function instead of create a regular range object (avoiding editing offset).
532PassRefPtrWillBeRawPtr<Range> createRange(Document& document, const VisiblePosition& start, const VisiblePosition& end, ExceptionState& exceptionState)
533{
534    RefPtrWillBeRawPtr<Range> selectedRange = Range::create(document);
535    selectedRange->setStart(start.deepEquivalent().containerNode(), start.deepEquivalent().computeOffsetInContainerNode(), exceptionState);
536    if (!exceptionState.hadException())
537        selectedRange->setEnd(end.deepEquivalent().containerNode(), end.deepEquivalent().computeOffsetInContainerNode(), exceptionState);
538    return selectedRange.release();
539}
540
541bool isListElement(Node* n)
542{
543    return (n && (isHTMLUListElement(*n) || isHTMLOListElement(*n) || isHTMLDListElement(*n)));
544}
545
546bool isListItem(const Node* n)
547{
548    return n && n->renderer() && n->renderer()->isListItem();
549}
550
551Node* enclosingNodeWithTag(const Position& p, const QualifiedName& tagName)
552{
553    if (p.isNull())
554        return 0;
555
556    Node* root = highestEditableRoot(p);
557    for (Node* n = p.deprecatedNode(); n; n = n->parentNode()) {
558        if (root && !n->rendererIsEditable())
559            continue;
560        if (n->hasTagName(tagName))
561            return n;
562        if (n == root)
563            return 0;
564    }
565
566    return 0;
567}
568
569Node* enclosingNodeOfType(const Position& p, bool (*nodeIsOfType)(const Node*), EditingBoundaryCrossingRule rule)
570{
571    // FIXME: support CanSkipCrossEditingBoundary
572    ASSERT(rule == CanCrossEditingBoundary || rule == CannotCrossEditingBoundary);
573    if (p.isNull())
574        return 0;
575
576    Node* root = rule == CannotCrossEditingBoundary ? highestEditableRoot(p) : 0;
577    for (Node* n = p.deprecatedNode(); n; n = n->parentNode()) {
578        // Don't return a non-editable node if the input position was editable, since
579        // the callers from editing will no doubt want to perform editing inside the returned node.
580        if (root && !n->rendererIsEditable())
581            continue;
582        if (nodeIsOfType(n))
583            return n;
584        if (n == root)
585            return 0;
586    }
587
588    return 0;
589}
590
591Node* highestEnclosingNodeOfType(const Position& p, bool (*nodeIsOfType)(const Node*), EditingBoundaryCrossingRule rule, Node* stayWithin)
592{
593    Node* highest = 0;
594    Node* root = rule == CannotCrossEditingBoundary ? highestEditableRoot(p) : 0;
595    for (Node* n = p.containerNode(); n && n != stayWithin; n = n->parentNode()) {
596        if (root && !n->rendererIsEditable())
597            continue;
598        if (nodeIsOfType(n))
599            highest = n;
600        if (n == root)
601            break;
602    }
603
604    return highest;
605}
606
607static bool hasARenderedDescendant(Node* node, Node* excludedNode)
608{
609    for (Node* n = node->firstChild(); n;) {
610        if (n == excludedNode) {
611            n = NodeTraversal::nextSkippingChildren(*n, node);
612            continue;
613        }
614        if (n->renderer())
615            return true;
616        n = NodeTraversal::next(*n, node);
617    }
618    return false;
619}
620
621Node* highestNodeToRemoveInPruning(Node* node, Node* excludeNode)
622{
623    Node* previousNode = 0;
624    Node* rootEditableElement = node ? node->rootEditableElement() : 0;
625    for (; node; node = node->parentNode()) {
626        if (RenderObject* renderer = node->renderer()) {
627            if (!renderer->canHaveChildren() || hasARenderedDescendant(node, previousNode) || rootEditableElement == node || excludeNode == node)
628                return previousNode;
629        }
630        previousNode = node;
631    }
632    return 0;
633}
634
635Node* enclosingTableCell(const Position& p)
636{
637    return toElement(enclosingNodeOfType(p, isTableCell));
638}
639
640Element* enclosingAnchorElement(const Position& p)
641{
642    if (p.isNull())
643        return 0;
644
645    Node* node = p.deprecatedNode();
646    while (node && !(node->isElementNode() && node->isLink()))
647        node = node->parentNode();
648    return toElement(node);
649}
650
651HTMLElement* enclosingList(Node* node)
652{
653    if (!node)
654        return 0;
655
656    Node* root = highestEditableRoot(firstPositionInOrBeforeNode(node));
657
658    for (ContainerNode* n = node->parentNode(); n; n = n->parentNode()) {
659        if (isHTMLUListElement(*n) || isHTMLOListElement(*n))
660            return toHTMLElement(n);
661        if (n == root)
662            return 0;
663    }
664
665    return 0;
666}
667
668Node* enclosingListChild(Node *node)
669{
670    if (!node)
671        return 0;
672    // Check for a list item element, or for a node whose parent is a list element. Such a node
673    // will appear visually as a list item (but without a list marker)
674    Node* root = highestEditableRoot(firstPositionInOrBeforeNode(node));
675
676    // FIXME: This function is inappropriately named if it starts with node instead of node->parentNode()
677    for (Node* n = node; n && n->parentNode(); n = n->parentNode()) {
678        if (isHTMLLIElement(*n) || (isListElement(n->parentNode()) && n != root))
679            return n;
680        if (n == root || isTableCell(n))
681            return 0;
682    }
683
684    return 0;
685}
686
687// FIXME: This method should not need to call isStartOfParagraph/isEndOfParagraph
688Node* enclosingEmptyListItem(const VisiblePosition& visiblePos)
689{
690    // Check that position is on a line by itself inside a list item
691    Node* listChildNode = enclosingListChild(visiblePos.deepEquivalent().deprecatedNode());
692    if (!listChildNode || !isStartOfParagraph(visiblePos) || !isEndOfParagraph(visiblePos))
693        return 0;
694
695    VisiblePosition firstInListChild(firstPositionInOrBeforeNode(listChildNode));
696    VisiblePosition lastInListChild(lastPositionInOrAfterNode(listChildNode));
697
698    if (firstInListChild != visiblePos || lastInListChild != visiblePos)
699        return 0;
700
701    return listChildNode;
702}
703
704HTMLElement* outermostEnclosingList(Node* node, Node* rootList)
705{
706    HTMLElement* list = enclosingList(node);
707    if (!list)
708        return 0;
709
710    while (HTMLElement* nextList = enclosingList(list)) {
711        if (nextList == rootList)
712            break;
713        list = nextList;
714    }
715
716    return list;
717}
718
719bool canMergeLists(Element* firstList, Element* secondList)
720{
721    if (!firstList || !secondList || !firstList->isHTMLElement() || !secondList->isHTMLElement())
722        return false;
723
724    return firstList->hasTagName(secondList->tagQName()) // make sure the list types match (ol vs. ul)
725    && firstList->rendererIsEditable() && secondList->rendererIsEditable() // both lists are editable
726    && firstList->rootEditableElement() == secondList->rootEditableElement() // don't cross editing boundaries
727    && isVisiblyAdjacent(positionInParentAfterNode(*firstList), positionInParentBeforeNode(*secondList));
728    // Make sure there is no visible content between this li and the previous list
729}
730
731bool isRenderedTableElement(const Node* node)
732{
733    return isHTMLTableElement(*node) && node->renderer();
734}
735
736bool isRenderedTable(const Node* node)
737{
738    if (!node || !node->isElementNode())
739        return false;
740
741    RenderObject* renderer = node->renderer();
742    return (renderer && renderer->isTable());
743}
744
745bool isTableCell(const Node* node)
746{
747    ASSERT(node);
748    RenderObject* r = node->renderer();
749    return r ? r->isTableCell() : isHTMLTableCellElement(*node);
750}
751
752bool isEmptyTableCell(const Node* node)
753{
754    // Returns true IFF the passed in node is one of:
755    //   .) a table cell with no children,
756    //   .) a table cell with a single BR child, and which has no other child renderers, including :before and :after renderers
757    //   .) the BR child of such a table cell
758
759    // Find rendered node
760    while (node && !node->renderer())
761        node = node->parentNode();
762    if (!node)
763        return false;
764
765    // Make sure the rendered node is a table cell or <br>.
766    // If it's a <br>, then the parent node has to be a table cell.
767    RenderObject* renderer = node->renderer();
768    if (renderer->isBR()) {
769        renderer = renderer->parent();
770        if (!renderer)
771            return false;
772    }
773    if (!renderer->isTableCell())
774        return false;
775
776    // Check that the table cell contains no child renderers except for perhaps a single <br>.
777    RenderObject* childRenderer = toRenderTableCell(renderer)->firstChild();
778    if (!childRenderer)
779        return true;
780    if (!childRenderer->isBR())
781        return false;
782    return !childRenderer->nextSibling();
783}
784
785PassRefPtrWillBeRawPtr<HTMLElement> createDefaultParagraphElement(Document& document)
786{
787    switch (document.frame()->editor().defaultParagraphSeparator()) {
788    case EditorParagraphSeparatorIsDiv:
789        return HTMLDivElement::create(document);
790    case EditorParagraphSeparatorIsP:
791        return HTMLParagraphElement::create(document);
792    }
793
794    ASSERT_NOT_REACHED();
795    return nullptr;
796}
797
798PassRefPtrWillBeRawPtr<HTMLElement> createBreakElement(Document& document)
799{
800    return HTMLBRElement::create(document);
801}
802
803PassRefPtrWillBeRawPtr<HTMLElement> createOrderedListElement(Document& document)
804{
805    return HTMLOListElement::create(document);
806}
807
808PassRefPtrWillBeRawPtr<HTMLElement> createUnorderedListElement(Document& document)
809{
810    return HTMLUListElement::create(document);
811}
812
813PassRefPtrWillBeRawPtr<HTMLElement> createListItemElement(Document& document)
814{
815    return HTMLLIElement::create(document);
816}
817
818PassRefPtrWillBeRawPtr<HTMLElement> createHTMLElement(Document& document, const QualifiedName& name)
819{
820    return createHTMLElement(document, name.localName());
821}
822
823PassRefPtrWillBeRawPtr<HTMLElement> createHTMLElement(Document& document, const AtomicString& tagName)
824{
825    return HTMLElementFactory::createHTMLElement(tagName, document, 0, false);
826}
827
828bool isTabSpanNode(const Node* node)
829{
830    if (!isHTMLSpanElement(node) || toElement(node)->getAttribute(classAttr) != AppleTabSpanClass)
831        return false;
832    UseCounter::count(node->document(), UseCounter::EditingAppleTabSpanClass);
833    return true;
834}
835
836bool isTabSpanTextNode(const Node* node)
837{
838    return node && node->isTextNode() && node->parentNode() && isTabSpanNode(node->parentNode());
839}
840
841Node* tabSpanNode(const Node* node)
842{
843    return isTabSpanTextNode(node) ? node->parentNode() : 0;
844}
845
846PassRefPtrWillBeRawPtr<Element> createTabSpanElement(Document& document, PassRefPtrWillBeRawPtr<Node> prpTabTextNode)
847{
848    RefPtrWillBeRawPtr<Node> tabTextNode = prpTabTextNode;
849
850    // Make the span to hold the tab.
851    RefPtrWillBeRawPtr<Element> spanElement = document.createElement(spanTag, false);
852    spanElement->setAttribute(classAttr, AppleTabSpanClass);
853    spanElement->setAttribute(styleAttr, "white-space:pre");
854
855    // Add tab text to that span.
856    if (!tabTextNode)
857        tabTextNode = document.createEditingTextNode("\t");
858
859    spanElement->appendChild(tabTextNode.release());
860
861    return spanElement.release();
862}
863
864PassRefPtrWillBeRawPtr<Element> createTabSpanElement(Document& document, const String& tabText)
865{
866    return createTabSpanElement(document, document.createTextNode(tabText));
867}
868
869PassRefPtrWillBeRawPtr<Element> createTabSpanElement(Document& document)
870{
871    return createTabSpanElement(document, PassRefPtrWillBeRawPtr<Node>(nullptr));
872}
873
874bool isNodeRendered(const Node *node)
875{
876    if (!node)
877        return false;
878
879    RenderObject* renderer = node->renderer();
880    if (!renderer)
881        return false;
882
883    return renderer->style()->visibility() == VISIBLE;
884}
885
886unsigned numEnclosingMailBlockquotes(const Position& p)
887{
888    unsigned num = 0;
889    for (Node* n = p.deprecatedNode(); n; n = n->parentNode())
890        if (isMailBlockquote(n))
891            num++;
892
893    return num;
894}
895
896void updatePositionForNodeRemoval(Position& position, Node& node)
897{
898    if (position.isNull())
899        return;
900    switch (position.anchorType()) {
901    case Position::PositionIsBeforeChildren:
902        if (position.containerNode() == node)
903            position = positionInParentBeforeNode(node);
904        break;
905    case Position::PositionIsAfterChildren:
906        if (position.containerNode() == node)
907            position = positionInParentAfterNode(node);
908        break;
909    case Position::PositionIsOffsetInAnchor:
910        if (position.containerNode() == node.parentNode() && static_cast<unsigned>(position.offsetInContainerNode()) > node.nodeIndex())
911            position.moveToOffset(position.offsetInContainerNode() - 1);
912        else if (node.containsIncludingShadowDOM(position.containerNode()))
913            position = positionInParentBeforeNode(node);
914        break;
915    case Position::PositionIsAfterAnchor:
916        if (node.containsIncludingShadowDOM(position.anchorNode()))
917            position = positionInParentAfterNode(node);
918        break;
919    case Position::PositionIsBeforeAnchor:
920        if (node.containsIncludingShadowDOM(position.anchorNode()))
921            position = positionInParentBeforeNode(node);
922        break;
923    }
924}
925
926bool isMailBlockquote(const Node *node)
927{
928    if (!node || !node->hasTagName(blockquoteTag))
929        return false;
930
931    return toElement(node)->getAttribute("type") == "cite";
932}
933
934int caretMinOffset(const Node* n)
935{
936    RenderObject* r = n->renderer();
937    ASSERT(!n->isCharacterDataNode() || !r || r->isText()); // FIXME: This was a runtime check that seemingly couldn't fail; changed it to an assertion for now.
938    return r ? r->caretMinOffset() : 0;
939}
940
941// If a node can contain candidates for VisiblePositions, return the offset of the last candidate, otherwise
942// return the number of children for container nodes and the length for unrendered text nodes.
943int caretMaxOffset(const Node* n)
944{
945    // For rendered text nodes, return the last position that a caret could occupy.
946    if (n->isTextNode() && n->renderer())
947        return n->renderer()->caretMaxOffset();
948    // For containers return the number of children. For others do the same as above.
949    return lastOffsetForEditing(n);
950}
951
952bool lineBreakExistsAtVisiblePosition(const VisiblePosition& visiblePosition)
953{
954    return lineBreakExistsAtPosition(visiblePosition.deepEquivalent().downstream());
955}
956
957bool lineBreakExistsAtPosition(const Position& position)
958{
959    if (position.isNull())
960        return false;
961
962    if (isHTMLBRElement(*position.anchorNode()) && position.atFirstEditingPositionForNode())
963        return true;
964
965    if (!position.anchorNode()->renderer())
966        return false;
967
968    if (!position.anchorNode()->isTextNode() || !position.anchorNode()->renderer()->style()->preserveNewline())
969        return false;
970
971    Text* textNode = toText(position.anchorNode());
972    unsigned offset = position.offsetInContainerNode();
973    return offset < textNode->length() && textNode->data()[offset] == '\n';
974}
975
976// Modifies selections that have an end point at the edge of a table
977// that contains the other endpoint so that they don't confuse
978// code that iterates over selected paragraphs.
979VisibleSelection selectionForParagraphIteration(const VisibleSelection& original)
980{
981    VisibleSelection newSelection(original);
982    VisiblePosition startOfSelection(newSelection.visibleStart());
983    VisiblePosition endOfSelection(newSelection.visibleEnd());
984
985    // If the end of the selection to modify is just after a table, and
986    // if the start of the selection is inside that table, then the last paragraph
987    // that we'll want modify is the last one inside the table, not the table itself
988    // (a table is itself a paragraph).
989    if (Node* table = isFirstPositionAfterTable(endOfSelection))
990        if (startOfSelection.deepEquivalent().deprecatedNode()->isDescendantOf(table))
991            newSelection = VisibleSelection(startOfSelection, endOfSelection.previous(CannotCrossEditingBoundary));
992
993    // If the start of the selection to modify is just before a table,
994    // and if the end of the selection is inside that table, then the first paragraph
995    // we'll want to modify is the first one inside the table, not the paragraph
996    // containing the table itself.
997    if (Node* table = isLastPositionBeforeTable(startOfSelection))
998        if (endOfSelection.deepEquivalent().deprecatedNode()->isDescendantOf(table))
999            newSelection = VisibleSelection(startOfSelection.next(CannotCrossEditingBoundary), endOfSelection);
1000
1001    return newSelection;
1002}
1003
1004// FIXME: indexForVisiblePosition and visiblePositionForIndex use TextIterators to convert between
1005// VisiblePositions and indices. But TextIterator iteration using TextIteratorEmitsCharactersBetweenAllVisiblePositions
1006// does not exactly match VisiblePosition iteration, so using them to preserve a selection during an editing
1007// opertion is unreliable. TextIterator's TextIteratorEmitsCharactersBetweenAllVisiblePositions mode needs to be fixed,
1008// or these functions need to be changed to iterate using actual VisiblePositions.
1009// FIXME: Deploy these functions everywhere that TextIterators are used to convert between VisiblePositions and indices.
1010int indexForVisiblePosition(const VisiblePosition& visiblePosition, RefPtrWillBeRawPtr<ContainerNode>& scope)
1011{
1012    if (visiblePosition.isNull())
1013        return 0;
1014
1015    Position p(visiblePosition.deepEquivalent());
1016    Document& document = *p.document();
1017    ShadowRoot* shadowRoot = p.anchorNode()->containingShadowRoot();
1018
1019    if (shadowRoot)
1020        scope = shadowRoot;
1021    else
1022        scope = document.documentElement();
1023
1024    RefPtrWillBeRawPtr<Range> range = Range::create(document, firstPositionInNode(scope.get()), p.parentAnchoredEquivalent());
1025
1026    return TextIterator::rangeLength(range.get(), true);
1027}
1028
1029VisiblePosition visiblePositionForIndex(int index, ContainerNode* scope)
1030{
1031    if (!scope)
1032        return VisiblePosition();
1033    RefPtrWillBeRawPtr<Range> range = PlainTextRange(index).createRangeForSelection(*scope);
1034    // Check for an invalid index. Certain editing operations invalidate indices because
1035    // of problems with TextIteratorEmitsCharactersBetweenAllVisiblePositions.
1036    if (!range)
1037        return VisiblePosition();
1038    return VisiblePosition(range->startPosition());
1039}
1040
1041// Determines whether two positions are visibly next to each other (first then second)
1042// while ignoring whitespaces and unrendered nodes
1043bool isVisiblyAdjacent(const Position& first, const Position& second)
1044{
1045    return VisiblePosition(first) == VisiblePosition(second.upstream());
1046}
1047
1048// Determines whether a node is inside a range or visibly starts and ends at the boundaries of the range.
1049// Call this function to determine whether a node is visibly fit inside selectedRange
1050bool isNodeVisiblyContainedWithin(Node& node, const Range& selectedRange)
1051{
1052    // If the node is inside the range, then it surely is contained within
1053    if (selectedRange.compareNode(&node, IGNORE_EXCEPTION) == Range::NODE_INSIDE)
1054        return true;
1055
1056    bool startIsVisuallySame = visiblePositionBeforeNode(node) == VisiblePosition(selectedRange.startPosition());
1057    if (startIsVisuallySame && comparePositions(positionInParentAfterNode(node), selectedRange.endPosition()) < 0)
1058        return true;
1059
1060    bool endIsVisuallySame = visiblePositionAfterNode(node) == VisiblePosition(selectedRange.endPosition());
1061    if (endIsVisuallySame && comparePositions(selectedRange.startPosition(), positionInParentBeforeNode(node)) < 0)
1062        return true;
1063
1064    return startIsVisuallySame && endIsVisuallySame;
1065}
1066
1067bool isRenderedAsNonInlineTableImageOrHR(const Node* node)
1068{
1069    if (!node)
1070        return false;
1071    RenderObject* renderer = node->renderer();
1072    return renderer && ((renderer->isTable() && !renderer->isInline()) || (renderer->isImage() && !renderer->isInline()) || renderer->isHR());
1073}
1074
1075bool areIdenticalElements(const Node* first, const Node* second)
1076{
1077    if (!first->isElementNode() || !second->isElementNode())
1078        return false;
1079
1080    const Element* firstElement = toElement(first);
1081    const Element* secondElement = toElement(second);
1082    if (!firstElement->hasTagName(secondElement->tagQName()))
1083        return false;
1084
1085    return firstElement->hasEquivalentAttributes(secondElement);
1086}
1087
1088bool isNonTableCellHTMLBlockElement(const Node* node)
1089{
1090    return node->hasTagName(listingTag)
1091        || node->hasTagName(olTag)
1092        || node->hasTagName(preTag)
1093        || node->hasTagName(tableTag)
1094        || node->hasTagName(ulTag)
1095        || node->hasTagName(xmpTag)
1096        || node->hasTagName(h1Tag)
1097        || node->hasTagName(h2Tag)
1098        || node->hasTagName(h3Tag)
1099        || node->hasTagName(h4Tag)
1100        || node->hasTagName(h5Tag);
1101}
1102
1103Position adjustedSelectionStartForStyleComputation(const VisibleSelection& selection)
1104{
1105    // This function is used by range style computations to avoid bugs like:
1106    // <rdar://problem/4017641> REGRESSION (Mail): you can only bold/unbold a selection starting from end of line once
1107    // It is important to skip certain irrelevant content at the start of the selection, so we do not wind up
1108    // with a spurious "mixed" style.
1109
1110    VisiblePosition visiblePosition(selection.start());
1111    if (visiblePosition.isNull())
1112        return Position();
1113
1114    // if the selection is a caret, just return the position, since the style
1115    // behind us is relevant
1116    if (selection.isCaret())
1117        return visiblePosition.deepEquivalent();
1118
1119    // if the selection starts just before a paragraph break, skip over it
1120    if (isEndOfParagraph(visiblePosition))
1121        return visiblePosition.next().deepEquivalent().downstream();
1122
1123    // otherwise, make sure to be at the start of the first selected node,
1124    // instead of possibly at the end of the last node before the selection
1125    return visiblePosition.deepEquivalent().downstream();
1126}
1127
1128} // namespace WebCore
1129