Range.cpp 61.5 KB
Newer Older
darin@apple.com's avatar
darin@apple.com committed
1
/*
kocienda's avatar
kocienda committed
2 3 4 5
 * (C) 1999 Lars Knoll (knoll@kde.org)
 * (C) 2000 Gunnstein Lye (gunnstein@netcom.no)
 * (C) 2000 Frederik Holljen (frederik.holljen@hig.no)
 * (C) 2001 Peter Kelly (pmk@post.com)
6
 * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011 Apple Inc. All rights reserved.
7
 * Copyright (C) 2011 Motorola Mobility. All rights reserved.
kocienda's avatar
kocienda committed
8 9 10 11 12 13 14 15 16 17 18 19 20
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public License
 * along with this library; see the file COPYING.LIB.  If not, write to
ddkilzer's avatar
ddkilzer committed
21 22
 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
 * Boston, MA 02110-1301, USA.
kocienda's avatar
kocienda committed
23 24
 */

mjs's avatar
mjs committed
25
#include "config.h"
darin's avatar
darin committed
26
#include "Range.h"
darin's avatar
darin committed
27

28 29
#include "ClientRect.h"
#include "ClientRectList.h"
darin's avatar
darin committed
30
#include "DocumentFragment.h"
31
#include "ExceptionCode.h"
32
#include "FloatQuad.h"
33
#include "Frame.h"
34
#include "FrameView.h"
darin@apple.com's avatar
darin@apple.com committed
35
#include "HTMLElement.h"
36 37
#include "HTMLNames.h"
#include "Node.h"
38
#include "NodeTraversal.h"
darin@apple.com's avatar
darin@apple.com committed
39
#include "NodeWithIndex.h"
40
#include "Page.h"
41
#include "ProcessingInstruction.h"
42
#include "RangeException.h"
43 44
#include "RenderBoxModelObject.h"
#include "RenderText.h"
darin's avatar
darin committed
45
#include "Text.h"
darin's avatar
darin committed
46
#include "TextIterator.h"
darin@apple.com's avatar
darin@apple.com committed
47
#include "VisiblePosition.h"
48
#include "VisibleUnits.h"
49
#include "htmlediting.h"
darin's avatar
darin committed
50
#include "markup.h"
51
#include <stdio.h>
52
#include <wtf/RefCountedLeakCounter.h>
53
#include <wtf/Vector.h>
54
#include <wtf/text/CString.h>
55
#include <wtf/text/StringBuilder.h>
kocienda's avatar
kocienda committed
56

