1 /*

     2  * Copyright (C) 2004, 2005, 2006, 2007 Apple Inc. All rights reserved.

     3  *

     4  * Redistribution and use in source and binary forms, with or without

     5  * modification, are permitted provided that the following conditions

     6  * are met:

     7  * 1. Redistributions of source code must retain the above copyright

     8  *    notice, this list of conditions and the following disclaimer.

     9  * 2. Redistributions in binary form must reproduce the above copyright

    10  *    notice, this list of conditions and the following disclaimer in the

    11  *    documentation and/or other materials provided with the distribution.

    12  *

    13  * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY

    14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE

    15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR

    16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE COMPUTER, INC. OR

    17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,

    18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,

    19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR

    20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY

    21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT

    22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE

    23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 

    24  */

    25 

    26 #include "config.h"

    27 #include "htmlediting.h"

    28 

    29 #include "CharacterNames.h"

    30 #include "Document.h"

    31 #include "EditingText.h"

    32 #include "HTMLBRElement.h"

    33 #include "HTMLDivElement.h"

    34 #include "HTMLElementFactory.h"

    35 #include "HTMLInterchange.h"

    36 #include "HTMLLIElement.h"

    37 #include "HTMLNames.h"

    38 #include "HTMLOListElement.h"

    39 #include "HTMLUListElement.h"

    40 #include "PositionIterator.h"

    41 #include "RenderObject.h"

    42 #include "Range.h"

    43 #include "VisibleSelection.h"

    44 #include "Text.h"

    45 #include "TextIterator.h"

    46 #include "VisiblePosition.h"

    47 #include "visible_units.h"

    48 #include <wtf/StdLibExtras.h>

    49 

    50 #if ENABLE(WML)

    51 #include "WMLNames.h"

    52 #endif

    53 

    54 using namespace std;

    55 

    56 namespace WebCore {

    57 

    58 using namespace HTMLNames;

    59 

    60 // Atomic means that the node has no children, or has children which are ignored for the

    61 // purposes of editing.

    62 bool isAtomicNode(const Node *node)

    63 {

    64     return node && (!node->hasChildNodes() || editingIgnoresContent(node));

    65 }

    66 

    67 // Returns true for nodes that either have no content, or have content that is ignored (skipped 

    68 // over) while editing.  There are no VisiblePositions inside these nodes.

    69 bool editingIgnoresContent(const Node* node)

    70 {

    71     return !canHaveChildrenForEditing(node) && !node->isTextNode();

    72 }

    73 

    74 bool canHaveChildrenForEditing(const Node* node)

    75 {

    76     return !node->hasTagName(hrTag) &&

    77            !node->hasTagName(brTag) &&

    78            !node->hasTagName(imgTag) &&

    79            !node->hasTagName(buttonTag) &&

    80            !node->hasTagName(inputTag) &&

    81            !node->hasTagName(textareaTag) &&

    82            !node->hasTagName(objectTag) &&

    83            !node->hasTagName(iframeTag) &&

    84            !node->hasTagName(embedTag) &&

    85            !node->hasTagName(appletTag) &&

    86            !node->hasTagName(selectTag) &&

    87            !node->hasTagName(datagridTag) &&

    88 #if ENABLE(WML)

    89            !node->hasTagName(WMLNames::doTag) &&

    90 #endif

    91            !node->isTextNode();

    92 }

    93 

    94 // Compare two positions, taking into account the possibility that one or both

    95 // could be inside a shadow tree. Only works for non-null values.

    96 int comparePositions(const Position& a, const Position& b)

    97 {

    98     Node* nodeA = a.node();

    99     ASSERT(nodeA);

   100     Node* nodeB = b.node();

   101     ASSERT(nodeB);

   102     int offsetA = a.deprecatedEditingOffset();

   103     int offsetB = b.deprecatedEditingOffset();

   104 

   105     Node* shadowAncestorA = nodeA->shadowAncestorNode();

   106     if (shadowAncestorA == nodeA)

   107         shadowAncestorA = 0;

   108     Node* shadowAncestorB = nodeB->shadowAncestorNode();

   109     if (shadowAncestorB == nodeB)

   110         shadowAncestorB = 0;

   111 

   112     int bias = 0;

   113     if (shadowAncestorA != shadowAncestorB) {

   114         if (shadowAncestorA) {

   115             nodeA = shadowAncestorA;

   116             offsetA = 0;

   117             bias = 1;

   118         }

   119         if (shadowAncestorB) {

   120             nodeB = shadowAncestorB;

   121             offsetB = 0;

   122             bias = -1;

   123         }

   124     }

   125 

   126     int result = Range::compareBoundaryPoints(nodeA, offsetA, nodeB, offsetB);

   127     return result ? result : bias;

   128 }

   129 

   130 int comparePositions(const VisiblePosition& a, const VisiblePosition& b)

   131 {

   132     return comparePositions(a.deepEquivalent(), b.deepEquivalent());

   133 }

   134 

   135 Node* highestEditableRoot(const Position& position)

   136 {

   137     Node* node = position.node();

   138     if (!node)

   139         return 0;

   140         

   141     Node* highestRoot = editableRootForPosition(position);

   142     if (!highestRoot)

   143         return 0;

   144     

   145     node = highestRoot;

   146     while (node) {

   147         if (node->isContentEditable())

   148             highestRoot = node;

   149         if (node->hasTagName(bodyTag))

   150             break;

   151         node = node->parentNode();

   152     }

   153     

   154     return highestRoot;

   155 }

   156 

   157 Node* lowestEditableAncestor(Node* node)

   158 {

   159     if (!node)

   160         return 0;

   161     

   162     Node *lowestRoot = 0;

   163     while (node) {

   164         if (node->isContentEditable())

   165             return node->rootEditableElement();

   166         if (node->hasTagName(bodyTag))

   167             break;

   168         node = node->parentNode();

   169     }

   170     

   171     return lowestRoot;

   172 }

   173 

   174 bool isEditablePosition(const Position& p)

   175 {

   176     Node* node = p.node();

   177     if (!node)

   178         return false;

   179         

   180     if (node->renderer() && node->renderer()->isTable())

   181         node = node->parentNode();

   182     

   183     return node->isContentEditable();

   184 }

   185 

   186 bool isAtUnsplittableElement(const Position& pos)

   187 {

   188     Node* node = pos.node();

   189     return (node == editableRootForPosition(pos) || node == enclosingNodeOfType(pos, &isTableCell));

   190 }

   191     

   192     

   193 bool isRichlyEditablePosition(const Position& p)

   194 {

   195     Node* node = p.node();

   196     if (!node)

   197         return false;

   198         

   199     if (node->renderer() && node->renderer()->isTable())

   200         node = node->parentNode();

   201     

   202     return node->isContentRichlyEditable();

   203 }

   204 

   205 Element* editableRootForPosition(const Position& p)

   206 {

   207     Node* node = p.node();

   208     if (!node)

   209         return 0;

   210         

   211     if (node->renderer() && node->renderer()->isTable())

   212         node = node->parentNode();

   213     

   214     return node->rootEditableElement();

   215 }

   216 

   217 // Finds the enclosing element until which the tree can be split.

   218 // When a user hits ENTER, he/she won't expect this element to be split into two.

   219 // You may pass it as the second argument of splitTreeToNode.

   220 Element* unsplittableElementForPosition(const Position& p)

   221 {

   222     // Since enclosingNodeOfType won't search beyond the highest root editable node,

   223     // this code works even if the closest table cell was outside of the root editable node.

   224     Element* enclosingCell = static_cast<Element*>(enclosingNodeOfType(p, &isTableCell, true));

   225     if (enclosingCell)

   226         return enclosingCell;

   227 

   228     return editableRootForPosition(p);

   229 }

   230 

   231 Position nextCandidate(const Position& position)

   232 {

   233     PositionIterator p = position;

   234     while (!p.atEnd()) {

   235         p.increment();

   236         if (p.isCandidate())

   237             return p;

   238     }

   239     return Position();

   240 }

   241 

   242 Position nextVisuallyDistinctCandidate(const Position& position)

   243 {

   244     Position p = position;

   245     Position downstreamStart = p.downstream();

   246     while (!p.atEndOfTree()) {

   247         p = p.next(Character);

   248         if (p.isCandidate() && p.downstream() != downstreamStart)

   249             return p;

   250     }

   251     return Position();

   252 }

   253 

   254 Position previousCandidate(const Position& position)

   255 {

   256     PositionIterator p = position;

   257     while (!p.atStart()) {

   258         p.decrement();

   259         if (p.isCandidate())

   260             return p;

   261     }

   262     return Position();

   263 }

   264 

   265 Position previousVisuallyDistinctCandidate(const Position& position)

   266 {

   267     Position p = position;

   268     Position downstreamStart = p.downstream();

   269     while (!p.atStartOfTree()) {

   270         p = p.previous(Character);

   271         if (p.isCandidate() && p.downstream() != downstreamStart)

   272             return p;

   273     }

   274     return Position();

   275 }

   276 

   277 VisiblePosition firstEditablePositionAfterPositionInRoot(const Position& position, Node* highestRoot)

   278 {

   279     // position falls before highestRoot.

   280     if (comparePositions(position, firstDeepEditingPositionForNode(highestRoot)) == -1 && highestRoot->isContentEditable())

   281         return firstDeepEditingPositionForNode(highestRoot);

   282 

   283     Position p = position;

   284     

   285     if (Node* shadowAncestor = p.node()->shadowAncestorNode())

   286         if (shadowAncestor != p.node())

   287             p = lastDeepEditingPositionForNode(shadowAncestor);

   288     

   289     while (p.node() && !isEditablePosition(p) && p.node()->isDescendantOf(highestRoot))

   290         p = isAtomicNode(p.node()) ? positionInParentAfterNode(p.node()) : nextVisuallyDistinctCandidate(p);

   291     

   292     if (p.node() && p.node() != highestRoot && !p.node()->isDescendantOf(highestRoot))

   293         return VisiblePosition();

   294     

   295     return VisiblePosition(p);

   296 }

   297 

   298 VisiblePosition lastEditablePositionBeforePositionInRoot(const Position& position, Node* highestRoot)

   299 {

   300     // When position falls after highestRoot, the result is easy to compute.

   301     if (comparePositions(position, lastDeepEditingPositionForNode(highestRoot)) == 1)

   302         return lastDeepEditingPositionForNode(highestRoot);

   303 

   304     Position p = position;

   305     

   306     if (Node* shadowAncestor = p.node()->shadowAncestorNode())

   307         if (shadowAncestor != p.node())

   308             p = firstDeepEditingPositionForNode(shadowAncestor);

   309     

   310     while (p.node() && !isEditablePosition(p) && p.node()->isDescendantOf(highestRoot))

   311         p = isAtomicNode(p.node()) ? positionInParentBeforeNode(p.node()) : previousVisuallyDistinctCandidate(p);

   312     

   313     if (p.node() && p.node() != highestRoot && !p.node()->isDescendantOf(highestRoot))

   314         return VisiblePosition();

   315     

   316     return VisiblePosition(p);

   317 }

   318 

   319 // FIXME: The method name, comment, and code say three different things here!

   320 // Whether or not content before and after this node will collapse onto the same line as it.

   321 bool isBlock(const Node* node)

   322 {

   323     return node && node->renderer() && !node->renderer()->isInline();

   324 }

   325 

   326 // FIXME: Deploy this in all of the places where enclosingBlockFlow/enclosingBlockFlowOrTableElement are used.

   327 // FIXME: Pass a position to this function.  The enclosing block of [table, x] for example, should be the 

   328 // block that contains the table and not the table, and this function should be the only one responsible for 

   329 // knowing about these kinds of special cases.

   330 Node* enclosingBlock(Node* node)

   331 {

   332     return static_cast<Element*>(enclosingNodeOfType(Position(node, 0), isBlock));

   333 }

   334 

   335 // Internally editing uses "invalid" positions for historical reasons.  For

   336 // example, in <div><img /></div>, Editing might use (img, 1) for the position

   337 // after <img>, but we have to convert that to (div, 1) before handing the

   338 // position to a Range object.  Ideally all internal positions should

   339 // be "range compliant" for simplicity.

   340 Position rangeCompliantEquivalent(const Position& pos)

   341 {

   342     if (pos.isNull())

   343         return Position();

   344 

   345     Node* node = pos.node();

   346 

   347     if (pos.deprecatedEditingOffset() <= 0) {

   348         if (node->parentNode() && (editingIgnoresContent(node) || isTableElement(node)))

   349             return positionInParentBeforeNode(node);

   350         return Position(node, 0);

   351     }

   352 

   353     if (node->offsetInCharacters())

   354         return Position(node, min(node->maxCharacterOffset(), pos.deprecatedEditingOffset()));

   355 

   356     int maxCompliantOffset = node->childNodeCount();

   357     if (pos.deprecatedEditingOffset() > maxCompliantOffset) {

   358         if (node->parentNode())

   359             return positionInParentAfterNode(node);

   360 

   361         // there is no other option at this point than to

   362         // use the highest allowed position in the node

   363         return Position(node, maxCompliantOffset);

   364     } 

   365 

   366     // Editing should never generate positions like this.

   367     if ((pos.deprecatedEditingOffset() < maxCompliantOffset) && editingIgnoresContent(node)) {

   368         ASSERT_NOT_REACHED();

   369         return node->parentNode() ? positionInParentBeforeNode(node) : Position(node, 0);

   370     }

   371     

   372     if (pos.deprecatedEditingOffset() == maxCompliantOffset && (editingIgnoresContent(node) || isTableElement(node)))

   373         return positionInParentAfterNode(node);

   374     

   375     return Position(pos);

   376 }

   377 

   378 Position rangeCompliantEquivalent(const VisiblePosition& vpos)

   379 {

   380     return rangeCompliantEquivalent(vpos.deepEquivalent());

   381 }

   382 

   383 // This method is used to create positions in the DOM. It returns the maximum valid offset

   384 // in a node.  It returns 1 for some elements even though they do not have children, which

   385 // creates technically invalid DOM Positions.  Be sure to call rangeCompliantEquivalent

   386 // on a Position before using it to create a DOM Range, or an exception will be thrown.

   387 int lastOffsetForEditing(const Node* node)

   388 {

   389     ASSERT(node);

   390     if (!node)

   391         return 0;

   392     if (node->offsetInCharacters())

   393         return node->maxCharacterOffset();

   394 

   395     if (node->hasChildNodes())

   396         return node->childNodeCount();

   397 

   398     // NOTE: This should preempt the childNodeCount for, e.g., select nodes

   399     if (editingIgnoresContent(node))

   400         return 1;

   401 

   402     return 0;

   403 }

   404 

   405 String stringWithRebalancedWhitespace(const String& string, bool startIsStartOfParagraph, bool endIsEndOfParagraph)

   406 {

   407     DEFINE_STATIC_LOCAL(String, twoSpaces, ("  "));

   408     DEFINE_STATIC_LOCAL(String, nbsp, ("\xa0"));

   409     DEFINE_STATIC_LOCAL(String, pattern, (" \xa0"));

   410 

   411     String rebalancedString = string;

   412 

   413     rebalancedString.replace(noBreakSpace, ' ');

   414     rebalancedString.replace('\n', ' ');

   415     rebalancedString.replace('\t', ' ');

   416     

   417     rebalancedString.replace(twoSpaces, pattern);

   418     

   419     if (startIsStartOfParagraph && rebalancedString[0] == ' ')

   420         rebalancedString.replace(0, 1, nbsp);

   421     int end = rebalancedString.length() - 1;

   422     if (endIsEndOfParagraph && rebalancedString[end] == ' ')

   423         rebalancedString.replace(end, 1, nbsp);    

   424 

   425     return rebalancedString;

   426 }

   427 

   428 bool isTableStructureNode(const Node *node)

   429 {

   430     RenderObject *r = node->renderer();

   431     return (r && (r->isTableCell() || r->isTableRow() || r->isTableSection() || r->isTableCol()));

   432 }

   433 

   434 const String& nonBreakingSpaceString()

   435 {

   436     DEFINE_STATIC_LOCAL(String, nonBreakingSpaceString, (&noBreakSpace, 1));

   437     return nonBreakingSpaceString;

   438 }

   439 

   440 // FIXME: need to dump this

   441 bool isSpecialElement(const Node *n)

   442 {

   443     if (!n)

   444         return false;

   445         

   446     if (!n->isHTMLElement())

   447         return false;

   448 

   449     if (n->isLink())

   450         return true;

   451 

   452     RenderObject *renderer = n->renderer();

   453     if (!renderer)

   454         return false;

   455         

   456     if (renderer->style()->display() == TABLE || renderer->style()->display() == INLINE_TABLE)

   457         return true;

   458 

   459     if (renderer->style()->isFloating())

   460         return true;

   461 

   462     if (renderer->style()->position() != StaticPosition)

   463         return true;

   464         

   465     return false;

   466 }

   467 

   468 // Checks if a string is a valid tag for the FormatBlockCommand function of execCommand. Expects lower case strings.

   469 bool validBlockTag(const AtomicString& blockTag)

   470 {

   471     if (blockTag.isEmpty())

   472         return false;

   473 

   474     DEFINE_STATIC_LOCAL(HashSet<AtomicString>, blockTags, ());

   475     if (blockTags.isEmpty()) {

   476         blockTags.add(addressTag.localName());

   477         blockTags.add(articleTag.localName());

   478         blockTags.add(asideTag.localName());

   479         blockTags.add(blockquoteTag.localName());

   480         blockTags.add(ddTag.localName());

   481         blockTags.add(divTag.localName());

   482         blockTags.add(dlTag.localName());

   483         blockTags.add(dtTag.localName());

   484         blockTags.add(footerTag.localName());

   485         blockTags.add(h1Tag.localName());

   486         blockTags.add(h2Tag.localName());

   487         blockTags.add(h3Tag.localName());

   488         blockTags.add(h4Tag.localName());

   489         blockTags.add(h5Tag.localName());

   490         blockTags.add(h6Tag.localName());

   491         blockTags.add(headerTag.localName());

   492         blockTags.add(hgroupTag.localName());

   493         blockTags.add(navTag.localName());

   494         blockTags.add(pTag.localName());

   495         blockTags.add(preTag.localName());

   496         blockTags.add(sectionTag.localName());

   497     }

   498     return blockTags.contains(blockTag);

   499 }

   500 

   501 static Node* firstInSpecialElement(const Position& pos)

   502 {

   503     // FIXME: This begins at pos.node(), which doesn't necessarily contain pos (suppose pos was [img, 0]).  See <rdar://problem/5027702>.

   504     Node* rootEditableElement = pos.node()->rootEditableElement();

   505     for (Node* n = pos.node(); n && n->rootEditableElement() == rootEditableElement; n = n->parentNode())

   506         if (isSpecialElement(n)) {

   507             VisiblePosition vPos = VisiblePosition(pos, DOWNSTREAM);

   508             VisiblePosition firstInElement = VisiblePosition(n, 0, DOWNSTREAM);

   509             if (isTableElement(n) && vPos == firstInElement.next())

   510                 return n;

   511             if (vPos == firstInElement)

   512                 return n;

   513         }

   514     return 0;

   515 }

   516 

   517 static Node* lastInSpecialElement(const Position& pos)

   518 {

   519     // FIXME: This begins at pos.node(), which doesn't necessarily contain pos (suppose pos was [img, 0]).  See <rdar://problem/5027702>.

   520     Node* rootEditableElement = pos.node()->rootEditableElement();

   521     for (Node* n = pos.node(); n && n->rootEditableElement() == rootEditableElement; n = n->parentNode())

   522         if (isSpecialElement(n)) {

   523             VisiblePosition vPos = VisiblePosition(pos, DOWNSTREAM);

   524             VisiblePosition lastInElement = VisiblePosition(n, n->childNodeCount(), DOWNSTREAM);

   525             if (isTableElement(n) && vPos == lastInElement.previous())

   526                 return n;

   527             if (vPos == lastInElement)

   528                 return n;

   529         }

   530     return 0;

   531 }

   532 

   533 bool isFirstVisiblePositionInSpecialElement(const Position& pos)

   534 {

   535     return firstInSpecialElement(pos);

   536 }

   537 

   538 Position positionBeforeContainingSpecialElement(const Position& pos, Node** containingSpecialElement)

   539 {

   540     Node* n = firstInSpecialElement(pos);

   541     if (!n)

   542         return pos;

   543     Position result = positionInParentBeforeNode(n);

   544     if (result.isNull() || result.node()->rootEditableElement() != pos.node()->rootEditableElement())

   545         return pos;

   546     if (containingSpecialElement)

   547         *containingSpecialElement = n;

   548     return result;

   549 }

   550 

   551 bool isLastVisiblePositionInSpecialElement(const Position& pos)

   552 {

   553     return lastInSpecialElement(pos);

   554 }

   555 

   556 Position positionAfterContainingSpecialElement(const Position& pos, Node **containingSpecialElement)

   557 {

   558     Node* n = lastInSpecialElement(pos);

   559     if (!n)

   560         return pos;

   561     Position result = positionInParentAfterNode(n);

   562     if (result.isNull() || result.node()->rootEditableElement() != pos.node()->rootEditableElement())

   563         return pos;

   564     if (containingSpecialElement)

   565         *containingSpecialElement = n;

   566     return result;

   567 }

   568 

   569 Position positionOutsideContainingSpecialElement(const Position &pos, Node **containingSpecialElement)

   570 {

   571     if (isFirstVisiblePositionInSpecialElement(pos))

   572         return positionBeforeContainingSpecialElement(pos, containingSpecialElement);

   573     if (isLastVisiblePositionInSpecialElement(pos))

   574         return positionAfterContainingSpecialElement(pos, containingSpecialElement);

   575     return pos;

   576 }

   577 

   578 Node* isFirstPositionAfterTable(const VisiblePosition& visiblePosition)

   579 {

   580     Position upstream(visiblePosition.deepEquivalent().upstream());

   581     if (upstream.node() && upstream.node()->renderer() && upstream.node()->renderer()->isTable() && upstream.atLastEditingPositionForNode())

   582         return upstream.node();

   583     

   584     return 0;

   585 }

   586 

   587 Node* isLastPositionBeforeTable(const VisiblePosition& visiblePosition)

   588 {

   589     Position downstream(visiblePosition.deepEquivalent().downstream());

   590     if (downstream.node() && downstream.node()->renderer() && downstream.node()->renderer()->isTable() && downstream.atFirstEditingPositionForNode())

   591         return downstream.node();

   592     

   593     return 0;

   594 }

   595 

   596 // Returns the visible position at the beginning of a node

   597 VisiblePosition visiblePositionBeforeNode(Node* node)

   598 {

   599     ASSERT(node);

   600     if (node->childNodeCount())

   601         return VisiblePosition(node, 0, DOWNSTREAM);

   602     ASSERT(node->parentNode());

   603     return positionInParentBeforeNode(node);

   604 }

   605 

   606 // Returns the visible position at the ending of a node

   607 VisiblePosition visiblePositionAfterNode(Node* node)

   608 {

   609     ASSERT(node);

   610     if (node->childNodeCount())

   611         return VisiblePosition(node, node->childNodeCount(), DOWNSTREAM);

   612     ASSERT(node->parentNode());

   613     return positionInParentAfterNode(node);

   614 }

   615 

   616 // Create a range object with two visible positions, start and end.

   617 // create(PassRefPtr<Document>, const Position&, const Position&); will use deprecatedEditingOffset

   618 // Use this function instead of create a regular range object (avoiding editing offset).

   619 PassRefPtr<Range> createRange(PassRefPtr<Document> document, const VisiblePosition& start, const VisiblePosition& end, ExceptionCode& ec)

   620 {

   621     ec = 0;

   622     RefPtr<Range> selectedRange = Range::create(document);

   623     selectedRange->setStart(start.deepEquivalent().containerNode(), start.deepEquivalent().computeOffsetInContainerNode(), ec);

   624     if (!ec)

   625         selectedRange->setEnd(end.deepEquivalent().containerNode(), end.deepEquivalent().computeOffsetInContainerNode(), ec);

   626     return selectedRange.release();

   627 }

   628 

   629 // Extend rangeToExtend to include nodes that wraps range and visibly starts and ends inside or at the boudnaries of maximumRange

   630 // e.g. if the original range spaned "hello" in <div>hello</div>, then this function extends the range to contain div's around it.

   631 // Call this function before copying / moving paragraphs to contain all wrapping nodes.

   632 // This function stops extending the range immediately below rootNode; i.e. the extended range can contain a child node of rootNode

   633 // but it can never contain rootNode itself.

   634 PassRefPtr<Range> extendRangeToWrappingNodes(PassRefPtr<Range> range, const Range* maximumRange, const Node* rootNode)

   635 {

   636     ASSERT(range);

   637     ASSERT(maximumRange);

   638 

   639     ExceptionCode ec = 0;

   640     Node* ancestor = range->commonAncestorContainer(ec);// find the cloeset common ancestor

   641     Node* highestNode = 0;

   642     // traverse through ancestors as long as they are contained within the range, content-editable, and below rootNode (could be =0).

   643     while (ancestor && ancestor->isContentEditable() && isNodeVisiblyContainedWithin(ancestor, maximumRange) && ancestor != rootNode) {

   644         highestNode = ancestor;

   645         ancestor = ancestor->parentNode();

   646     }

   647 

   648     if (!highestNode)

   649         return range;

   650 

   651     // Create new range with the highest editable node contained within the range

   652     RefPtr<Range> extendedRange = Range::create(range->ownerDocument());

   653     extendedRange->selectNode(highestNode, ec);

   654     return extendedRange.release();

   655 }

   656 

   657 bool isListElement(Node *n)

   658 {

   659     return (n && (n->hasTagName(ulTag) || n->hasTagName(olTag) || n->hasTagName(dlTag)));

   660 }

   661 

   662 bool isListItem(Node *n)

   663 {

   664     return n && n->renderer() && n->renderer()->isListItem();

   665 }

   666 

   667 Node* enclosingNodeWithTag(const Position& p, const QualifiedName& tagName)

   668 {

   669     if (p.isNull())

   670         return 0;

   671         

   672     Node* root = highestEditableRoot(p);

   673     for (Node* n = p.node(); n; n = n->parentNode()) {

   674         if (root && !n->isContentEditable())

   675             continue;

   676         if (n->hasTagName(tagName))

   677             return n;

   678         if (n == root)

   679             return 0;

   680     }

   681     

   682     return 0;

   683 }

   684 

   685 Node* enclosingNodeOfType(const Position& p, bool (*nodeIsOfType)(const Node*), bool onlyReturnEditableNodes)

   686 {

   687     if (p.isNull())

   688         return 0;

   689         

   690     Node* root = highestEditableRoot(p);

   691     for (Node* n = p.node(); n; n = n->parentNode()) {

   692         // Don't return a non-editable node if the input position was editable, since

   693         // the callers from editing will no doubt want to perform editing inside the returned node.

   694         if (root && !n->isContentEditable() && onlyReturnEditableNodes)

   695             continue;

   696         if ((*nodeIsOfType)(n))

   697             return n;

   698         if (n == root)

   699             return 0;

   700     }

   701     

   702     return 0;

   703 }

   704 

   705 Node* highestEnclosingNodeOfType(const Position& p, bool (*nodeIsOfType)(const Node*))

   706 {

   707     Node* highest = 0;

   708     Node* root = highestEditableRoot(p);

   709     for (Node* n = p.node(); n; n = n->parentNode()) {

   710         if ((*nodeIsOfType)(n))

   711             highest = n;

   712         if (n == root)

   713             break;

   714     }

   715     

   716     return highest;

   717 }

   718 

   719 Node* enclosingTableCell(const Position& p)

   720 {

   721     return static_cast<Element*>(enclosingNodeOfType(p, isTableCell));

   722 }

   723 

   724 Node* enclosingAnchorElement(const Position& p)

   725 {

   726     if (p.isNull())

   727         return 0;

   728     

   729     Node* node = p.node();

   730     while (node && !(node->isElementNode() && node->isLink()))

   731         node = node->parentNode();

   732     return node;

   733 }

   734 

   735 HTMLElement* enclosingList(Node* node)

   736 {

   737     if (!node)

   738         return 0;

   739         

   740     Node* root = highestEditableRoot(Position(node, 0));

   741     

   742     for (Node* n = node->parentNode(); n; n = n->parentNode()) {

   743         if (n->hasTagName(ulTag) || n->hasTagName(olTag))

   744             return static_cast<HTMLElement*>(n);

   745         if (n == root)

   746             return 0;

   747     }

   748     

   749     return 0;

   750 }

   751 

   752 HTMLElement* enclosingListChild(Node *node)

   753 {

   754     if (!node)

   755         return 0;

   756     // Check for a list item element, or for a node whose parent is a list element.  Such a node

   757     // will appear visually as a list item (but without a list marker)

   758     Node* root = highestEditableRoot(Position(node, 0));

   759     

   760     // FIXME: This function is inappropriately named if it starts with node instead of node->parentNode()

   761     for (Node* n = node; n && n->parentNode(); n = n->parentNode()) {

   762         if (n->hasTagName(liTag) || isListElement(n->parentNode()))

   763             return static_cast<HTMLElement*>(n);

   764         if (n == root || isTableCell(n))

   765             return 0;

   766     }

   767     

   768     return 0;

   769 }

   770 

   771 static HTMLElement* embeddedSublist(Node* listItem)

   772 {

   773     // Check the DOM so that we'll find collapsed sublists without renderers.

   774     for (Node* n = listItem->firstChild(); n; n = n->nextSibling()) {

   775         if (isListElement(n))

   776             return static_cast<HTMLElement*>(n);

   777     }

   778     

   779     return 0;

   780 }

   781 

   782 static Node* appendedSublist(Node* listItem)

   783 {

   784     // Check the DOM so that we'll find collapsed sublists without renderers.

   785     for (Node* n = listItem->nextSibling(); n; n = n->nextSibling()) {

   786         if (isListElement(n))

   787             return static_cast<HTMLElement*>(n);

   788         if (isListItem(listItem))

   789             return 0;

   790     }

   791     

   792     return 0;

   793 }

   794 

   795 // FIXME: This method should not need to call isStartOfParagraph/isEndOfParagraph

   796 Node* enclosingEmptyListItem(const VisiblePosition& visiblePos)

   797 {

   798     // Check that position is on a line by itself inside a list item

   799     Node* listChildNode = enclosingListChild(visiblePos.deepEquivalent().node());

   800     if (!listChildNode || !isStartOfParagraph(visiblePos) || !isEndOfParagraph(visiblePos))

   801         return 0;

   802 

   803     VisiblePosition firstInListChild(firstDeepEditingPositionForNode(listChildNode));

   804     VisiblePosition lastInListChild(lastDeepEditingPositionForNode(listChildNode));

   805 

   806     if (firstInListChild != visiblePos || lastInListChild != visiblePos)

   807         return 0;

   808     

   809     if (embeddedSublist(listChildNode) || appendedSublist(listChildNode))

   810         return 0;

   811         

   812     return listChildNode;

   813 }

   814 

   815 HTMLElement* outermostEnclosingList(Node* node, Node* rootList)

   816 {

   817     HTMLElement* list = enclosingList(node);

   818     if (!list)

   819         return 0;

   820 

   821     while (HTMLElement* nextList = enclosingList(list)) {

   822         if (nextList == rootList)

   823             break;

   824         list = nextList;

   825     }

   826 

   827     return list;

   828 }

   829 

   830 bool canMergeLists(Element* firstList, Element* secondList)

   831 {

   832     if (!firstList || !secondList)

   833         return false;

   834 

   835     return firstList->hasTagName(secondList->tagQName())// make sure the list types match (ol vs. ul)

   836     && firstList->isContentEditable() && secondList->isContentEditable()// both lists are editable

   837     && firstList->rootEditableElement() == secondList->rootEditableElement()// don't cross editing boundaries

   838     && isVisiblyAdjacent(positionInParentAfterNode(firstList), positionInParentBeforeNode(secondList));

   839     // Make sure there is no visible content between this li and the previous list

   840 }

   841 

   842 Node* highestAncestor(Node* node)

   843 {

   844     ASSERT(node);

   845     Node* parent = node;

   846     while ((node = node->parentNode()))

   847         parent = node;

   848     return parent;

   849 }

   850 

   851 // FIXME: do not require renderer, so that this can be used within fragments, or rename to isRenderedTable()

   852 bool isTableElement(Node* n)

   853 {

   854     if (!n || !n->isElementNode())

   855         return false;

   856 

   857     RenderObject* renderer = n->renderer();

   858     return (renderer && (renderer->style()->display() == TABLE || renderer->style()->display() == INLINE_TABLE));

   859 }

   860 

   861 bool isTableCell(const Node* node)

   862 {

   863     RenderObject* r = node->renderer();

   864     if (!r)

   865         return node->hasTagName(tdTag) || node->hasTagName(thTag);

   866     

   867     return r->isTableCell();

   868 }

   869 

   870 bool isEmptyTableCell(const Node* node)

   871 {

   872     // Returns true IFF the passed in node is one of:

   873     //   .) a table cell with no children,

   874     //   .) a table cell with a single BR child, and which has no other child renderers, including :before and :after renderers

   875     //   .) the BR child of such a table cell

   876 

   877     // Find rendered node

   878     while (node && !node->renderer())

   879         node = node->parent();

   880     if (!node)

   881         return false;

   882 

   883     // Make sure the rendered node is a table cell or <br>.

   884     // If it's a <br>, then the parent node has to be a table cell.

   885     RenderObject* renderer = node->renderer();

   886     if (renderer->isBR()) {

   887         renderer = renderer->parent();

   888         if (!renderer)

   889             return false;

   890     }

   891     if (!renderer->isTableCell())

   892         return false;

   893 

   894     // Check that the table cell contains no child renderers except for perhaps a single <br>.

   895     RenderObject* childRenderer = renderer->firstChild();

   896     if (!childRenderer)

   897         return true;

   898     if (!childRenderer->isBR())

   899         return false;

   900     return !childRenderer->nextSibling();

   901 }

   902 

   903 PassRefPtr<HTMLElement> createDefaultParagraphElement(Document* document)

   904 {

   905     return HTMLDivElement::create(document);

   906 }

   907 

   908 PassRefPtr<HTMLElement> createBreakElement(Document* document)

   909 {

   910     return HTMLBRElement::create(document);

   911 }

   912 

   913 PassRefPtr<HTMLElement> createOrderedListElement(Document* document)

   914 {

   915     return HTMLOListElement::create(document);

   916 }

   917 

   918 PassRefPtr<HTMLElement> createUnorderedListElement(Document* document)

   919 {

   920     return HTMLUListElement::create(document);

   921 }

   922 

   923 PassRefPtr<HTMLElement> createListItemElement(Document* document)

   924 {

   925     return HTMLLIElement::create(document);

   926 }

   927 

   928 PassRefPtr<HTMLElement> createHTMLElement(Document* document, const QualifiedName& name)

   929 {

   930     return HTMLElementFactory::createHTMLElement(name, document, 0, false);

   931 }

   932 

   933 PassRefPtr<HTMLElement> createHTMLElement(Document* document, const AtomicString& tagName)

   934 {

   935     return createHTMLElement(document, QualifiedName(nullAtom, tagName, xhtmlNamespaceURI));

   936 }

   937 

   938 bool isTabSpanNode(const Node *node)

   939 {

   940     return node && node->hasTagName(spanTag) && node->isElementNode() && static_cast<const Element *>(node)->getAttribute(classAttr) == AppleTabSpanClass;

   941 }

   942 

   943 bool isTabSpanTextNode(const Node *node)

   944 {

   945     return node && node->isTextNode() && node->parentNode() && isTabSpanNode(node->parentNode());

   946 }

   947 

   948 Node *tabSpanNode(const Node *node)

   949 {

   950     return isTabSpanTextNode(node) ? node->parentNode() : 0;

   951 }

   952 

   953 bool isNodeInTextFormControl(Node* node)

   954 {

   955     if (!node)

   956         return false;

   957     Node* ancestor = node->shadowAncestorNode();

   958     if (ancestor == node)

   959         return false;

   960     return ancestor->isElementNode() && static_cast<Element*>(ancestor)->isTextFormControl();

   961 }

   962     

   963 Position positionBeforeTabSpan(const Position& pos)

   964 {

   965     Node *node = pos.node();

   966     if (isTabSpanTextNode(node))

   967         node = tabSpanNode(node);

   968     else if (!isTabSpanNode(node))

   969         return pos;

   970     

   971     return positionInParentBeforeNode(node);

   972 }

   973 

   974 PassRefPtr<Element> createTabSpanElement(Document* document, PassRefPtr<Node> tabTextNode)

   975 {

   976     // Make the span to hold the tab.

   977     RefPtr<Element> spanElement = document->createElement(spanTag, false);

   978     spanElement->setAttribute(classAttr, AppleTabSpanClass);

   979     spanElement->setAttribute(styleAttr, "white-space:pre");

   980 

   981     // Add tab text to that span.

   982     if (!tabTextNode)

   983         tabTextNode = document->createEditingTextNode("\t");

   984 

   985     ExceptionCode ec = 0;

   986     spanElement->appendChild(tabTextNode, ec);

   987     ASSERT(ec == 0);

   988 

   989     return spanElement.release();

   990 }

   991 

   992 PassRefPtr<Element> createTabSpanElement(Document* document, const String& tabText)

   993 {

   994     return createTabSpanElement(document, document->createTextNode(tabText));

   995 }

   996 

   997 PassRefPtr<Element> createTabSpanElement(Document* document)

   998 {

   999     return createTabSpanElement(document, PassRefPtr<Node>());

  1000 }

  1001 

  1002 bool isNodeRendered(const Node *node)

  1003 {

  1004     if (!node)

  1005         return false;

  1006 

  1007     RenderObject *renderer = node->renderer();

  1008     if (!renderer)

  1009         return false;

  1010 

  1011     return renderer->style()->visibility() == VISIBLE;

  1012 }

  1013 

  1014 Node *nearestMailBlockquote(const Node *node)

  1015 {

  1016     for (Node *n = const_cast<Node *>(node); n; n = n->parentNode()) {

  1017         if (isMailBlockquote(n))

  1018             return n;

  1019     }

  1020     return 0;

  1021 }

  1022 

  1023 unsigned numEnclosingMailBlockquotes(const Position& p)

  1024 {

  1025     unsigned num = 0;

  1026     for (Node* n = p.node(); n; n = n->parentNode())

  1027         if (isMailBlockquote(n))

  1028             num++;

  1029     

  1030     return num;

  1031 }

  1032 

  1033 bool isMailBlockquote(const Node *node)

  1034 {

  1035     if (!node || !node->hasTagName(blockquoteTag))

  1036         return false;

  1037         

  1038     return static_cast<const Element *>(node)->getAttribute("type") == "cite";

  1039 }

  1040 

  1041 int caretMinOffset(const Node* n)

  1042 {

  1043     RenderObject* r = n->renderer();

  1044     ASSERT(!n->isCharacterDataNode() || !r || r->isText()); // FIXME: This was a runtime check that seemingly couldn't fail; changed it to an assertion for now.

  1045     return r ? r->caretMinOffset() : 0;

  1046 }

  1047 

  1048 // If a node can contain candidates for VisiblePositions, return the offset of the last candidate, otherwise 

  1049 // return the number of children for container nodes and the length for unrendered text nodes.

  1050 int caretMaxOffset(const Node* n)

  1051 {

  1052     // For rendered text nodes, return the last position that a caret could occupy.

  1053     if (n->isTextNode() && n->renderer())

  1054         return n->renderer()->caretMaxOffset();

  1055     // For containers return the number of children.  For others do the same as above.

  1056     return lastOffsetForEditing(n);

  1057 }

  1058 

  1059 bool lineBreakExistsAtVisiblePosition(const VisiblePosition& visiblePosition)

  1060 {

  1061     return lineBreakExistsAtPosition(visiblePosition.deepEquivalent().downstream());

  1062 }

  1063 

  1064 bool lineBreakExistsAtPosition(const Position& position)

  1065 {

  1066     if (position.isNull())

  1067         return false;

  1068     

  1069     if (position.anchorNode()->hasTagName(brTag) && position.atFirstEditingPositionForNode())

  1070         return true;

  1071     

  1072     if (!position.anchorNode()->isTextNode() || !position.anchorNode()->renderer()->style()->preserveNewline())

  1073         return false;

  1074     

  1075     Text* textNode = static_cast<Text*>(position.anchorNode());

  1076     unsigned offset = position.offsetInContainerNode();

  1077     return offset < textNode->length() && textNode->data()[offset] == '\n';

  1078 }

  1079 

  1080 // Modifies selections that have an end point at the edge of a table

  1081 // that contains the other endpoint so that they don't confuse

  1082 // code that iterates over selected paragraphs.

  1083 VisibleSelection selectionForParagraphIteration(const VisibleSelection& original)

  1084 {

  1085     VisibleSelection newSelection(original);

  1086     VisiblePosition startOfSelection(newSelection.visibleStart());

  1087     VisiblePosition endOfSelection(newSelection.visibleEnd());

  1088     

  1089     // If the end of the selection to modify is just after a table, and

  1090     // if the start of the selection is inside that table, then the last paragraph

  1091     // that we'll want modify is the last one inside the table, not the table itself

  1092     // (a table is itself a paragraph).

  1093     if (Node* table = isFirstPositionAfterTable(endOfSelection))

  1094         if (startOfSelection.deepEquivalent().node()->isDescendantOf(table))

  1095             newSelection = VisibleSelection(startOfSelection, endOfSelection.previous(true));

  1096     

  1097     // If the start of the selection to modify is just before a table,

  1098     // and if the end of the selection is inside that table, then the first paragraph

  1099     // we'll want to modify is the first one inside the table, not the paragraph

  1100     // containing the table itself.

  1101     if (Node* table = isLastPositionBeforeTable(startOfSelection))

  1102         if (endOfSelection.deepEquivalent().node()->isDescendantOf(table))

  1103             newSelection = VisibleSelection(startOfSelection.next(true), endOfSelection);

  1104     

  1105     return newSelection;

  1106 }

  1107 

  1108 

  1109 int indexForVisiblePosition(const VisiblePosition& visiblePosition)

  1110 {

  1111     if (visiblePosition.isNull())

  1112         return 0;

  1113     Position p(visiblePosition.deepEquivalent());

  1114     RefPtr<Range> range = Range::create(p.node()->document(), Position(p.node()->document(), 0), rangeCompliantEquivalent(p));

  1115     return TextIterator::rangeLength(range.get(), true);

  1116 }

  1117 

  1118 // Determines whether two positions are visibly next to each other (first then second)

  1119 // while ignoring whitespaces and unrendered nodes

  1120 bool isVisiblyAdjacent(const Position& first, const Position& second)

  1121 {

  1122     return VisiblePosition(first) == VisiblePosition(second.upstream());

  1123 }

  1124 

  1125 // Determines whether a node is inside a range or visibly starts and ends at the boundaries of the range.

  1126 // Call this function to determine whether a node is visibly fit inside selectedRange

  1127 bool isNodeVisiblyContainedWithin(Node* node, const Range* selectedRange)

  1128 {

  1129     ASSERT(node);

  1130     ASSERT(selectedRange);

  1131     // If the node is inside the range, then it surely is contained within

  1132     ExceptionCode ec = 0;

  1133     if (selectedRange->compareNode(node, ec) == Range::NODE_INSIDE)

  1134         return true;

  1135