2ab359164940bfb9e5ff4d2f612d3711d09b9845
[WebKit.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::UsingComposedCharacters;
48 using DOM::Position;
49 using DOM::Range;
50 using DOM::RangeImpl;
51 using DOM::TextImpl;
52
53 namespace khtml {
54
55 VisiblePosition::VisiblePosition(const Position &pos, EAffinity affinity, EInitHint initHint)
56 {
57     init(pos, initHint, affinity);
58 }
59
60 VisiblePosition::VisiblePosition(NodeImpl *node, long offset, EAffinity affinity, EInitHint initHint)
61 {
62     init(Position(node, offset), initHint, affinity);
63 }
64
65 VisiblePosition::VisiblePosition(const VisiblePosition &other)
66 {
67     m_deepPosition = other.m_deepPosition;
68     m_affinity = other.m_affinity;
69 }
70
71 void VisiblePosition::init(const Position &pos, EInitHint initHint, EAffinity affinity)
72 {
73     m_affinity = affinity;
74
75     // A first step toward eliminating the initHint parameter.
76     // For <br> 0, it's important not to move past the <br>.
77     if (pos.node() && pos.node()->id() == ID_BR && pos.offset() == 0)
78         initHint = INIT_UP;
79
80     switch (initHint) {
81         case INIT_UP:
82             initUpstream(pos);
83             break;
84         case INIT_DOWN:
85             initDownstream(pos);
86             break;
87         default:
88             ASSERT_NOT_REACHED();
89             break;
90     }
91 }
92
93 void VisiblePosition::initUpstream(const Position &pos)
94 {
95     Position deepPos = deepEquivalent(pos);
96
97     if (isCandidate(deepPos)) {
98         m_deepPosition = deepPos;
99         Position next = nextVisiblePosition(deepPos);
100         if (next.isNotNull()) {
101             Position previous = previousVisiblePosition(next);
102             if (previous.isNotNull())
103                 m_deepPosition = previous;
104         }
105     }
106     else {
107         Position previous = previousVisiblePosition(deepPos);
108         if (previous.isNotNull()) {
109             m_deepPosition = previous;
110         } else {
111             Position next = nextVisiblePosition(deepPos);
112             if (next.isNotNull())
113                 m_deepPosition = next;
114         }
115     }
116 }
117
118 static bool isRenderedBR(NodeImpl *node)
119 {
120     if (!node)
121         return false;
122
123     RenderObject *renderer = node->renderer();
124     if (!renderer)
125         return false;
126     
127     if (renderer->style()->visibility() != VISIBLE)
128         return false;
129
130     if (renderer->isBR())
131         return true;
132
133     return false;
134 }
135
136 void VisiblePosition::initDownstream(const Position &pos)
137 {
138     Position deepPos = deepEquivalent(pos);
139
140     if (isCandidate(deepPos)) {
141         m_deepPosition = deepPos;
142         Position previous = previousVisiblePosition(deepPos);
143         if (previous.isNotNull()) {
144             Position next = nextVisiblePosition(previous);
145             if (next.isNotNull())
146                 m_deepPosition = next;
147         }
148     } else {
149         Position next = nextVisiblePosition(deepPos);
150         if (next.isNotNull()) {
151             m_deepPosition = next;
152         } else if (isRenderedBR(deepPos.node()) && deepPos.offset() == 1) {
153             m_deepPosition = deepPos;
154         } else {
155             Position previous = previousVisiblePosition(deepPos);
156             if (previous.isNotNull())
157                 m_deepPosition = previous;
158         }
159     }
160 }
161
162 VisiblePosition VisiblePosition::next() const
163 {
164     VisiblePosition result = VisiblePosition(nextVisiblePosition(m_deepPosition), m_affinity);
165     setAffinityUsingLinePosition(result);
166     return result;
167 }
168
169 VisiblePosition VisiblePosition::previous() const
170 {
171     VisiblePosition result =  VisiblePosition(previousVisiblePosition(m_deepPosition), DOWNSTREAM);
172
173 #ifndef NDEBUG
174     // we should always be able to make the affinity DOWNSTREAM, because going previous from an
175     // UPSTREAM position can never yield another UPSTREAM position (unless line wrap length is 0!).
176     if (result.isNotNull() && m_affinity == UPSTREAM) {
177         VisiblePosition temp = result;
178         temp.setAffinity(UPSTREAM);
179         ASSERT(!visiblePositionsOnDifferentLines(temp, result));
180     }
181 #endif
182     return result;
183 }
184
185 Position VisiblePosition::previousVisiblePosition(const Position &pos)
186 {
187     if (pos.isNull() || pos.atStart())
188         return Position();
189
190     Position test = deepEquivalent(pos);
191     Position downstreamTest = test.downstream();
192     bool acceptAnyVisiblePosition = !isCandidate(test);
193
194     Position current = test;
195     while (!current.atStart()) {
196         current = current.previous(UsingComposedCharacters);
197         if (isCandidate(current) && (acceptAnyVisiblePosition || (downstreamTest != current.downstream()))) {
198             return current;
199         }
200     }
201     
202     return Position();
203 }
204
205 Position VisiblePosition::nextVisiblePosition(const Position &pos)
206 {
207     if (pos.isNull() || pos.atEnd())
208         return Position();
209
210     Position test = deepEquivalent(pos);
211     bool acceptAnyVisiblePosition = !isCandidate(test);
212
213     Position current = test;
214     Position downstreamTest = test.downstream();
215     while (!current.atEnd()) {
216         current = current.next(UsingComposedCharacters);
217         if (isCandidate(current) && (acceptAnyVisiblePosition || (downstreamTest != current.downstream()))) {
218             return current;
219         }
220     }
221     
222     return Position();
223 }
224
225 bool VisiblePosition::isCandidate(const Position &pos)
226 {
227     if (pos.isNull())
228         return false;
229         
230     RenderObject *renderer = pos.node()->renderer();
231     if (!renderer)
232         return false;
233     
234     if (renderer->style()->visibility() != VISIBLE)
235         return false;
236
237     if (renderer->isReplaced())
238         // return true for replaced elements
239         return pos.offset() == 0 || pos.offset() == 1;
240
241     if (renderer->isBR()) {
242         if (pos.offset() == 0) {
243             InlineBox* box = static_cast<RenderText*>(renderer)->firstTextBox();
244             if (box) {
245                 // return true for offset 0 into BR element on a line by itself
246                 RootInlineBox* root = box->root();
247                 if (root)
248                     return root->firstLeafChild() == box && root->lastLeafChild() == box;
249             }
250         }   
251         return false;
252     }
253     
254     if (renderer->isText()) {
255         RenderText *textRenderer = static_cast<RenderText *>(renderer);
256         for (InlineTextBox *box = textRenderer->firstTextBox(); box; box = box->nextTextBox()) {
257             if (pos.offset() >= box->m_start && pos.offset() <= box->m_start + box->m_len) {
258                 // return true if in a text node
259                 return true;
260             }
261         }
262     }
263     
264     if (renderer->isBlockFlow() && (!renderer->firstChild() || !pos.node()->firstChild()) && 
265        (renderer->height() || pos.node()->id() == ID_BODY)) {
266         // return true for offset 0 into rendered blocks that are empty of rendered kids, but have a height
267         return pos.offset() == 0;
268     }
269     
270     return false;
271 }
272
273 Position VisiblePosition::deepEquivalent(const Position &pos)
274 {
275     NodeImpl *node = pos.node();
276     long offset = pos.offset();
277
278     if (!node)
279         return Position();
280     
281     if (isAtomicNode(node))
282         return pos;
283
284     if (offset >= (long)node->childNodeCount()) {
285         do {
286             NodeImpl *child = node->lastChild();
287             if (!child)
288                 break;
289             node = child;
290         } while (!isAtomicNode(node));
291         return Position(node, node->caretMaxOffset());
292     }
293     
294     node = node->childNode(offset);
295     ASSERT(node);
296     while (!isAtomicNode(node)) {
297         NodeImpl *child = node->firstChild();
298         if (!child)
299             break;
300         node = child;
301     }
302     return Position(node, 0);
303 }
304
305 Position VisiblePosition::downstreamDeepEquivalent() const
306 {
307     Position pos = m_deepPosition;
308     
309     if (pos.isNull() || pos.atEnd())
310         return pos;
311
312     Position downstreamTest = pos.downstream();
313
314     Position current = pos;
315     while (!current.atEnd()) {
316         current = current.next(UsingComposedCharacters);
317         if (isCandidate(current)) {
318             if (downstreamTest != current.downstream())
319                 break;
320             pos = current;
321         }
322     }
323     
324     return pos;
325 }
326
327 Position VisiblePosition::rangeCompliantEquivalent(const Position &pos)
328 {
329     NodeImpl *node = pos.node();
330     if (!node)
331         return Position();
332     
333     // FIXME: This clamps out-of-range values.
334     // Instead we should probably assert, and not use such values.
335
336     long offset = pos.offset();
337     if (!offsetInCharacters(node->nodeType()) && isAtomicNode(node) && offset > 0)
338         return Position(node->parentNode(), node->nodeIndex() + 1);
339
340     return Position(node, kMax(0L, kMin(offset, maxOffset(node))));
341 }
342
343 long VisiblePosition::maxOffset(const NodeImpl *node)
344 {
345     return offsetInCharacters(node->nodeType()) ? (long)static_cast<const CharacterDataImpl *>(node)->length() : (long)node->childNodeCount();
346 }
347
348 bool VisiblePosition::isAtomicNode(const NodeImpl *node)
349 {
350     return node && (!node->hasChildNodes() || (node->id() == ID_OBJECT && node->renderer() && node->renderer()->isReplaced()));
351 }
352
353 QChar VisiblePosition::character() const
354 {
355     Position pos = position();
356     NodeImpl *node = pos.node();
357     if (!node || !node->isTextNode()) {
358         return QChar();
359     }
360     TextImpl *textNode = static_cast<TextImpl *>(pos.node());
361     long offset = pos.offset();
362     if ((unsigned)offset >= textNode->length()) {
363         return QChar();
364     }
365     return textNode->data()[offset];
366 }
367
368 bool isEqualIgnoringAffinity(const VisiblePosition &a, const VisiblePosition &b)
369 {
370     bool result = a.m_deepPosition == b.m_deepPosition;
371     if (result) {
372         // We want to catch cases where positions are equal, but affinities are not, since
373         // this is very likely a bug, given the places where this call is used. The difference
374         // is very likely due to code that set the affinity on a VisiblePosition "by hand" and 
375         // did so incorrectly.
376         ASSERT(a.m_affinity == b.m_affinity);
377     }
378     return result;
379 }
380
381 bool isNotEqualIgnoringAffinity(const VisiblePosition &a, const VisiblePosition &b)
382 {
383     return !isEqualIgnoringAffinity(a, b);
384 }
385
386 void VisiblePosition::debugPosition(const char *msg) const
387 {
388     if (isNull())
389         fprintf(stderr, "Position [%s]: null\n", msg);
390     else
391         fprintf(stderr, "Position [%s]: %s [%p] at %ld\n", msg, m_deepPosition.node()->nodeName().string().latin1(), m_deepPosition.node(), m_deepPosition.offset());
392 }
393
394 #ifndef NDEBUG
395 void VisiblePosition::formatForDebugger(char *buffer, unsigned length) const
396 {
397     m_deepPosition.formatForDebugger(buffer, length);
398 }
399 #endif
400
401 Range makeRange(const VisiblePosition &start, const VisiblePosition &end)
402 {
403     Position s = start.position();
404     Position e = end.position();
405     return Range(s.node(), s.offset(), e.node(), e.offset());
406 }
407
408 VisiblePosition startVisiblePosition(const Range &r, EAffinity affinity)
409 {
410     return VisiblePosition(r.startContainer().handle(), r.startOffset(), affinity);
411 }
412
413 VisiblePosition endVisiblePosition(const Range &r, EAffinity affinity)
414 {
415     return VisiblePosition(r.endContainer().handle(), r.endOffset(), affinity);
416 }
417
418 bool setStart(Range &r, const VisiblePosition &c)
419 {
420     RangeImpl *ri = r.handle();
421     if (!ri)
422         return false;
423     Position p = c.position();
424     int code = 0;
425     ri->setStart(p.node(), p.offset(), code);
426     return code == 0;
427 }
428
429 bool setEnd(Range &r, const VisiblePosition &c)
430 {
431     RangeImpl *ri = r.handle();
432     if (!ri)
433         return false;
434     Position p = c.position();
435     int code = 0;
436     ri->setEnd(p.node(), p.offset(), code);
437     return code == 0;
438 }
439
440 void setAffinityUsingLinePosition(VisiblePosition &pos)
441 {
442     // When not moving across line wrap, make sure to end up with DOWNSTREAM affinity.  
443     if (pos.isNotNull() && pos.affinity() == UPSTREAM) {
444         VisiblePosition temp(pos);
445         temp.setAffinity(DOWNSTREAM);
446         if (!visiblePositionsOnDifferentLines(temp, pos))
447             pos.setAffinity(DOWNSTREAM);
448     }
449 }
450
451 DOM::NodeImpl *enclosingBlockFlowElement(const VisiblePosition &vp)
452 {
453     if (vp.isNull())
454         return NULL;
455
456     return vp.position().node()->enclosingBlockFlowElement();
457 }
458
459 bool visiblePositionsOnDifferentLines(const VisiblePosition &pos1, const VisiblePosition &pos2)
460 {
461     if (pos1.isNull() || pos2.isNull())
462         return false;
463     if (pos1 == pos2)
464         return false;
465     
466     Position p1 = pos1.deepEquivalent();
467     Position p2 = pos2.deepEquivalent();
468     RenderObject *r1 = p1.node()->renderer();
469     RenderObject *r2 = p2.node()->renderer();
470     if (r1->isBlockFlow() || r2->isBlockFlow())
471         return r1 == r2 ? false : true;
472     InlineBox *b1 = r1 ? r1->inlineBox(p1.offset(), pos1.affinity()) : 0;
473     InlineBox *b2 = r2 ? r2->inlineBox(p2.offset(), pos2.affinity()) : 0;
474     return (b1 && b2 && b1->root() != b2->root());
475 }
476
477 enum EBlockRelationship { 
478     NoBlockRelationship, 
479     SameBlockRelationship, 
480     PeerBlockRelationship, 
481     AncestorBlockRelationship, 
482     DescendantBlockRelationship, 
483     OtherBlockRelationship 
484 };
485
486 static EBlockRelationship blockRelationship(const VisiblePosition &pos1, const VisiblePosition &pos2)
487 {
488     if (pos1.isNull() || pos2.isNull())
489         return NoBlockRelationship;
490     if (pos1 == pos2)
491         return SameBlockRelationship;
492
493     Position p1 = pos1.deepEquivalent();
494     Position p2 = pos2.deepEquivalent();
495     NodeImpl *b1 = p1.node()->enclosingBlockFlowElement();
496     NodeImpl *b2 = p2.node()->enclosingBlockFlowElement();
497     if (!b1 || !b2)
498         return NoBlockRelationship;
499     if (b1 == b2) 
500         return SameBlockRelationship;
501     if (b1->parentNode() == b2->parentNode())
502         return PeerBlockRelationship;
503     if (b2->isAncestor(b1))
504         return AncestorBlockRelationship;
505     if (b1->isAncestor(b2))
506         return DescendantBlockRelationship;
507     return OtherBlockRelationship;
508 }
509
510 bool visiblePositionsInDifferentBlocks(const VisiblePosition &pos1, const VisiblePosition &pos2)
511 {
512     switch (blockRelationship(pos1, pos2)) {
513         case NoBlockRelationship:
514         case SameBlockRelationship:
515             return false;
516         case PeerBlockRelationship:
517         case AncestorBlockRelationship:
518         case DescendantBlockRelationship:
519         case OtherBlockRelationship:
520             return true;
521     }
522     ASSERT_NOT_REACHED();
523     return false;
524 }
525
526 bool isFirstVisiblePositionOnLine(const VisiblePosition &pos)
527 {
528     if (pos.isNull())
529         return false;
530         
531     VisiblePosition previous = pos.previous();
532     return previous.isNull() || visiblePositionsOnDifferentLines(pos, previous);
533 }
534
535 bool isFirstVisiblePositionInParagraph(const VisiblePosition &pos)
536 {
537     if (pos.isNull())
538         return false;
539
540     return pos.deepEquivalent().upstream().node()->id() == ID_BR || isFirstVisiblePositionInBlock(pos);
541 }
542
543 bool isFirstVisiblePositionInBlock(const VisiblePosition &pos)
544 {
545     if (pos.isNull())
546         return false;
547
548     Position upstream = pos.deepEquivalent().upstream();
549     return upstream.node()->isBlockFlow() && upstream.offset() == 0;
550 }
551
552 bool isFirstVisiblePositionInNode(const VisiblePosition &pos, const NodeImpl *node)
553 {
554     if (pos.isNull())
555         return false;
556         
557     VisiblePosition previous = pos.previous();
558     return previous.isNull() || !previous.deepEquivalent().node()->isAncestor(node);
559 }
560
561 bool isLastVisiblePositionOnLine(const VisiblePosition &pos)
562 {
563     if (pos.isNull())
564         return false;
565         
566     VisiblePosition next = pos.next();
567     return next.isNull() || visiblePositionsOnDifferentLines(pos, next);
568 }
569
570 bool isLastVisiblePositionInParagraph(const VisiblePosition &pos)
571 {
572     if (pos.isNull())
573         return false;
574
575     return pos.deepEquivalent().downstream().node()->id() == ID_BR || isLastVisiblePositionInBlock(pos);
576 }
577
578 bool isLastVisiblePositionInBlock(const VisiblePosition &pos)
579 {
580     if (pos.isNull())
581         return false;
582         
583     VisiblePosition next = pos.next();
584     if (next.isNull())
585         return true;
586     
587     switch (blockRelationship(pos, next)) {
588         case NoBlockRelationship:
589         case SameBlockRelationship:
590         case AncestorBlockRelationship:
591             return false;
592         case OtherBlockRelationship:
593         case PeerBlockRelationship:
594         case DescendantBlockRelationship:
595             return true;
596     }
597     ASSERT_NOT_REACHED();
598     return false;
599 }
600
601 bool isLastVisiblePositionInNode(const VisiblePosition &pos, const NodeImpl *node)
602 {
603     if (pos.isNull())
604         return false;
605         
606     VisiblePosition next = pos.next();
607     return next.isNull() || !next.deepEquivalent().node()->isAncestor(node);
608 }
609
610 }  // namespace DOM