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