Range.cpp 62.4 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 Apple Inc. All rights reserved.
kocienda's avatar
kocienda committed
7 8 9 10 11 12 13 14 15 16 17 18 19
 *
 * 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
20 21
 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
 * Boston, MA 02110-1301, USA.
kocienda's avatar
kocienda committed
22 23
 */

mjs's avatar
mjs committed
24
#include "config.h"
darin's avatar
darin committed
25
#include "Range.h"
darin@apple.com's avatar
darin@apple.com committed
26
#include "RangeException.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 "FloatQuad.h"
32
#include "FrameView.h"
darin@apple.com's avatar
darin@apple.com committed
33
#include "HTMLElement.h"
darin@apple.com's avatar
darin@apple.com committed
34
#include "NodeWithIndex.h"
35
#include "ProcessingInstruction.h"
36 37
#include "RenderBoxModelObject.h"
#include "RenderText.h"
darin's avatar
darin committed
38
#include "Text.h"
darin's avatar
darin committed
39
#include "TextIterator.h"
darin@apple.com's avatar
darin@apple.com committed
40
#include "VisiblePosition.h"
41
#include "htmlediting.h"
darin's avatar
darin committed
42 43
#include "markup.h"
#include "visible_units.h"
44
#include <stdio.h>
45
#include <wtf/text/CString.h>
46
#include <wtf/RefCountedLeakCounter.h>
47
#include <wtf/Vector.h>
kocienda's avatar
kocienda committed
48

darin's avatar
darin committed
49
namespace WebCore {
kocienda's avatar
kocienda committed
50

darin's avatar
darin committed
51
using namespace std;
adele's avatar
adele committed
52

ggaren's avatar
ggaren committed
53
#ifndef NDEBUG
54
static WTF::RefCountedLeakCounter rangeCounter("Range");
ggaren's avatar
ggaren committed
55 56
#endif

darin@apple.com's avatar
darin@apple.com committed
57 58
inline Range::Range(PassRefPtr<Document> ownerDocument)
    : m_ownerDocument(ownerDocument)
59 60
    , m_start(m_ownerDocument)
    , m_end(m_ownerDocument)
kocienda's avatar
kocienda committed
61
{
ggaren's avatar
ggaren committed
62
#ifndef NDEBUG
63
    rangeCounter.increment();
ggaren's avatar
ggaren committed
64
#endif
darin@apple.com's avatar
darin@apple.com committed
65 66

    m_ownerDocument->attachRange(this);
kocienda's avatar
kocienda committed
67 68
}

darin@apple.com's avatar
darin@apple.com committed
69 70 71 72 73 74 75
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)
76 77
    , m_start(m_ownerDocument)
    , m_end(m_ownerDocument)
kocienda's avatar
kocienda committed
78
{
ggaren's avatar
ggaren committed
79
#ifndef NDEBUG
80
    rangeCounter.increment();
ggaren's avatar
ggaren committed
81
#endif
darin@apple.com's avatar
darin@apple.com committed
82

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

sullivan's avatar
sullivan committed
85
    // Simply setting the containers and offsets directly would not do any of the checking
darin@apple.com's avatar
darin@apple.com committed
86
    // that setStart and setEnd do, so we call those functions.
sullivan's avatar
sullivan committed
87 88
    ExceptionCode ec = 0;
    setStart(startContainer, startOffset, ec);
darin@apple.com's avatar
darin@apple.com committed
89
    ASSERT(!ec);
sullivan's avatar
sullivan committed
90
    setEnd(endContainer, endOffset, ec);
darin@apple.com's avatar
darin@apple.com committed
91
    ASSERT(!ec);
kocienda's avatar
kocienda committed
92 93
}

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

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

mjs's avatar
mjs committed
104 105
Range::~Range()
{
eric@webkit.org's avatar
eric@webkit.org committed
106 107
    // 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
108

ggaren's avatar
ggaren committed
109
#ifndef NDEBUG
110
    rangeCounter.decrement();
ggaren's avatar
ggaren committed
111
#endif
mjs's avatar
mjs committed
112 113
}

114 115 116 117 118 119 120 121 122 123 124
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
125
Node* Range::startContainer(ExceptionCode& ec) const
kocienda's avatar
kocienda committed
126
{
127
    if (!m_start.container()) {
darin's avatar
darin committed
128
        ec = INVALID_STATE_ERR;
kocienda's avatar
kocienda committed
129 130 131
        return 0;
    }

132
    return m_start.container();
kocienda's avatar
kocienda committed
133 134
}

