WebCore/dom/Range.cpp

   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, 2008 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 #include "RangeException.h"
  27
  28 #include "CString.h"
  29 #include "Document.h"
  30 #include "DocumentFragment.h"
  31 #include "ExceptionCode.h"
  32 #include "HTMLElement.h"
  33 #include "HTMLNames.h"
  34 #include "NodeWithIndex.h"
  35 #include "ProcessingInstruction.h"
  36 #include "RenderBlock.h"
  37 #include "Text.h"
  38 #include "TextIterator.h"
  39 #include "markup.h"
  40 #include "visible_units.h"
  41 #include <stdio.h>
  42 #include <wtf/RefCountedLeakCounter.h>
  43
  44 namespace WebCore {
  45
  46 using namespace std;
  47 using namespace HTMLNames;
  48
  49 #ifndef NDEBUG
  50 static WTF::RefCountedLeakCounter rangeCounter("Range");
  51 #endif
  52
  53 inline Range::Range(PassRefPtr<Document> ownerDocument)
  54     : m_ownerDocument(ownerDocument)
  55     , m_start(m_ownerDocument)
  56     , m_end(m_ownerDocument)
  57 {
  58 #ifndef NDEBUG
  59     rangeCounter.increment();
  60 #endif
  61
  62     m_ownerDocument->attachRange(this);
  63 }
  64
  65 PassRefPtr<Range> Range::create(PassRefPtr<Document> ownerDocument)
  66 {
  67     return adoptRef(new Range(ownerDocument));
  68 }
  69
  70 inline Range::Range(PassRefPtr<Document> ownerDocument, PassRefPtr<Node> startContainer, int startOffset, PassRefPtr<Node> endContainer, int endOffset)
  71     : m_ownerDocument(ownerDocument)
  72     , m_start(m_ownerDocument)
  73     , m_end(m_ownerDocument)
  74 {
  75 #ifndef NDEBUG
  76     rangeCounter.increment();
  77 #endif
  78
  79     m_ownerDocument->attachRange(this);
  80
  81     // Simply setting the containers and offsets directly would not do any of the checking
  82     // that setStart and setEnd do, so we call those functions.
  83     ExceptionCode ec = 0;
  84     setStart(startContainer, startOffset, ec);
  85     ASSERT(!ec);
  86     setEnd(endContainer, endOffset, ec);
  87     ASSERT(!ec);
  88 }
  89
  90 PassRefPtr<Range> Range::create(PassRefPtr<Document> ownerDocument, PassRefPtr<Node> startContainer, int startOffset, PassRefPtr<Node> endContainer, int endOffset)
  91 {
  92     return adoptRef(new Range(ownerDocument, startContainer, startOffset, endContainer, endOffset));
  93 }
  94
  95 PassRefPtr<Range> Range::create(PassRefPtr<Document> ownerDocument, const Position& start, const Position& end)
  96 {
  97     return adoptRef(new Range(ownerDocument, start.container.get(), start.posOffset, end.container.get(), end.posOffset));
  98 }
  99
 100 Range::~Range()
 101 {
 102     if (m_start.container())
 103         m_ownerDocument->detachRange(this);
 104
 105 #ifndef NDEBUG
 106     rangeCounter.decrement();
 107 #endif
 108 }
 109
 110 Node* Range::startContainer(ExceptionCode& ec) const
 111 {
 112     if (!m_start.container()) {
 113         ec = INVALID_STATE_ERR;
 114         return 0;
 115     }
 116
 117     return m_start.container();
 118 }
 119
 120 int Range::startOffset(ExceptionCode& ec) const
 121 {
 122     if (!m_start.container()) {
 123         ec = INVALID_STATE_ERR;
 124         return 0;
 125     }
 126
 127     return m_start.offset();
 128 }
 129
 130 Node* Range::endContainer(ExceptionCode& ec) const
 131 {
 132     if (!m_start.container()) {
 133         ec = INVALID_STATE_ERR;
 134         return 0;
 135     }
 136
 137     return m_end.container();
 138 }
 139
 140 int Range::endOffset(ExceptionCode& ec) const
 141 {
 142     if (!m_start.container()) {
 143         ec = INVALID_STATE_ERR;
 144         return 0;
 145     }
 146
 147     return m_end.offset();
 148 }
 149
 150 Node* Range::commonAncestorContainer(ExceptionCode& ec) const
 151 {
 152     if (!m_start.container()) {
 153         ec = INVALID_STATE_ERR;
 154         return 0;
 155     }
 156
 157     return commonAncestorContainer(m_start.container(), m_end.container());
 158 }
 159
 160 Node* Range::commonAncestorContainer(Node* containerA, Node* containerB)
 161 {
 162     for (Node* parentA = containerA; parentA; parentA = parentA->parentNode()) {
 163         for (Node* parentB = containerB; parentB; parentB = parentB->parentNode()) {
 164             if (parentA == parentB)
 165                 return parentA;
 166         }
 167     }
 168     return 0;
 169 }
 170
 171 bool Range::collapsed(ExceptionCode& ec) const
 172 {
 173     if (!m_start.container()) {
 174         ec = INVALID_STATE_ERR;
 175         return 0;
 176     }
 177
 178     return m_start == m_end;
 179 }
 180
 181 void Range::setStart(PassRefPtr<Node> refNode, int offset, ExceptionCode& ec)
 182 {
 183     if (!m_start.container()) {
 184         ec = INVALID_STATE_ERR;
 185         return;
 186     }
 187
 188     if (!refNode) {
 189         ec = NOT_FOUND_ERR;
 190         return;
 191     }
 192
 193     if (refNode->document() != m_ownerDocument) {
 194         ec = WRONG_DOCUMENT_ERR;
 195         return;
 196     }
 197
 198     ec = 0;
 199     Node* childNode = checkNodeWOffset(refNode.get(), offset, ec);
 200     if (ec)
 201         return;
 202
 203     m_start.set(refNode, offset, childNode);
 204
 205     // check if different root container
 206     Node* endRootContainer = m_end.container();
 207     while (endRootContainer->parentNode())
 208         endRootContainer = endRootContainer->parentNode();
 209     Node* startRootContainer = m_start.container();
 210     while (startRootContainer->parentNode())
 211         startRootContainer = startRootContainer->parentNode();
 212     if (startRootContainer != endRootContainer)
 213         collapse(true, ec);
 214     // check if new start after end
 215     else if (compareBoundaryPoints(m_start.container(), m_start.offset(), m_end.container(), m_end.offset()) > 0)
 216         collapse(true, ec);
 217 }
 218
 219 void Range::setEnd(PassRefPtr<Node> refNode, int offset, ExceptionCode& ec)
 220 {
 221     if (!m_start.container()) {
 222         ec = INVALID_STATE_ERR;
 223         return;
 224     }
 225
 226     if (!refNode) {
 227         ec = NOT_FOUND_ERR;
 228         return;
 229     }
 230
 231     if (refNode->document() != m_ownerDocument) {
 232         ec = WRONG_DOCUMENT_ERR;
 233         return;
 234     }
 235
 236     ec = 0;
 237     Node* childNode = checkNodeWOffset(refNode.get(), offset, ec);
 238     if (ec)
 239         return;
 240
 241     m_end.set(refNode, offset, childNode);
 242
 243     // check if different root container
 244     Node* endRootContainer = m_end.container();
 245     while (endRootContainer->parentNode())
 246         endRootContainer = endRootContainer->parentNode();
 247     Node* startRootContainer = m_start.container();
 248     while (startRootContainer->parentNode())
 249         startRootContainer = startRootContainer->parentNode();
 250     if (startRootContainer != endRootContainer)
 251         collapse(false, ec);
 252     // check if new end before start
 253     if (compareBoundaryPoints(m_start.container(), m_start.offset(), m_end.container(), m_end.offset()) > 0)
 254         collapse(false, ec);
 255 }
 256
 257 void Range::collapse(bool toStart, ExceptionCode& ec)
 258 {
 259     if (!m_start.container()) {
 260         ec = INVALID_STATE_ERR;
 261         return;
 262     }
 263
 264     if (toStart)
 265         m_end = m_start;
 266     else
 267         m_start = m_end;
 268 }
 269
 270 bool Range::isPointInRange(Node* refNode, int offset, ExceptionCode& ec)
 271 {
 272     if (!refNode) {
 273         ec = NOT_FOUND_ERR;
 274         return false;
 275     }
 276
 277     if (!m_start.container() && refNode->attached()) {
 278         ec = INVALID_STATE_ERR;
 279         return false;
 280     }
 281
 282     if (m_start.container() && !refNode->attached()) {
 283         // Firefox doesn't throw an exception for this case; it returns false.
 284         return false;
 285     }
 286
 287     if (refNode->document() != m_ownerDocument) {
 288         ec = WRONG_DOCUMENT_ERR;
 289         return false;
 290     }
 291
 292     ec = 0;
 293     checkNodeWOffset(refNode, offset, ec);
 294     if (ec)
 295         return false;
 296
 297     return compareBoundaryPoints(refNode, offset, m_start.container(), m_start.offset()) >= 0
 298         && compareBoundaryPoints(refNode, offset, m_end.container(), m_end.offset()) <= 0;
 299 }
 300
 301 short Range::comparePoint(Node* refNode, int offset, ExceptionCode& ec)
 302 {
 303     // http://developer.mozilla.org/en/docs/DOM:range.comparePoint
 304     // This method returns -1, 0 or 1 depending on if the point described by the
 305     // refNode node and an offset within the node is before, same as, or after the range respectively.
 306
 307     if (!refNode) {
 308         ec = NOT_FOUND_ERR;
 309         return 0;
 310     }
 311
 312     if (!m_start.container() && refNode->attached()) {
 313         ec = INVALID_STATE_ERR;
 314         return 0;
 315     }
 316
 317     if (m_start.container() && !refNode->attached()) {
 318         // Firefox doesn't throw an exception for this case; it returns -1.
 319         return -1;
 320     }
 321
 322     if (refNode->document() != m_ownerDocument) {
 323         ec = WRONG_DOCUMENT_ERR;
 324         return 0;
 325     }
 326
 327     ec = 0;
 328     checkNodeWOffset(refNode, offset, ec);
 329     if (ec)
 330         return 0;
 331
 332     // compare to start, and point comes before
 333     if (compareBoundaryPoints(refNode, offset, m_start.container(), m_start.offset()) < 0)
 334         return -1;
 335
 336     // compare to end, and point comes after
 337     if (compareBoundaryPoints(refNode, offset, m_end.container(), m_end.offset()) > 0)
 338         return 1;
 339
 340     // point is in the middle of this range, or on the boundary points
 341     return 0;
 342 }
 343
 344 Range::CompareResults Range::compareNode(Node* refNode, ExceptionCode& ec)
 345 {
 346     // http://developer.mozilla.org/en/docs/DOM:range.compareNode
 347     // This method returns 0, 1, 2, or 3 based on if the node is before, after,
 348     // before and after(surrounds), or inside the range, respectively
 349
 350     if (!refNode) {
 351         ec = NOT_FOUND_ERR;
 352         return NODE_BEFORE;
 353     }
 354
 355     if (!m_start.container() && refNode->attached()) {
 356         ec = INVALID_STATE_ERR;
 357         return NODE_BEFORE;
 358     }
 359
 360     if (m_start.container() && !refNode->attached()) {
 361         // Firefox doesn't throw an exception for this case; it returns 0.
 362         return NODE_BEFORE;
 363     }
 364
 365     if (refNode->document() != m_ownerDocument) {
 366         // Firefox doesn't throw an exception for this case; it returns 0.
 367         return NODE_BEFORE;
 368     }
 369
 370     Node* parentNode = refNode->parentNode();
 371     int nodeIndex = refNode->nodeIndex();
 372
 373     if (!parentNode) {
 374         // if the node is the top document we should return NODE_BEFORE_AND_AFTER
 375         // but we throw to match firefox behavior
 376         ec = NOT_FOUND_ERR;
 377         return NODE_BEFORE;
 378     }
 379
 380     if (comparePoint(parentNode, nodeIndex, ec) < 0) { // starts before
 381         if (comparePoint(parentNode, nodeIndex + 1, ec) > 0) // ends after the range
 382             return NODE_BEFORE_AND_AFTER;
 383         return NODE_BEFORE; // ends before or in the range
 384     } else { // starts at or after the range start
 385         if (comparePoint(parentNode, nodeIndex + 1, ec) > 0) // ends after the range
 386             return NODE_AFTER;
 387         return NODE_INSIDE; // ends inside the range
 388     }
 389 }
 390
 391
 392 short Range::compareBoundaryPoints(CompareHow how, const Range* sourceRange, ExceptionCode& ec) const
 393 {
 394     if (!m_start.container()) {
 395         ec = INVALID_STATE_ERR;
 396         return 0;
 397     }
 398
 399     if (!sourceRange) {
 400         ec = NOT_FOUND_ERR;
 401         return 0;
 402     }
 403
 404     ec = 0;
 405     Node* thisCont = commonAncestorContainer(ec);
 406     if (ec)
 407         return 0;
 408     Node* sourceCont = sourceRange->commonAncestorContainer(ec);
 409     if (ec)
 410         return 0;
 411
 412     if (thisCont->document() != sourceCont->document()) {
 413         ec = WRONG_DOCUMENT_ERR;
 414         return 0;
 415     }
 416
 417     Node* thisTop = thisCont;
 418     Node* sourceTop = sourceCont;
 419     while (thisTop->parentNode())
 420         thisTop = thisTop->parentNode();
 421     while (sourceTop->parentNode())
 422         sourceTop = sourceTop->parentNode();
 423     if (thisTop != sourceTop) { // in different DocumentFragments
 424         ec = WRONG_DOCUMENT_ERR;
 425         return 0;
 426     }
 427
 428     switch (how) {
 429         case START_TO_START:
 430             return compareBoundaryPoints(m_start.container(), m_start.offset(),
 431                 sourceRange->m_start.container(), sourceRange->m_start.offset());
 432         case START_TO_END:
 433             return compareBoundaryPoints(m_end.container(), m_end.offset(),
 434                 sourceRange->m_start.container(), sourceRange->m_start.offset());
 435         case END_TO_END:
 436             return compareBoundaryPoints(m_end.container(), m_end.offset(),
 437                 sourceRange->m_end.container(), sourceRange->m_end.offset());
 438         case END_TO_START:
 439             return compareBoundaryPoints(m_start.container(), m_start.offset(),
 440                 sourceRange->m_end.container(), sourceRange->m_end.offset());
 441     }
 442
 443     ec = SYNTAX_ERR;
 444     return 0;
 445 }
 446
 447 short Range::compareBoundaryPoints(Node* containerA, int offsetA, Node* containerB, int offsetB)
 448 {
 449     ASSERT(containerA && containerB);
 450     if (!containerA)
 451         return -1;
 452     if (!containerB)
 453         return 1;
 454     // see DOM2 traversal & range section 2.5
 455
 456     // case 1: both points have the same container
 457     if (containerA == containerB) {
 458         if (offsetA == offsetB)
 459             return 0;           // A is equal to B
 460         if (offsetA < offsetB)
 461             return -1;          // A is before B
 462         else
 463             return 1;           // A is after B
 464     }
 465
 466     // case 2: node C (container B or an ancestor) is a child node of A
 467     Node* c = containerB;
 468     while (c && c->parentNode() != containerA)
 469         c = c->parentNode();
 470     if (c) {
 471         int offsetC = 0;
 472         Node* n = containerA->firstChild();
 473         while (n != c && offsetC < offsetA) {
 474             offsetC++;
 475             n = n->nextSibling();
 476         }
 477
 478         if (offsetA <= offsetC)
 479             return -1;              // A is before B
 480         else
 481             return 1;               // A is after B
 482     }
 483
 484     // case 3: node C (container A or an ancestor) is a child node of B
 485     c = containerA;
 486     while (c && c->parentNode() != containerB)
 487         c = c->parentNode();
 488     if (c) {
 489         int offsetC = 0;
 490         Node* n = containerB->firstChild();
 491         while (n != c && offsetC < offsetB) {
 492             offsetC++;
 493             n = n->nextSibling();
 494         }
 495
 496         if (offsetC < offsetB)
 497             return -1;              // A is before B
 498         else
 499             return 1;               // A is after B
 500     }
 501
 502     // case 4: containers A & B are siblings, or children of siblings
 503     // ### we need to do a traversal here instead
 504     Node* commonAncestor = commonAncestorContainer(containerA, containerB);
 505     if (!commonAncestor)
 506         return 0;
 507     Node* childA = containerA;
 508     while (childA && childA->parentNode() != commonAncestor)
 509         childA = childA->parentNode();
 510     if (!childA)
 511         childA = commonAncestor;
 512     Node* childB = containerB;
 513     while (childB && childB->parentNode() != commonAncestor)
 514         childB = childB->parentNode();
 515     if (!childB)
 516         childB = commonAncestor;
 517
 518     if (childA == childB)
 519         return 0; // A is equal to B
 520
 521     Node* n = commonAncestor->firstChild();
 522     while (n) {
 523         if (n == childA)
 524             return -1; // A is before B
 525         if (n == childB)
 526             return 1; // A is after B
 527         n = n->nextSibling();
 528     }
 529
 530     // Should never reach this point.
 531     ASSERT_NOT_REACHED();
 532     return 0;
 533 }
 534
 535 short Range::compareBoundaryPoints(const Position& a, const Position& b)
 536 {
 537     return compareBoundaryPoints(a.container.get(), a.posOffset, b.container.get(), b.posOffset);
 538 }
 539
 540 bool Range::boundaryPointsValid() const
 541 {
 542     return m_start.container() && compareBoundaryPoints(m_start.container(), m_start.offset(), m_end.container(), m_end.offset()) <= 0;
 543 }
 544
 545 void Range::deleteContents(ExceptionCode& ec)
 546 {
 547     checkDeleteExtract(ec);
 548     if (ec)
 549         return;
 550
 551     processContents(DELETE_CONTENTS, ec);
 552 }
 553
 554 bool Range::intersectsNode(Node* refNode, ExceptionCode& ec)
 555 {
 556     // http://developer.mozilla.org/en/docs/DOM:range.intersectsNode
 557     // Returns a bool if the node intersects the range.
 558
 559     if (!refNode) {
 560         ec = NOT_FOUND_ERR;
 561         return false;
 562     }
 563
 564     if (!m_start.container() && refNode->attached()
 565             || m_start.container() && !refNode->attached()
 566             || refNode->document() != m_ownerDocument) {
 567         // Firefox doesn't throw an exception for these cases; it returns false.
 568         return false;
 569     }
 570
 571     Node* parentNode = refNode->parentNode();
 572     int nodeIndex = refNode->nodeIndex();
 573
 574     if (!parentNode) {
 575         // if the node is the top document we should return NODE_BEFORE_AND_AFTER
 576         // but we throw to match firefox behavior
 577         ec = NOT_FOUND_ERR;
 578         return false;
 579     }
 580
 581     if (comparePoint(parentNode, nodeIndex, ec) < 0 && // starts before start
 582         comparePoint(parentNode, nodeIndex + 1, ec) < 0) { // ends before start
 583         return false;
 584     } else if (comparePoint(parentNode, nodeIndex, ec) > 0 && // starts after end
 585                comparePoint(parentNode, nodeIndex + 1, ec) > 0) { // ends after end
 586         return false;
 587     }
 588
 589     return true; // all other cases
 590 }
 591
 592 PassRefPtr<DocumentFragment> Range::processContents(ActionType action, ExceptionCode& ec)
 593 {
 594     // FIXME: To work properly with mutation events, we will have to take into account
 595     // situations where the tree is being transformed while we work on it - ugh!
 596
 597     RefPtr<DocumentFragment> fragment;
 598     if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS)
 599         fragment = new DocumentFragment(m_ownerDocument.get());
 600
 601     ec = 0;
 602     if (collapsed(ec))
 603         return fragment.release();
 604     if (ec)
 605         return 0;
 606
 607     Node* commonRoot = commonAncestorContainer(ec);
 608     if (ec)
 609         return 0;
 610     ASSERT(commonRoot);
 611
 612     // what is the highest node that partially selects the start of the range?
 613     Node* partialStart = 0;
 614     if (m_start.container() != commonRoot) {
 615         partialStart = m_start.container();
 616         while (partialStart->parentNode() != commonRoot)
 617             partialStart = partialStart->parentNode();
 618     }
 619
 620     // what is the highest node that partially selects the end of the range?
 621     Node* partialEnd = 0;
 622     if (m_end.container() != commonRoot) {
 623         partialEnd = m_end.container();
 624         while (partialEnd->parentNode() != commonRoot)
 625             partialEnd = partialEnd->parentNode();
 626     }
 627
 628     // Simple case: the start and end containers are the same. We just grab
 629     // everything >= start offset and < end offset
 630     if (m_start.container() == m_end.container()) {
 631         Node::NodeType startNodeType = m_start.container()->nodeType();
 632         if (startNodeType == Node::TEXT_NODE || startNodeType == Node::CDATA_SECTION_NODE || startNodeType == Node::COMMENT_NODE) {
 633             if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) {
 634                 RefPtr<CharacterData> c = static_pointer_cast<CharacterData>(m_start.container()->cloneNode(true));
 635                 c->deleteData(m_end.offset(), c->length() - m_end.offset(), ec);
 636                 c->deleteData(0, m_start.offset(), ec);
 637                 fragment->appendChild(c.release(), ec);
 638             }
 639             if (action == EXTRACT_CONTENTS || action == DELETE_CONTENTS)
 640                 static_cast<CharacterData*>(m_start.container())->deleteData(m_start.offset(), m_end.offset() - m_start.offset(), ec);
 641         } else if (startNodeType == Node::PROCESSING_INSTRUCTION_NODE) {
 642             if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) {
 643                 RefPtr<ProcessingInstruction> c = static_pointer_cast<ProcessingInstruction>(m_start.container()->cloneNode(true));
 644                 c->setData(c->data().substring(m_start.offset(), m_end.offset() - m_start.offset()), ec);
 645                 fragment->appendChild(c.release(), ec);
 646             }
 647             if (action == EXTRACT_CONTENTS || action == DELETE_CONTENTS) {
 648                 ProcessingInstruction* pi = static_cast<ProcessingInstruction*>(m_start.container());
 649                 String data(pi->data());
 650                 data.remove(m_start.offset(), m_end.offset() - m_start.offset());
 651                 pi->setData(data, ec);
 652             }
 653         } else {
 654             Node* n = m_start.container()->firstChild();
 655             int i;
 656             for (i = 0; n && i < m_start.offset(); i++) // skip until start offset
 657                 n = n->nextSibling();
 658             int endOffset = m_end.offset();
 659             while (n && i < endOffset) { // delete until end offset
 660                 Node* next = n->nextSibling();
 661                 if (action == EXTRACT_CONTENTS)
 662                     fragment->appendChild(n, ec); // will remove n from its parent
 663                 else if (action == CLONE_CONTENTS)
 664                     fragment->appendChild(n->cloneNode(true), ec);
 665                 else
 666                     m_start.container()->removeChild(n, ec);
 667                 n = next;
 668                 i++;
 669             }
 670         }
 671         return fragment.release();
 672     }
 673
 674     // Complex case: Start and end containers are different.
 675     // There are three possiblities here:
 676     // 1. Start container == commonRoot (End container must be a descendant)
 677     // 2. End container == commonRoot (Start container must be a descendant)
 678     // 3. Neither is commonRoot, they are both descendants
 679     //
 680     // In case 3, we grab everything after the start (up until a direct child
 681     // of commonRoot) into leftContents, and everything before the end (up until
 682     // a direct child of commonRoot) into rightContents. Then we process all
 683     // commonRoot children between leftContents and rightContents
 684     //
 685     // In case 1 or 2, we skip either processing of leftContents or rightContents,
 686     // in which case the last lot of nodes either goes from the first or last
 687     // child of commonRoot.
 688     //
 689     // These are deleted, cloned, or extracted (i.e. both) depending on action.
 690
 691     RefPtr<Node> leftContents;
 692     if (m_start.container() != commonRoot) {
 693         // process the left-hand side of the range, up until the last ancestor of
 694         // start container before commonRoot
 695         Node::NodeType startNodeType = m_start.container()->nodeType();
 696         if (startNodeType == Node::TEXT_NODE || startNodeType == Node::CDATA_SECTION_NODE || startNodeType == Node::COMMENT_NODE) {
 697             if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) {
 698                 RefPtr<CharacterData> c = static_pointer_cast<CharacterData>(m_start.container()->cloneNode(true));
 699                 c->deleteData(0, m_start.offset(), ec);
 700                 leftContents = c.release();
 701             }
 702             if (action == EXTRACT_CONTENTS || action == DELETE_CONTENTS)
 703                 static_cast<CharacterData*>(m_start.container())->deleteData(
 704                     m_start.offset(), static_cast<CharacterData*>(m_start.container())->length() - m_start.offset(), ec);
 705         } else if (startNodeType == Node::PROCESSING_INSTRUCTION_NODE) {
 706             if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) {
 707                 RefPtr<ProcessingInstruction> c = static_pointer_cast<ProcessingInstruction>(m_start.container()->cloneNode(true));
 708                 c->setData(c->data().substring(m_start.offset()), ec);
 709                 leftContents = c.release();
 710             }
 711             if (action == EXTRACT_CONTENTS || action == DELETE_CONTENTS) {
 712                 ProcessingInstruction* pi = static_cast<ProcessingInstruction*>(m_start.container());
 713                 String data(pi->data());
 714                 pi->setData(data.left(m_start.offset()), ec);
 715             }
 716         } else {
 717             if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS)
 718                 leftContents = m_start.container()->cloneNode(false);
 719             Node* n = m_start.container()->firstChild();
 720             for (int i = 0; n && i < m_start.offset(); i++) // skip until start offset
 721                 n = n->nextSibling();
 722             while (n) { // process until end
 723                 Node* next = n->nextSibling();
 724                 if (action == EXTRACT_CONTENTS)
 725                     leftContents->appendChild(n, ec); // will remove n from start container
 726                 else if (action == CLONE_CONTENTS)
 727                     leftContents->appendChild(n->cloneNode(true), ec);
 728                 else
 729                     m_start.container()->removeChild(n, ec);
 730                 n = next;
 731             }
 732         }
 733
 734         Node* leftParent = m_start.container()->parentNode();
 735         Node* n = m_start.container()->nextSibling();
 736         for (; leftParent != commonRoot; leftParent = leftParent->parentNode()) {
 737             if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) {
 738                 RefPtr<Node> leftContentsParent = leftParent->cloneNode(false);
 739                 leftContentsParent->appendChild(leftContents,ec);
 740                 leftContents = leftContentsParent;
 741             }
 742
 743             Node* next;
 744             for (; n; n = next) {
 745                 next = n->nextSibling();
 746                 if (action == EXTRACT_CONTENTS)
 747                     leftContents->appendChild(n,ec); // will remove n from leftParent
 748                 else if (action == CLONE_CONTENTS)
 749                     leftContents->appendChild(n->cloneNode(true),ec);
 750                 else
 751                     leftParent->removeChild(n,ec);
 752             }
 753             n = leftParent->nextSibling();
 754         }
 755     }
 756
 757     RefPtr<Node> rightContents;
 758     if (m_end.container() != commonRoot) {
 759         // delete the right-hand side of the range, up until the last ancestor of
 760         // end container before commonRoot
 761         Node::NodeType endNodeType = m_end.container()->nodeType();
 762         if (endNodeType == Node::TEXT_NODE || endNodeType == Node::CDATA_SECTION_NODE || endNodeType == Node::COMMENT_NODE) {
 763             if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) {
 764                 RefPtr<CharacterData> c = static_pointer_cast<CharacterData>(m_end.container()->cloneNode(true));
 765                 c->deleteData(m_end.offset(), static_cast<CharacterData*>(m_end.container())->length() - m_end.offset(), ec);
 766                 rightContents = c;
 767             }
 768             if (action == EXTRACT_CONTENTS || action == DELETE_CONTENTS)
 769                 static_cast<CharacterData*>(m_end.container())->deleteData(0, m_end.offset(), ec);
 770         } else if (endNodeType == Node::PROCESSING_INSTRUCTION_NODE) {
 771             if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) {
 772                 RefPtr<ProcessingInstruction> c = static_pointer_cast<ProcessingInstruction>(m_end.container()->cloneNode(true));
 773                 c->setData(c->data().left(m_end.offset()), ec);
 774                 rightContents = c.release();
 775             }
 776             if (action == EXTRACT_CONTENTS || action == DELETE_CONTENTS) {
 777                 ProcessingInstruction* pi = static_cast<ProcessingInstruction*>(m_end.container());
 778                 pi->setData(pi->data().substring(m_end.offset()), ec);
 779             }
 780         } else {
 781             if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS)
 782                 rightContents = m_end.container()->cloneNode(false);
 783             Node* n = m_end.container()->firstChild();
 784             if (n && m_end.offset()) {
 785                 for (int i = 0; i + 1 < m_end.offset(); i++) { // skip to end.offset()
 786                     Node* next = n->nextSibling();
 787                     if (!next)
 788                         break;
 789                     n = next;
 790                 }
 791                 Node* prev;
 792                 for (; n; n = prev) {
 793                     prev = n->previousSibling();
 794                     if (action == EXTRACT_CONTENTS)
 795                         rightContents->insertBefore(n, rightContents->firstChild(), ec); // will remove n from its parent
 796                     else if (action == CLONE_CONTENTS)
 797                         rightContents->insertBefore(n->cloneNode(true), rightContents->firstChild(), ec);
 798                     else
 799                         m_end.container()->removeChild(n, ec);
 800                 }
 801             }
 802         }
 803
 804         Node* rightParent = m_end.container()->parentNode();
 805         Node* n = m_end.container()->previousSibling();
 806         for (; rightParent != commonRoot; rightParent = rightParent->parentNode()) {
 807             if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) {
 808                 RefPtr<Node> rightContentsParent = rightParent->cloneNode(false);
 809                 rightContentsParent->appendChild(rightContents,ec);
 810                 rightContents = rightContentsParent;
 811             }
 812             Node* prev;
 813             for (; n; n = prev) {
 814                 prev = n->previousSibling();
 815                 if (action == EXTRACT_CONTENTS)
 816                     rightContents->insertBefore(n, rightContents->firstChild(), ec); // will remove n from its parent
 817                 else if (action == CLONE_CONTENTS)
 818                     rightContents->insertBefore(n->cloneNode(true), rightContents->firstChild(), ec);
 819                 else
 820                     rightParent->removeChild(n, ec);
 821             }
 822             n = rightParent->previousSibling();
 823         }
 824     }
 825
 826     // delete all children of commonRoot between the start and end container
 827
 828     Node* processStart; // child of commonRoot
 829     if (m_start.container() == commonRoot) {
 830         processStart = m_start.container()->firstChild();
 831         for (int i = 0; i < m_start.offset(); i++)
 832             processStart = processStart->nextSibling();
 833     } else {
 834         processStart = m_start.container();
 835         while (processStart->parentNode() != commonRoot)
 836             processStart = processStart->parentNode();
 837         processStart = processStart->nextSibling();
 838     }
 839     Node* processEnd; // child of commonRoot
 840     if (m_end.container() == commonRoot) {
 841         processEnd = m_end.container()->firstChild();
 842         for (int i = 0; i < m_end.offset(); i++)
 843             processEnd = processEnd->nextSibling();
 844     } else {
 845         processEnd = m_end.container();
 846         while (processEnd->parentNode() != commonRoot)
 847             processEnd = processEnd->parentNode();
 848     }
 849
 850     // Now add leftContents, stuff in between, and rightContents to the fragment
 851     // (or just delete the stuff in between)
 852
 853     if ((action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) && leftContents)
 854         fragment->appendChild(leftContents, ec);
 855
 856     Node* next;
 857     Node* n;
 858     if (processStart) {
 859         for (n = processStart; n && n != processEnd; n = next) {
 860             next = n->nextSibling();
 861             if (action == EXTRACT_CONTENTS)
 862                 fragment->appendChild(n, ec); // will remove from commonRoot
 863             else if (action == CLONE_CONTENTS)
 864                 fragment->appendChild(n->cloneNode(true), ec);
 865             else
 866                 commonRoot->removeChild(n, ec);
 867         }
 868     }
 869
 870     if ((action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) && rightContents)
 871         fragment->appendChild(rightContents, ec);
 872
 873     return fragment.release();
 874 }
 875
 876 PassRefPtr<DocumentFragment> Range::extractContents(ExceptionCode& ec)
 877 {
 878     checkDeleteExtract(ec);
 879     if (ec)
 880         return 0;
 881
 882     return processContents(EXTRACT_CONTENTS, ec);
 883 }
 884
 885 PassRefPtr<DocumentFragment> Range::cloneContents(ExceptionCode& ec)
 886 {
 887     if (!m_start.container()) {
 888         ec = INVALID_STATE_ERR;
 889         return 0;
 890     }
 891
 892     return processContents(CLONE_CONTENTS, ec);
 893 }
 894
 895 void Range::insertNode(PassRefPtr<Node> prpNewNode, ExceptionCode& ec)
 896 {
 897     RefPtr<Node> newNode = prpNewNode;
 898
 899     ec = 0;
 900
 901     if (!m_start.container()) {
 902         ec = INVALID_STATE_ERR;
 903         return;
 904     }
 905
 906     if (!newNode) {
 907         ec = NOT_FOUND_ERR;
 908         return;
 909     }
 910
 911     // NO_MODIFICATION_ALLOWED_ERR: Raised if an ancestor container of either boundary-point of
 912     // the Range is read-only.
 913     if (containedByReadOnly()) {
 914         ec = NO_MODIFICATION_ALLOWED_ERR;
 915         return;
 916     }
 917
 918     // WRONG_DOCUMENT_ERR: Raised if newParent and the container of the start of the Range were
 919     // not created from the same document.
 920     if (newNode->document() != m_start.container()->document()) {
 921         ec = WRONG_DOCUMENT_ERR;
 922         return;
 923     }
 924
 925     // HIERARCHY_REQUEST_ERR: Raised if the container of the start of the Range is of a type that
 926     // does not allow children of the type of newNode or if newNode is an ancestor of the container.
 927
 928     // an extra one here - if a text node is going to split, it must have a parent to insert into
 929     bool startIsText = m_start.container()->isTextNode();
 930     if (startIsText && !m_start.container()->parentNode()) {
 931         ec = HIERARCHY_REQUEST_ERR;
 932         return;
 933     }
 934
 935     // In the case where the container is a text node, we check against the container's parent, because
 936     // text nodes get split up upon insertion.
 937     Node* checkAgainst;
 938     if (startIsText)
 939         checkAgainst = m_start.container()->parentNode();
 940     else
 941         checkAgainst = m_start.container();
 942
 943     Node::NodeType newNodeType = newNode->nodeType();
 944     int numNewChildren;
 945     if (newNodeType == Node::DOCUMENT_FRAGMENT_NODE) {
 946         // check each child node, not the DocumentFragment itself
 947         numNewChildren = 0;
 948         for (Node* c = newNode->firstChild(); c; c = c->nextSibling()) {
 949             if (!checkAgainst->childTypeAllowed(c->nodeType())) {
 950                 ec = HIERARCHY_REQUEST_ERR;
 951                 return;
 952             }
 953             ++numNewChildren;
 954         }
 955     } else {
 956         numNewChildren = 1;
 957         if (!checkAgainst->childTypeAllowed(newNodeType)) {
 958             ec = HIERARCHY_REQUEST_ERR;
 959             return;
 960         }
 961     }
 962
 963     for (Node* n = m_start.container(); n; n = n->parentNode()) {
 964         if (n == newNode) {
 965             ec = HIERARCHY_REQUEST_ERR;
 966             return;
 967         }
 968     }
 969
 970     // INVALID_NODE_TYPE_ERR: Raised if newNode is an Attr, Entity, Notation, or Document node.
 971     if (newNodeType == Node::ATTRIBUTE_NODE || newNodeType == Node::ENTITY_NODE
 972             || newNodeType == Node::NOTATION_NODE || newNodeType == Node::DOCUMENT_NODE) {
 973         ec = RangeException::INVALID_NODE_TYPE_ERR;
 974         return;
 975     }
 976
 977     bool collapsed = m_start == m_end;
 978     if (startIsText) {
 979         RefPtr<Text> newText = static_cast<Text*>(m_start.container())->splitText(m_start.offset(), ec);
 980         if (ec)
 981             return;
 982         m_start.container()->parentNode()->insertBefore(newNode.release(), newText.get(), ec);
 983         if (ec)
 984             return;
 985
 986         // This special case doesn't seem to match the DOM specification, but it's currently required
 987         // to pass Acid3. We might later decide to remove this.
 988         if (collapsed)
 989             m_end.setToChild(newText.get());
 990     } else {
 991         RefPtr<Node> lastChild;
 992         if (collapsed)
 993             lastChild = (newNodeType == Node::DOCUMENT_FRAGMENT_NODE) ? newNode->lastChild() : newNode;
 994
 995         int startOffset = m_start.offset();
 996         m_start.container()->insertBefore(newNode.release(), m_start.container()->childNode(startOffset), ec);
 997         if (ec)
 998             return;
 999
1000         // This special case doesn't seem to match the DOM specification, but it's currently required
1001         // to pass Acid3. We might later decide to remove this.
1002         if (collapsed)
1003             m_end.set(m_start.container(), startOffset + numNewChildren, lastChild.get());
1004     }
1005 }
1006
1007 String Range::toString(ExceptionCode& ec) const
1008 {
1009     if (!m_start.container()) {
1010         ec = INVALID_STATE_ERR;
1011         return String();
1012     }
1013
1014     Vector<UChar> result;
1015
1016     Node* pastLast = pastLastNode();
1017     for (Node* n = firstNode(); n != pastLast; n = n->traverseNextNode()) {
1018         if (n->nodeType() == Node::TEXT_NODE || n->nodeType() == Node::CDATA_SECTION_NODE) {
1019             String data = static_cast<CharacterData*>(n)->data();
1020             int length = data.length();
1021             int start = (n == m_start.container()) ? min(max(0, m_start.offset()), length) : 0;
1022             int end = (n == m_end.container()) ? min(max(start, m_end.offset()), length) : length;
1023             result.append(data.characters() + start, end - start);
1024         }
1025     }
1026
1027     return String::adopt(result);
1028 }
1029
1030 String Range::toHTML() const
1031 {
1032     return createMarkup(this);
1033 }
1034
1035 String Range::text() const
1036 {
1037     if (!m_start.container())
1038         return String();
1039
1040     // We need to update layout, since plainText uses line boxes in the render tree.
1041     // FIXME: As with innerText, we'd like this to work even if there are no render objects.
1042     m_start.container()->document()->updateLayout();
1043
1044     return plainText(this);
1045 }
1046
1047 PassRefPtr<DocumentFragment> Range::createContextualFragment(const String& markup, ExceptionCode& ec) const
1048 {
1049     if (!m_start.container()) {
1050         ec = INVALID_STATE_ERR;
1051         return 0;
1052     }
1053
1054     Node* element = m_start.container()->isElementNode() ? m_start.container() : m_start.container()->parentNode();
1055     if (!element || !element->isHTMLElement()) {
1056         ec = NOT_SUPPORTED_ERR;
1057         return 0;
1058     }
1059
1060     RefPtr<DocumentFragment> fragment = static_cast<HTMLElement*>(element)->createContextualFragment(markup);
1061     if (!fragment) {
1062         ec = NOT_SUPPORTED_ERR;
1063         return 0;
1064     }
1065
1066     return fragment.release();
1067 }
1068
1069
1070 void Range::detach(ExceptionCode& ec)
1071 {
1072     if (!m_start.container()) {
1073         ec = INVALID_STATE_ERR;
1074         return;
1075     }
1076
1077     m_ownerDocument->detachRange(this);
1078
1079     m_start.clear();
1080     m_end.clear();
1081 }
1082
1083 Node* Range::checkNodeWOffset(Node* n, int offset, ExceptionCode& ec) const
1084 {
1085     switch (n->nodeType()) {
1086         case Node::DOCUMENT_TYPE_NODE:
1087         case Node::ENTITY_NODE:
1088         case Node::NOTATION_NODE:
1089             ec = RangeException::INVALID_NODE_TYPE_ERR;
1090             return 0;
1091         case Node::CDATA_SECTION_NODE:
1092         case Node::COMMENT_NODE:
1093         case Node::TEXT_NODE:
1094             if (static_cast<unsigned>(offset) > static_cast<CharacterData*>(n)->length())
1095                 ec = INDEX_SIZE_ERR;
1096             return 0;
1097         case Node::PROCESSING_INSTRUCTION_NODE:
1098             if (static_cast<unsigned>(offset) > static_cast<ProcessingInstruction*>(n)->data().length())
1099                 ec = INDEX_SIZE_ERR;
1100             return 0;
1101         case Node::ATTRIBUTE_NODE:
1102         case Node::DOCUMENT_FRAGMENT_NODE:
1103         case Node::DOCUMENT_NODE:
1104         case Node::ELEMENT_NODE:
1105         case Node::ENTITY_REFERENCE_NODE:
1106         case Node::XPATH_NAMESPACE_NODE: {
1107             if (!offset)
1108                 return 0;
1109             Node* childBefore = n->childNode(offset - 1);
1110             if (!childBefore)
1111                 ec = INDEX_SIZE_ERR;
1112             return childBefore;
1113         }
1114     }
1115     ASSERT_NOT_REACHED();
1116     return 0;
1117 }
1118
1119 void Range::checkNodeBA(Node* n, ExceptionCode& ec) const
1120 {
1121     // INVALID_NODE_TYPE_ERR: Raised if the root container of refNode is not an
1122     // Attr, Document or DocumentFragment node or part of a shadow DOM tree
1123     // or if refNode is a Document, DocumentFragment, Attr, Entity, or Notation node.
1124
1125     switch (n->nodeType()) {
1126         case Node::ATTRIBUTE_NODE:
1127         case Node::DOCUMENT_FRAGMENT_NODE:
1128         case Node::DOCUMENT_NODE:
1129         case Node::ENTITY_NODE:
1130         case Node::NOTATION_NODE:
1131             ec = RangeException::INVALID_NODE_TYPE_ERR;
1132             return;
1133         case Node::CDATA_SECTION_NODE:
1134         case Node::COMMENT_NODE:
1135         case Node::DOCUMENT_TYPE_NODE:
1136         case Node::ELEMENT_NODE:
1137         case Node::ENTITY_REFERENCE_NODE:
1138         case Node::PROCESSING_INSTRUCTION_NODE:
1139         case Node::TEXT_NODE:
1140         case Node::XPATH_NAMESPACE_NODE:
1141             break;
1142     }
1143
1144     Node* root = n;
1145     while (Node* parent = root->parentNode())
1146         root = parent;
1147
1148     switch (root->nodeType()) {
1149         case Node::ATTRIBUTE_NODE:
1150         case Node::DOCUMENT_NODE:
1151         case Node::DOCUMENT_FRAGMENT_NODE:
1152             break;
1153         case Node::CDATA_SECTION_NODE:
1154         case Node::COMMENT_NODE:
1155         case Node::DOCUMENT_TYPE_NODE:
1156         case Node::ELEMENT_NODE:
1157         case Node::ENTITY_NODE:
1158         case Node::ENTITY_REFERENCE_NODE:
1159         case Node::NOTATION_NODE:
1160         case Node::PROCESSING_INSTRUCTION_NODE:
1161         case Node::TEXT_NODE:
1162         case Node::XPATH_NAMESPACE_NODE:
1163             if (root->isShadowNode())
1164                 break;
1165             ec = RangeException::INVALID_NODE_TYPE_ERR;
1166             return;
1167     }
1168 }
1169
1170 PassRefPtr<Range> Range::cloneRange(ExceptionCode& ec) const
1171 {
1172     if (!m_start.container()) {
1173         ec = INVALID_STATE_ERR;
1174         return 0;
1175     }
1176
1177     return Range::create(m_ownerDocument, m_start.container(), m_start.offset(), m_end.container(), m_end.offset());
1178 }
1179
1180 void Range::setStartAfter(Node* refNode, ExceptionCode& ec)
1181 {
1182     if (!m_start.container()) {
1183         ec = INVALID_STATE_ERR;
1184         return;
1185     }
1186
1187     if (!refNode) {
1188         ec = NOT_FOUND_ERR;
1189         return;
1190     }
1191
1192     if (refNode->document() != m_ownerDocument) {
1193         ec = WRONG_DOCUMENT_ERR;
1194         return;
1195     }
1196
1197     ec = 0;
1198     checkNodeBA(refNode, ec);
1199     if (ec)
1200         return;
1201
1202     setStart(refNode->parentNode(), refNode->nodeIndex() + 1, ec);
1203 }
1204
1205 void Range::setEndBefore(Node* refNode, ExceptionCode& ec)
1206 {
1207     if (!m_start.container()) {
1208         ec = INVALID_STATE_ERR;
1209         return;
1210     }
1211
1212     if (!refNode) {
1213         ec = NOT_FOUND_ERR;
1214         return;
1215     }
1216
1217     if (refNode->document() != m_ownerDocument) {
1218         ec = WRONG_DOCUMENT_ERR;
1219         return;
1220     }
1221
1222     ec = 0;
1223     checkNodeBA(refNode, ec);
1224     if (ec)
1225         return;
1226
1227     setEnd(refNode->parentNode(), refNode->nodeIndex(), ec);
1228 }
1229
1230 void Range::setEndAfter(Node* refNode, ExceptionCode& ec)
1231 {
1232     if (!m_start.container()) {
1233         ec = INVALID_STATE_ERR;
1234         return;
1235     }
1236
1237     if (!refNode) {
1238         ec = NOT_FOUND_ERR;
1239         return;
1240     }
1241
1242     if (refNode->document() != m_ownerDocument) {
1243         ec = WRONG_DOCUMENT_ERR;
1244         return;
1245     }
1246
1247     ec = 0;
1248     checkNodeBA(refNode, ec);
1249     if (ec)
1250         return;
1251
1252     setEnd(refNode->parentNode(), refNode->nodeIndex() + 1, ec);
1253
1254 }
1255
1256 void Range::selectNode(Node* refNode, ExceptionCode& ec)
1257 {
1258     if (!m_start.container()) {
1259         ec = INVALID_STATE_ERR;
1260         return;
1261     }
1262
1263     if (!refNode) {
1264         ec = NOT_FOUND_ERR;
1265         return;
1266     }
1267
1268     // INVALID_NODE_TYPE_ERR: Raised if an ancestor of refNode is an Entity, Notation or
1269     // DocumentType node or if refNode is a Document, DocumentFragment, Attr, Entity, or Notation
1270     // node.
1271     for (Node* anc = refNode->parentNode(); anc; anc = anc->parentNode()) {
1272         switch (anc->nodeType()) {
1273             case Node::ATTRIBUTE_NODE:
1274             case Node::CDATA_SECTION_NODE:
1275             case Node::COMMENT_NODE:
1276             case Node::DOCUMENT_FRAGMENT_NODE:
1277             case Node::DOCUMENT_NODE:
1278             case Node::ELEMENT_NODE:
1279             case Node::ENTITY_REFERENCE_NODE:
1280             case Node::PROCESSING_INSTRUCTION_NODE:
1281             case Node::TEXT_NODE:
1282             case Node::XPATH_NAMESPACE_NODE:
1283                 break;
1284             case Node::DOCUMENT_TYPE_NODE:
1285             case Node::ENTITY_NODE:
1286             case Node::NOTATION_NODE:
1287                 ec = RangeException::INVALID_NODE_TYPE_ERR;
1288                 return;
1289         }
1290     }
1291
1292     switch (refNode->nodeType()) {
1293         case Node::CDATA_SECTION_NODE:
1294         case Node::COMMENT_NODE:
1295         case Node::DOCUMENT_TYPE_NODE:
1296         case Node::ELEMENT_NODE:
1297         case Node::ENTITY_REFERENCE_NODE:
1298         case Node::PROCESSING_INSTRUCTION_NODE:
1299         case Node::TEXT_NODE:
1300         case Node::XPATH_NAMESPACE_NODE:
1301             break;
1302         case Node::ATTRIBUTE_NODE:
1303         case Node::DOCUMENT_FRAGMENT_NODE:
1304         case Node::DOCUMENT_NODE:
1305         case Node::ENTITY_NODE:
1306         case Node::NOTATION_NODE:
1307             ec = RangeException::INVALID_NODE_TYPE_ERR;
1308             return;
1309     }
1310
1311     ec = 0;
1312     setStartBefore(refNode, ec);
1313     if (ec)
1314         return;
1315     setEndAfter(refNode, ec);
1316 }
1317
1318 void Range::selectNodeContents(Node* refNode, ExceptionCode& ec)
1319 {
1320     if (!m_start.container()) {
1321         ec = INVALID_STATE_ERR;
1322         return;
1323     }
1324
1325     if (!refNode) {
1326         ec = NOT_FOUND_ERR;
1327         return;
1328     }
1329
1330     // INVALID_NODE_TYPE_ERR: Raised if refNode or an ancestor of refNode is an Entity, Notation
1331     // or DocumentType node.
1332     for (Node* n = refNode; n; n = n->parentNode()) {
1333         switch (n->nodeType()) {
1334             case Node::ATTRIBUTE_NODE:
1335             case Node::CDATA_SECTION_NODE:
1336             case Node::COMMENT_NODE:
1337             case Node::DOCUMENT_FRAGMENT_NODE:
1338             case Node::DOCUMENT_NODE:
1339             case Node::ELEMENT_NODE:
1340             case Node::ENTITY_REFERENCE_NODE:
1341             case Node::PROCESSING_INSTRUCTION_NODE:
1342             case Node::TEXT_NODE:
1343             case Node::XPATH_NAMESPACE_NODE:
1344                 break;
1345             case Node::DOCUMENT_TYPE_NODE:
1346             case Node::ENTITY_NODE:
1347             case Node::NOTATION_NODE:
1348                 ec = RangeException::INVALID_NODE_TYPE_ERR;
1349                 return;
1350         }
1351     }
1352
1353     m_start.setToStart(refNode);
1354     m_end.setToEnd(refNode);
1355 }
1356
1357 void Range::surroundContents(PassRefPtr<Node> passNewParent, ExceptionCode& ec)
1358 {
1359     RefPtr<Node> newParent = passNewParent;
1360
1361     if (!m_start.container()) {
1362         ec = INVALID_STATE_ERR;
1363         return;
1364     }
1365
1366     if (!newParent) {
1367         ec = NOT_FOUND_ERR;
1368         return;
1369     }
1370
1371     // INVALID_NODE_TYPE_ERR: Raised if node is an Attr, Entity, DocumentType, Notation,
1372     // Document, or DocumentFragment node.
1373     switch (newParent->nodeType()) {
1374         case Node::ATTRIBUTE_NODE:
1375         case Node::DOCUMENT_FRAGMENT_NODE:
1376         case Node::DOCUMENT_NODE:
1377         case Node::DOCUMENT_TYPE_NODE:
1378         case Node::ENTITY_NODE:
1379         case Node::NOTATION_NODE:
1380             ec = RangeException::INVALID_NODE_TYPE_ERR;
1381             return;
1382         case Node::CDATA_SECTION_NODE:
1383         case Node::COMMENT_NODE:
1384         case Node::ELEMENT_NODE:
1385         case Node::ENTITY_REFERENCE_NODE:
1386         case Node::PROCESSING_INSTRUCTION_NODE:
1387         case Node::TEXT_NODE:
1388         case Node::XPATH_NAMESPACE_NODE:
1389             break;
1390     }
1391
1392     // NO_MODIFICATION_ALLOWED_ERR: Raised if an ancestor container of either boundary-point of
1393     // the Range is read-only.
1394     if (containedByReadOnly()) {
1395         ec = NO_MODIFICATION_ALLOWED_ERR;
1396         return;
1397     }
1398
1399     // WRONG_DOCUMENT_ERR: Raised if newParent and the container of the start of the Range were
1400     // not created from the same document.
1401     if (newParent->document() != m_start.container()->document()) {
1402         ec = WRONG_DOCUMENT_ERR;
1403         return;
1404     }
1405
1406     // Raise a HIERARCHY_REQUEST_ERR if m_start.container() doesn't accept children like newParent.
1407     Node* parentOfNewParent = m_start.container();
1408
1409     // If m_start.container() is a character data node, it will be split and it will be its parent that will
1410     // need to accept newParent (or in the case of a comment, it logically "would" be inserted into the parent,
1411     // although this will fail below for another reason).
1412     if (parentOfNewParent->isCharacterDataNode())
1413         parentOfNewParent = parentOfNewParent->parentNode();
1414     if (!parentOfNewParent->childTypeAllowed(newParent->nodeType())) {
1415         ec = HIERARCHY_REQUEST_ERR;
1416         return;
1417     }
1418
1419     if (m_start.container() == newParent || m_start.container()->isDescendantOf(newParent.get())) {
1420         ec = HIERARCHY_REQUEST_ERR;
1421         return;
1422     }
1423
1424     // FIXME: Do we need a check if the node would end up with a child node of a type not
1425     // allowed by the type of node?
1426
1427     // BAD_BOUNDARYPOINTS_ERR: Raised if the Range partially selects a non-Text node.
1428     if (m_start.container()->nodeType() != Node::TEXT_NODE) {
1429         if (m_start.offset() > 0 && m_start.offset() < maxStartOffset()) {
1430             ec = RangeException::BAD_BOUNDARYPOINTS_ERR;
1431             return;
1432         }
1433     }
1434     if (m_end.container()->nodeType() != Node::TEXT_NODE) {
1435         if (m_end.offset() > 0 && m_end.offset() < maxEndOffset()) {
1436             ec = RangeException::BAD_BOUNDARYPOINTS_ERR;
1437             return;
1438         }
1439     }
1440
1441     ec = 0;
1442     while (Node* n = newParent->firstChild()) {
1443         newParent->removeChild(n, ec);
1444         if (ec)
1445             return;
1446     }
1447     RefPtr<DocumentFragment> fragment = extractContents(ec);
1448     if (ec)
1449         return;
1450     insertNode(newParent, ec);
1451     if (ec)
1452         return;
1453     newParent->appendChild(fragment.release(), ec);
1454     if (ec)
1455         return;
1456     selectNode(newParent.get(), ec);
1457 }
1458
1459 void Range::setStartBefore(Node* refNode, ExceptionCode& ec)
1460 {
1461     if (!m_start.container()) {
1462         ec = INVALID_STATE_ERR;
1463         return;
1464     }
1465
1466     if (!refNode) {
1467         ec = NOT_FOUND_ERR;
1468         return;
1469     }
1470
1471     if (refNode->document() != m_ownerDocument) {
1472         ec = WRONG_DOCUMENT_ERR;
1473         return;
1474     }
1475
1476     ec = 0;
1477     checkNodeBA(refNode, ec);
1478     if (ec)
1479         return;
1480
1481     setStart(refNode->parentNode(), refNode->nodeIndex(), ec);
1482 }
1483
1484 void Range::checkDeleteExtract(ExceptionCode& ec)
1485 {
1486     if (!m_start.container()) {
1487         ec = INVALID_STATE_ERR;
1488         return;
1489     }
1490
1491     ec = 0;
1492     if (!commonAncestorContainer(ec) || ec)
1493         return;
1494
1495     Node* pastLast = pastLastNode();
1496     for (Node* n = firstNode(); n != pastLast; n = n->traverseNextNode()) {
1497         if (n->isReadOnlyNode()) {
1498             ec = NO_MODIFICATION_ALLOWED_ERR;
1499             return;
1500         }
1501         if (n->nodeType() == Node::DOCUMENT_TYPE_NODE) {
1502             ec = HIERARCHY_REQUEST_ERR;
1503             return;
1504         }
1505     }
1506
1507     if (containedByReadOnly()) {
1508         ec = NO_MODIFICATION_ALLOWED_ERR;
1509         return;
1510     }
1511 }
1512
1513 bool Range::containedByReadOnly() const
1514 {
1515     for (Node* n = m_start.container(); n; n = n->parentNode()) {
1516         if (n->isReadOnlyNode())
1517             return true;
1518     }
1519     for (Node* n = m_end.container(); n; n = n->parentNode()) {
1520         if (n->isReadOnlyNode())
1521             return true;
1522     }
1523     return false;
1524 }
1525
1526 Node* Range::firstNode() const
1527 {
1528     if (!m_start.container())
1529         return 0;
1530     if (m_start.container()->offsetInCharacters())
1531         return m_start.container();
1532     if (Node* child = m_start.container()->childNode(m_start.offset()))
1533         return child;
1534     if (!m_start.offset())
1535         return m_start.container();
1536     return m_start.container()->traverseNextSibling();
1537 }
1538
1539 Position Range::editingStartPosition() const
1540 {
1541     // This function is used by range style computations to avoid bugs like:
1542     // <rdar://problem/4017641> REGRESSION (Mail): you can only bold/unbold a selection starting from end of line once
1543     // It is important to skip certain irrelevant content at the start of the selection, so we do not wind up
1544     // with a spurious "mixed" style.
1545
1546     VisiblePosition visiblePosition(m_start.container(), m_start.offset(), VP_DEFAULT_AFFINITY);
1547     if (visiblePosition.isNull())
1548         return Position();
1549
1550     ExceptionCode ec = 0;
1551     // if the selection is a caret, just return the position, since the style
1552     // behind us is relevant
1553     if (collapsed(ec))
1554         return visiblePosition.deepEquivalent();
1555
1556     // if the selection starts just before a paragraph break, skip over it
1557     if (isEndOfParagraph(visiblePosition))
1558         return visiblePosition.next().deepEquivalent().downstream();
1559
1560     // otherwise, make sure to be at the start of the first selected node,
1561     // instead of possibly at the end of the last node before the selection
1562     return visiblePosition.deepEquivalent().downstream();
1563 }
1564
1565 Node* Range::shadowTreeRootNode() const
1566 {
1567     return startContainer() ? startContainer()->shadowTreeRootNode() : 0;
1568 }
1569
1570 Node* Range::pastLastNode() const
1571 {
1572     if (!m_start.container() || !m_end.container())
1573         return 0;
1574     if (m_end.container()->offsetInCharacters())
1575         return m_end.container()->traverseNextSibling();
1576     if (Node* child = m_end.container()->childNode(m_end.offset()))
1577         return child;
1578     return m_end.container()->traverseNextSibling();
1579 }
1580
1581 IntRect Range::boundingBox()
1582 {
1583     IntRect result;
1584     Vector<IntRect> rects;
1585     addLineBoxRects(rects);
1586     const size_t n = rects.size();
1587     for (size_t i = 0; i < n; ++i)
1588         result.unite(rects[i]);
1589     return result;
1590 }
1591
1592 void Range::addLineBoxRects(Vector<IntRect>& rects, bool useSelectionHeight)
1593 {
1594     if (!m_start.container() || !m_end.container())
1595         return;
1596
1597     RenderObject* start = m_start.container()->renderer();
1598     RenderObject* end = m_end.container()->renderer();
1599     if (!start || !end)
1600         return;
1601
1602     RenderObject* stop = end->nextInPreOrderAfterChildren();
1603     for (RenderObject* r = start; r && r != stop; r = r->nextInPreOrder()) {
1604         // only ask leaf render objects for their line box rects
1605         if (!r->firstChild()) {
1606             int startOffset = r == start ? m_start.offset() : 0;
1607             int endOffset = r == end ? m_end.offset() : INT_MAX;
1608             r->addLineBoxRects(rects, startOffset, endOffset, useSelectionHeight);
1609         }
1610     }
1611 }
1612
1613 #ifndef NDEBUG
1614 #define FormatBufferSize 1024
1615 void Range::formatForDebugger(char* buffer, unsigned length) const
1616 {
1617     String result;
1618     String s;
1619
1620     if (!m_start.container() || !m_end.container())
1621         result = "<empty>";
1622     else {
1623         char s[FormatBufferSize];
1624         result += "from offset ";
1625         result += String::number(m_start.offset());
1626         result += " of ";
1627         m_start.container()->formatForDebugger(s, FormatBufferSize);
1628         result += s;
1629         result += " to offset ";
1630         result += String::number(m_end.offset());
1631         result += " of ";
1632         m_end.container()->formatForDebugger(s, FormatBufferSize);
1633         result += s;
1634     }
1635
1636     strncpy(buffer, result.utf8().data(), length - 1);
1637 }
1638 #undef FormatBufferSize
1639 #endif
1640
1641 bool operator==(const Range& a, const Range& b)
1642 {
1643     if (&a == &b)
1644         return true;
1645     // Not strictly legal C++, but in practice this can happen, and this check works
1646     // fine with GCC to detect such cases and return false rather than crashing.
1647     if (!&a || !&b)
1648         return false;
1649     return a.startPosition() == b.startPosition() && a.endPosition() == b.endPosition();
1650 }
1651
1652 PassRefPtr<Range> rangeOfContents(Node* node)
1653 {
1654     ASSERT(node);
1655     RefPtr<Range> range = Range::create(node->document());
1656     int exception = 0;
1657     range->selectNodeContents(node, exception);
1658     return range.release();
1659 }
1660
1661 int Range::maxStartOffset() const
1662 {
1663     if (!m_start.container())
1664         return 0;
1665     if (!m_start.container()->offsetInCharacters())
1666         return m_start.container()->childNodeCount();
1667     return m_start.container()->maxCharacterOffset();
1668 }
1669
1670 int Range::maxEndOffset() const
1671 {
1672     if (!m_end.container())
1673         return 0;
1674     if (!m_end.container()->offsetInCharacters())
1675         return m_end.container()->childNodeCount();
1676     return m_end.container()->maxCharacterOffset();
1677 }
1678
1679 static inline void boundaryNodeChildrenChanged(RangeBoundaryPoint& boundary, ContainerNode* container)
1680 {
1681     if (!boundary.childBefore())
1682         return;
1683     if (boundary.container() != container)
1684         return;
1685     boundary.invalidateOffset();
1686 }
1687
1688 void Range::nodeChildrenChanged(ContainerNode* container)
1689 {
1690     ASSERT(container);
1691     ASSERT(container->document() == m_ownerDocument);
1692     boundaryNodeChildrenChanged(m_start, container);
1693     boundaryNodeChildrenChanged(m_end, container);
1694 }
1695
1696 static inline void boundaryNodeWillBeRemoved(RangeBoundaryPoint& boundary, Node* nodeToBeRemoved)
1697 {
1698     if (boundary.childBefore() == nodeToBeRemoved) {
1699         boundary.childBeforeWillBeRemoved();
1700         return;
1701     }
1702
1703     for (Node* n = boundary.container(); n; n = n->parentNode()) {
1704         if (n == nodeToBeRemoved) {
1705             boundary.setToChild(nodeToBeRemoved);
1706             return;
1707         }
1708     }
1709 }
1710
1711 void Range::nodeWillBeRemoved(Node* node)
1712 {
1713     ASSERT(node);
1714     ASSERT(node->document() == m_ownerDocument);
1715     ASSERT(node != m_ownerDocument);
1716     ASSERT(node->parentNode());
1717     boundaryNodeWillBeRemoved(m_start, node);
1718     boundaryNodeWillBeRemoved(m_end, node);
1719 }
1720
1721 static inline void boundaryTextInserted(RangeBoundaryPoint& boundary, Node* text, unsigned offset, unsigned length)
1722 {
1723     if (boundary.container() != text)
1724         return;
1725     unsigned boundaryOffset = boundary.offset();
1726     if (offset >= boundaryOffset)
1727         return;
1728     boundary.setOffset(boundaryOffset + length);
1729 }
1730
1731 void Range::textInserted(Node* text, unsigned offset, unsigned length)
1732 {
1733     ASSERT(text);
1734     ASSERT(text->document() == m_ownerDocument);
1735     boundaryTextInserted(m_start, text, offset, length);
1736     boundaryTextInserted(m_end, text, offset, length);
1737 }
1738
1739 static inline void boundaryTextRemoved(RangeBoundaryPoint& boundary, Node* text, unsigned offset, unsigned length)
1740 {
1741     if (boundary.container() != text)
1742         return;
1743     unsigned boundaryOffset = boundary.offset();
1744     if (offset >= boundaryOffset)
1745         return;
1746     if (offset + length >= boundaryOffset)
1747         boundary.setOffset(offset);
1748     else
1749         boundary.setOffset(boundaryOffset - length);
1750 }
1751
1752 void Range::textRemoved(Node* text, unsigned offset, unsigned length)
1753 {
1754     ASSERT(text);
1755     ASSERT(text->document() == m_ownerDocument);
1756     boundaryTextRemoved(m_start, text, offset, length);
1757     boundaryTextRemoved(m_end, text, offset, length);
1758 }
1759
1760 static inline void boundaryTextNodesMerged(RangeBoundaryPoint& boundary, NodeWithIndex& oldNode, unsigned offset)
1761 {
1762     if (boundary.container() == oldNode.node())
1763         boundary.set(oldNode.node()->previousSibling(), boundary.offset() + offset, 0);
1764     else if (boundary.container() == oldNode.node()->parentNode() && boundary.offset() == oldNode.index())
1765         boundary.set(oldNode.node()->previousSibling(), offset, 0);
1766 }
1767
1768 void Range::textNodesMerged(NodeWithIndex& oldNode, unsigned offset)
1769 {
1770     ASSERT(oldNode.node());
1771     ASSERT(oldNode.node()->document() == m_ownerDocument);
1772     ASSERT(oldNode.node()->parentNode());
1773     ASSERT(oldNode.node()->isTextNode());
1774     ASSERT(oldNode.node()->previousSibling());
1775     ASSERT(oldNode.node()->previousSibling()->isTextNode());
1776     boundaryTextNodesMerged(m_start, oldNode, offset);
1777     boundaryTextNodesMerged(m_end, oldNode, offset);
1778 }
1779
1780 static inline void boundaryTextNodesSplit(RangeBoundaryPoint& boundary, Text* oldNode)
1781 {
1782     if (boundary.container() != oldNode)
1783         return;
1784     unsigned boundaryOffset = boundary.offset();
1785     if (boundaryOffset <= oldNode->length())
1786         return;
1787     boundary.set(oldNode->nextSibling(), boundaryOffset - oldNode->length(), 0);
1788 }
1789
1790 void Range::textNodeSplit(Text* oldNode)
1791 {
1792     ASSERT(oldNode);
1793     ASSERT(oldNode->document() == m_ownerDocument);
1794     ASSERT(oldNode->parentNode());
1795     ASSERT(oldNode->isTextNode());
1796     ASSERT(oldNode->nextSibling());
1797     ASSERT(oldNode->nextSibling()->isTextNode());
1798     boundaryTextNodesSplit(m_start, oldNode);
1799     boundaryTextNodesSplit(m_end, oldNode);
1800 }
1801
1802 }