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