darin's avatar
darin committed
135
int Range::startOffset(ExceptionCode& ec) const
kocienda's avatar
kocienda committed
136
{
137
    if (!m_start.container()) {
darin's avatar
darin committed
138
        ec = INVALID_STATE_ERR;
kocienda's avatar
kocienda committed
139 140 141
        return 0;
    }

142
    return m_start.offset();
kocienda's avatar
kocienda committed
143 144
}

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

152
    return m_end.container();
kocienda's avatar
kocienda committed
153 154
}

darin's avatar
darin committed
155
int Range::endOffset(ExceptionCode& ec) const
kocienda's avatar
kocienda committed
156
{
157
    if (!m_start.container()) {
darin's avatar
darin committed
158
        ec = INVALID_STATE_ERR;
kocienda's avatar
kocienda committed
159 160 161
        return 0;
    }

162
    return m_end.offset();
kocienda's avatar
kocienda committed
163 164
}

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

172
    return commonAncestorContainer(m_start.container(), m_end.container());
kocienda's avatar
kocienda committed
173 174
}

darin@apple.com's avatar
darin@apple.com committed
175
Node* Range::commonAncestorContainer(Node* containerA, Node* containerB)
kocienda's avatar
kocienda committed
176
{
darin@apple.com's avatar
darin@apple.com committed
177 178 179 180 181
    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
182
    }
darin@apple.com's avatar
darin@apple.com committed
183
    return 0;
kocienda's avatar
kocienda committed
184 185
}

darin's avatar
darin committed
186
bool Range::collapsed(ExceptionCode& ec) const
kocienda's avatar
kocienda committed
187
{
188
    if (!m_start.container()) {
darin's avatar
darin committed
189
        ec = INVALID_STATE_ERR;
kocienda's avatar
kocienda committed
190 191 192
        return 0;
    }

193
    return m_start == m_end;
kocienda's avatar
kocienda committed
194 195
}

darin@apple.com's avatar
darin@apple.com committed
196
void Range::setStart(PassRefPtr<Node> refNode, int offset, ExceptionCode& ec)
kocienda's avatar
kocienda committed
197
{
198
    if (!m_start.container()) {
darin's avatar
darin committed
199
        ec = INVALID_STATE_ERR;
kocienda's avatar
kocienda committed
200 201 202 203
        return;
    }

    if (!refNode) {
darin's avatar
darin committed
204
        ec = NOT_FOUND_ERR;
kocienda's avatar
kocienda committed
205 206 207
        return;
    }

ggaren's avatar
ggaren committed
208
    if (refNode->document() != m_ownerDocument) {
darin's avatar
darin committed
209
        ec = WRONG_DOCUMENT_ERR;
kocienda's avatar
kocienda committed
210 211 212
        return;
    }

antti@apple.com's avatar
antti@apple.com committed
213
    ec = 0;
214
    Node* childNode = checkNodeWOffset(refNode.get(), offset, ec);
darin's avatar
darin committed
215
    if (ec)
kocienda's avatar
kocienda committed
216 217
        return;

218
    m_start.set(refNode, offset, childNode);
kocienda's avatar
kocienda committed
219 220

    // check if different root container
221
    Node* endRootContainer = m_end.container();
kocienda's avatar
kocienda committed
222 223
    while (endRootContainer->parentNode())
        endRootContainer = endRootContainer->parentNode();
224
    Node* startRootContainer = m_start.container();
kocienda's avatar
kocienda committed
225 226 227
    while (startRootContainer->parentNode())
        startRootContainer = startRootContainer->parentNode();
    if (startRootContainer != endRootContainer)
darin's avatar
darin committed
228
        collapse(true, ec);
kocienda's avatar
kocienda committed
229
    // check if new start after end
230 231
    else if (compareBoundaryPoints(m_start, m_end, ec) > 0) {
        ASSERT(!ec);
darin's avatar
darin committed
232
        collapse(true, ec);
233
    }
kocienda's avatar
kocienda committed
234 235
}

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

    if (!refNode) {
darin's avatar
darin committed
244
        ec = NOT_FOUND_ERR;
kocienda's avatar
kocienda committed
245 246 247
        return;
    }

ggaren's avatar
ggaren committed
248
    if (refNode->document() != m_ownerDocument) {
darin's avatar
darin committed
249
        ec = WRONG_DOCUMENT_ERR;
kocienda's avatar
kocienda committed
250 251 252
        return;
    }