darin's avatar
darin committed
57
namespace WebCore {
kocienda's avatar
kocienda committed
58

darin's avatar
darin committed
59
using namespace std;
60
using namespace HTMLNames;
adele's avatar
adele committed
61

62
DEFINE_DEBUG_ONLY_GLOBAL(WTF::RefCountedLeakCounter, rangeCounter, ("Range"));
ggaren's avatar
ggaren committed
63

darin@apple.com's avatar
darin@apple.com committed
64 65
inline Range::Range(PassRefPtr<Document> ownerDocument)
    : m_ownerDocument(ownerDocument)
66 67
    , m_start(m_ownerDocument)
    , m_end(m_ownerDocument)
kocienda's avatar
kocienda committed
68
{
ggaren's avatar
ggaren committed
69
#ifndef NDEBUG
70
    rangeCounter.increment();
ggaren's avatar
ggaren committed
71
#endif
darin@apple.com's avatar
darin@apple.com committed
72 73

    m_ownerDocument->attachRange(this);
kocienda's avatar
kocienda committed
74 75
}

darin@apple.com's avatar
darin@apple.com committed
76 77 78 79 80 81 82
PassRefPtr<Range> Range::create(PassRefPtr<Document> ownerDocument)
{
    return adoptRef(new Range(ownerDocument));
}

inline Range::Range(PassRefPtr<Document> ownerDocument, PassRefPtr<Node> startContainer, int startOffset, PassRefPtr<Node> endContainer, int endOffset)
    : m_ownerDocument(ownerDocument)
83 84
    , m_start(m_ownerDocument)
    , m_end(m_ownerDocument)
kocienda's avatar
kocienda committed
85
{
ggaren's avatar
ggaren committed
86
#ifndef NDEBUG
87
    rangeCounter.increment();
ggaren's avatar
ggaren committed
88
#endif
darin@apple.com's avatar
darin@apple.com committed
89

darin@apple.com's avatar
darin@apple.com committed
90 91
    m_ownerDocument->attachRange(this);

sullivan's avatar
sullivan committed
92
    // Simply setting the containers and offsets directly would not do any of the checking
darin@apple.com's avatar
darin@apple.com committed
93
    // that setStart and setEnd do, so we call those functions.
94 95
    setStart(startContainer, startOffset);
    setEnd(endContainer, endOffset);
kocienda's avatar
kocienda committed
96 97
}

darin@apple.com's avatar
darin@apple.com committed
98
PassRefPtr<Range> Range::create(PassRefPtr<Document> ownerDocument, PassRefPtr<Node> startContainer, int startOffset, PassRefPtr<Node> endContainer, int endOffset)
justing's avatar
justing committed
99
{
darin@apple.com's avatar
darin@apple.com committed
100 101 102 103 104
    return adoptRef(new Range(ownerDocument, startContainer, startOffset, endContainer, endOffset));
}

PassRefPtr<Range> Range::create(PassRefPtr<Document> ownerDocument, const Position& start, const Position& end)
{
105
    return adoptRef(new Range(ownerDocument, start.containerNode(), start.computeOffsetInContainerNode(), end.containerNode(), end.computeOffsetInContainerNode()));
justing's avatar
justing committed
106 107
}

mjs's avatar
mjs committed
108 109
Range::~Range()
{
eric@webkit.org's avatar
eric@webkit.org committed
110 111
    // Always detach (even if we've already detached) to fix https://bugs.webkit.org/show_bug.cgi?id=26044
    m_ownerDocument->detachRange(this);
darin@apple.com's avatar
darin@apple.com committed
112

ggaren's avatar
ggaren committed
113
#ifndef NDEBUG
114
    rangeCounter.decrement();
ggaren's avatar
ggaren committed
115
#endif
mjs's avatar
mjs committed
116 117
}

118 119 120 121 122 123 124 125 126 127 128
void Range::setDocument(Document* document)
{
    ASSERT(m_ownerDocument != document);
    if (m_ownerDocument)
        m_ownerDocument->detachRange(this);
    m_ownerDocument = document;
    m_start.setToStartOfNode(document);
    m_end.setToStartOfNode(document);
    m_ownerDocument->attachRange(this);
}

darin@apple.com's avatar
darin@apple.com committed
129
Node* Range::startContainer(ExceptionCode& ec) const
kocienda's avatar
kocienda committed
130
{
131
    if (!m_start.container()) {
darin's avatar
darin committed
132
        ec = INVALID_STATE_ERR;
kocienda's avatar
kocienda committed
133 134 135
        return 0;
    }

136
    return m_start.container();
kocienda's avatar
kocienda committed
137 138
}

darin's avatar
darin committed
139
int Range::startOffset(ExceptionCode& ec) const
kocienda's avatar
kocienda committed
140
{
141
    if (!m_start.container()) {
darin's avatar
darin committed
142
        ec = INVALID_STATE_ERR;
kocienda's avatar
kocienda committed
143 144 145
        return 0;
    }

146
    return m_start.offset();
kocienda's avatar
kocienda committed
147 148
}

darin@apple.com's avatar
darin@apple.com committed
149
Node* Range::endContainer(ExceptionCode& ec) const
kocienda's avatar
kocienda committed
150
{
151
    if (!m_start.container()) {
darin's avatar
darin committed
152
        ec = INVALID_STATE_ERR;
kocienda's avatar
kocienda committed
153 154 155
        return 0;
    }

156
    return m_end.container();
kocienda's avatar
kocienda committed
157 158
}

darin's avatar
darin committed
159
int Range::endOffset(ExceptionCode& ec) const
kocienda's avatar
kocienda committed
160
{
161
    if (!m_start.container()) {
darin's avatar
darin committed
162
        ec = INVALID_STATE_ERR;
kocienda's avatar
kocienda committed
163 164 165
        return 0;
    }

166
    return m_end.offset();
kocienda's avatar
kocienda committed
167 168
}

darin@apple.com's avatar
darin@apple.com committed
169
Node* Range::commonAncestorContainer(ExceptionCode& ec) const
kocienda's avatar
kocienda committed
170
{
171
    if (!m_start.container()) {
darin's avatar
darin committed
172
        ec = INVALID_STATE_ERR;
kocienda's avatar
kocienda committed
173 174 175
        return 0;
    }

176
    return commonAncestorContainer(m_start.container(), m_end.container());
kocienda's avatar
kocienda committed
177 178
}

darin@apple.com's avatar
darin@apple.com committed
179
Node* Range::commonAncestorContainer(Node* containerA, Node* containerB)
kocienda's avatar
kocienda committed
180
{
darin@apple.com's avatar
darin@apple.com committed
181 182 183 184 185
    for (Node* parentA = containerA; parentA; parentA = parentA->parentNode()) {
        for (Node* parentB = containerB; parentB; parentB = parentB->parentNode()) {
            if (parentA == parentB)
                return parentA;
        }
kocienda's avatar
kocienda committed
186
    }
darin@apple.com's avatar
darin@apple.com committed
187
    return 0;
kocienda's avatar
kocienda committed
188 189
}

darin's avatar
darin committed
190
bool Range::collapsed(ExceptionCode& ec) const
kocienda's avatar
kocienda committed
191
{
192
    if (!m_start.container()) {
darin's avatar
darin committed
193
        ec = INVALID_STATE_ERR;
kocienda's avatar
kocienda committed
194 195 196
        return 0;
    }

197
    return m_start == m_end;
kocienda's avatar
kocienda committed
198 199
}

200 201 202 203 204 205 206 207 208 209 210 211
static inline bool checkForDifferentRootContainer(const RangeBoundaryPoint& start, const RangeBoundaryPoint& end)
{
    Node* endRootContainer = end.container();
    while (endRootContainer->parentNode())
        endRootContainer = endRootContainer->parentNode();
    Node* startRootContainer = start.container();
    while (startRootContainer->parentNode())
        startRootContainer = startRootContainer->parentNode();

    return startRootContainer != endRootContainer || (Range::compareBoundaryPoints(start, end, ASSERT_NO_EXCEPTION) > 0);
}

darin@apple.com's avatar
darin@apple.com committed
212
void Range::setStart(PassRefPtr<Node> refNode, int offset, ExceptionCode& ec)
kocienda's avatar
kocienda committed
213
{
214
    if (!m_start.container()) {
darin's avatar
darin committed
215
        ec = INVALID_STATE_ERR;
kocienda's avatar
kocienda committed
216 217 218 219
        return;
    }

    if (!refNode) {
darin's avatar
darin committed
220
        ec = NOT_FOUND_ERR;
kocienda's avatar
kocienda committed
221 222 223
        return;
    }

224
    bool didMoveDocument = false;
ggaren's avatar
ggaren committed
225
    if (refNode->document() != m_ownerDocument) {
226 227
        setDocument(refNode->document());
        didMoveDocument = true;
kocienda's avatar
kocienda committed
228 229
    }

antti@apple.com's avatar
antti@apple.com committed
230
    ec = 0;
231
    Node* childNode = checkNodeWOffset(refNode.get(), offset, ec);
darin's avatar
darin committed
232
    if (ec)
kocienda's avatar
kocienda committed
233 234
        return;

235
    m_start.set(refNode, offset, childNode);
kocienda's avatar
kocienda committed
236

237
    if (didMoveDocument || checkForDifferentRootContainer(m_start, m_end))
darin's avatar
darin committed
238
        collapse(true, ec);
kocienda's avatar
kocienda committed
239 240
}

darin@apple.com's avatar
darin@apple.com committed
241
void Range::setEnd(PassRefPtr<Node> refNode, int offset, ExceptionCode& ec)
kocienda's avatar
kocienda committed
242
{
243
    if (!m_start.container()) {
darin's avatar
darin committed
244
        ec = INVALID_STATE_ERR;
kocienda's avatar
kocienda committed
245 246 247 248
        return;
    }

    if (!refNode) {
darin's avatar
darin committed
249
        ec = NOT_FOUND_ERR;
kocienda's avatar
kocienda committed
250 251 252
        return;
    }

253
    bool didMoveDocument = false;
ggaren's avatar
ggaren committed
254
    if (refNode->document() != m_ownerDocument) {
255 256
        setDocument(refNode->document());
        didMoveDocument = true;
kocienda's avatar
kocienda committed
257 258
    }

antti@apple.com's avatar
antti@apple.com committed
259
    ec = 0;
260
    Node* childNode = checkNodeWOffset(refNode.get(), offset, ec);
darin's avatar
darin committed
261
    if (ec)
kocienda's avatar
kocienda committed
262 263
        return;

264
    m_end.set(refNode, offset, childNode);
kocienda's avatar
kocienda committed
265

266
    if (didMoveDocument || checkForDifferentRootContainer(m_start, m_end))
darin's avatar
darin committed
267
        collapse(false, ec);
kocienda's avatar
kocienda committed
268 269
}

270 271 272 273 274 275 276 277 278
void Range::setStart(const Position& start, ExceptionCode& ec)
{
    Position parentAnchored = start.parentAnchoredEquivalent();
    setStart(parentAnchored.containerNode(), parentAnchored.offsetInContainerNode(), ec);
}

void Range::setEnd(const Position& end, ExceptionCode& ec)
{
    Position parentAnchored = end.parentAnchoredEquivalent();
279
    setEnd(parentAnchored.containerNode(), parentAnchored.offsetInContainerNode(), ec);
280 281
}

darin@apple.com's avatar
darin@apple.com committed
282
void Range::collapse(bool toStart, ExceptionCode& ec)
kocienda's avatar
kocienda committed
283
{
284
    if (!m_start.container()) {
darin's avatar
darin committed
285
        ec = INVALID_STATE_ERR;
kocienda's avatar
kocienda committed
286 287 288
        return;
    }

darin@apple.com's avatar
darin@apple.com committed
289 290 291 292
    if (toStart)
        m_end = m_start;
    else
        m_start = m_end;
kocienda's avatar
kocienda committed
293 294
}

aliceli1's avatar
aliceli1 committed
295 296
bool Range::isPointInRange(Node* refNode, int offset, ExceptionCode& ec)
{
ap@webkit.org's avatar
ap@webkit.org committed
297 298
    if (!m_start.container()) {
        ec = INVALID_STATE_ERR;
aliceli1's avatar
aliceli1 committed
299 300 301
        return false;
    }

ap@webkit.org's avatar
ap@webkit.org committed
302 303
    if (!refNode) {
        ec = HIERARCHY_REQUEST_ERR;
aliceli1's avatar
aliceli1 committed
304 305 306
        return false;
    }

307
    if (!refNode->attached() || refNode->document() != m_ownerDocument) {
aliceli1's avatar
aliceli1 committed
308 309 310
        return false;
    }

antti@apple.com's avatar
antti@apple.com committed
311
    ec = 0;
aliceli1's avatar
aliceli1 committed
312 313 314 315
    checkNodeWOffset(refNode, offset, ec);
    if (ec)
        return false;

316 317
    return compareBoundaryPoints(refNode, offset, m_start.container(), m_start.offset(), ec) >= 0 && !ec
        && compareBoundaryPoints(refNode, offset, m_end.container(), m_end.offset(), ec) <= 0 && !ec;
aliceli1's avatar
aliceli1 committed
318 319
}

320
short Range::comparePoint(Node* refNode, int offset, ExceptionCode& ec) const
aliceli1's avatar
aliceli1 committed
321 322
{
    // http://developer.mozilla.org/en/docs/DOM:range.comparePoint
justing's avatar
justing committed
323
    // This method returns -1, 0 or 1 depending on if the point described by the 
aliceli1's avatar
aliceli1 committed
324 325
    // refNode node and an offset within the node is before, same as, or after the range respectively.

ap@webkit.org's avatar
ap@webkit.org committed
326
    if (!m_start.container()) {
aliceli1's avatar
aliceli1 committed
327 328 329 330
        ec = INVALID_STATE_ERR;
        return 0;
    }

ap@webkit.org's avatar
ap@webkit.org committed
331 332 333
    if (!refNode) {
        ec = HIERARCHY_REQUEST_ERR;
        return 0;
aliceli1's avatar
aliceli1 committed
334 335
    }

ap@webkit.org's avatar
ap@webkit.org committed
336
    if (!refNode->attached() || refNode->document() != m_ownerDocument) {
aliceli1's avatar
aliceli1 committed
337 338 339 340
        ec = WRONG_DOCUMENT_ERR;
        return 0;
    }

antti@apple.com's avatar
antti@apple.com committed
341
    ec = 0;
aliceli1's avatar
aliceli1 committed
342 343 344 345 346
    checkNodeWOffset(refNode, offset, ec);
    if (ec)
        return 0;

    // compare to start, and point comes before
347
    if (compareBoundaryPoints(refNode, offset, m_start.container(), m_start.offset(), ec) < 0)
aliceli1's avatar
aliceli1 committed
348 349
        return -1;

350 351 352
    if (ec)
        return 0;

aliceli1's avatar
aliceli1 committed
353
    // compare to end, and point comes after
354
    if (compareBoundaryPoints(refNode, offset, m_end.container(), m_end.offset(), ec) > 0 && !ec)
aliceli1's avatar
aliceli1 committed
355
        return 1;
darin@apple.com's avatar
darin@apple.com committed
356

aliceli1's avatar
aliceli1 committed
357
    // point is in the middle of this range, or on the boundary points
darin@apple.com's avatar
darin@apple.com committed
358
    return 0;
aliceli1's avatar
aliceli1 committed
359 360
}

361
Range::CompareResults Range::compareNode(Node* refNode, ExceptionCode& ec) const
kmccullo's avatar
kmccullo committed
362 363 364 365 366 367 368 369 370 371
{
    // http://developer.mozilla.org/en/docs/DOM:range.compareNode
    // This method returns 0, 1, 2, or 3 based on if the node is before, after,
    // before and after(surrounds), or inside the range, respectively

    if (!refNode) {
        ec = NOT_FOUND_ERR;
        return NODE_BEFORE;
    }
    
372
    if (!m_start.container() && refNode->attached()) {
kmccullo's avatar
kmccullo committed
373 374 375 376
        ec = INVALID_STATE_ERR;
        return NODE_BEFORE;
    }

377
    if (m_start.container() && !refNode->attached()) {
darin@apple.com's avatar
darin@apple.com committed
378
        // Firefox doesn't throw an exception for this case; it returns 0.
kmccullo's avatar
kmccullo committed
379 380 381 382
        return NODE_BEFORE;
    }

    if (refNode->document() != m_ownerDocument) {
darin@apple.com's avatar
darin@apple.com committed
383
        // Firefox doesn't throw an exception for this case; it returns 0.
kmccullo's avatar
kmccullo committed
384 385 386
        return NODE_BEFORE;
    }

387
    ContainerNode* parentNode = refNode->parentNode();
darin@apple.com's avatar
darin@apple.com committed
388
    int nodeIndex = refNode->nodeIndex();
kmccullo's avatar
kmccullo committed
389 390 391 392 393 394 395 396
    
    if (!parentNode) {
        // if the node is the top document we should return NODE_BEFORE_AND_AFTER
        // but we throw to match firefox behavior
        ec = NOT_FOUND_ERR;
        return NODE_BEFORE;
    }

darin@apple.com's avatar
darin@apple.com committed
397 398
    if (comparePoint(parentNode, nodeIndex, ec) < 0) { // starts before
        if (comparePoint(parentNode, nodeIndex + 1, ec) > 0) // ends after the range
kmccullo's avatar
kmccullo committed
399 400 401
            return NODE_BEFORE_AND_AFTER;
        return NODE_BEFORE; // ends before or in the range
    } else { // starts at or after the range start
darin@apple.com's avatar
darin@apple.com committed
402
        if (comparePoint(parentNode, nodeIndex + 1, ec) > 0) // ends after the range
kmccullo's avatar
kmccullo committed
403 404 405 406 407
            return NODE_AFTER;
        return NODE_INSIDE; // ends inside the range
    }
}

darin@apple.com's avatar
darin@apple.com committed
408
short Range::compareBoundaryPoints(CompareHow how, const Range* sourceRange, ExceptionCode& ec) const
kocienda's avatar
kocienda committed
409
{
410
    if (!m_start.container()) {
darin's avatar
darin committed
411
        ec = INVALID_STATE_ERR;
kocienda's avatar
kocienda committed
412 413 414 415
        return 0;
    }

    if (!sourceRange) {
darin's avatar
darin committed
416
        ec = NOT_FOUND_ERR;
kocienda's avatar
kocienda committed
417 418 419
        return 0;
    }

antti@apple.com's avatar
antti@apple.com committed
420
    ec = 0;
darin@apple.com's avatar
darin@apple.com committed
421
    Node* thisCont = commonAncestorContainer(ec);
antti@apple.com's avatar
antti@apple.com committed
422 423
    if (ec)
        return 0;
darin@apple.com's avatar
darin@apple.com committed
424
    Node* sourceCont = sourceRange->commonAncestorContainer(ec);
darin's avatar
darin committed
425
    if (ec)
kocienda's avatar
kocienda committed
426 427
        return 0;

ggaren's avatar
ggaren committed
428
    if (thisCont->document() != sourceCont->document()) {
darin's avatar
darin committed
429
        ec = WRONG_DOCUMENT_ERR;
kocienda's avatar
kocienda committed
430 431 432
        return 0;
    }

darin@apple.com's avatar
darin@apple.com committed
433 434
    Node* thisTop = thisCont;
    Node* sourceTop = sourceCont;
kocienda's avatar
kocienda committed
435
    while (thisTop->parentNode())
darin's avatar
darin committed
436
        thisTop = thisTop->parentNode();
kocienda's avatar
kocienda committed
437
    while (sourceTop->parentNode())
darin's avatar
darin committed
438
        sourceTop = sourceTop->parentNode();
kocienda's avatar
kocienda committed
439
    if (thisTop != sourceTop) { // in different DocumentFragments
darin's avatar
darin committed
440
        ec = WRONG_DOCUMENT_ERR;
kocienda's avatar
kocienda committed
441 442 443
        return 0;
    }

darin@apple.com's avatar
darin@apple.com committed
444 445
    switch (how) {
        case START_TO_START:
446
            return compareBoundaryPoints(m_start, sourceRange->m_start, ec);
darin@apple.com's avatar
darin@apple.com committed
447
        case START_TO_END:
448
            return compareBoundaryPoints(m_end, sourceRange->m_start, ec);
darin@apple.com's avatar
darin@apple.com committed
449
        case END_TO_END:
450
            return compareBoundaryPoints(m_end, sourceRange->m_end, ec);
darin@apple.com's avatar
darin@apple.com committed
451
        case END_TO_START:
452
            return compareBoundaryPoints(m_start, sourceRange->m_end, ec);
kocienda's avatar
kocienda committed
453
    }
darin@apple.com's avatar
darin@apple.com committed
454 455 456

    ec = SYNTAX_ERR;
    return 0;
kocienda's avatar
kocienda committed
457 458
}

459
short Range::compareBoundaryPoints(Node* containerA, int offsetA, Node* containerB, int offsetB, ExceptionCode& ec)
kocienda's avatar
kocienda committed
460
{
darin@apple.com's avatar
darin@apple.com committed
461 462 463
    ASSERT(containerA);
    ASSERT(containerB);

justing's avatar
justing committed
464 465 466 467
    if (!containerA)
        return -1;
    if (!containerB)
        return 1;
darin@apple.com's avatar
darin@apple.com committed
468

kocienda's avatar
kocienda committed
469 470 471
    // see DOM2 traversal & range section 2.5

    // case 1: both points have the same container
darin@apple.com's avatar
darin@apple.com committed
472
    if (containerA == containerB) {
473 474 475 476 477 478
        if (offsetA == offsetB)
            return 0;           // A is equal to B
        if (offsetA < offsetB)
            return -1;          // A is before B
        else
            return 1;           // A is after B
kocienda's avatar
kocienda committed
479 480 481
    }

    // case 2: node C (container B or an ancestor) is a child node of A
darin@apple.com's avatar
darin@apple.com committed
482
    Node* c = containerB;
kocienda's avatar
kocienda committed
483 484 485 486
    while (c && c->parentNode() != containerA)
        c = c->parentNode();
    if (c) {
        int offsetC = 0;
darin@apple.com's avatar
darin@apple.com committed
487
        Node* n = containerA->firstChild();
488
        while (n != c && offsetC < offsetA) {
kocienda's avatar
kocienda committed
489 490 491 492
            offsetC++;
            n = n->nextSibling();
        }

493 494 495 496
        if (offsetA <= offsetC)
            return -1;              // A is before B
        else
            return 1;               // A is after B
kocienda's avatar
kocienda committed
497 498 499 500 501 502 503 504
    }

    // case 3: node C (container A or an ancestor) is a child node of B
    c = containerA;
    while (c && c->parentNode() != containerB)
        c = c->parentNode();
    if (c) {
        int offsetC = 0;
darin@apple.com's avatar
darin@apple.com committed
505
        Node* n = containerB->firstChild();
506
        while (n != c && offsetC < offsetB) {
kocienda's avatar
kocienda committed
507 508 509 510
            offsetC++;
            n = n->nextSibling();
        }

darin@apple.com's avatar
darin@apple.com committed
511
        if (offsetC < offsetB)
512 513 514
            return -1;              // A is before B
        else
            return 1;               // A is after B
kocienda's avatar
kocienda committed
515 516 517 518
    }

    // case 4: containers A & B are siblings, or children of siblings
    // ### we need to do a traversal here instead
darin@apple.com's avatar
darin@apple.com committed
519
    Node* commonAncestor = commonAncestorContainer(containerA, containerB);
520 521
    if (!commonAncestor) {
        ec = WRONG_DOCUMENT_ERR;
justing's avatar
justing committed
522
        return 0;
523
    }
darin@apple.com's avatar
darin@apple.com committed
524 525
    Node* childA = containerA;
    while (childA && childA->parentNode() != commonAncestor)
kocienda's avatar
kocienda committed
526
        childA = childA->parentNode();
kocienda's avatar
kocienda committed
527
    if (!childA)
darin@apple.com's avatar
darin@apple.com committed
528 529 530
        childA = commonAncestor;
    Node* childB = containerB;
    while (childB && childB->parentNode() != commonAncestor)
kocienda's avatar
kocienda committed
531
        childB = childB->parentNode();
kocienda's avatar
kocienda committed
532
    if (!childB)
darin@apple.com's avatar
darin@apple.com committed
533
        childB = commonAncestor;
kocienda's avatar
kocienda committed
534

darin's avatar
darin committed
535 536 537
    if (childA == childB)
        return 0; // A is equal to B

darin@apple.com's avatar
darin@apple.com committed
538
    Node* n = commonAncestor->firstChild();
darin's avatar
darin committed
539
    while (n) {
kocienda's avatar
kocienda committed
540
        if (n == childA)
darin's avatar
darin committed
541
            return -1; // A is before B
kocienda's avatar
kocienda committed
542
        if (n == childB)
darin's avatar
darin committed
543
            return 1; // A is after B
kocienda's avatar
kocienda committed
544 545 546
        n = n->nextSibling();
    }

darin's avatar
darin committed
547
    // Should never reach this point.
darin@apple.com's avatar
darin@apple.com committed
548
    ASSERT_NOT_REACHED();
darin's avatar
darin committed
549
    return 0;
kocienda's avatar
kocienda committed
550 551
}

552
short Range::compareBoundaryPoints(const RangeBoundaryPoint& boundaryA, const RangeBoundaryPoint& boundaryB, ExceptionCode& ec)
553
{
554
    return compareBoundaryPoints(boundaryA.container(), boundaryA.offset(), boundaryB.container(), boundaryB.offset(), ec);
555 556
}

darin's avatar
darin committed
557
bool Range::boundaryPointsValid() const
kocienda's avatar
kocienda committed
558
{
559 560
    ExceptionCode ec = 0;
    return m_start.container() && compareBoundaryPoints(m_start, m_end, ec) <= 0 && !ec;
kocienda's avatar
kocienda committed
561 562
}

darin@apple.com's avatar
darin@apple.com committed
563 564
void Range::deleteContents(ExceptionCode& ec)
{
darin's avatar
darin committed
565 566
    checkDeleteExtract(ec);
    if (ec)
darin's avatar
darin committed
567
        return;
kocienda's avatar
kocienda committed
568

darin@apple.com's avatar
darin@apple.com committed
569
    processContents(DELETE_CONTENTS, ec);
kocienda's avatar
kocienda committed
570 571
}

kmccullo's avatar
kmccullo committed
572 573 574 575 576
bool Range::intersectsNode(Node* refNode, ExceptionCode& ec)
{
    // http://developer.mozilla.org/en/docs/DOM:range.intersectsNode
    // Returns a bool if the node intersects the range.

577 578 579 580 581
    // Throw exception if the range is already detached.
    if (!m_start.container()) {
        ec = INVALID_STATE_ERR;
        return false;
    }
kmccullo's avatar
kmccullo committed
582 583 584 585
    if (!refNode) {
        ec = NOT_FOUND_ERR;
        return false;
    }
586 587

    if (!refNode->attached() || refNode->document() != m_ownerDocument) {
darin@apple.com's avatar
darin@apple.com committed
588
        // Firefox doesn't throw an exception for these cases; it returns false.
kmccullo's avatar
kmccullo committed
589
        return false;
darin@apple.com's avatar
darin@apple.com committed
590
    }
kmccullo's avatar
kmccullo committed
591

592
    ContainerNode* parentNode = refNode->parentNode();
darin@apple.com's avatar
darin@apple.com committed
593
    int nodeIndex = refNode->nodeIndex();
kmccullo's avatar
kmccullo committed
594 595 596 597 598 599 600 601
    
    if (!parentNode) {
        // if the node is the top document we should return NODE_BEFORE_AND_AFTER
        // but we throw to match firefox behavior
        ec = NOT_FOUND_ERR;
        return false;
    }

darin@apple.com's avatar
darin@apple.com committed
602 603
    if (comparePoint(parentNode, nodeIndex, ec) < 0 && // starts before start
        comparePoint(parentNode, nodeIndex + 1, ec) < 0) { // ends before start
kmccullo's avatar
kmccullo committed
604
        return false;
darin@apple.com's avatar
darin@apple.com committed
605 606
    } else if (comparePoint(parentNode, nodeIndex, ec) > 0 && // starts after end
               comparePoint(parentNode, nodeIndex + 1, ec) > 0) { // ends after end
kmccullo's avatar
kmccullo committed
607 608 609
        return false;
    }
    
darin@apple.com's avatar
darin@apple.com committed
610
    return true; // all other cases
kmccullo's avatar
kmccullo committed
611 612
}

613 614 615 616 617 618 619 620 621 622 623 624 625
static inline Node* highestAncestorUnderCommonRoot(Node* node, Node* commonRoot)
{
    if (node == commonRoot)
        return 0;

    ASSERT(commonRoot->contains(node));

    while (node->parentNode() != commonRoot)
        node = node->parentNode();

    return node;
}

626 627 628 629
static inline Node* childOfCommonRootBeforeOffset(Node* container, unsigned offset, Node* commonRoot)
{
    ASSERT(container);
    ASSERT(commonRoot);
630 631 632
    
    if (!commonRoot->contains(container))
        return 0;
633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669

    if (container == commonRoot) {
        container = container->firstChild();
        for (unsigned i = 0; container && i < offset; i++)
            container = container->nextSibling();
    } else {
        while (container->parentNode() != commonRoot)
            container = container->parentNode();
    }

    return container;
}

static inline unsigned lengthOfContentsInNode(Node* node)
{
    // This switch statement must be consistent with that of Range::processContentsBetweenOffsets.
    switch (node->nodeType()) {
    case Node::TEXT_NODE:
    case Node::CDATA_SECTION_NODE:
    case Node::COMMENT_NODE:
        return static_cast<CharacterData*>(node)->length();
    case Node::PROCESSING_INSTRUCTION_NODE:
        return static_cast<ProcessingInstruction*>(node)->data().length();
    case Node::ELEMENT_NODE:
    case Node::ATTRIBUTE_NODE:
    case Node::ENTITY_REFERENCE_NODE:
    case Node::ENTITY_NODE:
    case Node::DOCUMENT_NODE:
    case Node::DOCUMENT_TYPE_NODE:
    case Node::DOCUMENT_FRAGMENT_NODE:
    case Node::NOTATION_NODE:
    case Node::XPATH_NAMESPACE_NODE:
        return node->childNodeCount();
    }
    ASSERT_NOT_REACHED();
    return 0;
}
670

darin@apple.com's avatar
darin@apple.com committed
671
PassRefPtr<DocumentFragment> Range::processContents(ActionType action, ExceptionCode& ec)
kocienda's avatar
kocienda committed
672
{
673 674
    typedef Vector<RefPtr<Node> > NodeVector;

andrew@webkit.org's avatar
andrew@webkit.org committed
675 676
    RefPtr<DocumentFragment> fragment;
    if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS)
677
        fragment = DocumentFragment::create(m_ownerDocument.get());
678

antti@apple.com's avatar
antti@apple.com committed
679
    ec = 0;
darin's avatar
darin committed
680
    if (collapsed(ec))
andrew@webkit.org's avatar
andrew@webkit.org committed
681
        return fragment.release();
darin's avatar
darin committed
682
    if (ec)
kocienda's avatar
kocienda committed
683 684
        return 0;

685
    RefPtr<Node> commonRoot = commonAncestorContainer(ec);
darin's avatar
darin committed
686
    if (ec)
kocienda's avatar
kocienda committed
687
        return 0;
darin@apple.com's avatar
darin@apple.com committed
688
    ASSERT(commonRoot);
kocienda's avatar
kocienda committed
689

690
    if (m_start.container() == m_end.container()) {
691 692
        processContentsBetweenOffsets(action, fragment, m_start.container(), m_start.offset(), m_end.offset(), ec);
        return fragment;
kocienda's avatar
kocienda committed
693 694
    }

695
    // what is the highest node that partially selects the start / end of the range?
696 697
    RefPtr<Node> partialStart = highestAncestorUnderCommonRoot(m_start.container(), commonRoot.get());
    RefPtr<Node> partialEnd = highestAncestorUnderCommonRoot(m_end.container(), commonRoot.get());
698 699

