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