antti@apple.com's avatar
antti@apple.com committed
253
    ec = 0;
254
    Node* childNode = checkNodeWOffset(refNode.get(), offset, ec);
darin's avatar
darin committed
255
    if (ec)
kocienda's avatar
kocienda committed
256 257
        return;

258
    m_end.set(refNode, offset, childNode);
kocienda's avatar
kocienda committed
259 260

    // check if different root container
261
    Node* endRootContainer = m_end.container();
kocienda's avatar
kocienda committed
262 263
    while (endRootContainer->parentNode())
        endRootContainer = endRootContainer->parentNode();
264
    Node* startRootContainer = m_start.container();
kocienda's avatar
kocienda committed
265 266 267
    while (startRootContainer->parentNode())
        startRootContainer = startRootContainer->parentNode();
    if (startRootContainer != endRootContainer)
darin's avatar
darin committed
268
        collapse(false, ec);
kocienda's avatar
kocienda committed
269
    // check if new end before start
270 271
    if (compareBoundaryPoints(m_start, m_end, ec) > 0) {
        ASSERT(!ec);
darin's avatar
darin committed
272
        collapse(false, ec);
273
    }
kocienda's avatar
kocienda committed
274 275
}

darin@apple.com's avatar
darin@apple.com committed
276
void Range::collapse(bool toStart, ExceptionCode& ec)
kocienda's avatar
kocienda committed
277
{
278
    if (!m_start.container()) {
darin's avatar
darin committed
279
        ec = INVALID_STATE_ERR;
kocienda's avatar
kocienda committed
280 281 282
        return;
    }

darin@apple.com's avatar
darin@apple.com committed
283 284 285 286
    if (toStart)
        m_end = m_start;
    else
        m_start = m_end;
kocienda's avatar
kocienda committed
287 288
}

aliceli1's avatar
aliceli1 committed
289 290
bool Range::isPointInRange(Node* refNode, int offset, ExceptionCode& ec)
{
ap@webkit.org's avatar
ap@webkit.org committed
291 292
    if (!m_start.container()) {
        ec = INVALID_STATE_ERR;
aliceli1's avatar
aliceli1 committed
293 294 295
        return false;
    }

ap@webkit.org's avatar
ap@webkit.org committed
296 297
    if (!refNode) {
        ec = HIERARCHY_REQUEST_ERR;
aliceli1's avatar
aliceli1 committed
298 299 300
        return false;
    }

ap@webkit.org's avatar
ap@webkit.org committed
301
    if (!refNode->attached()) {
darin@apple.com's avatar
darin@apple.com committed
302
        // Firefox doesn't throw an exception for this case; it returns false.
aliceli1's avatar
aliceli1 committed
303 304 305 306 307 308 309 310
        return false;
    }

    if (refNode->document() != m_ownerDocument) {
        ec = WRONG_DOCUMENT_ERR;
        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 577 578 579 580 581
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.

    if (!refNode) {
        ec = NOT_FOUND_ERR;
        return false;
    }
    
582 583
    if ((!m_start.container() && refNode->attached())
            || (m_start.container() && !refNode->attached())
darin@apple.com's avatar
darin@apple.com committed
584 585
            || refNode->document() != m_ownerDocument) {
        // Firefox doesn't throw an exception for these cases; it returns false.
kmccullo's avatar
kmccullo committed
586
        return false;
darin@apple.com's avatar
darin@apple.com committed
587
    }
kmccullo's avatar
kmccullo committed
588

589
    ContainerNode* parentNode = refNode->parentNode();
darin@apple.com's avatar
darin@apple.com committed
590
    int nodeIndex = refNode->nodeIndex();
kmccullo's avatar
kmccullo committed
591 592 593 594 595 596 597 598
    
    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
599 600
    if (comparePoint(parentNode, nodeIndex, ec) < 0 && // starts before start
        comparePoint(parentNode, nodeIndex + 1, ec) < 0) { // ends before start
kmccullo's avatar
kmccullo committed
601
        return false;
darin@apple.com's avatar
darin@apple.com committed
602 603
    } else if (comparePoint(parentNode, nodeIndex, ec) > 0 && // starts after end
               comparePoint(parentNode, nodeIndex + 1, ec) > 0) { // ends after end
kmccullo's avatar
kmccullo committed
604 605 606
        return false;
    }
    
darin@apple.com's avatar
darin@apple.com committed
607
    return true; // all other cases
kmccullo's avatar
kmccullo committed
608 609
}

610 611 612 613 614 615 616 617 618 619 620 621 622
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;
}

