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