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