623 624 625 626 627 628 629 630 631 632 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
static inline Node* childOfCommonRootBeforeOffset(Node* container, unsigned offset, Node* commonRoot)
{
    ASSERT(container);
    ASSERT(commonRoot);
    ASSERT(commonRoot->contains(container));

    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:
660
    case Node::SHADOW_ROOT_NODE:
661 662 663 664 665
        return node->childNodeCount();
    }
    ASSERT_NOT_REACHED();
    return 0;
}
666

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

andrew@webkit.org's avatar
andrew@webkit.org committed
671 672
    RefPtr<DocumentFragment> fragment;
    if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS)
673
        fragment = DocumentFragment::create(m_ownerDocument.get());
674

antti@apple.com's avatar
antti@apple.com committed
675
    ec = 0;
darin's avatar
darin committed
676
    if (collapsed(ec))
andrew@webkit.org's avatar
andrew@webkit.org committed
677
        return fragment.release();
darin's avatar
darin committed
678
    if (ec)
kocienda's avatar
kocienda committed
679 680
        return 0;

darin@apple.com's avatar
darin@apple.com committed
681
    Node* commonRoot = commonAncestorContainer(ec);
darin's avatar
darin committed
682
    if (ec)
kocienda's avatar
kocienda committed
683
        return 0;
darin@apple.com's avatar
darin@apple.com committed
684
    ASSERT(commonRoot);
kocienda's avatar
kocienda committed
685

686
    if (m_start.container() == m_end.container()) {
687 688
        processContentsBetweenOffsets(action, fragment, m_start.container(), m_start.offset(), m_end.offset(), ec);
        return fragment;
kocienda's avatar
kocienda committed
689 690
    }

691 692 693 694 695
    // what is the highest node that partially selects the start / end of the range?
    Node* partialStart = highestAncestorUnderCommonRoot(m_start.container(), commonRoot);
    Node* partialEnd = highestAncestorUnderCommonRoot(m_end.container(), commonRoot);

    // Start and end containers are different.
696
    // There are three possibilities here:
darin@apple.com's avatar
darin@apple.com committed
697 698 699
    // 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
700 701
    //
    // In case 3, we grab everything after the start (up until a direct child
darin@apple.com's avatar
darin@apple.com committed
702 703 704
    // 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
705 706 707
    //
    // 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
708
    // child of commonRoot.
kocienda's avatar
kocienda committed
709 710 711
    //
    // These are deleted, cloned, or extracted (i.e. both) depending on action.

darin's avatar
darin committed
712
    RefPtr<Node> leftContents;
713
    if (m_start.container() != commonRoot) {
714
        leftContents = processContentsBetweenOffsets(action, 0, m_start.container(), m_start.offset(), lengthOfContentsInNode(m_start.container()), ec);
715
        leftContents = processAncestorsAndTheirSiblings(action, m_start.container(), ProcessContentsForward, leftContents, commonRoot, ec);
kocienda's avatar
kocienda committed
716 717
    }

darin@apple.com's avatar
darin@apple.com committed
718
    RefPtr<Node> rightContents;
719
    if (m_end.container() != commonRoot) {
720
        rightContents = processContentsBetweenOffsets(action, 0, m_end.container(), 0, m_end.offset(), ec);
721
        rightContents = processAncestorsAndTheirSiblings(action, m_end.container(), ProcessContentsBackward, rightContents, commonRoot, ec);
kocienda's avatar
kocienda committed
722 723
    }

darin@apple.com's avatar
darin@apple.com committed
724
    // delete all children of commonRoot between the start and end container
725 726
    Node* processStart = childOfCommonRootBeforeOffset(m_start.container(), m_start.offset(), commonRoot);
    if (m_start.container() != commonRoot) // processStart contains nodes before m_start.
kocienda's avatar
kocienda committed
727
        processStart = processStart->nextSibling();
728
    Node* processEnd = childOfCommonRootBeforeOffset(m_end.container(), m_end.offset(), commonRoot);
kocienda's avatar
kocienda committed
729

