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, 2009, 2010, 2011 Apple Inc. All rights reserved.
7 * Copyright (C) 2011 Motorola Mobility. All rights reserved.
8 *
9 * This library is free software; you can redistribute it and/or
10 * modify it under the terms of the GNU Library General Public
11 * License as published by the Free Software Foundation; either
12 * version 2 of the License, or (at your option) any later version.
13 *
14 * This library is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 * Library General Public License for more details.
18 *
19 * You should have received a copy of the GNU Library General Public License
20 * along with this library; see the file COPYING.LIB. If not, write to
21 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
22 * Boston, MA 02110-1301, USA.
23 */
24
25#include "config.h"
26#include "Range.h"
27
28#include "Comment.h"
29#include "DOMRect.h"
30#include "DOMRectList.h"
31#include "DocumentFragment.h"
32#include "Editing.h"
33#include "Event.h"
34#include "Frame.h"
35#include "FrameView.h"
36#include "HTMLBodyElement.h"
37#include "HTMLElement.h"
38#include "HTMLHtmlElement.h"
39#include "HTMLNames.h"
40#include "NodeTraversal.h"
41#include "NodeWithIndex.h"
42#include "ProcessingInstruction.h"
43#include "RenderBoxModelObject.h"
44#include "RenderText.h"
45#include "ScopedEventQueue.h"
46#include "TextIterator.h"
47#include "VisiblePosition.h"
48#include "VisibleUnits.h"
49#include "markup.h"
50#include <stdio.h>
51#include <wtf/RefCountedLeakCounter.h>
52#include <wtf/text/CString.h>
53#include <wtf/text/StringBuilder.h>
54
55#if PLATFORM(IOS_FAMILY)
56#include "SelectionRect.h"
57#endif
58
59namespace WebCore {
60
61using namespace HTMLNames;
62
63DEFINE_DEBUG_ONLY_GLOBAL(WTF::RefCountedLeakCounter, rangeCounter, ("Range"));
64
65enum ContentsProcessDirection { ProcessContentsForward, ProcessContentsBackward };
66enum class CoordinateSpace { Absolute, Client };
67
68static ExceptionOr<void> processNodes(Range::ActionType, Vector<Ref<Node>>&, Node* oldContainer, RefPtr<Node> newContainer);
69static ExceptionOr<RefPtr<Node>> processContentsBetweenOffsets(Range::ActionType, RefPtr<DocumentFragment>, RefPtr<Node> container, unsigned startOffset, unsigned endOffset);
70static ExceptionOr<RefPtr<Node>> processAncestorsAndTheirSiblings(Range::ActionType, Node* container, ContentsProcessDirection, ExceptionOr<RefPtr<Node>>&& passedClonedContainer, Node* commonRoot);
71
72inline Range::Range(Document& ownerDocument)
73 : m_ownerDocument(ownerDocument)
74 , m_start(&ownerDocument)
75 , m_end(&ownerDocument)
76{
77#ifndef NDEBUG
78 rangeCounter.increment();
79#endif
80
81 m_ownerDocument->attachRange(*this);
82}
83
84Ref<Range> Range::create(Document& ownerDocument)
85{
86 return adoptRef(*new Range(ownerDocument));
87}
88
89inline Range::Range(Document& ownerDocument, Node* startContainer, int startOffset, Node* endContainer, int endOffset)
90 : m_ownerDocument(ownerDocument)
91 , m_start(&ownerDocument)
92 , m_end(&ownerDocument)
93{
94#ifndef NDEBUG
95 rangeCounter.increment();
96#endif
97
98 m_ownerDocument->attachRange(*this);
99
100 // Simply setting the containers and offsets directly would not do any of the checking
101 // that setStart and setEnd do, so we call those functions.
102 if (startContainer)
103 setStart(*startContainer, startOffset);
104 if (endContainer)
105 setEnd(*endContainer, endOffset);
106}
107
108Ref<Range> Range::create(Document& ownerDocument, RefPtr<Node>&& startContainer, int startOffset, RefPtr<Node>&& endContainer, int endOffset)
109{
110 return adoptRef(*new Range(ownerDocument, startContainer.get(), startOffset, endContainer.get(), endOffset));
111}
112
113Ref<Range> Range::create(Document& ownerDocument, const Position& start, const Position& end)
114{
115 return adoptRef(*new Range(ownerDocument, start.containerNode(), start.computeOffsetInContainerNode(), end.containerNode(), end.computeOffsetInContainerNode()));
116}
117
118Ref<Range> Range::create(Document& ownerDocument, const VisiblePosition& visibleStart, const VisiblePosition& visibleEnd)
119{
120 Position start = visibleStart.deepEquivalent().parentAnchoredEquivalent();
121 Position end = visibleEnd.deepEquivalent().parentAnchoredEquivalent();
122 return adoptRef(*new Range(ownerDocument, start.anchorNode(), start.deprecatedEditingOffset(), end.anchorNode(), end.deprecatedEditingOffset()));
123}
124
125Range::~Range()
126{
127 m_ownerDocument->detachRange(*this);
128
129#ifndef NDEBUG
130 rangeCounter.decrement();
131#endif
132}
133
134void Range::setDocument(Document& document)
135{
136 ASSERT(m_ownerDocument.ptr() != &document);
137 m_ownerDocument->detachRange(*this);
138 m_ownerDocument = document;
139 m_start.setToStartOfNode(document);
140 m_end.setToStartOfNode(document);
141 m_ownerDocument->attachRange(*this);
142}
143
144Node* Range::commonAncestorContainer(Node* containerA, Node* containerB)
145{
146 for (Node* parentA = containerA; parentA; parentA = parentA->parentNode()) {
147 for (Node* parentB = containerB; parentB; parentB = parentB->parentNode()) {
148 if (parentA == parentB)
149 return parentA;
150 }
151 }
152 return nullptr;
153}
154
155static inline bool checkForDifferentRootContainer(const RangeBoundaryPoint& start, const RangeBoundaryPoint& end)
156{
157 Node* endRootContainer = end.container();
158 while (endRootContainer->parentNode())
159 endRootContainer = endRootContainer->parentNode();
160 Node* startRootContainer = start.container();
161 while (startRootContainer->parentNode())
162 startRootContainer = startRootContainer->parentNode();
163
164 return startRootContainer != endRootContainer || Range::compareBoundaryPoints(start, end).releaseReturnValue() > 0;
165}
166
167ExceptionOr<void> Range::setStart(Ref<Node>&& refNode, unsigned offset)
168{
169 bool didMoveDocument = false;
170 if (&refNode->document() != &ownerDocument()) {
171 setDocument(refNode->document());
172 didMoveDocument = true;
173 }
174
175 auto childNode = checkNodeWOffset(refNode, offset);
176 if (childNode.hasException())
177 return childNode.releaseException();
178
179 m_start.set(WTFMove(refNode), offset, childNode.releaseReturnValue());
180
181 if (didMoveDocument || checkForDifferentRootContainer(m_start, m_end))
182 collapse(true);
183
184 return { };
185}
186
187ExceptionOr<void> Range::setEnd(Ref<Node>&& refNode, unsigned offset)
188{
189 bool didMoveDocument = false;
190 if (&refNode->document() != &ownerDocument()) {
191 setDocument(refNode->document());
192 didMoveDocument = true;
193 }
194
195 auto childNode = checkNodeWOffset(refNode, offset);
196 if (childNode.hasException())
197 return childNode.releaseException();
198
199 m_end.set(WTFMove(refNode), offset, childNode.releaseReturnValue());
200
201 if (didMoveDocument || checkForDifferentRootContainer(m_start, m_end))
202 collapse(false);
203
204 return { };
205}
206
207ExceptionOr<void> Range::setStart(const Position& start)
208{
209 Position parentAnchored = start.parentAnchoredEquivalent();
210 if (!parentAnchored.containerNode())
211 return Exception { TypeError };
212 return setStart(*parentAnchored.containerNode(), parentAnchored.offsetInContainerNode());
213}
214
215ExceptionOr<void> Range::setEnd(const Position& end)
216{
217 Position parentAnchored = end.parentAnchoredEquivalent();
218 if (!parentAnchored.containerNode())
219 return Exception { TypeError };
220 return setEnd(*parentAnchored.containerNode(), parentAnchored.offsetInContainerNode());
221}
222
223void Range::collapse(bool toStart)
224{
225 if (toStart)
226 m_end = m_start;
227 else
228 m_start = m_end;
229}
230
231ExceptionOr<bool> Range::isPointInRange(Node& refNode, unsigned offset)
232{
233 if (&refNode.document() != &ownerDocument())
234 return false;
235
236 auto checkNodeResult = checkNodeWOffset(refNode, offset);
237 if (checkNodeResult.hasException()) {
238 // DOM4 spec requires us to check whether refNode and start container have the same root first
239 // but we do it in the reverse order to avoid O(n) operation here in common case.
240 if (!commonAncestorContainer(&refNode, &startContainer()))
241 return false;
242 return checkNodeResult.releaseException();
243 }
244
245 auto startCompareResult = compareBoundaryPoints(&refNode, offset, &startContainer(), m_start.offset());
246 if (!(!startCompareResult.hasException() && startCompareResult.releaseReturnValue() >= 0))
247 return false;
248 auto endCompareResult = compareBoundaryPoints(&refNode, offset, &endContainer(), m_end.offset());
249 return !endCompareResult.hasException() && endCompareResult.releaseReturnValue() <= 0;
250}
251
252ExceptionOr<short> Range::comparePoint(Node& refNode, unsigned offset) const
253{
254 // http://developer.mozilla.org/en/docs/DOM:range.comparePoint
255 // This method returns -1, 0 or 1 depending on if the point described by the
256 // refNode node and an offset within the node is before, same as, or after the range respectively.
257 if (&refNode.document() != &ownerDocument())
258 return Exception { WrongDocumentError };
259
260 auto checkNodeResult = checkNodeWOffset(refNode, offset);
261 if (checkNodeResult.hasException()) {
262 // DOM4 spec requires us to check whether refNode and start container have the same root first
263 // but we do it in the reverse order to avoid O(n) operation here in common case.
264 if (!refNode.isConnected() && !commonAncestorContainer(&refNode, &startContainer()))
265 return Exception { WrongDocumentError };
266 return checkNodeResult.releaseException();
267 }
268
269 // compare to start, and point comes before
270 auto startCompareResult = compareBoundaryPoints(&refNode, offset, &startContainer(), m_start.offset());
271 if (startCompareResult.hasException())
272 return startCompareResult.releaseException();
273 if (startCompareResult.releaseReturnValue() < 0)
274 return -1;
275
276 // compare to end, and point comes after
277 auto endCompareResult = compareBoundaryPoints(&refNode, offset, &endContainer(), m_end.offset());
278 if (endCompareResult.hasException())
279 return endCompareResult.releaseException();
280 if (endCompareResult.releaseReturnValue() > 0)
281 return 1;
282
283 // point is in the middle of this range, or on the boundary points
284 return 0;
285}
286
287ExceptionOr<Range::CompareResults> Range::compareNode(Node& refNode) const
288{
289 // http://developer.mozilla.org/en/docs/DOM:range.compareNode
290 // This method returns 0, 1, 2, or 3 based on if the node is before, after,
291 // before and after(surrounds), or inside the range, respectively
292
293 if (!refNode.isConnected()) {
294 // Firefox doesn't throw an exception for this case; it returns 0.
295 return NODE_BEFORE;
296 }
297
298 if (&refNode.document() != &ownerDocument()) {
299 // Firefox doesn't throw an exception for this case; it returns 0.
300 return NODE_BEFORE;
301 }
302
303 auto* parentNode = refNode.parentNode();
304 if (!parentNode) {
305 // If the node is the top of the tree we should return NODE_BEFORE_AND_AFTER,
306 // but we throw to match firefox behavior.
307 return Exception { NotFoundError };
308 }
309 auto nodeIndex = refNode.computeNodeIndex();
310
311 auto nodeStartCompareResult = comparePoint(*parentNode, nodeIndex);
312 if (nodeStartCompareResult.hasException())
313 return nodeStartCompareResult.releaseException();
314 auto nodeEndCompareResult = comparePoint(*parentNode, nodeIndex + 1);
315 if (nodeEndCompareResult.hasException())
316 return nodeEndCompareResult.releaseException();
317
318 bool nodeStartsBeforeRange = nodeStartCompareResult.releaseReturnValue() < 0;
319 bool nodeEndsAfterRange = nodeEndCompareResult.releaseReturnValue() > 0;
320
321 return nodeStartsBeforeRange
322 ? (nodeEndsAfterRange ? NODE_BEFORE_AND_AFTER : NODE_BEFORE)
323 : (nodeEndsAfterRange ? NODE_AFTER : NODE_INSIDE);
324}
325
326static inline Node* top(Node& node)
327{
328 auto* top = &node;
329 while (auto* parent = top->parentNode())
330 top = parent;
331 return top;
332}
333
334ExceptionOr<short> Range::compareBoundaryPoints(CompareHow how, const Range& sourceRange) const
335{
336 auto* thisContainer = commonAncestorContainer();
337 auto* sourceContainer = sourceRange.commonAncestorContainer();
338 if (!thisContainer || !sourceContainer || &thisContainer->document() != &sourceContainer->document() || top(*thisContainer) != top(*sourceContainer))
339 return Exception { WrongDocumentError };
340
341 switch (how) {
342 case START_TO_START:
343 return compareBoundaryPoints(m_start, sourceRange.m_start);
344 case START_TO_END:
345 return compareBoundaryPoints(m_end, sourceRange.m_start);
346 case END_TO_END:
347 return compareBoundaryPoints(m_end, sourceRange.m_end);
348 case END_TO_START:
349 return compareBoundaryPoints(m_start, sourceRange.m_end);
350 }
351
352 return Exception { SyntaxError };
353}
354
355ExceptionOr<short> Range::compareBoundaryPointsForBindings(unsigned short how, const Range& sourceRange) const
356{
357 switch (how) {
358 case START_TO_START:
359 case START_TO_END:
360 case END_TO_END:
361 case END_TO_START:
362 return compareBoundaryPoints(static_cast<CompareHow>(how), sourceRange);
363 }
364 return Exception { NotSupportedError };
365}
366
367ExceptionOr<short> Range::compareBoundaryPoints(Node* containerA, unsigned offsetA, Node* containerB, unsigned offsetB)
368{
369 ASSERT(containerA);
370 ASSERT(containerB);
371
372 if (!containerA)
373 return -1;
374 if (!containerB)
375 return 1;
376
377 // see DOM2 traversal & range section 2.5
378
379 // case 1: both points have the same container
380 if (containerA == containerB) {
381 if (offsetA == offsetB)
382 return 0; // A is equal to B
383 if (offsetA < offsetB)
384 return -1; // A is before B
385 return 1; // A is after B
386 }
387
388 // case 2: node C (container B or an ancestor) is a child node of A
389 Node* c = containerB;
390 while (c && c->parentNode() != containerA)
391 c = c->parentNode();
392 if (c) {
393 unsigned offsetC = 0;
394 Node* n = containerA->firstChild();
395 while (n != c && offsetC < offsetA) {
396 offsetC++;
397 n = n->nextSibling();
398 }
399 if (offsetA <= offsetC)
400 return -1; // A is before B
401 return 1; // A is after B
402 }
403
404 // case 3: node C (container A or an ancestor) is a child node of B
405 c = containerA;
406 while (c && c->parentNode() != containerB)
407 c = c->parentNode();
408 if (c) {
409 unsigned offsetC = 0;
410 Node* n = containerB->firstChild();
411 while (n != c && offsetC < offsetB) {
412 offsetC++;
413 n = n->nextSibling();
414 }
415 if (offsetC < offsetB)
416 return -1; // A is before B
417 return 1; // A is after B
418 }
419
420 // case 4: containers A & B are siblings, or children of siblings
421 // ### we need to do a traversal here instead
422 auto* commonAncestor = commonAncestorContainer(containerA, containerB);
423 if (!commonAncestor)
424 return Exception { WrongDocumentError };
425 Node* childA = containerA;
426 while (childA && childA->parentNode() != commonAncestor)
427 childA = childA->parentNode();
428 if (!childA)
429 childA = commonAncestor;
430 Node* childB = containerB;
431 while (childB && childB->parentNode() != commonAncestor)
432 childB = childB->parentNode();
433 if (!childB)
434 childB = commonAncestor;
435
436 if (childA == childB)
437 return 0; // A is equal to B
438
439 Node* n = commonAncestor->firstChild();
440 while (n) {
441 if (n == childA)
442 return -1; // A is before B
443 if (n == childB)
444 return 1; // A is after B
445 n = n->nextSibling();
446 }
447
448 // Should never reach this point.
449 ASSERT_NOT_REACHED();
450 return 0;
451}
452
453ExceptionOr<short> Range::compareBoundaryPoints(const RangeBoundaryPoint& boundaryA, const RangeBoundaryPoint& boundaryB)
454{
455 return compareBoundaryPoints(boundaryA.container(), boundaryA.offset(), boundaryB.container(), boundaryB.offset());
456}
457
458bool Range::boundaryPointsValid() const
459{
460 auto result = compareBoundaryPoints(m_start, m_end);
461 return !result.hasException() && result.releaseReturnValue() <= 0;
462}
463
464ExceptionOr<void> Range::deleteContents()
465{
466 auto result = processContents(Delete);
467 if (result.hasException())
468 return result.releaseException();
469 return { };
470}
471
472ExceptionOr<bool> Range::intersectsNode(Node& refNode) const
473{
474 if (!refNode.isConnected() || &refNode.document() != &ownerDocument())
475 return false;
476
477 ContainerNode* parentNode = refNode.parentNode();
478 if (!parentNode)
479 return true;
480
481 unsigned nodeIndex = refNode.computeNodeIndex();
482
483 // If (parent, offset) is before end and (parent, offset + 1) is after start, return true.
484 // Otherwise, return false.
485 auto result = comparePoint(*parentNode, nodeIndex);
486 if (result.hasException())
487 return result.releaseException();
488 auto compareFirst = result.releaseReturnValue();
489 result = comparePoint(*parentNode, nodeIndex + 1);
490 if (result.hasException())
491 return result.releaseException();
492 auto compareSecond = result.releaseReturnValue();
493
494 bool isFirstBeforeEnd = m_start == m_end ? compareFirst < 0 : compareFirst <= 0;
495 bool isSecondAfterStart = m_start == m_end ? compareSecond > 0 : compareSecond >= 0;
496
497 return isFirstBeforeEnd && isSecondAfterStart;
498}
499
500static inline Node* highestAncestorUnderCommonRoot(Node* node, Node* commonRoot)
501{
502 if (node == commonRoot)
503 return 0;
504
505 ASSERT(commonRoot->contains(node));
506
507 while (node->parentNode() != commonRoot)
508 node = node->parentNode();
509
510 return node;
511}
512
513static inline Node* childOfCommonRootBeforeOffset(Node* container, unsigned offset, Node* commonRoot)
514{
515 ASSERT(container);
516 ASSERT(commonRoot);
517
518 if (!commonRoot->contains(container))
519 return 0;
520
521 if (container == commonRoot) {
522 container = container->firstChild();
523 for (unsigned i = 0; container && i < offset; i++)
524 container = container->nextSibling();
525 } else {
526 while (container->parentNode() != commonRoot)
527 container = container->parentNode();
528 }
529
530 return container;
531}
532
533static inline unsigned lengthOfContentsInNode(Node& node)
534{
535 // This switch statement must be consistent with that of Range::processContentsBetweenOffsets.
536 switch (node.nodeType()) {
537 case Node::DOCUMENT_TYPE_NODE:
538 case Node::ATTRIBUTE_NODE:
539 return 0;
540 case Node::TEXT_NODE:
541 case Node::CDATA_SECTION_NODE:
542 case Node::COMMENT_NODE:
543 case Node::PROCESSING_INSTRUCTION_NODE:
544 return downcast<CharacterData>(node).length();
545 case Node::ELEMENT_NODE:
546 case Node::DOCUMENT_NODE:
547 case Node::DOCUMENT_FRAGMENT_NODE:
548 return downcast<ContainerNode>(node).countChildNodes();
549 }
550 ASSERT_NOT_REACHED();
551 return 0;
552}
553
554ExceptionOr<RefPtr<DocumentFragment>> Range::processContents(ActionType action)
555{
556 RefPtr<DocumentFragment> fragment;
557 if (action == Extract || action == Clone)
558 fragment = DocumentFragment::create(ownerDocument());
559
560 if (collapsed())
561 return fragment;
562
563 RefPtr<Node> commonRoot = commonAncestorContainer();
564 ASSERT(commonRoot);
565
566 if (&startContainer() == &endContainer()) {
567 auto result = processContentsBetweenOffsets(action, fragment, &startContainer(), m_start.offset(), m_end.offset());
568 if (result.hasException())
569 return result.releaseException();
570 return fragment;
571 }
572
573 // Since mutation events can modify the range during the process, the boundary points need to be saved.
574 RangeBoundaryPoint originalStart(m_start);
575 RangeBoundaryPoint originalEnd(m_end);
576
577 // what is the highest node that partially selects the start / end of the range?
578 RefPtr<Node> partialStart = highestAncestorUnderCommonRoot(originalStart.container(), commonRoot.get());
579 RefPtr<Node> partialEnd = highestAncestorUnderCommonRoot(originalEnd.container(), commonRoot.get());
580
581 // Start and end containers are different.
582 // There are three possibilities here:
583 // 1. Start container == commonRoot (End container must be a descendant)
584 // 2. End container == commonRoot (Start container must be a descendant)
585 // 3. Neither is commonRoot, they are both descendants
586 //
587 // In case 3, we grab everything after the start (up until a direct child
588 // of commonRoot) into leftContents, and everything before the end (up until
589 // a direct child of commonRoot) into rightContents. Then we process all
590 // commonRoot children between leftContents and rightContents
591 //
592 // In case 1 or 2, we skip either processing of leftContents or rightContents,
593 // in which case the last lot of nodes either goes from the first or last
594 // child of commonRoot.
595 //
596 // These are deleted, cloned, or extracted (i.e. both) depending on action.
597
598 // Note that we are verifying that our common root hierarchy is still intact
599 // after any DOM mutation event, at various stages below. See webkit bug 60350.
600
601 RefPtr<Node> leftContents;
602 if (originalStart.container() != commonRoot && commonRoot->contains(originalStart.container())) {
603 auto firstResult = processContentsBetweenOffsets(action, nullptr, originalStart.container(), originalStart.offset(), lengthOfContentsInNode(*originalStart.container()));
604 auto secondResult = processAncestorsAndTheirSiblings(action, originalStart.container(), ProcessContentsForward, WTFMove(firstResult), commonRoot.get());
605 // FIXME: A bit peculiar that we silently ignore the exception here, but we do have at least some regression tests that rely on this behavior.
606 if (!secondResult.hasException())
607 leftContents = secondResult.releaseReturnValue();
608 }
609
610 RefPtr<Node> rightContents;
611 if (&endContainer() != commonRoot && commonRoot->contains(originalEnd.container())) {
612 auto firstResult = processContentsBetweenOffsets(action, nullptr, originalEnd.container(), 0, originalEnd.offset());
613 auto secondResult = processAncestorsAndTheirSiblings(action, originalEnd.container(), ProcessContentsBackward, WTFMove(firstResult), commonRoot.get());
614 // FIXME: A bit peculiar that we silently ignore the exception here, but we do have at least some regression tests that rely on this behavior.
615 if (!secondResult.hasException())
616 rightContents = secondResult.releaseReturnValue();
617 }
618
619 // delete all children of commonRoot between the start and end container
620 RefPtr<Node> processStart = childOfCommonRootBeforeOffset(originalStart.container(), originalStart.offset(), commonRoot.get());
621 if (processStart && originalStart.container() != commonRoot) // processStart contains nodes before m_start.
622 processStart = processStart->nextSibling();
623 RefPtr<Node> processEnd = childOfCommonRootBeforeOffset(originalEnd.container(), originalEnd.offset(), commonRoot.get());
624
625 // Collapse the range, making sure that the result is not within a node that was partially selected.
626 if (action == Extract || action == Delete) {
627 if (partialStart && commonRoot->contains(partialStart.get())) {
628 auto result = setStart(*partialStart->parentNode(), partialStart->computeNodeIndex() + 1);
629 if (result.hasException())
630 return result.releaseException();
631 } else if (partialEnd && commonRoot->contains(partialEnd.get())) {
632 auto result = setStart(*partialEnd->parentNode(), partialEnd->computeNodeIndex());
633 if (result.hasException())
634 return result.releaseException();
635 }
636 m_end = m_start;
637 }
638
639 // Now add leftContents, stuff in between, and rightContents to the fragment
640 // (or just delete the stuff in between)
641
642 if ((action == Extract || action == Clone) && leftContents) {
643 auto result = fragment->appendChild(*leftContents);
644 if (result.hasException())
645 return result.releaseException();
646 }
647
648 if (processStart) {
649 Vector<Ref<Node>> nodes;
650 for (Node* node = processStart.get(); node && node != processEnd; node = node->nextSibling())
651 nodes.append(*node);
652 auto result = processNodes(action, nodes, commonRoot.get(), fragment.get());
653 if (result.hasException())
654 return result.releaseException();
655 }
656
657 if ((action == Extract || action == Clone) && rightContents) {
658 auto result = fragment->appendChild(*rightContents);
659 if (result.hasException())
660 return result.releaseException();
661 }
662
663 return fragment;
664}
665
666static inline ExceptionOr<void> deleteCharacterData(CharacterData& data, unsigned startOffset, unsigned endOffset)
667{
668 if (data.length() - endOffset) {
669 auto result = data.deleteData(endOffset, data.length() - endOffset);
670 if (result.hasException())
671 return result.releaseException();
672 }
673 if (startOffset) {
674 auto result = data.deleteData(0, startOffset);
675 if (result.hasException())
676 return result.releaseException();
677 }
678 return { };
679}
680
681static ExceptionOr<RefPtr<Node>> processContentsBetweenOffsets(Range::ActionType action, RefPtr<DocumentFragment> fragment, RefPtr<Node> container, unsigned startOffset, unsigned endOffset)
682{
683 ASSERT(container);
684 ASSERT(startOffset <= endOffset);
685
686 RefPtr<Node> result;
687
688 // This switch statement must be consistent with that of lengthOfContentsInNode.
689 switch (container->nodeType()) {
690 case Node::TEXT_NODE:
691 case Node::CDATA_SECTION_NODE:
692 case Node::COMMENT_NODE:
693 endOffset = std::min(endOffset, downcast<CharacterData>(*container).length());
694 startOffset = std::min(startOffset, endOffset);
695 if (action == Range::Extract || action == Range::Clone) {
696 Ref<CharacterData> characters = downcast<CharacterData>(container->cloneNode(true).get());
697 auto deleteResult = deleteCharacterData(characters, startOffset, endOffset);
698 if (deleteResult.hasException())
699 return deleteResult.releaseException();
700 if (fragment) {
701 result = fragment;
702 auto appendResult = result->appendChild(characters);
703 if (appendResult.hasException())
704 return appendResult.releaseException();
705 } else
706 result = WTFMove(characters);
707 }
708 if (action == Range::Extract || action == Range::Delete) {
709 auto deleteResult = downcast<CharacterData>(*container).deleteData(startOffset, endOffset - startOffset);
710 if (deleteResult.hasException())
711 return deleteResult.releaseException();
712 }
713 break;
714 case Node::PROCESSING_INSTRUCTION_NODE: {
715 auto& instruction = downcast<ProcessingInstruction>(*container);
716 endOffset = std::min(endOffset, downcast<ProcessingInstruction>(*container).data().length());
717 startOffset = std::min(startOffset, endOffset);
718 if (action == Range::Extract || action == Range::Clone) {
719 Ref<ProcessingInstruction> processingInstruction = downcast<ProcessingInstruction>(container->cloneNode(true).get());
720 processingInstruction->setData(processingInstruction->data().substring(startOffset, endOffset - startOffset));
721 if (fragment) {
722 result = fragment;
723 auto appendResult = result->appendChild(processingInstruction);
724 if (appendResult.hasException())
725 return appendResult.releaseException();
726 } else
727 result = WTFMove(processingInstruction);
728 }
729 if (action == Range::Extract || action == Range::Delete) {
730 String data { instruction.data() };
731 data.remove(startOffset, endOffset - startOffset);
732 instruction.setData(data);
733 }
734 break;
735 }
736 case Node::ELEMENT_NODE:
737 case Node::ATTRIBUTE_NODE:
738 case Node::DOCUMENT_NODE:
739 case Node::DOCUMENT_TYPE_NODE:
740 case Node::DOCUMENT_FRAGMENT_NODE:
741 // FIXME: Should we assert that some nodes never appear here?
742 if (action == Range::Extract || action == Range::Clone) {
743 if (fragment)
744 result = fragment;
745 else
746 result = container->cloneNode(false);
747 }
748 Vector<Ref<Node>> nodes;
749 Node* n = container->firstChild();
750 for (unsigned i = startOffset; n && i; i--)
751 n = n->nextSibling();
752 for (unsigned i = startOffset; n && i < endOffset; i++, n = n->nextSibling()) {
753 if (action != Range::Delete && n->isDocumentTypeNode()) {
754 return Exception { HierarchyRequestError };
755 }
756 nodes.append(*n);
757 }
758 auto processResult = processNodes(action, nodes, container.get(), result);
759 if (processResult.hasException())
760 return processResult.releaseException();
761 break;
762 }
763
764 return result;
765}
766
767static ExceptionOr<void> processNodes(Range::ActionType action, Vector<Ref<Node>>& nodes, Node* oldContainer, RefPtr<Node> newContainer)
768{
769 for (auto& node : nodes) {
770 switch (action) {
771 case Range::Delete: {
772 auto result = oldContainer->removeChild(node);
773 if (result.hasException())
774 return result.releaseException();
775 break;
776 }
777 case Range::Extract: {
778 auto result = newContainer->appendChild(node); // will remove node from its parent
779 if (result.hasException())
780 return result.releaseException();
781 break;
782 }
783 case Range::Clone: {
784 auto result = newContainer->appendChild(node->cloneNode(true));
785 if (result.hasException())
786 return result.releaseException();
787 break;
788 }
789 }
790 }
791 return { };
792}
793
794ExceptionOr<RefPtr<Node>> processAncestorsAndTheirSiblings(Range::ActionType action, Node* container, ContentsProcessDirection direction, ExceptionOr<RefPtr<Node>>&& passedClonedContainer, Node* commonRoot)
795{
796 if (passedClonedContainer.hasException())
797 return WTFMove(passedClonedContainer);
798
799 RefPtr<Node> clonedContainer = passedClonedContainer.releaseReturnValue();
800
801 Vector<Ref<ContainerNode>> ancestors;
802 for (ContainerNode* ancestor = container->parentNode(); ancestor && ancestor != commonRoot; ancestor = ancestor->parentNode())
803 ancestors.append(*ancestor);
804
805 RefPtr<Node> firstChildInAncestorToProcess = direction == ProcessContentsForward ? container->nextSibling() : container->previousSibling();
806 for (auto& ancestor : ancestors) {
807 if (action == Range::Extract || action == Range::Clone) {
808 auto clonedAncestor = ancestor->cloneNode(false); // Might have been removed already during mutation event.
809 if (clonedContainer) {
810 auto result = clonedAncestor->appendChild(*clonedContainer);
811 if (result.hasException())
812 return result.releaseException();
813 }
814 clonedContainer = WTFMove(clonedAncestor);
815 }
816
817 // Copy siblings of an ancestor of start/end containers
818 // FIXME: This assertion may fail if DOM is modified during mutation event
819 // FIXME: Share code with Range::processNodes
820 ASSERT(!firstChildInAncestorToProcess || firstChildInAncestorToProcess->parentNode() == ancestor.ptr());
821
822 Vector<Ref<Node>> nodes;
823 for (Node* child = firstChildInAncestorToProcess.get(); child;
824 child = (direction == ProcessContentsForward) ? child->nextSibling() : child->previousSibling())
825 nodes.append(*child);
826
827 for (auto& child : nodes) {
828 switch (action) {
829 case Range::Delete: {
830 auto result = ancestor->removeChild(child);
831 if (result.hasException())
832 return result.releaseException();
833 break;
834 }
835 case Range::Extract: // will remove child from ancestor
836 if (direction == ProcessContentsForward) {
837 auto result = clonedContainer->appendChild(child);
838 if (result.hasException())
839 return result.releaseException();
840 } else {
841 auto result = clonedContainer->insertBefore(child, clonedContainer->firstChild());
842 if (result.hasException())
843 return result.releaseException();
844 }
845 break;
846 case Range::Clone:
847 if (direction == ProcessContentsForward) {
848 auto result = clonedContainer->appendChild(child->cloneNode(true));
849 if (result.hasException())
850 return result.releaseException();
851 } else {
852 auto result = clonedContainer->insertBefore(child->cloneNode(true), clonedContainer->firstChild());
853 if (result.hasException())
854 return result.releaseException();
855 }
856 break;
857 }
858 }
859 firstChildInAncestorToProcess = direction == ProcessContentsForward ? ancestor->nextSibling() : ancestor->previousSibling();
860 }
861
862 return clonedContainer;
863}
864
865ExceptionOr<Ref<DocumentFragment>> Range::extractContents()
866{
867 auto result = processContents(Extract);
868 if (result.hasException())
869 return result.releaseException();
870 return result.releaseReturnValue().releaseNonNull();
871}
872
873ExceptionOr<Ref<DocumentFragment>> Range::cloneContents()
874{
875 auto result = processContents(Clone);
876 if (result.hasException())
877 return result.releaseException();
878 return result.releaseReturnValue().releaseNonNull();
879}
880
881ExceptionOr<void> Range::insertNode(Ref<Node>&& node)
882{
883 auto startContainerNodeType = startContainer().nodeType();
884
885 if (startContainerNodeType == Node::COMMENT_NODE || startContainerNodeType == Node::PROCESSING_INSTRUCTION_NODE)
886 return Exception { HierarchyRequestError };
887 bool startIsText = startContainerNodeType == Node::TEXT_NODE;
888 if (startIsText && !startContainer().parentNode())
889 return Exception { HierarchyRequestError };
890 if (node.ptr() == &startContainer())
891 return Exception { HierarchyRequestError };
892
893 RefPtr<Node> referenceNode = startIsText ? &startContainer() : startContainer().traverseToChildAt(startOffset());
894 Node* parentNode = referenceNode ? referenceNode->parentNode() : &startContainer();
895 if (!is<ContainerNode>(parentNode))
896 return Exception { HierarchyRequestError };
897
898 Ref<ContainerNode> parent = downcast<ContainerNode>(*parentNode);
899
900 auto result = parent->ensurePreInsertionValidity(node, referenceNode.get());
901 if (result.hasException())
902 return result.releaseException();
903
904 EventQueueScope scope;
905 if (startIsText) {
906 auto result = downcast<Text>(startContainer()).splitText(startOffset());
907 if (result.hasException())
908 return result.releaseException();
909 referenceNode = result.releaseReturnValue();
910 }
911
912 if (referenceNode == node.ptr())
913 referenceNode = referenceNode->nextSibling();
914
915 auto removeResult = node->remove();
916 if (removeResult.hasException())
917 return removeResult.releaseException();
918
919 unsigned newOffset = referenceNode ? referenceNode->computeNodeIndex() : parent->countChildNodes();
920 if (is<DocumentFragment>(node))
921 newOffset += downcast<DocumentFragment>(node.get()).countChildNodes();
922 else
923 ++newOffset;
924
925 auto insertResult = parent->insertBefore(node, referenceNode.get());
926 if (insertResult.hasException())
927 return insertResult.releaseException();
928
929 if (collapsed())
930 return setEnd(WTFMove(parent), newOffset);
931
932 return { };
933}
934
935String Range::toString() const
936{
937 StringBuilder builder;
938
939 Node* pastLast = pastLastNode();
940 for (Node* node = firstNode(); node != pastLast; node = NodeTraversal::next(*node)) {
941 auto type = node->nodeType();
942 if (type == Node::TEXT_NODE || type == Node::CDATA_SECTION_NODE) {
943 auto& data = downcast<CharacterData>(*node).data();
944 unsigned length = data.length();
945 unsigned start = node == &startContainer() ? std::min(m_start.offset(), length) : 0U;
946 unsigned end = node == &endContainer() ? std::min(std::max(start, m_end.offset()), length) : length;
947 builder.append(data, start, end - start);
948 }
949 }
950
951 return builder.toString();
952}
953
954String Range::text() const
955{
956 // We need to update layout, since plainText uses line boxes in the render tree.
957 // FIXME: As with innerText, we'd like this to work even if there are no render objects.
958 startContainer().document().updateLayout();
959
960 return plainText(this);
961}
962
963// https://w3c.github.io/DOM-Parsing/#widl-Range-createContextualFragment-DocumentFragment-DOMString-fragment
964ExceptionOr<Ref<DocumentFragment>> Range::createContextualFragment(const String& markup)
965{
966 Node& node = startContainer();
967 RefPtr<Element> element;
968 if (is<Document>(node) || is<DocumentFragment>(node))
969 element = nullptr;
970 else if (is<Element>(node))
971 element = &downcast<Element>(node);
972 else
973 element = node.parentElement();
974 if (!element || (element->document().isHTMLDocument() && is<HTMLHtmlElement>(*element)))
975 element = HTMLBodyElement::create(node.document());
976 return WebCore::createContextualFragment(*element, markup, AllowScriptingContentAndDoNotMarkAlreadyStarted);
977}
978
979void Range::detach()
980{
981 // This is now a no-op as per the DOM specification.
982}
983
984ExceptionOr<Node*> Range::checkNodeWOffset(Node& node, unsigned offset) const
985{
986 switch (node.nodeType()) {
987 case Node::DOCUMENT_TYPE_NODE:
988 return Exception { InvalidNodeTypeError };
989 case Node::CDATA_SECTION_NODE:
990 case Node::COMMENT_NODE:
991 case Node::TEXT_NODE:
992 case Node::PROCESSING_INSTRUCTION_NODE:
993 if (offset > downcast<CharacterData>(node).length())
994 return Exception { IndexSizeError };
995 return nullptr;
996 case Node::ATTRIBUTE_NODE:
997 case Node::DOCUMENT_FRAGMENT_NODE:
998 case Node::DOCUMENT_NODE:
999 case Node::ELEMENT_NODE: {
1000 if (!offset)
1001 return nullptr;
1002 Node* childBefore = node.traverseToChildAt(offset - 1);
1003 if (!childBefore)
1004 return Exception { IndexSizeError };
1005 return childBefore;
1006 }
1007 }
1008 ASSERT_NOT_REACHED();
1009 return Exception { InvalidNodeTypeError };
1010}
1011
1012Ref<Range> Range::cloneRange() const
1013{
1014 return Range::create(ownerDocument(), &startContainer(), m_start.offset(), &endContainer(), m_end.offset());
1015}
1016
1017ExceptionOr<void> Range::setStartAfter(Node& refNode)
1018{
1019 if (!refNode.parentNode())
1020 return Exception { InvalidNodeTypeError };
1021 return setStart(*refNode.parentNode(), refNode.computeNodeIndex() + 1);
1022}
1023
1024ExceptionOr<void> Range::setEndBefore(Node& refNode)
1025{
1026 if (!refNode.parentNode())
1027 return Exception { InvalidNodeTypeError };
1028 return setEnd(*refNode.parentNode(), refNode.computeNodeIndex());
1029}
1030
1031ExceptionOr<void> Range::setEndAfter(Node& refNode)
1032{
1033 if (!refNode.parentNode())
1034 return Exception { InvalidNodeTypeError };
1035 return setEnd(*refNode.parentNode(), refNode.computeNodeIndex() + 1);
1036}
1037
1038ExceptionOr<void> Range::selectNode(Node& refNode)
1039{
1040 if (!refNode.parentNode())
1041 return Exception { InvalidNodeTypeError };
1042
1043 if (&ownerDocument() != &refNode.document())
1044 setDocument(refNode.document());
1045
1046 unsigned index = refNode.computeNodeIndex();
1047 auto result = setStart(*refNode.parentNode(), index);
1048 if (result.hasException())
1049 return result.releaseException();
1050 return setEnd(*refNode.parentNode(), index + 1);
1051}
1052
1053ExceptionOr<void> Range::selectNodeContents(Node& refNode)
1054{
1055 if (refNode.isDocumentTypeNode())
1056 return Exception { InvalidNodeTypeError };
1057
1058 if (&ownerDocument() != &refNode.document())
1059 setDocument(refNode.document());
1060
1061 m_start.setToStartOfNode(refNode);
1062 m_end.setToEndOfNode(refNode);
1063
1064 return { };
1065}
1066
1067// https://dom.spec.whatwg.org/#dom-range-surroundcontents
1068ExceptionOr<void> Range::surroundContents(Node& newParent)
1069{
1070 Ref<Node> protectedNewParent(newParent);
1071
1072 // Step 1: If a non-Text node is partially contained in the context object, then throw an InvalidStateError.
1073 Node* startNonTextContainer = &startContainer();
1074 if (startNonTextContainer->nodeType() == Node::TEXT_NODE)
1075 startNonTextContainer = startNonTextContainer->parentNode();
1076 Node* endNonTextContainer = &endContainer();
1077 if (endNonTextContainer->nodeType() == Node::TEXT_NODE)
1078 endNonTextContainer = endNonTextContainer->parentNode();
1079 if (startNonTextContainer != endNonTextContainer)
1080 return Exception { InvalidStateError };
1081
1082 // Step 2: If newParent is a Document, DocumentType, or DocumentFragment node, then throw an InvalidNodeTypeError.
1083 switch (newParent.nodeType()) {
1084 case Node::ATTRIBUTE_NODE:
1085 case Node::DOCUMENT_FRAGMENT_NODE:
1086 case Node::DOCUMENT_NODE:
1087 case Node::DOCUMENT_TYPE_NODE:
1088 return Exception { InvalidNodeTypeError };
1089 case Node::CDATA_SECTION_NODE:
1090 case Node::COMMENT_NODE:
1091 case Node::ELEMENT_NODE:
1092 case Node::PROCESSING_INSTRUCTION_NODE:
1093 case Node::TEXT_NODE:
1094 break;
1095 }
1096
1097 // Step 3: Let fragment be the result of extracting context object.
1098 auto fragment = extractContents();
1099 if (fragment.hasException())
1100 return fragment.releaseException();
1101
1102 // Step 4: If newParent has children, replace all with null within newParent.
1103 if (newParent.hasChildNodes())
1104 downcast<ContainerNode>(newParent).replaceAllChildren(nullptr);
1105
1106 // Step 5: Insert newParent into context object.
1107 auto insertResult = insertNode(newParent);
1108 if (insertResult.hasException())
1109 return insertResult.releaseException();
1110
1111 // Step 6: Append fragment to newParent.
1112 auto appendResult = newParent.appendChild(fragment.releaseReturnValue());
1113 if (appendResult.hasException())
1114 return appendResult.releaseException();
1115
1116 // Step 7: Select newParent within context object.
1117 return selectNode(newParent);
1118}
1119
1120ExceptionOr<void> Range::setStartBefore(Node& refNode)
1121{
1122 if (!refNode.parentNode())
1123 return Exception { InvalidNodeTypeError };
1124 return setStart(*refNode.parentNode(), refNode.computeNodeIndex());
1125}
1126
1127Node* Range::firstNode() const
1128{
1129 if (startContainer().isCharacterDataNode())
1130 return &startContainer();
1131 if (Node* child = startContainer().traverseToChildAt(m_start.offset()))
1132 return child;
1133 if (!m_start.offset())
1134 return &startContainer();
1135 return NodeTraversal::nextSkippingChildren(startContainer());
1136}
1137
1138ShadowRoot* Range::shadowRoot() const
1139{
1140 return startContainer().containingShadowRoot();
1141}
1142
1143Node* Range::pastLastNode() const
1144{
1145 if (endContainer().isCharacterDataNode())
1146 return NodeTraversal::nextSkippingChildren(endContainer());
1147 if (Node* child = endContainer().traverseToChildAt(m_end.offset()))
1148 return child;
1149 return NodeTraversal::nextSkippingChildren(endContainer());
1150}
1151
1152IntRect Range::absoluteBoundingBox() const
1153{
1154 IntRect result;
1155 Vector<IntRect> rects;
1156 absoluteTextRects(rects);
1157 for (auto& rect : rects)
1158 result.unite(rect);
1159 return result;
1160}
1161
1162Vector<FloatRect> Range::absoluteRectsForRangeInText(Node* node, RenderText& renderText, bool useSelectionHeight, bool& isFixed, RespectClippingForTextRects respectClippingForTextRects) const
1163{
1164 unsigned startOffset = node == &startContainer() ? m_start.offset() : 0;
1165 unsigned endOffset = node == &endContainer() ? m_end.offset() : std::numeric_limits<unsigned>::max();
1166
1167 auto textQuads = renderText.absoluteQuadsForRange(startOffset, endOffset, useSelectionHeight, &isFixed);
1168
1169 if (respectClippingForTextRects == RespectClippingForTextRects::Yes) {
1170 Vector<FloatRect> clippedRects;
1171 clippedRects.reserveInitialCapacity(textQuads.size());
1172
1173 auto absoluteClippedOverflowRect = renderText.absoluteClippedOverflowRect();
1174
1175 for (auto& quad : textQuads) {
1176 auto clippedRect = intersection(quad.boundingBox(), absoluteClippedOverflowRect);
1177 if (!clippedRect.isEmpty())
1178 clippedRects.uncheckedAppend(clippedRect);
1179 }
1180
1181 return clippedRects;
1182 }
1183
1184 Vector<FloatRect> floatRects;
1185 floatRects.reserveInitialCapacity(textQuads.size());
1186 for (auto& quad : textQuads)
1187 floatRects.uncheckedAppend(quad.boundingBox());
1188 return floatRects;
1189}
1190
1191void Range::absoluteTextRects(Vector<IntRect>& rects, bool useSelectionHeight, RangeInFixedPosition* inFixed, RespectClippingForTextRects respectClippingForTextRects) const
1192{
1193 // FIXME: This function should probably return FloatRects.
1194
1195 bool allFixed = true;
1196 bool someFixed = false;
1197
1198 Node* stopNode = pastLastNode();
1199 for (Node* node = firstNode(); node != stopNode; node = NodeTraversal::next(*node)) {
1200 RenderObject* renderer = node->renderer();
1201 if (!renderer)
1202 continue;
1203 bool isFixed = false;
1204 if (renderer->isBR())
1205 renderer->absoluteRects(rects, flooredLayoutPoint(renderer->localToAbsolute()));
1206 else if (is<RenderText>(*renderer)) {
1207 auto rectsForRenderer = absoluteRectsForRangeInText(node, downcast<RenderText>(*renderer), useSelectionHeight, isFixed, respectClippingForTextRects);
1208 for (auto& rect : rectsForRenderer)
1209 rects.append(enclosingIntRect(rect));
1210 } else
1211 continue;
1212 allFixed &= isFixed;
1213 someFixed |= isFixed;
1214 }
1215
1216 if (inFixed)
1217 *inFixed = allFixed ? EntirelyFixedPosition : (someFixed ? PartiallyFixedPosition : NotFixedPosition);
1218}
1219
1220void Range::absoluteTextQuads(Vector<FloatQuad>& quads, bool useSelectionHeight, RangeInFixedPosition* inFixed) const
1221{
1222 bool allFixed = true;
1223 bool someFixed = false;
1224
1225 Node* stopNode = pastLastNode();
1226 for (Node* node = firstNode(); node != stopNode; node = NodeTraversal::next(*node)) {
1227 RenderObject* renderer = node->renderer();
1228 if (!renderer)
1229 continue;
1230 bool isFixed = false;
1231 if (renderer->isBR())
1232 renderer->absoluteQuads(quads, &isFixed);
1233 else if (is<RenderText>(*renderer)) {
1234 unsigned startOffset = node == &startContainer() ? m_start.offset() : 0;
1235 unsigned endOffset = node == &endContainer() ? m_end.offset() : std::numeric_limits<unsigned>::max();
1236 quads.appendVector(downcast<RenderText>(*renderer).absoluteQuadsForRange(startOffset, endOffset, useSelectionHeight, &isFixed));
1237 } else
1238 continue;
1239 allFixed &= isFixed;
1240 someFixed |= isFixed;
1241 }
1242
1243 if (inFixed)
1244 *inFixed = allFixed ? EntirelyFixedPosition : (someFixed ? PartiallyFixedPosition : NotFixedPosition);
1245}
1246
1247#if PLATFORM(IOS_FAMILY)
1248static bool intervalsSufficientlyOverlap(int startA, int endA, int startB, int endB)
1249{
1250 if (endA <= startA || endB <= startB)
1251 return false;
1252
1253 const float sufficientOverlap = .75;
1254
1255 int lengthA = endA - startA;
1256 int lengthB = endB - startB;
1257
1258 int maxStart = std::max(startA, startB);
1259 int minEnd = std::min(endA, endB);
1260
1261 if (maxStart > minEnd)
1262 return false;
1263
1264 return minEnd - maxStart >= sufficientOverlap * std::min(lengthA, lengthB);
1265}
1266
1267static inline void adjustLineHeightOfSelectionRects(Vector<SelectionRect>& rects, size_t numberOfRects, int lineNumber, int lineTop, int lineHeight)
1268{
1269 ASSERT(rects.size() >= numberOfRects);
1270 for (size_t i = numberOfRects; i; ) {
1271 --i;
1272 if (rects[i].lineNumber())
1273 break;
1274 rects[i].setLineNumber(lineNumber);
1275 rects[i].setLogicalTop(lineTop);
1276 rects[i].setLogicalHeight(lineHeight);
1277 }
1278}
1279
1280static SelectionRect coalesceSelectionRects(const SelectionRect& original, const SelectionRect& previous)
1281{
1282 SelectionRect result(unionRect(previous.rect(), original.rect()), original.isHorizontal(), original.pageNumber());
1283 result.setDirection(original.containsStart() || original.containsEnd() ? original.direction() : previous.direction());
1284 result.setContainsStart(previous.containsStart() || original.containsStart());
1285 result.setContainsEnd(previous.containsEnd() || original.containsEnd());
1286 result.setIsFirstOnLine(previous.isFirstOnLine() || original.isFirstOnLine());
1287 result.setIsLastOnLine(previous.isLastOnLine() || original.isLastOnLine());
1288 return result;
1289}
1290
1291// This function is similar in spirit to addLineBoxRects, but annotates the returned rectangles
1292// with additional state which helps iOS draw selections in its unique way.
1293int Range::collectSelectionRectsWithoutUnionInteriorLines(Vector<SelectionRect>& rects) const
1294{
1295 auto& startContainer = this->startContainer();
1296 auto& endContainer = this->endContainer();
1297 int startOffset = m_start.offset();
1298 int endOffset = m_end.offset();
1299
1300 Vector<SelectionRect> newRects;
1301 Node* stopNode = pastLastNode();
1302 bool hasFlippedWritingMode = startContainer.renderer() && startContainer.renderer()->style().isFlippedBlocksWritingMode();
1303 bool containsDifferentWritingModes = false;
1304 for (Node* node = firstNode(); node && node != stopNode; node = NodeTraversal::next(*node)) {
1305 RenderObject* renderer = node->renderer();
1306 // Only ask leaf render objects for their line box rects.
1307 if (renderer && !renderer->firstChildSlow() && renderer->style().userSelect() != UserSelect::None) {
1308 bool isStartNode = renderer->node() == &startContainer;
1309 bool isEndNode = renderer->node() == &endContainer;
1310 if (hasFlippedWritingMode != renderer->style().isFlippedBlocksWritingMode())
1311 containsDifferentWritingModes = true;
1312 // FIXME: Sending 0 for the startOffset is a weird way of telling the renderer that the selection
1313 // doesn't start inside it, since we'll also send 0 if the selection *does* start in it, at offset 0.
1314 //
1315 // FIXME: Selection endpoints aren't always inside leaves, and we only build SelectionRects for leaves,
1316 // so we can't accurately determine which SelectionRects contain the selection start and end using
1317 // only the offsets of the start and end. We need to pass the whole Range.
1318 int beginSelectionOffset = isStartNode ? startOffset : 0;
1319 int endSelectionOffset = isEndNode ? endOffset : std::numeric_limits<int>::max();
1320 renderer->collectSelectionRects(newRects, beginSelectionOffset, endSelectionOffset);
1321 for (auto& selectionRect : newRects) {
1322 if (selectionRect.containsStart() && !isStartNode)
1323 selectionRect.setContainsStart(false);
1324 if (selectionRect.containsEnd() && !isEndNode)
1325 selectionRect.setContainsEnd(false);
1326 if (selectionRect.logicalWidth() || selectionRect.logicalHeight())
1327 rects.append(selectionRect);
1328 }
1329 newRects.shrink(0);
1330 }
1331 }
1332
1333 // The range could span over nodes with different writing modes.
1334 // If this is the case, we use the writing mode of the common ancestor.
1335 if (containsDifferentWritingModes) {
1336 if (Node* ancestor = commonAncestorContainer(&startContainer, &endContainer))
1337 hasFlippedWritingMode = ancestor->renderer()->style().isFlippedBlocksWritingMode();
1338 }
1339
1340 const size_t numberOfRects = rects.size();
1341
1342 // If the selection ends in a BR, then add the line break bit to the last
1343 // rect we have. This will cause its selection rect to extend to the
1344 // end of the line.
1345 if (stopNode && stopNode->hasTagName(HTMLNames::brTag) && numberOfRects) {
1346 // Only set the line break bit if the end of the range actually
1347 // extends all the way to include the <br>. VisiblePosition helps to
1348 // figure this out.
1349 VisiblePosition endPosition(createLegacyEditingPosition(&endContainer, endOffset), VP_DEFAULT_AFFINITY);
1350 VisiblePosition brPosition(createLegacyEditingPosition(stopNode, 0), VP_DEFAULT_AFFINITY);
1351 if (endPosition == brPosition)
1352 rects.last().setIsLineBreak(true);
1353 }
1354
1355 int lineTop = std::numeric_limits<int>::max();
1356 int lineBottom = std::numeric_limits<int>::min();
1357 int lastLineTop = lineTop;
1358 int lastLineBottom = lineBottom;
1359 int lineNumber = 0;
1360
1361 for (size_t i = 0; i < numberOfRects; ++i) {
1362 int currentRectTop = rects[i].logicalTop();
1363 int currentRectBottom = currentRectTop + rects[i].logicalHeight();
1364
1365 // We don't want to count the ruby text as a separate line.
1366 if (intervalsSufficientlyOverlap(currentRectTop, currentRectBottom, lineTop, lineBottom) || (i && rects[i].isRubyText())) {
1367 // Grow the current line bounds.
1368 lineTop = std::min(lineTop, currentRectTop);
1369 lineBottom = std::max(lineBottom, currentRectBottom);
1370 // Avoid overlap with the previous line.
1371 if (!hasFlippedWritingMode)
1372 lineTop = std::max(lastLineBottom, lineTop);
1373 else
1374 lineBottom = std::min(lastLineTop, lineBottom);
1375 } else {
1376 adjustLineHeightOfSelectionRects(rects, i, lineNumber, lineTop, lineBottom - lineTop);
1377 if (!hasFlippedWritingMode) {
1378 lastLineTop = lineTop;
1379 if (currentRectBottom >= lastLineTop) {
1380 lastLineBottom = lineBottom;
1381 lineTop = lastLineBottom;
1382 } else {
1383 lineTop = currentRectTop;
1384 lastLineBottom = std::numeric_limits<int>::min();
1385 }
1386 lineBottom = currentRectBottom;
1387 } else {
1388 lastLineBottom = lineBottom;
1389 if (currentRectTop <= lastLineBottom && i && rects[i].pageNumber() == rects[i - 1].pageNumber()) {
1390 lastLineTop = lineTop;
1391 lineBottom = lastLineTop;
1392 } else {
1393 lastLineTop = std::numeric_limits<int>::max();
1394 lineBottom = currentRectBottom;
1395 }
1396 lineTop = currentRectTop;
1397 }
1398 ++lineNumber;
1399 }
1400 }
1401
1402 // Adjust line height.
1403 adjustLineHeightOfSelectionRects(rects, numberOfRects, lineNumber, lineTop, lineBottom - lineTop);
1404
1405 // Sort the rectangles and make sure there are no gaps. The rectangles could be unsorted when
1406 // there is ruby text and we could have gaps on the line when adjacent elements on the line
1407 // have a different orientation.
1408 size_t firstRectWithCurrentLineNumber = 0;
1409 for (size_t currentRect = 1; currentRect < numberOfRects; ++currentRect) {
1410 if (rects[currentRect].lineNumber() != rects[currentRect - 1].lineNumber()) {
1411 firstRectWithCurrentLineNumber = currentRect;
1412 continue;
1413 }
1414 if (rects[currentRect].logicalLeft() >= rects[currentRect - 1].logicalLeft())
1415 continue;
1416
1417 SelectionRect selectionRect = rects[currentRect];
1418 size_t i;
1419 for (i = currentRect; i > firstRectWithCurrentLineNumber && selectionRect.logicalLeft() < rects[i - 1].logicalLeft(); --i)
1420 rects[i] = rects[i - 1];
1421 rects[i] = selectionRect;
1422 }
1423
1424 for (size_t j = 1; j < numberOfRects; ++j) {
1425 if (rects[j].lineNumber() != rects[j - 1].lineNumber())
1426 continue;
1427 SelectionRect& previousRect = rects[j - 1];
1428 bool previousRectMayNotReachRightEdge = (previousRect.direction() == TextDirection::LTR && previousRect.containsEnd()) || (previousRect.direction() == TextDirection::RTL && previousRect.containsStart());
1429 if (previousRectMayNotReachRightEdge)
1430 continue;
1431 int adjustedWidth = rects[j].logicalLeft() - previousRect.logicalLeft();
1432 if (adjustedWidth > previousRect.logicalWidth())
1433 previousRect.setLogicalWidth(adjustedWidth);
1434 }
1435
1436 int maxLineNumber = lineNumber;
1437
1438 // Extend rects out to edges as needed.
1439 for (size_t i = 0; i < numberOfRects; ++i) {
1440 SelectionRect& selectionRect = rects[i];
1441 if (!selectionRect.isLineBreak() && selectionRect.lineNumber() >= maxLineNumber)
1442 continue;
1443 if (selectionRect.direction() == TextDirection::RTL && selectionRect.isFirstOnLine()) {
1444 selectionRect.setLogicalWidth(selectionRect.logicalWidth() + selectionRect.logicalLeft() - selectionRect.minX());
1445 selectionRect.setLogicalLeft(selectionRect.minX());
1446 } else if (selectionRect.direction() == TextDirection::LTR && selectionRect.isLastOnLine())
1447 selectionRect.setLogicalWidth(selectionRect.maxX() - selectionRect.logicalLeft());
1448 }
1449
1450 return maxLineNumber;
1451}
1452
1453void Range::collectSelectionRects(Vector<SelectionRect>& rects) const
1454{
1455 int maxLineNumber = collectSelectionRectsWithoutUnionInteriorLines(rects);
1456 const size_t numberOfRects = rects.size();
1457
1458 // Union all the rectangles on interior lines (i.e. not first or last).
1459 // On first and last lines, just avoid having overlaps by merging intersecting rectangles.
1460 Vector<SelectionRect> unionedRects;
1461 IntRect interiorUnionRect;
1462 for (size_t i = 0; i < numberOfRects; ++i) {
1463 SelectionRect& currentRect = rects[i];
1464 if (currentRect.lineNumber() == 1) {
1465 ASSERT(interiorUnionRect.isEmpty());
1466 if (!unionedRects.isEmpty()) {
1467 SelectionRect& previousRect = unionedRects.last();
1468 if (previousRect.rect().intersects(currentRect.rect())) {
1469 previousRect = coalesceSelectionRects(currentRect, previousRect);
1470 continue;
1471 }
1472 }
1473 // Couldn't merge with previous rect, so just appending.
1474 unionedRects.append(currentRect);
1475 } else if (currentRect.lineNumber() < maxLineNumber) {
1476 if (interiorUnionRect.isEmpty()) {
1477 // Start collecting interior rects.
1478 interiorUnionRect = currentRect.rect();
1479 } else if (interiorUnionRect.intersects(currentRect.rect())
1480 || interiorUnionRect.maxX() == currentRect.rect().x()
1481 || interiorUnionRect.maxY() == currentRect.rect().y()
1482 || interiorUnionRect.x() == currentRect.rect().maxX()
1483 || interiorUnionRect.y() == currentRect.rect().maxY()) {
1484 // Only union the lines that are attached.
1485 // For iBooks, the interior lines may cross multiple horizontal pages.
1486 interiorUnionRect.unite(currentRect.rect());
1487 } else {
1488 unionedRects.append(SelectionRect(interiorUnionRect, currentRect.isHorizontal(), currentRect.pageNumber()));
1489 interiorUnionRect = currentRect.rect();
1490 }
1491 } else {
1492 // Processing last line.
1493 if (!interiorUnionRect.isEmpty()) {
1494 unionedRects.append(SelectionRect(interiorUnionRect, currentRect.isHorizontal(), currentRect.pageNumber()));
1495 interiorUnionRect = IntRect();
1496 }
1497
1498 ASSERT(!unionedRects.isEmpty());
1499 SelectionRect& previousRect = unionedRects.last();
1500 if (previousRect.logicalTop() == currentRect.logicalTop() && previousRect.rect().intersects(currentRect.rect())) {
1501 // previousRect is also on the last line, and intersects the current one.
1502 previousRect = coalesceSelectionRects(currentRect, previousRect);
1503 continue;
1504 }
1505 // Couldn't merge with previous rect, so just appending.
1506 unionedRects.append(currentRect);
1507 }
1508 }
1509
1510 rects.swap(unionedRects);
1511}
1512#endif
1513
1514#if ENABLE(TREE_DEBUGGING)
1515void Range::formatForDebugger(char* buffer, unsigned length) const
1516{
1517 StringBuilder result;
1518
1519 const int FormatBufferSize = 1024;
1520 char s[FormatBufferSize];
1521 result.appendLiteral("from offset ");
1522 result.appendNumber(m_start.offset());
1523 result.appendLiteral(" of ");
1524 startContainer().formatForDebugger(s, FormatBufferSize);
1525 result.append(s);
1526 result.appendLiteral(" to offset ");
1527 result.appendNumber(m_end.offset());
1528 result.appendLiteral(" of ");
1529 endContainer().formatForDebugger(s, FormatBufferSize);
1530 result.append(s);
1531
1532 strncpy(buffer, result.toString().utf8().data(), length - 1);
1533}
1534#endif
1535
1536bool Range::contains(const Range& other) const
1537{
1538 if (commonAncestorContainer()->ownerDocument() != other.commonAncestorContainer()->ownerDocument())
1539 return false;
1540
1541 auto startToStart = compareBoundaryPoints(Range::START_TO_START, other);
1542 if (startToStart.hasException() || startToStart.releaseReturnValue() > 0)
1543 return false;
1544
1545 auto endToEnd = compareBoundaryPoints(Range::END_TO_END, other);
1546 return !endToEnd.hasException() && endToEnd.releaseReturnValue() >= 0;
1547}
1548
1549bool Range::contains(const VisiblePosition& position) const
1550{
1551 RefPtr<Range> positionRange = makeRange(position, position);
1552 if (!positionRange)
1553 return false;
1554 return contains(*positionRange);
1555}
1556
1557bool areRangesEqual(const Range* a, const Range* b)
1558{
1559 if (a == b)
1560 return true;
1561 if (!a || !b)
1562 return false;
1563 return a->startPosition() == b->startPosition() && a->endPosition() == b->endPosition();
1564}
1565
1566bool rangesOverlap(const Range* a, const Range* b)
1567{
1568 if (!a || !b)
1569 return false;
1570
1571 if (a == b)
1572 return true;
1573
1574 if (a->commonAncestorContainer()->ownerDocument() != b->commonAncestorContainer()->ownerDocument())
1575 return false;
1576
1577 short startToStart = a->compareBoundaryPoints(Range::START_TO_START, *b).releaseReturnValue();
1578 short endToEnd = a->compareBoundaryPoints(Range::END_TO_END, *b).releaseReturnValue();
1579
1580 // First range contains the second range.
1581 if (startToStart <= 0 && endToEnd >= 0)
1582 return true;
1583
1584 // End of first range is inside second range.
1585 if (a->compareBoundaryPoints(Range::START_TO_END, *b).releaseReturnValue() >= 0 && endToEnd <= 0)
1586 return true;
1587
1588 // Start of first range is inside second range.
1589 if (startToStart >= 0 && a->compareBoundaryPoints(Range::END_TO_START, *b).releaseReturnValue() <= 0)
1590 return true;
1591
1592 return false;
1593}
1594
1595Ref<Range> rangeOfContents(Node& node)
1596{
1597 auto range = Range::create(node.document());
1598 range->selectNodeContents(node);
1599 return range;
1600}
1601
1602static inline void boundaryNodeChildrenChanged(RangeBoundaryPoint& boundary, ContainerNode& container)
1603{
1604 if (!boundary.childBefore())
1605 return;
1606 if (boundary.container() != &container)
1607 return;
1608 boundary.invalidateOffset();
1609}
1610
1611void Range::nodeChildrenChanged(ContainerNode& container)
1612{
1613 ASSERT(&container.document() == &ownerDocument());
1614 boundaryNodeChildrenChanged(m_start, container);
1615 boundaryNodeChildrenChanged(m_end, container);
1616}
1617
1618static inline void boundaryNodeChildrenWillBeRemoved(RangeBoundaryPoint& boundary, ContainerNode& container)
1619{
1620 for (Node* nodeToBeRemoved = container.firstChild(); nodeToBeRemoved; nodeToBeRemoved = nodeToBeRemoved->nextSibling()) {
1621 if (boundary.childBefore() == nodeToBeRemoved) {
1622 boundary.setToStartOfNode(container);
1623 return;
1624 }
1625
1626 for (Node* n = boundary.container(); n; n = n->parentNode()) {
1627 if (n == nodeToBeRemoved) {
1628 boundary.setToStartOfNode(container);
1629 return;
1630 }
1631 }
1632 }
1633}
1634
1635void Range::nodeChildrenWillBeRemoved(ContainerNode& container)
1636{
1637 ASSERT(&container.document() == &ownerDocument());
1638 boundaryNodeChildrenWillBeRemoved(m_start, container);
1639 boundaryNodeChildrenWillBeRemoved(m_end, container);
1640}
1641
1642static inline void boundaryNodeWillBeRemoved(RangeBoundaryPoint& boundary, Node& nodeToBeRemoved)
1643{
1644 if (boundary.childBefore() == &nodeToBeRemoved) {
1645 boundary.childBeforeWillBeRemoved();
1646 return;
1647 }
1648
1649 for (Node* n = boundary.container(); n; n = n->parentNode()) {
1650 if (n == &nodeToBeRemoved) {
1651 boundary.setToBeforeChild(nodeToBeRemoved);
1652 return;
1653 }
1654 }
1655}
1656
1657void Range::nodeWillBeRemoved(Node& node)
1658{
1659 ASSERT(&node.document() == &ownerDocument());
1660 ASSERT(&node != &ownerDocument());
1661 ASSERT(node.parentNode());
1662 boundaryNodeWillBeRemoved(m_start, node);
1663 boundaryNodeWillBeRemoved(m_end, node);
1664}
1665
1666static inline void boundaryTextInserted(RangeBoundaryPoint& boundary, Node& text, unsigned offset, unsigned length)
1667{
1668 if (boundary.container() != &text)
1669 return;
1670 unsigned boundaryOffset = boundary.offset();
1671 if (offset >= boundaryOffset)
1672 return;
1673 boundary.setOffset(boundaryOffset + length);
1674}
1675
1676void Range::textInserted(Node& text, unsigned offset, unsigned length)
1677{
1678 ASSERT(&text.document() == &ownerDocument());
1679 boundaryTextInserted(m_start, text, offset, length);
1680 boundaryTextInserted(m_end, text, offset, length);
1681}
1682
1683static inline void boundaryTextRemoved(RangeBoundaryPoint& boundary, Node& text, unsigned offset, unsigned length)
1684{
1685 if (boundary.container() != &text)
1686 return;
1687 unsigned boundaryOffset = boundary.offset();
1688 if (offset >= boundaryOffset)
1689 return;
1690 if (offset + length >= boundaryOffset)
1691 boundary.setOffset(offset);
1692 else
1693 boundary.setOffset(boundaryOffset - length);
1694}
1695
1696void Range::textRemoved(Node& text, unsigned offset, unsigned length)
1697{
1698 ASSERT(&text.document() == &ownerDocument());
1699 boundaryTextRemoved(m_start, text, offset, length);
1700 boundaryTextRemoved(m_end, text, offset, length);
1701}
1702
1703static inline void boundaryTextNodesMerged(RangeBoundaryPoint& boundary, NodeWithIndex& oldNode, unsigned offset)
1704{
1705 if (boundary.container() == oldNode.node())
1706 boundary.set(*oldNode.node()->previousSibling(), boundary.offset() + offset, 0);
1707 else if (boundary.container() == oldNode.node()->parentNode() && static_cast<int>(boundary.offset()) == oldNode.index())
1708 boundary.set(*oldNode.node()->previousSibling(), offset, 0);
1709}
1710
1711void Range::textNodesMerged(NodeWithIndex& oldNode, unsigned offset)
1712{
1713 ASSERT(oldNode.node());
1714 ASSERT(&oldNode.node()->document() == &ownerDocument());
1715 ASSERT(oldNode.node()->parentNode());
1716 ASSERT(oldNode.node()->isTextNode());
1717 ASSERT(oldNode.node()->previousSibling());
1718 ASSERT(oldNode.node()->previousSibling()->isTextNode());
1719 boundaryTextNodesMerged(m_start, oldNode, offset);
1720 boundaryTextNodesMerged(m_end, oldNode, offset);
1721}
1722
1723static inline void boundaryTextNodesSplit(RangeBoundaryPoint& boundary, Text& oldNode)
1724{
1725 auto* parent = oldNode.parentNode();
1726 if (boundary.container() == &oldNode) {
1727 unsigned splitOffset = oldNode.length();
1728 unsigned boundaryOffset = boundary.offset();
1729 if (boundaryOffset > splitOffset) {
1730 if (parent)
1731 boundary.set(*oldNode.nextSibling(), boundaryOffset - splitOffset, 0);
1732 else
1733 boundary.setOffset(splitOffset);
1734 }
1735 return;
1736 }
1737 if (!parent)
1738 return;
1739 if (boundary.container() == parent && boundary.childBefore() == &oldNode) {
1740 auto* newChild = oldNode.nextSibling();
1741 ASSERT(newChild);
1742 boundary.setToAfterChild(*newChild);
1743 }
1744}
1745
1746void Range::textNodeSplit(Text& oldNode)
1747{
1748 ASSERT(&oldNode.document() == &ownerDocument());
1749 ASSERT(!oldNode.parentNode() || oldNode.nextSibling());
1750 ASSERT(!oldNode.parentNode() || oldNode.nextSibling()->isTextNode());
1751 boundaryTextNodesSplit(m_start, oldNode);
1752 boundaryTextNodesSplit(m_end, oldNode);
1753}
1754
1755ExceptionOr<void> Range::expand(const String& unit)
1756{
1757 VisiblePosition start { startPosition() };
1758 VisiblePosition end { endPosition() };
1759 if (unit == "word") {
1760 start = startOfWord(start);
1761 end = endOfWord(end);
1762 } else if (unit == "sentence") {
1763 start = startOfSentence(start);
1764 end = endOfSentence(end);
1765 } else if (unit == "block") {
1766 start = startOfParagraph(start);
1767 end = endOfParagraph(end);
1768 } else if (unit == "document") {
1769 start = startOfDocument(start);
1770 end = endOfDocument(end);
1771 } else
1772 return { };
1773
1774 auto* startContainer = start.deepEquivalent().containerNode();
1775 if (!startContainer)
1776 return Exception { TypeError };
1777 auto result = setStart(*startContainer, start.deepEquivalent().computeOffsetInContainerNode());
1778 if (result.hasException())
1779 return result.releaseException();
1780 auto* endContainer = end.deepEquivalent().containerNode();
1781 if (!endContainer)
1782 return Exception { TypeError };
1783 return setEnd(*endContainer, end.deepEquivalent().computeOffsetInContainerNode());
1784}
1785
1786Ref<DOMRectList> Range::getClientRects() const
1787{
1788 return DOMRectList::create(borderAndTextRects(CoordinateSpace::Client));
1789}
1790
1791Ref<DOMRect> Range::getBoundingClientRect() const
1792{
1793 return DOMRect::create(boundingRect(CoordinateSpace::Client));
1794}
1795
1796Vector<FloatRect> Range::borderAndTextRects(CoordinateSpace space, RespectClippingForTextRects respectClippingForTextRects) const
1797{
1798 Vector<FloatRect> rects;
1799
1800 ownerDocument().updateLayoutIgnorePendingStylesheets();
1801
1802 Node* stopNode = pastLastNode();
1803
1804 HashSet<Node*> selectedElementsSet;
1805 for (Node* node = firstNode(); node != stopNode; node = NodeTraversal::next(*node)) {
1806 if (is<Element>(*node))
1807 selectedElementsSet.add(node);
1808 }
1809
1810 // Don't include elements that are only partially selected.
1811 Node* lastNode = m_end.childBefore() ? m_end.childBefore() : &endContainer();
1812 for (Node* parent = lastNode->parentNode(); parent; parent = parent->parentNode())
1813 selectedElementsSet.remove(parent);
1814
1815 for (Node* node = firstNode(); node != stopNode; node = NodeTraversal::next(*node)) {
1816 if (is<Element>(*node) && selectedElementsSet.contains(node) && (!node->parentNode() || !selectedElementsSet.contains(node->parentNode()))) {
1817 if (auto* renderer = downcast<Element>(*node).renderBoxModelObject()) {
1818 Vector<FloatQuad> elementQuads;
1819 renderer->absoluteQuads(elementQuads);
1820 if (space == CoordinateSpace::Client)
1821 node->document().convertAbsoluteToClientQuads(elementQuads, renderer->style());
1822
1823 for (auto& quad : elementQuads)
1824 rects.append(quad.boundingBox());
1825 }
1826 } else if (is<Text>(*node)) {
1827 if (auto* renderer = downcast<Text>(*node).renderer()) {
1828 bool isFixed;
1829 auto clippedRects = absoluteRectsForRangeInText(node, *renderer, false, isFixed, respectClippingForTextRects);
1830 if (space == CoordinateSpace::Client)
1831 node->document().convertAbsoluteToClientRects(clippedRects, renderer->style());
1832
1833 rects.appendVector(clippedRects);
1834 }
1835 }
1836 }
1837
1838 return rects;
1839}
1840
1841FloatRect Range::boundingRect(CoordinateSpace space, RespectClippingForTextRects respectClippingForTextRects) const
1842{
1843 FloatRect result;
1844 for (auto& rect : borderAndTextRects(space, respectClippingForTextRects))
1845 result.uniteIfNonZero(rect);
1846 return result;
1847}
1848
1849FloatRect Range::absoluteBoundingRect(RespectClippingForTextRects respectClippingForTextRects) const
1850{
1851 return boundingRect(CoordinateSpace::Absolute, respectClippingForTextRects);
1852}
1853
1854WTF::TextStream& operator<<(WTF::TextStream& ts, const RangeBoundaryPoint& r)
1855{
1856 return ts << r.toPosition();
1857}
1858
1859WTF::TextStream& operator<<(WTF::TextStream& ts, const Range& r)
1860{
1861 return ts << "Range: " << "start: " << r.startPosition() << " end: " << r.endPosition();
1862}
1863
1864} // namespace WebCore
1865
1866#if ENABLE(TREE_DEBUGGING)
1867
1868void showTree(const WebCore::Range* range)
1869{
1870 if (range && range->boundaryPointsValid()) {
1871 range->startContainer().showTreeAndMark(&range->startContainer(), "S", &range->endContainer(), "E");
1872 fprintf(stderr, "start offset: %d, end offset: %d\n", range->startOffset(), range->endOffset());
1873 }
1874}
1875
1876#endif
1877