    // Start and end containers are different.
700
    // There are three possibilities here:
darin@apple.com's avatar
darin@apple.com committed
701 702 703
    // 1. Start container == commonRoot (End container must be a descendant)
    // 2. End container == commonRoot (Start container must be a descendant)
    // 3. Neither is commonRoot, they are both descendants
kocienda's avatar
kocienda committed
704 705
    //
    // In case 3, we grab everything after the start (up until a direct child
darin@apple.com's avatar
darin@apple.com committed
706 707 708
    // of commonRoot) into leftContents, and everything before the end (up until
    // a direct child of commonRoot) into rightContents. Then we process all
    // commonRoot children between leftContents and rightContents
kocienda's avatar
kocienda committed
709 710 711
    //
    // In case 1 or 2, we skip either processing of leftContents or rightContents,
    // in which case the last lot of nodes either goes from the first or last
darin@apple.com's avatar
darin@apple.com committed
712
    // child of commonRoot.
kocienda's avatar
kocienda committed
713 714 715
    //
    // These are deleted, cloned, or extracted (i.e. both) depending on action.

716 717 718
    // Note that we are verifying that our common root hierarchy is still intact
    // after any DOM mutation event, at various stages below. See webkit bug 60350.

darin's avatar
darin committed
719
    RefPtr<Node> leftContents;
720
    if (m_start.container() != commonRoot && commonRoot->contains(m_start.container())) {
721
        leftContents = processContentsBetweenOffsets(action, 0, m_start.container(), m_start.offset(), lengthOfContentsInNode(m_start.container()), ec);
722
        leftContents = processAncestorsAndTheirSiblings(action, m_start.container(), ProcessContentsForward, leftContents, commonRoot.get(), ec);
kocienda's avatar
kocienda committed
723 724
    }

darin@apple.com's avatar
darin@apple.com committed
725
    RefPtr<Node> rightContents;
726
    if (m_end.container() != commonRoot && commonRoot->contains(m_end.container())) {
727
        rightContents = processContentsBetweenOffsets(action, 0, m_end.container(), 0, m_end.offset(), ec);
728
        rightContents = processAncestorsAndTheirSiblings(action, m_end.container(), ProcessContentsBackward, rightContents, commonRoot.get(), ec);
kocienda's avatar
kocienda committed
729 730
    }

darin@apple.com's avatar
darin@apple.com committed
731
    // delete all children of commonRoot between the start and end container
732 733
    RefPtr<Node> processStart = childOfCommonRootBeforeOffset(m_start.container(), m_start.offset(), commonRoot.get());
    if (processStart && m_start.container() != commonRoot) // processStart contains nodes before m_start.
kocienda's avatar
kocienda committed
734
        processStart = processStart->nextSibling();
735
    RefPtr<Node> processEnd = childOfCommonRootBeforeOffset(m_end.container(), m_end.offset(), commonRoot.get());
kocienda's avatar
kocienda committed
736

ap@webkit.org's avatar
ap@webkit.org committed
737 738
    // Collapse the range, making sure that the result is not within a node that was partially selected.
    if (action == EXTRACT_CONTENTS || action == DELETE_CONTENTS) {
739
        if (partialStart && commonRoot->contains(partialStart.get()))
ap@webkit.org's avatar
ap@webkit.org committed
740
            setStart(partialStart->parentNode(), partialStart->nodeIndex() + 1, ec);
741
        else if (partialEnd && commonRoot->contains(partialEnd.get()))
ap@webkit.org's avatar
ap@webkit.org committed
742 743 744 745 746 747
            setStart(partialEnd->parentNode(), partialEnd->nodeIndex(), ec);
        if (ec)
            return 0;
        m_end = m_start;
    }

kocienda's avatar
kocienda committed
748 749 750 751
    // Now add leftContents, stuff in between, and rightContents to the fragment
    // (or just delete the stuff in between)