ap@webkit.org's avatar
ap@webkit.org committed
730 731 732 733 734 735 736 737 738 739 740
    // Collapse the range, making sure that the result is not within a node that was partially selected.
    if (action == EXTRACT_CONTENTS || action == DELETE_CONTENTS) {
        if (partialStart)
            setStart(partialStart->parentNode(), partialStart->nodeIndex() + 1, ec);
        else if (partialEnd)
            setStart(partialEnd->parentNode(), partialEnd->nodeIndex(), ec);
        if (ec)
            return 0;
        m_end = m_start;
    }

kocienda's avatar
kocienda committed
741 742 743 744
    // 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
745
        fragment->appendChild(leftContents, ec);
kocienda's avatar
kocienda committed
746 747

    if (processStart) {
748 749 750
        NodeVector nodes;
        for (Node* n = processStart; n && n != processEnd; n = n->nextSibling())
            nodes.append(n);
751
        processNodes(action, nodes, commonRoot, fragment, ec);
kocienda's avatar
kocienda committed
752 753 754
    }

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

darin's avatar
darin committed
757
    return fragment.release();
kocienda's avatar
kocienda committed
758 759
}

760 761 762 763 764 765 766 767
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);
}

768 769 770 771 772
PassRefPtr<Node> Range::processContentsBetweenOffsets(ActionType action, PassRefPtr<DocumentFragment> fragment,
    Node* container, unsigned startOffset, unsigned endOffset, ExceptionCode& ec)
{
    ASSERT(container);
    ASSERT(startOffset <= endOffset);
773 774 775

    // This switch statement must be consistent with that of lengthOfContentsInNode.
    RefPtr<Node> result;   
776 777 778 779
    switch (container->nodeType()) {
    case Node::TEXT_NODE:
    case Node::CDATA_SECTION_NODE:
    case Node::COMMENT_NODE:
780
        ASSERT(endOffset <= static_cast<CharacterData*>(container)->length());
781 782
        if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) {
            RefPtr<CharacterData> c = static_pointer_cast<CharacterData>(container->cloneNode(true));
783
            deleteCharacterData(c, startOffset, endOffset, ec);
784 785 786 787 788 789 790 791 792 793
            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:
794
        ASSERT(endOffset <= static_cast<ProcessingInstruction*>(container)->data().length());
795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819
        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:
820
    case Node::SHADOW_ROOT_NODE:
821 822 823 824 825 826 827 828 829 830 831 832 833 834 835
        // 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);

836
        processNodes(action, nodes, container, result, ec);
837 838 839 840 841 842
        break;
    }

    return result;
}

843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859
void Range::processNodes(ActionType action, Vector<RefPtr<Node> >& nodes, PassRefPtr<Node> oldContainer, PassRefPtr<Node> newContainer, ExceptionCode& ec)
{
    for (unsigned i = 0; i < nodes.size(); i++) {
        switch (action) {
        case DELETE_CONTENTS:
            oldContainer->removeChild(nodes[i].get(), ec);
            break;
        case EXTRACT_CONTENTS:
            newContainer->appendChild(nodes[i].release(), ec); // will remove n from its parent
            break;
        case CLONE_CONTENTS:
            newContainer->appendChild(nodes[i]->cloneNode(true), ec);
            break;
        }
    }
}

860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878
PassRefPtr<Node> Range::processAncestorsAndTheirSiblings(ActionType action, Node* container, ContentsProcessDirection direction, PassRefPtr<Node> passedClonedContainer, Node* commonRoot, ExceptionCode& ec)
{
    RefPtr<Node> clonedContainer = passedClonedContainer;
    Vector<RefPtr<Node> > ancestors;
    for (ContainerNode* n = container->parentNode(); n && n != commonRoot; n = n->parentNode())
        ancestors.append(n);

    RefPtr<Node> firstChildInAncestorToProcess = direction == ProcessContentsForward ? container->nextSibling() : container->previousSibling();
    for (Vector<RefPtr<Node> >::const_iterator it = ancestors.begin(); it != ancestors.end(); it++) {
        RefPtr<Node> ancestor = *it;
        if (action == EXTRACT_CONTENTS || action == CLONE_CONTENTS) {
            if (RefPtr<Node> clonedAncestor = ancestor->cloneNode(false)) { // Might have been removed already during mutation event.
                clonedAncestor->appendChild(clonedContainer, ec);
                clonedContainer = clonedAncestor;
            }
        }

        // Copy siblings of an ancestor of start/end containers
        // FIXME: This assertion may fail if DOM is modified during mutation event
879
        // FIXME: Share code with Range::processNodes
880 881 882