2009-08-18 Maciej Stachowiak <mjs@apple.com>
[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 AtomicString& blockTag)
463 {
464     if (blockTag.isEmpty())
465         return false;
466
467     DEFINE_STATIC_LOCAL(HashSet<AtomicString>, blockTags, ());
468     if (blockTags.isEmpty()) {
469         blockTags.add(addressTag.localName());
470         blockTags.add(blockquoteTag.localName());
471         blockTags.add(ddTag.localName());
472         blockTags.add(divTag.localName());
473         blockTags.add(dlTag.localName());
474         blockTags.add(dtTag.localName());
475         blockTags.add(h1Tag.localName());
476         blockTags.add(h2Tag.localName());
477         blockTags.add(h3Tag.localName());
478         blockTags.add(h4Tag.localName());
479         blockTags.add(h5Tag.localName());
480         blockTags.add(h6Tag.localName());
481         blockTags.add(navTag.localName());
482         blockTags.add(pTag.localName());
483         blockTags.add(preTag.localName());
484     }
485     return blockTags.contains(blockTag);
486 }
487
488 static Node* firstInSpecialElement(const Position& pos)
489 {
490     Node* rootEditableElement = pos.node()->rootEditableElement();
491     for (Node* n = pos.node(); n && n->rootEditableElement() == rootEditableElement; n = n->parentNode())
492         if (isSpecialElement(n)) {
493             VisiblePosition vPos = VisiblePosition(pos, DOWNSTREAM);
494             VisiblePosition firstInElement = VisiblePosition(n, 0, DOWNSTREAM);
495             if (isTableElement(n) && vPos == firstInElement.next())
496                 return n;
497             if (vPos == firstInElement)
498                 return n;
499         }
500     return 0;
501 }
502
503 static Node* lastInSpecialElement(const Position& pos)
504 {
505     Node* rootEditableElement = pos.node()->rootEditableElement();
506     for (Node* n = pos.node(); n && n->rootEditableElement() == rootEditableElement; n = n->parentNode())
507         if (isSpecialElement(n)) {
508             VisiblePosition vPos = VisiblePosition(pos, DOWNSTREAM);
509             VisiblePosition lastInElement = VisiblePosition(n, n->childNodeCount(), DOWNSTREAM);
510             if (isTableElement(n) && vPos == lastInElement.previous())
511                 return n;
512             if (vPos == lastInElement)
513                 return n;
514         }
515     return 0;
516 }
517
518 bool isFirstVisiblePositionInSpecialElement(const Position& pos)
519 {
520     return firstInSpecialElement(pos);
521 }
522
523 Position positionBeforeContainingSpecialElement(const Position& pos, Node** containingSpecialElement)
524 {
525     Node* n = firstInSpecialElement(pos);
526     if (!n)
527         return pos;
528     Position result = positionBeforeNode(n);
529     if (result.isNull() || result.node()->rootEditableElement() != pos.node()->rootEditableElement())
530         return pos;
531     if (containingSpecialElement)
532         *containingSpecialElement = n;
533     return result;
534 }
535
536 bool isLastVisiblePositionInSpecialElement(const Position& pos)
537 {
538     return lastInSpecialElement(pos);
539 }
540
541 Position positionAfterContainingSpecialElement(const Position& pos, Node **containingSpecialElement)
542 {
543     Node* n = lastInSpecialElement(pos);
544     if (!n)
545         return pos;
546     Position result = positionAfterNode(n);
547     if (result.isNull() || result.node()->rootEditableElement() != pos.node()->rootEditableElement())
548         return pos;
549     if (containingSpecialElement)
550         *containingSpecialElement = n;
551     return result;
552 }
553
554 Position positionOutsideContainingSpecialElement(const Position &pos, Node **containingSpecialElement)
555 {
556     if (isFirstVisiblePositionInSpecialElement(pos))
557         return positionBeforeContainingSpecialElement(pos, containingSpecialElement);
558     if (isLastVisiblePositionInSpecialElement(pos))
559         return positionAfterContainingSpecialElement(pos, containingSpecialElement);
560     return pos;
561 }
562
563 Node* isFirstPositionAfterTable(const VisiblePosition& visiblePosition)
564 {
565     Position upstream(visiblePosition.deepEquivalent().upstream());
566     if (upstream.node() && upstream.node()->renderer() && upstream.node()->renderer()->isTable() && upstream.atLastEditingPositionForNode())
567         return upstream.node();
568     
569     return 0;
570 }
571
572 Node* isLastPositionBeforeTable(const VisiblePosition& visiblePosition)
573 {
574     Position downstream(visiblePosition.deepEquivalent().downstream());
575     if (downstream.node() && downstream.node()->renderer() && downstream.node()->renderer()->isTable() && downstream.atFirstEditingPositionForNode())
576         return downstream.node();
577     
578     return 0;
579 }
580
581 Position positionBeforeNode(const Node* node)
582 {
583     ASSERT(node);
584     // FIXME: Should ASSERT(node->parentNode()) but doing so results in editing/deleting/delete-ligature-001.html crashing
585     return Position(node->parentNode(), node->nodeIndex());
586 }
587
588 Position positionAfterNode(const Node* node)
589 {
590     ASSERT(node);
591     // FIXME: Should ASSERT(node->parentNode()) but doing so results in editing/deleting/delete-ligature-001.html crashing
592     return Position(node->parentNode(), node->nodeIndex() + 1);
593 }
594
595 // Returns the visible position at the beginning of a node
596 VisiblePosition visiblePositionBeforeNode(Node* node)
597 {
598     ASSERT(node);
599     if (node->childNodeCount())
600         return VisiblePosition(node, 0, DOWNSTREAM);
601     ASSERT(node->parentNode());
602     return positionBeforeNode(node);
603 }
604
605 // Returns the visible position at the ending of a node
606 VisiblePosition visiblePositionAfterNode(Node* node)
607 {
608     ASSERT(node);
609     if (node->childNodeCount())
610         return VisiblePosition(node, node->childNodeCount(), DOWNSTREAM);
611     ASSERT(node->parentNode());
612     return positionAfterNode(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).
618 PassRefPtr<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.
633 PassRefPtr<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
656 bool isListElement(Node *n)
657 {
658     return (n && (n->hasTagName(ulTag) || n->hasTagName(olTag) || n->hasTagName(dlTag)));
659 }
660
661 Node* enclosingNodeWithTag(const Position& p, const QualifiedName& tagName)
662 {
663     if (p.isNull())
664         return 0;
665         
666     Node* root = highestEditableRoot(p);
667     for (Node* n = p.node(); n; n = n->parentNode()) {
668         if (root && !n->isContentEditable())
669             continue;
670         if (n->hasTagName(tagName))
671             return n;
672         if (n == root)
673             return 0;
674     }
675     
676     return 0;
677 }
678
679 Node* enclosingNodeOfType(const Position& p, bool (*nodeIsOfType)(const Node*), bool onlyReturnEditableNodes)
680 {
681     if (p.isNull())
682         return 0;
683         
684     Node* root = highestEditableRoot(p);
685     for (Node* n = p.node(); n; n = n->parentNode()) {
686         // Don't return a non-editable node if the input position was editable, since
687         // the callers from editing will no doubt want to perform editing inside the returned node.
688         if (root && !n->isContentEditable() && onlyReturnEditableNodes)
689             continue;
690         if ((*nodeIsOfType)(n))
691             return n;
692         if (n == root)
693             return 0;
694     }
695     
696     return 0;
697 }
698
699 Node* highestEnclosingNodeOfType(const Position& p, bool (*nodeIsOfType)(const Node*))
700 {
701     Node* highest = 0;
702     Node* root = highestEditableRoot(p);
703     for (Node* n = p.node(); n; n = n->parentNode()) {
704         if ((*nodeIsOfType)(n))
705             highest = n;
706         if (n == root)
707             break;
708     }
709     
710     return highest;
711 }
712
713 Node* enclosingTableCell(const Position& p)
714 {
715     return static_cast<Element*>(enclosingNodeOfType(p, isTableCell));
716 }
717
718 Node* enclosingAnchorElement(const Position& p)
719 {
720     if (p.isNull())
721         return 0;
722     
723     Node* node = p.node();
724     while (node && !(node->isElementNode() && node->isLink()))
725         node = node->parentNode();
726     return node;
727 }
728
729 HTMLElement* enclosingList(Node* node)
730 {
731     if (!node)
732         return 0;
733         
734     Node* root = highestEditableRoot(Position(node, 0));
735     
736     for (Node* n = node->parentNode(); n; n = n->parentNode()) {
737         if (n->hasTagName(ulTag) || n->hasTagName(olTag))
738             return static_cast<HTMLElement*>(n);
739         if (n == root)
740             return 0;
741     }
742     
743     return 0;
744 }
745
746 HTMLElement* enclosingListChild(Node *node)
747 {
748     if (!node)
749         return 0;
750     // Check for a list item element, or for a node whose parent is a list element.  Such a node
751     // will appear visually as a list item (but without a list marker)
752     Node* root = highestEditableRoot(Position(node, 0));
753     
754     // FIXME: This function is inappropriately named if it starts with node instead of node->parentNode()
755     for (Node* n = node; n && n->parentNode(); n = n->parentNode()) {
756         if (n->hasTagName(liTag) || isListElement(n->parentNode()))
757             return static_cast<HTMLElement*>(n);
758         if (n == root || isTableCell(n))
759             return 0;
760     }
761     
762     return 0;
763 }
764
765 static HTMLElement* embeddedSublist(Node* listItem)
766 {
767     // Check the DOM so that we'll find collapsed sublists without renderers.
768     for (Node* n = listItem->firstChild(); n; n = n->nextSibling()) {
769         if (isListElement(n))
770             return static_cast<HTMLElement*>(n);
771     }
772     
773     return 0;
774 }
775
776 static Node* appendedSublist(Node* listItem)
777 {
778     // Check the DOM so that we'll find collapsed sublists without renderers.
779     for (Node* n = listItem->nextSibling(); n; n = n->nextSibling()) {
780         if (isListElement(n))
781             return static_cast<HTMLElement*>(n);
782         if (n->renderer() && n->renderer()->isListItem())
783             return 0;
784     }
785     
786     return 0;
787 }
788
789 // FIXME: This method should not need to call isStartOfParagraph/isEndOfParagraph
790 Node* enclosingEmptyListItem(const VisiblePosition& visiblePos)
791 {
792     // Check that position is on a line by itself inside a list item
793     Node* listChildNode = enclosingListChild(visiblePos.deepEquivalent().node());
794     if (!listChildNode || !isStartOfParagraph(visiblePos) || !isEndOfParagraph(visiblePos))
795         return 0;
796
797     VisiblePosition firstInListChild(firstDeepEditingPositionForNode(listChildNode));
798     VisiblePosition lastInListChild(lastDeepEditingPositionForNode(listChildNode));
799
800     if (firstInListChild != visiblePos || lastInListChild != visiblePos)
801         return 0;
802     
803     if (embeddedSublist(listChildNode) || appendedSublist(listChildNode))
804         return 0;
805         
806     return listChildNode;
807 }
808
809 HTMLElement* outermostEnclosingList(Node* node)
810 {
811     HTMLElement* list = enclosingList(node);
812     if (!list)
813         return 0;
814     while (HTMLElement* nextList = enclosingList(list))
815         list = nextList;
816     return list;
817 }
818
819 bool canMergeLists(Element* firstList, Element* secondList)
820 {
821     if (!firstList || !secondList)
822         return false;
823
824     return firstList->hasTagName(secondList->tagQName())// make sure the list types match (ol vs. ul)
825     && firstList->isContentEditable() && secondList->isContentEditable()// both lists are editable
826     && firstList->rootEditableElement() == secondList->rootEditableElement()// don't cross editing boundaries
827     && isVisiblyAdjacent(positionAfterNode(firstList), positionBeforeNode(secondList));
828     // Make sure there is no visible content between this li and the previous list
829 }
830
831 Node* highestAncestor(Node* node)
832 {
833     ASSERT(node);
834     Node* parent = node;
835     while ((node = node->parentNode()))
836         parent = node;
837     return parent;
838 }
839
840 // FIXME: do not require renderer, so that this can be used within fragments, or rename to isRenderedTable()
841 bool isTableElement(Node* n)
842 {
843     if (!n || !n->isElementNode())
844         return false;
845
846     RenderObject* renderer = n->renderer();
847     return (renderer && (renderer->style()->display() == TABLE || renderer->style()->display() == INLINE_TABLE));
848 }
849
850 bool isTableCell(const Node* node)
851 {
852     RenderObject* r = node->renderer();
853     if (!r)
854         return node->hasTagName(tdTag) || node->hasTagName(thTag);
855     
856     return r->isTableCell();
857 }
858
859 PassRefPtr<HTMLElement> createDefaultParagraphElement(Document* document)
860 {
861     return new HTMLDivElement(divTag, document);
862 }
863
864 PassRefPtr<HTMLElement> createBreakElement(Document* document)
865 {
866     return new HTMLBRElement(brTag, document);
867 }
868
869 PassRefPtr<HTMLElement> createOrderedListElement(Document* document)
870 {
871     return new HTMLOListElement(olTag, document);
872 }
873
874 PassRefPtr<HTMLElement> createUnorderedListElement(Document* document)
875 {
876     return new HTMLUListElement(ulTag, document);
877 }
878
879 PassRefPtr<HTMLElement> createListItemElement(Document* document)
880 {
881     return new HTMLLIElement(liTag, document);
882 }
883
884 PassRefPtr<HTMLElement> createHTMLElement(Document* document, const QualifiedName& name)
885 {
886     return HTMLElementFactory::createHTMLElement(name, document, 0, false);
887 }
888
889 PassRefPtr<HTMLElement> createHTMLElement(Document* document, const AtomicString& tagName)
890 {
891     return createHTMLElement(document, QualifiedName(nullAtom, tagName, xhtmlNamespaceURI));
892 }
893
894 bool isTabSpanNode(const Node *node)
895 {
896     return node && node->hasTagName(spanTag) && node->isElementNode() && static_cast<const Element *>(node)->getAttribute(classAttr) == AppleTabSpanClass;
897 }
898
899 bool isTabSpanTextNode(const Node *node)
900 {
901     return node && node->isTextNode() && node->parentNode() && isTabSpanNode(node->parentNode());
902 }
903
904 Node *tabSpanNode(const Node *node)
905 {
906     return isTabSpanTextNode(node) ? node->parentNode() : 0;
907 }
908
909 Position positionBeforeTabSpan(const Position& pos)
910 {
911     Node *node = pos.node();
912     if (isTabSpanTextNode(node))
913         node = tabSpanNode(node);
914     else if (!isTabSpanNode(node))
915         return pos;
916     
917     return positionBeforeNode(node);
918 }
919
920 PassRefPtr<Element> createTabSpanElement(Document* document, PassRefPtr<Node> tabTextNode)
921 {
922     // Make the span to hold the tab.
923     RefPtr<Element> spanElement = document->createElement(spanTag, false);
924     spanElement->setAttribute(classAttr, AppleTabSpanClass);
925     spanElement->setAttribute(styleAttr, "white-space:pre");
926
927     // Add tab text to that span.
928     if (!tabTextNode)
929         tabTextNode = document->createEditingTextNode("\t");
930
931     ExceptionCode ec = 0;
932     spanElement->appendChild(tabTextNode, ec);
933     ASSERT(ec == 0);
934
935     return spanElement.release();
936 }
937
938 PassRefPtr<Element> createTabSpanElement(Document* document, const String& tabText)
939 {
940     return createTabSpanElement(document, document->createTextNode(tabText));
941 }
942
943 PassRefPtr<Element> createTabSpanElement(Document* document)
944 {
945     return createTabSpanElement(document, PassRefPtr<Node>());
946 }
947
948 bool isNodeRendered(const Node *node)
949 {
950     if (!node)
951         return false;
952
953     RenderObject *renderer = node->renderer();
954     if (!renderer)
955         return false;
956
957     return renderer->style()->visibility() == VISIBLE;
958 }
959
960 Node *nearestMailBlockquote(const Node *node)
961 {
962     for (Node *n = const_cast<Node *>(node); n; n = n->parentNode()) {
963         if (isMailBlockquote(n))
964             return n;
965     }
966     return 0;
967 }
968
969 unsigned numEnclosingMailBlockquotes(const Position& p)
970 {
971     unsigned num = 0;
972     for (Node* n = p.node(); n; n = n->parentNode())
973         if (isMailBlockquote(n))
974             num++;
975     
976     return num;
977 }
978
979 bool isMailBlockquote(const Node *node)
980 {
981     if (!node || (!node->isElementNode() && !node->hasTagName(blockquoteTag)))
982         return false;
983         
984     return static_cast<const Element *>(node)->getAttribute("type") == "cite";
985 }
986
987 int caretMinOffset(const Node* n)
988 {
989     RenderObject* r = n->renderer();
990     ASSERT(!n->isCharacterDataNode() || !r || r->isText()); // FIXME: This was a runtime check that seemingly couldn't fail; changed it to an assertion for now.
991     return r ? r->caretMinOffset() : 0;
992 }
993
994 // If a node can contain candidates for VisiblePositions, return the offset of the last candidate, otherwise 
995 // return the number of children for container nodes and the length for unrendered text nodes.
996 int caretMaxOffset(const Node* n)
997 {
998     // For rendered text nodes, return the last position that a caret could occupy.
999     if (n->isTextNode() && n->renderer())
1000         return n->renderer()->caretMaxOffset();
1001     // For containers return the number of children.  For others do the same as above.
1002     return lastOffsetForEditing(n);
1003 }
1004
1005 bool lineBreakExistsAtVisiblePosition(const VisiblePosition& visiblePosition)
1006 {
1007     return lineBreakExistsAtPosition(visiblePosition.deepEquivalent().downstream());
1008 }
1009
1010 bool lineBreakExistsAtPosition(const Position& position)
1011 {
1012     if (position.isNull())
1013         return false;
1014     
1015     if (position.anchorNode()->hasTagName(brTag) && position.atFirstEditingPositionForNode())
1016         return true;
1017     
1018     if (!position.anchorNode()->isTextNode() || !position.anchorNode()->renderer()->style()->preserveNewline())
1019         return false;
1020     
1021     Text* textNode = static_cast<Text*>(position.anchorNode());
1022     unsigned offset = position.offsetInContainerNode();
1023     return offset < textNode->length() && textNode->data()[offset] == '\n';
1024 }
1025
1026 // Modifies selections that have an end point at the edge of a table
1027 // that contains the other endpoint so that they don't confuse
1028 // code that iterates over selected paragraphs.
1029 VisibleSelection selectionForParagraphIteration(const VisibleSelection& original)
1030 {
1031     VisibleSelection newSelection(original);
1032     VisiblePosition startOfSelection(newSelection.visibleStart());
1033     VisiblePosition endOfSelection(newSelection.visibleEnd());
1034     
1035     // If the end of the selection to modify is just after a table, and
1036     // if the start of the selection is inside that table, then the last paragraph
1037     // that we'll want modify is the last one inside the table, not the table itself
1038     // (a table is itself a paragraph).
1039     if (Node* table = isFirstPositionAfterTable(endOfSelection))
1040         if (startOfSelection.deepEquivalent().node()->isDescendantOf(table))
1041             newSelection = VisibleSelection(startOfSelection, endOfSelection.previous(true));
1042     
1043     // If the start of the selection to modify is just before a table,
1044     // and if the end of the selection is inside that table, then the first paragraph
1045     // we'll want to modify is the first one inside the table, not the paragraph
1046     // containing the table itself.
1047     if (Node* table = isLastPositionBeforeTable(startOfSelection))
1048         if (endOfSelection.deepEquivalent().node()->isDescendantOf(table))
1049             newSelection = VisibleSelection(startOfSelection.next(true), endOfSelection);
1050     
1051     return newSelection;
1052 }
1053
1054
1055 int indexForVisiblePosition(const VisiblePosition& visiblePosition)
1056 {
1057     if (visiblePosition.isNull())
1058         return 0;
1059     Position p(visiblePosition.deepEquivalent());
1060     RefPtr<Range> range = Range::create(p.node()->document(), Position(p.node()->document(), 0), rangeCompliantEquivalent(p));
1061     return TextIterator::rangeLength(range.get(), true);
1062 }
1063
1064 // Determines whether two positions are visibly next to each other (first then second)
1065 // while ignoring whitespaces and unrendered nodes
1066 bool isVisiblyAdjacent(const Position& first, const Position& second)
1067 {
1068     return VisiblePosition(first) == VisiblePosition(second.upstream());
1069 }
1070
1071 // Determines whether a node is inside a range or visibly starts and ends at the boundaries of the range.
1072 // Call this function to determine whether a node is visibly fit inside selectedRange
1073 bool isNodeVisiblyContainedWithin(Node* node, const Range* selectedRange)
1074 {
1075     ASSERT(node);
1076     ASSERT(selectedRange);
1077     // If the node is inside the range, then it surely is contained within
1078     ExceptionCode ec = 0;
1079     if (selectedRange->compareNode(node, ec) == Range::NODE_INSIDE)
1080         return true;
1081
1082     // If the node starts and ends at where selectedRange starts and ends, the node is contained within
1083     return visiblePositionBeforeNode(node) == selectedRange->startPosition()
1084         && visiblePositionAfterNode(node) == selectedRange->endPosition();
1085 }
1086
1087 PassRefPtr<Range> avoidIntersectionWithNode(const Range* range, Node* node)
1088 {
1089     if (!range)
1090         return 0;
1091
1092     Document* document = range->ownerDocument();
1093
1094     Node* startContainer = range->startContainer();
1095     int startOffset = range->startOffset();
1096     Node* endContainer = range->endContainer();
1097     int endOffset = range->endOffset();
1098
1099     if (!startContainer)
1100         return 0;
1101
1102     ASSERT(endContainer);
1103
1104     if (startContainer == node || startContainer->isDescendantOf(node)) {
1105         ASSERT(node->parentNode());
1106         startContainer = node->parentNode();
1107         startOffset = node->nodeIndex();
1108     }
1109     if (endContainer == node || endContainer->isDescendantOf(node)) {
1110         ASSERT(node->parentNode());
1111         endContainer = node->parentNode();
1112         endOffset = node->nodeIndex();
1113     }
1114
1115     return Range::create(document, startContainer, startOffset, endContainer, endOffset);
1116 }
1117
1118 VisibleSelection avoidIntersectionWithNode(const VisibleSelection& selection, Node* node)
1119 {
1120     if (selection.isNone())
1121         return VisibleSelection(selection);
1122         
1123     VisibleSelection updatedSelection(selection);
1124     Node* base = selection.base().node();
1125     Node* extent = selection.extent().node();
1126     ASSERT(base);
1127     ASSERT(extent);
1128     
1129     if (base == node || base->isDescendantOf(node)) {
1130         ASSERT(node->parentNode());
1131         updatedSelection.setBase(Position(node->parentNode(), node->nodeIndex()));
1132     }
1133     
1134     if (extent == node || extent->isDescendantOf(node)) {
1135         ASSERT(node->parentNode());
1136         updatedSelection.setExtent(Position(node->parentNode(), node->nodeIndex()));
1137     }
1138         
1139     return updatedSelection;
1140 }
1141
1142 } // namespace WebCore