    if ((action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) && leftContents)
darin@apple.com's avatar
darin@apple.com committed
752
        fragment->appendChild(leftContents, ec);
kocienda's avatar
kocienda committed
753 754

    if (processStart) {
755
        NodeVector nodes;
756
        for (Node* n = processStart.get(); n && n != processEnd; n = n->nextSibling())
757
            nodes.append(n);
758
        processNodes(action, nodes, commonRoot, fragment, ec);
kocienda's avatar
kocienda committed
759 760 761
    }

    if ((action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) && rightContents)
darin@apple.com's avatar
darin@apple.com committed
762 763
        fragment->appendChild(rightContents, ec);

darin's avatar
darin committed
764
    return fragment.release();
kocienda's avatar
kocienda committed
765 766
}

767 768 769 770 771 772 773 774
static inline void deleteCharacterData(PassRefPtr<CharacterData> data, unsigned startOffset, unsigned endOffset, ExceptionCode& ec)
{
    if (data->length() - endOffset)
        data->deleteData(endOffset, data->length() - endOffset, ec);
    if (startOffset)
        data->deleteData(0, startOffset, ec);
}

775 776 777 778 779
PassRefPtr<Node> Range::processContentsBetweenOffsets(ActionType action, PassRefPtr<DocumentFragment> fragment,
    Node* container, unsigned startOffset, unsigned endOffset, ExceptionCode& ec)
{
    ASSERT(container);
    ASSERT(startOffset <= endOffset);
780 781 782

    // This switch statement must be consistent with that of lengthOfContentsInNode.
    RefPtr<Node> result;   
783 784 785 786
    switch (container->nodeType()) {
    case Node::TEXT_NODE:
    case Node::CDATA_SECTION_NODE:
    case Node::COMMENT_NODE:
787
        ASSERT(endOffset <= static_cast<CharacterData*>(container)->length());
788 789
        if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) {
            RefPtr<CharacterData> c = static_pointer_cast<CharacterData>(container->cloneNode(true));
790
            deleteCharacterData(c, startOffset, endOffset, ec);
791 792 793 794 795 796 797 798 799 800
            if (fragment) {
                result = fragment;
                result->appendChild(c.release(), ec);
            } else
                result = c.release();
        }
        if (action == EXTRACT_CONTENTS || action == DELETE_CONTENTS)
            static_cast<CharacterData*>(container)->deleteData(startOffset, endOffset - startOffset, ec);
        break;
    case Node::PROCESSING_INSTRUCTION_NODE:
801
        ASSERT(endOffset <= static_cast<ProcessingInstruction*>(container)->data().length());
802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841
        if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) {
            RefPtr<ProcessingInstruction> c = static_pointer_cast<ProcessingInstruction>(container->cloneNode(true));
            c->setData(c->data().substring(startOffset, endOffset - startOffset), ec);
            if (fragment) {
                result = fragment;
                result->appendChild(c.release(), ec);
            } else
                result = c.release();
        }
        if (action == EXTRACT_CONTENTS || action == DELETE_CONTENTS) {
            ProcessingInstruction* pi = static_cast<ProcessingInstruction*>(container);
            String data(pi->data());
            data.remove(startOffset, endOffset - startOffset);
            pi->setData(data, ec);
        }
        break;
    case Node::ELEMENT_NODE:
    case Node::ATTRIBUTE_NODE:
    case Node::ENTITY_REFERENCE_NODE:
    case Node::ENTITY_NODE:
    case Node::DOCUMENT_NODE:
    case Node::DOCUMENT_TYPE_NODE:
    case Node::DOCUMENT_FRAGMENT_NODE:
    case Node::NOTATION_NODE:
    case Node::XPATH_NAMESPACE_NODE:
        // FIXME: Should we assert that some nodes never appear here?
        if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) {
            if (fragment)
                result = fragment;
            else
                result = container->cloneNode(false);
        }

        Node* n = container->firstChild();
        Vector<RefPtr<Node> > nodes;
        for (unsigned i = startOffset; n && i; i--)
            n = n->nextSibling();
        for (unsigned i = startOffset; n && i < endOffset; i++, n = n->nextSibling())
            nodes.append(n);

842
        processNodes(action, nodes, container, result, ec);
843 844 845
        break;
    }

846
    return result.release();
847 848
}

849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865
void Range::processNodes(ActionType action, Vector<RefPtr<Node> >& nodes, PassRefPtr<Node> oldContainer, PassRefPtr<Node> newContainer, ExceptionCode& ec)
{
    for (unsigned