Reviewed by John
[WebKit-https.git] / WebCore / khtml / editing / visible_position.cpp
1 /*
2  * Copyright (C) 2004 Apple Computer, Inc.  All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE COMPUTER, INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
24  */
25
26 #include "visible_position.h"
27
28 #include "misc/htmltags.h"
29 #include "rendering/render_line.h"
30 #include "rendering/render_object.h"
31 #include "rendering/render_text.h"
32 #include "xml/dom2_rangeimpl.h"
33 #include "xml/dom_nodeimpl.h"
34 #include "xml/dom_textimpl.h"
35
36 #if APPLE_CHANGES
37 #include "KWQAssertions.h"
38 #include "KWQLogging.h"
39 #else
40 #define ASSERT(assertion) assert(assertion)
41 #define LOG(channel, formatAndArgs...) ((void)0)
42 #endif
43
44 using DOM::CharacterDataImpl;
45 using DOM::NodeImpl;
46 using DOM::offsetInCharacters;
47 using DOM::Position;
48 using DOM::Range;
49 using DOM::RangeImpl;
50 using DOM::StayInBlock;
51 using DOM::TextImpl;
52
53 namespace khtml {
54
55 VisiblePosition::VisiblePosition(NodeImpl *node, long offset, EAffinity affinity)
56 {
57     Position pos = Position(node, offset);
58
59     // A first step toward eliminating the affinity parameter.
60     // For <br> 0, it's important not to move past the <br>.
61     if (node && node->id() == ID_BR && offset == 0)
62         affinity = UPSTREAM;
63
64     switch (affinity) {
65         case UPSTREAM:
66             initUpstream(pos);
67             break;
68         case DOWNSTREAM:
69             initDownstream(pos);
70             break;
71         default:
72             ASSERT_NOT_REACHED();
73             break;
74     }
75 }
76
77 VisiblePosition::VisiblePosition(const Position &pos, EAffinity affinity)
78 {
79     // A first step toward eliminating the affinity parameter.
80     // For <br> 0, it's important not to move past the <br>.
81     if (pos.node() && pos.node()->id() == ID_BR && pos.offset() == 0)
82         affinity = UPSTREAM;
83
84     switch (affinity) {
85         case UPSTREAM:
86             initUpstream(pos);
87             break;
88         case DOWNSTREAM:
89             initDownstream(pos);
90             break;
91         default:
92             ASSERT_NOT_REACHED();
93             break;
94     }
95 }
96
97 void VisiblePosition::initUpstream(const Position &pos)
98 {
99     Position deepPos = deepEquivalent(pos);
100
101     if (isCandidate(deepPos)) {
102         m_deepPosition = deepPos;
103         Position next = nextVisiblePosition(deepPos);
104         if (next.isNotNull()) {
105             Position previous = previousVisiblePosition(next);
106             if (previous.isNotNull())
107                 m_deepPosition = previous;
108         }
109     }
110     else {
111         Position previous = previousVisiblePosition(deepPos);
112         if (previous.isNotNull()) {
113             m_deepPosition = previous;
114         }
115         else {
116             Position next = nextVisiblePosition(deepPos);
117             if (next.isNotNull())
118                 m_deepPosition = next;
119         }
120     }
121 }
122
123 void VisiblePosition::initDownstream(const Position &pos)
124 {
125     Position deepPos = deepEquivalent(pos);
126
127     if (isCandidate(deepPos)) {
128         m_deepPosition = deepPos;
129         Position previous = previousVisiblePosition(deepPos);
130         if (previous.isNotNull()) {
131             Position next = nextVisiblePosition(previous);
132             if (next.isNotNull())
133                 m_deepPosition = next;
134         }
135     }
136     else {
137         Position next = nextVisiblePosition(deepPos);
138         if (next.isNotNull()) {
139             m_deepPosition = next;
140         }
141         else {
142             Position previous = previousVisiblePosition(deepPos);
143             if (previous.isNotNull())
144                 m_deepPosition = previous;
145         }
146     }
147 }
148
149 VisiblePosition VisiblePosition::next() const
150 {
151     VisiblePosition result;
152     result.m_deepPosition = nextVisiblePosition(m_deepPosition);
153     return result;
154 }
155
156 VisiblePosition VisiblePosition::previous() const
157 {
158     VisiblePosition result;
159     result.m_deepPosition = previousVisiblePosition(m_deepPosition);
160     return result;
161 }
162
163 Position VisiblePosition::previousVisiblePosition(const Position &pos)
164 {
165     if (pos.isNull() || atStart(pos))
166         return Position();
167
168     Position test = deepEquivalent(pos);
169     Position downstreamTest = test.downstream(StayInBlock);
170     bool acceptAnyVisiblePosition = !isCandidate(test);
171
172     Position current = test;
173     while (!atStart(current)) {
174         current = previousPosition(current);
175         if (isCandidate(current) && (acceptAnyVisiblePosition || (downstreamTest != current.downstream(StayInBlock)))) {
176             return current;
177         }
178     }
179     
180     return Position();
181 }
182
183 Position VisiblePosition::nextVisiblePosition(const Position &pos)
184 {
185     if (pos.isNull() || atEnd(pos))
186         return Position();
187
188     Position test = deepEquivalent(pos);
189     bool acceptAnyVisiblePosition = !isCandidate(test);
190
191     Position current = test;
192     Position downstreamTest = test.downstream(StayInBlock);
193     while (!atEnd(current)) {
194         current = nextPosition(current);
195         if (isCandidate(current) && (acceptAnyVisiblePosition || (downstreamTest != current.downstream(StayInBlock)))) {
196             return current;
197         }
198     }
199     
200     return Position();
201 }
202
203 Position VisiblePosition::previousPosition(const Position &pos)
204 {
205     if (pos.isNull())
206         return pos;
207     
208     Position result;
209
210     if (pos.offset() <= 0) {
211         NodeImpl *prevNode = pos.node()->traversePreviousNode();
212         if (prevNode)
213             result = Position(prevNode, prevNode->maxOffset());
214     }
215     else {
216         result = Position(pos.node(), pos.offset() - 1);
217     }
218     
219     return result;
220 }
221
222 Position VisiblePosition::nextPosition(const Position &pos)
223 {
224     if (pos.isNull())
225         return pos;
226     
227     Position result;
228
229     if (pos.offset() >= pos.node()->maxOffset()) {
230         NodeImpl *nextNode = pos.node()->traverseNextNode();
231         if (nextNode)
232             result = Position(nextNode, 0);
233     }
234     else {
235         result = Position(pos.node(), pos.offset() + 1);
236     }
237     
238     return result;
239 }
240
241 bool VisiblePosition::atStart(const Position &pos)
242 {
243     if (pos.isNull())
244         return true;
245
246     return pos.offset() <= 0 && pos.node()->previousLeafNode() == 0;
247 }
248
249 bool VisiblePosition::atEnd(const Position &pos)
250 {
251     if (pos.isNull())
252         return true;
253
254     return pos.offset() >= pos.node()->maxOffset() && pos.node()->nextLeafNode() == 0;
255 }
256
257 bool VisiblePosition::isCandidate(const Position &pos)
258 {
259     if (pos.isNull())
260         return false;
261         
262     RenderObject *renderer = pos.node()->renderer();
263     if (!renderer)
264         return false;
265     
266     if (renderer->style()->visibility() != VISIBLE)
267         return false;
268
269     if (renderer->isReplaced())
270         // return true for replaced elements
271         return pos.offset() == 0 || pos.offset() == 1;
272
273     if (renderer->isBR()) {
274         if (pos.offset() == 0) {
275             InlineBox* box = static_cast<RenderText*>(renderer)->firstTextBox();
276             if (box) {
277                 // return true for offset 0 into BR element on a line by itself
278                 RootInlineBox* root = box->root();
279                 if (root)
280                     return root->firstLeafChild() == box && root->lastLeafChild() == box;
281             }
282         }   
283         return false;
284     }
285     
286     if (renderer->isText()) {
287         RenderText *textRenderer = static_cast<RenderText *>(renderer);
288         for (InlineTextBox *box = textRenderer->firstTextBox(); box; box = box->nextTextBox()) {
289             if (pos.offset() >= box->m_start && pos.offset() <= box->m_start + box->m_len) {
290                 // return true if in a text node
291                 return true;
292             }
293             else if (pos.offset() < box->m_start) {
294                 // The offset we're looking for is before this node
295                 // this means the offset must be in content that is
296                 // not rendered. Return false.
297                 return false;
298             }
299         }
300     }
301     
302     if (renderer->isBlockFlow() && !renderer->firstChild() && (renderer->height() || pos.node()->id() == ID_BODY))
303         // return true for offset 0 into rendered blocks that are empty of rendered kids, but have a height
304         return pos.offset() == 0;
305     
306     return false;
307 }
308
309 Position VisiblePosition::deepEquivalent(const Position &pos)
310 {
311     NodeImpl *node = pos.node();
312     long offset = pos.offset();
313
314     if (!node)
315         return Position();
316     
317     if (isAtomicNode(node))
318         return pos;
319
320     if (offset >= (long)node->childNodeCount()) {
321         do {
322             NodeImpl *child = node->lastChild();
323             if (!child)
324                 break;
325             node = child;
326         } while (!isAtomicNode(node));
327         return Position(node, node->caretMaxOffset());
328     }
329     
330     node = node->childNode(offset);
331     ASSERT(node);
332     while (!isAtomicNode(node)) {
333         NodeImpl *child = node->firstChild();
334         if (!child)
335             break;
336         node = child;
337     }
338     return Position(node, 0);
339 }
340
341 Position VisiblePosition::downstreamDeepEquivalent() const
342 {
343     Position pos = m_deepPosition;
344     
345     if (pos.isNull() || atEnd(pos))
346         return pos;
347
348     Position downstreamTest = pos.downstream(StayInBlock);
349
350     Position current = pos;
351     while (!atEnd(current)) {
352         current = nextPosition(current);
353         if (isCandidate(current)) {
354             if (downstreamTest != current.downstream(StayInBlock))
355                 break;
356             pos = current;
357         }
358     }
359     
360     return pos;
361 }
362
363 Position VisiblePosition::rangeCompliantEquivalent(const Position &pos)
364 {
365     NodeImpl *node = pos.node();
366     if (!node)
367         return Position();
368     
369     // FIXME: This clamps out-of-range values.
370     // Instead we should probably assert, and not use such values.
371
372     long offset = pos.offset();
373     if (!offsetInCharacters(node->nodeType()) && isAtomicNode(node) && offset > 0)
374         return Position(node->parentNode(), node->nodeIndex() + 1);
375
376     return Position(node, kMax(0L, kMin(offset, maxOffset(node))));
377 }
378
379 long VisiblePosition::maxOffset(const NodeImpl *node)
380 {
381     return offsetInCharacters(node->nodeType()) ? (long)static_cast<const CharacterDataImpl *>(node)->length() : (long)node->childNodeCount();
382 }
383
384 bool VisiblePosition::isAtomicNode(const NodeImpl *node)
385 {
386     return node && (!node->hasChildNodes() || (node->id() == ID_OBJECT && node->renderer() && node->renderer()->isReplaced()));
387 }
388
389 QChar VisiblePosition::character() const
390 {
391     Position pos = position();
392     NodeImpl *node = pos.node();
393     if (!node || !node->isTextNode()) {
394         return QChar();
395     }
396     TextImpl *textNode = static_cast<TextImpl *>(pos.node());
397     long offset = pos.offset();
398     if ((unsigned)offset >= textNode->length()) {
399         return QChar();
400     }
401     return textNode->data()[offset];
402 }
403
404 void VisiblePosition::debugPosition(const char *msg) const
405 {
406     if (isNull())
407         fprintf(stderr, "Position [%s]: null\n", msg);
408     else
409         fprintf(stderr, "Position [%s]: %s [%p] at %d\n", msg, getTagName(m_deepPosition.node()->id()).string().latin1(), m_deepPosition.node(), m_deepPosition.offset());
410 }
411
412 #ifndef NDEBUG
413 void VisiblePosition::formatForDebugger(char *buffer, unsigned length) const
414 {
415     m_deepPosition.formatForDebugger(buffer, length);
416 }
417 #endif
418
419 Range makeRange(const VisiblePosition &start, const VisiblePosition &end)
420 {
421     Position s = start.position();
422     Position e = end.position();
423     return Range(s.node(), s.offset(), e.node(), e.offset());
424 }
425
426 VisiblePosition startVisiblePosition(const Range &r)
427 {
428     return VisiblePosition(r.startContainer().handle(), r.startOffset());
429 }
430
431 VisiblePosition endVisiblePosition(const Range &r)
432 {
433     return VisiblePosition(r.endContainer().handle(), r.endOffset());
434 }
435
436 bool setStart(Range &r, const VisiblePosition &c)
437 {
438     RangeImpl *ri = r.handle();
439     if (!ri)
440         return false;
441     Position p = c.position();
442     int code = 0;
443     ri->setStart(p.node(), p.offset(), code);
444     return code == 0;
445 }
446
447 bool setEnd(Range &r, const VisiblePosition &c)
448 {
449     RangeImpl *ri = r.handle();
450     if (!ri)
451         return false;
452     Position p = c.position();
453     int code = 0;
454     ri->setEnd(p.node(), p.offset(), code);
455     return code == 0;
456 }
457
458 bool visiblePositionsOnDifferentLines(const VisiblePosition &pos1, const VisiblePosition &pos2)
459 {
460     if (pos1.isNull() || pos2.isNull())
461         return false;
462     if (pos1 == pos2)
463         return false;
464     
465     Position p1 = pos1.deepEquivalent();
466     Position p2 = pos2.deepEquivalent();
467     RenderObject *r1 = p1.node()->renderer();
468     RenderObject *r2 = p2.node()->renderer();
469     if (r1->isBlockFlow() || r2->isBlockFlow())
470         return r1 == r2 ? false : true;
471     InlineBox *b1 = r1 ? r1->inlineBox(p1.offset()) : 0;
472     InlineBox *b2 = r2 ? r2->inlineBox(p2.offset()) : 0;
473     return (b1 && b2 && b1->root() != b2->root());
474 }
475
476 enum EBlockRelationship { 
477     NoBlockRelationship, 
478     SameBlockRelationship, 
479     PeerBlockRelationship, 
480     AncestorBlockRelationship, 
481     DescendantBlockRelationship, 
482     OtherBlockRelationship 
483 };
484
485 static EBlockRelationship blockRelationship(const VisiblePosition &pos1, const VisiblePosition &pos2)
486 {
487     if (pos1.isNull() || pos2.isNull())
488         return NoBlockRelationship;
489     if (pos1 == pos2)
490         return SameBlockRelationship;
491
492     Position p1 = pos1.deepEquivalent();
493     Position p2 = pos2.deepEquivalent();
494     NodeImpl *b1 = p1.node()->enclosingBlockFlowElement();
495     NodeImpl *b2 = p2.node()->enclosingBlockFlowElement();
496     if (!b1 || !b2)
497         return NoBlockRelationship;
498     if (b1 == b2) 
499         return SameBlockRelationship;
500     if (b1->parentNode() == b2->parentNode())
501         return PeerBlockRelationship;
502     if (b2->isAncestor(b1))
503         return AncestorBlockRelationship;
504     if (b1->isAncestor(b2))
505         return DescendantBlockRelationship;
506     return OtherBlockRelationship;
507 }
508
509 bool visiblePositionsInDifferentBlocks(const VisiblePosition &pos1, const VisiblePosition &pos2)
510 {
511     switch (blockRelationship(pos1, pos2)) {
512         case NoBlockRelationship:
513         case SameBlockRelationship:
514             return false;
515         case PeerBlockRelationship:
516         case AncestorBlockRelationship:
517         case DescendantBlockRelationship:
518         case OtherBlockRelationship:
519             return true;
520     }
521     ASSERT_NOT_REACHED();
522     return false;
523 }
524
525 bool isFirstVisiblePositionOnLine(const VisiblePosition &pos)
526 {
527     if (pos.isNull())
528         return false;
529         
530     VisiblePosition previous = pos.previous();
531     return previous.isNull() || visiblePositionsOnDifferentLines(pos, previous);
532 }
533
534 bool isFirstVisiblePositionInBlock(const VisiblePosition &pos)
535 {
536     if (pos.isNull())
537         return false;
538         
539     VisiblePosition previous = pos.previous();
540     if (previous.isNull())
541         return true;
542     
543     switch (blockRelationship(pos, previous)) {
544         case NoBlockRelationship:
545         case SameBlockRelationship:
546         case AncestorBlockRelationship:
547         case OtherBlockRelationship:
548             return false;
549         case PeerBlockRelationship:
550         case DescendantBlockRelationship:
551             return true;
552     }
553     ASSERT_NOT_REACHED();
554     return false;
555 }
556
557 bool isFirstVisiblePositionInNode(const VisiblePosition &pos, const NodeImpl *node)
558 {
559     if (pos.isNull())
560         return false;
561         
562     VisiblePosition previous = pos.previous();
563     return previous.isNull() || !previous.deepEquivalent().node()->isAncestor(node);
564 }
565
566 bool isLastVisiblePositionOnLine(const VisiblePosition &pos)
567 {
568     if (pos.isNull())
569         return false;
570         
571     VisiblePosition next = pos.next();
572     return next.isNull() || visiblePositionsOnDifferentLines(pos, next);
573 }
574
575 bool isLastVisiblePositionInBlock(const VisiblePosition &pos)
576 {
577     if (pos.isNull())
578         return false;
579         
580     VisiblePosition next = pos.next();
581     if (next.isNull())
582         return true;
583     
584     switch (blockRelationship(pos, next)) {
585         case NoBlockRelationship:
586         case SameBlockRelationship:
587         case AncestorBlockRelationship:
588         case DescendantBlockRelationship:
589         case OtherBlockRelationship:
590             return false;
591         case PeerBlockRelationship:
592             return true;
593     }
594     ASSERT_NOT_REACHED();
595     return false;
596 }
597
598 bool isLastVisiblePositionInNode(const VisiblePosition &pos, const NodeImpl *node)
599 {
600     if (pos.isNull())
601         return false;
602         
603     VisiblePosition next = pos.next();
604     return next.isNull() || !next.deepEquivalent().node()->isAncestor(node);
605 }
606
607 }  // namespace DOM