2011-01-29 Patrick Gansterer <paroga@webkit.org>
[WebKit-https.git] / Source / 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 "Document.h"
30 #include "EditingText.h"
31 #include "HTMLBRElement.h"
32 #include "HTMLDivElement.h"
33 #include "HTMLElementFactory.h"
34 #include "HTMLInterchange.h"
35 #include "HTMLLIElement.h"
36 #include "HTMLNames.h"
37 #include "HTMLOListElement.h"
38 #include "HTMLUListElement.h"
39 #include "PositionIterator.h"
40 #include "RenderObject.h"
41 #include "Range.h"
42 #include "VisibleSelection.h"
43 #include "Text.h"
44 #include "TextIterator.h"
45 #include "VisiblePosition.h"
46 #include "visible_units.h"
47 #include <wtf/StdLibExtras.h>
48 #include <wtf/unicode/CharacterNames.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 isAtUnsplittableElement(const Position& pos)
187 {
188     Node* node = pos.node();
189     return (node == editableRootForPosition(pos) || node == enclosingNodeOfType(pos, &isTableCell));
190 }
191     
192     
193 bool 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
205 Element* 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.
220 Element* 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
231 Position 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
242 Position 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
254 Position 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
265 Position 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
277 VisiblePosition 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
298 VisiblePosition 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.
321 bool 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.
330 Node* enclosingBlock(Node* node)
331 {
332     return static_cast<Element*>(enclosingNodeOfType(firstPositionInOrBeforeNode(node), isBlock));
333 }
334
335 // This method is used to create positions in the DOM. It returns the maximum valid offset
336 // in a node.  It returns 1 for some elements even though they do not have children, which
337 // creates technically invalid DOM Positions.  Be sure to call parentAnchoredEquivalent
338 // on a Position before using it to create a DOM Range, or an exception will be thrown.
339 int lastOffsetForEditing(const Node* node)
340 {
341     ASSERT(node);
342     if (!node)
343         return 0;
344     if (node->offsetInCharacters())
345         return node->maxCharacterOffset();
346
347     if (node->hasChildNodes())
348         return node->childNodeCount();
349
350     // NOTE: This should preempt the childNodeCount for, e.g., select nodes
351     if (editingIgnoresContent(node))
352         return 1;
353
354     return 0;
355 }
356
357 String stringWithRebalancedWhitespace(const String& string, bool startIsStartOfParagraph, bool endIsEndOfParagraph)
358 {
359     Vector<UChar> rebalancedString;
360     append(rebalancedString, string);
361
362     bool previousCharacterWasSpace = false;
363     for (size_t i = 0; i < rebalancedString.size(); i++) {
364         if (!isWhitespace(rebalancedString[i])) {
365             previousCharacterWasSpace = false;
366             continue;
367         }
368
369         if (previousCharacterWasSpace || (!i && startIsStartOfParagraph) || (i + 1 == rebalancedString.size() && endIsEndOfParagraph)) {
370             rebalancedString[i] = noBreakSpace;
371             previousCharacterWasSpace = false;
372         } else {
373             rebalancedString[i] = ' ';
374             previousCharacterWasSpace = true;
375         }
376             
377     }
378
379     return String::adopt(rebalancedString);
380 }
381
382 bool isTableStructureNode(const Node *node)
383 {
384     RenderObject *r = node->renderer();
385     return (r && (r->isTableCell() || r->isTableRow() || r->isTableSection() || r->isTableCol()));
386 }
387
388 const String& nonBreakingSpaceString()
389 {
390     DEFINE_STATIC_LOCAL(String, nonBreakingSpaceString, (&noBreakSpace, 1));
391     return nonBreakingSpaceString;
392 }
393
394 // FIXME: need to dump this
395 bool isSpecialElement(const Node *n)
396 {
397     if (!n)
398         return false;
399         
400     if (!n->isHTMLElement())
401         return false;
402
403     if (n->isLink())
404         return true;
405
406     RenderObject *renderer = n->renderer();
407     if (!renderer)
408         return false;
409         
410     if (renderer->style()->display() == TABLE || renderer->style()->display() == INLINE_TABLE)
411         return true;
412
413     if (renderer->style()->isFloating())
414         return true;
415
416     if (renderer->style()->position() != StaticPosition)
417         return true;
418         
419     return false;
420 }
421
422 static Node* firstInSpecialElement(const Position& pos)
423 {
424     // FIXME: This begins at pos.node(), which doesn't necessarily contain pos (suppose pos was [img, 0]).  See <rdar://problem/5027702>.
425     Node* rootEditableElement = pos.node()->rootEditableElement();
426     for (Node* n = pos.node(); n && n->rootEditableElement() == rootEditableElement; n = n->parentNode())
427         if (isSpecialElement(n)) {
428             VisiblePosition vPos = VisiblePosition(pos, DOWNSTREAM);
429             VisiblePosition firstInElement = VisiblePosition(n, 0, DOWNSTREAM);
430             if (isTableElement(n) && vPos == firstInElement.next())
431                 return n;
432             if (vPos == firstInElement)
433                 return n;
434         }
435     return 0;
436 }
437
438 static Node* lastInSpecialElement(const Position& pos)
439 {
440     // FIXME: This begins at pos.node(), which doesn't necessarily contain pos (suppose pos was [img, 0]).  See <rdar://problem/5027702>.
441     Node* rootEditableElement = pos.node()->rootEditableElement();
442     for (Node* n = pos.node(); n && n->rootEditableElement() == rootEditableElement; n = n->parentNode())
443         if (isSpecialElement(n)) {
444             VisiblePosition vPos = VisiblePosition(pos, DOWNSTREAM);
445             VisiblePosition lastInElement = VisiblePosition(n, n->childNodeCount(), DOWNSTREAM);
446             if (isTableElement(n) && vPos == lastInElement.previous())
447                 return n;
448             if (vPos == lastInElement)
449                 return n;
450         }
451     return 0;
452 }
453
454 bool isFirstVisiblePositionInSpecialElement(const Position& pos)
455 {
456     return firstInSpecialElement(pos);
457 }
458
459 Position positionBeforeContainingSpecialElement(const Position& pos, Node** containingSpecialElement)
460 {
461     Node* n = firstInSpecialElement(pos);
462     if (!n)
463         return pos;
464     Position result = positionInParentBeforeNode(n);
465     if (result.isNull() || result.node()->rootEditableElement() != pos.node()->rootEditableElement())
466         return pos;
467     if (containingSpecialElement)
468         *containingSpecialElement = n;
469     return result;
470 }
471
472 bool isLastVisiblePositionInSpecialElement(const Position& pos)
473 {
474     return lastInSpecialElement(pos);
475 }
476
477 Position positionAfterContainingSpecialElement(const Position& pos, Node **containingSpecialElement)
478 {
479     Node* n = lastInSpecialElement(pos);
480     if (!n)
481         return pos;
482     Position result = positionInParentAfterNode(n);
483     if (result.isNull() || result.node()->rootEditableElement() != pos.node()->rootEditableElement())
484         return pos;
485     if (containingSpecialElement)
486         *containingSpecialElement = n;
487     return result;
488 }
489
490 Position positionOutsideContainingSpecialElement(const Position &pos, Node **containingSpecialElement)
491 {
492     if (isFirstVisiblePositionInSpecialElement(pos))
493         return positionBeforeContainingSpecialElement(pos, containingSpecialElement);
494     if (isLastVisiblePositionInSpecialElement(pos))
495         return positionAfterContainingSpecialElement(pos, containingSpecialElement);
496     return pos;
497 }
498
499 Node* isFirstPositionAfterTable(const VisiblePosition& visiblePosition)
500 {
501     Position upstream(visiblePosition.deepEquivalent().upstream());
502     if (upstream.node() && upstream.node()->renderer() && upstream.node()->renderer()->isTable() && upstream.atLastEditingPositionForNode())
503         return upstream.node();
504     
505     return 0;
506 }
507
508 Node* isLastPositionBeforeTable(const VisiblePosition& visiblePosition)
509 {
510     Position downstream(visiblePosition.deepEquivalent().downstream());
511     if (downstream.node() && downstream.node()->renderer() && downstream.node()->renderer()->isTable() && downstream.atFirstEditingPositionForNode())
512         return downstream.node();
513     
514     return 0;
515 }
516
517 // Returns the visible position at the beginning of a node
518 VisiblePosition visiblePositionBeforeNode(Node* node)
519 {
520     ASSERT(node);
521     if (node->childNodeCount())
522         return VisiblePosition(node, 0, DOWNSTREAM);
523     ASSERT(node->parentNode());
524     return positionInParentBeforeNode(node);
525 }
526
527 // Returns the visible position at the ending of a node
528 VisiblePosition visiblePositionAfterNode(Node* node)
529 {
530     ASSERT(node);
531     if (node->childNodeCount())
532         return VisiblePosition(node, node->childNodeCount(), DOWNSTREAM);
533     ASSERT(node->parentNode());
534     return positionInParentAfterNode(node);
535 }
536
537 // Create a range object with two visible positions, start and end.
538 // create(PassRefPtr<Document>, const Position&, const Position&); will use deprecatedEditingOffset
539 // Use this function instead of create a regular range object (avoiding editing offset).
540 PassRefPtr<Range> createRange(PassRefPtr<Document> document, const VisiblePosition& start, const VisiblePosition& end, ExceptionCode& ec)
541 {
542     ec = 0;
543     RefPtr<Range> selectedRange = Range::create(document);
544     selectedRange->setStart(start.deepEquivalent().containerNode(), start.deepEquivalent().computeOffsetInContainerNode(), ec);
545     if (!ec)
546         selectedRange->setEnd(end.deepEquivalent().containerNode(), end.deepEquivalent().computeOffsetInContainerNode(), ec);
547     return selectedRange.release();
548 }
549
550 // Extend rangeToExtend to include nodes that wraps range and visibly starts and ends inside or at the boudnaries of maximumRange
551 // e.g. if the original range spaned "hello" in <div>hello</div>, then this function extends the range to contain div's around it.
552 // Call this function before copying / moving paragraphs to contain all wrapping nodes.
553 // This function stops extending the range immediately below rootNode; i.e. the extended range can contain a child node of rootNode
554 // but it can never contain rootNode itself.
555 PassRefPtr<Range> extendRangeToWrappingNodes(PassRefPtr<Range> range, const Range* maximumRange, const Node* rootNode)
556 {
557     ASSERT(range);
558     ASSERT(maximumRange);
559
560     ExceptionCode ec = 0;
561     Node* ancestor = range->commonAncestorContainer(ec);// find the cloeset common ancestor
562     Node* highestNode = 0;
563     // traverse through ancestors as long as they are contained within the range, content-editable, and below rootNode (could be =0).
564     while (ancestor && ancestor->isContentEditable() && isNodeVisiblyContainedWithin(ancestor, maximumRange) && ancestor != rootNode) {
565         highestNode = ancestor;
566         ancestor = ancestor->parentNode();
567     }
568
569     if (!highestNode)
570         return range;
571
572     // Create new range with the highest editable node contained within the range
573     RefPtr<Range> extendedRange = Range::create(range->ownerDocument());
574     extendedRange->selectNode(highestNode, ec);
575     return extendedRange.release();
576 }
577
578 bool isListElement(Node *n)
579 {
580     return (n && (n->hasTagName(ulTag) || n->hasTagName(olTag) || n->hasTagName(dlTag)));
581 }
582
583 bool isListItem(Node *n)
584 {
585     return n && n->renderer() && n->renderer()->isListItem();
586 }
587
588 Node* enclosingNodeWithTag(const Position& p, const QualifiedName& tagName)
589 {
590     if (p.isNull())
591         return 0;
592         
593     Node* root = highestEditableRoot(p);
594     for (Node* n = p.node(); n; n = n->parentNode()) {
595         if (root && !n->isContentEditable())
596             continue;
597         if (n->hasTagName(tagName))
598             return n;
599         if (n == root)
600             return 0;
601     }
602     
603     return 0;
604 }
605
606 Node* enclosingNodeOfType(const Position& p, bool (*nodeIsOfType)(const Node*), bool onlyReturnEditableNodes)
607 {
608     if (p.isNull())
609         return 0;
610         
611     Node* root = highestEditableRoot(p);
612     for (Node* n = p.node(); n; n = n->parentNode()) {
613         // Don't return a non-editable node if the input position was editable, since
614         // the callers from editing will no doubt want to perform editing inside the returned node.
615         if (root && !n->isContentEditable() && onlyReturnEditableNodes)
616             continue;
617         if ((*nodeIsOfType)(n))
618             return n;
619         if (n == root)
620             return 0;
621     }
622     
623     return 0;
624 }
625
626 Node* highestEnclosingNodeOfType(const Position& p, bool (*nodeIsOfType)(const Node*))
627 {
628     Node* highest = 0;
629     Node* root = highestEditableRoot(p);
630     for (Node* n = p.node(); n; n = n->parentNode()) {
631         if ((*nodeIsOfType)(n))
632             highest = n;
633         if (n == root)
634             break;
635     }
636     
637     return highest;
638 }
639
640 Node* enclosingTableCell(const Position& p)
641 {
642     return static_cast<Element*>(enclosingNodeOfType(p, isTableCell));
643 }
644
645 Node* enclosingAnchorElement(const Position& p)
646 {
647     if (p.isNull())
648         return 0;
649     
650     Node* node = p.node();
651     while (node && !(node->isElementNode() && node->isLink()))
652         node = node->parentNode();
653     return node;
654 }
655
656 HTMLElement* enclosingList(Node* node)
657 {
658     if (!node)
659         return 0;
660         
661     Node* root = highestEditableRoot(firstPositionInOrBeforeNode(node));
662     
663     for (ContainerNode* n = node->parentNode(); n; n = n->parentNode()) {
664         if (n->hasTagName(ulTag) || n->hasTagName(olTag))
665             return static_cast<HTMLElement*>(n);
666         if (n == root)
667             return 0;
668     }
669     
670     return 0;
671 }
672
673 HTMLElement* enclosingListChild(Node *node)
674 {
675     if (!node)
676         return 0;
677     // Check for a list item element, or for a node whose parent is a list element.  Such a node
678     // will appear visually as a list item (but without a list marker)
679     Node* root = highestEditableRoot(firstPositionInOrBeforeNode(node));
680     
681     // FIXME: This function is inappropriately named if it starts with node instead of node->parentNode()
682     for (Node* n = node; n && n->parentNode(); n = n->parentNode()) {
683         if (n->hasTagName(liTag) || isListElement(n->parentNode()))
684             return static_cast<HTMLElement*>(n);
685         if (n == root || isTableCell(n))
686             return 0;
687     }
688     
689     return 0;
690 }
691
692 static HTMLElement* embeddedSublist(Node* listItem)
693 {
694     // Check the DOM so that we'll find collapsed sublists without renderers.
695     for (Node* n = listItem->firstChild(); n; n = n->nextSibling()) {
696         if (isListElement(n))
697             return static_cast<HTMLElement*>(n);
698     }
699     
700     return 0;
701 }
702
703 static Node* appendedSublist(Node* listItem)
704 {
705     // Check the DOM so that we'll find collapsed sublists without renderers.
706     for (Node* n = listItem->nextSibling(); n; n = n->nextSibling()) {
707         if (isListElement(n))
708             return static_cast<HTMLElement*>(n);
709         if (isListItem(listItem))
710             return 0;
711     }
712     
713     return 0;
714 }
715
716 // FIXME: This method should not need to call isStartOfParagraph/isEndOfParagraph
717 Node* enclosingEmptyListItem(const VisiblePosition& visiblePos)
718 {
719     // Check that position is on a line by itself inside a list item
720     Node* listChildNode = enclosingListChild(visiblePos.deepEquivalent().node());
721     if (!listChildNode || !isStartOfParagraph(visiblePos) || !isEndOfParagraph(visiblePos))
722         return 0;
723
724     VisiblePosition firstInListChild(firstDeepEditingPositionForNode(listChildNode));
725     VisiblePosition lastInListChild(lastDeepEditingPositionForNode(listChildNode));
726
727     if (firstInListChild != visiblePos || lastInListChild != visiblePos)
728         return 0;
729     
730     if (embeddedSublist(listChildNode) || appendedSublist(listChildNode))
731         return 0;
732         
733     return listChildNode;
734 }
735
736 HTMLElement* outermostEnclosingList(Node* node, Node* rootList)
737 {
738     HTMLElement* list = enclosingList(node);
739     if (!list)
740         return 0;
741
742     while (HTMLElement* nextList = enclosingList(list)) {
743         if (nextList == rootList)
744             break;
745         list = nextList;
746     }
747
748     return list;
749 }
750
751 bool canMergeLists(Element* firstList, Element* secondList)
752 {
753     if (!firstList || !secondList || !firstList->isHTMLElement() || !secondList->isHTMLElement())
754         return false;
755
756     return firstList->hasTagName(secondList->tagQName())// make sure the list types match (ol vs. ul)
757     && firstList->isContentEditable() && secondList->isContentEditable()// both lists are editable
758     && firstList->rootEditableElement() == secondList->rootEditableElement()// don't cross editing boundaries
759     && isVisiblyAdjacent(positionInParentAfterNode(firstList), positionInParentBeforeNode(secondList));
760     // Make sure there is no visible content between this li and the previous list
761 }
762
763 Node* highestAncestor(Node* node)
764 {
765     ASSERT(node);
766     Node* parent = node;
767     while ((node = node->parentNode()))
768         parent = node;
769     return parent;
770 }
771
772 // FIXME: do not require renderer, so that this can be used within fragments, or rename to isRenderedTable()
773 bool isTableElement(Node* n)
774 {
775     if (!n || !n->isElementNode())
776         return false;
777
778     RenderObject* renderer = n->renderer();
779     return (renderer && (renderer->style()->display() == TABLE || renderer->style()->display() == INLINE_TABLE));
780 }
781
782 bool isTableCell(const Node* node)
783 {
784     RenderObject* r = node->renderer();
785     if (!r)
786         return node->hasTagName(tdTag) || node->hasTagName(thTag);
787     
788     return r->isTableCell();
789 }
790
791 bool isEmptyTableCell(const Node* node)
792 {
793     // Returns true IFF the passed in node is one of:
794     //   .) a table cell with no children,
795     //   .) a table cell with a single BR child, and which has no other child renderers, including :before and :after renderers
796     //   .) the BR child of such a table cell
797
798     // Find rendered node
799     while (node && !node->renderer())
800         node = node->parentNode();
801     if (!node)
802         return false;
803
804     // Make sure the rendered node is a table cell or <br>.
805     // If it's a <br>, then the parent node has to be a table cell.
806     RenderObject* renderer = node->renderer();
807     if (renderer->isBR()) {
808         renderer = renderer->parent();
809         if (!renderer)
810             return false;
811     }
812     if (!renderer->isTableCell())
813         return false;
814
815     // Check that the table cell contains no child renderers except for perhaps a single <br>.
816     RenderObject* childRenderer = renderer->firstChild();
817     if (!childRenderer)
818         return true;
819     if (!childRenderer->isBR())
820         return false;
821     return !childRenderer->nextSibling();
822 }
823
824 PassRefPtr<HTMLElement> createDefaultParagraphElement(Document* document)
825 {
826     return HTMLDivElement::create(document);
827 }
828
829 PassRefPtr<HTMLElement> createBreakElement(Document* document)
830 {
831     return HTMLBRElement::create(document);
832 }
833
834 PassRefPtr<HTMLElement> createOrderedListElement(Document* document)
835 {
836     return HTMLOListElement::create(document);
837 }
838
839 PassRefPtr<HTMLElement> createUnorderedListElement(Document* document)
840 {
841     return HTMLUListElement::create(document);
842 }
843
844 PassRefPtr<HTMLElement> createListItemElement(Document* document)
845 {
846     return HTMLLIElement::create(document);
847 }
848
849 PassRefPtr<HTMLElement> createHTMLElement(Document* document, const QualifiedName& name)
850 {
851     return HTMLElementFactory::createHTMLElement(name, document, 0, false);
852 }
853
854 PassRefPtr<HTMLElement> createHTMLElement(Document* document, const AtomicString& tagName)
855 {
856     return createHTMLElement(document, QualifiedName(nullAtom, tagName, xhtmlNamespaceURI));
857 }
858
859 bool isTabSpanNode(const Node *node)
860 {
861     return node && node->hasTagName(spanTag) && node->isElementNode() && static_cast<const Element *>(node)->getAttribute(classAttr) == AppleTabSpanClass;
862 }
863
864 bool isTabSpanTextNode(const Node *node)
865 {
866     return node && node->isTextNode() && node->parentNode() && isTabSpanNode(node->parentNode());
867 }
868
869 Node *tabSpanNode(const Node *node)
870 {
871     return isTabSpanTextNode(node) ? node->parentNode() : 0;
872 }
873
874 bool isNodeInTextFormControl(Node* node)
875 {
876     if (!node)
877         return false;
878     Node* ancestor = node->shadowAncestorNode();
879     if (ancestor == node)
880         return false;
881     return ancestor->isElementNode() && static_cast<Element*>(ancestor)->isTextFormControl();
882 }
883     
884 Position positionBeforeTabSpan(const Position& pos)
885 {
886     Node *node = pos.node();
887     if (isTabSpanTextNode(node))
888         node = tabSpanNode(node);
889     else if (!isTabSpanNode(node))
890         return pos;
891     
892     return positionInParentBeforeNode(node);
893 }
894
895 PassRefPtr<Element> createTabSpanElement(Document* document, PassRefPtr<Node> tabTextNode)
896 {
897     // Make the span to hold the tab.
898     RefPtr<Element> spanElement = document->createElement(spanTag, false);
899     spanElement->setAttribute(classAttr, AppleTabSpanClass);
900     spanElement->setAttribute(styleAttr, "white-space:pre");
901
902     // Add tab text to that span.
903     if (!tabTextNode)
904         tabTextNode = document->createEditingTextNode("\t");
905
906     ExceptionCode ec = 0;
907     spanElement->appendChild(tabTextNode, ec);
908     ASSERT(ec == 0);
909
910     return spanElement.release();
911 }
912
913 PassRefPtr<Element> createTabSpanElement(Document* document, const String& tabText)
914 {
915     return createTabSpanElement(document, document->createTextNode(tabText));
916 }
917
918 PassRefPtr<Element> createTabSpanElement(Document* document)
919 {
920     return createTabSpanElement(document, PassRefPtr<Node>());
921 }
922
923 bool isNodeRendered(const Node *node)
924 {
925     if (!node)
926         return false;
927
928     RenderObject *renderer = node->renderer();
929     if (!renderer)
930         return false;
931
932     return renderer->style()->visibility() == VISIBLE;
933 }
934
935 Node *nearestMailBlockquote(const Node *node)
936 {
937     for (Node *n = const_cast<Node *>(node); n; n = n->parentNode()) {
938         if (isMailBlockquote(n))
939             return n;
940     }
941     return 0;
942 }
943
944 unsigned numEnclosingMailBlockquotes(const Position& p)
945 {
946     unsigned num = 0;
947     for (Node* n = p.node(); n; n = n->parentNode())
948         if (isMailBlockquote(n))
949             num++;
950     
951     return num;
952 }
953
954 bool isMailBlockquote(const Node *node)
955 {
956     if (!node || !node->hasTagName(blockquoteTag))
957         return false;
958         
959     return static_cast<const Element *>(node)->getAttribute("type") == "cite";
960 }
961
962 int caretMinOffset(const Node* n)
963 {
964     RenderObject* r = n->renderer();
965     ASSERT(!n->isCharacterDataNode() || !r || r->isText()); // FIXME: This was a runtime check that seemingly couldn't fail; changed it to an assertion for now.
966     return r ? r->caretMinOffset() : 0;
967 }
968
969 // If a node can contain candidates for VisiblePositions, return the offset of the last candidate, otherwise 
970 // return the number of children for container nodes and the length for unrendered text nodes.
971 int caretMaxOffset(const Node* n)
972 {
973     // For rendered text nodes, return the last position that a caret could occupy.
974     if (n->isTextNode() && n->renderer())
975         return n->renderer()->caretMaxOffset();
976     // For containers return the number of children.  For others do the same as above.
977     return lastOffsetForEditing(n);
978 }
979
980 bool lineBreakExistsAtVisiblePosition(const VisiblePosition& visiblePosition)
981 {
982     return lineBreakExistsAtPosition(visiblePosition.deepEquivalent().downstream());
983 }
984
985 bool lineBreakExistsAtPosition(const Position& position)
986 {
987     if (position.isNull())
988         return false;
989     
990     if (position.anchorNode()->hasTagName(brTag) && position.atFirstEditingPositionForNode())
991         return true;
992     
993     if (!position.anchorNode()->renderer())
994         return false;
995     
996     if (!position.anchorNode()->isTextNode() || !position.anchorNode()->renderer()->style()->preserveNewline())
997         return false;
998     
999     Text* textNode = static_cast<Text*>(position.anchorNode());
1000     unsigned offset = position.offsetInContainerNode();
1001     return offset < textNode->length() && textNode->data()[offset] == '\n';
1002 }
1003
1004 // Modifies selections that have an end point at the edge of a table
1005 // that contains the other endpoint so that they don't confuse
1006 // code that iterates over selected paragraphs.
1007 VisibleSelection selectionForParagraphIteration(const VisibleSelection& original)
1008 {
1009     VisibleSelection newSelection(original);
1010     VisiblePosition startOfSelection(newSelection.visibleStart());
1011     VisiblePosition endOfSelection(newSelection.visibleEnd());
1012     
1013     // If the end of the selection to modify is just after a table, and
1014     // if the start of the selection is inside that table, then the last paragraph
1015     // that we'll want modify is the last one inside the table, not the table itself
1016     // (a table is itself a paragraph).
1017     if (Node* table = isFirstPositionAfterTable(endOfSelection))
1018         if (startOfSelection.deepEquivalent().node()->isDescendantOf(table))
1019             newSelection = VisibleSelection(startOfSelection, endOfSelection.previous(true));
1020     
1021     // If the start of the selection to modify is just before a table,
1022     // and if the end of the selection is inside that table, then the first paragraph
1023     // we'll want to modify is the first one inside the table, not the paragraph
1024     // containing the table itself.
1025     if (Node* table = isLastPositionBeforeTable(startOfSelection))
1026         if (endOfSelection.deepEquivalent().node()->isDescendantOf(table))
1027             newSelection = VisibleSelection(startOfSelection.next(true), endOfSelection);
1028     
1029     return newSelection;
1030 }
1031
1032
1033 int indexForVisiblePosition(const VisiblePosition& visiblePosition)
1034 {
1035     if (visiblePosition.isNull())
1036         return 0;
1037     Position p(visiblePosition.deepEquivalent());
1038     RefPtr<Range> range = Range::create(p.node()->document(), firstPositionInNode(p.anchorNode()->document()->documentElement()),
1039                                         p.parentAnchoredEquivalent());
1040     return TextIterator::rangeLength(range.get(), true);
1041 }
1042
1043 // Determines whether two positions are visibly next to each other (first then second)
1044 // while ignoring whitespaces and unrendered nodes
1045 bool isVisiblyAdjacent(const Position& first, const Position& second)
1046 {
1047     return VisiblePosition(first) == VisiblePosition(second.upstream());
1048 }
1049
1050 // Determines whether a node is inside a range or visibly starts and ends at the boundaries of the range.
1051 // Call this function to determine whether a node is visibly fit inside selectedRange
1052 bool isNodeVisiblyContainedWithin(Node* node, const Range* selectedRange)
1053 {
1054     ASSERT(node);
1055     ASSERT(selectedRange);
1056     // If the node is inside the range, then it surely is contained within
1057     ExceptionCode ec = 0;
1058     if (selectedRange->compareNode(node, ec) == Range::NODE_INSIDE)
1059         return true;
1060
1061     bool startIsVisuallySame = visiblePositionBeforeNode(node) == selectedRange->startPosition();
1062     if (startIsVisuallySame && comparePositions(positionInParentAfterNode(node), selectedRange->endPosition()) < 0)
1063         return true;
1064
1065     bool endIsVisuallySame = visiblePositionAfterNode(node) == selectedRange->endPosition();
1066     if (endIsVisuallySame && comparePositions(selectedRange->startPosition(), positionInParentBeforeNode(node)) < 0)
1067         return true;
1068
1069     return startIsVisuallySame && endIsVisuallySame;
1070 }
1071
1072 bool isRenderedAsNonInlineTableImageOrHR(const Node* node)
1073 {
1074     if (!node)
1075         return false;
1076     RenderObject* renderer = node->renderer();
1077     return renderer && ((renderer->isTable() && !renderer->isInline()) || (renderer->isImage() && !renderer->isInline()) || renderer->isHR());
1078 }
1079
1080 PassRefPtr<Range> avoidIntersectionWithNode(const Range* range, Node* node)
1081 {
1082     if (!range)
1083         return 0;
1084
1085     Document* document = range->ownerDocument();
1086
1087     Node* startContainer = range->startContainer();
1088     int startOffset = range->startOffset();
1089     Node* endContainer = range->endContainer();
1090     int endOffset = range->endOffset();
1091
1092     if (!startContainer)
1093         return 0;
1094
1095     ASSERT(endContainer);
1096
1097     if (startContainer == node || startContainer->isDescendantOf(node)) {
1098         ASSERT(node->parentNode());
1099         startContainer = node->parentNode();
1100         startOffset = node->nodeIndex();
1101     }
1102     if (endContainer == node || endContainer->isDescendantOf(node)) {
1103         ASSERT(node->parentNode());
1104         endContainer = node->parentNode();
1105         endOffset = node->nodeIndex();
1106     }
1107
1108     return Range::create(document, startContainer, startOffset, endContainer, endOffset);
1109 }
1110
1111 VisibleSelection avoidIntersectionWithNode(const VisibleSelection& selection, Node* node)
1112 {
1113     if (selection.isNone())
1114         return VisibleSelection(selection);
1115
1116     VisibleSelection updatedSelection(selection);
1117     Node* base = selection.base().node();
1118     Node* extent = selection.extent().node();
1119     ASSERT(base);
1120     ASSERT(extent);
1121
1122     if (base == node || base->isDescendantOf(node)) {
1123         ASSERT(node->parentNode());
1124         updatedSelection.setBase(positionInParentBeforeNode(node));
1125     }
1126
1127     if (extent == node || extent->isDescendantOf(node)) {
1128         ASSERT(node->parentNode());
1129         updatedSelection.setExtent(positionInParentBeforeNode(node));
1130     }
1131
1132     return updatedSelection;
1133 }
1134
1135 } // namespace WebCore