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