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 "htmlediting.h"
28
29#include "Document.h"
30#include "EditingText.h"
31#include "HTMLBRElement.h"
32#include "HTMLDivElement.h"
33#include "HTMLElementFactory.h"
34#include "HTMLInterchange.h"
35#include "HTMLLIElement.h"
36#include "HTMLNames.h"
37#include "HTMLObjectElement.h"
38#include "HTMLOListElement.h"
39#include "HTMLUListElement.h"
40#include "PositionIterator.h"
41#include "RenderObject.h"
42#include "Range.h"
43#include "VisibleSelection.h"
44#include "Text.h"
45#include "TextIterator.h"
46#include "VisiblePosition.h"
47#include "visible_units.h"
48#include <wtf/StdLibExtras.h>
49#include <wtf/unicode/CharacterNames.h>
50
51#if ENABLE(WML)
52#include "WMLNames.h"
53#endif
54
55using namespace std;
56
57namespace WebCore {
58
59using namespace HTMLNames;
60
61// Atomic means that the node has no children, or has children which are ignored for the
62// purposes of editing.
63bool isAtomicNode(const Node *node)
64{
65    return node && (!node->hasChildNodes() || editingIgnoresContent(node));
66}
67
68// Returns true for nodes that either have no content, or have content that is ignored (skipped
69// over) while editing.  There are no VisiblePositions inside these nodes.
70bool editingIgnoresContent(const Node* node)
71{
72    return !canHaveChildrenForEditing(node) && !node->isTextNode();
73}
74
75bool canHaveChildrenForEditing(const Node* node)
76{
77    return !node->isTextNode()
78        && !node->hasTagName(brTag)
79        && !node->hasTagName(imgTag)
80        && !node->hasTagName(inputTag)
81        && !node->hasTagName(textareaTag)
82        && (!node->hasTagName(objectTag) || static_cast<const HTMLObjectElement*>(node)->useFallbackContent())
83        && !node->hasTagName(iframeTag)
84        && !node->hasTagName(embedTag)
85        && !node->hasTagName(appletTag)
86        && !node->hasTagName(selectTag)
87#if ENABLE(WML)
88        && !node->hasTagName(WMLNames::doTag)
89#endif
90        && ((!node->hasTagName(hrTag) && !node->hasTagName(datagridTag)) || node->hasChildNodes());
91}
92
93// Compare two positions, taking into account the possibility that one or both
94// could be inside a shadow tree. Only works for non-null values.
95int comparePositions(const Position& a, const Position& b)
96{
97    Node* nodeA = a.deprecatedNode();
98    ASSERT(nodeA);
99    Node* nodeB = b.deprecatedNode();
100    ASSERT(nodeB);
101    int offsetA = a.deprecatedEditingOffset();
102    int offsetB = b.deprecatedEditingOffset();
103
104    Node* shadowAncestorA = nodeA->shadowAncestorNode();
105    if (shadowAncestorA == nodeA)
106        shadowAncestorA = 0;
107    Node* shadowAncestorB = nodeB->shadowAncestorNode();
108    if (shadowAncestorB == nodeB)
109        shadowAncestorB = 0;
110
111    int bias = 0;
112    if (shadowAncestorA != shadowAncestorB) {
113        if (shadowAncestorA) {
114            nodeA = shadowAncestorA;
115            offsetA = 0;
116            bias = 1;
117        }
118        if (shadowAncestorB) {
119            nodeB = shadowAncestorB;
120            offsetB = 0;
121            bias = -1;
122        }
123    }
124
125    ExceptionCode ec;
126    int result = Range::compareBoundaryPoints(nodeA, offsetA, nodeB, offsetB, ec);
127    return result ? result : bias;
128}
129
130int comparePositions(const VisiblePosition& a, const VisiblePosition& b)
131{
132    return comparePositions(a.deepEquivalent(), b.deepEquivalent());
133}
134
135Node* highestEditableRoot(const Position& position)
136{
137    Node* node = position.deprecatedNode();
138    if (!node)
139        return 0;
140
141    Node* highestRoot = editableRootForPosition(position);
142    if (!highestRoot)
143        return 0;
144
145    node = highestRoot;
146    while (node) {
147        if (node->rendererIsEditable())
148            highestRoot = node;
149        if (node->hasTagName(bodyTag))
150            break;
151        node = node->parentNode();
152    }
153
154    return highestRoot;
155}
156
157Node* lowestEditableAncestor(Node* node)
158{
159    if (!node)
160        return 0;
161
162    Node *lowestRoot = 0;
163    while (node) {
164        if (node->rendererIsEditable())
165            return node->rootEditableElement();
166        if (node->hasTagName(bodyTag))
167            break;
168        node = node->parentNode();
169    }
170
171    return lowestRoot;
172}
173
174bool isEditablePosition(const Position& p)
175{
176    Node* node = p.deprecatedNode();
177    if (!node)
178        return false;
179
180    if (node->renderer() && node->renderer()->isTable())
181        node = node->parentNode();
182
183    return node->rendererIsEditable();
184}
185
186bool isAtUnsplittableElement(const Position& pos)
187{
188    Node* node = pos.deprecatedNode();
189    return (node == editableRootForPosition(pos) || node == enclosingNodeOfType(pos, &isTableCell));
190}
191
192
193bool isRichlyEditablePosition(const Position& p)
194{
195    Node* node = p.deprecatedNode();
196    if (!node)
197        return false;
198
199    if (node->renderer() && node->renderer()->isTable())
200        node = node->parentNode();
201
202    return node->rendererIsRichlyEditable();
203}
204
205Element* editableRootForPosition(const Position& p)
206{
207    Node* node = p.deprecatedNode();
208    if (!node)
209        return 0;
210
211    if (node->renderer() && node->renderer()->isTable())
212        node = node->parentNode();
213
214    return node->rootEditableElement();
215}
216
217// Finds the enclosing element until which the tree can be split.
218// When a user hits ENTER, he/she won't expect this element to be split into two.
219// You may pass it as the second argument of splitTreeToNode.
220Element* unsplittableElementForPosition(const Position& p)
221{
222    // Since enclosingNodeOfType won't search beyond the highest root editable node,
223    // this code works even if the closest table cell was outside of the root editable node.
224    Element* enclosingCell = static_cast<Element*>(enclosingNodeOfType(p, &isTableCell));
225    if (enclosingCell)
226        return enclosingCell;
227
228    return editableRootForPosition(p);
229}
230
231Position nextCandidate(const Position& position)
232{
233    PositionIterator p = position;
234    while (!p.atEnd()) {
235        p.increment();
236        if (p.isCandidate())
237            return p;
238    }
239    return Position();
240}
241
242Position nextVisuallyDistinctCandidate(const Position& position)
243{
244    Position p = position;
245    Position downstreamStart = p.downstream();
246    while (!p.atEndOfTree()) {
247        p = p.next(Character);
248        if (p.isCandidate() && p.downstream() != downstreamStart)
249            return p;
250    }
251    return Position();
252}
253
254Position previousCandidate(const Position& position)
255{
256    PositionIterator p = position;
257    while (!p.atStart()) {
258        p.decrement();
259        if (p.isCandidate())
260            return p;
261    }
262    return Position();
263}
264
265Position previousVisuallyDistinctCandidate(const Position& position)
266{
267    Position p = position;
268    Position downstreamStart = p.downstream();
269    while (!p.atStartOfTree()) {
270        p = p.previous(Character);
271        if (p.isCandidate() && p.downstream() != downstreamStart)
272            return p;
273    }
274    return Position();
275}
276
277VisiblePosition firstEditablePositionAfterPositionInRoot(const Position& position, Node* highestRoot)
278{
279    // position falls before highestRoot.
280    if (comparePositions(position, firstPositionInNode(highestRoot)) == -1 && highestRoot->rendererIsEditable())
281        return firstPositionInNode(highestRoot);
282
283    Position p = position;
284
285    if (Node* shadowAncestor = p.deprecatedNode()->shadowAncestorNode())
286        if (shadowAncestor != p.deprecatedNode())
287            p = positionAfterNode(shadowAncestor);
288
289    while (p.deprecatedNode() && !isEditablePosition(p) && p.deprecatedNode()->isDescendantOf(highestRoot))
290        p = isAtomicNode(p.deprecatedNode()) ? positionInParentAfterNode(p.deprecatedNode()) : nextVisuallyDistinctCandidate(p);
291
292    if (p.deprecatedNode() && p.deprecatedNode() != highestRoot && !p.deprecatedNode()->isDescendantOf(highestRoot))
293        return VisiblePosition();
294
295    return VisiblePosition(p);
296}
297
298VisiblePosition lastEditablePositionBeforePositionInRoot(const Position& position, Node* highestRoot)
299{
300    // When position falls after highestRoot, the result is easy to compute.
301    if (comparePositions(position, lastPositionInNode(highestRoot)) == 1)
302        return lastPositionInNode(highestRoot);
303
304    Position p = position;
305
306    if (Node* shadowAncestor = p.deprecatedNode()->shadowAncestorNode()) {
307        if (shadowAncestor != p.deprecatedNode())
308            p = firstPositionInOrBeforeNode(shadowAncestor);
309    }
310
311    while (p.deprecatedNode() && !isEditablePosition(p) && p.deprecatedNode()->isDescendantOf(highestRoot))
312        p = isAtomicNode(p.deprecatedNode()) ? positionInParentBeforeNode(p.deprecatedNode()) : previousVisuallyDistinctCandidate(p);
313
314    if (p.deprecatedNode() && p.deprecatedNode() != highestRoot && !p.deprecatedNode()->isDescendantOf(highestRoot))
315        return VisiblePosition();
316
317    return VisiblePosition(p);
318}
319
320// FIXME: The method name, comment, and code say three different things here!
321// Whether or not content before and after this node will collapse onto the same line as it.
322bool isBlock(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.
331Node* enclosingBlock(Node* node, EditingBoundaryCrossingRule rule)
332{
333    return static_cast<Element*>(enclosingNodeOfType(firstPositionInOrBeforeNode(node), isBlock, rule));
334}
335
336TextDirection directionOfEnclosingBlock(const Position& position)
337{
338    Node* enclosingBlockNode = enclosingBlock(position.containerNode());
339    if (!enclosingBlockNode)
340        return LTR;
341    RenderObject* renderer = enclosingBlockNode->renderer();
342    return renderer ? renderer->style()->direction() : LTR;
343}
344
345// This method is used to create positions in the DOM. It returns the maximum valid offset
346// in a node.  It returns 1 for some elements even though they do not have children, which
347// creates technically invalid DOM Positions.  Be sure to call parentAnchoredEquivalent
348// on a Position before using it to create a DOM Range, or an exception will be thrown.
349int lastOffsetForEditing(const Node* node)
350{
351    ASSERT(node);
352    if (!node)
353        return 0;
354    if (node->offsetInCharacters())
355        return node->maxCharacterOffset();
356
357    if (node->hasChildNodes())
358        return node->childNodeCount();
359
360    // NOTE: This should preempt the childNodeCount for, e.g., select nodes
361    if (editingIgnoresContent(node))
362        return 1;
363
364    return 0;
365}
366
367String stringWithRebalancedWhitespace(const String& string, bool startIsStartOfParagraph, bool endIsEndOfParagraph)
368{
369    Vector<UChar> rebalancedString;
370    append(rebalancedString, string);
371
372    bool previousCharacterWasSpace = false;
373    for (size_t i = 0; i < rebalancedString.size(); i++) {
374        if (!isWhitespace(rebalancedString[i])) {
375            previousCharacterWasSpace = false;
376            continue;
377        }
378
379        if (previousCharacterWasSpace || (!i && startIsStartOfParagraph) || (i + 1 == rebalancedString.size() && endIsEndOfParagraph)) {
380            rebalancedString[i] = noBreakSpace;
381            previousCharacterWasSpace = false;
382        } else {
383            rebalancedString[i] = ' ';
384            previousCharacterWasSpace = true;
385        }
386
387    }
388
389    return String::adopt(rebalancedString);
390}
391
392bool isTableStructureNode(const Node *node)
393{
394    RenderObject *r = node->renderer();
395    return (r && (r->isTableCell() || r->isTableRow() || r->isTableSection() || r->isTableCol()));
396}
397
398const String& nonBreakingSpaceString()
399{
400    DEFINE_STATIC_LOCAL(String, nonBreakingSpaceString, (&noBreakSpace, 1));
401    return nonBreakingSpaceString;
402}
403
404// FIXME: need to dump this
405bool isSpecialElement(const Node *n)
406{
407    if (!n)
408        return false;
409
410    if (!n->isHTMLElement())
411        return false;
412
413    if (n->isLink())
414        return true;
415
416    RenderObject *renderer = n->renderer();
417    if (!renderer)
418        return false;
419
420    if (renderer->style()->display() == TABLE || renderer->style()->display() == INLINE_TABLE)
421        return true;
422
423    if (renderer->style()->isFloating())
424        return true;
425
426    if (renderer->style()->position() != StaticPosition)
427        return true;
428
429    return false;
430}
431
432static Node* firstInSpecialElement(const Position& pos)
433{
434    // FIXME: This begins at pos.deprecatedNode(), which doesn't necessarily contain pos (suppose pos was [img, 0]).  See <rdar://problem/5027702>.
435    Node* rootEditableElement = pos.deprecatedNode()->rootEditableElement();
436    for (Node* n = pos.deprecatedNode(); n && n->rootEditableElement() == rootEditableElement; n = n->parentNode())
437        if (isSpecialElement(n)) {
438            VisiblePosition vPos = VisiblePosition(pos, DOWNSTREAM);
439            VisiblePosition firstInElement = VisiblePosition(firstPositionInOrBeforeNode(n), DOWNSTREAM);
440            if (isTableElement(n) && vPos == firstInElement.next())
441                return n;
442            if (vPos == firstInElement)
443                return n;
444        }
445    return 0;
446}
447
448static Node* lastInSpecialElement(const Position& pos)
449{
450    // FIXME: This begins at pos.deprecatedNode(), which doesn't necessarily contain pos (suppose pos was [img, 0]).  See <rdar://problem/5027702>.
451    Node* rootEditableElement = pos.deprecatedNode()->rootEditableElement();
452    for (Node* n = pos.deprecatedNode(); n && n->rootEditableElement() == rootEditableElement; n = n->parentNode())
453        if (isSpecialElement(n)) {
454            VisiblePosition vPos = VisiblePosition(pos, DOWNSTREAM);
455            VisiblePosition lastInElement = VisiblePosition(Position(n, n->childNodeCount(), Position::PositionIsOffsetInAnchor), DOWNSTREAM);
456            if (isTableElement(n) && vPos == lastInElement.previous())
457                return n;
458            if (vPos == lastInElement)
459                return n;
460        }
461    return 0;
462}
463
464bool isFirstVisiblePositionInSpecialElement(const Position& pos)
465{
466    return firstInSpecialElement(pos);
467}
468
469Position positionBeforeContainingSpecialElement(const Position& pos, Node** containingSpecialElement)
470{
471    Node* n = firstInSpecialElement(pos);
472    if (!n)
473        return pos;
474    Position result = positionInParentBeforeNode(n);
475    if (result.isNull() || result.deprecatedNode()->rootEditableElement() != pos.deprecatedNode()->rootEditableElement())
476        return pos;
477    if (containingSpecialElement)
478        *containingSpecialElement = n;
479    return result;
480}
481
482bool isLastVisiblePositionInSpecialElement(const Position& pos)
483{
484    return lastInSpecialElement(pos);
485}
486
487Position positionAfterContainingSpecialElement(const Position& pos, Node **containingSpecialElement)
488{
489    Node* n = lastInSpecialElement(pos);
490    if (!n)
491        return pos;
492    Position result = positionInParentAfterNode(n);
493    if (result.isNull() || result.deprecatedNode()->rootEditableElement() != pos.deprecatedNode()->rootEditableElement())
494        return pos;
495    if (containingSpecialElement)
496        *containingSpecialElement = n;
497    return result;
498}
499
500Position positionOutsideContainingSpecialElement(const Position &pos, Node **containingSpecialElement)
501{
502    if (isFirstVisiblePositionInSpecialElement(pos))
503        return positionBeforeContainingSpecialElement(pos, containingSpecialElement);
504    if (isLastVisiblePositionInSpecialElement(pos))
505        return positionAfterContainingSpecialElement(pos, containingSpecialElement);
506    return pos;
507}
508
509Node* isFirstPositionAfterTable(const VisiblePosition& visiblePosition)
510{
511    Position upstream(visiblePosition.deepEquivalent().upstream());
512    if (upstream.deprecatedNode() && upstream.deprecatedNode()->renderer() && upstream.deprecatedNode()->renderer()->isTable() && upstream.atLastEditingPositionForNode())
513        return upstream.deprecatedNode();
514
515    return 0;
516}
517
518Node* isLastPositionBeforeTable(const VisiblePosition& visiblePosition)
519{
520    Position downstream(visiblePosition.deepEquivalent().downstream());
521    if (downstream.deprecatedNode() && downstream.deprecatedNode()->renderer() && downstream.deprecatedNode()->renderer()->isTable() && downstream.atFirstEditingPositionForNode())
522        return downstream.deprecatedNode();
523
524    return 0;
525}
526
527// Returns the visible position at the beginning of a node
528VisiblePosition visiblePositionBeforeNode(Node* node)
529{
530    ASSERT(node);
531    if (node->childNodeCount())
532        return VisiblePosition(firstPositionInOrBeforeNode(node), DOWNSTREAM);
533    ASSERT(node->parentNode());
534    return positionInParentBeforeNode(node);
535}
536
537// Returns the visible position at the ending of a node
538VisiblePosition visiblePositionAfterNode(Node* node)
539{
540    ASSERT(node);
541    if (node->childNodeCount())
542        return VisiblePosition(lastPositionInOrAfterNode(node), DOWNSTREAM);
543    ASSERT(node->parentNode());
544    return positionInParentAfterNode(node);
545}
546
547// Create a range object with two visible positions, start and end.
548// create(PassRefPtr<Document>, const Position&, const Position&); will use deprecatedEditingOffset
549// Use this function instead of create a regular range object (avoiding editing offset).
550PassRefPtr<Range> createRange(PassRefPtr<Document> document, const VisiblePosition& start, const VisiblePosition& end, ExceptionCode& ec)
551{
552    ec = 0;
553    RefPtr<Range> selectedRange = Range::create(document);
554    selectedRange->setStart(start.deepEquivalent().containerNode(), start.deepEquivalent().computeOffsetInContainerNode(), ec);
555    if (!ec)
556        selectedRange->setEnd(end.deepEquivalent().containerNode(), end.deepEquivalent().computeOffsetInContainerNode(), ec);
557    return selectedRange.release();
558}
559
560// Extend rangeToExtend to include nodes that wraps range and visibly starts and ends inside or at the boudnaries of maximumRange
561// e.g. if the original range spaned "hello" in <div>hello</div>, then this function extends the range to contain div's around it.
562// Call this function before copying / moving paragraphs to contain all wrapping nodes.
563// This function stops extending the range immediately below rootNode; i.e. the extended range can contain a child node of rootNode
564// but it can never contain rootNode itself.
565PassRefPtr<Range> extendRangeToWrappingNodes(PassRefPtr<Range> range, const Range* maximumRange, const Node* rootNode)
566{
567    ASSERT(range);
568    ASSERT(maximumRange);
569
570    ExceptionCode ec = 0;
571    Node* ancestor = range->commonAncestorContainer(ec);// find the cloeset common ancestor
572    Node* highestNode = 0;
573    // traverse through ancestors as long as they are contained within the range, content-editable, and below rootNode (could be =0).
574    while (ancestor && ancestor->rendererIsEditable() && isNodeVisiblyContainedWithin(ancestor, maximumRange) && ancestor != rootNode) {
575        highestNode = ancestor;
576        ancestor = ancestor->parentNode();
577    }
578
579    if (!highestNode)
580        return range;
581
582    // Create new range with the highest editable node contained within the range
583    RefPtr<Range> extendedRange = Range::create(range->ownerDocument());
584    extendedRange->selectNode(highestNode, ec);
585    return extendedRange.release();
586}
587
588bool isListElement(Node *n)
589{
590    return (n && (n->hasTagName(ulTag) || n->hasTagName(olTag) || n->hasTagName(dlTag)));
591}
592
593bool isListItem(Node *n)
594{
595    return n && n->renderer() && n->renderer()->isListItem();
596}
597
598Node* enclosingNodeWithTag(const Position& p, const QualifiedName& tagName)
599{
600    if (p.isNull())
601        return 0;
602
603    Node* root = highestEditableRoot(p);
604    for (Node* n = p.deprecatedNode(); n; n = n->parentNode()) {
605        if (root && !n->rendererIsEditable())
606            continue;
607        if (n->hasTagName(tagName))
608            return n;
609        if (n == root)
610            return 0;
611    }
612
613    return 0;
614}
615
616Node* enclosingNodeOfType(const Position& p, bool (*nodeIsOfType)(const Node*), EditingBoundaryCrossingRule rule)
617{
618    // FIXME: support CanSkipCrossEditingBoundary
619    ASSERT(rule == CanCrossEditingBoundary || rule == CannotCrossEditingBoundary);
620    if (p.isNull())
621        return 0;
622
623    Node* root = rule == CannotCrossEditingBoundary ? highestEditableRoot(p) : 0;
624    for (Node* n = p.deprecatedNode(); n; n = n->parentNode()) {
625        // Don't return a non-editable node if the input position was editable, since
626        // the callers from editing will no doubt want to perform editing inside the returned node.
627        if (root && !n->rendererIsEditable())
628            continue;
629        if (nodeIsOfType(n))
630            return n;
631        if (n == root)
632            return 0;
633    }
634
635    return 0;
636}
637
638Node* highestEnclosingNodeOfType(const Position& p, bool (*nodeIsOfType)(const Node*), EditingBoundaryCrossingRule rule)
639{
640    Node* highest = 0;
641    Node* root = rule == CannotCrossEditingBoundary ? highestEditableRoot(p) : 0;
642    for (Node* n = p.containerNode(); n; n = n->parentNode()) {
643        if (root && !n->rendererIsEditable())
644            continue;
645        if (nodeIsOfType(n))
646            highest = n;
647        if (n == root)
648            break;
649    }
650
651    return highest;
652}
653
654Node* enclosingTableCell(const Position& p)
655{
656    return static_cast<Element*>(enclosingNodeOfType(p, isTableCell));
657}
658
659Node* enclosingAnchorElement(const Position& p)
660{
661    if (p.isNull())
662        return 0;
663
664    Node* node = p.deprecatedNode();
665    while (node && !(node->isElementNode() && node->isLink()))
666        node = node->parentNode();
667    return node;
668}
669
670HTMLElement* enclosingList(Node* node)
671{
672    if (!node)
673        return 0;
674
675    Node* root = highestEditableRoot(firstPositionInOrBeforeNode(node));
676
677    for (ContainerNode* n = node->parentNode(); n; n = n->parentNode()) {
678        if (n->hasTagName(ulTag) || n->hasTagName(olTag))
679            return toHTMLElement(n);
680        if (n == root)
681            return 0;
682    }
683
684    return 0;
685}
686
687Node* enclosingListChild(Node *node)
688{
689    if (!node)
690        return 0;
691    // Check for a list item element, or for a node whose parent is a list element.  Such a node
692    // will appear visually as a list item (but without a list marker)
693    Node* root = highestEditableRoot(firstPositionInOrBeforeNode(node));
694
695    // FIXME: This function is inappropriately named if it starts with node instead of node->parentNode()
696    for (Node* n = node; n && n->parentNode(); n = n->parentNode()) {
697        if (n->hasTagName(liTag) || isListElement(n->parentNode()))
698            return n;
699        if (n == root || isTableCell(n))
700            return 0;
701    }
702
703    return 0;
704}
705
706static HTMLElement* embeddedSublist(Node* listItem)
707{
708    // Check the DOM so that we'll find collapsed sublists without renderers.
709    for (Node* n = listItem->firstChild(); n; n = n->nextSibling()) {
710        if (isListElement(n))
711            return toHTMLElement(n);
712    }
713
714    return 0;
715}
716
717static Node* appendedSublist(Node* listItem)
718{
719    // Check the DOM so that we'll find collapsed sublists without renderers.
720    for (Node* n = listItem->nextSibling(); n; n = n->nextSibling()) {
721        if (isListElement(n))
722            return toHTMLElement(n);
723        if (isListItem(listItem))
724            return 0;
725    }
726
727    return 0;
728}
729
730// FIXME: This method should not need to call isStartOfParagraph/isEndOfParagraph
731Node* enclosingEmptyListItem(const VisiblePosition& visiblePos)
732{
733    // Check that position is on a line by itself inside a list item
734    Node* listChildNode = enclosingListChild(visiblePos.deepEquivalent().deprecatedNode());
735    if (!listChildNode || !isStartOfParagraph(visiblePos) || !isEndOfParagraph(visiblePos))
736        return 0;
737
738    VisiblePosition firstInListChild(firstPositionInOrBeforeNode(listChildNode));
739    VisiblePosition lastInListChild(lastPositionInOrAfterNode(listChildNode));
740
741    if (firstInListChild != visiblePos || lastInListChild != visiblePos)
742        return 0;
743
744    if (embeddedSublist(listChildNode) || appendedSublist(listChildNode))
745        return 0;
746
747    return listChildNode;
748}
749
750HTMLElement* outermostEnclosingList(Node* node, Node* rootList)
751{
752    HTMLElement* list = enclosingList(node);
753    if (!list)
754        return 0;
755
756    while (HTMLElement* nextList = enclosingList(list)) {
757        if (nextList == rootList)
758            break;
759        list = nextList;
760    }
761
762    return list;
763}
764
765bool canMergeLists(Element* firstList, Element* secondList)
766{
767    if (!firstList || !secondList || !firstList->isHTMLElement() || !secondList->isHTMLElement())
768        return false;
769
770    return firstList->hasTagName(secondList->tagQName())// make sure the list types match (ol vs. ul)
771    && firstList->rendererIsEditable() && secondList->rendererIsEditable() // both lists are editable
772    && firstList->rootEditableElement() == secondList->rootEditableElement()// don't cross editing boundaries
773    && isVisiblyAdjacent(positionInParentAfterNode(firstList), positionInParentBeforeNode(secondList));
774    // Make sure there is no visible content between this li and the previous list
775}
776
777Node* highestAncestor(Node* node)
778{
779    ASSERT(node);
780    Node* parent = node;
781    while ((node = node->parentNode()))
782        parent = node;
783    return parent;
784}
785
786// FIXME: do not require renderer, so that this can be used within fragments, or rename to isRenderedTable()
787bool isTableElement(Node* n)
788{
789    if (!n || !n->isElementNode())
790        return false;
791
792    RenderObject* renderer = n->renderer();
793    return (renderer && (renderer->style()->display() == TABLE || renderer->style()->display() == INLINE_TABLE));
794}
795
796bool isTableCell(const Node* node)
797{
798    RenderObject* r = node->renderer();
799    if (!r)
800        return node->hasTagName(tdTag) || node->hasTagName(thTag);
801
802    return r->isTableCell();
803}
804
805bool isEmptyTableCell(const Node* node)
806{
807    // Returns true IFF the passed in node is one of:
808    //   .) a table cell with no children,
809    //   .) a table cell with a single BR child, and which has no other child renderers, including :before and :after renderers
810    //   .) the BR child of such a table cell
811
812    // Find rendered node
813    while (node && !node->renderer())
814        node = node->parentNode();
815    if (!node)
816        return false;
817
818    // Make sure the rendered node is a table cell or <br>.
819    // If it's a <br>, then the parent node has to be a table cell.
820    RenderObject* renderer = node->renderer();
821    if (renderer->isBR()) {
822        renderer = renderer->parent();
823        if (!renderer)
824            return false;
825    }
826    if (!renderer->isTableCell())
827        return false;
828
829    // Check that the table cell contains no child renderers except for perhaps a single <br>.
830    RenderObject* childRenderer = renderer->firstChild();
831    if (!childRenderer)
832        return true;
833    if (!childRenderer->isBR())
834        return false;
835    return !childRenderer->nextSibling();
836}
837
838PassRefPtr<HTMLElement> createDefaultParagraphElement(Document* document)
839{
840    return HTMLDivElement::create(document);
841}
842
843PassRefPtr<HTMLElement> createBreakElement(Document* document)
844{
845    return HTMLBRElement::create(document);
846}
847
848PassRefPtr<HTMLElement> createOrderedListElement(Document* document)
849{
850    return HTMLOListElement::create(document);
851}
852
853PassRefPtr<HTMLElement> createUnorderedListElement(Document* document)
854{
855    return HTMLUListElement::create(document);
856}
857
858PassRefPtr<HTMLElement> createListItemElement(Document* document)
859{
860    return HTMLLIElement::create(document);
861}
862
863PassRefPtr<HTMLElement> createHTMLElement(Document* document, const QualifiedName& name)
864{
865    return HTMLElementFactory::createHTMLElement(name, document, 0, false);
866}
867
868PassRefPtr<HTMLElement> createHTMLElement(Document* document, const AtomicString& tagName)
869{
870    return createHTMLElement(document, QualifiedName(nullAtom, tagName, xhtmlNamespaceURI));
871}
872
873bool isTabSpanNode(const Node *node)
874{
875    return node && node->hasTagName(spanTag) && node->isElementNode() && static_cast<const Element *>(node)->getAttribute(classAttr) == AppleTabSpanClass;
876}
877
878bool isTabSpanTextNode(const Node *node)
879{
880    return node && node->isTextNode() && node->parentNode() && isTabSpanNode(node->parentNode());
881}
882
883Node *tabSpanNode(const Node *node)
884{
885    return isTabSpanTextNode(node) ? node->parentNode() : 0;
886}
887
888bool isNodeInTextFormControl(Node* node)
889{
890    if (!node)
891        return false;
892    Node* ancestor = node->shadowAncestorNode();
893    if (ancestor == node)
894        return false;
895    return ancestor->isElementNode() && static_cast<Element*>(ancestor)->isTextFormControl();
896}
897
898Position positionOutsideTabSpan(const Position& pos)
899{
900    Node* node = pos.containerNode();
901    if (isTabSpanTextNode(node))
902        node = tabSpanNode(node);
903    else if (!isTabSpanNode(node))
904        return pos;
905
906    if (node && VisiblePosition(pos) == lastPositionInNode(node))
907        return positionInParentAfterNode(node);
908
909    return positionInParentBeforeNode(node);
910}
911
912PassRefPtr<Element> createTabSpanElement(Document* document, PassRefPtr<Node> tabTextNode)
913{
914    // Make the span to hold the tab.
915    RefPtr<Element> spanElement = document->createElement(spanTag, false);
916    spanElement->setAttribute(classAttr, AppleTabSpanClass);
917    spanElement->setAttribute(styleAttr, "white-space:pre");
918
919    // Add tab text to that span.
920    if (!tabTextNode)
921        tabTextNode = document->createEditingTextNode("\t");
922
923    ExceptionCode ec = 0;
924    spanElement->appendChild(tabTextNode, ec);
925    ASSERT(ec == 0);
926
927    return spanElement.release();
928}
929
930PassRefPtr<Element> createTabSpanElement(Document* document, const String& tabText)
931{
932    return createTabSpanElement(document, document->createTextNode(tabText));
933}
934
935PassRefPtr<Element> createTabSpanElement(Document* document)
936{
937    return createTabSpanElement(document, PassRefPtr<Node>());
938}
939
940bool isNodeRendered(const Node *node)
941{
942    if (!node)
943        return false;
944
945    RenderObject *renderer = node->renderer();
946    if (!renderer)
947        return false;
948
949    return renderer->style()->visibility() == VISIBLE;
950}
951
952unsigned numEnclosingMailBlockquotes(const Position& p)
953{
954    unsigned num = 0;
955    for (Node* n = p.deprecatedNode(); n; n = n->parentNode())
956        if (isMailBlockquote(n))
957            num++;
958
959    return num;
960}
961
962bool isMailBlockquote(const Node *node)
963{
964    if (!node || !node->hasTagName(blockquoteTag))
965        return false;
966
967    return static_cast<const Element *>(node)->getAttribute("type") == "cite";
968}
969
970int caretMinOffset(const Node* n)
971{
972    RenderObject* r = n->renderer();
973    ASSERT(!n->isCharacterDataNode() || !r || r->isText()); // FIXME: This was a runtime check that seemingly couldn't fail; changed it to an assertion for now.
974    return r ? r->caretMinOffset() : 0;
975}
976
977// If a node can contain candidates for VisiblePositions, return the offset of the last candidate, otherwise
978// return the number of children for container nodes and the length for unrendered text nodes.
979int caretMaxOffset(const Node* n)
980{
981    // For rendered text nodes, return the last position that a caret could occupy.
982    if (n->isTextNode() && n->renderer())
983        return n->renderer()->caretMaxOffset();
984    // For containers return the number of children.  For others do the same as above.
985    return lastOffsetForEditing(n);
986}
987
988bool lineBreakExistsAtVisiblePosition(const VisiblePosition& visiblePosition)
989{
990    return lineBreakExistsAtPosition(visiblePosition.deepEquivalent().downstream());
991}
992
993bool lineBreakExistsAtPosition(const Position& position)
994{
995    if (position.isNull())
996        return false;
997
998    if (position.anchorNode()->hasTagName(brTag) && position.atFirstEditingPositionForNode())
999        return true;
1000
1001    if (!position.anchorNode()->renderer())
1002        return false;
1003
1004    if (!position.anchorNode()->isTextNode() || !position.anchorNode()->renderer()->style()->preserveNewline())
1005        return false;
1006
1007    Text* textNode = static_cast<Text*>(position.anchorNode());
1008    unsigned offset = position.offsetInContainerNode();
1009    return offset < textNode->length() && textNode->data()[offset] == '\n';
1010}
1011
1012// Modifies selections that have an end point at the edge of a table
1013// that contains the other endpoint so that they don't confuse
1014// code that iterates over selected paragraphs.
1015VisibleSelection selectionForParagraphIteration(const VisibleSelection& original)
1016{
1017    VisibleSelection newSelection(original);
1018    VisiblePosition startOfSelection(newSelection.visibleStart());
1019    VisiblePosition endOfSelection(newSelection.visibleEnd());
1020
1021    // If the end of the selection to modify is just after a table, and
1022    // if the start of the selection is inside that table, then the last paragraph
1023    // that we'll want modify is the last one inside the table, not the table itself
1024    // (a table is itself a paragraph).
1025    if (Node* table = isFirstPositionAfterTable(endOfSelection))
1026        if (startOfSelection.deepEquivalent().deprecatedNode()->isDescendantOf(table))
1027            newSelection = VisibleSelection(startOfSelection, endOfSelection.previous(CannotCrossEditingBoundary));
1028
1029    // If the start of the selection to modify is just before a table,
1030    // and if the end of the selection is inside that table, then the first paragraph
1031    // we'll want to modify is the first one inside the table, not the paragraph
1032    // containing the table itself.
1033    if (Node* table = isLastPositionBeforeTable(startOfSelection))
1034        if (endOfSelection.deepEquivalent().deprecatedNode()->isDescendantOf(table))
1035            newSelection = VisibleSelection(startOfSelection.next(CannotCrossEditingBoundary), endOfSelection);
1036
1037    return newSelection;
1038}
1039
1040
1041int indexForVisiblePosition(const VisiblePosition& visiblePosition)
1042{
1043    if (visiblePosition.isNull())
1044        return 0;
1045    Position p(visiblePosition.deepEquivalent());
1046    RefPtr<Range> range = Range::create(p.anchorNode()->document(), firstPositionInNode(p.anchorNode()->document()->documentElement()),
1047                                        p.parentAnchoredEquivalent());
1048    return TextIterator::rangeLength(range.get(), true);
1049}
1050
1051// Determines whether two positions are visibly next to each other (first then second)
1052// while ignoring whitespaces and unrendered nodes
1053bool isVisiblyAdjacent(const Position& first, const Position& second)
1054{
1055    return VisiblePosition(first) == VisiblePosition(second.upstream());
1056}
1057
1058// Determines whether a node is inside a range or visibly starts and ends at the boundaries of the range.
1059// Call this function to determine whether a node is visibly fit inside selectedRange
1060bool isNodeVisiblyContainedWithin(Node* node, const Range* selectedRange)
1061{
1062    ASSERT(node);
1063    ASSERT(selectedRange);
1064    // If the node is inside the range, then it surely is contained within
1065    ExceptionCode ec = 0;
1066    if (selectedRange->compareNode(node, ec) == Range::NODE_INSIDE)
1067        return true;
1068
1069    bool startIsVisuallySame = visiblePositionBeforeNode(node) == selectedRange->startPosition();
1070    if (startIsVisuallySame && comparePositions(positionInParentAfterNode(node), selectedRange->endPosition()) < 0)
1071        return true;
1072
1073    bool endIsVisuallySame = visiblePositionAfterNode(node) == selectedRange->endPosition();
1074    if (endIsVisuallySame && comparePositions(selectedRange->startPosition(), positionInParentBeforeNode(node)) < 0)
1075        return true;
1076
1077    return startIsVisuallySame && endIsVisuallySame;
1078}
1079
1080bool isRenderedAsNonInlineTableImageOrHR(const Node* node)
1081{
1082    if (!node)
1083        return false;
1084    RenderObject* renderer = node->renderer();
1085    return renderer && ((renderer->isTable() && !renderer->isInline()) || (renderer->isImage() && !renderer->isInline()) || renderer->isHR());
1086}
1087
1088PassRefPtr<Range> avoidIntersectionWithNode(const Range* range, Node* node)
1089{
1090    if (!range)
1091        return 0;
1092
1093    Document* document = range->ownerDocument();
1094
1095    Node* startContainer = range->startContainer();
1096    int startOffset = range->startOffset();
1097    Node* endContainer = range->endContainer();
1098    int endOffset = range->endOffset();
1099
1100    if (!startContainer)
1101        return 0;
1102
1103    ASSERT(endContainer);
1104
1105    if (startContainer == node || startContainer->isDescendantOf(node)) {
1106        ASSERT(node->parentNode());
1107        startContainer = node->parentNode();
1108        startOffset = node->nodeIndex();
1109    }
1110    if (endContainer == node || endContainer->isDescendantOf(node)) {
1111        ASSERT(node->parentNode());
1112        endContainer = node->parentNode();
1113        endOffset = node->nodeIndex();
1114    }
1115
1116    return Range::create(document, startContainer, startOffset, endContainer, endOffset);
1117}
1118
1119VisibleSelection avoidIntersectionWithNode(const VisibleSelection& selection, Node* node)
1120{
1121    if (selection.isNone())
1122        return VisibleSelection(selection);
1123
1124    VisibleSelection updatedSelection(selection);
1125    Node* base = selection.base().deprecatedNode();
1126    Node* extent = selection.extent().deprecatedNode();
1127    ASSERT(base);
1128    ASSERT(extent);
1129
1130    if (base == node || base->isDescendantOf(node)) {
1131        ASSERT(node->parentNode());
1132        updatedSelection.setBase(positionInParentBeforeNode(node));
1133    }
1134
1135    if (extent == node || extent->isDescendantOf(node)) {
1136        ASSERT(node->parentNode());
1137        updatedSelection.setExtent(positionInParentBeforeNode(node));
1138    }
1139
1140    return updatedSelection;
1141}
1142
1143} // namespace WebCore
1144