1 /**

     2  * (C) 1999 Lars Knoll (knoll@kde.org)

     3  * (C) 2000 Gunnstein Lye (gunnstein@netcom.no)

     4  * (C) 2000 Frederik Holljen (frederik.holljen@hig.no)

     5  * (C) 2001 Peter Kelly (pmk@post.com)

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

     7  *

     8  * This library is free software; you can redistribute it and/or

     9  * modify it under the terms of the GNU Library General Public

    10  * License as published by the Free Software Foundation; either

    11  * version 2 of the License, or (at your option) any later version.

    12  *

    13  * This library is distributed in the hope that it will be useful,

    14  * but WITHOUT ANY WARRANTY; without even the implied warranty of

    15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

    16  * Library General Public License for more details.

    17  *

    18  * You should have received a copy of the GNU Library General Public License

    19  * along with this library; see the file COPYING.LIB.  If not, write to

    20  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,

    21  * Boston, MA 02110-1301, USA.

    22  */

    23 

    24 #include "config.h"

    25 #include "Range.h"

    26 

    27 #include "Document.h"

    28 #include "DocumentFragment.h"

    29 #include "ExceptionCode.h"

    30 #include "HTMLElement.h"

    31 #include "HTMLNames.h"

    32 #include "ProcessingInstruction.h"

    33 #include "RangeException.h"

    34 #include "RenderBlock.h"

    35 #include "Text.h"

    36 #include "TextIterator.h"

    37 #include "markup.h"

    38 #include "visible_units.h"

    39 

    40 namespace WebCore {

    41 

    42 using namespace std;

    43 using namespace HTMLNames;

    44 

    45 #ifndef NDEBUG

    46 class RangeCounter {

    47 public:

    48     static unsigned count;

    49     ~RangeCounter()

    50     {

    51         if (count)

    52             fprintf(stderr, "LEAK: %u Range\n", count);

    53     }

    54 };

    55 unsigned RangeCounter::count = 0;

    56 static RangeCounter rangeCounter;

    57 #endif

    58 

    59 Range::Range(Document* ownerDocument)

    60     : m_ownerDocument(ownerDocument)

    61     , m_startContainer(ownerDocument)

    62     , m_startOffset(0)

    63     , m_endContainer(ownerDocument)

    64     , m_endOffset(0)

    65     , m_detached(false)

    66 {

    67 #ifndef NDEBUG

    68     ++RangeCounter::count;

    69 #endif

    70 }

    71 

    72 Range::Range(Document* ownerDocument,

    73               Node* startContainer, int startOffset,

    74               Node* endContainer, int endOffset)

    75     : m_ownerDocument(ownerDocument)

    76     , m_startContainer(ownerDocument)

    77     , m_startOffset(0)

    78     , m_endContainer(ownerDocument)

    79     , m_endOffset(0)

    80     , m_detached(false)

    81 {

    82 #ifndef NDEBUG

    83     ++RangeCounter::count;

    84 #endif

    85     // Simply setting the containers and offsets directly would not do any of the checking

    86     // that setStart and setEnd do, so we must call those functions.

    87     ExceptionCode ec = 0;

    88     setStart(startContainer, startOffset, ec);

    89     ASSERT(ec == 0);

    90     setEnd(endContainer, endOffset, ec);

    91     ASSERT(ec == 0);

    92 }

    93 

    94 Range::Range(Document* ownerDocument, const Position& start, const Position& end)

    95     : m_ownerDocument(ownerDocument)

    96     , m_startContainer(ownerDocument)

    97     , m_startOffset(0)

    98     , m_endContainer(ownerDocument)

    99     , m_endOffset(0)

   100     , m_detached(false)

   101 {

   102 #ifndef NDEBUG

   103     ++RangeCounter::count;

   104 #endif

   105     // Simply setting the containers and offsets directly would not do any of the checking

   106     // that setStart and setEnd do, so we must call those functions.

   107     ExceptionCode ec = 0;

   108     setStart(start.node(), start.offset(), ec);

   109     ASSERT(ec == 0);

   110     setEnd(end.node(), end.offset(), ec);

   111     ASSERT(ec == 0);

   112 }

   113 

   114 Range::~Range()

   115 {

   116 #ifndef NDEBUG

   117     --RangeCounter::count;

   118 #endif

   119 }

   120 

   121 Node *Range::startContainer(ExceptionCode& ec) const

   122 {

   123     if (m_detached) {

   124         ec = INVALID_STATE_ERR;

   125         return 0;

   126     }

   127 

   128     return m_startContainer.get();

   129 }

   130 

   131 int Range::startOffset(ExceptionCode& ec) const

   132 {

   133     if (m_detached) {

   134         ec = INVALID_STATE_ERR;

   135         return 0;

   136     }

   137 

   138     return m_startOffset;

   139 }

   140 

   141 Node *Range::endContainer(ExceptionCode& ec) const

   142 {

   143     if (m_detached) {

   144         ec = INVALID_STATE_ERR;

   145         return 0;

   146     }

   147 

   148     return m_endContainer.get();

   149 }

   150 

   151 int Range::endOffset(ExceptionCode& ec) const

   152 {

   153     if (m_detached) {

   154         ec = INVALID_STATE_ERR;

   155         return 0;

   156     }

   157 

   158     return m_endOffset;

   159 }

   160 

   161 Node *Range::commonAncestorContainer(ExceptionCode& ec) const

   162 {

   163     if (m_detached) {

   164         ec = INVALID_STATE_ERR;

   165         return 0;

   166     }

   167 

   168     Node *com = commonAncestorContainer(m_startContainer.get(), m_endContainer.get());

   169     if (!com) //  should never happen

   170         ec = WRONG_DOCUMENT_ERR;

   171     return com;

   172 }

   173 

   174 Node *Range::commonAncestorContainer(Node *containerA, Node *containerB)

   175 {

   176     Node *parentStart;

   177 

   178     for (parentStart = containerA; parentStart; parentStart = parentStart->parentNode()) {

   179         Node *parentEnd = containerB;

   180         while (parentEnd && (parentStart != parentEnd))

   181             parentEnd = parentEnd->parentNode();

   182         if (parentStart == parentEnd)

   183             break;

   184     }

   185         

   186     return parentStart;

   187 }

   188 

   189 bool Range::collapsed(ExceptionCode& ec) const

   190 {

   191     if (m_detached) {

   192         ec = INVALID_STATE_ERR;

   193         return 0;

   194     }

   195 

   196     return (m_startContainer == m_endContainer && m_startOffset == m_endOffset);

   197 }

   198 

   199 void Range::setStart( Node *refNode, int offset, ExceptionCode& ec)

   200 {

   201     if (m_detached) {

   202         ec = INVALID_STATE_ERR;

   203         return;

   204     }

   205 

   206     if (!refNode) {

   207         ec = NOT_FOUND_ERR;

   208         return;

   209     }

   210 

   211     if (refNode->document() != m_ownerDocument) {

   212         ec = WRONG_DOCUMENT_ERR;

   213         return;

   214     }

   215 

   216     checkNodeWOffset( refNode, offset, ec );

   217     if (ec)

   218         return;

   219 

   220     m_startContainer = refNode;

   221     m_startOffset = offset;

   222 

   223     // check if different root container

   224     Node* endRootContainer = m_endContainer.get();

   225     while (endRootContainer->parentNode())

   226         endRootContainer = endRootContainer->parentNode();

   227     Node* startRootContainer = m_startContainer.get();

   228     while (startRootContainer->parentNode())

   229         startRootContainer = startRootContainer->parentNode();

   230     if (startRootContainer != endRootContainer)

   231         collapse(true, ec);

   232     // check if new start after end

   233     else if (compareBoundaryPoints(m_startContainer.get(), m_startOffset, m_endContainer.get(), m_endOffset) > 0)

   234         collapse(true, ec);

   235 }

   236 

   237 void Range::setEnd( Node *refNode, int offset, ExceptionCode& ec)

   238 {

   239     if (m_detached) {

   240         ec = INVALID_STATE_ERR;

   241         return;

   242     }

   243 

   244     if (!refNode) {

   245         ec = NOT_FOUND_ERR;

   246         return;

   247     }

   248 

   249     if (refNode->document() != m_ownerDocument) {

   250         ec = WRONG_DOCUMENT_ERR;

   251         return;

   252     }

   253 

   254     checkNodeWOffset( refNode, offset, ec );

   255     if (ec)

   256         return;

   257 

   258     m_endContainer = refNode;

   259     m_endOffset = offset;

   260 

   261     // check if different root container

   262     Node* endRootContainer = m_endContainer.get();

   263     while (endRootContainer->parentNode())

   264         endRootContainer = endRootContainer->parentNode();

   265     Node* startRootContainer = m_startContainer.get();

   266     while (startRootContainer->parentNode())

   267         startRootContainer = startRootContainer->parentNode();

   268     if (startRootContainer != endRootContainer)

   269         collapse(false, ec);

   270     // check if new end before start

   271     if (compareBoundaryPoints(m_startContainer.get(), m_startOffset, m_endContainer.get(), m_endOffset) > 0)

   272         collapse(false, ec);

   273 }

   274 

   275 void Range::collapse( bool toStart, ExceptionCode& ec)

   276 {

   277     if (m_detached) {

   278         ec = INVALID_STATE_ERR;

   279         return;

   280     }

   281 

   282     if (toStart) {  // collapse to start

   283         m_endContainer = m_startContainer;

   284         m_endOffset = m_startOffset;

   285     } else {        // collapse to end

   286         m_startContainer = m_endContainer;

   287         m_startOffset = m_endOffset;

   288     }

   289 }

   290 

   291 bool Range::isPointInRange(Node* refNode, int offset, ExceptionCode& ec)

   292 {

   293     if (!refNode) {

   294         ec = NOT_FOUND_ERR;

   295         return false;

   296     }

   297 

   298     if (m_detached && refNode->attached()) {

   299         ec = INVALID_STATE_ERR;

   300         return false;

   301     }

   302 

   303     if (!m_detached && !refNode->attached()) {

   304         // firefox doesn't throw an exception for this case; it returns false

   305         return false;

   306     }

   307 

   308     if (refNode->document() != m_ownerDocument) {

   309         ec = WRONG_DOCUMENT_ERR;

   310         return false;

   311     }

   312 

   313     checkNodeWOffset(refNode, offset, ec);

   314     if (ec)

   315         return false;

   316 

   317 

   318     // point is not before the start and not after the end

   319     if ((compareBoundaryPoints(refNode, offset, m_startContainer.get(), m_startOffset) != -1) && 

   320         (compareBoundaryPoints(refNode, offset, m_endContainer.get(), m_endOffset) != 1))

   321         return true;

   322     else

   323         return false;

   324 }

   325 

   326 short Range::comparePoint(Node* refNode, int offset, ExceptionCode& ec)

   327 {

   328     // http://developer.mozilla.org/en/docs/DOM:range.comparePoint

   329     // This method returns -1, 0 or 1 depending on if the point described by the 

   330     // refNode node and an offset within the node is before, same as, or after the range respectively.

   331 

   332     if (!refNode) {

   333         ec = NOT_FOUND_ERR;

   334         return 0;

   335     }

   336 

   337     if (m_detached && refNode->attached()) {

   338         ec = INVALID_STATE_ERR;

   339         return 0;

   340     }

   341 

   342     if (!m_detached && !refNode->attached()) {

   343         // firefox doesn't throw an exception for this case; it returns -1

   344         return -1;

   345     }

   346 

   347     if (refNode->document() != m_ownerDocument) {

   348         ec = WRONG_DOCUMENT_ERR;

   349         return 0;

   350     }

   351 

   352     checkNodeWOffset(refNode, offset, ec);

   353     if (ec)

   354         return 0;

   355 

   356     // compare to start, and point comes before

   357     if (compareBoundaryPoints(refNode, offset, m_startContainer.get(), m_startOffset) == -1)

   358         return -1;

   359 

   360     // compare to end, and point comes after

   361     else if (compareBoundaryPoints(refNode, offset, m_endContainer.get(), m_endOffset) == 1)

   362         return 1;

   363     

   364     // point is in the middle of this range, or on the boundary points

   365     else

   366         return 0;

   367 }

   368 

   369 Range::CompareResults Range::compareNode(Node* refNode, ExceptionCode& ec)

   370 {

   371     // http://developer.mozilla.org/en/docs/DOM:range.compareNode

   372     // This method returns 0, 1, 2, or 3 based on if the node is before, after,

   373     // before and after(surrounds), or inside the range, respectively

   374 

   375     if (!refNode) {

   376         ec = NOT_FOUND_ERR;

   377         return NODE_BEFORE;

   378     }

   379     

   380     if (m_detached && refNode->attached()) {

   381         ec = INVALID_STATE_ERR;

   382         return NODE_BEFORE;

   383     }

   384 

   385     if (!m_detached && !refNode->attached()) {

   386         // firefox doesn't throw an exception for this case; it returns 0

   387         return NODE_BEFORE;

   388     }

   389 

   390     if (refNode->document() != m_ownerDocument) {

   391         // firefox doesn't throw an exception for this case; it returns 0

   392         return NODE_BEFORE;

   393     }

   394 

   395     Node* parentNode = refNode->parentNode();

   396     unsigned nodeIndex = refNode->nodeIndex();

   397     

   398     if (!parentNode) {

   399         // if the node is the top document we should return NODE_BEFORE_AND_AFTER

   400         // but we throw to match firefox behavior

   401         ec = NOT_FOUND_ERR;

   402         return NODE_BEFORE;

   403     }

   404 

   405     if (comparePoint(parentNode, nodeIndex, ec) == -1) { // starts before

   406         if (comparePoint(parentNode, nodeIndex + 1, ec) == 1) // ends after the range

   407             return NODE_BEFORE_AND_AFTER;

   408         return NODE_BEFORE; // ends before or in the range

   409     } else { // starts at or after the range start

   410         if (comparePoint(parentNode, nodeIndex + 1, ec) == 1) // ends after the range

   411             return NODE_AFTER;

   412         return NODE_INSIDE; // ends inside the range

   413     }

   414 }

   415 

   416 

   417 short Range::compareBoundaryPoints(CompareHow how, const Range *sourceRange, ExceptionCode& ec) const

   418 {

   419     if (m_detached) {

   420         ec = INVALID_STATE_ERR;

   421         return 0;

   422     }

   423 

   424     if (!sourceRange) {

   425         ec = NOT_FOUND_ERR;

   426         return 0;

   427     }

   428 

   429     Node *thisCont = commonAncestorContainer(ec);

   430     Node *sourceCont = sourceRange->commonAncestorContainer(ec);

   431     if (ec)

   432         return 0;

   433 

   434     if (thisCont->document() != sourceCont->document()) {

   435         ec = WRONG_DOCUMENT_ERR;

   436         return 0;

   437     }

   438 

   439     Node *thisTop = thisCont;

   440     Node *sourceTop = sourceCont;

   441     while (thisTop->parentNode())

   442         thisTop = thisTop->parentNode();

   443     while (sourceTop->parentNode())

   444         sourceTop = sourceTop->parentNode();

   445     if (thisTop != sourceTop) { // in different DocumentFragments

   446         ec = WRONG_DOCUMENT_ERR;

   447         return 0;

   448     }

   449 

   450     switch(how)

   451     {

   452     case START_TO_START:

   453         return compareBoundaryPoints( m_startContainer.get(), m_startOffset,

   454                                       sourceRange->startContainer(ec), sourceRange->startOffset(ec) );

   455         break;

   456     case START_TO_END:

   457         return compareBoundaryPoints( m_startContainer.get(), m_startOffset,

   458                                       sourceRange->endContainer(ec), sourceRange->endOffset(ec) );

   459         break;

   460     case END_TO_END:

   461         return compareBoundaryPoints( m_endContainer.get(), m_endOffset,

   462                                       sourceRange->endContainer(ec), sourceRange->endOffset(ec) );

   463         break;

   464     case END_TO_START:

   465         return compareBoundaryPoints( m_endContainer.get(), m_endOffset,

   466                                       sourceRange->startContainer(ec), sourceRange->startOffset(ec) );

   467         break;

   468     default:

   469         ec = SYNTAX_ERR;

   470         return 0;

   471     }

   472 }

   473 

   474 short Range::compareBoundaryPoints( Node *containerA, int offsetA, Node *containerB, int offsetB )

   475 {

   476     ASSERT(containerA && containerB);

   477     if (!containerA)

   478         return -1;

   479     if (!containerB)

   480         return 1;

   481     // see DOM2 traversal & range section 2.5

   482 

   483     // case 1: both points have the same container

   484     if(containerA == containerB) {

   485         if (offsetA == offsetB)

   486             return 0;           // A is equal to B

   487         if (offsetA < offsetB)

   488             return -1;          // A is before B

   489         else

   490             return 1;           // A is after B

   491     }

   492 

   493     // case 2: node C (container B or an ancestor) is a child node of A

   494     Node *c = containerB;

   495     while (c && c->parentNode() != containerA)

   496         c = c->parentNode();

   497     if (c) {

   498         int offsetC = 0;

   499         Node *n = containerA->firstChild();

   500         while (n != c && offsetC < offsetA) {

   501             offsetC++;

   502             n = n->nextSibling();

   503         }

   504 

   505         if (offsetA <= offsetC)

   506             return -1;              // A is before B

   507         else

   508             return 1;               // A is after B

   509     }

   510 

   511     // case 3: node C (container A or an ancestor) is a child node of B

   512     c = containerA;

   513     while (c && c->parentNode() != containerB)

   514         c = c->parentNode();

   515     if (c) {

   516         int offsetC = 0;

   517         Node *n = containerB->firstChild();

   518         while (n != c && offsetC < offsetB) {

   519             offsetC++;

   520             n = n->nextSibling();

   521         }

   522 

   523         if(offsetC < offsetB)

   524             return -1;              // A is before B

   525         else

   526             return 1;               // A is after B

   527     }

   528 

   529     // case 4: containers A & B are siblings, or children of siblings

   530     // ### we need to do a traversal here instead

   531     Node *cmnRoot = commonAncestorContainer(containerA,containerB);

   532     if (!cmnRoot)

   533         return 0;

   534     Node *childA = containerA;

   535     while (childA && childA->parentNode() != cmnRoot)

   536         childA = childA->parentNode();

   537     if (!childA)

   538         childA = cmnRoot;

   539     Node *childB = containerB;

   540     while (childB && childB->parentNode() != cmnRoot)

   541         childB = childB->parentNode();

   542     if (!childB)

   543         childB = cmnRoot;

   544 

   545     if (childA == childB)

   546         return 0; // A is equal to B

   547 

   548     Node *n = cmnRoot->firstChild();

   549     while (n) {

   550         if (n == childA)

   551             return -1; // A is before B

   552         if (n == childB)

   553             return 1; // A is after B

   554         n = n->nextSibling();

   555     }

   556 

   557     // Should never reach this point.

   558     ASSERT(0);

   559     return 0;

   560 }

   561 

   562 short Range::compareBoundaryPoints( const Position &a, const Position &b )

   563 {

   564     return compareBoundaryPoints(a.node(), a.offset(), b.node(), b.offset());

   565 }

   566 

   567 bool Range::boundaryPointsValid() const

   568 {

   569     return m_startContainer && m_endContainer && compareBoundaryPoints(m_startContainer.get(), m_startOffset, m_endContainer.get(), m_endOffset) <= 0;

   570 }

   571 

   572 void Range::deleteContents(ExceptionCode& ec) {

   573     if (m_detached) {

   574         ec = INVALID_STATE_ERR;

   575         return;

   576     }

   577 

   578     checkDeleteExtract(ec);

   579     if (ec)

   580         return;

   581 

   582     processContents(DELETE_CONTENTS,ec);

   583 }

   584 

   585 bool Range::intersectsNode(Node* refNode, ExceptionCode& ec)

   586 {

   587     // http://developer.mozilla.org/en/docs/DOM:range.intersectsNode

   588     // Returns a bool if the node intersects the range.

   589 

   590     if (!refNode) {

   591         ec = NOT_FOUND_ERR;

   592         return false;

   593     }

   594     

   595     if (m_detached && refNode->attached() ||

   596         !m_detached && !refNode->attached() ||

   597         refNode->document() != m_ownerDocument)

   598         // firefox doesn't throw an exception for these case; it returns false

   599         return false;

   600 

   601     Node* parentNode = refNode->parentNode();

   602     unsigned nodeIndex = refNode->nodeIndex();

   603     

   604     if (!parentNode) {

   605         // if the node is the top document we should return NODE_BEFORE_AND_AFTER

   606         // but we throw to match firefox behavior

   607         ec = NOT_FOUND_ERR;

   608         return false;

   609     }

   610 

   611     if (comparePoint(parentNode, nodeIndex, ec) == -1 && // starts before start

   612         comparePoint(parentNode, nodeIndex + 1, ec) == -1) { // ends before start

   613         return false;

   614     } else if(comparePoint(parentNode, nodeIndex, ec) == 1 && // starts after end

   615               comparePoint(parentNode, nodeIndex + 1, ec) == 1) { // ends after end

   616         return false;

   617     }

   618     

   619     return true;    //all other cases

   620 }

   621 

   622 PassRefPtr<DocumentFragment> Range::processContents ( ActionType action, ExceptionCode& ec)

   623 {

   624     // ### when mutation events are implemented, we will have to take into account

   625     // situations where the tree is being transformed while we delete - ugh!

   626 

   627     // ### perhaps disable node deletion notification for this range while we do this?

   628 

   629     if (collapsed(ec))

   630         return 0;

   631     if (ec)

   632         return 0;

   633 

   634     Node *cmnRoot = commonAncestorContainer(ec);

   635     if (ec)

   636         return 0;

   637 

   638     // what is the highest node that partially selects the start of the range?

   639     Node *partialStart = 0;

   640     if (m_startContainer != cmnRoot) {

   641         partialStart = m_startContainer.get();

   642         while (partialStart->parentNode() != cmnRoot)

   643             partialStart = partialStart->parentNode();

   644     }

   645 

   646     // what is the highest node that partially selects the end of the range?

   647     Node *partialEnd = 0;

   648     if (m_endContainer != cmnRoot) {

   649         partialEnd = m_endContainer.get();

   650         while (partialEnd->parentNode() != cmnRoot)

   651             partialEnd = partialEnd->parentNode();

   652     }

   653 

   654     RefPtr<DocumentFragment> fragment;

   655     if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS)

   656         fragment = new DocumentFragment(m_ownerDocument.get());

   657 

   658     // Simple case: the start and end containers are the same. We just grab

   659     // everything >= start offset and < end offset

   660     if (m_startContainer == m_endContainer) {

   661         if(m_startContainer->nodeType() == Node::TEXT_NODE ||

   662            m_startContainer->nodeType() == Node::CDATA_SECTION_NODE ||

   663            m_startContainer->nodeType() == Node::COMMENT_NODE) {

   664 

   665             if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) {

   666                 RefPtr<CharacterData> c = static_pointer_cast<CharacterData>(m_startContainer->cloneNode(true));

   667                 c->deleteData(m_endOffset, c->length() - m_endOffset, ec);

   668                 c->deleteData(0, m_startOffset, ec);

   669                 fragment->appendChild(c.release(), ec);

   670             }

   671             if (action == EXTRACT_CONTENTS || action == DELETE_CONTENTS) {

   672                 static_cast<CharacterData*>(m_startContainer.get())->deleteData(m_startOffset,m_endOffset-m_startOffset,ec);

   673                 m_startContainer->document()->updateLayout();

   674             }

   675         }

   676         else if (m_startContainer->nodeType() == Node::PROCESSING_INSTRUCTION_NODE) {

   677             // ### operate just on data ?

   678         }

   679         else {

   680             Node *n = m_startContainer->firstChild();

   681             unsigned i;

   682             for (i = 0; n && i < m_startOffset; i++) // skip until m_startOffset

   683                 n = n->nextSibling();

   684             while (n && i < m_endOffset) { // delete until m_endOffset

   685                 Node *next = n->nextSibling();

   686                 if (action == EXTRACT_CONTENTS)

   687                     fragment->appendChild(n,ec); // will remove n from it's parent

   688                 else if (action == CLONE_CONTENTS)

   689                     fragment->appendChild(n->cloneNode(true),ec);

   690                 else

   691                     m_startContainer->removeChild(n,ec);

   692                 n = next;

   693                 i++;

   694             }

   695         }

   696         if (action == EXTRACT_CONTENTS || action == DELETE_CONTENTS)

   697             collapse(true,ec);

   698         return fragment.release();

   699     }

   700 

   701     // Complex case: Start and end containers are different.

   702     // There are three possiblities here:

   703     // 1. Start container == cmnRoot (End container must be a descendant)

   704     // 2. End container == cmnRoot (Start container must be a descendant)

   705     // 3. Neither is cmnRoot, they are both descendants

   706     //

   707     // In case 3, we grab everything after the start (up until a direct child

   708     // of cmnRoot) into leftContents, and everything before the end (up until

   709     // a direct child of cmnRoot) into rightContents. Then we process all

   710     // cmnRoot children between leftContents and rightContents

   711     //

   712     // In case 1 or 2, we skip either processing of leftContents or rightContents,

   713     // in which case the last lot of nodes either goes from the first or last

   714     // child of cmnRoot.

   715     //

   716     // These are deleted, cloned, or extracted (i.e. both) depending on action.

   717 

   718     RefPtr<Node> leftContents;

   719     if (m_startContainer != cmnRoot) {

   720         // process the left-hand side of the range, up until the last ancestor of

   721         // m_startContainer before cmnRoot

   722         if(m_startContainer->nodeType() == Node::TEXT_NODE ||

   723            m_startContainer->nodeType() == Node::CDATA_SECTION_NODE ||

   724            m_startContainer->nodeType() == Node::COMMENT_NODE) {

   725 

   726             if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) {

   727                 RefPtr<CharacterData> c = static_pointer_cast<CharacterData>(m_startContainer->cloneNode(true));

   728                 c->deleteData(0, m_startOffset, ec);

   729                 leftContents = c.release();

   730             }

   731             if (action == EXTRACT_CONTENTS || action == DELETE_CONTENTS) {

   732                 static_cast<CharacterData*>(m_startContainer.get())->deleteData(

   733                     m_startOffset, static_cast<CharacterData*>(m_startContainer.get())->length() - m_startOffset, ec);

   734                 m_startContainer->document()->updateLayout();

   735             }

   736         }

   737         else if (m_startContainer->nodeType() == Node::PROCESSING_INSTRUCTION_NODE) {

   738             // ### operate just on data ?

   739             // leftContents = ...

   740         }

   741         else {

   742             if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS)

   743                 leftContents = m_startContainer->cloneNode(false);

   744             Node *n = m_startContainer->firstChild();

   745             for (unsigned i = 0; n && i < m_startOffset; i++) // skip until m_startOffset

   746                 n = n->nextSibling();

   747             while (n) { // process until end

   748                 Node *next = n->nextSibling();

   749                 if (action == EXTRACT_CONTENTS)

   750                     leftContents->appendChild(n,ec); // will remove n from m_startContainer

   751                 else if (action == CLONE_CONTENTS)

   752                     leftContents->appendChild(n->cloneNode(true),ec);

   753                 else

   754                     m_startContainer->removeChild(n,ec);

   755                 n = next;

   756             }

   757         }

   758 

   759         Node *leftParent = m_startContainer->parentNode();

   760         Node *n = m_startContainer->nextSibling();

   761         for (; leftParent != cmnRoot; leftParent = leftParent->parentNode()) {

   762             if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) {

   763                 RefPtr<Node> leftContentsParent = leftParent->cloneNode(false);

   764                 leftContentsParent->appendChild(leftContents,ec);

   765                 leftContents = leftContentsParent;

   766             }

   767 

   768             Node *next;

   769             for (; n; n = next) {

   770                 next = n->nextSibling();

   771                 if (action == EXTRACT_CONTENTS)

   772                     leftContents->appendChild(n,ec); // will remove n from leftParent

   773                 else if (action == CLONE_CONTENTS)

   774                     leftContents->appendChild(n->cloneNode(true),ec);

   775                 else

   776                     leftParent->removeChild(n,ec);

   777             }

   778             n = leftParent->nextSibling();

   779         }

   780     }

   781 

   782     RefPtr<Node> rightContents = 0;

   783     if (m_endContainer != cmnRoot) {

   784         // delete the right-hand side of the range, up until the last ancestor of

   785         // m_endContainer before cmnRoot

   786         if(m_endContainer->nodeType() == Node::TEXT_NODE ||

   787            m_endContainer->nodeType() == Node::CDATA_SECTION_NODE ||

   788            m_endContainer->nodeType() == Node::COMMENT_NODE) {

   789 

   790             if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) {

   791                 RefPtr<CharacterData> c = static_pointer_cast<CharacterData>(m_endContainer->cloneNode(true));

   792                 c->deleteData(m_endOffset, static_cast<CharacterData*>(m_endContainer.get())->length() - m_endOffset, ec);

   793                 rightContents = c;

   794             }

   795             if (action == EXTRACT_CONTENTS || action == DELETE_CONTENTS) {

   796                 static_cast<CharacterData*>(m_endContainer.get())->deleteData(0, m_endOffset, ec);

   797                 m_startContainer->document()->updateLayout();

   798             }

   799         }

   800         else if (m_startContainer->nodeType() == Node::PROCESSING_INSTRUCTION_NODE) {

   801             // ### operate just on data ?

   802             // rightContents = ...

   803         }

   804         else {

   805             if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS)

   806                 rightContents = m_endContainer->cloneNode(false);

   807             Node *n = m_endContainer->firstChild();

   808             if (n && m_endOffset) {

   809                 for (unsigned i = 0; i+1 < m_endOffset; i++) { // skip to m_endOffset

   810                     Node *next = n->nextSibling();

   811                     if (!next)

   812                         break;

   813                     n = next;

   814                 }

   815                 Node *prev;

   816                 for (; n; n = prev) {

   817                     prev = n->previousSibling();

   818                     if (action == EXTRACT_CONTENTS)

   819                         rightContents->insertBefore(n,rightContents->firstChild(),ec); // will remove n from it's parent

   820                     else if (action == CLONE_CONTENTS)

   821                         rightContents->insertBefore(n->cloneNode(true),rightContents->firstChild(),ec);

   822                     else

   823                         m_endContainer->removeChild(n,ec);

   824                 }

   825             }

   826         }

   827 

   828         Node *rightParent = m_endContainer->parentNode();

   829         Node *n = m_endContainer->previousSibling();

   830         for (; rightParent != cmnRoot; rightParent = rightParent->parentNode()) {

   831             if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) {

   832                 RefPtr<Node> rightContentsParent = rightParent->cloneNode(false);

   833                 rightContentsParent->appendChild(rightContents,ec);

   834                 rightContents = rightContentsParent;

   835             }

   836 

   837             Node *prev;

   838             for (; n; n = prev) {

   839                 prev = n->previousSibling();

   840                 if (action == EXTRACT_CONTENTS)

   841                     rightContents->insertBefore(n,rightContents->firstChild(),ec); // will remove n from it's parent

   842                 else if (action == CLONE_CONTENTS)

   843                     rightContents->insertBefore(n->cloneNode(true),rightContents->firstChild(),ec);

   844                 else

   845                     rightParent->removeChild(n,ec);

   846             }

   847             n = rightParent->previousSibling();

   848         }

   849     }

   850 

   851     // delete all children of cmnRoot between the start and end container

   852 

   853     Node *processStart; // child of cmnRooot

   854     if (m_startContainer == cmnRoot) {

   855         unsigned i;

   856         processStart = m_startContainer->firstChild();

   857         for (i = 0; i < m_startOffset; i++)

   858             processStart = processStart->nextSibling();

   859     }

   860     else {

   861         processStart = m_startContainer.get();

   862         while (processStart->parentNode() != cmnRoot)

   863             processStart = processStart->parentNode();

   864         processStart = processStart->nextSibling();

   865     }

   866     Node *processEnd; // child of cmnRooot

   867     if (m_endContainer == cmnRoot) {

   868         unsigned i;

   869         processEnd = m_endContainer->firstChild();

   870         for (i = 0; i < m_endOffset; i++)

   871             processEnd = processEnd->nextSibling();

   872     }

   873     else {

   874         processEnd = m_endContainer.get();

   875         while (processEnd->parentNode() != cmnRoot)

   876             processEnd = processEnd->parentNode();

   877     }

   878 

   879     // Now add leftContents, stuff in between, and rightContents to the fragment

   880     // (or just delete the stuff in between)

   881 

   882     if ((action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) && leftContents)

   883       fragment->appendChild(leftContents,ec);

   884 

   885     Node *next;

   886     Node *n;

   887     if (processStart) {

   888         for (n = processStart; n && n != processEnd; n = next) {

   889             next = n->nextSibling();

   890 

   891             if (action == EXTRACT_CONTENTS)

   892                 fragment->appendChild(n,ec); // will remove from cmnRoot

   893             else if (action == CLONE_CONTENTS)

   894                 fragment->appendChild(n->cloneNode(true),ec);

   895             else

   896                 cmnRoot->removeChild(n,ec);

   897         }

   898     }

   899 

   900     if ((action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) && rightContents)

   901       fragment->appendChild(rightContents,ec);

   902 

   903     // collapse to the proper position - see spec section 2.6

   904     if (action == EXTRACT_CONTENTS || action == DELETE_CONTENTS) {

   905         if (!partialStart && !partialEnd)

   906             collapse(true,ec);

   907         else if (partialStart) {

   908             m_startContainer = partialStart->parentNode();

   909             m_endContainer = partialStart->parentNode();

   910             m_startOffset = m_endOffset = partialStart->nodeIndex()+1;

   911         }

   912         else if (partialEnd) {

   913             m_startContainer = partialEnd->parentNode();

   914             m_endContainer = partialEnd->parentNode();

   915             m_startOffset = m_endOffset = partialEnd->nodeIndex();

   916         }

   917     }

   918     return fragment.release();

   919 }

   920 

   921 

   922 PassRefPtr<DocumentFragment> Range::extractContents(ExceptionCode& ec)

   923 {

   924     if (m_detached) {

   925         ec = INVALID_STATE_ERR;

   926         return 0;

   927     }

   928 

   929     checkDeleteExtract(ec);

   930     if (ec)

   931         return 0;

   932 

   933     return processContents(EXTRACT_CONTENTS,ec);

   934 }

   935 

   936 PassRefPtr<DocumentFragment> Range::cloneContents( int &ec  )

   937 {

   938     if (m_detached) {

   939         ec = INVALID_STATE_ERR;

   940         return 0;

   941     }

   942 

   943     return processContents(CLONE_CONTENTS,ec);

   944 }

   945 

   946 void Range::insertNode(PassRefPtr<Node> newNode, ExceptionCode& ec)

   947 {

   948     if (m_detached) {

   949         ec = INVALID_STATE_ERR;

   950         return;

   951     }

   952 

   953     if (!newNode) {

   954         ec = NOT_FOUND_ERR;

   955         return;

   956     }

   957 

   958     // NO_MODIFICATION_ALLOWED_ERR: Raised if an ancestor container of either boundary-point of

   959     // the Range is read-only.

   960     if (containedByReadOnly()) {

   961         ec = NO_MODIFICATION_ALLOWED_ERR;

   962         return;

   963     }

   964 

   965     // WRONG_DOCUMENT_ERR: Raised if newParent and the container of the start of the Range were

   966     // not created from the same document.

   967     if (newNode->document() != m_startContainer->document()) {

   968         ec = WRONG_DOCUMENT_ERR;

   969         return;

   970     }

   971 

   972 

   973     // HIERARCHY_REQUEST_ERR: Raised if the container of the start of the Range is of a type that

   974     // does not allow children of the type of newNode or if newNode is an ancestor of the container.

   975 

   976     // an extra one here - if a text node is going to split, it must have a parent to insert into

   977     if (m_startContainer->nodeType() == Node::TEXT_NODE && !m_startContainer->parentNode()) {

   978         ec = HIERARCHY_REQUEST_ERR;

   979         return;

   980     }

   981 

   982     // In the case where the container is a text node, we check against the container's parent, because

   983     // text nodes get split up upon insertion.

   984     Node *checkAgainst;

   985     if (m_startContainer->nodeType() == Node::TEXT_NODE)

   986         checkAgainst = m_startContainer->parentNode();

   987     else

   988         checkAgainst = m_startContainer.get();

   989 

   990     if (newNode->nodeType() == Node::DOCUMENT_FRAGMENT_NODE) {

   991         // check each child node, not the DocumentFragment itself

   992         Node *c;

   993         for (c = newNode->firstChild(); c; c = c->nextSibling()) {

   994             if (!checkAgainst->childTypeAllowed(c->nodeType())) {

   995                 ec = HIERARCHY_REQUEST_ERR;

   996                 return;

   997             }

   998         }

   999     }

  1000     else {

  1001         if (!checkAgainst->childTypeAllowed(newNode->nodeType())) {

  1002             ec = HIERARCHY_REQUEST_ERR;

  1003             return;

  1004         }

  1005     }

  1006 

  1007     for (Node *n = m_startContainer.get(); n; n = n->parentNode()) {

  1008         if (n == newNode) {

  1009             ec = HIERARCHY_REQUEST_ERR;

  1010             return;

  1011         }

  1012     }

  1013 

  1014     // INVALID_NODE_TYPE_ERR: Raised if newNode is an Attr, Entity, Notation, or Document node.

  1015     if( newNode->nodeType() == Node::ATTRIBUTE_NODE ||

  1016         newNode->nodeType() == Node::ENTITY_NODE ||

  1017         newNode->nodeType() == Node::NOTATION_NODE ||

  1018         newNode->nodeType() == Node::DOCUMENT_NODE) {

  1019         ec = INVALID_NODE_TYPE_ERR;

  1020         return;

  1021     }

  1022 

  1023     if( m_startContainer->nodeType() == Node::TEXT_NODE ||

  1024         m_startContainer->nodeType() == Node::CDATA_SECTION_NODE )

  1025     {

  1026         Text *newText = static_cast<Text*>(m_startContainer.get())->splitText(m_startOffset,ec);

  1027         if (ec)

  1028             return;

  1029         m_startContainer->parentNode()->insertBefore( newNode, newText, ec );

  1030     }

  1031     else {

  1032         m_startContainer->insertBefore( newNode, m_startContainer->childNode( m_startOffset ), ec );

  1033     }

  1034 }

  1035 

  1036 String Range::toString(ExceptionCode& ec) const

  1037 {

  1038     if (m_detached) {

  1039         ec = INVALID_STATE_ERR;

  1040         return String();

  1041     }

  1042 

  1043     Vector<UChar> result;

  1044 

  1045     Node* pastEnd = pastEndNode();

  1046     for (Node* n = startNode(); n != pastEnd; n = n->traverseNextNode()) {

  1047         if (n->nodeType() == Node::TEXT_NODE || n->nodeType() == Node::CDATA_SECTION_NODE) {

  1048             String data = static_cast<CharacterData*>(n)->data();

  1049             unsigned length = data.length();

  1050             unsigned start = (n == m_startContainer) ? min(m_startOffset, length) : 0;

  1051             unsigned end = (n == m_endContainer) ? min(max(start, m_endOffset), length) : length;

  1052             result.append(data.characters() + start, end - start);

  1053         }

  1054     }

  1055 

  1056     return String::adopt(result);

  1057 }

  1058 

  1059 String Range::toHTML() const

  1060 {

  1061     return createMarkup(this);

  1062 }

  1063 

  1064 String Range::text() const

  1065 {

  1066     if (m_detached)

  1067         return String();

  1068 

  1069     // We need to update layout, since plainText uses line boxes in the render tree.

  1070     // FIXME: As with innerText, we'd like this to work even if there are no render objects.

  1071     m_startContainer->document()->updateLayout();

  1072 

  1073     // FIXME: Maybe DOMRange constructor should take const DOMRange*; if it did we would not need this const_cast.

  1074     return plainText(const_cast<Range *>(this));

  1075 }

  1076 

  1077 PassRefPtr<DocumentFragment> Range::createContextualFragment(const String &html, ExceptionCode& ec) const

  1078 {

  1079     if (m_detached) {

  1080         ec = INVALID_STATE_ERR;

  1081         return 0;

  1082     }

  1083 

  1084     Node* htmlElement = m_startContainer->isHTMLElement() ? m_startContainer.get() : m_startContainer->parentNode();

  1085     

  1086     if (!htmlElement->isHTMLElement()) {

  1087         ec = NOT_SUPPORTED_ERR;

  1088         return 0;

  1089     }

  1090 

  1091     RefPtr<DocumentFragment> fragment = static_cast<HTMLElement*>(htmlElement)->createContextualFragment(html);

  1092     if (!fragment) {

  1093         ec = NOT_SUPPORTED_ERR;

  1094         return 0;

  1095     }

  1096 

  1097     return fragment.release();

  1098 }

  1099 

  1100 

  1101 void Range::detach(ExceptionCode& ec)

  1102 {

  1103     if (m_detached) {

  1104         ec = INVALID_STATE_ERR;

  1105         return;

  1106     }

  1107 

  1108     m_startContainer = 0;

  1109     m_endContainer = 0;

  1110     m_detached = true;

  1111 }

  1112 

  1113 bool Range::isDetached() const

  1114 {

  1115     return m_detached;

  1116 }

  1117 

  1118 void Range::checkNodeWOffset( Node *n, int offset, ExceptionCode& ec) const

  1119 {

  1120     if( offset < 0 ) {

  1121         ec = INDEX_SIZE_ERR;

  1122     }

  1123 

  1124     switch (n->nodeType()) {

  1125         case Node::ENTITY_NODE:

  1126         case Node::NOTATION_NODE:

  1127         case Node::DOCUMENT_TYPE_NODE:

  1128             ec = INVALID_NODE_TYPE_ERR;

  1129             break;

  1130         case Node::TEXT_NODE:

  1131         case Node::COMMENT_NODE:

  1132         case Node::CDATA_SECTION_NODE:

  1133             if ( (unsigned)offset > static_cast<CharacterData*>(n)->length() )

  1134                 ec = INDEX_SIZE_ERR;

  1135             break;