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